From be58721dbf882fa8830f3669f499b0a5b501e90f Mon Sep 17 00:00:00 2001 From: John Snow Date: Fri, 17 Apr 2015 19:49:55 -0400 Subject: hbitmap: add hbitmap_merge 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 Reviewed-by: Max Reitz Reviewed-by: Eric Blake Reviewed-by: Stefan Hajnoczi Message-id: 1429314609-29776-8-git-send-email-jsnow@redhat.com Signed-off-by: Stefan Hajnoczi Signed-off-by: Kevin Wolf --- include/qemu/hbitmap.h | 13 +++++++++++++ 1 file changed, 13 insertions(+) (limited to 'include/qemu') 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. * -- cgit v1.1