From: Rusty Russell Date: Sat, 30 Oct 2010 10:14:42 +0000 (+1030) Subject: jbitset: new module. X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=5e880e4ce45a3cececd0996b384482780a92070d jbitset: new module. --- diff --git a/ccan/jbitset/_info b/ccan/jbitset/_info new file mode 100644 index 00000000..4fa4dd98 --- /dev/null +++ b/ccan/jbitset/_info @@ -0,0 +1,82 @@ +#include +#include +#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 + * #include + * #include + * #include + * + * // Define jbit_char_ 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 + */ +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; +} diff --git a/ccan/jbitset/jbitset.c b/ccan/jbitset/jbitset.c new file mode 100644 index 00000000..0756e304 --- /dev/null +++ b/ccan/jbitset/jbitset.c @@ -0,0 +1,41 @@ +#include +#include +#include +#include + +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); +} diff --git a/ccan/jbitset/jbitset.h b/ccan/jbitset/jbitset.h new file mode 100644 index 00000000..bbce7eb2 --- /dev/null +++ b/ccan/jbitset/jbitset.h @@ -0,0 +1,299 @@ +#ifndef CCAN_JBITSET_H +#define CCAN_JBITSET_H +#include +#include +#include +#include + +/** + * 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 */ diff --git a/ccan/jbitset/jbitset_type.h b/ccan/jbitset/jbitset_type.h new file mode 100644 index 00000000..abd8c2b6 --- /dev/null +++ b/ccan/jbitset/jbitset_type.h @@ -0,0 +1,84 @@ +#ifndef CCAN_JBITSET_TYPE_H +#define CCAN_JBITSET_TYPE_H +#include + +/** + * 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__*) + * + * 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 */ diff --git a/ccan/jbitset/test/run-type.c b/ccan/jbitset/test/run-type.c new file mode 100644 index 00000000..1eefb423 --- /dev/null +++ b/ccan/jbitset/test/run-type.c @@ -0,0 +1,57 @@ +#include +#include +#include + +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(); +} diff --git a/ccan/jbitset/test/run.c b/ccan/jbitset/test/run.c new file mode 100644 index 00000000..09f00bd9 --- /dev/null +++ b/ccan/jbitset/test/run.c @@ -0,0 +1,66 @@ +#include +#include + +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(); +}