@@ -19,6 +19,7 @@
#include "host-utils.h"
typedef struct HBitmap HBitmap;
+
typedef struct HBitmapIter HBitmapIter;
#define BITS_PER_LEVEL (BITS_PER_LONG == 32 ? 5 : 6)
@@ -51,6 +52,44 @@ struct HBitmapIter {
unsigned long cur[HBITMAP_LEVELS];
};
+struct HBitmap {
+ /* Number of total bits in the bottom level. */
+ uint64_t size;
+
+ /* Number of set bits in the bottom level. */
+ uint64_t count;
+
+ /* A scaling factor. Given a granularity of G, each bit in the bitmap will
+ * will actually represent a group of 2^G elements. Each operation on a
+ * range of bits first rounds the bits to determine which group they land
+ * in, and then affect the entire page; iteration will only visit the first
+ * bit of each group. Here is an example of operations in a size-16,
+ * granularity-1 HBitmap:
+ *
+ * initial state 00000000
+ * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8)
+ * reset(start=1, count=3) 00111000 (iter: 4, 6, 8)
+ * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10)
+ * reset(start=5, count=5) 00000000
+ *
+ * From an implementation point of view, when setting or resetting bits,
+ * the bitmap will scale bit numbers right by this amount of bits. When
+ * iterating, the bitmap will scale bit numbers left by this amount of
+ * bits.
+ */
+ int granularity;
+
+ /* A number of progressively less coarse bitmaps (i.e. level 0 is the
+ * coarsest). Each bit in level N represents a word in level N+1 that
+ * has a set bit, except the last level where each bit represents the
+ * actual bitmap.
+ *
+ * Note that all bitmaps have the same number of levels. Even a 1-bit
+ * bitmap will still allocate HBITMAP_LEVELS arrays.
+ */
+ unsigned long *levels[HBITMAP_LEVELS];
+};
+
/**
* hbitmap_alloc:
* @size: Number of bits in the bitmap.
@@ -54,44 +54,6 @@
* O(logB n) as in the non-amortized complexity).
*/
-struct HBitmap {
- /* Number of total bits in the bottom level. */
- uint64_t size;
-
- /* Number of set bits in the bottom level. */
- uint64_t count;
-
- /* A scaling factor. Given a granularity of G, each bit in the bitmap will
- * will actually represent a group of 2^G elements. Each operation on a
- * range of bits first rounds the bits to determine which group they land
- * in, and then affect the entire page; iteration will only visit the first
- * bit of each group. Here is an example of operations in a size-16,
- * granularity-1 HBitmap:
- *
- * initial state 00000000
- * set(start=0, count=9) 11111000 (iter: 0, 2, 4, 6, 8)
- * reset(start=1, count=3) 00111000 (iter: 4, 6, 8)
- * set(start=9, count=2) 00111100 (iter: 4, 6, 8, 10)
- * reset(start=5, count=5) 00000000
- *
- * From an implementation point of view, when setting or resetting bits,
- * the bitmap will scale bit numbers right by this amount of bits. When
- * iterating, the bitmap will scale bit numbers left by this amount of
- * bits.
- */
- int granularity;
-
- /* A number of progressively less coarse bitmaps (i.e. level 0 is the
- * coarsest). Each bit in level N represents a word in level N+1 that
- * has a set bit, except the last level where each bit represents the
- * actual bitmap.
- *
- * Note that all bitmaps have the same number of levels. Even a 1-bit
- * bitmap will still allocate HBITMAP_LEVELS arrays.
- */
- unsigned long *levels[HBITMAP_LEVELS];
-};
-
static inline int popcountl(unsigned long l)
{
return BITS_PER_LONG == 32 ? ctpop32(l) : ctpop64(l);
The struct field will be used outside of hbitmap.c once become a list, move it to public header. Signed-off-by: Fam Zheng <famz@redhat.com> --- include/qemu/hbitmap.h | 39 +++++++++++++++++++++++++++++++++++++++ util/hbitmap.c | 38 -------------------------------------- 2 files changed, 39 insertions(+), 38 deletions(-)