[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Qemu-devel] [PATCH v2 35/45] add hierarchical bitmap data type and
From: |
Eric Blake |
Subject: |
Re: [Qemu-devel] [PATCH v2 35/45] add hierarchical bitmap data type and test cases |
Date: |
Wed, 26 Sep 2012 20:53:34 -0600 |
User-agent: |
Mozilla/5.0 (X11; Linux x86_64; rv:15.0) Gecko/20120911 Thunderbird/15.0.1 |
On 09/26/2012 09:56 AM, Paolo Bonzini wrote:
> HBitmaps provides an array of bits. The bits are stored as usual in an
> array of unsigned longs, but HBitmap is also optimized to provide fast
> iteration over set bits; going from one bit to the next is O(logB n)
> worst case, with B = sizeof(long) * CHAR_BIT: the result is low enough
> that the number of levels is in fact fixed.
> +++ b/hbitmap.c
> @@ -0,0 +1,400 @@
> +/*
> + * Hierarchical Bitmap Data Type
> + *
> + * Copyright Red Hat, Inc., 2012
vs.
> +++ b/tests/test-hbitmap.c
> @@ -0,0 +1,408 @@
> +/*
> + * Hierarchical bitmap unit-tests.
> + *
> + * Copyright (C) 2012 Red Hat Inc.
Is there a preferred form for the copyright line?
> +++ b/hbitmap.h
> @@ -0,0 +1,207 @@
> +
> +/* We need to place a sentinel in level 0 to speed up iteration. Thus,
> + * we do this instead of HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL. The
> + * difference is that it allocates an extra level when HBITMAP_LOG_MAX_SIZE
> + * is an exact multiple of BITS_PER_LEVEL.
> + */
> +#define HBITMAP_LEVELS ((HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL) + 1)
Comment is a bit misleading. Don't you mean:
Thus, we do this instead of (HBITMAP_LOG_MAX_SIZE + BITS_PER_LEVEL -
1)/BITS_PER_LEVEL.
(aka ceil(1.0*HBITMAP_LOG_MAX_SIZE / BITS_PER_LEVEL))
--
Eric Blake address@hidden +1-919-301-3266
Libvirt virtualization library http://libvirt.org
signature.asc
Description: OpenPGP digital signature
- Re: [Qemu-devel] [PATCH v2 32/45] qmp: add pull_event function, (continued)
- [Qemu-devel] [PATCH v2 36/45] block: implement dirty bitmap using HBitmap, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 37/45] block: make round_to_clusters public, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 39/45] block: return count of dirty sectors, not chunks, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 38/45] mirror: perform COW if the cluster size is bigger than the granularity, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 41/45] mirror: allow customizing the granularity, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 43/45] mirror: add buf-size argument to drive-mirror, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 42/45] mirror: switch mirror_iteration to AIO, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 44/45] mirror: support more than one in-flight AIO operation, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 35/45] add hierarchical bitmap data type and test cases, Paolo Bonzini, 2012/09/26
- Re: [Qemu-devel] [PATCH v2 35/45] add hierarchical bitmap data type and test cases,
Eric Blake <=
- [Qemu-devel] [PATCH v2 34/45] host-utils: add ffsl, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 45/45] mirror: support arbitrarily-sized iterations, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 21/45] block: add bdrv_open_backing_file, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 28/45] mirror: implement completion, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 15/45] stream: add on-error argument, Paolo Bonzini, 2012/09/26
- [Qemu-devel] [PATCH v2 30/45] iostatus: forward block_job_iostatus_reset to block job, Paolo Bonzini, 2012/09/26