[Libguestfs] [PATCH nbdkit v2 1/4] common/bitmap: Add bitmap_next function and tests.
Eric Blake
eblake at redhat.com
Thu Jan 3 02:32:49 UTC 2019
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>
More information about the Libguestfs
mailing list