[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

[libvirt] [PATCH 2/5] util: add two functions to find last set or unset bit in bitmap



virBitmapNextLastSetBit: Search for the last set bit before
certain position.

virBitmapNextLastSetBit: Search for the last clear bit before
certain position.
---
 src/libvirt_private.syms |  2 +
 src/util/virbitmap.c     | 96 ++++++++++++++++++++++++++++++++++++++++++++++++
 src/util/virbitmap.h     |  6 +++
 tests/virbitmaptest.c    | 51 ++++++++++++++++++++++++-
 4 files changed, 154 insertions(+), 1 deletion(-)

diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms
index 5cad990..a17465a 100644
--- a/src/libvirt_private.syms
+++ b/src/libvirt_private.syms
@@ -1045,6 +1045,8 @@ virBitmapNew;
 virBitmapNewCopy;
 virBitmapNewData;
 virBitmapNextClearBit;
+virBitmapNextLastClearBit;
+virBitmapNextLastSetBit;
 virBitmapNextSetBit;
 virBitmapParse;
 virBitmapSetAll;
diff --git a/src/util/virbitmap.c b/src/util/virbitmap.c
index 21509ac..bb677db 100644
--- a/src/util/virbitmap.c
+++ b/src/util/virbitmap.c
@@ -50,6 +50,21 @@ struct _virBitmap {
 #define VIR_BITMAP_BIT_OFFSET(b)  ((b) % VIR_BITMAP_BITS_PER_UNIT)
 #define VIR_BITMAP_BIT(b)         (1UL << VIR_BITMAP_BIT_OFFSET(b))
 
+/* helper function to get last set bit in long integer */
+static int
+flsl(long mask)
+{
+    int bit = VIR_BITMAP_BITS_PER_UNIT;
+
+    if (mask == 0)
+        return 0;
+
+    for (; !(mask & 1UL << (VIR_BITMAP_BITS_PER_UNIT - 1)); bit--) {
+        mask = (unsigned long)mask << 1;
+    }
+
+    return bit;
+}
 
 /**
  * virBitmapNew:
@@ -632,6 +647,46 @@ virBitmapNextSetBit(virBitmapPtr bitmap, ssize_t pos)
 }
 
 /**
+ * virBitmapNextLastSetBit
+ * @bitmap: the bitmap
+ * @pos: the position before which to search for a set bit
+ *
+ * Search for the last set bit before position @pos in bitmap @bitmap.
+ * @pos can be -1 to search for the last set bit. Position starts
+ * at bitmap->max_bit.
+ */
+
+ssize_t
+virBitmapNextLastSetBit(virBitmapPtr bitmap, ssize_t pos)
+{
+    ssize_t nl;
+    size_t nb;
+    unsigned long bits;
+
+    if (pos < 0)
+        pos = bitmap->max_bit;
+
+    pos--;
+
+    if (pos < 0 || pos >= bitmap->max_bit)
+        return -1;
+
+    nl = pos / VIR_BITMAP_BITS_PER_UNIT;
+    nb = pos % VIR_BITMAP_BITS_PER_UNIT;
+
+    bits = bitmap->map[nl] & -1UL >> (VIR_BITMAP_BITS_PER_UNIT - nb - 1);
+
+    while (bits == 0 && --nl >= 0) {
+        bits = bitmap->map[nl];
+    }
+
+    if (bits == 0)
+        return -1;
+
+    return flsl(bits) - 1 + nl * VIR_BITMAP_BITS_PER_UNIT;
+}
+
+/**
  * virBitmapNextClearBit:
  * @bitmap: the bitmap
  * @pos: the position after which to search for a clear bit
@@ -679,6 +734,47 @@ virBitmapNextClearBit(virBitmapPtr bitmap, ssize_t pos)
     return ffsl(bits) - 1 + nl * VIR_BITMAP_BITS_PER_UNIT;
 }
 
+/**
+ * virBitmapNextLastClearBit:
+ * @bitmap: the bitmap
+ * @pos: the position before which to search for a clear bit
+ *
+ * Search for the last clear bit before position @pos in bitmap @bitmap.
+ * @pos can be -1 to search for the last clear bit. Position starts
+ * at bitmap->max_bit.
+ *
+ * Returns the position of the found bit, or -1 if no bit found.
+ */
+ssize_t
+virBitmapNextLastClearBit(virBitmapPtr bitmap, ssize_t pos)
+{
+    ssize_t nl;
+    size_t nb;
+    unsigned long bits;
+
+    if (pos < 0)
+        pos = bitmap->max_bit;
+
+    pos--;
+
+    if (pos < 0 || pos >= bitmap->max_bit)
+        return -1;
+
+    nl = pos / VIR_BITMAP_BITS_PER_UNIT;
+    nb = pos % VIR_BITMAP_BITS_PER_UNIT;
+
+    bits = ~bitmap->map[nl] & -1UL >> (VIR_BITMAP_BITS_PER_UNIT - nb - 1);
+
+    while (bits == 0 && --nl >= 0) {
+        bits = ~bitmap->map[nl];
+    }
+
+    if (bits == 0)
+        return -1;
+
+    return flsl(bits) - 1 + nl * VIR_BITMAP_BITS_PER_UNIT;
+}
+
 /* Return the number of bits currently set in the map.  */
 size_t
 virBitmapCountBits(virBitmapPtr bitmap)
diff --git a/src/util/virbitmap.h b/src/util/virbitmap.h
index 044c7a6..d650e1f 100644
--- a/src/util/virbitmap.h
+++ b/src/util/virbitmap.h
@@ -103,9 +103,15 @@ bool virBitmapIsAllSet(virBitmapPtr bitmap)
 ssize_t virBitmapNextSetBit(virBitmapPtr bitmap, ssize_t pos)
     ATTRIBUTE_NONNULL(1);
 
+ssize_t virBitmapNextLastSetBit(virBitmapPtr bitmap, ssize_t pos)
+    ATTRIBUTE_NONNULL(1);
+
 ssize_t virBitmapNextClearBit(virBitmapPtr bitmap, ssize_t pos)
     ATTRIBUTE_NONNULL(1);
 
+ssize_t virBitmapNextLastClearBit(virBitmapPtr bitmap, ssize_t pos)
+    ATTRIBUTE_NONNULL(1);
+
 size_t virBitmapCountBits(virBitmapPtr bitmap)
     ATTRIBUTE_NONNULL(1);
 
diff --git a/tests/virbitmaptest.c b/tests/virbitmaptest.c
index 95d010a..f0a3086 100644
--- a/tests/virbitmaptest.c
+++ b/tests/virbitmaptest.c
@@ -161,7 +161,9 @@ error:
     return ret;
 }
 
-/* test for virBitmapNextSetBit, virBitmapNextClearBit */
+/* test for virBitmapNextSetBit, virBitmapNextClearBit
+ * virBitmapNextLastSetBit, virBitmapNextLastClearBit
+ */
 static int test4(const void *data ATTRIBUTE_UNUSED)
 {
     const char *bitsString = "0, 2-4, 6-10, 12, 14-18, 20, 22, 25";
@@ -193,9 +195,21 @@ static int test4(const void *data ATTRIBUTE_UNUSED)
         if (virBitmapNextClearBit(bitmap, i - 1) != i)
             goto error;
     }
+
     if (virBitmapNextClearBit(bitmap, i) != -1)
         goto error;
 
+    if (virBitmapNextLastSetBit(bitmap, -1) != -1)
+        goto error;
+
+    for (i = size; i > 0; i--) {
+        if (virBitmapNextLastClearBit(bitmap, i) != i - 1)
+            goto error;
+    }
+
+    if (virBitmapNextLastClearBit(bitmap, i) != -1)
+        goto error;
+
     virBitmapFree(bitmap);
     bitmap = NULL;
 
@@ -218,6 +232,18 @@ static int test4(const void *data ATTRIBUTE_UNUSED)
     if (virBitmapNextSetBit(bitmap, i) != -1)
         goto error;
 
+    j = 1;
+    i = -1;
+
+    while (j <= ARRAY_CARDINALITY(bitsPos)) {
+        i = virBitmapNextLastSetBit(bitmap, i);
+        if (i != bitsPos[ARRAY_CARDINALITY(bitsPos) - j++])
+            goto error;
+    }
+
+    if (virBitmapNextLastSetBit(bitmap, i) != -1)
+        goto error;
+
     j = 0;
     i = -1;
 
@@ -230,6 +256,18 @@ static int test4(const void *data ATTRIBUTE_UNUSED)
     if (virBitmapNextClearBit(bitmap, i) != -1)
         goto error;
 
+    j = 1;
+    i = -1;
+
+    while (j <= ARRAY_CARDINALITY(bitsPosInv)) {
+        i = virBitmapNextLastClearBit(bitmap, i);
+        if (i != bitsPosInv[ARRAY_CARDINALITY(bitsPosInv) - j++])
+            goto error;
+    }
+
+    if (virBitmapNextLastClearBit(bitmap, i) != -1)
+        goto error;
+
     /* 3. full set */
 
     virBitmapSetAll(bitmap);
@@ -244,6 +282,17 @@ static int test4(const void *data ATTRIBUTE_UNUSED)
     if (virBitmapNextClearBit(bitmap, -1) != -1)
         goto error;
 
+    for (i = size; i > 0; i--) {
+        if (virBitmapNextLastSetBit(bitmap, i) != i - 1)
+            goto error;
+    }
+
+    if (virBitmapNextLastSetBit(bitmap, i) != -1)
+        goto error;
+
+    if (virBitmapNextLastClearBit(bitmap, -1) != -1)
+        goto error;
+
     virBitmapFree(bitmap);
     return 0;
 
-- 
1.7.11.2


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]