[Libguestfs] [PATCH nbdkit v2 1/4] common/bitmap: Add bitmap_next function and tests.

[Eric Blake]

On 1/1/19 8:33 AM, Richard W.M. Jones wrote:
> It's useful to be able to search for the next non-zero entry in a
> bitmap.  This commit adds a ‘bitmap_next’ function to do that.
> Because the bitmap is just a uint8_t buffer, using fast string
> functions we should be able to do this quickly even if the bitmap is
> sparse.  (However the actual implementation is not optimized since
> that is quite complicated - see to-do comments in
> common/include/nextnonzero.h).
> 
> I wasn't confident about the correctness of the code and so this
> commit also adds some unit tests covering all of the bitmap code.
> ---

> +#define NBDKIT_NEXTNONZERO_H
> +
> +/* Given a byte buffer, return a pointer to the first non-zero byte,
> + * or return NULL if we reach the end of the buffer.
> + *
> + * XXX: Even with -O3 -mavx2, gcc 8.2.1 makes a terrible job with this

maybe s/makes/does/

> + * loop, compiling it completely naively.  QEMU has an AVX2
> + * implementation of a similar loop.
> + *

> +/* Unit tests of the bitmap code. */
> +

> +
> +  /* Check the values of all bits. */
> +  for (i = j = 0; i < nr_blocks; ++i) {
> +    if (i == blks[j]) { /* previously set bit */
> +      vexp = (j & 1) == 0 ? 1 : (1<<bpb) - 1;
> +      v = bitmap_get_blk (&bm, blks[j], 0);
> +      assert (v == vexp);
> +      ++j;
> +    }
> +    else { /* unset bit, except it to be zero */

s/except/expect/

> +      v = bitmap_get_blk (&bm, i, 0);
> +      assert (v == 0);
> +    }
> +  }
> +

Otherwise looks good.

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3226
Virtualization:  qemu.org | libvirt.org

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: OpenPGP digital signature
URL: <http://listman.redhat.com/archives/libguestfs/attachments/20190102/97ffd0b7/attachment.sig>