Merge branch 'master' of ozlabs.org:ccan

diff --git a/Makefile-ccan b/Makefile-ccan
index c4a8f455ff98683ad4721165d3eafeeef3f91b39..d81031eab1add188d4ac71220a422edd1524e869 100644 (file)
--- 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 (symlink)
index 0000000..dc314ec
--- /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 (file)
index 0000000..2038058
--- /dev/null
+++ b/ccan/bitmap/_info
@@ -0,0 +1,31 @@
+#include <string.h>
+#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 <david@gibson.dropbear.id.au>
+ */
+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 (file)
index 0000000..f43449d
--- /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 <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
+
+#include <ccan/endian/endian.h>
+
+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 (file)
index 0000000..b67172a
--- /dev/null
+++ b/ccan/bitmap/test/run.c
@@ -0,0 +1,116 @@
+#include <ccan/bitmap/bitmap.h>
+#include <ccan/tap/tap.h>
+#include <ccan/array_size/array_size.h>
+#include <ccan/foreach/foreach.h>
+
+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();
+}