On 09/26/2012 09:56 AM, Paolo Bonzini wrote: > HBitmaps provides an array of bits. The bits are stored as usual in an > array of unsigned longs, but HBitmap is also optimized to provide fast > iteration over set bits; going from one bit to the next is O(logB n) > worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough > that the number of levels is in fact fixed.
> +++ b/hbitmap.c > @@ -0,0 +1,400 @@ > +/* > + * Hierarchical Bitmap Data Type > + * > + * Copyright Red Hat, Inc., 2012 vs. > +++ b/tests/test-hbitmap.c > @@ -0,0 +1,408 @@ > +/* > + * Hierarchical bitmap unit-tests. > + * > + * Copyright (C) 2012 Red Hat Inc. Is there a preferred form for the copyright line? > +++ b/hbitmap.h > @@ -0,0 +1,207 @@ > + > +/* We need to place a sentinel in level 0 to speed up iteration. Thus, > + * we do this instead of HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL. The > + * difference is that it allocates an extra level when HBITMAP_LOG_MAX_SIZE > + * is an exact multiple of BITS_PER_LEVEL. > + */ > +#define HBITMAP_LEVELS ((HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL) + 1) Comment is a bit misleading. Don't you mean: Thus, we do this instead of (HBITMAP_LOG_MAX_SIZE + BITS_PER_LEVEL - 1)/BITS_PER_LEVEL. (aka ceil(1.0*HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL)) -- Eric Blake ebl...@redhat.com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
