[PATCH v5 1/3] bitmap: add virBitmapLastSetBit for finding the last bit position of bitmap

[Chen Fan <chen.fan.fnst@xxxxxxxxxxxxxx>]

Signed-off-by: Chen Fan <chen.fan.fnst@xxxxxxxxxxxxxx>
---
 src/libvirt_private.syms |  1 +
 src/util/virbitmap.c     | 45 +++++++++++++++++++++++++++++++++++++++++++++
 src/util/virbitmap.h     |  3 +++
 tests/virbitmaptest.c    | 13 ++++++++++++-
 4 files changed, 61 insertions(+), 1 deletion(-)

diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms
index d63a8f0..1e2bc0a 100644
--- a/src/libvirt_private.syms
+++ b/src/libvirt_private.syms
@@ -1011,6 +1011,7 @@ virBitmapFree;
 virBitmapGetBit;
 virBitmapIsAllClear;
 virBitmapIsAllSet;
+virBitmapLastSetBit;
 virBitmapNew;
 virBitmapNewCopy;
 virBitmapNewData;
diff --git a/src/util/virbitmap.c b/src/util/virbitmap.c
index b6bd074..04a2388 100644
--- a/src/util/virbitmap.c
+++ b/src/util/virbitmap.c
@@ -651,6 +651,51 @@ virBitmapNextSetBit(virBitmapPtr bitmap, ssize_t pos)
 }
 
 /**
+ * virBitmapLastSetBit:
+ * @bitmap: the bitmap
+ *
+ * Search for the last set bit in bitmap @bitmap.
+ *
+ * Returns the position of the found bit, or -1 if no bit is set.
+ */
+ssize_t
+virBitmapLastSetBit(virBitmapPtr bitmap)
+{
+    ssize_t i;
+    int unusedBits;
+    ssize_t sz;
+    unsigned long bits;
+
+    unusedBits = bitmap->map_len * VIR_BITMAP_BITS_PER_UNIT - bitmap->max_bit;
+
+    sz = bitmap->map_len - 1;
+    if (unusedBits > 0) {
+        bits = bitmap->map[sz] & (VIR_BITMAP_BIT(VIR_BITMAP_BITS_PER_UNIT - unusedBits) - 1);
+        if (bits != 0)
+            goto found;
+
+        sz--;
+    }
+
+    for (; sz >= 0; sz--) {
+        bits = bitmap->map[sz];
+        if (bits != 0)
+            goto found;
+    }
+
+    if (bits == 0)
+        return -1;
+
+ found:
+    for (i = VIR_BITMAP_BITS_PER_UNIT - 1; i >= 0; i--) {
+        if (bits & 1UL << i)
+            return i + sz * VIR_BITMAP_BITS_PER_UNIT;
+    }
+
+    return -1;
+}
+
+/**
  * virBitmapNextClearBit:
  * @bitmap: the bitmap
  * @pos: the position after which to search for a clear bit
diff --git a/src/util/virbitmap.h b/src/util/virbitmap.h
index 4493cc9..565264c 100644
--- a/src/util/virbitmap.h
+++ b/src/util/virbitmap.h
@@ -105,6 +105,9 @@ bool virBitmapIsAllClear(virBitmapPtr bitmap)
 ssize_t virBitmapNextSetBit(virBitmapPtr bitmap, ssize_t pos)
     ATTRIBUTE_NONNULL(1);
 
+ssize_t virBitmapLastSetBit(virBitmapPtr bitmap)
+    ATTRIBUTE_NONNULL(1);
+
 ssize_t virBitmapNextClearBit(virBitmapPtr bitmap, ssize_t pos)
     ATTRIBUTE_NONNULL(1);
 
diff --git a/tests/virbitmaptest.c b/tests/virbitmaptest.c
index ea832ad..ac5f298 100644
--- a/tests/virbitmaptest.c
+++ b/tests/virbitmaptest.c
@@ -171,7 +171,7 @@ test3(const void *data ATTRIBUTE_UNUSED)
     return ret;
 }
 
-/* test for virBitmapNextSetBit, virBitmapNextClearBit */
+/* test for virBitmapNextSetBit, virBitmapLastSetBit, virBitmapNextClearBit */
 static int
 test4(const void *data ATTRIBUTE_UNUSED)
 {
@@ -200,6 +200,9 @@ test4(const void *data ATTRIBUTE_UNUSED)
     if (virBitmapNextSetBit(bitmap, -1) != -1)
         goto error;
 
+    if (virBitmapLastSetBit(bitmap) != -1)
+        goto error;
+
     for (i = 0; i < size; i++) {
         if (virBitmapNextClearBit(bitmap, i - 1) != i)
             goto error;
@@ -232,6 +235,11 @@ test4(const void *data ATTRIBUTE_UNUSED)
     if (virBitmapNextSetBit(bitmap, i) != -1)
         goto error;
 
+    j = sizeof(bitsPos)/sizeof(int) - 1;
+
+    if (virBitmapLastSetBit(bitmap) != bitsPos[j])
+        goto error;
+
     j = 0;
     i = -1;
 
@@ -255,6 +263,9 @@ test4(const void *data ATTRIBUTE_UNUSED)
     if (virBitmapNextSetBit(bitmap, i) != -1)
         goto error;
 
+    if (virBitmapLastSetBit(bitmap) != size - 1)
+        goto error;
+
     if (virBitmapNextClearBit(bitmap, -1) != -1)
         goto error;
 
-- 
1.9.3

--
libvir-list mailing list
libvir-list@xxxxxxxxxx
https://www.redhat.com/mailman/listinfo/libvir-list