From: Rusty Russell Date: Sat, 30 Oct 2010 10:15:36 +0000 (+1030) Subject: jmap: new module X-Git-Url: http://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=4116b284c098f6c67f62d8292e93d8f73d833e9d jmap: new module --- diff --git a/ccan/jmap/_info b/ccan/jmap/_info new file mode 100644 index 00000000..03aa4ca8 --- /dev/null +++ b/ccan/jmap/_info @@ -0,0 +1,97 @@ +#include +#include +#include "config.h" + +/** + * jmap - map from indices to values (based on libJudy) + * + * This provides a convenient wrapper for using JudyL arrays; using + * integers or pointers as an index, Judy arrays provide an efficient + * map to integers or pointers. + * + * jmap.h simply contains wrappers for a size_t-indexed size_t values, and + * jmap_type.h contain a wrapper macro for size_t->pointer maps and pointer + * ->pointer maps. + * + * Example: + * // Silly example of associating data with arguments by pointer and int. + * #include + * #include + * #include + * + * struct opt_detail { + * bool is_long; + * unsigned int length; // == 1 if !is_long. + * }; + * + * // Define jmap_arg_ and jmap_arg, for int -> argv. + * JMAP_DEFINE_UINTIDX_TYPE(char, arg); + * // Define jmap_opt_ and jmap_opt, for argv -> struct opt_detail *. + * JMAP_DEFINE_PTRIDX_TYPE(char, struct opt_detail, opt); + * + * int main(int argc, char *argv[]) + * { + * int i; + * // This map is equivalent to the argv[] array. Silly example. + * struct jmap_arg *arg = jmap_arg_new(); + * struct jmap_opt *opt = jmap_opt_new(); + * struct opt_detail *d; + * + * // Note: this is not correct for real parsing! + * for (i = 0; i < argc; i++) { + * jmap_arg_add(arg, i, argv[i]); + * if (i < 1 || argv[i][0] != '-') + * continue; + * d = malloc(sizeof(*d)); + * if (argv[i][1] == '-') { + * // -- + * d->is_long = true; + * d->length = strlen(argv[i]+2); + * } else { + * // - + * d->is_long = false; + * d->length = 1; + * } + * jmap_opt_add(opt, argv[i], d); + * } + * + * printf("Found %u options:\n", jmap_opt_count(opt)); + * for (i = jmap_arg_first(arg,-1); i!=-1; i = jmap_arg_next(arg,i,-1)) { + * char *a = jmap_arg_get(arg, i); + * d = jmap_opt_get(opt, a); + * printf(" Arg %i ('%s') is a %s of %u chars\n", + * i, a, + * d == NULL ? "normal argument" + * : d->is_long ? "long option" + * : "short option", + * d == NULL ? strlen(a) : d->length); + * // We no longer need it, so free it here. + * free(d); + * } + * jmap_opt_free(opt); + * jmap_arg_free(arg); + * 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/jmap/jmap.c b/ccan/jmap/jmap.c new file mode 100644 index 00000000..279f6519 --- /dev/null +++ b/ccan/jmap/jmap.c @@ -0,0 +1,45 @@ +#include +#include +#include +#include + +struct jmap *jmap_new(void) +{ + struct jmap *map; + + /* Judy uses Word_t, we use size_t. */ + BUILD_ASSERT(sizeof(size_t) == sizeof(Word_t)); + + map = malloc(sizeof(*map)); + if (map) { + map->judy = NULL; + memset(&map->err, 0, sizeof(map->err)); + map->errstr = NULL; + map->num_accesses = 0; + map->acc_value = NULL; + map->acc_index = 0; + map->funcname = NULL; + } + return map; +} + +const char *jmap_error_(struct jmap *map) +{ + char *str; + free((char *)map->errstr); + map->errstr = str = malloc(100); + if (!map->errstr) + return "out of memory"; + + sprintf(str, + "JU_ERRNO_* == %d, ID == %d\n", + JU_ERRNO(&map->err), JU_ERRID(&map->err)); + return str; +} + +void jmap_free(const struct jmap *map) +{ + free((char *)map->errstr); + Judy1FreeArray((PPvoid_t)&map->judy, PJE0); + free((void *)map); +} diff --git a/ccan/jmap/jmap.h b/ccan/jmap/jmap.h new file mode 100644 index 00000000..faba53c0 --- /dev/null +++ b/ccan/jmap/jmap.h @@ -0,0 +1,527 @@ +#ifndef CCAN_JMAP_H +#define CCAN_JMAP_H +#include +#include +#include +#include +#ifdef DEBUG +#include +#endif + +/** + * jmap_new - create a new, empty jmap. + * + * See Also: + * JMAP_DEFINE_TYPE() + * + * Example: + * struct jmap *map = jmap_new(); + * if (!map) + * errx(1, "Failed to allocate jmap"); + */ +struct jmap *jmap_new(void); + +/** + * jmap_free - destroy a jmap. + * @map: the map returned from jmap_new. + * + * Example: + * jmap_free(map); + */ +void jmap_free(const struct jmap *map); + +/* This is exposed in the header so we can inline. Treat it as private! */ +struct jmap { + Pvoid_t judy; + JError_t err; + const char *errstr; + /* Used if !NDEBUG */ + int num_accesses; + /* Used if DEBUG */ + size_t *acc_value; + size_t acc_index; + const char *funcname; +}; +const char *COLD_ATTRIBUTE jmap_error_(struct jmap *map); + +/* Debugging checks. */ +static inline void jmap_debug_add_access(const struct jmap *map, + size_t index, size_t *val, + const char *funcname) +{ +#ifdef DEBUG + if (!map->acc_value) { + ((struct jmap *)map)->acc_value = val; + ((struct jmap *)map)->acc_index = index; + ((struct jmap *)map)->funcname = funcname; + } +#endif + if (val) + assert(++((struct jmap *)map)->num_accesses); +} + +static inline void jmap_debug_del_access(struct jmap *map, size_t **val) +{ + assert(--map->num_accesses >= 0); +#ifdef DEBUG + if (map->acc_value == *val) + map->acc_value = NULL; +#endif + /* Set it to some invalid value. Not NULL, they might rely on that! */ + assert((*val = (void *)jmap_new) != NULL); +} + +static inline void jmap_debug_access(struct jmap *map) +{ +#ifdef DEBUG + if (map->num_accesses && map->acc_value) + fprintf(stderr, + "jmap: still got index %zu, val %zu (%p) from %s\n", + map->acc_index, *map->acc_value, map->acc_value, + map->funcname); +#endif + assert(!map->num_accesses); +} + +/** + * jmap_error - test for an error in the a previous jmap_ operation. + * @map: the map 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 jmap_free() on the map. + * + * Other than out-of-memory, errors are caused by memory corruption or + * interface misuse. + * + * Example: + * struct jmap *map = jmap_new(); + * const char *errstr; + * + * if (!map) + * err(1, "allocating jmap"); + * errstr = jmap_error(map); + * if (errstr) + * errx(1, "Woah, error on newly created map?! %s", errstr); + */ +static inline const char *jmap_error(struct jmap *map) +{ + if (JU_ERRNO(&map->err) <= JU_ERRNO_NFMAX) + return NULL; + return jmap_error_(map); +} + +/** + * jmap_add - add or replace a value for a given index in the map. + * @map: map from jmap_new + * @index: the index to map + * @value: the value to associate with the index + * + * Adds index into the map; replaces value if it's already there. + * Returns false on error (out of memory). + * + * Example: + * if (!jmap_add(map, 0, 1)) + * err(1, "jmap_add failed!"); + */ +static inline bool jmap_add(struct jmap *map, size_t index, size_t value) +{ + Word_t *val; + jmap_debug_access(map); + val = (void *)JudyLIns(&map->judy, index, &map->err); + if (val == PJERR) + return false; + *val = value; + return true; +} + +/** + * jmap_set - change a value for an existing index in the map. + * @map: map from jmap_new + * @index: the index to map + * @value: the value to associate with the index + * + * This sets the value of an index if it already exists, and return true, + * otherwise returns false and does nothing. + * + * Example: + * if (!jmap_set(map, 0, 2)) + * err(1, "jmap_set: index 0 not found"); + */ +static inline bool jmap_set(const struct jmap *map, size_t index, size_t value) +{ + Word_t *val; + val = (void *)JudyLGet(map->judy, index, (JError_t *)&map->err); + if (val && val != PJERR) { + *val = value; + return true; + } + return false; +} + +/** + * jmap_del - remove an index from the map. + * @map: map from jmap_new + * @index: the index to map + * + * Example: + * if (!jmap_del(map, 0)) + * err(1, "jmap_del failed!"); + */ +static inline bool jmap_del(struct jmap *map, size_t index) +{ + jmap_debug_access(map); + return JudyLDel(&map->judy, index, &map->err) == 1; +} + +/** + * jmap_test - test if a given index is defined. + * @map: map from jmap_new + * @index: the index to find + * + * Example: + * jmap_add(map, 0, 1); + * assert(jmap_test(map, 0)); + */ +static inline bool jmap_test(const struct jmap *map, size_t index) +{ + return JudyLGet(map->judy, index, (JError_t *)&map->err) != NULL; +} + +/** + * jmap_get - get a value for a given index. + * @map: map from jmap_new + * @index: the index to find + * @invalid: the value to return if the index isn't found. + * + * Example: + * jmap_add(map, 0, 1); + * assert(jmap_get(map, 0, -1) == 1); + * + * See Also: + * jmap_getval() + */ +static inline size_t jmap_get(const struct jmap *map, size_t index, + size_t invalid) +{ + Word_t *val; + val = (void *)JudyLGet(map->judy, index, (JError_t *)&map->err); + if (!val || val == PJERR) + return invalid; + return *val; +} + +/** + * jmap_popcount - get population of (some part of) the map. + * @map: map from jmap_new + * @start: first index to count + * @end_incl: last index to count (use -1 for end). + * + * Example: + * assert(jmap_popcount(map, 0, 1000) <= jmap_popcount(map, 0, 2000)); + */ +static inline size_t jmap_popcount(const struct jmap *map, + size_t start, size_t end_incl) +{ + return JudyLCount(map->judy, start, end_incl, (JError_t *)&map->err); +} + +/** + * jmap_nth - return the index of the nth value in the map. + * @map: map from jmap_new + * @n: which index we are interested in (0-based) + * @invalid: what to return if n >= map population + * + * This normally returns the nth index in the map, and often there is a + * convenient known-invalid value (ie. something which is never in the + * map). Otherwise you can use jmap_nthval(). + * + * Example: + * size_t i, index; + * + * // We know 0 isn't in map. + * assert(!jmap_test(map, 0)); + * for (i = 0; (index = jmap_nth(map, i, 0)) != 0; i++) { + * assert(jmap_popcount(map, 0, index) == i); + * printf("Index %zu = %zu\n", i, index); + * } + * + * See Also: + * jmap_nthval(); + */ +static inline size_t jmap_nth(const struct jmap *map, + size_t n, size_t invalid) +{ + Word_t index; + if (!JudyLByCount(map->judy, n+1, &index, (JError_t *)&map->err)) + index = invalid; + return index; +} + +/** + * jmap_first - return the first index in the map. + * @map: map from jmap_new + * @invalid: return value if jmap is empty. + * + * This is equivalent to jmap_nth(map, 0, invalid). + * + * Example: + * assert(!jmap_test(map, 0)); + * printf("Map indices (increasing order):"); + * for (i = jmap_first(map, 0); i; i = jmap_next(map, i, 0)) + * printf(" %zu", i); + * printf("\n"); + * + * See Also: + * jmap_firstval() + */ +static inline size_t jmap_first(const struct jmap *map, size_t invalid) +{ + Word_t index = 0; + if (!JudyLFirst(map->judy, &index, (JError_t *)&map->err)) + index = invalid; + else + assert(index != invalid); + return index; +} + +/** + * jmap_next - return the next index in the map. + * @map: map from jmap_new + * @prev: previous index + * @invalid: return value if there prev was final index in map. + * + * This is usually used to find an adjacent index after jmap_first. + * See Also: + * jmap_nextval() + */ +static inline size_t jmap_next(const struct jmap *map, size_t prev, + size_t invalid) +{ + if (!JudyLNext(map->judy, (Word_t *)&prev, (JError_t *)&map->err)) + prev = invalid; + else + assert(prev != invalid); + return prev; +} + +/** + * jmap_last - return the last index in the map. + * @map: map from jmap_new + * @invalid: return value if map is empty. + * + * Example: + * assert(!jmap_test(map, 0)); + * printf("Map indices (increasing order):"); + * for (i = jmap_last(map, 0); i; i = jmap_prev(map, i, 0)) + * printf(" %zu", i); + * printf("\n"); + * See Also: + * jmap_lastval() + */ +static inline size_t jmap_last(const struct jmap *map, size_t invalid) +{ + Word_t index = -1; + if (!JudyLLast(map->judy, &index, (JError_t *)&map->err)) + index = invalid; + else + assert(index != invalid); + return index; +} + +/** + * jmap_prev - return the previous index in the map. + * @map: map from jmap_new + * @prev: previous index + * @invalid: return value if no previous indices are in the map. + * + * This is usually used to find an prior adjacent index after jmap_last. + * See Also: + * jmap_prevval() + */ +static inline size_t jmap_prev(const struct jmap *map, size_t prev, + size_t invalid) +{ + if (!JudyLPrev(map->judy, (Word_t *)&prev, (JError_t *)&map->err)) + prev = invalid; + else + assert(prev != invalid); + return prev; +} + +/** + * jmap_getval - access a value in-place for a given index. + * @map: map from jmap_new + * @index: the index to find + * + * Returns a pointer into the map, or NULL if the index isn't in the + * map. Like the other val functions (jmap_nthval, jmap_firstval + * etc), this pointer cannot be used after a jmap_add or jmap_del + * call, and you must call jmap_putval() once you are finished. + * + * Unless you define NDEBUG, jmap_add and kmap_del will check that you + * have called jmap_putval(). + * + * Example: + * size_t *p; + * jmap_add(map, 0, 1); + * p = jmap_getval(map, 0); + * if (!p) + * errx(1, "Could not find 0 in map!"); + * if (*p != 1) + * errx(1, "Value in map was not 0?!"); + * *p = 7; + * jmap_putval(map, &p); + * // Accessing p now would probably crash. + * + * See Also: + * jmap_putval(), jmap_firstval() + */ +static inline size_t *jmap_getval(struct jmap *map, size_t index) +{ + size_t *val; + val = (void *)JudyLGet(map->judy, index, (JError_t *)&map->err); + jmap_debug_add_access(map, index, val, "jmap_getval"); + return val; +} + +/** + * jmap_putval - revoke access to a value. + * @map: map from jmap_new + * @p: the pointer to a pointer to the value + * + * @p is a pointer to the (successful) value retuned from one of the + * jmap_*val functions (listed below). After this, it will be invalid. + * + * Unless NDEBUG is defined, this will actually alter the value of p + * to point to garbage to help avoid accidental use. + * + * See Also: + * jmap_getval(), jmap_nthval(), jmap_firstval(), jmap_nextval(), + * jmap_lastval(), jmap_prevval(). + */ +static inline void jmap_putval(struct jmap *map, size_t **p) +{ + jmap_debug_del_access(map, p); +} + +/** + * jmap_nthval - access the value of the nth value in the map. + * @map: map from jmap_new + * @n: which index we are interested in (0-based) + * + * This returns a pointer to the value at the nth index in the map, + * or NULL if there are n is greater than the population of the map. + * You must use jmap_putval() on the pointer once you are done with it. + * + * Example: + * size_t *val; + * + * // We know 0 isn't in map. + * assert(!jmap_test(map, 0)); + * for (i = 0; (val = jmap_nthval(map, i, &index)) != NULL; i++) { + * assert(jmap_popcount(map, 0, index) == i); + * printf("Index %zu = %zu, value = %zu\n", i, index, *val); + * jmap_putval(map, &val); + * } + * + * See Also: + * jmap_nth(); + */ +static inline size_t *jmap_nthval(const struct jmap *map, + size_t n, size_t *index) +{ + size_t *val; + val = (size_t *)JudyLByCount(map->judy, n+1, (Word_t *)index, + (JError_t *)&map->err); + jmap_debug_add_access(map, *index, val, "jmap_nthval"); + return val; +} + +/** + * jmap_firstval - access the first value in the map. + * @map: map from jmap_new + * @index: set to the first index in the map. + * + * Returns NULL if the map is empty; otherwise this returns a pointer to + * the first value, which you must call jmap_putval() on! + * + * Example: + * // Add one to every value. + * for (val = jmap_firstval(map, &i); val; val = jmap_nextval(map, &i)) { + * (*val)++; + * jmap_putval(map, &val); + * } + * printf("\n"); + * + * See Also: + * jmap_first, jmap_nextval() + */ +static inline size_t *jmap_firstval(const struct jmap *map, size_t *index) +{ + size_t *val; + *index = 0; + val = (size_t *)JudyLFirst(map->judy, (Word_t *)index, + (JError_t *)&map->err); + jmap_debug_add_access(map, *index, val, "jmap_firstval"); + return val; +} + +/** + * jmap_nextval - access the next value in the map. + * @map: map from jmap_new + * @index: previous index, updated with the new index. + * + * This returns a pointer to a value (which you must call jmap_putval on) + * or NULL. This usually used to find an adjacent value after jmap_firstval. + * + * See Also: + * jmap_firstval(), jmap_putval() + */ +static inline size_t *jmap_nextval(const struct jmap *map, size_t *index) +{ + size_t *val; + val = (size_t *)JudyLNext(map->judy, (Word_t *)index, + (JError_t *)&map->err); + jmap_debug_add_access(map, *index, val, "jmap_nextval"); + return val; +} + +/** + * jmap_lastval - access the last value in the map. + * @map: map from jmap_new + * @index: set to the last index in the map. + * + * See Also: + * jmap_last(), jmap_putval() + */ +static inline size_t *jmap_lastval(const struct jmap *map, size_t *index) +{ + size_t *val; + *index = -1; + val = (size_t *)JudyLLast(map->judy, (Word_t *)index, + (JError_t *)&map->err); + jmap_debug_add_access(map, *index, val, "jmap_lastval"); + return val; +} + +/** + * jmap_prevval - access the previous value in the map. + * @map: map from jmap_new + * @index: previous index, updated with the new index. + * + * This returns a pointer to a value (which you must call jmap_putval on) + * or NULL. This usually used to find an adjacent value after jmap_lastval. + * + * See Also: + * jmap_lastval(), jmap_putval() + */ +static inline size_t *jmap_prevval(const struct jmap *map, size_t *index) +{ + size_t *val; + val = (size_t *)JudyLPrev(map->judy, (Word_t *)index, + (JError_t *)&map->err); + jmap_debug_add_access(map, *index, val, "jmap_prevval"); + return val; +} +#endif /* CCAN_JMAP_H */ diff --git a/ccan/jmap/jmap_type.h b/ccan/jmap/jmap_type.h new file mode 100644 index 00000000..dbbb97bf --- /dev/null +++ b/ccan/jmap/jmap_type.h @@ -0,0 +1,276 @@ +#ifndef CCAN_JMAP_TYPE_H +#define CCAN_JMAP_TYPE_H +#include + +/** + * JMAP_DEFINE_UINTIDX_TYPE - create a set of jmap ops for integer->ptr map + * @type: a type whose pointers will be values in the map. + * @name: a name for all the functions to define (of form jmap__*) + * + * It's easiest if NULL values aren't placed in the map: jmap_@name_get will + * return NULL if an index isn't valid. + * + * The following wrapper functions are defined; each one is the same as + * the jmap.h generic equivalent except where noted: + * + * struct jmap_@name *jmap_@name_new(void); + * void jmap_@name_free(const struct jmap_@name *map); + * const char *jmap_@name_error(struct jmap_@name *map); + * + * bool jmap_@name_add(const struct jmap_@name *map, + * size_t index, const type *value); + * bool jmap_@name_set(const struct jmap_@name *map, + * size_t index, const type *value); + * bool jmap_@name_del(struct jmap_@name *map, size_t index); + * bool jmap_@name_test(const struct jmap_@name *map, size_t index); + * + * type *jmap_@name_get(const struct jmap_@name *map, size_t index); + * size_t jmap_@name_popcount(const struct jmap_@name *map, + * size_t start, size_t end_incl); + * size_t jmap_@name_nth(const struct jmap_@name *map, + * size_t n, size_t invalid); + * size_t jmap_@name_first(const struct jmap_@name *map, + * size_t invalid); + * size_t jmap_@name_next(const struct jmap_@name *map, + * size_t prev, size_t invalid); + * size_t jmap_@name_last(const struct jmap_@name *map, + * size_t invalid); + * size_t jmap_@name_prev(const struct jmap_@name *map, + * size_t prev, size_t invalid); + * + * type **jmap_@name_getval(const struct jmap_@name *map, size_t index); + * void jmap_@name_putval(struct jmap_@name *map, type ***p); + * type **jmap_@name_nthval(struct jmap_@name *map, + * size_t n, size_t *index); + * type **jmap_@name_firstval(const struct jmap_@name *map, + * size_t *index); + * type **jmap_@name_nextval(const struct jmap_@name *map, size_t *index); + * type **jmap_@name_lastval(const struct jmap_@name *map, size_t *index); + * type **jmap_@name_prevval(const struct jmap_@name *map, size_t *index); + */ +#define JMAP_DEFINE_UINTIDX_TYPE(type, name) \ +struct jmap_##name; \ +static inline struct jmap_##name *jmap_##name##_new(void) \ +{ \ + return (struct jmap_##name *)jmap_new(); \ +} \ +static inline void jmap_##name##_free(const struct jmap_##name *map) \ +{ \ + jmap_free((const struct jmap *)map); \ +} \ +static inline const char *jmap_##name##_error(struct jmap_##name *map) \ +{ \ + return jmap_error((struct jmap *)map); \ +} \ +static inline bool jmap_##name##_add(struct jmap_##name *map, \ + size_t index, const type *value) \ +{ \ + return jmap_add((struct jmap *)map, index, (size_t)value); \ +} \ +static inline bool jmap_##name##_set(const struct jmap_##name *map, \ + size_t index, const type *value) \ +{ \ + return jmap_set((const struct jmap *)map, index, (size_t)value); \ +} \ +static inline bool jmap_##name##_del(struct jmap_##name *map, size_t index) \ +{ \ + return jmap_del((struct jmap *)map, index); \ +} \ +static inline bool jmap_##name##_test(const struct jmap_##name *map, \ + size_t index) \ +{ \ + return jmap_test((const struct jmap *)map, (size_t)index); \ +} \ +static inline type *jmap_##name##_get(const struct jmap_##name *map, \ + size_t index) \ +{ \ + return (type *)jmap_get((const struct jmap *)map, index, 0); \ +} \ +static inline size_t jmap_##name##_popcount(const struct jmap_##name *map, \ + size_t start, size_t end_incl) \ +{ \ + return jmap_popcount((const struct jmap *)map, start, end_incl); \ +} \ +static inline size_t jmap_##name##_nth(const struct jmap_##name *map, \ + size_t n, size_t invalid) \ +{ \ + return jmap_nth((const struct jmap *)map, n, invalid); \ +} \ +static inline size_t jmap_##name##_first(const struct jmap_##name *map, \ + size_t invalid) \ +{ \ + return jmap_first((const struct jmap *)map, invalid); \ +} \ +static inline size_t jmap_##name##_next(const struct jmap_##name *map, \ + size_t prev, size_t invalid) \ +{ \ + return jmap_next((const struct jmap *)map, prev, invalid); \ +} \ +static inline size_t jmap_##name##_last(const struct jmap_##name *map, \ + size_t invalid) \ +{ \ + return jmap_last((const struct jmap *)map, invalid); \ +} \ +static inline size_t jmap_##name##_prev(const struct jmap_##name *map, \ + size_t prev, size_t invalid) \ +{ \ + return jmap_prev((const struct jmap *)map, prev, invalid); \ +} \ +static inline type **jmap_##name##_getval(const struct jmap_##name *map, \ + size_t index) \ +{ \ + return (type **)jmap_getval((struct jmap *)map, index); \ +} \ +static inline void jmap_##name##_putval(struct jmap_##name *map, \ + type ***p) \ +{ \ + return jmap_putval((struct jmap *)map, (size_t **)p); \ +} \ +static inline type **jmap_##name##_nthval(struct jmap_##name *map, \ + size_t n, size_t *index) \ +{ \ + return (type **)jmap_nthval((struct jmap *)map, n, index); \ +} \ +static inline type **jmap_##name##_firstval(const struct jmap_##name *map, \ + size_t *index) \ +{ \ + return (type **)jmap_firstval((const struct jmap *)map, index); \ +} \ +static inline type **jmap_##name##_nextval(const struct jmap_##name *map, \ + size_t *index) \ +{ \ + return (type **)jmap_nextval((const struct jmap *)map, index); \ +} \ +static inline type **jmap_##name##_lastval(const struct jmap_##name *map, \ + size_t *index) \ +{ \ + return (type **)jmap_lastval((const struct jmap *)map, index); \ +} \ +static inline type **jmap_##name##_prevval(const struct jmap_##name *map, \ + size_t *index) \ +{ \ + return (type **)jmap_prevval((const struct jmap *)map, index); \ +} + +/** + * JMAP_DEFINE_PTRIDX_TYPE - create a map of jmap ops for ptr->ptr map + * @itype: a type whose pointers will index into the map. + * @type: a type whose pointers will be values in the map. + * @name: a name for all the functions to define (of form jmap__*) + * + * This macro defines a map of inline functions for typesafe and + * convenient usage of a pointer-indexed Judy map of pointers. It is + * assumed that a NULL pointer is never an index in the map, as + * various functions return NULL for "invalid index". Similarly, + * jmap_@name_get will return NULL if an index isn't valid, so NULL indices + * are not recommended (though you can tell using jmap_@name_test). + * + * Since the ordering is by index pointer value, it's generally quite useless. + * Thus we don't define order-specific functions, except first/next for + * traversal. + * + * The following wrapper functions are defined; each one is the same as + * the jmap.h generic equivalent: + * + * struct jmap_@name *jmap_@name_new(void); + * void jmap_@name_free(const struct jmap_@name *map); + * const char *jmap_@name_error(struct jmap_@name *map); + * + * bool jmap_@name_add(const struct jmap_@name *map, + * const itype *index, const type *value); + * bool jmap_@name_set(const struct jmap_@name *map, + * const itype *index, const type *value); + * bool jmap_@name_del(struct jmap_@name *map, const itype *index); + * bool jmap_@name_test(const struct jmap_@name *map, const itype *index); + * + * type *jmap_@name_get(const struct jmap_@name *map, const itype *index); + * itype *jmap_@name_count(const struct jmap_@name *map); + * itype *jmap_@name_first(const struct jmap_@name *map); + * itype *jmap_@name_next(const struct jmap_@name *map, + * const itype *prev); + * + * type **jmap_@name_getval(const struct jmap_@name *map, + * const itype *index); + * void jmap_@name_putval(struct jmap_@name *map, type ***p); + * type **jmap_@name_firstval(const struct jmap_@name *map, + * const itype **index); + * type **jmap_@name_nextval(const struct jmap_@name *map, + * const itype **index); + */ +#define JMAP_DEFINE_PTRIDX_TYPE(itype, type, name) \ +struct jmap_##name; \ +static inline struct jmap_##name *jmap_##name##_new(void) \ +{ \ + return (struct jmap_##name *)jmap_new(); \ +} \ +static inline void jmap_##name##_free(const struct jmap_##name *map) \ +{ \ + jmap_free((const struct jmap *)map); \ +} \ +static inline const char *jmap_##name##_error(struct jmap_##name *map) \ +{ \ + return jmap_error((struct jmap *)map); \ +} \ +static inline bool jmap_##name##_add(struct jmap_##name *map, \ + const itype *index, const type *value) \ +{ \ + return jmap_add((struct jmap *)map, (size_t)index, \ + (size_t)value); \ +} \ +static inline bool jmap_##name##_set(const struct jmap_##name *map, \ + const itype *index, const type *value) \ +{ \ + return jmap_set((const struct jmap *)map, (size_t)index, \ + (size_t)value); \ +} \ +static inline bool jmap_##name##_del(struct jmap_##name *map, \ + const itype *index) \ +{ \ + return jmap_del((struct jmap *)map, (size_t)index); \ +} \ +static inline bool jmap_##name##_test(const struct jmap_##name *map, \ + const itype *index) \ +{ \ + return jmap_test((const struct jmap *)map, (size_t)index); \ +} \ +static inline type *jmap_##name##_get(const struct jmap_##name *map, \ + const itype *index) \ +{ \ + return (type *)jmap_get((const struct jmap *)map, (size_t)index, 0); \ +} \ +static inline size_t jmap_##name##_count(const struct jmap_##name *map) \ +{ \ + return jmap_popcount((const struct jmap *)map, 0, -1); \ +} \ +static inline itype *jmap_##name##_first(const struct jmap_##name *map) \ +{ \ + return (itype *)jmap_first((const struct jmap *)map, 0); \ +} \ +static inline itype *jmap_##name##_next(const struct jmap_##name *map, \ + const itype *prev) \ +{ \ + return (itype *)jmap_next((const struct jmap *)map, (size_t)prev, 0); \ +} \ +static inline type **jmap_##name##_getval(const struct jmap_##name *map, \ + const itype *index) \ +{ \ + return (type **)jmap_getval((struct jmap *)map, (size_t)index); \ +} \ +static inline void jmap_##name##_putval(struct jmap_##name *map, \ + type ***p) \ +{ \ + return jmap_putval((struct jmap *)map, (size_t **)p); \ +} \ +static inline type **jmap_##name##_firstval(const struct jmap_##name *map, \ + itype **index) \ +{ \ + return (type **)jmap_firstval((const struct jmap *)map, \ + (size_t *)index); \ +} \ +static inline type **jmap_##name##_nextval(const struct jmap_##name *map, \ + itype **index) \ +{ \ + return (type **)jmap_nextval((const struct jmap *)map, \ + (size_t *)index); \ +} +#endif /* CCAN_JMAP_TYPE_H */ diff --git a/ccan/jmap/test/run-access-count.c b/ccan/jmap/test/run-access-count.c new file mode 100644 index 00000000..c31f24ec --- /dev/null +++ b/ccan/jmap/test/run-access-count.c @@ -0,0 +1,62 @@ +/* Test our access counting failures. */ +#include +#include +#include +#include +#include + +int main(int argc, char *argv[]) +{ + struct jmap *map; + size_t *value; + int status; + + plan_tests(9); + + map = jmap_new(); + ok1(jmap_error(map) == NULL); + ok1(jmap_add(map, 0, 1)); + + /* add while holding value. */ + value = jmap_getval(map, 0); + ok1(value); + if (!fork()) { + jmap_add(map, 1, 2); + exit(0); + } else { + wait(&status); + ok1(WIFSIGNALED(status) && WTERMSIG(status) == SIGABRT); + } + jmap_putval(map, &value); + + /* del while holding value. */ + value = jmap_getval(map, 0); + ok1(value); + if (!fork()) { + jmap_del(map, 0); + exit(0); + } else { + wait(&status); + ok1(WIFSIGNALED(status) && WTERMSIG(status) == SIGABRT); + } + jmap_putval(map, &value); + + ok1(jmap_add(map, 0, 1)); + + /* set while holding value ok. */ + value = jmap_getval(map, 0); + ok1(value); + if (!fork()) { + jmap_set(map, 0, 2); + exit(0); + } else { + wait(&status); + ok1(WIFEXITED(status) && WEXITSTATUS(status) == 0); + } + jmap_putval(map, &value); + + /* FIXME: test jmap_nthval, jmap_firstval etc. */ + jmap_free(map); + + return exit_status(); +} diff --git a/ccan/jmap/test/run-ptridx-type.c b/ccan/jmap/test/run-ptridx-type.c new file mode 100644 index 00000000..83642a8e --- /dev/null +++ b/ccan/jmap/test/run-ptridx-type.c @@ -0,0 +1,101 @@ +#include +#include +#include + +struct foo; +struct idx; + +JMAP_DEFINE_PTRIDX_TYPE(struct idx, struct foo, foo); + +#define NUM 100 + +static int cmp_ptr(const void *a, const void *b) +{ + return *(char **)a - *(char **)b; +} + +int main(int argc, char *argv[]) +{ + struct jmap_foo *map; + struct foo *foo[NUM], **foop; + struct idx *idx[NUM], *index; + + unsigned int i; + + plan_tests(25 + NUM*2 + 6); + for (i = 0; i < NUM; i++) + foo[i] = malloc(20); + + qsort(foo, NUM, sizeof(foo[0]), cmp_ptr); + + /* idx[i] == foo[i] + 1, for easy checking */ + for (i = 0; i < NUM; i++) + idx[i] = (void *)((char *)foo[i] + 1); + + map = jmap_foo_new(); + ok1(jmap_foo_error(map) == NULL); + + ok1(jmap_foo_test(map, idx[i]) == false); + ok1(jmap_foo_get(map, idx[i]) == (struct foo *)NULL); + ok1(jmap_foo_count(map) == 0); + ok1(jmap_foo_first(map) == (struct idx *)NULL); + ok1(jmap_foo_del(map, idx[0]) == false); + + /* Set only works on existing cases. */ + ok1(jmap_foo_set(map, idx[0], foo[0]) == false); + ok1(jmap_foo_add(map, idx[0], foo[1]) == true); + ok1(jmap_foo_get(map, idx[0]) == foo[1]); + ok1(jmap_foo_set(map, idx[0], foo[0]) == true); + ok1(jmap_foo_get(map, idx[0]) == foo[0]); + + ok1(jmap_foo_test(map, idx[0]) == true); + ok1(jmap_foo_count(map) == 1); + ok1(jmap_foo_first(map) == idx[0]); + ok1(jmap_foo_next(map, idx[0]) == NULL); + + ok1(jmap_foo_del(map, idx[0]) == true); + ok1(jmap_foo_test(map, idx[0]) == false); + ok1(jmap_foo_count(map) == 0); + + for (i = 0; i < NUM; i++) + jmap_foo_add(map, idx[i], foo[i]); + + ok1(jmap_foo_count(map) == NUM); + + ok1(jmap_foo_first(map) == idx[0]); + ok1(jmap_foo_next(map, idx[0]) == idx[1]); + ok1(jmap_foo_next(map, idx[NUM-1]) == NULL); + + ok1(jmap_foo_get(map, idx[0]) == foo[0]); + ok1(jmap_foo_get(map, idx[NUM-1]) == foo[NUM-1]); + ok1(jmap_foo_get(map, (void *)((char *)idx[NUM-1] + 1)) == NULL); + + /* Reverse values in map. */ + for (i = 0; i < NUM; i++) { + foop = jmap_foo_getval(map, idx[i]); + ok1(*foop == foo[i]); + *foop = foo[NUM-1-i]; + jmap_foo_putval(map, &foop); + } + for (i = 0; i < NUM; i++) + ok1(jmap_foo_get(map, idx[i]) == foo[NUM-1-i]); + + foop = jmap_foo_firstval(map, &index); + ok1(index == idx[0]); + ok1(*foop == foo[NUM-1]); + jmap_foo_putval(map, &foop); + + foop = jmap_foo_nextval(map, &index); + ok1(index == idx[1]); + ok1(*foop == foo[NUM-2]); + jmap_foo_putval(map, &foop); + + index = idx[NUM-1]; + foop = jmap_foo_nextval(map, &index); + ok1(foop == NULL); + + ok1(jmap_foo_error(map) == NULL); + jmap_foo_free(map); + + return exit_status(); +} diff --git a/ccan/jmap/test/run-uintidx-type.c b/ccan/jmap/test/run-uintidx-type.c new file mode 100644 index 00000000..1dcb8829 --- /dev/null +++ b/ccan/jmap/test/run-uintidx-type.c @@ -0,0 +1,130 @@ +#include +#include +#include + +struct foo; + +JMAP_DEFINE_UINTIDX_TYPE(struct foo, foo); + +#define NUM 100 + +int main(int argc, char *argv[]) +{ + struct jmap_foo *map; + struct foo *foo[NUM], **foop; + unsigned int i; + + plan_tests(37 + NUM*2 + 19); + for (i = 0; i < NUM; i++) + foo[i] = malloc(20); + + map = jmap_foo_new(); + ok1(jmap_foo_error(map) == NULL); + + ok1(jmap_foo_test(map, 0) == false); + ok1(jmap_foo_get(map, 0) == (struct foo *)NULL); + ok1(jmap_foo_popcount(map, 0, -1) == 0); + ok1(jmap_foo_first(map, 0) == 0); + ok1(jmap_foo_last(map, 0) == 0); + ok1(jmap_foo_del(map, 0) == false); + + /* Set only works on existing cases. */ + ok1(jmap_foo_set(map, 0, foo[0]) == false); + ok1(jmap_foo_add(map, 0, foo[1]) == true); + ok1(jmap_foo_get(map, 0) == foo[1]); + ok1(jmap_foo_set(map, 0, foo[0]) == true); + ok1(jmap_foo_get(map, 0) == foo[0]); + + ok1(jmap_foo_test(map, 0) == true); + ok1(jmap_foo_popcount(map, 0, -1) == 1); + ok1(jmap_foo_first(map, -1) == 0); + ok1(jmap_foo_last(map, -1) == 0); + ok1(jmap_foo_next(map, 0, -1) == (size_t)-1); + ok1(jmap_foo_prev(map, 0, -1) == (size_t)-1); + + ok1(jmap_foo_del(map, 0) == true); + ok1(jmap_foo_test(map, 0) == false); + ok1(jmap_foo_popcount(map, 0, -1) == 0); + + for (i = 0; i < NUM; i++) + jmap_foo_add(map, i, foo[i]); + + ok1(jmap_foo_popcount(map, 0, -1) == NUM); + ok1(jmap_foo_popcount(map, 0, NUM-1) == NUM); + ok1(jmap_foo_popcount(map, 0, NUM/2-1) == NUM/2); + ok1(jmap_foo_popcount(map, NUM/2, NUM) == NUM - NUM/2); + + ok1(jmap_foo_nth(map, 0, -1) == 0); + ok1(jmap_foo_nth(map, NUM-1, -1) == NUM-1); + ok1(jmap_foo_nth(map, NUM, -1) == (size_t)-1); + ok1(jmap_foo_first(map, -1) == 0); + ok1(jmap_foo_last(map, -1) == NUM-1); + ok1(jmap_foo_next(map, 0, -1) == 1); + ok1(jmap_foo_next(map, NUM-1, -1) == (size_t)-1); + ok1(jmap_foo_prev(map, 1, -1) == 0); + ok1(jmap_foo_prev(map, 0, -1) == (size_t)-1); + + ok1(jmap_foo_get(map, 0) == foo[0]); + ok1(jmap_foo_get(map, NUM-1) == foo[NUM-1]); + ok1(jmap_foo_get(map, NUM) == NULL); + + /* Reverse values in map. */ + for (i = 0; i < NUM; i++) { + foop = jmap_foo_getval(map, i); + ok1(*foop == foo[i]); + *foop = foo[NUM-1-i]; + jmap_foo_putval(map, &foop); + } + for (i = 0; i < NUM; i++) + ok1(jmap_foo_get(map, i) == foo[NUM-1-i]); + + foop = jmap_foo_nthval(map, 0, &i); + ok1(i == 0); + ok1(*foop == foo[NUM-1]); + jmap_foo_putval(map, &foop); + foop = jmap_foo_nthval(map, NUM-1, &i); + ok1(i == NUM-1); + ok1(*foop == foo[0]); + jmap_foo_putval(map, &foop); + + foop = jmap_foo_firstval(map, &i); + ok1(i == 0); + ok1(*foop == foo[NUM-1]); + jmap_foo_putval(map, &foop); + + foop = jmap_foo_nextval(map, &i); + ok1(i == 1); + ok1(*foop == foo[NUM-2]); + jmap_foo_putval(map, &foop); + + foop = jmap_foo_prevval(map, &i); + ok1(i == 0); + ok1(*foop == foo[NUM-1]); + jmap_foo_putval(map, &foop); + + foop = jmap_foo_prevval(map, &i); + ok1(foop == NULL); + + foop = jmap_foo_lastval(map, &i); + ok1(i == NUM-1); + ok1(*foop == foo[0]); + jmap_foo_putval(map, &foop); + + foop = jmap_foo_prevval(map, &i); + ok1(i == NUM-2); + ok1(*foop == foo[1]); + jmap_foo_putval(map, &foop); + + foop = jmap_foo_nextval(map, &i); + ok1(i == NUM-1); + ok1(*foop == foo[0]); + jmap_foo_putval(map, &foop); + + foop = jmap_foo_nextval(map, &i); + ok1(foop == NULL); + + ok1(jmap_foo_error(map) == NULL); + jmap_foo_free(map); + + return exit_status(); +} diff --git a/ccan/jmap/test/run.c b/ccan/jmap/test/run.c new file mode 100644 index 00000000..7f91489d --- /dev/null +++ b/ccan/jmap/test/run.c @@ -0,0 +1,113 @@ +#include +#define DEBUG +#include + +int main(int argc, char *argv[]) +{ + struct jmap *map; + size_t i, *value; + const char *err; + + plan_tests(53); + + map = jmap_new(); + ok1(jmap_error(map) == NULL); + + ok1(jmap_test(map, 0) == false); + ok1(jmap_del(map, 0) == false); + ok1(jmap_add(map, 0, 1) == true); + ok1(jmap_test(map, 0) == true); + ok1(jmap_get(map, 0, -1) == 1); + ok1(jmap_get(map, 1, -1) == (size_t)-1); + ok1(jmap_del(map, 0) == true); + + ok1(jmap_popcount(map, 0, -1) == 0); + ok1(jmap_nth(map, 0, 0) == 0); + ok1(jmap_nth(map, 0, -1) == (size_t)-1); + ok1(jmap_first(map, 0) == 0); + ok1(jmap_first(map, -1) == (size_t)-1); + ok1(jmap_last(map, 0) == 0); + ok1(jmap_last(map, -1) == (size_t)-1); + + ok1(jmap_getval(map, 0) == NULL); + + /* Map a million indices, 16 apart. */ + for (i = 0; i < 1000000; i++) + jmap_add(map, i << 4, (i << 5) + 1); + + /* This only take 6.3MB on my 32-bit system. */ + diag("%u bytes memory used\n", (unsigned)JudyLMemUsed(map->judy)); + + ok1(jmap_get(map, 0, -1) == 1); + ok1(jmap_get(map, 999999 << 4, -1) == (999999 << 5) + 1); + ok1(jmap_popcount(map, 0, -1) == 1000000); + ok1(jmap_nth(map, 0, -1) == 0); + ok1(jmap_nth(map, 999999, -1) == 999999 << 4); + ok1(jmap_nth(map, 1000000, -1) == (size_t)-1); + ok1(jmap_first(map, -1) == 0); + ok1(jmap_last(map, -1) == 999999 << 4); + ok1(jmap_next(map, 0, -1) == 1 << 4); + ok1(jmap_next(map, 999999 << 4, -1) == (size_t)-1); + ok1(jmap_prev(map, 1, -1) == 0); + ok1(jmap_prev(map, 0, -1) == (size_t)-1); + ok1(jmap_error(map) == NULL); + + /* Accessors. */ + value = jmap_getval(map, 0); + ok1(value && *value == 1); + *value = 2; + ok1(jmap_get(map, 0, -1) == 2); + jmap_putval(map, &value); + ok1(jmap_get(map, 0, -1) == 2); + ok1(jmap_set(map, 0, 1)); + + value = jmap_getval(map, 999999 << 4); + ok1(value && *value == (999999 << 5) + 1); + jmap_putval(map, &value); + + value = jmap_nthval(map, 0, &i); + ok1(i == 0); + ok1(value && *value == 1); + jmap_putval(map, &value); + value = jmap_nthval(map, 999999, &i); + ok1(i == 999999 << 4); + ok1(value && *value == (999999 << 5) + 1); + jmap_putval(map, &value); + ok1(jmap_nthval(map, 1000000, &i) == NULL); + + value = jmap_firstval(map, &i); + ok1(i == 0); + ok1(value && *value == 1); + jmap_putval(map, &value); + ok1(jmap_prevval(map, &i) == NULL); + + i = 0; + value = jmap_nextval(map, &i); + ok1(i == 1 << 4); + ok1(value && *value == (1 << 5) + 1); + jmap_putval(map, &value); + + value = jmap_lastval(map, &i); + ok1(i == 999999 << 4); + ok1(value && *value == (999999 << 5) + 1); + jmap_putval(map, &value); + ok1(jmap_nextval(map, &i) == NULL); + + i = 999999 << 4; + value = jmap_prevval(map, &i); + ok1(i == 999998 << 4); + ok1(value && *value == (999998 << 5) + 1); + jmap_putval(map, &value); + + /* Test error handling */ + JU_ERRNO(&map->err) = 100; + JU_ERRID(&map->err) = 991; + err = jmap_error(map); + ok1(err); + ok1(strstr(err, "100")); + ok1(strstr(err, "991")); + ok1(err == map->errstr); + jmap_free(map); + + return exit_status(); +}