From patchwork Wed Dec 12 13:46:34 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Bonzini X-Patchwork-Id: 205533 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id ADD612C0092 for ; Thu, 13 Dec 2012 01:11:54 +1100 (EST) Received: from localhost ([::1]:54337 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Timgk-000319-6m for incoming@patchwork.ozlabs.org; Wed, 12 Dec 2012 08:49:30 -0500 Received: from eggs.gnu.org ([208.118.235.92]:59124) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TimfE-0000PE-Fk for qemu-devel@nongnu.org; Wed, 12 Dec 2012 08:48:02 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Timf6-0003rV-KM for qemu-devel@nongnu.org; Wed, 12 Dec 2012 08:47:56 -0500 Received: from mail-ie0-f169.google.com ([209.85.223.169]:58428) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Timf6-0003rL-En for qemu-devel@nongnu.org; Wed, 12 Dec 2012 08:47:48 -0500 Received: by mail-ie0-f169.google.com with SMTP id c14so1766775ieb.28 for ; Wed, 12 Dec 2012 05:47:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:from:to:cc:subject:date:message-id:x-mailer:in-reply-to :references; bh=qEmHWWxK/4zsoaV+hHV6PhvL8C6Ik+Zn3Iz5Y8/0pxw=; b=s6XNByF6pZG1KKo4xH/S2c7kYgB95I1R1Qo17N5YqxispbUu7ZLeoNF6lIR5OrrNyE wq8bAWiNnhhhIh5IYH+l0CVyoP6YJUIN4iomf0PK4Hcm1G4HFTXIK1r+okGTacfOtUcH E9/hCqc4BPYsZ7rLnK/MCvZL8Jqi0fKNcjyM690cv6wmEoe7TfLIv0qVqP77yE4qOZ89 SL6PjyI+u8hYZnyJUH+vpPWBUrcA15py63Spi87v7IWxmDcjItkLAg165q+FwcStUzo1 yvvX1ZLAI389Eaw/a814uUKgEghq1lZsAhMsb53YzYOtVD0kdZ+kkvs3pk9m8i9tGLZ8 7+/w== Received: by 10.50.150.175 with SMTP id uj15mr13218397igb.52.1355320067975; Wed, 12 Dec 2012 05:47:47 -0800 (PST) Received: from yakj.usersys.redhat.com (93-34-219-150.ip51.fastwebnet.it. [93.34.219.150]) by mx.google.com with ESMTPS id fv6sm1786818igc.17.2012.12.12.05.47.45 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 12 Dec 2012 05:47:47 -0800 (PST) From: Paolo Bonzini To: qemu-devel@nongnu.org Date: Wed, 12 Dec 2012 14:46:34 +0100 Message-Id: <1355319999-30627-16-git-send-email-pbonzini@redhat.com> X-Mailer: git-send-email 1.8.0.1 In-Reply-To: <1355319999-30627-1-git-send-email-pbonzini@redhat.com> References: <1355319999-30627-1-git-send-email-pbonzini@redhat.com> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 209.85.223.169 Cc: kwolf@redhat.com, jcody@redhat.com, stefanha@redhat.com Subject: [Qemu-devel] [PATCH 15/20] hbitmap: add hbitmap_copy X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Signed-off-by: Paolo Bonzini Reviewed-by: Eric Blake --- 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;