jbitset: rename to jset, use ccan/tcon
authorRusty Russell <rusty@rustcorp.com.au>
Fri, 23 Sep 2011 02:29:49 +0000 (11:59 +0930)
committerRusty Russell <rusty@rustcorp.com.au>
Fri, 23 Sep 2011 02:29:49 +0000 (11:59 +0930)
It's now a completely generic set implementation, and uses ccan/tcon
to always be typesafe.  It handles both integer and pointer types.

14 files changed:
Makefile
ccan/jbitset/LICENSE [deleted symlink]
ccan/jbitset/_info [deleted file]
ccan/jbitset/jbitset.c [deleted file]
ccan/jbitset/jbitset.h [deleted file]
ccan/jbitset/jbitset_type.h [deleted file]
ccan/jbitset/test/run-type.c [deleted file]
ccan/jbitset/test/run.c [deleted file]
ccan/jset/LICENSE [new symlink]
ccan/jset/_info [new file with mode: 0644]
ccan/jset/jset.c [new file with mode: 0644]
ccan/jset/jset.h [new file with mode: 0644]
ccan/jset/test/run-pointer-type.c [new file with mode: 0644]
ccan/jset/test/run.c [new file with mode: 0644]

index 1063f4c57d05b4bd4369f282fb68999d173f74f0..658953af4a49628b6df7cf8863ab828ce8497033 100644 (file)
--- 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/LICENSE b/ccan/jbitset/LICENSE
deleted file mode 120000 (symlink)
index dc314ec..0000000
+++ /dev/null
@@ -1 +0,0 @@
-../../licenses/LGPL-2.1
\ No newline at end of file
diff --git a/ccan/jbitset/_info b/ccan/jbitset/_info
deleted file mode 100644 (file)
index 52f7f12..0000000
+++ /dev/null
@@ -1,82 +0,0 @@
-#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 (v2.1 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;
-}
diff --git a/ccan/jbitset/jbitset.c b/ccan/jbitset/jbitset.c
deleted file mode 100644 (file)
index a077afa..0000000
+++ /dev/null
@@ -1,44 +0,0 @@
-/* Licensed under LGPLv2.1+ - see LICENSE file for details */
-#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 unsigned long directly. */
-       BUILD_ASSERT(sizeof(unsigned long) == sizeof(Word_t));
-       /* We pack pointers into jbitset (in jbitset_type.h) */
-       BUILD_ASSERT(sizeof(Word_t) >= sizeof(void *));
-
-       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
deleted file mode 100644 (file)
index acac2a7..0000000
+++ /dev/null
@@ -1,309 +0,0 @@
-/* Licensed under LGPLv2.1+ - see LICENSE file for details */
-#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 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 (file)
index c563a8e..0000000
+++ /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 <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 */
diff --git a/ccan/jbitset/test/run-type.c b/ccan/jbitset/test/run-type.c
deleted file mode 100644 (file)
index 47c5bfb..0000000
+++ /dev/null
@@ -1,60 +0,0 @@
-#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);
-
-       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 (file)
index 09f00bd..0000000
+++ /dev/null
@@ -1,66 +0,0 @@
-#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();
-}
diff --git a/ccan/jset/LICENSE b/ccan/jset/LICENSE
new file mode 120000 (symlink)
index 0000000..dc314ec
--- /dev/null
@@ -0,0 +1 @@
+../../licenses/LGPL-2.1
\ No newline at end of file
diff --git a/ccan/jset/_info b/ccan/jset/_info
new file mode 100644 (file)
index 0000000..6ff928f
--- /dev/null
@@ -0,0 +1,83 @@
+#include <stdio.h>
+#include <string.h>
+#include "config.h"
+
+/**
+ * jset - set of pointers (based on libJudy)
+ *
+ * This provides a convenient wrapper for using Judy bitsets; using
+ * pointers (or unsigned longs) as the index, Judy arrays provide an
+ * efficient bit array or bit map of variable size.
+ *
+ * jset.h contains typesafe wrappers for this usage.
+ *
+ * Example:
+ * // Simple analysis of one-byte mallocs.
+ * #include <ccan/jset/jset.h>
+ * #include <stdlib.h>
+ * #include <stdio.h>
+ * #include <err.h>
+ *
+ * struct jset_char {
+ *     JSET_MEMBERS(char *);
+ * };
+ *
+ * int main(int argc, char *argv[])
+ * {
+ *     unsigned int i, runs, reuse;
+ *     size_t mindist = -1;
+ *     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 (!jset_set(set, malloc(1)))
+ *                     errx(1, "same pointer allocated twice!");
+ *
+ *     // Calculate minimum distance
+ *     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 = jset_first(set); p; p = jset_next(set, p))
+ *             free(p);
+ *     for (reuse = 0, i = 0; i < runs; i++)
+ *             reuse += jset_test(set, malloc(1));
+ *
+ *     printf("Allocation density (bytes): %zu\n"
+ *            "Minimum inter-pointer distance: %zu\n"
+ *            "Reuse rate: %.0f%%\n",
+ *            (jset_last(set) - jset_first(set)) / runs,
+ *            mindist,
+ *            100.0 * reuse / runs);
+ *     return 0;
+ * }
+ *
+ * License: LGPL (v2.1 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("ccan/tcon\n");
+               printf("Judy\n");
+               return 0;
+       }
+
+       if (strcmp(argv[1], "libs") == 0) {
+               printf("Judy\n");
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/jset/jset.c b/ccan/jset/jset.c
new file mode 100644 (file)
index 0000000..42d23ac
--- /dev/null
@@ -0,0 +1,45 @@
+/* Licensed under LGPLv2.1+ - see LICENSE file for details */
+#include <ccan/jset/jset.h>
+#include <ccan/build_assert/build_assert.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct jset *jset_new_(size_t size)
+{
+       struct jset *set;
+
+       /* Judy uses Word_t, we use unsigned long directly. */
+       BUILD_ASSERT(sizeof(unsigned long) == sizeof(Word_t));
+       /* We pack pointers into jset (in jset_type.h) */
+       BUILD_ASSERT(sizeof(Word_t) >= sizeof(void *));
+
+       assert(size >= sizeof(*set));
+       set = malloc(size);
+       if (set) {
+               set->judy = NULL;
+               memset(&set->err, 0, sizeof(set->err));
+               set->errstr = NULL;
+       }
+       return set;
+}
+
+const char *jset_error_str_(struct jset *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 jset_free_(const struct jset *set)
+{
+       free((char *)set->errstr);
+       Judy1FreeArray((PPvoid_t)&set->judy, PJE0);
+       free((void *)set);
+}
diff --git a/ccan/jset/jset.h b/ccan/jset/jset.h
new file mode 100644 (file)
index 0000000..ba72f09
--- /dev/null
@@ -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 <ccan/compiler/compiler.h>
+#include <ccan/tcon/tcon.h>
+#include <Judy.h>
+#include <stdbool.h>
+#include <assert.h>
+
+/**
+ * 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 (file)
index 0000000..7cf86df
--- /dev/null
@@ -0,0 +1,61 @@
+#include <ccan/tap/tap.h>
+#include <ccan/jset/jset.c>
+
+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 (file)
index 0000000..a0fb8a8
--- /dev/null
@@ -0,0 +1,66 @@
+#include <ccan/tap/tap.h>
+#include <ccan/jset/jset.c>
+
+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();
+}