| Message ID | 1429314609-29776-8-git-send-email-jsnow@redhat.com |
|---|---|
| State | New |
| Headers | show |
On 18.04.2015 01:49, 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 <jsnow@redhat.com> > --- > include/qemu/hbitmap.h | 13 +++++++++++++ > util/hbitmap.c | 33 +++++++++++++++++++++++++++++++++ > 2 files changed, 46 insertions(+) Reviewed-by: Max Reitz <mreitz@redhat.com>
On 04/17/2015 05:49 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 <jsnow@redhat.com> > --- > include/qemu/hbitmap.h | 13 +++++++++++++ > util/hbitmap.c | 33 +++++++++++++++++++++++++++++++++ > 2 files changed, 46 insertions(+) Reviewed-by: Eric Blake <eblake@redhat.com>
On Fri, Apr 17, 2015 at 07:49:55PM -0400, 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 <jsnow@redhat.com> > --- > include/qemu/hbitmap.h | 13 +++++++++++++ > util/hbitmap.c | 33 +++++++++++++++++++++++++++++++++ > 2 files changed, 46 insertions(+) Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>
diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index 550d7ce..6cb2d0e 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -65,6 +65,19 @@ struct HBitmapIter { HBitmap *hbitmap_alloc(uint64_t size, int granularity); /** + * hbitmap_merge: + * @a: The bitmap to store the result in. + * @b: The bitmap to merge into @a. + * @return true if the merge was successful, + * false if it was not attempted. + * + * Merge two bitmaps together. + * A := A (BITOR) B. + * B is left unmodified. + */ +bool hbitmap_merge(HBitmap *a, const HBitmap *b); + +/** * hbitmap_empty: * @hb: HBitmap to operate on. * diff --git a/util/hbitmap.c b/util/hbitmap.c index 5b78613..150d6e9 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -399,3 +399,36 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity) hb->levels[0][0] |= 1UL << (BITS_PER_LONG - 1); return hb; } + +/** + * Given HBitmaps A and B, let A := A (BITOR) B. + * Bitmap B will not be modified. + * + * @return true if the merge was successful, + * false if it was not attempted. + */ +bool hbitmap_merge(HBitmap *a, const HBitmap *b) +{ + int i; + uint64_t 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++) { + a->levels[i][j] |= b->levels[i][j]; + } + } + + return true; +}
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 <jsnow@redhat.com> --- include/qemu/hbitmap.h | 13 +++++++++++++ util/hbitmap.c | 33 +++++++++++++++++++++++++++++++++ 2 files changed, 46 insertions(+)