Re: [Qemu-devel] [PATCH v2 35/45] add hierarchical bitmap data type and test cases

[Eric Blake]

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   address@hidden    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature