[libvirt] [PATCH 1/3] util: bitmap: Intoduce self-expanding bitmap APIs
Peter Krempa
pkrempa at redhat.com
Tue Mar 22 14:00:11 UTC 2016
In some cases it's impractical to use the regular APIs as the bitmap
size needs to be pre-declared. These new APIs allow to use bitmaps that
self expand.
The new code adds a property to the bitmap to track the alocation of
memory so that VIR_RESIZE_N can be used.
---
src/libvirt_private.syms | 3 ++
src/util/virbitmap.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++
src/util/virbitmap.h | 8 +++++
tests/virbitmaptest.c | 51 ++++++++++++++++++++++++++
4 files changed, 155 insertions(+)
diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms
index af133c5..311858f 100644
--- a/src/libvirt_private.syms
+++ b/src/libvirt_private.syms
@@ -1134,6 +1134,7 @@ virAuthConfigNewData;
# util/virbitmap.h
virBitmapClearAll;
virBitmapClearBit;
+virBitmapClearBitExpand;
virBitmapCopy;
virBitmapCountBits;
virBitmapDataToString;
@@ -1148,6 +1149,7 @@ virBitmapLastSetBit;
virBitmapNew;
virBitmapNewCopy;
virBitmapNewData;
+virBitmapNewEmpty;
virBitmapNewQuiet;
virBitmapNextClearBit;
virBitmapNextSetBit;
@@ -1155,6 +1157,7 @@ virBitmapOverlaps;
virBitmapParse;
virBitmapSetAll;
virBitmapSetBit;
+virBitmapSetBitExpand;
virBitmapSize;
virBitmapString;
virBitmapSubtract;
diff --git a/src/util/virbitmap.c b/src/util/virbitmap.c
index f116607..cce91f2 100644
--- a/src/util/virbitmap.c
+++ b/src/util/virbitmap.c
@@ -43,6 +43,7 @@
struct _virBitmap {
size_t max_bit;
size_t map_len;
+ size_t map_alloc;
unsigned long *map;
};
@@ -83,6 +84,7 @@ virBitmapNewQuiet(size_t size)
bitmap->max_bit = size;
bitmap->map_len = sz;
+ bitmap->map_alloc = sz;
return bitmap;
}
@@ -109,6 +111,25 @@ virBitmapNew(size_t size)
/**
+ * virBitmapNewEmpty
+ *
+ * Allocate an empty bitmap. It can be used with self-expanding APIs.
+ *
+ * Returns a pointer to the allocated bitmap or NULL if memory cannot be
+ * allocated. Reports libvirt errors.
+ */
+virBitmapPtr
+virBitmapNewEmpty(void)
+{
+ virBitmapPtr ret;
+
+ ignore_value(VIR_ALLOC(ret));
+
+ return ret;
+}
+
+
+/**
* virBitmapFree:
* @bitmap: previously allocated bitmap
*
@@ -155,6 +176,54 @@ int virBitmapSetBit(virBitmapPtr bitmap, size_t b)
}
/**
+ * virBitmapExpand:
+ * @map: Pointer to bitmap
+ * @b: bit position to include in bitmap
+ *
+ * Resizes the bitmap so that bit @b will fit into it. This shall be called only
+ * if @b would not fit into the map.
+ *
+ * Returns 0 on success, -1 on error.
+ */
+static int virBitmapExpand(virBitmapPtr map, size_t b)
+{
+ size_t new_len = VIR_DIV_UP(b, VIR_BITMAP_BITS_PER_UNIT);
+
+ /* resize the memory if necessary */
+ if (map->map_len < new_len) {
+ if (VIR_RESIZE_N(map->map, map->map_alloc, map->map_len,
+ new_len - map->map_len) < 0)
+ return -1;
+ }
+
+ map->max_bit = b + 1;
+ map->map_len = new_len;
+
+ return 0;
+}
+
+
+/**
+ * virBitmapSetBitExpand:
+ * @bitmap: Pointer to bitmap
+ * @b: bit position to set
+ *
+ * Set bit position @b in @bitmap. Expands the bitmap as necessary so that @b is
+ * included in the map.
+ *
+ * Returns 0 on if bit is successfully set, -1 on error.
+ */
+int virBitmapSetBitExpand(virBitmapPtr bitmap, size_t b)
+{
+ if (bitmap->max_bit <= b && virBitmapExpand(bitmap, b) < 0)
+ return -1;
+
+ bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] |= VIR_BITMAP_BIT(b);
+ return 0;
+}
+
+
+/**
* virBitmapClearBit:
* @bitmap: Pointer to bitmap
* @b: bit position to clear
@@ -172,6 +241,30 @@ int virBitmapClearBit(virBitmapPtr bitmap, size_t b)
return 0;
}
+
+/**
+ * virBitmapClearBitExpand:
+ * @bitmap: Pointer to bitmap
+ * @b: bit position to set
+ *
+ * Clear bit position @b in @bitmap. Expands the bitmap as necessary so that
+ * @b is included in the map.
+ *
+ * Returns 0 on if bit is successfully cleared, -1 on error.
+ */
+int virBitmapClearBitExpand(virBitmapPtr bitmap, size_t b)
+{
+ if (bitmap->max_bit <= b) {
+ if (virBitmapExpand(bitmap, b) < 0)
+ return -1;
+ } else {
+ bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] &= ~VIR_BITMAP_BIT(b);
+ }
+
+ return 0;
+}
+
+
/* Helper function. caller must ensure b < bitmap->max_bit */
static bool virBitmapIsSet(virBitmapPtr bitmap, size_t b)
{
diff --git a/src/util/virbitmap.h b/src/util/virbitmap.h
index 846aca3..79f53dd 100644
--- a/src/util/virbitmap.h
+++ b/src/util/virbitmap.h
@@ -37,6 +37,7 @@ typedef virBitmap *virBitmapPtr;
*/
virBitmapPtr virBitmapNewQuiet(size_t size) ATTRIBUTE_RETURN_CHECK;
virBitmapPtr virBitmapNew(size_t size) ATTRIBUTE_RETURN_CHECK;
+virBitmapPtr virBitmapNewEmpty(void) ATTRIBUTE_RETURN_CHECK;
/*
* Free previously allocated bitmap
@@ -55,12 +56,19 @@ int virBitmapCopy(virBitmapPtr dst, virBitmapPtr src);
int virBitmapSetBit(virBitmapPtr bitmap, size_t b)
ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK;
+int virBitmapSetBitExpand(virBitmapPtr bitmap, size_t b)
+ ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK;
+
+
/*
* Clear bit position @b in @bitmap
*/
int virBitmapClearBit(virBitmapPtr bitmap, size_t b)
ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK;
+int virBitmapClearBitExpand(virBitmapPtr bitmap, size_t b)
+ ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK;
+
/*
* Get bit @b in @bitmap. Returns false if b is out of range.
*/
diff --git a/tests/virbitmaptest.c b/tests/virbitmaptest.c
index 967a5c8..92f1e6e 100644
--- a/tests/virbitmaptest.c
+++ b/tests/virbitmaptest.c
@@ -590,6 +590,54 @@ test11(const void *opaque)
return ret;
}
+#define TEST_MAP(sz, expect) \
+ do { \
+ char *actual = virBitmapFormat(map); \
+ if (virBitmapSize(map) != sz) { \
+ fprintf(stderr, "\n expected bitmap size: '%d' actual size: " \
+ "'%zu'\n", sz, virBitmapSize(map)); \
+ goto cleanup; \
+ } \
+ if (STRNEQ_NULLABLE(expect, actual)) { \
+ fprintf(stderr, "\n expected bitmap contents '%s' actual contents "\
+ "'%s'\n", NULLSTR(expect), NULLSTR(actual)); \
+ VIR_FREE(actual); \
+ goto cleanup; \
+ } \
+ VIR_FREE(actual); \
+ } while (0)
+
+/* test self-expanding bitmap APIs */
+static int
+test12(const void *opaque ATTRIBUTE_UNUSED)
+{
+ virBitmapPtr map = NULL;
+ int ret = -1;
+
+ if (!(map = virBitmapNewEmpty()))
+ return -1;
+
+ TEST_MAP(0, "");
+
+ if (virBitmapSetBitExpand(map, 100) < 0)
+ goto cleanup;
+
+ TEST_MAP(101, "100");
+
+ if (virBitmapClearBitExpand(map, 150) < 0)
+ goto cleanup;
+
+ TEST_MAP(151, "100");
+
+ ret = 0;
+
+ cleanup:
+ virBitmapFree(map);
+ return ret;
+}
+#undef TEST_MAP
+
+
#define TESTBINARYOP(A, B, RES, FUNC) \
testBinaryOpData.a = A; \
testBinaryOpData.b = B; \
@@ -633,6 +681,9 @@ mymain(void)
TESTBINARYOP("0-3", "0,^0", "0-3", test11);
TESTBINARYOP("0,2", "1,3", "0,2", test11);
+ if (virtTestRun("test12", test12, NULL) < 0)
+ ret = -1;
+
return ret;
}
--
2.7.3
More information about the libvir-list
mailing list