On Mon, Mar 02, 2015 at 06:19:52PM -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 <js...@redhat.com> > Reviewed-by: Max Reitz <mre...@redhat.com> > Reviewed-by: Stefan Hajnoczi <stefa...@redhat.com> > --- > include/qemu/hbitmap.h | 11 +++++++++++ > util/hbitmap.c | 32 ++++++++++++++++++++++++++++++++ > 2 files changed, 43 insertions(+)
Reviewed-by: Stefan Hajnoczi <stefa...@redhat.com>
pgp_u50pkpGRd.pgp
Description: PGP signature
