Am 21.01.2013 17:09, schrieb Paolo Bonzini: > 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. > > In order to do this, it stacks multiple bitmaps with progressively coarser > granularity; in all levels except the last, bit N is set iff the N-th > unsigned long is nonzero in the immediately next level. When iteration > completes on the last level it can examine the 2nd-last level to quickly > skip entire words, and even do so recursively to skip blocks of 64 words or > powers thereof (32 on 32-bit machines). > > Given an index in the bitmap, it can be split in group of bits like > this (for the 64-bit case): > > bits 0-57 => word in the last bitmap | bits 58-63 => bit in the word > bits 0-51 => word in the 2nd-last bitmap | bits 52-57 => bit in the word > bits 0-45 => word in the 3rd-last bitmap | bits 46-51 => bit in the word > > So it is easy to move up simply by shifting the index right by > log2(BITS_PER_LONG) bits. To move down, you shift the index left > similarly, and add the word index within the group. Iteration uses > ffs (find first set bit) to find the next word to examine; this > operation can be done in constant time in most current architectures. > > Setting or clearing a range of m bits on all levels, the work to perform > is O(m + m/W + m/W^2 + ...), which is O(m) like on a regular bitmap. > > When iterating on a bitmap, each bit (on any level) is only visited > once. Hence, The total cost of visiting a bitmap with m bits in it is > the number of bits that are set in all bitmaps. Unless the bitmap is > extremely sparse, this is also O(m + m/W + m/W^2 + ...), so the amortized > cost of advancing from one bit to the next is usually constant. > > Reviewed-by: Laszlo Ersek <ler...@redhat.com> > Reviewed-by: Eric Blake <ebl...@redhat.com> > Signed-off-by: Paolo Bonzini <pbonz...@redhat.com>
make check failed for me, and it turns out it was because MALLOC_CHECK_=3 was set. Look: $ valgrind tests/test-hbitmap ==5964== Memcheck, a memory error detector ==5964== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al. ==5964== Using Valgrind-3.6.1 and LibVEX; rerun with -h for copyright info ==5964== Command: tests/test-hbitmap ==5964== /hbitmap/size/0: OK /hbitmap/size/unaligned: OK /hbitmap/iter/empty: OK /hbitmap/iter/past: ==5964== Invalid read of size 8 ==5964== at 0x10A6E1: hbitmap_iter_init (hbitmap.c:158) ==5964== by 0x108D24: hbitmap_test_check (test-hbitmap.c:42) ==5964== by 0x50ABCA7: g_test_run_suite_internal (gtestutils.c:1174) ==5964== by 0x50ABE15: g_test_run_suite_internal (gtestutils.c:1233) ==5964== by 0x50ABE15: g_test_run_suite_internal (gtestutils.c:1233) ==5964== by 0x50AC10E: g_test_run_suite (gtestutils.c:1282) ==5964== by 0x108B12: main (test-hbitmap.c:405) ==5964== Address 0x9af7c90 is 0 bytes after a block of size 32,768 alloc'd ==5964== at 0x4A04B84: calloc (vg_replace_malloc.c:467) ==5964== by 0x508E667: g_malloc0 (gmem.c:196) ==5964== by 0x10AE63: hbitmap_alloc (hbitmap.c:390) ==5964== by 0x108F95: hbitmap_test_init (test-hbitmap.c:80) ==5964== by 0x109DF3: test_hbitmap_iter_past (test-hbitmap.c:204) ==5964== by 0x50ABCA7: g_test_run_suite_internal (gtestutils.c:1174) ==5964== by 0x50ABE15: g_test_run_suite_internal (gtestutils.c:1233) ==5964== by 0x50ABE15: g_test_run_suite_internal (gtestutils.c:1233) ==5964== by 0x50AC10E: g_test_run_suite (gtestutils.c:1282) ==5964== by 0x108B12: main (test-hbitmap.c:405) ==5964== Kevin
