--- /dev/null
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * jbitset - variable-length bitset (based on libJudy)
+ *
+ * This provides a convenient wrapper for using Judy bitsets; using
+ * integers or pointers as an index, Judy arrays provide an efficient
+ * bit array or bit map of variable size.
+ *
+ * jbitset.h simply contains wrappers for a size_t-indexed bitset, and
+ * jbitset_type.h contain a wrapper macro for pointer bitsets.
+ *
+ * Example:
+ * // Simple analysis of one-byte mallocs.
+ * #include <stdlib.h>
+ * #include <stdio.h>
+ * #include <err.h>
+ * #include <ccan/jbitset/jbitset_type.h>
+ *
+ * // Define jbit_char_<op> and jbitset_char, for char * bitset.
+ * JBIT_DEFINE_TYPE(char, char);
+ *
+ * int main(int argc, char *argv[])
+ * {
+ * unsigned int i, runs, reuse;
+ * size_t mindist = -1;
+ * struct jbitset_char *set = jbit_char_new();
+ * char *p, *prev;
+ *
+ * runs = (argc == 1 ? 1000 : atoi(argv[1]));
+ * if (!runs)
+ * errx(1, "Invalid number of allocations '%s'", argv[1]);
+ *
+ * for (i = 0; i < runs; i++)
+ * if (!jbit_char_set(set, malloc(1)))
+ * errx(1, "same pointer allocated twice!");
+ *
+ * // Calculate minimum distance
+ * prev = jbit_char_first(set)+1;
+ * for (p = jbit_char_first(set); p; prev = p, p = jbit_char_next(set,p))
+ * if (p - prev < mindist)
+ * mindist = p - prev;
+ *
+ * // Free them all, see how many we reallocate.
+ * for (p = jbit_char_first(set); p; p = jbit_char_next(set, p))
+ * free(p);
+ * for (reuse = 0, i = 0; i < runs; i++)
+ * reuse += jbit_char_test(set, malloc(1));
+ *
+ * printf("Allocation density (bytes): %zu\n"
+ * "Minimum inter-pointer distance: %zu\n"
+ * "Reuse rate: %.0f%%\n",
+ * (jbit_char_last(set) - jbit_char_first(set)) / runs,
+ * mindist,
+ * 100.0 * reuse / runs);
+ * return 0;
+ * }
+ *
+ * License: LGPL (2 or any later version)
+ * Author: Rusty Russell <rusty@rustcorp.com.au>
+ */
+int main(int argc, char *argv[])
+{
+ if (argc != 2)
+ return 1;
+
+ if (strcmp(argv[1], "depends") == 0) {
+ printf("ccan/build_assert\n");
+ printf("ccan/compiler\n");
+ printf("Judy\n");
+ return 0;
+ }
+
+ if (strcmp(argv[1], "libs") == 0) {
+ printf("Judy\n");
+ return 0;
+ }
+
+ return 1;
+}
--- /dev/null
+#include <ccan/jbitset/jbitset.h>
+#include <ccan/build_assert/build_assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct jbitset *jbit_new(void)
+{
+ struct jbitset *set;
+
+ /* Judy uses Word_t, we use size_t. */
+ BUILD_ASSERT(sizeof(size_t) == sizeof(Word_t));
+
+ set = malloc(sizeof(*set));
+ if (set) {
+ set->judy = NULL;
+ memset(&set->err, 0, sizeof(set->err));
+ set->errstr = NULL;
+ }
+ return set;
+}
+
+const char *jbit_error_(struct jbitset *set)
+{
+ char *str;
+ free((char *)set->errstr);
+ set->errstr = str = malloc(100);
+ if (!set->errstr)
+ return "out of memory";
+
+ sprintf(str,
+ "JU_ERRNO_* == %d, ID == %d\n",
+ JU_ERRNO(&set->err), JU_ERRID(&set->err));
+ return str;
+}
+
+void jbit_free(const struct jbitset *set)
+{
+ free((char *)set->errstr);
+ Judy1FreeArray((PPvoid_t)&set->judy, PJE0);
+ free((void *)set);
+}
--- /dev/null
+#ifndef CCAN_JBITSET_H
+#define CCAN_JBITSET_H
+#include <Judy.h>
+#include <stdbool.h>
+#include <ccan/compiler/compiler.h>
+#include <assert.h>
+
+/**
+ * jbit_new - create a new, empty jbitset.
+ *
+ * See Also:
+ * JBIT_DEFINE_TYPE()
+ *
+ * Example:
+ * struct jbitset *set = jbit_new();
+ * if (!set)
+ * errx(1, "Failed to allocate jbitset");
+ */
+struct jbitset *jbit_new(void);
+
+/**
+ * jbit_free - destroy a jbitset.
+ * @set: the set returned from jbit_new.
+ *
+ * Example:
+ * jbit_free(set);
+ */
+void jbit_free(const struct jbitset *set);
+
+/* This is exposed in the header so we can inline. Treat it as private! */
+struct jbitset {
+ void *judy;
+ JError_t err;
+ const char *errstr;
+};
+const char *COLD_ATTRIBUTE jbit_error_(struct jbitset *set);
+
+/**
+ * jbit_error - test for an error in the a previous jbit_ operation.
+ * @set: the set to test.
+ *
+ * Under normal circumstances, return NULL to indicate no error has occurred.
+ * Otherwise, it will return a string containing the error. This string
+ * can only be freed by jbit_free() on the set.
+ *
+ * Other than out-of-memory, errors are caused by memory corruption or
+ * interface misuse.
+ *
+ * Example:
+ * struct jbitset *set = jbit_new();
+ * const char *errstr;
+ *
+ * if (!set)
+ * err(1, "allocating jbitset");
+ * errstr = jbit_error(set);
+ * if (errstr)
+ * errx(1, "Woah, error on newly created set?! %s", errstr);
+ */
+static inline const char *jbit_error(struct jbitset *set)
+{
+ if (JU_ERRNO(&set->err) <= JU_ERRNO_NFMAX)
+ return NULL;
+ return jbit_error_(set);
+}
+
+/**
+ * jbit_test - test a bit in the bitset.
+ * @set: bitset from jbit_new
+ * @index: the index to test
+ *
+ * Returns true if jbit_set() has been done on this index, false otherwise.
+ *
+ * Example:
+ * assert(!jbit_test(set, 0));
+ */
+static inline bool jbit_test(const struct jbitset *set, size_t index)
+{
+ return Judy1Test(set->judy, index, (JError_t *)&set->err);
+}
+
+/**
+ * jbit_set - set a bit in the bitset.
+ * @set: bitset from jbit_new
+ * @index: the index to set
+ *
+ * Returns false if it was already set (ie. nothing changed)
+ *
+ * Example:
+ * if (jbit_set(set, 0))
+ * err(1, "Bit 0 was already set?!");
+ */
+static inline bool jbit_set(struct jbitset *set, size_t index)
+{
+ return Judy1Set(&set->judy, index, &set->err);
+}
+
+/**
+ * jbit_clear - clear a bit in the bitset.
+ * @set: bitset from jbit_new
+ * @index: the index to set
+ *
+ * Returns the old bit value (ie. false if nothing changed).
+ *
+ * Example:
+ * if (jbit_clear(set, 0))
+ * err(1, "Bit 0 was already clear?!");
+ */
+static inline bool jbit_clear(struct jbitset *set, size_t index)
+{
+ return Judy1Unset(&set->judy, index, &set->err);
+}
+
+/**
+ * jbit_popcount - get population of (some part of) bitset.
+ * @set: bitset from jbit_new
+ * @start: first index to count
+ * @end_incl: last index to count (use -1 for end).
+ *
+ * Example:
+ * assert(jbit_popcount(set, 0, 1000) <= jbit_popcount(set, 0, 2000));
+ */
+static inline size_t jbit_popcount(const struct jbitset *set,
+ size_t start, size_t end_incl)
+{
+ return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err);
+}
+
+/**
+ * jbit_nth - return the index of the nth bit which is set.
+ * @set: bitset from jbit_new
+ * @n: which bit we are interested in (0-based)
+ * @invalid: what to return if n >= set population
+ *
+ * This normally returns the nth bit in the set, and often there is a
+ * convenient known-invalid value (ie. something which is never in the
+ * set). Otherwise, and a wrapper function like this can be used:
+ *
+ * static bool jbit_nth_index(struct jbitset *set, size_t n, size_t *idx)
+ * {
+ * // Zero might be valid, if it's first in set.
+ * if (n == 0 && jbit_test(set, 0)) {
+ * *idx = 0;
+ * return true;
+ * }
+ * *idx = jbit_nth(set, n, 0);
+ * return (*idx != 0);
+ * }
+ *
+ * Example:
+ * size_t i, val;
+ *
+ * // We know 0 isn't in set.
+ * assert(!jbit_test(set, 0));
+ * for (i = 0; (val = jbit_nth(set, i, 0)) != 0; i++) {
+ * assert(jbit_popcount(set, 0, val) == i);
+ * printf("Value %zu = %zu\n", i, val);
+ * }
+ */
+static inline size_t jbit_nth(const struct jbitset *set,
+ size_t n, size_t invalid)
+{
+ Word_t index;
+ if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err))
+ index = invalid;
+ return index;
+}
+
+/**
+ * jbit_first - return the first bit which is set.
+ * @set: bitset from jbit_new
+ * @invalid: return value if no bits are set at all.
+ *
+ * This is equivalent to jbit_nth(set, 0, invalid).
+ *
+ * Example:
+ * assert(!jbit_test(set, 0));
+ * printf("Set contents (increasing order):");
+ * for (i = jbit_first(set, 0); i; i = jbit_next(set, i, 0))
+ * printf(" %zu", i);
+ * printf("\n");
+ */
+static inline size_t jbit_first(const struct jbitset *set, size_t invalid)
+{
+ Word_t index = 0;
+ if (!Judy1First(set->judy, &index, (JError_t *)&set->err))
+ index = invalid;
+ else
+ assert(index != invalid);
+ return index;
+}
+
+/**
+ * jbit_next - return the next bit which is set.
+ * @set: bitset from jbit_new
+ * @prev: previous index
+ * @invalid: return value if no bits are set at all.
+ *
+ * This is usually used to find an adjacent bit which is set, after
+ * jbit_first.
+ */
+static inline size_t jbit_next(const struct jbitset *set, size_t prev,
+ size_t invalid)
+{
+ if (!Judy1Next(set->judy, (Word_t *)&prev, (JError_t *)&set->err))
+ prev = invalid;
+ else
+ assert(prev != invalid);
+ return prev;
+}
+
+/**
+ * jbit_last - return the last bit which is set.
+ * @set: bitset from jbit_new
+ * @invalid: return value if no bits are set at all.
+ *
+ * Example:
+ * assert(!jbit_test(set, 0));
+ * printf("Set contents (decreasing order):");
+ * for (i = jbit_last(set, 0); i; i = jbit_prev(set, i, 0))
+ * printf(" %zu", i);
+ * printf("\n");
+ */
+static inline size_t jbit_last(const struct jbitset *set, size_t invalid)
+{
+ Word_t index = -1;
+ if (!Judy1Last(set->judy, &index, (JError_t *)&set->err))
+ index = invalid;
+ else
+ assert(index != invalid);
+ return index;
+}
+
+/**
+ * jbit_prev - return the previous bit which is set.
+ * @set: bitset from jbit_new
+ * @prev: previous index
+ * @invalid: return value if no bits are set at all.
+ *
+ * This is usually used to find an adjacent bit which is set, after
+ * jbit_last.
+ */
+static inline size_t jbit_prev(const struct jbitset *set, size_t prev,
+ size_t invalid)
+{
+ if (!Judy1Prev(set->judy, (Word_t *)&prev, (JError_t *)&set->err))
+ prev = invalid;
+ else
+ assert(prev != invalid);
+ return prev;
+}
+
+/**
+ * jbit_first_clear - return the first bit which is unset.
+ * @set: bitset from jbit_new
+ * @invalid: return value if no bits are clear at all.
+ *
+ * This allows for iterating the inverse of the bitmap.
+ */
+static inline size_t jbit_first_clear(const struct jbitset *set,
+ size_t invalid)
+{
+ Word_t index = 0;
+ if (!Judy1FirstEmpty(set->judy, &index, (JError_t *)&set->err))
+ index = invalid;
+ else
+ assert(index != invalid);
+ return index;
+}
+
+static inline size_t jbit_next_clear(const struct jbitset *set, size_t prev,
+ size_t invalid)
+{
+ if (!Judy1NextEmpty(set->judy, (Word_t *)&prev, (JError_t *)&set->err))
+ prev = invalid;
+ else
+ assert(prev != invalid);
+ return prev;
+}
+
+static inline size_t jbit_last_clear(const struct jbitset *set, size_t invalid)
+{
+ Word_t index = -1;
+ if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err))
+ index = invalid;
+ else
+ assert(index != invalid);
+ return index;
+}
+
+static inline size_t jbit_prev_clear(const struct jbitset *set, size_t prev,
+ size_t invalid)
+{
+ if (!Judy1PrevEmpty(set->judy, (Word_t *)&prev, (JError_t *)&set->err))
+ prev = invalid;
+ else
+ assert(prev != invalid);
+ return prev;
+}
+#endif /* CCAN_JBITSET_H */
--- /dev/null
+#ifndef CCAN_JBITSET_TYPE_H
+#define CCAN_JBITSET_TYPE_H
+#include <ccan/jbitset/jbitset.h>
+
+/**
+ * JBIT_DEFINE_TYPE - create a set of jbit ops for a given pointer type
+ * @type: a type whose pointers will go into the bitset.
+ * @name: a name for all the functions to define (of form jbit_<name>_*)
+ *
+ * This macro defines a set of inline functions for typesafe and convenient
+ * usage of a Judy bitset for pointers. It is assumed that a NULL pointer
+ * is never set in the bitset.
+ *
+ * Example:
+ * JBIT_DEFINE_TYPE(char, char);
+ * JBIT_DEFINE_TYPE(struct foo, foo);
+ *
+ * static struct jbitset_char *jc;
+ * struct jbitset_foo *jf;
+ *
+ * static void add_to_bitsets(const char *p, const struct foo *f)
+ * {
+ * // Note, this adds the pointer, not the string!
+ * jbit_char_set(jc, p);
+ * jbit_foo_set(jf, f);
+ * }
+ */
+#define JBIT_DEFINE_TYPE(type, name) \
+struct jbitset_##name; \
+static inline struct jbitset_##name *jbit_##name##_new(void) \
+{ \
+ return (struct jbitset_##name *)jbit_new(); \
+} \
+static inline void jbit_##name##_free(const struct jbitset_##name *set) \
+{ \
+ jbit_free((const struct jbitset *)set); \
+} \
+static inline const char *jbit_##name##_error(struct jbitset_##name *set) \
+{ \
+ return jbit_error((struct jbitset *)set); \
+} \
+static inline bool jbit_##name##_test(const struct jbitset_##name *set, \
+ const type *index) \
+{ \
+ return jbit_test((const struct jbitset *)set, (size_t)index); \
+} \
+static inline bool jbit_##name##_set(struct jbitset_##name *set, \
+ const type *index) \
+{ \
+ return jbit_set((struct jbitset *)set, (size_t)index); \
+} \
+static inline bool jbit_##name##_clear(struct jbitset_##name *set, \
+ const type *index) \
+{ \
+ return jbit_clear((struct jbitset *)set, (size_t)index); \
+} \
+static inline size_t jbit_##name##_count(struct jbitset_##name *set) \
+{ \
+ return jbit_popcount((const struct jbitset *)set, 0, -1); \
+} \
+static inline type *jbit_##name##_nth(const struct jbitset_##name *set, \
+ size_t n) \
+{ \
+ return (type *)jbit_nth((const struct jbitset *)set, n, 0); \
+} \
+static inline type *jbit_##name##_first(const struct jbitset_##name *set) \
+{ \
+ return (type *)jbit_first((const struct jbitset *)set, 0); \
+} \
+static inline type *jbit_##name##_next(struct jbitset_##name *set, \
+ const type *prev) \
+{ \
+ return (type *)jbit_next((const struct jbitset *)set, (size_t)prev, 0); \
+} \
+static inline type *jbit_##name##_last(struct jbitset_##name *set) \
+{ \
+ return (type *)jbit_last((const struct jbitset *)set, 0); \
+} \
+static inline type *jbit_##name##_prev(struct jbitset_##name *set, \
+ const type *prev) \
+{ \
+ return (type *)jbit_prev((const struct jbitset *)set, (size_t)prev, 0); \
+}
+#endif /* CCAN_JBITSET_TYPE_H */
--- /dev/null
+#include <ccan/tap/tap.h>
+#include <ccan/jbitset/jbitset_type.h>
+#include <ccan/jbitset/jbitset.c>
+
+struct foo;
+
+JBIT_DEFINE_TYPE(struct foo, foo);
+
+static int cmp_ptr(const void *a, const void *b)
+{
+ return *(char **)a - *(char **)b;
+}
+
+#define NUM 100
+
+int main(int argc, char *argv[])
+{
+ struct jbitset_foo *set;
+ struct foo *foo[NUM];
+ unsigned int i;
+
+ plan_tests(20);
+ for (i = 0; i < NUM; i++)
+ foo[i] = malloc(20);
+
+ set = jbit_foo_new();
+ ok1(jbit_foo_error(set) == NULL);
+
+ ok1(jbit_foo_set(set, foo[0]) == true);
+ ok1(jbit_foo_set(set, foo[0]) == false);
+ ok1(jbit_foo_clear(set, foo[0]) == true);
+ ok1(jbit_foo_clear(set, foo[0]) == false);
+ ok1(jbit_foo_count(set) == 0);
+ ok1(jbit_foo_nth(set, 0) == (struct foo *)NULL);
+ ok1(jbit_foo_first(set) == (struct foo *)NULL);
+ ok1(jbit_foo_last(set) == (struct foo *)NULL);
+
+ for (i = 0; i < NUM; i++)
+ jbit_foo_set(set, foo[i]);
+
+ qsort(foo, NUM, sizeof(foo[0]), cmp_ptr);
+
+ ok1(jbit_foo_count(set) == NUM);
+ ok1(jbit_foo_nth(set, 0) == foo[0]);
+ ok1(jbit_foo_nth(set, NUM-1) == foo[NUM-1]);
+ ok1(jbit_foo_nth(set, NUM) == (struct foo *)NULL);
+ ok1(jbit_foo_first(set) == foo[0]);
+ ok1(jbit_foo_last(set) == foo[NUM-1]);
+ ok1(jbit_foo_next(set, foo[0]) == foo[1]);
+ ok1(jbit_foo_next(set, foo[NUM-1]) == (struct foo *)NULL);
+ ok1(jbit_foo_prev(set, foo[1]) == foo[0]);
+ ok1(jbit_foo_prev(set, foo[0]) == (struct foo *)NULL);
+ ok1(jbit_foo_error(set) == NULL);
+ jbit_foo_free(set);
+
+ return exit_status();
+}
--- /dev/null
+#include <ccan/tap/tap.h>
+#include <ccan/jbitset/jbitset.c>
+
+int main(int argc, char *argv[])
+{
+ struct jbitset *set;
+ size_t i;
+ const char *err;
+
+ plan_tests(36);
+
+ set = jbit_new();
+ ok1(jbit_error(set) == NULL);
+
+ ok1(jbit_set(set, 0) == true);
+ ok1(jbit_set(set, 0) == false);
+ ok1(jbit_clear(set, 0) == true);
+ ok1(jbit_clear(set, 0) == false);
+ ok1(jbit_popcount(set, 0, -1) == 0);
+ ok1(jbit_nth(set, 0, 0) == 0);
+ ok1(jbit_nth(set, 0, -1) == (size_t)-1);
+ ok1(jbit_first(set, 0) == 0);
+ ok1(jbit_first(set, -1) == (size_t)-1);
+ ok1(jbit_last(set, 0) == 0);
+ ok1(jbit_last(set, -1) == (size_t)-1);
+ ok1(jbit_first_clear(set, -1) == 0);
+ ok1(jbit_first_clear(set, -2) == 0);
+ ok1(jbit_last_clear(set, 0) == (size_t)-1);
+ ok1(jbit_prev_clear(set, 1, -1) == 0);
+ ok1(jbit_next_clear(set, 0, -1) == 1);
+ ok1(jbit_next_clear(set, -1, -1) == -1);
+
+ /* Set a million bits, 16 bits apart. */
+ for (i = 0; i < 1000000; i++)
+ jbit_set(set, i << 4);
+
+ /* This only take 1.7MB on my 32-bit system. */
+ diag("%u bytes memory used\n", (unsigned)Judy1MemUsed(set->judy));
+
+ ok1(jbit_popcount(set, 0, -1) == 1000000);
+ ok1(jbit_nth(set, 0, -1) == 0);
+ ok1(jbit_nth(set, 999999, -1) == 999999 << 4);
+ ok1(jbit_nth(set, 1000000, -1) == (size_t)-1);
+ ok1(jbit_first(set, -1) == 0);
+ ok1(jbit_last(set, -1) == 999999 << 4);
+ ok1(jbit_first_clear(set, -1) == 1);
+ ok1(jbit_last_clear(set, 0) == (size_t)-1);
+ ok1(jbit_prev_clear(set, 1, -1) == (size_t)-1);
+ ok1(jbit_next(set, 0, -1) == 1 << 4);
+ ok1(jbit_next(set, 999999 << 4, -1) == (size_t)-1);
+ ok1(jbit_prev(set, 1, -1) == 0);
+ ok1(jbit_prev(set, 0, -1) == (size_t)-1);
+ ok1(jbit_error(set) == NULL);
+
+ /* Test error handling */
+ JU_ERRNO(&set->err) = 100;
+ JU_ERRID(&set->err) = 991;
+ err = jbit_error(set);
+ ok1(err);
+ ok1(strstr(err, "100"));
+ ok1(strstr(err, "991"));
+ ok1(err == set->errstr);
+ jbit_free(set);
+
+ return exit_status();
+}
projects / ccan / commitdiff