From b9c9f5d934cda9717e373824e81670ec075fe001 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Fri, 3 Oct 2014 00:14:59 +1000 Subject: [PATCH] bitmap: Extend allocation functions The bitmap module already has a simple allocation helper, which returns an uninitialized, dynamically allocated bitmap of a given size. This extends this with bitmap_alloc[01]() which allocate bitmaps and initialize them to all zero or all one. It also adds bitmap_realloc[01]() which reallocate an existing bitmap, preserving existing bits, and setting any new bits to all zero or all one. Signed-off-by: David Gibson Signed-off-by: Rusty Russell --- ccan/bitmap/bitmap.h | 53 ++++++++++++++++-- ccan/bitmap/test/run-alloc.c | 101 +++++++++++++++++++++++++++++++++++ 2 files changed, 149 insertions(+), 5 deletions(-) create mode 100644 ccan/bitmap/test/run-alloc.c diff --git a/ccan/bitmap/bitmap.h b/ccan/bitmap/bitmap.h index 34faf500..6c8d7e4d 100644 --- a/ccan/bitmap/bitmap.h +++ b/ccan/bitmap/bitmap.h @@ -30,11 +30,6 @@ static inline size_t bitmap_sizeof(unsigned long nbits) return BITMAP_NWORDS(nbits) * sizeof(bitmap_word); } -static inline bitmap *bitmap_alloc(unsigned long nbits) -{ - return malloc(bitmap_sizeof(nbits)); -} - static inline bitmap_word bitmap_bswap(bitmap_word w) { if (BITMAP_WORD_BITS == 32) @@ -192,4 +187,52 @@ static inline bool bitmap_empty(const bitmap *bitmap, unsigned long nbits) return true; } +/* + * Allocation functions + */ +static inline bitmap *bitmap_alloc(unsigned long nbits) +{ + return malloc(bitmap_sizeof(nbits)); +} + +static inline bitmap *bitmap_alloc0(unsigned long nbits) +{ + bitmap *bitmap; + + bitmap = bitmap_alloc(nbits); + bitmap_zero(bitmap, nbits); + return bitmap; +} + +static inline bitmap *bitmap_alloc1(unsigned long nbits) +{ + bitmap *bitmap; + + bitmap = bitmap_alloc(nbits); + bitmap_fill(bitmap, nbits); + return bitmap; +} + +static inline bitmap *bitmap_realloc0(bitmap *bitmap, + unsigned long obits, unsigned long nbits) +{ + bitmap = realloc(bitmap, bitmap_sizeof(nbits)); + + if (nbits > obits) + bitmap_zero_range(bitmap, obits, nbits); + + return bitmap; +} + +static inline bitmap *bitmap_realloc1(bitmap *bitmap, + unsigned long obits, unsigned long nbits) +{ + bitmap = realloc(bitmap, bitmap_sizeof(nbits)); + + if (nbits > obits) + bitmap_fill_range(bitmap, obits, nbits); + + return bitmap; +} + #endif /* CCAN_BITMAP_H_ */ diff --git a/ccan/bitmap/test/run-alloc.c b/ccan/bitmap/test/run-alloc.c new file mode 100644 index 00000000..fcdaf4da --- /dev/null +++ b/ccan/bitmap/test/run-alloc.c @@ -0,0 +1,101 @@ +#include +#include +#include +#include + +#include + +int bitmap_sizes[] = { + 1, 2, 3, 4, 5, 6, 7, 8, + 16, 17, 24, 32, 33, + 64, 65, 127, 128, 129, + 1023, 1024, 1025, +}; +#define NSIZES ARRAY_SIZE(bitmap_sizes) +#define NTESTS_BASE 4 +#define NTESTS_REALLOC 10 + +static void test_basic_alloc(int nbits) +{ + bitmap *bitmap; + + bitmap = bitmap_alloc0(nbits); + ok1(bitmap != NULL); + ok1(bitmap_empty(bitmap, nbits)); + + free(bitmap); + + bitmap = bitmap_alloc1(nbits); + ok1(bitmap != NULL); + ok1(bitmap_full(bitmap, nbits)); + + free(bitmap); +} + +static void test_realloc(int obits, int nbits) +{ + bitmap *bitmap; + int i; + bool wrong; + + bitmap = bitmap_alloc0(obits); + ok1(bitmap != NULL); + ok1(bitmap_empty(bitmap, obits)); + + bitmap = bitmap_realloc1(bitmap, obits, nbits); + ok1(bitmap != NULL); + if (obits < nbits) + ok1(bitmap_empty(bitmap, obits)); + else + ok1(bitmap_empty(bitmap, nbits)); + + wrong = false; + for (i = obits; i < nbits; i++) + wrong = wrong || !bitmap_test_bit(bitmap, i); + ok1(!wrong); + + free(bitmap); + + bitmap = bitmap_alloc1(obits); + ok1(bitmap != NULL); + ok1(bitmap_full(bitmap, obits)); + + bitmap = bitmap_realloc0(bitmap, obits, nbits); + ok1(bitmap != NULL); + if (obits < nbits) + ok1(bitmap_full(bitmap, obits)); + else + ok1(bitmap_full(bitmap, nbits)); + + wrong = false; + for (i = obits; i < nbits; i++) + wrong = wrong || bitmap_test_bit(bitmap, i); + ok1(!wrong); + + free(bitmap); +} + +int main(void) +{ + int i, j; + + /* This is how many tests you plan to run */ + plan_tests(NSIZES * NTESTS_BASE + NSIZES * NSIZES * NTESTS_REALLOC); + + for (i = 0; i < NSIZES; i++) { + diag("Testing %d-bit bitmap", bitmap_sizes[i]); + test_basic_alloc(bitmap_sizes[i]); + } + + for (i = 0; i < NSIZES; i++) { + for (j = 0; j < NSIZES; j++) { + diag("Testing %d-bit => %d-bit bitmap", + bitmap_sizes[i], bitmap_sizes[j]); + + test_realloc(bitmap_sizes[i], bitmap_sizes[j]); + } + } + + /* This exits depending on whether all tests passed */ + return exit_status(); +} -- 2.39.2