[libvirt] [PATCH v4 1/3] bitmap: add virBitmapLastSetBit for finding the last bit position of bitmap
Signed-off-by: Chen Fan <chen.fan.fnst(a)cn.fujitsu.com>
---
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..3e7269e 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 found.
+ */
+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