From: Rusty Russell Date: Fri, 13 Sep 2013 00:08:40 +0000 (+0930) Subject: Merge branch 'master' of ozlabs.org:ccan X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=d49754643794fe396b868ef98706898088ab1e84;hp=03d339d5ac08ced9d787aa556226c3f7fb849dc4 Merge branch 'master' of ozlabs.org:ccan --- diff --git a/Makefile-ccan b/Makefile-ccan index c4a8f455..d81031ea 100644 --- a/Makefile-ccan +++ b/Makefile-ccan @@ -10,6 +10,7 @@ CFLAGS = $(CCAN_CFLAGS) -I. $(DEPGEN) MODS_NO_SRC := alignof \ array_size \ asearch \ + bitmap \ build_assert \ bytestring \ cast \ 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..2038058f --- /dev/null +++ b/ccan/bitmap/_info @@ -0,0 +1,31 @@ +#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) { + printf("ccan/endian\n"); + return 0; + } + + if (strcmp(argv[1], "testdepends") == 0) { + printf("ccan/array_size\n"); + printf("ccan/foreach\n"); + return 0; + } + + return 1; +} diff --git a/ccan/bitmap/bitmap.h b/ccan/bitmap/bitmap.h new file mode 100644 index 00000000..f43449d7 --- /dev/null +++ b/ccan/bitmap/bitmap.h @@ -0,0 +1,188 @@ +/* Licensed under LGPLv2+ - see LICENSE file for details */ +#ifndef CCAN_BITMAP_H_ +#define CCAN_BITMAP_H_ + +#include +#include +#include +#include + +#include + +typedef unsigned long bitmap_word; + +#define BITMAP_WORD_BITS (sizeof(bitmap_word) * CHAR_BIT) +#define BITMAP_NWORDS(_n) \ + (((_n) + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS) + +/* + * We wrap each word in a structure for type checking. + */ +typedef struct { + bitmap_word w; +} bitmap; + +#define BITMAP_DECLARE(_name, _nbits) \ + bitmap (_name)[BITMAP_NWORDS(_nbits)] + +static inline size_t bitmap_sizeof(int nbits) +{ + return BITMAP_NWORDS(nbits) * sizeof(bitmap_word); +} + +static inline bitmap *bitmap_alloc(int nbits) +{ + return malloc(bitmap_sizeof(nbits)); +} + +static inline bitmap_word bitmap_bswap(bitmap_word w) +{ + if (BITMAP_WORD_BITS == 32) + return cpu_to_be32(w); + else if (BITMAP_WORD_BITS == 64) + return cpu_to_be64(w); +} + +#define BITMAP_WORD(_bm, _n) ((_bm)[(_n) / BITMAP_WORD_BITS].w) +#define BITMAP_WORDBIT(_n) \ + (bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1))) + +#define BITMAP_HEADWORDS(_nbits) \ + ((_nbits) / BITMAP_WORD_BITS) +#define BITMAP_HEADBYTES(_nbits) \ + (BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word)) + +#define BITMAP_TAILWORD(_bm, _nbits) \ + ((_bm)[BITMAP_HEADWORDS(_nbits)].w) +#define BITMAP_HASTAIL(_nbits) (((_nbits) % BITMAP_WORD_BITS) != 0) +#define BITMAP_TAILBITS(_nbits) \ + (bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS)))) +#define BITMAP_TAIL(_bm, _nbits) \ + (BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits)) + +static inline void bitmap_set_bit(bitmap *bitmap, int n) +{ + BITMAP_WORD(bitmap, n) |= BITMAP_WORDBIT(n); +} + +static inline void bitmap_clear_bit(bitmap *bitmap, int n) +{ + BITMAP_WORD(bitmap, n) &= ~BITMAP_WORDBIT(n); +} + +static inline void bitmap_change_bit(bitmap *bitmap, int n) +{ + BITMAP_WORD(bitmap, n) ^= BITMAP_WORDBIT(n); +} + +static inline bool bitmap_test_bit(bitmap *bitmap, int n) +{ + return !!(BITMAP_WORD(bitmap, n) & BITMAP_WORDBIT(n)); +} + + +static inline void bitmap_zero(bitmap *bitmap, int nbits) +{ + memset(bitmap, 0, bitmap_sizeof(nbits)); +} + +static inline void bitmap_fill(bitmap *bitmap, int nbits) +{ + memset(bitmap, 0xff, bitmap_sizeof(nbits)); +} + +static inline void bitmap_copy(bitmap *dst, bitmap *src, int nbits) +{ + memcpy(dst, src, bitmap_sizeof(nbits)); +} + +#define BITMAP_DEF_BINOP(_name, _op) \ + static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \ + int nbits) \ + { \ + int i = 0; \ + for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \ + dst[i].w = src1[i].w _op src2[i].w; \ + } \ + } + +BITMAP_DEF_BINOP(and, &) +BITMAP_DEF_BINOP(or, |) +BITMAP_DEF_BINOP(xor, ^) +BITMAP_DEF_BINOP(andnot, & ~) + +#undef BITMAP_DEF_BINOP + +static inline void bitmap_complement(bitmap *dst, bitmap *src, int nbits) +{ + int i; + + for (i = 0; i < BITMAP_NWORDS(nbits); i++) + dst[i].w = ~src[i].w; +} + +static inline bool bitmap_equal(bitmap *src1, bitmap *src2, int nbits) +{ + return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0) + && (!BITMAP_HASTAIL(nbits) + || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits))); +} + +static inline bool bitmap_intersects(bitmap *src1, bitmap *src2, int nbits) +{ + int i; + + for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) { + if (src1[i].w & src2[i].w) + return true; + } + if (BITMAP_HASTAIL(nbits) && + (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits))) + return true; + return false; +} + +static inline bool bitmap_subset(bitmap *src1, bitmap *src2, int nbits) +{ + int i; + + for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) { + if (src1[i].w & ~src2[i].w) + return false; + } + if (BITMAP_HASTAIL(nbits) && + (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits))) + return false; + return true; +} + +static inline bool bitmap_full(bitmap *bitmap, int nbits) +{ + int i; + + for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) { + if (bitmap[i].w != -1UL) + return false; + } + if (BITMAP_HASTAIL(nbits) && + (BITMAP_TAIL(bitmap, nbits) != BITMAP_TAILBITS(nbits))) + return false; + + return true; +} + +static inline bool bitmap_empty(bitmap *bitmap, int nbits) +{ + int i; + + for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) { + if (bitmap[i].w != 0) + return false; + } + if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bitmap, nbits) != 0)) + return false; + + return true; +} + +#endif /* CCAN_BITMAP_H_ */ diff --git a/ccan/bitmap/test/run.c b/ccan/bitmap/test/run.c new file mode 100644 index 00000000..b67172a5 --- /dev/null +++ b/ccan/bitmap/test/run.c @@ -0,0 +1,116 @@ +#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 9 + +static void test_sizes(int nbits, bool dynalloc) +{ + BITMAP_DECLARE(sbitmap, nbits); + uint32_t marker; + bitmap *bitmap; + int i, j; + bool wrong; + + if (dynalloc) { + bitmap = bitmap_alloc(nbits); + ok1(bitmap != NULL); + } else { + bitmap = sbitmap; + marker = 0xdeadbeef; + } + + 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); + + if (dynalloc) { + free(bitmap); + } else { + ok1(marker == 0xdeadbeef); + } +} + +int main(void) +{ + int i; + bool dynalloc; + + /* This is how many tests you plan to run */ + plan_tests(NSIZES * NTESTS * 2); + + for (i = 0; i < NSIZES; i++) { + foreach_int(dynalloc, false, true) { + diag("Testing %d-bit bitmap (%s allocation)", + bitmap_sizes[i], dynalloc ? "dynamic" : "static"); + test_sizes(bitmap_sizes[i], dynalloc); + } + } + + /* This exits depending on whether all tests passed */ + return exit_status(); +}