libqtest: Replace qtest_startf() by qtest_initf()

[qemu.git] / util / hbitmap.c

diff --git a/util/hbitmap.c b/util/hbitmap.c
index 21535cc90bc4993fc20618d6223e7152c2e6db45..bcd304041aad98bce1a22c7bd0b248f7b702edd7 100644 (file)
--- a/util/hbitmap.c
+++ b/util/hbitmap.c
@@ -141,7 +141,7 @@ unsigned long hbitmap_iter_skip_words(HBitmapIter *hbi)
     return cur;
 }
 
-int64_t hbitmap_iter_next(HBitmapIter *hbi)
+int64_t hbitmap_iter_next(HBitmapIter *hbi, bool advance)
 {
     unsigned long cur = hbi->cur[HBITMAP_LEVELS - 1] &
             hbi->hb->levels[HBITMAP_LEVELS - 1][hbi->pos];
@@ -154,8 +154,12 @@ int64_t hbitmap_iter_next(HBitmapIter *hbi)
         }
     }
 
-    /* The next call will resume work from the next bit.  */
-    hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
+    if (advance) {
+        /* The next call will resume work from the next bit.  */
+        hbi->cur[HBITMAP_LEVELS - 1] = cur & (cur - 1);
+    } else {
+        hbi->cur[HBITMAP_LEVELS - 1] = cur;
+    }
     item = ((uint64_t)hbi->pos << BITS_PER_LEVEL) + ctzl(cur);
 
     return item << hbi->granularity;
@@ -188,6 +192,45 @@ void hbitmap_iter_init(HBitmapIter *hbi, const HBitmap *hb, uint64_t first)
     }
 }
 
+int64_t hbitmap_next_zero(const HBitmap *hb, uint64_t start)
+{
+    size_t pos = (start >> hb->granularity) >> BITS_PER_LEVEL;
+    unsigned long *last_lev = hb->levels[HBITMAP_LEVELS - 1];
+    uint64_t sz = hb->sizes[HBITMAP_LEVELS - 1];
+    unsigned long cur = last_lev[pos];
+    unsigned start_bit_offset =
+            (start >> hb->granularity) & (BITS_PER_LONG - 1);
+    int64_t res;
+
+    cur |= (1UL << start_bit_offset) - 1;
+    assert((start >> hb->granularity) < hb->size);
+
+    if (cur == (unsigned long)-1) {
+        do {
+            pos++;
+        } while (pos < sz && last_lev[pos] == (unsigned long)-1);
+
+        if (pos >= sz) {
+            return -1;
+        }
+
+        cur = last_lev[pos];
+    }
+
+    res = (pos << BITS_PER_LEVEL) + ctol(cur);
+    if (res >= hb->size) {
+        return -1;
+    }
+
+    res = res << hb->granularity;
+    if (res < start) {
+        assert(((start - res) >> hb->granularity) == 0);
+        return start;
+    }
+
+    return res;
+}
+
 bool hbitmap_empty(const HBitmap *hb)
 {
     return hb->count == 0;
@@ -413,14 +456,14 @@ bool hbitmap_is_serializable(const HBitmap *hb)
 {
     /* Every serialized chunk must be aligned to 64 bits so that endianness
      * requirements can be fulfilled on both 64 bit and 32 bit hosts.
-     * We have hbitmap_serialization_granularity() which converts this
+     * We have hbitmap_serialization_align() which converts this
      * alignment requirement from bitmap bits to items covered (e.g. sectors).
      * That value is:
      *    64 << hb->granularity
      * Since this value must not exceed UINT64_MAX, hb->granularity must be
      * less than 58 (== 64 - 6, where 6 is ld(64), i.e. 1 << 6 == 64).
      *
-     * In order for hbitmap_serialization_granularity() to always return a
+     * In order for hbitmap_serialization_align() to always return a
      * meaningful value, bitmaps that are to be serialized must have a
      * granularity of less than 58. */
 
@@ -437,7 +480,7 @@ bool hbitmap_get(const HBitmap *hb, uint64_t item)
     return (hb->levels[HBITMAP_LEVELS - 1][pos >> BITS_PER_LEVEL] & bit) != 0;
 }
 
-uint64_t hbitmap_serialization_granularity(const HBitmap *hb)
+uint64_t hbitmap_serialization_align(const HBitmap *hb)
 {
     assert(hbitmap_is_serializable(hb));
 
@@ -454,7 +497,7 @@ static void serialization_chunk(const HBitmap *hb,
                                 unsigned long **first_el, uint64_t *el_count)
 {
     uint64_t last = start + count - 1;
-    uint64_t gran = hbitmap_serialization_granularity(hb);
+    uint64_t gran = hbitmap_serialization_align(hb);
 
     assert((start & (gran - 1)) == 0);
     assert((last >> hb->granularity) < hb->size);
@@ -591,6 +634,7 @@ void hbitmap_deserialize_finish(HBitmap *bitmap)
     }
 
     bitmap->levels[0][0] |= 1UL << (BITS_PER_LONG - 1);
+    bitmap->count = hb_count_between(bitmap, 0, bitmap->size - 1);
 }
 
 void hbitmap_free(HBitmap *hb)