Signed-off-by: Paolo Bonzini <pbonz...@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
