8:16 p.m.
We had an easy way to iterate set bits, but not for iterating
cleared bits.
* src/util/virbitmap.h (virBitmapNextClearBit): New prototype.
* src/util/virbitmap.c (virBitmapNextClearBit): Implement it.
* src/libvirt_private.syms (bitmap.h): Export it.
* tests/virbitmaptest.c (test4): Test it.
---
src/libvirt_private.syms | 1 +
src/util/virbitmap.c | 57 ++++++++++++++++++++++++++++++++++++++++++++----
src/util/virbitmap.h | 5 ++++-
tests/virbitmaptest.c | 46 +++++++++++++++++++++++++++++---------
4 files changed, 94 insertions(+), 15 deletions(-)
diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms
index c589236..3483831 100644
--- a/src/libvirt_private.syms
+++ b/src/libvirt_private.syms
@@ -18,6 +18,7 @@ virBitmapIsAllSet;
virBitmapNew;
virBitmapNewCopy;
virBitmapNewData;
+virBitmapNextClearBit;
virBitmapNextSetBit;
virBitmapParse;
virBitmapSetAll;
diff --git a/src/util/virbitmap.c b/src/util/virbitmap.c
index 2cfe03a..21509ac 100644
--- a/src/util/virbitmap.c
+++ b/src/util/virbitmap.c
@@ -1,7 +1,7 @@
/*
* virbitmap.h: Simple bitmap operations
*
- * Copyright (C) 2010-2012 Red Hat, Inc.
+ * Copyright (C) 2010-2013 Red Hat, Inc.
* Copyright (C) 2010 Novell, Inc.
*
* This library is free software; you can redistribute it and/or
@@ -595,13 +595,14 @@ bool virBitmapIsAllSet(virBitmapPtr bitmap)
* @bitmap: the bitmap
* @pos: the position after which to search for a set bit
*
- * search the first set bit after position @pos in bitmap @bitmap.
+ * Search for the first set bit after position @pos in bitmap @bitmap.
* @pos can be -1 to search for the first set bit. Position starts
* at 0.
*
- * returns the position of the found bit, or -1 if no bit found.
+ * Returns the position of the found bit, or -1 if no bit found.
*/
-ssize_t virBitmapNextSetBit(virBitmapPtr bitmap, ssize_t pos)
+ssize_t
+virBitmapNextSetBit(virBitmapPtr bitmap, ssize_t pos)
{
size_t nl;
size_t nb;
@@ -630,6 +631,54 @@ ssize_t virBitmapNextSetBit(virBitmapPtr bitmap, ssize_t pos)
return ffsl(bits) - 1 + nl * VIR_BITMAP_BITS_PER_UNIT;
}
+/**
+ * virBitmapNextClearBit:
+ * @bitmap: the bitmap
+ * @pos: the position after which to search for a clear bit
+ *
+ * Search for the first clear bit after position @pos in bitmap @bitmap.
+ * @pos can be -1 to search for the first set bit. Position starts
+ * at 0.
+ *
+ * Returns the position of the found bit, or -1 if no bit found.
+ */
+ssize_t
+virBitmapNextClearBit(virBitmapPtr bitmap, ssize_t pos)
+{
+ size_t nl;
+ size_t nb;
+ unsigned long bits;
+
+ if (pos < 0)
+ pos = -1;
+
+ pos++;
+
+ if (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 << nb) - 1);
+
+ while (bits == 0 && ++nl < bitmap->map_len) {
+ bits = ~bitmap->map[nl];
+ }
+
+ if (nl == bitmap->map_len - 1) {
+ /* Ensure tail bits are ignored. */
+ int tail = bitmap->max_bit % VIR_BITMAP_BITS_PER_UNIT;
+
+ if (tail)
+ bits &= -1UL >> (VIR_BITMAP_BITS_PER_UNIT - tail);
+ }
+ if (bits == 0)
+ return -1;
+
+ return ffsl(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 0f68b79..044c7a6 100644
--- a/src/util/virbitmap.h
+++ b/src/util/virbitmap.h
@@ -1,7 +1,7 @@
/*
* virbitmap.h: Simple bitmap operations
*
- * Copyright (C) 2012 Red Hat, Inc.
+ * Copyright (C) 2012-2013 Red Hat, Inc.
* Copyright (C) 2010 Novell, Inc.
*
* This library is free software; you can redistribute it and/or
@@ -103,6 +103,9 @@ bool virBitmapIsAllSet(virBitmapPtr bitmap)
ssize_t virBitmapNextSetBit(virBitmapPtr bitmap, ssize_t pos)
ATTRIBUTE_NONNULL(1);
+ssize_t virBitmapNextClearBit(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 66ffd1b..95d010a 100644
--- a/tests/virbitmaptest.c
+++ b/tests/virbitmaptest.c
@@ -1,4 +1,5 @@
/*
+ * Copyright (C) 2013 Red Hat, Inc.
* Copyright (C) 2012 Fujitsu.
*
* This library is free software; you can redistribute it and/or
@@ -160,7 +161,7 @@ error:
return ret;
}
-/* test for virBitmapNextSetBit */
+/* test for virBitmapNextSetBit, virBitmapNextClearBit */
static int test4(const void *data ATTRIBUTE_UNUSED)
{
const char *bitsString = "0, 2-4, 6-10, 12, 14-18, 20, 22, 25";
@@ -169,17 +170,30 @@ static int test4(const void *data ATTRIBUTE_UNUSED)
0, 2, 3, 4, 6, 7, 8, 9, 10, 12,
14, 15, 16, 17, 18, 20, 22, 25
};
- int npos = 18;
+ int bitsPosInv[] = {
+ 1, 5, 11, 13, 19, 21, 23, 24, 26, 27,
+ 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39
+ };
virBitmapPtr bitmap = NULL;
int i, j;
+ if (ARRAY_CARDINALITY(bitsPos) + ARRAY_CARDINALITY(bitsPosInv) != size)
+ goto error;
+
/* 1. zero set */
bitmap = virBitmapNew(size);
if (!bitmap)
goto error;
- if (virBitmapNextSetBit(bitmap, -1) >= 0)
+ if (virBitmapNextSetBit(bitmap, -1) != -1)
+ goto error;
+
+ for (i = 0; i < size; i++) {
+ if (virBitmapNextClearBit(bitmap, i - 1) != i)
+ goto error;
+ }
+ if (virBitmapNextClearBit(bitmap, i) != -1)
goto error;
virBitmapFree(bitmap);
@@ -195,27 +209,39 @@ static int test4(const void *data ATTRIBUTE_UNUSED)
j = 0;
i = -1;
- while (j < npos) {
+ while (j < ARRAY_CARDINALITY(bitsPos)) {
i = virBitmapNextSetBit(bitmap, i);
if (i != bitsPos[j++])
goto error;
}
- if (virBitmapNextSetBit(bitmap, i) > 0)
+ if (virBitmapNextSetBit(bitmap, i) != -1)
+ goto error;
+
+ j = 0;
+ i = -1;
+
+ while (j < ARRAY_CARDINALITY(bitsPosInv)) {
+ i = virBitmapNextClearBit(bitmap, i);
+ if (i != bitsPosInv[j++])
+ goto error;
+ }
+
+ if (virBitmapNextClearBit(bitmap, i) != -1)
goto error;
/* 3. full set */
- i = -1;
virBitmapSetAll(bitmap);
- for (j = 0; j < size; j++) {
- i = virBitmapNextSetBit(bitmap, i);
- if (i != j)
+ for (i = 0; i < size; i++) {
+ if (virBitmapNextSetBit(bitmap, i - 1) != i)
goto error;
}
+ if (virBitmapNextSetBit(bitmap, i) != -1)
+ goto error;
- if (virBitmapNextSetBit(bitmap, i) > 0)
+ if (virBitmapNextClearBit(bitmap, -1) != -1)
goto error;
virBitmapFree(bitmap);
--
1.8.1