[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]

[libvirt] [PATCH v1 1/8] New functions for virBitmap



In many places we store bitmap info in a chunk of data
(pointed to by a char *), and have redundant codes to
set/unset bits. This patch extends virBitmap, and convert
those codes to use virBitmap in subsquent patches.
---
 .gitignore               |    1 +
 src/libvirt_private.syms |   10 ++
 src/util/bitmap.c        |  391 +++++++++++++++++++++++++++++++++++++++++++++-
 src/util/bitmap.h        |   23 +++
 tests/Makefile.am        |    8 +-
 tests/virbitmaptest.c    |  134 ++++++++++++++++
 6 files changed, 562 insertions(+), 5 deletions(-)
 create mode 100644 tests/virbitmaptest.c

diff --git a/.gitignore b/.gitignore
index 5041ddf..9aaa1f5 100644
--- a/.gitignore
+++ b/.gitignore
@@ -155,6 +155,7 @@
 /tests/storagebackendsheepdogtest
 /tests/utiltest
 /tests/viratomictest
+/tests/virbitmaptest
 /tests/virauthconfigtest
 /tests/virbuftest
 /tests/virdrivermoduletest
diff --git a/src/libvirt_private.syms b/src/libvirt_private.syms
index 27eb43e..9c27218 100644
--- a/src/libvirt_private.syms
+++ b/src/libvirt_private.syms
@@ -7,11 +7,21 @@
 
 # bitmap.h
 virBitmapAlloc;
+virBitmapAllocFromData;
+virBitmapClearAll;
 virBitmapClearBit;
+virBitmapCmp;
+virBitmapCopy;
+virBitmapFormat;
 virBitmapFree;
 virBitmapGetBit;
+virBitmapIsAllSet;
+virBitmapParse;
+virBitmapSetAll;
 virBitmapSetBit;
+virBitmapSize;
 virBitmapString;
+virBitmapToData;
 
 
 # buf.h
diff --git a/src/util/bitmap.c b/src/util/bitmap.c
index 53a8a38..2e668c6 100644
--- a/src/util/bitmap.c
+++ b/src/util/bitmap.c
@@ -33,15 +33,17 @@
 #include "bitmap.h"
 #include "memory.h"
 #include "buf.h"
+#include "util.h"
+#include "c-ctype.h"
 
 
 struct _virBitmap {
     size_t size;
-    unsigned long *map;
+    unsigned char *map;
 };
 
 
-#define VIR_BITMAP_BITS_PER_UNIT  ((int) sizeof(unsigned long) * CHAR_BIT)
+#define VIR_BITMAP_BITS_PER_UNIT  ((int) sizeof(unsigned char) * CHAR_BIT)
 #define VIR_BITMAP_UNIT_OFFSET(b) ((b) / VIR_BITMAP_BITS_PER_UNIT)
 #define VIR_BITMAP_BIT_OFFSET(b)  ((b) % VIR_BITMAP_BITS_PER_UNIT)
 #define VIR_BITMAP_BIT(b)         (1UL << VIR_BITMAP_BIT_OFFSET(b))
@@ -129,6 +131,12 @@ int virBitmapClearBit(virBitmapPtr bitmap, size_t b)
     return 0;
 }
 
+/* Helper function. caller must ensure b < bitmap->size */
+static bool bitmapIsset(virBitmapPtr bitmap, size_t b)
+{
+    return !!(bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] & VIR_BITMAP_BIT(b));
+}
+
 /**
  * virBitmapGetBit:
  * @bitmap: Pointer to bitmap
@@ -145,7 +153,7 @@ int virBitmapGetBit(virBitmapPtr bitmap, size_t b, bool *result)
     if (bitmap->size <= b)
         return -1;
 
-    *result = !!(bitmap->map[VIR_BITMAP_UNIT_OFFSET(b)] & VIR_BITMAP_BIT(b));
+    *result = bitmapIsset(bitmap, b);
     return 0;
 }
 
@@ -168,7 +176,7 @@ char *virBitmapString(virBitmapPtr bitmap)
           VIR_BITMAP_BITS_PER_UNIT;
 
     while (sz--) {
-        virBufferAsprintf(&buf, "%0*lx",
+        virBufferAsprintf(&buf, "%0*hx",
                           VIR_BITMAP_BITS_PER_UNIT / 4,
                           bitmap->map[sz]);
     }
@@ -180,3 +188,378 @@ char *virBitmapString(virBitmapPtr bitmap)
 
     return virBufferContentAndReset(&buf);
 }
+
+/**
+ * virBitmapFormat:
+ * @bitmap: the bitmap
+ *
+ * This function is the counterpart of virBitmapParse. This function creates
+ * a human-readable string representing the bits in bitmap.
+ *
+ * See virBitmapParse for the format of @str.
+ *
+ * Returns the string on success or NULL otherwise. Caller should call
+ * VIR_FREE to free the string.
+ */
+char *virBitmapFormat(virBitmapPtr bitmap)
+{
+    virBuffer buf =VIR_BUFFER_INITIALIZER;
+    int first = -1;
+    int start, cur;
+    int ret;
+    bool isset;
+
+    if (!bitmap)
+        return NULL;
+
+    cur = 0;
+    start = -1;
+    while (cur < bitmap->size) {
+        ret = virBitmapGetBit(bitmap, cur, &isset);
+        if (ret != 0)
+            goto error;
+        else if (isset) {
+            if (start == -1)
+                start = cur;
+        } else if (start != -1) {
+            if (!first)
+                virBufferAddLit(&buf, ",");
+            else
+                first = 0;
+            if (cur == start + 1)
+                virBufferAsprintf(&buf, "%d", start);
+            else
+                virBufferAsprintf(&buf, "%d-%d", start, cur - 1);
+            start = -1;
+        }
+        cur++;
+    }
+
+    if (start != -1) {
+        if (!first)
+            virBufferAddLit(&buf, ",");
+        if (cur == start + 1)
+            virBufferAsprintf(&buf, "%d", start);
+        else
+            virBufferAsprintf(&buf, "%d-%d", start, cur - 1);
+    }
+
+    if (virBufferError(&buf)) {
+error:
+        virBufferFreeAndReset(&buf);
+        return NULL;
+    }
+
+    return virBufferContentAndReset(&buf);
+}
+
+/**
+ * virBitmapParse:
+ * @str: points to a string representing a human-readable bitmap
+ * @bitmap: a bitmap created from @str
+ * @bitmapSize: the upper limit of num of bits in created bitmap
+ *
+ * This function is the counterpart of virBitmapFormat. This function creates
+ * a bitmap, in which bits are set according to the content of @str.
+ *
+ * @str is a comma separated string of fields N, which means a number of bit
+ * to set, and ^N, which means to unset the bit, and N-M for ranges of bits
+ * to set.
+ *
+ * Returns the number of bits set in @bitmap, or -1 in case of error.
+ */
+
+int virBitmapParse(const char *str,
+                   char sep,
+                   virBitmapPtr *bitmap,
+                   size_t bitmapSize)
+{
+    int ret = 0;
+    int neg = 0;
+    const char *cur;
+    char *tmp;
+    int i, start, last;
+
+    if (!str)
+        return -1;
+
+    cur = str;
+    virSkipSpaces(&cur);
+
+    if (*cur == 0)
+        return -1;
+
+    *bitmap = virBitmapAlloc(bitmapSize);
+    if (!*bitmap)
+        return -1;
+
+    while (*cur != 0 && *cur != sep) {
+        /*
+         * 3 constructs are allowed:
+         *     - N   : a single CPU number
+         *     - N-M : a range of CPU numbers with N < M
+         *     - ^N  : remove a single CPU number from the current set
+         */
+        if (*cur == '^') {
+            cur++;
+            neg = 1;
+        }
+
+        if (!c_isdigit(*cur))
+            goto parse_error;
+
+        if (virStrToLong_i(cur, &tmp, 10, &start) < 0)
+            goto parse_error;
+        if (start < 0)
+            goto parse_error;
+
+        cur = tmp;
+
+        virSkipSpaces(&cur);
+
+        if (*cur == ',' || *cur == 0 || *cur == sep) {
+            if (neg) {
+                if (bitmapIsset(*bitmap, start)) {
+                    ignore_value(virBitmapClearBit(*bitmap, start));
+                    ret--;
+                }
+            } else {
+                if (!bitmapIsset(*bitmap, start)) {
+                    ignore_value(virBitmapSetBit(*bitmap, start));
+                    ret++;
+                }
+            }
+        } else if (*cur == '-') {
+            if (neg)
+                goto parse_error;
+
+            cur++;
+            virSkipSpaces(&cur);
+
+            if (virStrToLong_i(cur, &tmp, 10, &last) < 0)
+                goto parse_error;
+            if (last < start)
+                goto parse_error;
+
+            cur = tmp;
+
+            for (i = start; i <= last; i++) {
+                if (!bitmapIsset(*bitmap, i)) {
+                    ignore_value(virBitmapSetBit(*bitmap, i));
+                    ret++;
+                }
+            }
+
+            virSkipSpaces(&cur);
+        }
+
+        if (*cur == ',') {
+            cur++;
+            virSkipSpaces(&cur);
+            neg = 0;
+        } else if(*cur == 0 || *cur == sep) {
+            break;
+        } else {
+            goto parse_error;
+        }
+    }
+
+    return ret;
+
+parse_error:
+    virBitmapFree(*bitmap);
+    *bitmap = NULL;
+    return -1;
+}
+
+/**
+ * virBitmapCopy:
+ * @src: the source bitmap.
+ *
+ * Makes a copy of bitmap @src.
+ *
+ * returns the copied bitmap on success, or NULL otherwise. Caller
+ * should call virBitmapFree to free the returned bitmap.
+ */
+virBitmapPtr virBitmapCopy(virBitmapPtr src)
+{
+    virBitmapPtr dst;
+    size_t sz;
+
+    sz = (src->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
+         VIR_BITMAP_BITS_PER_UNIT;
+
+    if (VIR_ALLOC(dst) < 0)
+        return NULL;
+
+    if (VIR_ALLOC_N(dst->map, sz) < 0) {
+        VIR_FREE(dst);
+        return NULL;
+    }
+
+    memcpy(dst->map, src->map, sz);
+    dst->size = src->size;
+
+    return dst;
+}
+
+/**
+ * virBitmapAllocFromData:
+ * @data: the data
+ * @len: len of @data in byte
+ *
+ * Allocate a bitmap from a chunk of data containing bits
+ * information
+ *
+ * Returns a pointer to the allocated bitmap or NULL if
+ * memory cannot be allocated.
+ */
+virBitmapPtr virBitmapAllocFromData(void *data, int len)
+{
+    virBitmapPtr bitmap;
+
+    bitmap = virBitmapAlloc(len * CHAR_BIT);
+    if (!bitmap)
+        return NULL;
+
+    memcpy(bitmap->map, data, len);
+
+    return bitmap;
+}
+
+/**
+ * virBitmapToData:
+ * @data: the data
+ * @len: len of @data in byte
+ *
+ * Convert a bitmap to a chunk of data containing bits information.
+ * Data consists of sequential bytes, with lower bytes containing
+ * lower bits.
+ *
+ * Returns 0 on success, -1 otherwise.
+ */
+int virBitmapToData(virBitmapPtr bitmap, char **data, int *dataLen)
+{
+    size_t sz;
+
+    sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
+         VIR_BITMAP_BITS_PER_UNIT;
+
+    if (VIR_ALLOC_N(*data, sz) < 0)
+        return -1;
+
+    memcpy(*data, bitmap->map, sz);
+    *dataLen = sz;
+
+    return 0;
+}
+
+/**
+ * virBitmapCmp:
+ * @b1: bitmap 1
+ * @b2: bitmap 2
+ *
+ * Compares two bitmaps. Returns true if two bitmaps have exactly
+ * the same set of bits set, otherwise false.
+ */
+bool virBitmapCmp(virBitmapPtr b1, virBitmapPtr b2)
+{
+    virBitmapPtr b;
+    size_t sz1, sz2, sz;
+    int i;
+
+    sz1 = (b1->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
+         VIR_BITMAP_BITS_PER_UNIT;
+    sz2 = (b2->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
+         VIR_BITMAP_BITS_PER_UNIT;
+
+    sz = sz1 < sz2 ? sz1 : sz2;
+
+    for (i = 0; i < sz; i++) {
+        if (b1->map[i] != b2->map[i])
+            return false;
+    }
+
+    b = sz1 > sz ? b1 : b2;
+    sz = sz1 > sz ? sz1 : sz2;
+    for (; i < sz; i++) {
+        if (b->map[i])
+            return false;
+    }
+
+    return true;
+}
+
+size_t virBitmapSize(virBitmapPtr bitmap)
+{
+    return bitmap->size;
+}
+
+/**
+ * virBitmapSetAll:
+ * @bitmap: the bitmap
+ *
+ * set all bits in @bitmap.
+ */
+void virBitmapSetAll(virBitmapPtr bitmap)
+{
+    int i;
+    size_t sz;
+
+    sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
+         VIR_BITMAP_BITS_PER_UNIT;
+
+    for (i = 0; i < sz; i++)
+        bitmap->map[i] = -1;
+}
+
+/**
+ * virBitmapClearAll:
+ * @bitmap: the bitmap
+ *
+ * clear all bits in @bitmap.
+ */
+void virBitmapClearAll(virBitmapPtr bitmap)
+{
+    int i;
+    size_t sz;
+
+    sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
+         VIR_BITMAP_BITS_PER_UNIT;
+
+    for (i = 0; i < sz; i++)
+        bitmap->map[i] = 0;
+}
+
+/**
+ * virBitmapIsAllSet:
+ * @bitmap: the bitmap to check
+ *
+ * check if all bits in @bitmap are set.
+ */
+bool virBitmapIsAllSet(virBitmapPtr bitmap)
+{
+    int i;
+    int unusedBits;
+    size_t sz, tmp;
+
+    sz = (bitmap->size + VIR_BITMAP_BITS_PER_UNIT - 1) /
+         VIR_BITMAP_BITS_PER_UNIT;
+    unusedBits = sz * VIR_BITMAP_BITS_PER_UNIT - bitmap->size;
+
+    tmp = sz;
+    if (unusedBits > 0)
+        tmp = sz - 1;
+
+    for (i = 0; i < tmp; i++)
+        if (bitmap->map[i] != (unsigned char)-1)
+            return false;
+
+    if (unusedBits > 0) {
+        if ((bitmap->map[sz - 1] & ((1 << (VIR_BITMAP_BITS_PER_UNIT - unusedBits + 1)) - 1))
+            != ((1 << (VIR_BITMAP_BITS_PER_UNIT - unusedBits + 1)) - 1))
+            return false;
+    }
+
+    return true;
+}
diff --git a/src/util/bitmap.h b/src/util/bitmap.h
index c3e6222..4823604 100644
--- a/src/util/bitmap.h
+++ b/src/util/bitmap.h
@@ -62,4 +62,27 @@ int virBitmapGetBit(virBitmapPtr bitmap, size_t b, bool *result)
 char *virBitmapString(virBitmapPtr bitmap)
     ATTRIBUTE_NONNULL(1) ATTRIBUTE_RETURN_CHECK;
 
+char *virBitmapFormat(virBitmapPtr bitmap);
+
+int virBitmapParse(const char *str,
+                   char sep,
+                   virBitmapPtr *bitmap,
+                   size_t bitmapSize);
+
+virBitmapPtr virBitmapCopy(virBitmapPtr src);
+
+virBitmapPtr virBitmapAllocFromData(void *data, int len);
+
+int virBitmapToData(virBitmapPtr bitmap, char **data, int *dataLen);
+
+bool virBitmapCmp(virBitmapPtr b1, virBitmapPtr b2);
+
+size_t virBitmapSize(virBitmapPtr bitmap);
+
+void virBitmapSetAll(virBitmapPtr bitmap);
+
+void virBitmapClearAll(virBitmapPtr bitmap);
+
+bool virBitmapIsAllSet(virBitmapPtr bitmap);
+
 #endif
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 8cf8015..ec436df 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -92,7 +92,8 @@ test_programs = virshtest sockettest \
 	viratomictest \
 	utiltest virnettlscontexttest shunloadtest \
 	virtimetest viruritest virkeyfiletest \
-	virauthconfigtest
+	virauthconfigtest \
+        virbitmaptest
 
 if WITH_SECDRIVER_SELINUX
 test_programs += securityselinuxtest
@@ -562,6 +563,10 @@ viratomictest_SOURCES = \
 	viratomictest.c testutils.h testutils.c
 viratomictest_LDADD = $(LDADDS)
 
+virbitmaptest_SOURCES = \
+	virbitmaptest.c testutils.h testutils.c
+virbitmaptest_LDADD = $(LDADDS)
+
 jsontest_SOURCES = \
 	jsontest.c testutils.h testutils.c
 jsontest_LDADD = $(LDADDS)
@@ -592,6 +597,7 @@ shunloadtest_SOURCES = \
 shunloadtest_LDADD = $(LIB_PTHREAD)
 shunloadtest_DEPENDENCIES = libshunload.la
 
+
 if WITH_CIL
 CILOPTFLAGS =
 CILOPTINCS =
diff --git a/tests/virbitmaptest.c b/tests/virbitmaptest.c
new file mode 100644
index 0000000..c688618
--- /dev/null
+++ b/tests/virbitmaptest.c
@@ -0,0 +1,134 @@
+/*
+ * Copyright (C) 2012 Fujitsu.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library;  If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include <config.h>
+
+#include <time.h>
+#include <sched.h>
+
+#include "testutils.h"
+
+#include "bitmap.h"
+
+static int test1(const void *data ATTRIBUTE_UNUSED)
+{
+    virBitmapPtr bitmap;
+    int size;
+    int bit;
+    bool result;
+
+    size = 1024;
+    bit = 100;
+    bitmap = virBitmapAlloc(size);
+    if (virBitmapSetBit(bitmap, bit) < 0)
+        return -1;
+
+    if (virBitmapGetBit(bitmap, bit, &result) < 0)
+        return -1;
+
+    if (!result)
+        return -1;
+
+    if (virBitmapGetBit(bitmap, bit + 1, &result) < 0)
+        return -1;
+
+    if (result)
+        return -1;
+
+    return 0;
+}
+
+bool testBit(virBitmapPtr bitmap, unsigned int start, unsigned int end)
+{
+    int i;
+    bool result;
+
+    for (i = start; i <= end; i++) {
+        if (virBitmapGetBit(bitmap, i, &result) < 0)
+            return 0;
+        if (!result)
+            return 0;
+    }
+
+    return 1;
+}
+
+static int test2(const void *data ATTRIBUTE_UNUSED)
+{
+    const char *bitsString1 = "1-32,50,88-99,1021-1023";
+    char *bitsString2 = NULL;
+    virBitmapPtr bitmap = NULL;
+    int ret = -1;
+    int size = 1024;
+
+    if (virBitmapParse(bitsString1, 0, &bitmap, size) < 0)
+        goto error;
+
+    if (!testBit(bitmap, 1, 32))
+        goto error;
+    if (!testBit(bitmap, 50, 50))
+        goto error;
+    if (!testBit(bitmap, 88, 99))
+        goto error;
+    if (!testBit(bitmap, 1021, 1023))
+        goto error;
+
+    if (testBit(bitmap, 0, 0))
+        goto error;
+    if (testBit(bitmap, 33,49))
+        goto error;
+    if (testBit(bitmap, 51,87))
+        goto error;
+    if (testBit(bitmap, 100,1020))
+        goto error;
+
+    bitsString2 = virBitmapFormat(bitmap);
+    if (strcmp(bitsString1, bitsString2))
+        goto error;
+
+    virBitmapSetAll(bitmap);
+    if (!testBit(bitmap, 0, size - 1))
+        goto error;
+
+    virBitmapClearAll(bitmap);
+    if (testBit(bitmap, 0, size - 1))
+        goto error;
+
+    ret = 0;
+
+error:
+    virBitmapFree(bitmap);
+    VIR_FREE(bitsString2);
+    return ret;
+}
+
+static int
+mymain(void)
+{
+    int ret = 0;
+
+    if (virtTestRun("test1", 1, test1, NULL) < 0)
+        ret = -1;
+    if (virtTestRun("test2", 1, test2, NULL) < 0)
+        ret = -1;
+
+    return ret;
+}
+
+VIRT_TEST_MAIN(mymain)
-- 
1.7.10.2


[Date Prev][Date Next]   [Thread Prev][Thread Next]   [Thread Index] [Date Index] [Author Index]