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

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(a)linux.vnet.ibm.com&gt; --- 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(a)linux.vnet.ibm.com&gt; + */ + +#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(a)linux.vnet.ibm.com&gt; + */ + +#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;