From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:53605) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Y3E1y-0004S7-LG for qemu-devel@nongnu.org; Mon, 22 Dec 2014 20:13:04 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Y3E1s-0000x2-Ce for qemu-devel@nongnu.org; Mon, 22 Dec 2014 20:12:58 -0500 Received: from mx1.redhat.com ([209.132.183.28]:56841) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Y3E1s-0000wt-43 for qemu-devel@nongnu.org; Mon, 22 Dec 2014 20:12:52 -0500 From: John Snow Date: Mon, 22 Dec 2014 20:12:16 -0500 Message-Id: <1419297142-24282-8-git-send-email-jsnow@redhat.com> In-Reply-To: <1419297142-24282-1-git-send-email-jsnow@redhat.com> References: <1419297142-24282-1-git-send-email-jsnow@redhat.com> Subject: [Qemu-devel] [PATCH v10 07/13] hbitmap: add hbitmap_merge List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: qemu-devel@nongnu.org Cc: kwolf@redhat.com, famz@redhat.com, John Snow , armbru@redhat.com, mreitz@redhat.com, vsementsov@parallels.com, stefanha@redhat.com 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 --- include/qemu/hbitmap.h | 11 +++++++++++ util/hbitmap.c | 28 ++++++++++++++++++++++++++++ 2 files changed, 39 insertions(+) diff --git a/include/qemu/hbitmap.h b/include/qemu/hbitmap.h index b645cfc..c48c50a 100644 --- a/include/qemu/hbitmap.h +++ b/include/qemu/hbitmap.h @@ -73,6 +73,17 @@ HBitmap *hbitmap_alloc(uint64_t size, int granularity); HBitmap *hbitmap_copy(const HBitmap *bitmap); /** + * 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); + +/** * hbitmap_empty: * @hb: HBitmap to operate on. * diff --git a/util/hbitmap.c b/util/hbitmap.c index 033ad58..f400dcb 100644 --- a/util/hbitmap.c +++ b/util/hbitmap.c @@ -415,3 +415,31 @@ HBitmap *hbitmap_copy(const HBitmap *bitmap) return hb; } + +/** + * Given HBitmaps A and B, let A := A (BITOR) B. + * Bitmap B will not be modified. + */ +bool hbitmap_merge(HBitmap *a, const HBitmap *b) +{ + int i, j; + uint64_t size; + + if ((a->size != b->size) || (a->granularity != b->granularity)) { + return false; + } + + /* 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. + */ + size = a->size; + for (i = HBITMAP_LEVELS - 1; i >= 0; i--) { + size = MAX((size + BITS_PER_LONG - 1) >> BITS_PER_LEVEL, 1); + for (j = 0; j < size; j++) { + a->levels[i][j] |= b->levels[i][j]; + } + } + + return true; +} -- 1.9.3