Re: [Qemu-devel] [PATCH v13 05/17] hbitmap: add hbitmap_merge

[Stefan Hajnoczi <stefanha@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 898 bytes --]

On Fri, Feb 13, 2015 at 05:08:46PM -0500, John Snow wrote:
> 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 <jsnow@redhat.com>
> Reviewed-by: Max Reitz <mreitz@redhat.com>
> ---
>  include/qemu/hbitmap.h | 11 +++++++++++
>  util/hbitmap.c         | 32 ++++++++++++++++++++++++++++++++
>  2 files changed, 43 insertions(+)

Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]