On 04/08/2015 04:19 PM, John Snow wrote: > We add a bitmap merge operation to assist in error cases > where we wish to combine two bitmaps together. > > This is algorithmically O(bits) provided HBITMAP_LEVELS remains > constant. For a full bitmap on a 64bit machine: > sum(bits/64^k, k, 0, HBITMAP_LEVELS) ~= 1.01587 * bits > > We may be able to improve running speed for particularly sparse > bitmaps by using iterators, but the running time for dense maps > will be worse. > > We present the simpler solution first, and we can refine it later > if needed. > > Signed-off-by: John Snow <js...@redhat.com> > Reviewed-by: Max Reitz <mre...@redhat.com> > Reviewed-by: Stefan Hajnoczi <stefa...@redhat.com> > ---
> /**
> + * hbitmap_merge:
> + * @a: The bitmap to store the result in.
> + * @b: The bitmap to merge into @a.
> + *
> + * Merge two bitmaps together.
> + * A := A (BITOR) B.
> + * B is left unmodified.
> + */
> +bool hbitmap_merge(HBitmap *a, const HBitmap *b);
No mention of what the return value means.
> +bool hbitmap_merge(HBitmap *a, const HBitmap *b)
> +{
> + int i, j;
> +
> + if ((a->size != b->size) || (a->granularity != b->granularity)) {
> + return false;
> + }
> +
> + if (hbitmap_count(b) == 0) {
> + return true;
> + }
> +
> + /* This merge is O(size), as BITS_PER_LONG and HBITMAP_LEVELS are
> constant.
> + * It may be possible to improve running times for sparsely populated
> maps
> + * by using hbitmap_iter_next, but this is suboptimal for dense maps.
> + */
> + for (i = HBITMAP_LEVELS - 1; i >= 0; i--) {
> + for (j = 0; j < a->sizes[i]; j++) {
j is 'int', but a->sizes[i] is uint64_t. If we can ever have a bitmap
large enough that its size exceeds 2G at the largest level, then we have
an inf-loop due to overflow problem.
I'd feel safer if you make j be uint64_t here; but it might also be
possible to fix 6/21 to store sizes in a smaller data type along with
appropriate assertions that our bitmaps are never big enough to need a
level with more than 2G size.
--
Eric Blake eblake redhat com +1-919-301-3266
Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
