[Qemu-devel] [PATCH 15/20] hbitmap: add hbitmap_copy

[Paolo Bonzini <pbonzini@redhat.com>]

Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 hbitmap.c            | 48 +++++++++++++++++++++++++++++++++++++
 hbitmap.h            | 11 +++++++++
 tests/test-hbitmap.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 126 insertions(+)

diff --git a/hbitmap.c b/hbitmap.c
index aa4586f..99c749f 100644
--- a/hbitmap.c
+++ b/hbitmap.c
@@ -368,6 +368,54 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
     return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
 }
 
+void hbitmap_copy(HBitmap *dst, HBitmap *src)
+{
+    HBitmapIter dst_iter, src_iter;
+    size_t dst_pos, src_pos, old_dst_pos;
+    unsigned long dst_cur, src_cur;
+
+    assert(dst->granularity == src->granularity);
+    assert(dst->size == src->size);
+
+    hbitmap_iter_init(&dst_iter, dst, 0);
+    hbitmap_iter_init(&src_iter, src, 0);
+
+    dst_pos = hbitmap_iter_next_word(&dst_iter, &dst_cur);
+    src_pos = hbitmap_iter_next_word(&src_iter, &src_cur);
+
+    while (dst_pos != -1) {
+        if (dst_pos < src_pos) {
+            /* Clear all words up to src_pos.  Do it one by one,
+             * on the assumption that dst is sparse */
+            old_dst_pos = dst_pos;
+            dst_pos = hbitmap_iter_next_word(&dst_iter, &dst_cur);
+            dst->levels[HBITMAP_LEVELS - 1][old_dst_pos] = 0;
+            hb_reset_between(dst, HBITMAP_LEVELS - 2, old_dst_pos, old_dst_pos);
+            continue;
+        }
+
+        /* Copy one word from source to destination.  Update the
+         * upper levels if the corresponding word in dst was zero.
+         */
+        dst->levels[HBITMAP_LEVELS - 1][src_pos] = src_cur;
+        if (dst_pos > src_pos) {
+            hb_set_between(dst, HBITMAP_LEVELS - 2, src_pos, src_pos);
+        } else {
+            dst_pos = hbitmap_iter_next_word(&dst_iter, &dst_cur);
+        }
+        src_pos = hbitmap_iter_next_word(&src_iter, &src_cur);
+    }
+
+    /* Copy everything past the last 'one' in dst.  */
+    while (src_pos != -1) {
+        dst->levels[HBITMAP_LEVELS - 1][src_pos] = src_cur;
+        hb_set_between(dst, HBITMAP_LEVELS - 2, src_pos, src_pos);
+        src_pos = hbitmap_iter_next_word(&src_iter, &src_cur);
+    }
+
+    dst->count = src->count;
+}
+
 void hbitmap_free(HBitmap *hb)
 {
     unsigned i = HBITMAP_LEVELS;
diff --git a/hbitmap.h b/hbitmap.h
index 35ee51a..690e252 100644
--- a/hbitmap.h
+++ b/hbitmap.h
@@ -229,4 +229,15 @@ static inline size_t hbitmap_iter_next_word(HBitmapIter *hbi, unsigned long *p_c
 }
 
 
+/**
+ * hbitmap_copy:
+ * @dest: HBitmap to copy to.
+ * @src: HBitmap to copy from.
+ *
+ * Copy from one HBitmap to another, efficiently skipping zero
+ * areas in both the source and the destination.  The two bitmaps
+ * must have the same size and granularity.
+ */
+void hbitmap_copy(HBitmap *dest, HBitmap *src);
+
 #endif
diff --git a/tests/test-hbitmap.c b/tests/test-hbitmap.c
index b5d76a7..d6a93c2 100644
--- a/tests/test-hbitmap.c
+++ b/tests/test-hbitmap.c
@@ -24,6 +24,7 @@ typedef struct TestHBitmapData {
     unsigned long *bits;
     size_t         size;
     int            granularity;
+    int            id;
 } TestHBitmapData;
 
 
@@ -329,6 +330,52 @@ static void test_hbitmap_reset(TestHBitmapData *data,
     hbitmap_test_set(data, L3 / 2, L3);
 }
 
+static void test_hbitmap_copy(TestHBitmapData *data,
+                              const void *p_id)
+{
+    int id = *(int *)p_id;
+    HBitmap *aux;
+
+    hbitmap_test_init(data, L3, 0);
+    aux = hbitmap_alloc(L3, 0);
+
+    /* Add some bits to data.  */
+    if (id < 1 || id > 7) {
+        hbitmap_test_set(data, 2, 2);
+    }
+    if (id < 2 || id > 6) {
+        hbitmap_test_set(data, L1 * 3, L1 * 2);
+    }
+    if (id < 3 || id > 5) {
+        hbitmap_test_set(data, L1 * 7, 4);
+    }
+    if (id < 4) {
+        hbitmap_test_set(data, L1 * 10, 4);
+    }
+
+    /* Add some bits to the copy destination.  */
+    if (id < 5) {
+        hbitmap_set(aux, 0, 1);
+    }
+    if (id < 6) {
+        hbitmap_set(aux, L1 * 4, 2);
+    }
+    if (id < 7) {
+        hbitmap_set(aux, L1 * 7, 4);
+    }
+
+    hbitmap_copy(aux, data->hb);
+    hbitmap_test_check(data, 0);
+
+    /* Swap the two, the new data bitmap must still be the same as the
+     * check vector.
+     */
+    hbitmap_free(data->hb);
+    data->hb = aux;
+
+    hbitmap_test_check(data, 0);
+}
+
 static void test_hbitmap_granularity(TestHBitmapData *data,
                                      const void *unused)
 {
@@ -375,6 +422,17 @@ static void test_hbitmap_iter_granularity(TestHBitmapData *data,
     g_assert_cmpint(hbitmap_iter_next(&hbi), <, 0);
 }
 
+static void hbitmap_test_add_with_id(const char *testpath,
+                                     void (*test_func)(TestHBitmapData *data, const void *user_data),
+                                     int id)
+{
+    int *p_id = g_malloc0(sizeof(int));
+    *p_id = id;
+
+    g_test_add(testpath, TestHBitmapData, p_id, NULL, test_func,
+               hbitmap_test_teardown);
+}
+
 static void hbitmap_test_add(const char *testpath,
                                    void (*test_func)(TestHBitmapData *data, const void *user_data))
 {
@@ -402,6 +460,15 @@ int main(int argc, char **argv)
     hbitmap_test_add("/hbitmap/reset/empty", test_hbitmap_reset_empty);
     hbitmap_test_add("/hbitmap/reset/general", test_hbitmap_reset);
     hbitmap_test_add("/hbitmap/granularity", test_hbitmap_granularity);
+    hbitmap_test_add_with_id("/hbitmap/copy/0", test_hbitmap_copy, 0);
+    hbitmap_test_add_with_id("/hbitmap/copy/1", test_hbitmap_copy, 1);
+    hbitmap_test_add_with_id("/hbitmap/copy/2", test_hbitmap_copy, 2);
+    hbitmap_test_add_with_id("/hbitmap/copy/3", test_hbitmap_copy, 3);
+    hbitmap_test_add_with_id("/hbitmap/copy/4", test_hbitmap_copy, 4);
+    hbitmap_test_add_with_id("/hbitmap/copy/5", test_hbitmap_copy, 5);
+    hbitmap_test_add_with_id("/hbitmap/copy/6", test_hbitmap_copy, 6);
+    hbitmap_test_add_with_id("/hbitmap/copy/7", test_hbitmap_copy, 7);
+    hbitmap_test_add_with_id("/hbitmap/copy/8", test_hbitmap_copy, 8);
     g_test_run();
 
     return 0;
-- 
1.8.0.1