From ba88f53bc56206c7eccac7eac20447e19c34c024 Mon Sep 17 00:00:00 2001 From: David Gibson Date: Thu, 22 Aug 2013 22:39:02 +1000 Subject: [PATCH] bitmap: Add first cut at a bitmap module This adds a module for manipulating bitmaps, based on the API from the Linux kernel's bitmap.h. So far it's missing the trickier bits, but is a little more flexible, allowing bitmaps that don't have to be contained in an integer number of unsigned longs. Signed-off-by: David Gibson --- ccan/bitmap/LICENSE | 1 + ccan/bitmap/_info | 29 ++++++ ccan/bitmap/bitmap.h | 210 +++++++++++++++++++++++++++++++++++++++++ ccan/bitmap/test/run.c | 99 +++++++++++++++++++ 4 files changed, 339 insertions(+) create mode 120000 ccan/bitmap/LICENSE create mode 100644 ccan/bitmap/_info create mode 100644 ccan/bitmap/bitmap.h create mode 100644 ccan/bitmap/test/run.c diff --git a/ccan/bitmap/LICENSE b/ccan/bitmap/LICENSE new file mode 120000 index 00000000..dc314eca --- /dev/null +++ b/ccan/bitmap/LICENSE @@ -0,0 +1 @@ +../../licenses/LGPL-2.1 \ No newline at end of file diff --git a/ccan/bitmap/_info b/ccan/bitmap/_info new file mode 100644 index 00000000..058f8bb2 --- /dev/null +++ b/ccan/bitmap/_info @@ -0,0 +1,29 @@ +#include +#include "config.h" + +/** + * bitmap - bitmap handling + * + * This code handles manipulation of bitmaps, arbitrary length arrays + * of bits. + * + * License: LGPL (v2.1 or any later version) + * Author: David Gibson + */ +int main(int argc, char *argv[]) +{ + /* Expect exactly one argument */ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + return 0; + } + + if (strcmp(argv[1], "testdepends") == 0) { + printf("ccan/array_size\n"); + return 0; + } + + return 1; +} diff --git a/ccan/bitmap/bitmap.h b/ccan/bitmap/bitmap.h new file mode 100644 index 00000000..4c6c9507 --- /dev/null +++ b/ccan/bitmap/bitmap.h @@ -0,0 +1,210 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#ifndef CCAN_BITMAP_H_ +#define CCAN_BITMAP_H_ + +#include +#include +#include + +#define BITS_PER_LONG (sizeof(unsigned long) * 8) + +#define BYTE(_bm, _n) (((unsigned char *)(_bm))[(_n) / 8]) +#define LONG(_bm, _n) (((unsigned long *)(_bm))[(_n) / BITS_PER_LONG]) +#define BIT(_n) (0x80 >> ((_n) % 8)) + +#define BYTES(_nbits) ((_nbits) / 8) +#define BITS(_nbits) ((~(0xff >> ((_nbits) % 8))) & 0xff) + +static inline void bitmap_set_bit(void *bitmap, int n) +{ + BYTE(bitmap, n) |= BIT(n); +} + +static inline void bitmap_clear_bit(void *bitmap, int n) +{ + BYTE(bitmap, n) &= ~BIT(n); +} + +static inline void bitmap_change_bit(void *bitmap, int n) +{ + BYTE(bitmap, n) ^= BIT(n); +} + +static inline bool bitmap_test_bit(void *bitmap, int n) +{ + return !!(BYTE(bitmap, n) & BIT(n)); +} + + +static inline void bitmap_zero(void *bitmap, int nbits) +{ + memset(bitmap, 0, BYTES(nbits)); + if (BITS(nbits)) + BYTE(bitmap, nbits) &= ~BITS(nbits); +} + +static inline void bitmap_fill(void *bitmap, int nbits) +{ + memset(bitmap, 0xff, BYTES(nbits)); + if (BITS(nbits)) + BYTE(bitmap, nbits) |= BITS(nbits); +} + +static inline void bitmap_copy(void *dst, void *src, int nbits) +{ + memcpy(dst, src, BYTES(nbits)); + if (BITS(nbits)) { + BYTE(dst, nbits) &= ~BITS(nbits); + BYTE(dst, nbits) |= BYTE(src, nbits) & BITS(nbits); + } +} + +#define DEF_BINOP(_name, _op) \ + static inline void bitmap_##_name(void *dst, void *src1, void *src2, \ + int nbits) \ + { \ + int n = 0; \ + while ((nbits - n) >= BITS_PER_LONG) { \ + LONG(dst, n) = LONG(src1, n) _op LONG(src2, n); \ + n += BITS_PER_LONG; \ + } \ + while ((nbits - n) >= 8) { \ + BYTE(dst, n) = BYTE(src1, n) _op BYTE(src2, n); \ + n += 8; \ + } \ + if (BITS(nbits)) { \ + BYTE(dst, nbits) &= ~BITS(nbits); \ + BYTE(dst, nbits) |= (BYTE(src1, nbits) _op BYTE(src2, nbits)) \ + & BITS(nbits); \ + } \ + } + +DEF_BINOP(and, &) +DEF_BINOP(or, |) +DEF_BINOP(xor, ^) +DEF_BINOP(andnot, & ~) + +#undef DEF_BINOP + +static inline void bitmap_complement(void *dst, void *src, int nbits) +{ + int n = 0; + + while ((nbits - n) >= BITS_PER_LONG) { + LONG(dst, n) = ~LONG(src, n); + n += BITS_PER_LONG; + } + while ((nbits - n) >= 8) { + BYTE(dst, n) = ~BYTE(src, n); + n += 8; + } + if (BITS(nbits)) { + BYTE(dst, nbits) &= ~BITS(nbits); + BYTE(dst, nbits) |= ~BYTE(src, nbits) & BITS(nbits); + } +} + +static inline bool bitmap_equal(void *src1, void *src2, int nbits) +{ + if (memcmp(src1, src2, BYTES(nbits)) != 0) + return false; + if ((BYTE(src1, nbits) & BITS(nbits)) + != (BYTE(src2, nbits) & BITS(nbits))) + return false; + return true; +} + +static inline bool bitmap_intersects(void *src1, void *src2, int nbits) +{ + int n = 0; + + while ((nbits - n) >= BITS_PER_LONG) { + if (LONG(src1, n) & LONG(src2, n)) + return true; + n += BITS_PER_LONG; + } + while ((nbits - n) >= 8) { + if (BYTE(src1, n) & BYTE(src2, n)) + return true; + n += 8; + } + if (BITS(nbits) & BYTE(src1, nbits) & BYTE(src2, nbits)) { + return true; + } + return false; +} + +static inline bool bitmap_subset(void *src1, void *src2, int nbits) +{ + int n = 0; + + while ((nbits - n) >= BITS_PER_LONG) { + if (LONG(src1, n) & ~LONG(src2, n)) + return false; + n += BITS_PER_LONG; + } + while ((nbits - n) >= 8) { + if (BYTE(src1, n) & ~BYTE(src2, n)) + return false; + n += 8; + } + if (BITS(nbits) & (BYTE(src1, nbits) & ~BYTE(src2, nbits))) { + return false; + } + return true; +} + +static inline bool bitmap_full(void *bitmap, int nbits) +{ + int n = 0; + + while ((nbits - n) >= BITS_PER_LONG) { + if (LONG(bitmap, n) != -1UL) + return false; + n += BITS_PER_LONG; + } + while ((nbits - n) >= 8) { + if (BYTE(bitmap, n) != 0xff) + return false; + n += 8; + } + if (BITS(nbits) + && ((BITS(nbits) & BYTE(bitmap, nbits)) != BITS(nbits))) { + return false; + } + return true; +} + +static inline bool bitmap_empty(void *bitmap, int nbits) +{ + int n = 0; + + while ((nbits - n) >= BITS_PER_LONG) { + if (LONG(bitmap, n)) + return false; + n += BITS_PER_LONG; + } + while ((nbits - n) >= 8) { + if (BYTE(bitmap, n)) + return false; + n += 8; + } + if (BITS(nbits) && ((BITS(nbits) & BYTE(bitmap, nbits)))) { + return false; + } + return true; +} + + +static inline void *bitmap_alloc(int nbits) +{ + return malloc((nbits + 7) / 8); +} + +#undef BYTE +#undef LONG +#undef BIT +#undef BYTES +#undef BITS + +#endif /* CCAN_BITMAP_H_ */ diff --git a/ccan/bitmap/test/run.c b/ccan/bitmap/test/run.c new file mode 100644 index 00000000..76a8161c --- /dev/null +++ b/ccan/bitmap/test/run.c @@ -0,0 +1,99 @@ +#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 9 + +static void test_sizes(int nbits) +{ + void *bitmap = bitmap_alloc(nbits); + int i, j; + bool wrong; + + ok1(bitmap != NULL); + + bitmap_zero(bitmap, nbits); + wrong = false; + for (i = 0; i < nbits; i++) { + wrong = wrong || bitmap_test_bit(bitmap, i); + } + ok1(!wrong); + + bitmap_fill(bitmap, nbits); + wrong = false; + for (i = 0; i < nbits; i++) { + wrong = wrong || !bitmap_test_bit(bitmap, i); + } + ok1(!wrong); + + wrong = false; + for (i = 0; i < nbits; i++) { + bitmap_zero(bitmap, nbits); + bitmap_set_bit(bitmap, i); + for (j = 0; j < nbits; j++) { + bool val = (i == j); + + wrong = wrong || (bitmap_test_bit(bitmap, j) != val); + } + } + ok1(!wrong); + + wrong = false; + for (i = 0; i < nbits; i++) { + bitmap_fill(bitmap, nbits); + bitmap_clear_bit(bitmap, i); + for (j = 0; j < nbits; j++) { + bool val = !(i == j); + + wrong = wrong || (bitmap_test_bit(bitmap, j) != val); + } + } + ok1(!wrong); + + bitmap_zero(bitmap, nbits); + ok1(bitmap_empty(bitmap, nbits)); + + wrong = false; + for (i = 0; i < nbits; i++) { + bitmap_zero(bitmap, nbits); + bitmap_set_bit(bitmap, i); + wrong = wrong || bitmap_empty(bitmap, nbits); + } + ok1(!wrong); + + bitmap_fill(bitmap, nbits); + ok1(bitmap_full(bitmap, nbits)); + + wrong = false; + for (i = 0; i < nbits; i++) { + bitmap_fill(bitmap, nbits); + bitmap_clear_bit(bitmap, i); + wrong = wrong || bitmap_full(bitmap, nbits); + } + ok1(!wrong); + + free(bitmap); +} + +int main(void) +{ + int i; + + /* This is how many tests you plan to run */ + plan_tests(NSIZES * NTESTS); + + for (i = 0; i < NSIZES; i++) { + diag("Testing %d-bit bitmap", bitmap_sizes[i]); + test_sizes(bitmap_sizes[i]); + } + + /* This exits depending on whether all tests passed */ + return exit_status(); +} -- 2.39.2