[libvirt] [RFC][PATCH] Growable bitmap implementation

Stefan Berger stefanb at linux.vnet.ibm.com
Mon Feb 4 17:01:16 UTC 2013


Add a growable bitmap implementation building on top of the 'regular'
bitmap implementation. (no doubt, this could also be done differently...)

This patch also adds a test virgbitmaptest.c that is largely a copy of
virbitmaptest.c with some minor modifications to test for growth of the
bitmap.

Signed-off-by: Stefan Berger <stefanb at linux.vnet.ibm.com>

---
PS: This patch builds on top of a patch with a virBitmapNextClearBit
     implementation.

---
  src/Makefile.am          |    1
  src/libvirt_private.syms |   22 ++
  src/util/virbitmap.c     |   17 +
  src/util/virbitmap.h     |    6
  src/util/virgbitmap.c    |  348 ++++++++++++++++++++++++++++++++
  src/util/virgbitmap.h    |   95 ++++++++
  tests/Makefile.am        |    5
  tests/virgbitmaptest.c   |  499 
+++++++++++++++++++++++++++++++++++++++++++++++
  8 files changed, 993 insertions(+)

Index: libvirt/src/Makefile.am
===================================================================
--- libvirt.orig/src/Makefile.am
+++ libvirt/src/Makefile.am
@@ -71,6 +71,7 @@ UTIL_SOURCES =                            \
          util/virevent.c util/virevent.h            \
          util/vireventpoll.c util/vireventpoll.h        \
          util/virfile.c util/virfile.h            \
+        util/virgbitmap.c util/virgbitmap.h        \
          util/virhash.c util/virhash.h            \
          util/virhashcode.c util/virhashcode.h        \
          util/virhook.c util/virhook.h            \
Index: libvirt/src/util/virbitmap.c
===================================================================
--- libvirt.orig/src/util/virbitmap.c
+++ libvirt/src/util/virbitmap.c
@@ -111,6 +111,23 @@ int virBitmapCopy(virBitmapPtr dst, virB
      return 0;
  }

+/*
+ * virBitmapCopyResize:
+ * @dst: Destination bitmap
+ * @src: Source bitmap
+ *
+ * Copy bits from source bitmap @src into destination bitmap @dst
+ * where the source and destination bitmaps may be of different size.
+ * Any bits not found in the source bitmap will remain untouched
+ * in the destination bitmap.
+ */
+void virBitmapCopyResize(virBitmapPtr dst, virBitmapPtr src)
+{
+    size_t tocopy = MIN(src->map_len, dst->map_len);
+
+    memcpy(dst->map, src->map,
+           tocopy * sizeof(src->map[0]));
+}

  /**
   * virBitmapSetBit:
Index: libvirt/src/util/virbitmap.h
===================================================================
--- libvirt.orig/src/util/virbitmap.h
+++ libvirt/src/util/virbitmap.h
@@ -49,6 +49,12 @@ void virBitmapFree(virBitmapPtr bitmap);
  int virBitmapCopy(virBitmapPtr dst, virBitmapPtr src);

  /*
+ * Copy bits from @src to @dst. The bitmap sizes
+ * need not be the same
+ */
+void virBitmapCopyResize(virBitmapPtr dst, virBitmapPtr src);
+
+/*
   * Set bit position @b in @bitmap
   */
  int virBitmapSetBit(virBitmapPtr bitmap, size_t b)
Index: libvirt/src/util/virgbitmap.c
===================================================================
--- /dev/null
+++ libvirt/src/util/virgbitmap.c
@@ -0,0 +1,348 @@
+/*
+ * virgbitmap.c: Growable bitmap operations
+ *
+ * Copyright (C) 2013 IBM Corporation
+ *
+ * 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/>.
+ *
+ * Author: Stefan Berger <stefanb at linux.vnet.ibm.com>
+ */
+
+#include <config.h>
+
+#include "virgbitmap.h"
+#include "viralloc.h"
+
+struct _virGBitmap {
+    virBitmapPtr bitmap;
+};
+
+/**
+ * virGBitmapNew:
+ * @size: number of bits
+ *
+ * Allocate a growable bitmap capable of initially containing @size bits.
+ *
+ * Returns a pointer to the allocated bitmap or NULL if
+ * memory cannot be allocated.
+ */
+virGBitmapPtr virGBitmapNew(size_t size)
+{
+    virGBitmapPtr bitmap;
+
+    if (VIR_ALLOC(bitmap) < 0)
+        return NULL;
+
+    bitmap->bitmap = virBitmapNew(size);
+
+    if (!bitmap->bitmap) {
+        virGBitmapFree(bitmap);
+        return NULL;
+    }
+
+    return bitmap;
+}
+
+/**
+ * virGBitmapFree:
+ * @bitmap: previously allocated bitmap
+ *
+ * Free @bitmap previously allocated by virBitmapNew.
+ */
+void virGBitmapFree(virGBitmapPtr bitmap)
+{
+    if (bitmap) {
+        virBitmapFree(bitmap->bitmap);
+        VIR_FREE(bitmap);
+    }
+}
+
+/**
+ * virGBitmapResize:
+ * @bitmap: previously allocated bitmap
+ * @new_size: new size of the bitmap
+ *
+ * Resize the @bitmap to the given @new_size. Old bits are copied
+ * into the new
+ */
+static int virGBitmapResize(virGBitmapPtr bitmap, size_t new_size)
+{
+    virBitmapPtr bm;
+
+    if (!(bm = virBitmapNew(new_size)))
+        return -1;
+
+    virBitmapCopyResize(bm, bitmap->bitmap);
+
+    virBitmapFree(bitmap->bitmap);
+    bitmap->bitmap = bm;
+
+    return 0;
+}
+
+/**
+ * virGBitmapSetBit:
+ * @bitmap: Pointer to growable bitmap
+ * @b: bit position to set
+ *
+ * Set bit position @b in @bitmap. Grow the @bitmap if necessary
+ * filling newly allocated bits with zeros.
+ *
+ * Returns 0 on if bit is successfully set, -1 on error.
+ */
+int virGBitmapSetBit(virGBitmapPtr bitmap, ssize_t b)
+{
+    if (virBitmapSize(bitmap->bitmap) <= b &&
+        virGBitmapResize(bitmap,
+                       ((unsigned long long)b * 120) / 100) < 0)
+        return -1;
+
+    return virBitmapSetBit(bitmap->bitmap, b);
+}
+
+/**
+ * virBitmapGetBit:
+ * @bitmap: Pointer to bitmap
+ * @b: bit position to get
+ * @result: bool pointer to receive bit setting
+ *
+ * Get setting of bit position @b in @bitmap and store in @result.
+ * Note: If the bitmap is not currently large enough, it will grow
+ * to at least the size of the bit position @b.
+ *
+ * On success, @result will contain the setting of @b and 0 is
+ * returned.  On failure, -1 is returned and @result is unchanged.
+ */
+int virGBitmapGetBit(virGBitmapPtr bitmap, size_t b, bool *result)
+{
+    if (virBitmapSize(bitmap->bitmap) <= b) {
+        if (virGBitmapResize(bitmap,
+                             ((unsigned long long)b * 120) / 100) < 0)
+            return -1;
+        *result = 0;
+        return 0;
+    }
+
+    return virBitmapGetBit(bitmap->bitmap, b, result);
+}
+
+/**
+ * virGBitmapFormat:
+ * @bitmap: the bitmap
+ *
+ * This function is the counterpart of virGBitmapParse. This function 
creates
+ * a human-readable string representing the bits in bitmap.
+ *
+ * See virGBitmapParse for the format of @str.
+ *
+ * Returns the string on success or NULL otherwise. Caller should call
+ * VIR_FREE to free the string.
+ */
+char *virGBitmapFormat(virGBitmapPtr bitmap)
+{
+    return virBitmapFormat(bitmap->bitmap);
+}
+
+size_t virGBitmapSize(virGBitmapPtr bitmap)
+{
+    return virBitmapSize(bitmap->bitmap);
+}
+
+/**
+ * virGBitmapSetAll:
+ * @bitmap: the bitmap
+ *
+ * set all bits in @bitmap.
+ */
+void virGBitmapSetAll(virGBitmapPtr bitmap)
+{
+    virBitmapSetAll(bitmap->bitmap);
+}
+
+/**
+ * virGBitmapClearAll:
+ * @bitmap: the bitmap
+ *
+ * clear all bits in @bitmap.
+ */
+void virGBitmapClearAll(virGBitmapPtr bitmap)
+{
+    virBitmapClearAll(bitmap->bitmap);
+}
+
+/**
+ * virGBitmapIsAllSet:
+ * @bitmap: the bitmap to check
+ *
+ * check if all bits in @bitmap are set.
+ */
+bool virGBitmapIsAllSet(virGBitmapPtr bitmap)
+{
+    return virBitmapIsAllSet(bitmap->bitmap);
+}
+
+/**
+ * virGBitmapParse:
+ * @str: points to a string representing a human-readable bitmap
+ * @terminator: character separating the bitmap to parse
+ * @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.
+ *
+ * To allow parsing of bitmaps within larger strings it is possible to set
+ * a termination character in the argument @terminator. When the character
+ * in @terminator is encountered in @str, the parsing of the bitmap stops.
+ * Pass 0 as @terminator if it is not needed. Whitespace characters may not
+ * be used as terminators.
+ *
+ * Returns the number of bits set in @bitmap, or -1 in case of error.
+ */
+int
+virGBitmapParse(const char *str,
+               char terminator,
+               virGBitmapPtr *bitmap,
+               size_t bitmapSize)
+{
+    virGBitmapPtr res;
+
+    if (VIR_ALLOC(res) < 0)
+        return -1;
+
+    if (virBitmapParse(str, terminator, &res->bitmap, bitmapSize) < 0) {
+        VIR_FREE(res);
+        return -1;
+    }
+
+    *bitmap = res;
+
+    return 0;
+}
+
+
+/**
+ * virGBitmapNewData:
+ * @data: the data
+ * @len: length of @data in bytes
+ *
+ * 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.
+ */
+virGBitmapPtr virGBitmapNewData(void *data, int len)
+{
+    virGBitmapPtr res;
+
+    if (VIR_ALLOC(res) < 0)
+        return NULL;
+
+    res->bitmap = virBitmapNewData(data, len);
+    if (!res->bitmap) {
+        VIR_FREE(res);
+        return NULL;
+    }
+
+    return res;
+}
+
+/**
+ * virGBitmapToData:
+ * @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 virGBitmapToData(virGBitmapPtr bitmap, unsigned char **data, int 
*dataLen)
+{
+    return virBitmapToData(bitmap->bitmap, data, dataLen);
+}
+
+
+/**
+ * virGBitmapNextSetBit:
+ * @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.
+ * @pos can be -1 to search for the first set bit. Position starts
+ * at 0. This function will never grow the bitmap.
+ *
+ * returns the position of the found bit, or -1 if no bit found.
+ */
+ssize_t virGBitmapNextSetBit(virGBitmapPtr bitmap, ssize_t pos)
+{
+    /* never grow since we won't find set bits there */
+    return virBitmapNextSetBit(bitmap->bitmap, pos);
+}
+
+/**
+ * virGBitmapNextClearBit:
+ * @bitmap: the bitmap
+ * @pos: the position after which to search for a set bit
+ *
+ * Search 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. This function will grow the bitmap if the currently allocated
+ * bitmap has all bits set.
+ *
+ * returns the position of the found bit, or -1 if no bit found.
+ */
+ssize_t virGBitmapNextClearBit(virGBitmapPtr bitmap, ssize_t pos)
+{
+    size_t lastpos, newsize, max_bit;
+    ssize_t res;
+
+    if (pos < 0)
+        pos = -1;
+
+    if (pos < (ssize_t)virBitmapSize(bitmap->bitmap)) {
+        res =  virBitmapNextClearBit(bitmap->bitmap, pos);
+
+        if (res >= 0)
+            return res;
+    }
+
+    max_bit = virBitmapSize(bitmap->bitmap);
+
+    lastpos = max_bit - 1;
+    if (pos > lastpos)
+        lastpos = pos;
+
+    newsize = (max_bit > 80)
+              ? ((unsigned long long)max_bit * 120) / 100 /* 20 % growth */
+              : max_bit + 24;
+    if (virGBitmapResize(bitmap, newsize) < 0)
+        return -1;
+
+    return virBitmapNextClearBit(bitmap->bitmap, lastpos);
+}
+
+/* Return the number of bits currently set in the map.  */
+size_t
+virGBitmapCountBits(virGBitmapPtr bitmap)
+{
+    return virBitmapCountBits(bitmap->bitmap);
+}
Index: libvirt/src/util/virgbitmap.h
===================================================================
--- /dev/null
+++ libvirt/src/util/virgbitmap.h
@@ -0,0 +1,95 @@
+/*
+ * virgbitmap.h: Growable bitmap operations
+ *
+ * Copyright (C) 2013 IBM Corporation
+ *
+ * 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/>.
+ *
+ * Derived from virbitmap.h.
+ *
+ * Author: Stefan Berger <stefanb at linux.vnet.ibm.com>
+ */
+
+#ifndef __GBITMAP_H__
+# define __GBITMAP_H__
+
+# include "internal.h"
+
+# include <sys/types.h>
+
+# include "virbitmap.h"
+
+typedef struct _virGBitmap virGBitmap;
+typedef virGBitmap *virGBitmapPtr;
+
+/*
+ * Allocate a bitmap capable of initially containing @size bits.
+ */
+virGBitmapPtr virGBitmapNew(size_t size) ATTRIBUTE_RETURN_CHECK;
+
+/*
+ * Free previously allocated bitmap
+ */
+void virGBitmapFree(virGBitmapPtr bitmap);
+
+/*
+ * Set bit position @b in @bitmap
+ */
+int virGBitmapSetBit(virGBitmapPtr bitmap, ssize_t pos)
+    ATTRIBUTE_NONNULL(1);
+
+/*
+ * Get setting of bit position @b in @bitmap and store in @result
+ */
+int virGBitmapGetBit(virGBitmapPtr bitmap, size_t b, bool *result)
+    ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3) ATTRIBUTE_RETURN_CHECK;
+
+char *virGBitmapFormat(virGBitmapPtr bitmap)
+    ATTRIBUTE_NONNULL(1);
+
+int virGBitmapParse(const char *str,
+                    char sep,
+                    virGBitmapPtr *bitmap,
+                    size_t bitmapSize);
+
+virGBitmapPtr virGBitmapNewData(void *data, int len) ATTRIBUTE_NONNULL(1);
+
+int virGBitmapToData(virGBitmapPtr bitmap, unsigned char **data, int 
*dataLen)
+    ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(2);
+
+size_t virGBitmapSize(virGBitmapPtr bitmap)
+    ATTRIBUTE_NONNULL(1);
+
+void virGBitmapSetAll(virGBitmapPtr bitmap)
+    ATTRIBUTE_NONNULL(1);
+
+void virGBitmapClearAll(virGBitmapPtr bitmap)
+    ATTRIBUTE_NONNULL(1);
+
+bool virGBitmapIsAllSet(virGBitmapPtr bitmap)
+    ATTRIBUTE_NONNULL(1);
+
+    ATTRIBUTE_NONNULL(1) ATTRIBUTE_NONNULL(3);
+
+ssize_t virGBitmapNextSetBit(virGBitmapPtr bitmap, ssize_t pos)
+    ATTRIBUTE_NONNULL(1);
+
+ssize_t virGBitmapNextClearBit(virGBitmapPtr bitmap, ssize_t pos)
+    ATTRIBUTE_NONNULL(1);
+
+size_t virGBitmapCountBits(virGBitmapPtr bitmap)
+    ATTRIBUTE_NONNULL(1);
+
+#endif
Index: libvirt/tests/Makefile.am
===================================================================
--- libvirt.orig/tests/Makefile.am
+++ libvirt/tests/Makefile.am
@@ -96,6 +96,7 @@ test_programs = virshtest sockettest \
      virtimetest viruritest virkeyfiletest \
      virauthconfigtest \
      virbitmaptest \
+    virgbitmaptest \
      virlockspacetest \
      virstringtest \
          virportallocatortest \
@@ -649,6 +650,10 @@ virbitmaptest_SOURCES = \
      virbitmaptest.c testutils.h testutils.c
  virbitmaptest_LDADD = $(LDADDS)

+virgbitmaptest_SOURCES = \
+    virgbitmaptest.c testutils.h testutils.c
+virgbitmaptest_LDADD = $(LDADDS)
+
  jsontest_SOURCES = \
      jsontest.c testutils.h testutils.c
  jsontest_LDADD = $(LDADDS)
Index: libvirt/tests/virgbitmaptest.c
===================================================================
--- /dev/null
+++ libvirt/tests/virgbitmaptest.c
@@ -0,0 +1,499 @@
+/*
+ * 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 "testutils.h"
+
+#include "virgbitmap.h"
+
+static int test1(const void *data ATTRIBUTE_UNUSED)
+{
+    virGBitmapPtr bitmap;
+    int size;
+    int bit;
+    bool result;
+    int ret = -1;
+
+    size = 1024;
+    bit = 100;
+    if (!(bitmap = virGBitmapNew(size)))
+        goto error;
+
+    if (virGBitmapSetBit(bitmap, bit) < 0)
+        goto error;
+
+    if (virGBitmapGetBit(bitmap, bit, &result) < 0)
+        goto error;
+
+    if (!result)
+        goto error;
+
+    if (virGBitmapGetBit(bitmap, bit + 1, &result) < 0)
+        goto error;
+
+    if (result)
+        goto error;
+
+    ret = 0;
+
+error:
+    virGBitmapFree(bitmap);
+    return ret;
+}
+
+static int
+testBit(virGBitmapPtr bitmap,
+        unsigned int start,
+        unsigned int end,
+        bool expected)
+{
+    int i;
+    bool result;
+
+    for (i = start; i <= end; i++) {
+        if (virGBitmapGetBit(bitmap, i, &result) < 0)
+            return -1;
+        if (result == expected)
+            return 0;
+    }
+
+    return -1;
+}
+
+static int test2(const void *data ATTRIBUTE_UNUSED)
+{
+    const char *bitsString1 = "1-32,50,88-99,1021-1023";
+    const char *bitsStringAfter = "1-32,50,88-99,1021-1023,1111";
+    char *bitsString2 = NULL, *bitsString3 = NULL;
+    virGBitmapPtr bitmap = NULL;
+    int ret = -1;
+    int size = 1025;
+
+    if (virGBitmapParse(bitsString1, 0, &bitmap, size) < 0)
+        goto error;
+
+    if (testBit(bitmap, 1, 32, true) < 0)
+        goto error;
+    if (testBit(bitmap, 50, 50, true) < 0)
+        goto error;
+    if (testBit(bitmap, 88, 99, true) < 0)
+        goto error;
+    if (testBit(bitmap, 1021, 1023, true) < 0)
+        goto error;
+
+    if (testBit(bitmap, 0, 0, false) < 0)
+        goto error;
+    if (testBit(bitmap, 33, 49, false) < 0)
+        goto error;
+    if (testBit(bitmap, 51, 87, false) < 0)
+        goto error;
+    if (testBit(bitmap, 100, 1020, false) < 0)
+        goto error;
+
+    if (virGBitmapCountBits(bitmap) != 48)
+        goto error;
+
+    if (!(bitsString2 = virGBitmapFormat(bitmap)))
+        goto error;
+    if (strcmp(bitsString1, bitsString2))
+        goto error;
+
+    if (virGBitmapSetBit(bitmap, 1111) < 0)
+        goto error;
+
+    if (!(bitsString3 = virGBitmapFormat(bitmap)))
+        goto error;
+    if (strcmp(bitsStringAfter, bitsString3))
+        goto error;
+
+    size = 1111;
+    virGBitmapSetAll(bitmap);
+    if (testBit(bitmap, 0, size - 1, true) < 0)
+        goto error;
+    if (virGBitmapCountBits(bitmap) < size)
+        goto error;
+
+    if (!virGBitmapIsAllSet(bitmap))
+        goto error;
+
+    virGBitmapClearAll(bitmap);
+    if (testBit(bitmap, 0, size - 1, false) < 0)
+        goto error;
+    if (virGBitmapCountBits(bitmap) != 0)
+        goto error;
+
+    ret = 0;
+
+error:
+    virGBitmapFree(bitmap);
+    VIR_FREE(bitsString2);
+    VIR_FREE(bitsString3);
+    return ret;
+}
+
+static int test3(const void *data ATTRIBUTE_UNUSED)
+{
+    virGBitmapPtr bitmap = NULL;
+    int ret = -1;
+    int size = 5;
+    int i;
+
+    if ((bitmap = virGBitmapNew(size)) == NULL)
+        goto error;
+
+    for (i = 0; i < size * 2; i++)
+        ignore_value(virGBitmapSetBit(bitmap, i));
+
+    if (virGBitmapSize(bitmap) < (2 * size))
+        goto error;
+
+    if (!virGBitmapIsAllSet(bitmap))
+        goto error;
+
+    ret = 0;
+
+error:
+    virGBitmapFree(bitmap);
+    return ret;
+}
+
+/* test for virGBitmapNextSetBit */
+static int test4(const void *data ATTRIBUTE_UNUSED)
+{
+    const char *bitsString = "0, 2-4, 6-10, 12, 14-18, 20, 22, 25";
+    int size = 40;
+    int bitsPos[] = {
+        0,  2,  3,  4,  6,  7,  8,  9, 10, 12,
+        14, 15, 16, 17, 18, 20, 22, 25
+    };
+    int npos = 18;
+    virGBitmapPtr bitmap = NULL;
+    int i, j;
+
+    /* 1. zero set */
+
+    bitmap = virGBitmapNew(size);
+    if (!bitmap)
+        goto error;
+
+    if (virGBitmapNextSetBit(bitmap, -1) >= 0)
+        goto error;
+
+    virGBitmapFree(bitmap);
+    bitmap = NULL;
+
+    /* 2. partial set */
+
+    if (virGBitmapParse(bitsString, 0, &bitmap, size) < 0)
+        goto error;
+    if (!bitmap)
+        goto error;
+
+    j = 0;
+    i = -1;
+
+    while (j < npos) {
+        i = virGBitmapNextSetBit(bitmap, i);
+        if (i != bitsPos[j++])
+            goto error;
+    }
+
+    if (virGBitmapNextSetBit(bitmap, i) > 0)
+        goto error;
+
+    /* 3. full set */
+
+    i = -1;
+    virGBitmapSetAll(bitmap);
+
+    for (j = 0; j < size; j++) {
+        i = virGBitmapNextSetBit(bitmap, i);
+        if (i != j)
+            goto error;
+    }
+
+    if (virGBitmapNextSetBit(bitmap, i) > 0)
+        goto error;
+
+    virGBitmapFree(bitmap);
+    return 0;
+
+error:
+    virGBitmapFree(bitmap);
+    return -1;
+}
+
+/* test for virGBitmapNewData/ToData */
+static int test5(const void *v ATTRIBUTE_UNUSED)
+{
+    char data[] = {0x01, 0x02, 0x00, 0x00, 0x04};
+    unsigned char *data2 = NULL;
+    int len2;
+    int bits[] = {0, 9, 34};
+    virGBitmapPtr bitmap;
+    int i, j;
+    int ret = -1;
+
+    bitmap = virGBitmapNewData(data, sizeof(data));
+    if (!bitmap)
+        goto error;
+
+    i = 0;
+    j = -1;
+    while (i < sizeof(bits)/sizeof(int) &&
+           (j = virGBitmapNextSetBit(bitmap, j)) >= 0) {
+        if (j != bits[i++])
+            goto error;
+    }
+    if (virGBitmapNextSetBit(bitmap, j) > 0)
+        goto error;
+
+    ignore_value(virGBitmapSetBit(bitmap, 2));
+    ignore_value(virGBitmapSetBit(bitmap, 15));
+
+    if (virGBitmapToData(bitmap, &data2, &len2) < 0)
+        goto error;
+
+    if (len2 != sizeof(data) ||
+        data2[0] != 0x05 ||
+        data2[1] != 0x82 ||
+        data2[2] != 0x00 ||
+        data2[3] != 0x00 ||
+        data2[4] != 0x04)
+        goto error;
+
+    ret = 0;
+error:
+    virGBitmapFree(bitmap);
+    VIR_FREE(data2);
+    return ret;
+}
+
+/* test for virGBitmapFormat */
+static int test6(const void *v ATTRIBUTE_UNUSED)
+{
+    virGBitmapPtr bitmap = NULL;
+    char *str = NULL;
+    int size = 64;
+    int ret = -1;
+
+    bitmap = virGBitmapNew(size);
+    if (!bitmap)
+        goto error;
+
+    str = virGBitmapFormat(bitmap);
+    if (!str)
+        goto error;
+
+    if (!STREQ(str, ""))
+        goto error;
+
+    VIR_FREE(str);
+
+    ignore_value(virGBitmapSetBit(bitmap, 0));
+    str = virGBitmapFormat(bitmap);
+    if (!str)
+        goto error;
+
+    if (!STREQ(str, "0"))
+        goto error;
+
+    VIR_FREE(str);
+
+    ignore_value(virGBitmapSetBit(bitmap, 4));
+    ignore_value(virGBitmapSetBit(bitmap, 5));
+    str = virGBitmapFormat(bitmap);
+    if (!str)
+        goto error;
+
+    if (!STREQ(str, "0,4-5"))
+        goto error;
+
+    VIR_FREE(str);
+
+    ignore_value(virGBitmapSetBit(bitmap, 6));
+    str = virGBitmapFormat(bitmap);
+    if (!str)
+        goto error;
+
+    if (!STREQ(str, "0,4-6"))
+        goto error;
+
+    VIR_FREE(str);
+
+    ignore_value(virGBitmapSetBit(bitmap, 13));
+    ignore_value(virGBitmapSetBit(bitmap, 14));
+    ignore_value(virGBitmapSetBit(bitmap, 15));
+    ignore_value(virGBitmapSetBit(bitmap, 16));
+    str = virGBitmapFormat(bitmap);
+    if (!str)
+        goto error;
+
+    if (!STREQ(str, "0,4-6,13-16"))
+        goto error;
+
+    VIR_FREE(str);
+
+    ignore_value(virGBitmapSetBit(bitmap, 62));
+    ignore_value(virGBitmapSetBit(bitmap, 63));
+    str = virGBitmapFormat(bitmap);
+    if (!str)
+        goto error;
+
+    if (!STREQ(str, "0,4-6,13-16,62-63"))
+        goto error;
+
+
+    ret = 0;
+error:
+    virGBitmapFree(bitmap);
+    VIR_FREE(str);
+    return ret;
+}
+
+static int test7(const void *v ATTRIBUTE_UNUSED)
+{
+    virGBitmapPtr bitmap;
+    size_t i;
+    size_t maxBit[] = {
+        1, 8, 31, 32, 63, 64, 95, 96, 127, 128, 159, 160
+    };
+    size_t nmaxBit = 12;
+
+    for (i = 0; i < nmaxBit; i++) {
+        bitmap = virGBitmapNew(maxBit[i]);
+        if (!bitmap)
+            goto error;
+
+        if (virGBitmapIsAllSet(bitmap))
+            goto error;
+
+        ignore_value(virGBitmapSetBit(bitmap, 1));
+        if (virGBitmapIsAllSet(bitmap))
+            goto error;
+
+        virGBitmapSetAll(bitmap);
+        if (!virGBitmapIsAllSet(bitmap))
+            goto error;
+
+        virGBitmapFree(bitmap);
+    }
+
+    return 0;
+
+error:
+    virGBitmapFree(bitmap);
+    return -1;
+}
+
+/* test for virGBitmapNextClearBit */
+static int test8(const void *data ATTRIBUTE_UNUSED)
+{
+    const char *bitsString = "0, 2-4, 6-10, 12, 14-18, 20, 22, 25, 
28-33, 35, "
+        "41-42, 45-46";
+    int size = 48;
+    int noBitsPos[] = {
+        1,  5,  11, 13, 19, 21, 23, 24,
+        26, 27, 34, 36, 37, 38, 39, 40,
+        43, 44, 47
+    };
+    int npos = 19;
+    virGBitmapPtr bitmap = NULL;
+    int i, j;
+
+    /* 1. zero set */
+
+    bitmap = virGBitmapNew(size);
+    if (!bitmap)
+        goto error;
+
+    if (virGBitmapNextClearBit(bitmap, -1) != 0)
+        goto error;
+
+    virGBitmapFree(bitmap);
+    bitmap = NULL;
+
+    /* 2. partial set */
+
+    if (virGBitmapParse(bitsString, 0, &bitmap, size) < 0)
+        goto error;
+    if (!bitmap)
+        goto error;
+
+    j = 0;
+    i = -1;
+
+    while (j < npos) {
+        i = virGBitmapNextClearBit(bitmap, i);
+        if (i != noBitsPos[j++])
+            goto error;
+    }
+
+    if (virGBitmapNextSetBit(bitmap, i) > 0)
+        goto error;
+
+    /* 3. full set */
+
+    i = -1;
+    virGBitmapSetAll(bitmap);
+
+    for (j = 0; j < size; j++) {
+        i = virGBitmapNextSetBit(bitmap, i);
+        if (i != j)
+            goto error;
+    }
+
+    if (virGBitmapNextClearBit(bitmap, i) != i + 1)
+        goto error;
+
+    virGBitmapFree(bitmap);
+    return 0;
+
+error:
+    virGBitmapFree(bitmap);
+    return -1;
+}
+
+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;
+    if (virtTestRun("test3", 1, test3, NULL) < 0)
+        ret = -1;
+    if (virtTestRun("test4", 1, test4, NULL) < 0)
+        ret = -1;
+    if (virtTestRun("test5", 1, test5, NULL) < 0)
+        ret = -1;
+    if (virtTestRun("test6", 1, test6, NULL) < 0)
+        ret = -1;
+    if (virtTestRun("test7", 1, test7, NULL) < 0)
+        ret = -1;
+    if (virtTestRun("test8", 1, test8, NULL) < 0)
+        ret = -1;
+
+    return ret;
+}
+
+VIRT_TEST_MAIN(mymain)
Index: libvirt/src/libvirt_private.syms
===================================================================
--- libvirt.orig/src/libvirt_private.syms
+++ libvirt/src/libvirt_private.syms
@@ -9,6 +9,7 @@
  virBitmapClearAll;
  virBitmapClearBit;
  virBitmapCopy;
+virBitmapCopyResize;
  virBitmapCountBits;
  virBitmapEqual;
  virBitmapFormat;
@@ -1390,6 +1391,27 @@ virFileWrapperFdFree;
  virFileWrapperFdNew;


+# virbitmap.h
+virGBitmapClearAll;
+virGBitmapClearBit;
+virGBitmapCopy;
+virGBitmapCountBits;
+virGBitmapFormat;
+virGBitmapFree;
+virGBitmapGetBit;
+virGBitmapIsAllSet;
+virGBitmapNew;
+virGBitmapNewData;
+virGBitmapNextClearBit;
+virGBitmapNextSetBit;
+virGBitmapParse;
+virGBitmapSetAll;
+virGBitmapSetBit;
+virGBitmapSize;
+virGBitmapString;
+virGBitmapToData;
+
+
  # virinitctl.h
  virInitctlSetRunLevel;




More information about the libvir-list mailing list