From 805ea0672938b40dea437ca68f32bf3380c191ed Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Fri, 23 Sep 2011 11:59:49 +0930 Subject: [PATCH] jbitset: rename to jset, use ccan/tcon It's now a completely generic set implementation, and uses ccan/tcon to always be typesafe. It handles both integer and pointer types. --- Makefile | 2 +- ccan/jbitset/jbitset.h | 309 -------------------- ccan/jbitset/jbitset_type.h | 85 ------ ccan/jbitset/test/run-type.c | 60 ---- ccan/jbitset/test/run.c | 66 ----- ccan/{jbitset => jset}/LICENSE | 0 ccan/{jbitset => jset}/_info | 45 +-- ccan/{jbitset/jbitset.c => jset/jset.c} | 15 +- ccan/jset/jset.h | 362 ++++++++++++++++++++++++ ccan/jset/test/run-pointer-type.c | 61 ++++ ccan/jset/test/run.c | 66 +++++ 11 files changed, 521 insertions(+), 550 deletions(-) delete mode 100644 ccan/jbitset/jbitset.h delete mode 100644 ccan/jbitset/jbitset_type.h delete mode 100644 ccan/jbitset/test/run-type.c delete mode 100644 ccan/jbitset/test/run.c rename ccan/{jbitset => jset}/LICENSE (100%) rename ccan/{jbitset => jset}/_info (61%) rename ccan/{jbitset/jbitset.c => jset/jset.c} (73%) create mode 100644 ccan/jset/jset.h create mode 100644 ccan/jset/test/run-pointer-type.c create mode 100644 ccan/jset/test/run.c diff --git a/Makefile b/Makefile index 1063f4c5..658953af 100644 --- a/Makefile +++ b/Makefile @@ -12,7 +12,7 @@ # Trying to build the whole repo is usually a lose; there will be some # dependencies you don't have. -EXCLUDE=wwviaudio ogg_to_pcm jmap jbitset nfs +EXCLUDE=wwviaudio ogg_to_pcm jmap jset nfs # Where make scores puts the results SCOREDIR=scores/$(shell whoami)/$(shell uname -s)-$(shell uname -m)-$(CC)-$(shell git describe --always --dirty) diff --git a/ccan/jbitset/jbitset.h b/ccan/jbitset/jbitset.h deleted file mode 100644 index acac2a76..00000000 --- a/ccan/jbitset/jbitset.h +++ /dev/null @@ -1,309 +0,0 @@ -/* Licensed under LGPLv2.1+ - see LICENSE file for details */ -#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 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, unsigned long 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, unsigned long 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, unsigned long 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 unsigned long jbit_popcount(const struct jbitset *set, - unsigned long start, - unsigned long 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, - * unsigned long n, unsigned long *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: - * unsigned long 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 %lu = %lu\n", i, val); - * } - */ -static inline unsigned long jbit_nth(const struct jbitset *set, - unsigned long n, unsigned long invalid) -{ - unsigned long 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(" %lu", i); - * printf("\n"); - */ -static inline unsigned long jbit_first(const struct jbitset *set, - unsigned long invalid) -{ - unsigned long 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 unsigned long jbit_next(const struct jbitset *set, - unsigned long prev, - unsigned long invalid) -{ - if (!Judy1Next(set->judy, &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(" %lu", i); - * printf("\n"); - */ -static inline unsigned long jbit_last(const struct jbitset *set, - unsigned long invalid) -{ - unsigned long 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 unsigned long jbit_prev(const struct jbitset *set, - unsigned long prev, - unsigned long invalid) -{ - if (!Judy1Prev(set->judy, &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 unsigned long jbit_first_clear(const struct jbitset *set, - unsigned long invalid) -{ - unsigned long index = 0; - if (!Judy1FirstEmpty(set->judy, &index, (JError_t *)&set->err)) - index = invalid; - else - assert(index != invalid); - return index; -} - -static inline unsigned long jbit_next_clear(const struct jbitset *set, - unsigned long prev, - unsigned long invalid) -{ - if (!Judy1NextEmpty(set->judy, &prev, (JError_t *)&set->err)) - prev = invalid; - else - assert(prev != invalid); - return prev; -} - -static inline unsigned long jbit_last_clear(const struct jbitset *set, - unsigned long invalid) -{ - unsigned long index = -1; - if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err)) - index = invalid; - else - assert(index != invalid); - return index; -} - -static inline unsigned long jbit_prev_clear(const struct jbitset *set, - unsigned long prev, - unsigned long invalid) -{ - if (!Judy1PrevEmpty(set->judy, &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 deleted file mode 100644 index c563a8e5..00000000 --- a/ccan/jbitset/jbitset_type.h +++ /dev/null @@ -1,85 +0,0 @@ -/* Licensed under LGPLv2.1+ - see LICENSE file for details */ -#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 deleted file mode 100644 index 47c5bfb2..00000000 --- a/ccan/jbitset/test/run-type.c +++ /dev/null @@ -1,60 +0,0 @@ -#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); - - for (i = 0; i < NUM; i++) - free(foo[i]); - - return exit_status(); -} diff --git a/ccan/jbitset/test/run.c b/ccan/jbitset/test/run.c deleted file mode 100644 index 09f00bd9..00000000 --- a/ccan/jbitset/test/run.c +++ /dev/null @@ -1,66 +0,0 @@ -#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(); -} diff --git a/ccan/jbitset/LICENSE b/ccan/jset/LICENSE similarity index 100% rename from ccan/jbitset/LICENSE rename to ccan/jset/LICENSE diff --git a/ccan/jbitset/_info b/ccan/jset/_info similarity index 61% rename from ccan/jbitset/_info rename to ccan/jset/_info index 52f7f127..6ff928f1 100644 --- a/ccan/jbitset/_info +++ b/ccan/jset/_info @@ -3,56 +3,56 @@ #include "config.h" /** - * jbitset - variable-length bitset (based on libJudy) + * jset - set of pointers (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. + * pointers (or unsigned longs) as the 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. + * jset.h contains typesafe wrappers for this usage. * * Example: * // Simple analysis of one-byte mallocs. + * #include * #include * #include * #include - * #include - * - * // Define jbit_char_ and jbitset_char, for char * bitset. - * JBIT_DEFINE_TYPE(char, char); - * + * + * struct jset_char { + * JSET_MEMBERS(char *); + * }; + * * int main(int argc, char *argv[]) * { * unsigned int i, runs, reuse; * size_t mindist = -1; - * struct jbitset_char *set = jbit_char_new(); + * struct jset_char *set = jset_new(struct jset_char); * 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))) + * if (!jset_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)) + * prev = jset_first(set)+1; + * for (p = jset_first(set); p; prev = p, p = jset_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)) + * for (p = jset_first(set); p; p = jset_next(set, p)) * free(p); * for (reuse = 0, i = 0; i < runs; i++) - * reuse += jbit_char_test(set, malloc(1)); - * + * reuse += jset_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, + * (jset_last(set) - jset_first(set)) / runs, * mindist, * 100.0 * reuse / runs); * return 0; @@ -69,6 +69,7 @@ int main(int argc, char *argv[]) if (strcmp(argv[1], "depends") == 0) { printf("ccan/build_assert\n"); printf("ccan/compiler\n"); + printf("ccan/tcon\n"); printf("Judy\n"); return 0; } diff --git a/ccan/jbitset/jbitset.c b/ccan/jset/jset.c similarity index 73% rename from ccan/jbitset/jbitset.c rename to ccan/jset/jset.c index a077afa2..42d23ac9 100644 --- a/ccan/jbitset/jbitset.c +++ b/ccan/jset/jset.c @@ -1,19 +1,20 @@ /* Licensed under LGPLv2.1+ - see LICENSE file for details */ -#include +#include #include #include #include -struct jbitset *jbit_new(void) +struct jset *jset_new_(size_t size) { - struct jbitset *set; + struct jset *set; /* Judy uses Word_t, we use unsigned long directly. */ BUILD_ASSERT(sizeof(unsigned long) == sizeof(Word_t)); - /* We pack pointers into jbitset (in jbitset_type.h) */ + /* We pack pointers into jset (in jset_type.h) */ BUILD_ASSERT(sizeof(Word_t) >= sizeof(void *)); - set = malloc(sizeof(*set)); + assert(size >= sizeof(*set)); + set = malloc(size); if (set) { set->judy = NULL; memset(&set->err, 0, sizeof(set->err)); @@ -22,7 +23,7 @@ struct jbitset *jbit_new(void) return set; } -const char *jbit_error_(struct jbitset *set) +const char *jset_error_str_(struct jset *set) { char *str; free((char *)set->errstr); @@ -36,7 +37,7 @@ const char *jbit_error_(struct jbitset *set) return str; } -void jbit_free(const struct jbitset *set) +void jset_free_(const struct jset *set) { free((char *)set->errstr); Judy1FreeArray((PPvoid_t)&set->judy, PJE0); diff --git a/ccan/jset/jset.h b/ccan/jset/jset.h new file mode 100644 index 00000000..ba72f097 --- /dev/null +++ b/ccan/jset/jset.h @@ -0,0 +1,362 @@ +/* Licensed under LGPLv2.1+ - see LICENSE file for details */ +#ifndef CCAN_JSET_H +#define CCAN_JSET_H +#include "config.h" +#include +#include +#include +#include +#include + +/** + * struct jset - private definition of a jset. + * + * It's exposed here so you can put it in your structures and so we can + * supply inline functions. + */ +struct jset { + void *judy; + JError_t err; + const char *errstr; +}; + +/** + * JSET_MEMBERS - declare members for a type-specific jset. + * @type: type for this set to contain, or void * for any pointer. + * + * Example: + * struct jset_long { + * JSET_MEMBERS(long); + * }; + */ +#define JSET_MEMBERS(type) \ + struct jset raw; \ + TCON(type canary) + +/** + * jset_new - create a new, empty jset. + * @type: the tcon-containing type to allocate. + * + * Example: + * struct jset_long { + * JSET_MEMBERS(long); + * } *set = jset_new(struct jset_long); + * + * if (!set) + * errx(1, "Failed to allocate set"); + */ +#define jset_new(type) ((type *)jset_new_(sizeof(type))) + +/** + * jset_free - destroy a jset. + * @set: the set returned from jset_new. + * + * Example: + * jset_free(set); + */ +#define jset_free(set) jset_free_(&(set)->raw) + +/** + * jset_error - test for an error in the a previous jset_ 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 jset_free() on the set. + * + * Other than out-of-memory, errors are caused by memory corruption or + * interface misuse. + * + * Example: + * const char *errstr; + * + * errstr = jset_error(set); + * if (errstr) + * errx(1, "Woah, error on newly created set?! %s", errstr); + */ +#define jset_error(set) \ + jset_error_(&(set)->raw) + +/** + * jset_raw - unwrap the typed set and check the type + * @set: the typed jset + * @expr: the expression to check the type against (not evaluated) + * + * This macro usually causes the compiler to emit a warning if the + * variable is of an unexpected type. It is used internally where we + * need to access the raw underlying jset. + */ +#define jset_raw(set, expr) (&tcon_check((set), canary, (expr))->raw) + +/** + * jset_test - test a bit in the bitset. + * @set: bitset from jset_new + * @index: the index to test + * + * Returns true if jset_set() has been done on this index, false otherwise. + * + * Example: + * assert(!jset_test(set, 0)); + */ +#define jset_test(set, index) \ + jset_test_(jset_raw((set), (index)), (unsigned long)(index)) + +/** + * jset_set - set a bit in the bitset. + * @set: bitset from jset_new + * @index: the index to set + * + * Returns false if it was already set (ie. nothing changed) + * + * Example: + * if (jset_set(set, 0)) + * err(1, "Bit 0 was already set?!"); + */ +#define jset_set(set, index) \ + jset_set_(jset_raw((set), (index)), (unsigned long)(index)) + +/** + * jset_clear - clear a bit in the bitset. + * @set: bitset from jset_new + * @index: the index to set + * + * Returns the old bit value (ie. false if nothing changed). + * + * Example: + * if (jset_clear(set, 0)) + * err(1, "Bit 0 was already clear?!"); + */ +#define jset_clear(set, index) \ + jset_clear_(jset_raw((set), (index)), (unsigned long)(index)) + +/** + * jset_count - get population of bitset. + * @set: bitset from jset_new + * + * Example: + * // We expect 1000 entries. + * assert(jset_count(set) == 1000); + */ +#define jset_count(set) \ + jset_popcount_(&(set)->raw, 0, -1UL) + +/** + * jset_popcount - get population of (some part of) bitset. + * @set: bitset from jset_new + * @start: first index to count + * @end_incl: last index to count (use -1 for end). + * + * Example: + * assert(jset_popcount(set, 0, 1000) <= jset_popcount(set, 0, 2000)); + */ +#define jset_popcount(set, start, end_incl) \ + jset_popcount_(jset_raw((set), (start) ? (start) : (end_incl)), \ + (unsigned long)(start), (unsigned long)(end_incl)) + +/** + * jset_nth - return the index of the nth bit which is set. + * @set: bitset from jset_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 jset_nth_index(struct jset *set, + * unsigned long n, unsigned long *idx) + * { + * // Zero might be valid, if it's first in set. + * if (n == 0 && jset_test(set, 0)) { + * *idx = 0; + * return true; + * } + * *idx = jset_nth(set, n, 0); + * return (*idx != 0); + * } + * + * Example: + * unsigned long i, val; + * + * // We know 0 isn't in set. + * assert(!jset_test(set, 0)); + * for (i = 0; (val = jset_nth(set, i, 0)) != 0; i++) { + * assert(jset_popcount(set, 0, val) == i); + * printf("Value %lu = %lu\n", i, val); + * } + */ +#define jset_nth(set, n, invalid) \ + tcon_cast((set), canary, \ + jset_nth_(jset_raw((set), (invalid)), \ + (n), (unsigned long)(invalid))) + +/** + * jset_first - return the first bit which is set (must not contain 0). + * @set: bitset from jset_new + * + * This is equivalent to jset_nth(set, 0, 0). ie. useful only if 0 + * isn't in your set. + * + * Example: + * assert(!jset_test(set, 0)); + * printf("Set contents (increasing order):"); + * for (i = jset_first(set); i; i = jset_next(set, i)) + * printf(" %lu", i); + * printf("\n"); + */ +#define jset_first(set) \ + tcon_cast((set), canary, jset_first_(&(set)->raw)) + +/** + * jset_next - return the next bit which is set (must not contain 0). + * @set: bitset from jset_new + * @prev: previous index + * + * This is usually used to find an adjacent index which is set, after + * jset_first. + */ +#define jset_next(set, prev) \ + tcon_cast((set), canary, jset_next_(&(set)->raw, (unsigned long)(prev))) + +/** + * jset_last - return the last bit which is set (must not contain 0). + * @set: bitset from jset_new + * + * Example: + * assert(!jset_test(set, 0)); + * printf("Set contents (decreasing order):"); + * for (i = jset_last(set); i; i = jset_prev(set, i)) + * printf(" %lu", i); + * printf("\n"); + */ +#define jset_last(set) \ + tcon_cast((set), canary, jset_last_(&(set)->raw)) + +/** + * jset_prev - return the previous bit which is set (must not contain 0). + * @set: bitset from jset_new + * @prev: previous index + * + * This is usually used to find an adjacent bit which is set, after + * jset_last. + */ +#define jset_prev(set, prev) \ + tcon_cast((set), canary, jset_prev_(&(set)->raw, (unsigned long)(prev))) + +/** + * jset_first_clear - return the first bit which is unset + * @set: bitset from jset_new + * + * This allows for iterating the inverse of the bitmap; only returns 0 if the + * set is full. + */ +#define jset_first_clear(set) \ + tcon_cast((set), canary, jset_next_clear_(&(set)->raw, 0)) + +#define jset_next_clear(set, prev) \ + tcon_cast((set), canary, jset_next_clear_(&(set)->raw, \ + (unsigned long)(prev))) + +#define jset_last_clear(set) \ + tcon_cast((set), canary, jset_last_clear_(&(set)->raw)) + +#define jset_prev_clear(set, prev) \ + tcon_cast((set), canary, jset_prev_clear_(&(set)->raw, \ + (unsigned long)(prev))) + +/* Raw functions */ +struct jset *jset_new_(size_t size); +void jset_free_(const struct jset *set); +const char *COLD jset_error_str_(struct jset *set); +static inline const char *jset_error_(struct jset *set) +{ + if (JU_ERRNO(&set->err) <= JU_ERRNO_NFMAX) + return NULL; + return jset_error_str_(set); +} +static inline bool jset_test_(const struct jset *set, unsigned long index) +{ + return Judy1Test(set->judy, index, (JError_t *)&set->err); +} +static inline bool jset_set_(struct jset *set, unsigned long index) +{ + return Judy1Set(&set->judy, index, &set->err); +} +static inline bool jset_clear_(struct jset *set, unsigned long index) +{ + return Judy1Unset(&set->judy, index, &set->err); +} +static inline unsigned long jset_popcount_(const struct jset *set, + unsigned long start, + unsigned long end_incl) +{ + return Judy1Count(set->judy, start, end_incl, (JError_t *)&set->err); +} +static inline unsigned long jset_nth_(const struct jset *set, + unsigned long n, unsigned long invalid) +{ + unsigned long index; + if (!Judy1ByCount(set->judy, n+1, &index, (JError_t *)&set->err)) + index = invalid; + return index; +} +static inline unsigned long jset_first_(const struct jset *set) +{ + unsigned long index = 0; + if (!Judy1First(set->judy, &index, (JError_t *)&set->err)) + index = 0; + else + assert(index != 0); + return index; +} +static inline unsigned long jset_next_(const struct jset *set, + unsigned long prev) +{ + if (!Judy1Next(set->judy, &prev, (JError_t *)&set->err)) + prev = 0; + else + assert(prev != 0); + return prev; +} +static inline unsigned long jset_last_(const struct jset *set) +{ + unsigned long index = -1; + if (!Judy1Last(set->judy, &index, (JError_t *)&set->err)) + index = 0; + else + assert(index != 0); + return index; +} +static inline unsigned long jset_prev_(const struct jset *set, + unsigned long prev) +{ + if (!Judy1Prev(set->judy, &prev, (JError_t *)&set->err)) + prev = 0; + else + assert(prev != 0); + return prev; +} +static inline unsigned long jset_next_clear_(const struct jset *set, + unsigned long prev) +{ + if (!Judy1NextEmpty(set->judy, &prev, (JError_t *)&set->err)) + prev = 0; + else + assert(prev != 0); + return prev; +} +static inline unsigned long jset_last_clear_(const struct jset *set) +{ + unsigned long index = -1; + if (!Judy1LastEmpty(set->judy, &index, (JError_t *)&set->err)) + index = 0; + return index; +} +static inline unsigned long jset_prev_clear_(const struct jset *set, + unsigned long prev) +{ + if (!Judy1PrevEmpty(set->judy, &prev, (JError_t *)&set->err)) + prev = 0; + return prev; +} +#endif /* CCAN_JSET_H */ diff --git a/ccan/jset/test/run-pointer-type.c b/ccan/jset/test/run-pointer-type.c new file mode 100644 index 00000000..7cf86df0 --- /dev/null +++ b/ccan/jset/test/run-pointer-type.c @@ -0,0 +1,61 @@ +#include +#include + +struct foo; + +struct jset_foo { + JSET_MEMBERS(struct 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 jset_foo *set; + struct foo *foo[NUM]; + unsigned int i; + + plan_tests(20); + for (i = 0; i < NUM; i++) + foo[i] = malloc(20); + + set = jset_new(struct jset_foo); + ok1(jset_error(set) == NULL); + + ok1(jset_set(set, foo[0]) == true); + ok1(jset_set(set, foo[0]) == false); + ok1(jset_clear(set, foo[0]) == true); + ok1(jset_clear(set, foo[0]) == false); + ok1(jset_count(set) == 0); + ok1(jset_nth(set, 0, NULL) == (struct foo *)NULL); + ok1(jset_first(set) == (struct foo *)NULL); + ok1(jset_last(set) == (struct foo *)NULL); + + for (i = 0; i < NUM; i++) + jset_set(set, foo[i]); + + qsort(foo, NUM, sizeof(foo[0]), cmp_ptr); + + ok1(jset_count(set) == NUM); + ok1(jset_nth(set, 0, NULL) == foo[0]); + ok1(jset_nth(set, NUM-1, NULL) == foo[NUM-1]); + ok1(jset_nth(set, NUM, NULL) == (struct foo *)NULL); + ok1(jset_first(set) == foo[0]); + ok1(jset_last(set) == foo[NUM-1]); + ok1(jset_next(set, foo[0]) == foo[1]); + ok1(jset_next(set, foo[NUM-1]) == (struct foo *)NULL); + ok1(jset_prev(set, foo[1]) == foo[0]); + ok1(jset_prev(set, foo[0]) == (struct foo *)NULL); + ok1(jset_error(set) == NULL); + jset_free(set); + + for (i = 0; i < NUM; i++) + free(foo[i]); + + return exit_status(); +} diff --git a/ccan/jset/test/run.c b/ccan/jset/test/run.c new file mode 100644 index 00000000..a0fb8a8c --- /dev/null +++ b/ccan/jset/test/run.c @@ -0,0 +1,66 @@ +#include +#include + +int main(int argc, char *argv[]) +{ + struct jset_long { + JSET_MEMBERS(unsigned long); + } *set; + size_t i; + const char *err; + + plan_tests(34); + + set = jset_new(struct jset_long); + ok1(jset_error(set) == NULL); + + ok1(jset_set(set, 0) == true); + ok1(jset_set(set, 0) == false); + ok1(jset_clear(set, 0) == true); + ok1(jset_clear(set, 0) == false); + ok1(jset_popcount(set, 0, -1) == 0); + ok1(jset_nth(set, 0, 0) == 0); + ok1(jset_nth(set, 0, -1) == (size_t)-1); + ok1(jset_first(set) == 0); + ok1(jset_last(set) == 0); + ok1(jset_first_clear(set) == 1); + ok1(jset_last_clear(set) == (size_t)-1); + ok1(jset_prev_clear(set, 1) == 0); + ok1(jset_next_clear(set, 1) == 2); + ok1(jset_next_clear(set, -1) == 0); + + /* Set a million bits, 16 bits apart. */ + for (i = 0; i < 1000000; i++) + jset_set(set, 1 + (i << 4)); + + /* This only take 1.7MB on my 32-bit system. */ + diag("%u bytes memory used\n", (unsigned)Judy1MemUsed(set->raw.judy)); + + ok1(jset_popcount(set, 0, -1) == 1000000); + ok1(jset_nth(set, 0, -1) == 1); + ok1(jset_nth(set, 999999, -1) == 1 + (999999 << 4)); + ok1(jset_nth(set, 1000000, -1) == (size_t)-1); + ok1(jset_first(set) == 1); + ok1(jset_last(set) == 1 + (999999 << 4)); + ok1(jset_first_clear(set) == 2); + ok1(jset_last_clear(set) == (size_t)-1); + ok1(jset_prev_clear(set, 3) == 2); + ok1(jset_prev_clear(set, 2) == 0); + ok1(jset_next(set, 1) == 1 + (1 << 4)); + ok1(jset_next(set, 1 + (999999 << 4)) == 0); + ok1(jset_prev(set, 1) == 0); + ok1(jset_prev(set, 2) == 1); + ok1(jset_error(set) == NULL); + + /* Test error handling */ + JU_ERRNO(&set->raw.err) = 100; + JU_ERRID(&set->raw.err) = 991; + err = jset_error(set); + ok1(err); + ok1(strstr(err, "100")); + ok1(strstr(err, "991")); + ok1(err == set->raw.errstr); + jset_free(set); + + return exit_status(); +} -- 2.39.2