[libvirt] [PATCH 2/5] util: add two functions to find last set or unset bit in bitmap
Guannan Ren
gren at redhat.com
Mon Mar 18 09:10:19 UTC 2013
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
More information about the libvir-list
mailing list