From: Rusty Russell Date: Tue, 27 Sep 2011 05:07:01 +0000 (+0930) Subject: htable: clean up interface, document htable_type better. X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=0c3590dc33d644f73bb8587db454c491830aaf26 htable: clean up interface, document htable_type better. We change from htable_new()/htable_free() to htable_init/htable_clear. We also change HTABLE_DEFINE_TYPE() to be the full name, without automatically prepending htable_. --- diff --git a/ccan/htable/_info b/ccan/htable/_info index ed9a8a5d..1553da2b 100644 --- a/ccan/htable/_info +++ b/ccan/htable/_info @@ -62,7 +62,7 @@ * * int main(int argc, char *argv[]) * { - * struct htable *ht; + * struct htable ht; * unsigned int i; * unsigned long val; * @@ -71,14 +71,14 @@ * argv[0]); * * // Create and populate hash table. - * ht = htable_new(rehash, NULL); + * htable_init(&ht, rehash, NULL); * for (i = 0; i < sizeof(map)/sizeof(map[0]); i++) - * htable_add(ht, hash_string(map[i].name), &map[i]); + * htable_add(&ht, hash_string(map[i].name), &map[i]); * * // Add any aliases to the hash table. * for (i = 1; i < argc; i++) { * if (!strncmp(argv[i], "--alias=", strlen("--alias="))) - * add_alias(ht, argv[i] + strlen("--alias=")); + * add_alias(&ht, argv[i] + strlen("--alias=")); * else * break; * } @@ -86,7 +86,7 @@ * // Find the other args in the hash table. * for (val = 0; i < argc; i++) { * struct name_to_digit *n; - * n = htable_get(ht, hash_string(argv[i]), + * n = htable_get(&ht, hash_string(argv[i]), * streq, argv[i]); * if (!n) * errx(1, "Invalid digit name %s", argv[i]); diff --git a/ccan/htable/htable.c b/ccan/htable/htable.c index ba5f0de5..f3e52921 100644 --- a/ccan/htable/htable.c +++ b/ccan/htable/htable.c @@ -1,7 +1,6 @@ /* Licensed under LGPLv2+ - see LICENSE file for details */ #include #include -#include #include #include #include @@ -10,17 +9,6 @@ /* We use 0x1 as deleted marker. */ #define HTABLE_DELETED (0x1) -struct htable { - size_t (*rehash)(const void *elem, void *priv); - void *priv; - unsigned int bits; - size_t elems, deleted, max, max_with_deleted; - /* These are the bits which are the same in all pointers. */ - uintptr_t common_mask, common_bits; - uintptr_t perfect_bit; - uintptr_t *table; -}; - /* We clear out the bits which are always the same, and put metadata there. */ static inline uintptr_t get_extra_ptr_bits(const struct htable *ht, uintptr_t e) @@ -54,33 +42,29 @@ static inline uintptr_t get_hash_ptr_bits(const struct htable *ht, & ht->common_mask & ~ht->perfect_bit; } -struct htable *htable_new(size_t (*rehash)(const void *elem, void *priv), - void *priv) +void htable_init(struct htable *ht, + size_t (*rehash)(const void *elem, void *priv), void *priv) { - struct htable *ht = malloc(sizeof(struct htable)); - if (ht) { - ht->bits = 0; - ht->rehash = rehash; - ht->priv = priv; - ht->elems = 0; - ht->deleted = 0; - ht->max = 0; - ht->max_with_deleted = 0; - /* This guarantees we enter update_common first add. */ - ht->common_mask = -1; - ht->common_bits = 0; - ht->perfect_bit = 0; - /* Dummy table until first insert. */ - ht->table = &ht->perfect_bit; - } - return ht; + ht->bits = 0; + ht->rehash = rehash; + ht->priv = priv; + ht->elems = 0; + ht->deleted = 0; + ht->max = 0; + ht->max_with_deleted = 0; + /* This guarantees we enter update_common first add. */ + ht->common_mask = -1; + ht->common_bits = 0; + ht->perfect_bit = 0; + /* Dummy table until first insert. */ + ht->table = &ht->perfect_bit; } -void htable_free(const struct htable *ht) +void htable_clear(struct htable *ht) { if (ht->table != &ht->perfect_bit) free((void *)ht->table); - free((void *)ht); + htable_init(ht, ht->rehash, ht->priv); } static size_t hash_bucket(const struct htable *ht, size_t h) diff --git a/ccan/htable/htable.h b/ccan/htable/htable.h index 73f4da84..b3962ac0 100644 --- a/ccan/htable/htable.h +++ b/ccan/htable/htable.h @@ -2,25 +2,43 @@ #ifndef CCAN_HTABLE_H #define CCAN_HTABLE_H #include "config.h" +#include #include #include -struct htable; +/** + * struct htable - private definition of a htable. + * + * It's exposed here so you can put it in your structures and so we can + * supply inline functions. + */ +struct htable { + size_t (*rehash)(const void *elem, void *priv); + void *priv; + unsigned int bits; + size_t elems, deleted, max, max_with_deleted; + /* These are the bits which are the same in all pointers. */ + uintptr_t common_mask, common_bits; + uintptr_t perfect_bit; + uintptr_t *table; +}; /** - * htable_new - allocate a hash tree. + * htable_init - initialize an empty hash tree. + * @ht: the hash table to initialize * @rehash: hash function to use for rehashing. * @priv: private argument to @rehash function. */ -struct htable *htable_new(size_t (*hash)(const void *elem, void *priv), - void *priv); +void htable_init(struct htable *ht, + size_t (*rehash)(const void *elem, void *priv), void *priv); /** - * htable_free - dellocate a hash tree. + * htable_clear - empty a hash tree. + * @ht: the hash table to clear * * This doesn't do anything to any pointers left in it. */ -void htable_free(const struct htable *); +void htable_clear(struct htable *ht); /** * htable_rehash - use a hashtree's rehash function diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h index af9da1b2..3b555cde 100644 --- a/ccan/htable/htable_type.h +++ b/ccan/htable/htable_type.h @@ -7,88 +7,90 @@ /** * HTABLE_DEFINE_TYPE - create a set of htable ops for a type * @type: a type whose pointers will be values in the hash. - * @keyof: a function/macro to extract a key from a @type element. - * @hashfn: a hash function for a @key - * @cmpfn: a comparison function for two keyof()s. - * @name: a name for all the functions to define (of form htable__*) + * @keyof: a function/macro to extract a key: @keyof(const type *elem) + * @hashfn: a hash function for a @key: size_t @hashfn(const *) + * @eqfn: an equality function keys: bool @eqfn(const type *, const *) + * @prefix: a prefix for all the functions to define (of form _*) * * NULL values may not be placed into the hash table. * - * The following wrapper functions are defined; each one is a - * simplified version of the htable.h equivalent: + * This defines the type hashtable type and an iterator type: + * struct ; + * struct _iter; * - * // Creating and freeing. - * struct htable_@name *htable_@name_new(void); - * void htable_@name_free(const struct htable_@name *ht); + * It also defines initialization and freeing functions: + * void _init(struct *); + * void _clear(struct *); * - * // Add, delete and find. - * bool htable_@name_add(struct htable_@name *ht, const type *e); - * bool htable_@name_del(struct htable_@name *ht, const type *e); - * bool htable_@name_delkey(struct htable_@name *ht, const ktype *k); - * type *htable_@name_get(const struct htable_@name *ht, const ktype *k); + * Add function only fails if we run out of memory: + * bool _add(struct *ht, const *e); * - * // Iteration. - * struct htable_@name_iter; - * type *htable_@name_first(const struct htable_@name *ht, - * struct htable_@name_iter *i); - * type *htable_@name_next(const struct htable_@name *ht, - * struct htable_@name_iter *i); + * Delete and delete-by key return true if it was in the set: + * bool _del(struct *ht, const *e); + * bool _delkey(struct *ht, const *k); + * + * Find function return the matching element, or NULL: + * type *_get(const struct @name *ht, const *k); + * + * Iteration over hashtable is also supported: + * type *_first(const struct *ht, struct _iter *i); + * type *_next(const struct *ht, struct _iter *i); + * + * It's currently safe to iterate over a changing hashtable, but you might + * miss an element. Iteration isn't very efficient, either. */ -#define HTABLE_DEFINE_TYPE(type, keyof, hashfn, cmpfn, name) \ -struct htable_##name; \ -struct htable_##name##_iter { struct htable_iter i; }; \ -static inline size_t htable_##name##_hash(const void *elem, void *priv) \ -{ \ - return hashfn(keyof((const type *)elem)); \ -} \ -static inline struct htable_##name *htable_##name##_new(void) \ -{ \ - return (struct htable_##name *)htable_new(htable_##name##_hash, \ - NULL); \ -} \ -static inline void htable_##name##_free(const struct htable_##name *ht) \ -{ \ - htable_free((const struct htable *)ht); \ -} \ -static inline bool htable_##name##_add(struct htable_##name *ht, \ - const type *elem) \ -{ \ - return htable_add((struct htable *)ht, hashfn(keyof(elem)), elem); \ -} \ -static inline bool htable_##name##_del(const struct htable_##name *ht, \ - const type *elem) \ -{ \ - return htable_del((struct htable *)ht, hashfn(keyof(elem)), elem); \ -} \ -static inline type *htable_##name##_get(const struct htable_##name *ht, \ - const HTABLE_KTYPE(keyof) k) \ -{ \ - /* Typecheck for cmpfn */ \ - (void)sizeof(cmpfn((const type *)NULL, \ - keyof((const type *)NULL))); \ - return (type *)htable_get((const struct htable *)ht, \ +#define HTABLE_DEFINE_TYPE(type, keyof, hashfn, eqfn, name) \ + struct name { struct htable raw; }; \ + struct name##_iter { struct htable_iter i; }; \ + static inline size_t name##_hash(const void *elem, void *priv) \ + { \ + return hashfn(keyof((const type *)elem)); \ + } \ + static inline void name##_init(struct name *ht) \ + { \ + htable_init(&ht->raw, name##_hash, NULL); \ + } \ + static inline void name##_clear(struct name *ht) \ + { \ + htable_clear(&ht->raw); \ + } \ + static inline bool name##_add(struct name *ht, const type *elem) \ + { \ + return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \ + } \ + static inline bool name##_del(struct name *ht, const type *elem) \ + { \ + return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \ + } \ + static inline type *name##_get(const struct name *ht, \ + const HTABLE_KTYPE(keyof) k) \ + { \ + /* Typecheck for eqfn */ \ + (void)sizeof(eqfn((const type *)NULL, \ + keyof((const type *)NULL))); \ + return htable_get(&ht->raw, \ hashfn(k), \ - (bool (*)(const void *, void *))(cmpfn), \ + (bool (*)(const void *, void *))(eqfn), \ k); \ -} \ -static inline bool htable_##name##_delkey(struct htable_##name *ht, \ - const HTABLE_KTYPE(keyof) k) \ -{ \ - type *elem = htable_##name##_get(ht, k); \ - if (elem) \ - return htable_##name##_del(ht, elem); \ - return false; \ -} \ -static inline type *htable_##name##_first(const struct htable_##name *ht, \ - struct htable_##name##_iter *iter) \ -{ \ - return htable_first((const struct htable *)ht, &iter->i); \ -} \ -static inline type *htable_##name##_next(const struct htable_##name *ht, \ - struct htable_##name##_iter *iter) \ -{ \ - return htable_next((const struct htable *)ht, &iter->i); \ -} + } \ + static inline bool name##_delkey(struct name *ht, \ + const HTABLE_KTYPE(keyof) k) \ + { \ + type *elem = name##_get(ht, k); \ + if (elem) \ + return name##_del(ht, elem); \ + return false; \ + } \ + static inline type *name##_first(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_first(&ht->raw, &iter->i); \ + } \ + static inline type *name##_next(const struct name *ht, \ + struct name##_iter *iter) \ + { \ + return htable_next(&ht->raw, &iter->i); \ + } #if HAVE_TYPEOF #define HTABLE_KTYPE(keyof) typeof(keyof(NULL)) diff --git a/ccan/htable/test/run-size.c b/ccan/htable/test/run-size.c index 01e4bb41..c92401c3 100644 --- a/ccan/htable/test/run-size.c +++ b/ccan/htable/test/run-size.c @@ -16,7 +16,7 @@ static size_t hash(const void *elem, void *unused) int main(int argc, char *argv[]) { - struct htable *ht; + struct htable ht; uint64_t val[NUM_VALS]; unsigned int i; @@ -24,13 +24,13 @@ int main(int argc, char *argv[]) for (i = 0; i < NUM_VALS; i++) val[i] = i; - ht = htable_new(hash, NULL); + htable_init(&ht, hash, NULL); for (i = 0; i < NUM_VALS; i++) { - ok1(ht->max >= i); - ok1(ht->max <= i * 2); - htable_add(ht, hash(&val[i], NULL), &val[i]); + ok1(ht.max >= i); + ok1(ht.max <= i * 2); + htable_add(&ht, hash(&val[i], NULL), &val[i]); } - htable_free(ht); + htable_clear(&ht); return exit_status(); } diff --git a/ccan/htable/test/run-type.c b/ccan/htable/test/run-type.c index aca9c594..f97e7270 100644 --- a/ccan/htable/test/run-type.c +++ b/ccan/htable/test/run-type.c @@ -33,7 +33,7 @@ static bool cmp(const struct obj *obj, const unsigned int *key) return obj->key == *key; } -HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, obj); +HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj); static void add_vals(struct htable_obj *ht, struct obj val[], unsigned int num) @@ -110,7 +110,7 @@ static bool check_mask(struct htable *ht, const struct obj val[], unsigned num) int main(int argc, char *argv[]) { unsigned int i; - struct htable_obj *ht; + struct htable_obj ht; struct obj val[NUM_VALS]; unsigned int dne; void *p; @@ -121,57 +121,55 @@ int main(int argc, char *argv[]) val[i].key = i; dne = i; - ht = htable_obj_new(); - ok1(((struct htable *)ht)->max == 0); - ok1(((struct htable *)ht)->bits == 0); + htable_obj_init(&ht); + ok1(ht.raw.max == 0); + ok1(ht.raw.bits == 0); /* We cannot find an entry which doesn't exist. */ - ok1(!htable_obj_get(ht, &dne)); + ok1(!htable_obj_get(&ht, &dne)); /* Fill it, it should increase in size. */ - add_vals(ht, val, NUM_VALS); - ok1(((struct htable *)ht)->bits == NUM_BITS + 1); - ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits)); + add_vals(&ht, val, NUM_VALS); + ok1(ht.raw.bits == NUM_BITS + 1); + ok1(ht.raw.max < (1 << ht.raw.bits)); /* Mask should be set. */ - ok1(((struct htable *)ht)->common_mask != 0); - ok1(((struct htable *)ht)->common_mask != -1); - ok1(check_mask((struct htable *)ht, val, NUM_VALS)); + ok1(ht.raw.common_mask != 0); + ok1(ht.raw.common_mask != -1); + ok1(check_mask(&ht.raw, val, NUM_VALS)); /* Find all. */ - find_vals(ht, val, NUM_VALS); - ok1(!htable_obj_get(ht, &dne)); + find_vals(&ht, val, NUM_VALS); + ok1(!htable_obj_get(&ht, &dne)); /* Walk once, should get them all. */ i = 0; - for (p = htable_obj_first(ht,&iter); p; p = htable_obj_next(ht, &iter)) + for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter)) i++; ok1(i == NUM_VALS); /* Delete all. */ - del_vals(ht, val, NUM_VALS); - ok1(!htable_obj_get(ht, &val[0].key)); + del_vals(&ht, val, NUM_VALS); + ok1(!htable_obj_get(&ht, &val[0].key)); /* Worst case, a "pointer" which doesn't have any matching bits. */ - htable_add((struct htable *)ht, 0, - (void *)~(uintptr_t)&val[NUM_VALS-1]); - htable_obj_add(ht, &val[NUM_VALS-1]); - ok1(((struct htable *)ht)->common_mask == 0); - ok1(((struct htable *)ht)->common_bits == 0); + htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); + htable_obj_add(&ht, &val[NUM_VALS-1]); + ok1(ht.raw.common_mask == 0); + ok1(ht.raw.common_bits == 0); /* Delete the bogus one before we trip over it. */ - htable_del((struct htable *)ht, 0, - (void *)~(uintptr_t)&val[NUM_VALS-1]); + htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); /* Add the rest. */ - add_vals(ht, val, NUM_VALS-1); + add_vals(&ht, val, NUM_VALS-1); /* Check we can find them all. */ - find_vals(ht, val, NUM_VALS); - ok1(!htable_obj_get(ht, &dne)); + find_vals(&ht, val, NUM_VALS); + ok1(!htable_obj_get(&ht, &dne)); /* Delete them all by key. */ - del_vals_bykey(ht, val, NUM_VALS); - htable_obj_free(ht); + del_vals_bykey(&ht, val, NUM_VALS); + htable_obj_clear(&ht); return exit_status(); } diff --git a/ccan/htable/test/run.c b/ccan/htable/test/run.c index 5e9d23ee..1a9e2de4 100644 --- a/ccan/htable/test/run.c +++ b/ccan/htable/test/run.c @@ -99,7 +99,7 @@ int main(int argc, char *argv[]) { unsigned int i; uintptr_t perfect_bit; - struct htable *ht; + struct htable ht; uint64_t val[NUM_VALS]; uint64_t dne; void *p; @@ -110,81 +110,79 @@ int main(int argc, char *argv[]) val[i] = i; dne = i; - ht = htable_new(hash, NULL); - ok1(ht->max == 0); - ok1(ht->bits == 0); + htable_init(&ht, hash, NULL); + ok1(ht.max == 0); + ok1(ht.bits == 0); /* We cannot find an entry which doesn't exist. */ - ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne)); + ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne)); /* This should increase it once. */ - add_vals(ht, val, 0, 1); - ok1(ht->bits == 1); - ok1(ht->max == 1); - ok1(ht->common_mask == -1); + add_vals(&ht, val, 0, 1); + ok1(ht.bits == 1); + ok1(ht.max == 1); + ok1(ht.common_mask == -1); /* Mask should be set. */ - ok1(check_mask(ht, val, 1)); + ok1(check_mask(&ht, val, 1)); /* This should increase it again. */ - add_vals(ht, val, 1, 1); - ok1(ht->bits == 2); - ok1(ht->max == 3); + add_vals(&ht, val, 1, 1); + ok1(ht.bits == 2); + ok1(ht.max == 3); /* Mask should be set. */ - ok1(ht->common_mask != 0); - ok1(ht->common_mask != -1); - ok1(check_mask(ht, val, 2)); + ok1(ht.common_mask != 0); + ok1(ht.common_mask != -1); + ok1(check_mask(&ht, val, 2)); /* Now do the rest. */ - add_vals(ht, val, 2, NUM_VALS - 2); + add_vals(&ht, val, 2, NUM_VALS - 2); /* Find all. */ - find_vals(ht, val, NUM_VALS); - ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne)); + find_vals(&ht, val, NUM_VALS); + ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne)); /* Walk once, should get them all. */ i = 0; - for (p = htable_first(ht,&iter); p; p = htable_next(ht, &iter)) + for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter)) i++; ok1(i == NUM_VALS); /* Delete all. */ - del_vals(ht, val, NUM_VALS); - ok1(!htable_get(ht, hash(&val[0], NULL), objcmp, &val[0])); + del_vals(&ht, val, NUM_VALS); + ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0])); /* Worst case, a "pointer" which doesn't have any matching bits. */ - htable_add(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); - htable_add(ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]); - ok1(ht->common_mask == 0); - ok1(ht->common_bits == 0); + htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); + htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]); + ok1(ht.common_mask == 0); + ok1(ht.common_bits == 0); /* Get rid of bogus pointer before we trip over it! */ - htable_del(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); + htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); /* Add the rest. */ - add_vals(ht, val, 0, NUM_VALS-1); + add_vals(&ht, val, 0, NUM_VALS-1); /* Check we can find them all. */ - find_vals(ht, val, NUM_VALS); - ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne)); - - htable_free(ht); + find_vals(&ht, val, NUM_VALS); + ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne)); /* Corner cases: wipe out the perfect bit using bogus pointer. */ - ht = htable_new(hash, NULL); - htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1])); - ok1(ht->perfect_bit); - perfect_bit = ht->perfect_bit; - htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] + htable_clear(&ht); + htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1])); + ok1(ht.perfect_bit); + perfect_bit = ht.perfect_bit; + htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit)); - ok1(ht->perfect_bit == 0); - htable_del(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit)); + ok1(ht.perfect_bit == 0); + htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit)); /* Enlarging should restore it... */ - add_vals(ht, val, 0, NUM_VALS-1); + add_vals(&ht, val, 0, NUM_VALS-1); - ok1(ht->perfect_bit != 0); - htable_free(ht); + ok1(ht.perfect_bit != 0); + htable_clear(&ht); return exit_status(); } diff --git a/ccan/htable/tools/speed.c b/ccan/htable/tools/speed.c index 194f1120..0b4e4344 100644 --- a/ccan/htable/tools/speed.c +++ b/ccan/htable/tools/speed.c @@ -34,7 +34,7 @@ static bool cmp(const struct object *object, const unsigned int *key) return object->key == *key; } -HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, obj); +HTABLE_DEFINE_TYPE(struct object, objkey, hash_obj, cmp, htable_obj); static unsigned int popcount(unsigned long val) { @@ -136,8 +136,7 @@ int main(int argc, char *argv[]) struct object *objs; size_t i, j, num, deleted; struct timeval start, stop; - struct htable_obj *ht; - struct htable *htr; + struct htable_obj ht; bool make_dumb = false; if (argv[1] && strcmp(argv[1], "--dumb") == 0) { @@ -152,32 +151,31 @@ int main(int argc, char *argv[]) objs[i].self = &objs[i]; } - ht = htable_obj_new(); - htr = (void *)ht; + htable_obj_init(&ht); printf("Initial insert: "); fflush(stdout); gettimeofday(&start, NULL); for (i = 0; i < num; i++) - htable_obj_add(ht, objs[i].self); + htable_obj_add(&ht, objs[i].self); gettimeofday(&stop, NULL); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Details: hash size %u, mask bits %u, perfect %.0f%%\n", - 1U << htr->bits, popcount(htr->common_mask), - perfect(htr) * 100.0 / htr->elems); + 1U << ht.raw.bits, popcount(ht.raw.common_mask), + perfect(&ht.raw) * 100.0 / ht.raw.elems); if (make_dumb) { /* Screw with mask, to hobble us. */ - update_common(htr, (void *)~htr->common_bits); + update_common(&ht.raw, (void *)~ht.raw.common_bits); printf("Details: DUMB MODE: mask bits %u\n", - popcount(htr->common_mask)); + popcount(ht.raw.common_mask)); } printf("Initial lookup (match): "); fflush(stdout); gettimeofday(&start, NULL); for (i = 0; i < num; i++) - if (htable_obj_get(ht, &i)->self != objs[i].self) + if (htable_obj_get(&ht, &i)->self != objs[i].self) abort(); gettimeofday(&stop, NULL); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -187,7 +185,7 @@ int main(int argc, char *argv[]) gettimeofday(&start, NULL); for (i = 0; i < num; i++) { unsigned int n = i + num; - if (htable_obj_get(ht, &n)) + if (htable_obj_get(&ht, &n)) abort(); } gettimeofday(&stop, NULL); @@ -198,7 +196,7 @@ int main(int argc, char *argv[]) fflush(stdout); gettimeofday(&start, NULL); for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) - if (htable_obj_get(ht, &j)->self != &objs[j]) + if (htable_obj_get(&ht, &j)->self != &objs[j]) abort(); gettimeofday(&stop, NULL); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -208,7 +206,7 @@ int main(int argc, char *argv[]) fflush(stdout); gettimeofday(&start, NULL); for (i = 0; i < num; i++) - if (!htable_obj_del(ht, objs[i].self)) + if (!htable_obj_del(&ht, objs[i].self)) abort(); gettimeofday(&stop, NULL); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -218,7 +216,7 @@ int main(int argc, char *argv[]) fflush(stdout); gettimeofday(&start, NULL); for (i = 0; i < num; i++) - htable_obj_add(ht, objs[i].self); + htable_obj_add(&ht, objs[i].self); gettimeofday(&stop, NULL); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -227,13 +225,13 @@ int main(int argc, char *argv[]) fflush(stdout); gettimeofday(&start, NULL); for (i = 0; i < num; i+=2) - if (!htable_obj_del(ht, objs[i].self)) + if (!htable_obj_del(&ht, objs[i].self)) abort(); gettimeofday(&stop, NULL); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Details: rehashes %zu, delete markers %zu\n", - hashcount, count_deleted(htr)); + hashcount, count_deleted(&ht.raw)); printf("Adding (a different) half: "); fflush(stdout); @@ -243,22 +241,22 @@ int main(int argc, char *argv[]) gettimeofday(&start, NULL); for (i = 0; i < num; i+=2) - htable_obj_add(ht, objs[i].self); + htable_obj_add(&ht, objs[i].self); gettimeofday(&stop, NULL); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Details: delete markers %zu, perfect %.0f%%\n", - count_deleted(htr), perfect(htr) * 100.0 / htr->elems); + count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems); printf("Lookup after half-change (match): "); fflush(stdout); gettimeofday(&start, NULL); for (i = 1; i < num; i+=2) - if (htable_obj_get(ht, &i)->self != objs[i].self) + if (htable_obj_get(&ht, &i)->self != objs[i].self) abort(); for (i = 0; i < num; i+=2) { unsigned int n = i + num; - if (htable_obj_get(ht, &n)->self != objs[i].self) + if (htable_obj_get(&ht, &n)->self != objs[i].self) abort(); } gettimeofday(&stop, NULL); @@ -269,7 +267,7 @@ int main(int argc, char *argv[]) gettimeofday(&start, NULL); for (i = 0; i < num; i++) { unsigned int n = i + num * 2; - if (htable_obj_get(ht, &n)) + if (htable_obj_get(&ht, &n)) abort(); } gettimeofday(&stop, NULL); @@ -291,10 +289,10 @@ int main(int argc, char *argv[]) } gettimeofday(&start, NULL); for (j = 0; j < num; j++) { - if (!htable_obj_del(ht, &objs[j])) + if (!htable_obj_del(&ht, &objs[j])) abort(); objs[j].key = num*i+j; - if (!htable_obj_add(ht, &objs[j])) + if (!htable_obj_add(&ht, &objs[j])) abort(); } gettimeofday(&stop, NULL); @@ -305,15 +303,15 @@ int main(int argc, char *argv[]) /* Spread out the keys more to try to make it harder. */ printf("Details: reinserting with spread\n"); for (i = 0; i < num; i++) { - if (!htable_obj_del(ht, objs[i].self)) + if (!htable_obj_del(&ht, objs[i].self)) abort(); objs[i].key = num * 5 + i * 9; - if (!htable_obj_add(ht, objs[i].self)) + if (!htable_obj_add(&ht, objs[i].self)) abort(); } printf("Details: delete markers %zu, perfect %.0f%%\n", - count_deleted(htr), perfect(htr) * 100.0 / htr->elems); - i = worst_run(htr, &deleted); + count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems); + i = worst_run(&ht.raw, &deleted); printf("Details: worst run %zu (%zu deleted)\n", i, deleted); printf("Lookup after churn & spread (match): "); @@ -321,7 +319,7 @@ int main(int argc, char *argv[]) gettimeofday(&start, NULL); for (i = 0; i < num; i++) { unsigned int n = num * 5 + i * 9; - if (htable_obj_get(ht, &n)->self != objs[i].self) + if (htable_obj_get(&ht, &n)->self != objs[i].self) abort(); } gettimeofday(&stop, NULL); @@ -332,7 +330,7 @@ int main(int argc, char *argv[]) gettimeofday(&start, NULL); for (i = 0; i < num; i++) { unsigned int n = num * (5 + 9) + i * 9; - if (htable_obj_get(ht, &n)) + if (htable_obj_get(&ht, &n)) abort(); } gettimeofday(&stop, NULL); @@ -343,7 +341,7 @@ int main(int argc, char *argv[]) gettimeofday(&start, NULL); for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) { unsigned int n = num * 5 + j * 9; - if (htable_obj_get(ht, &n)->self != &objs[j]) + if (htable_obj_get(&ht, &n)->self != &objs[j]) abort(); } gettimeofday(&stop, NULL); @@ -354,7 +352,7 @@ int main(int argc, char *argv[]) fflush(stdout); gettimeofday(&start, NULL); for (i = 0; i < num; i+=2) - if (!htable_obj_del(ht, objs[i].self)) + if (!htable_obj_del(&ht, objs[i].self)) abort(); gettimeofday(&stop, NULL); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -367,12 +365,12 @@ int main(int argc, char *argv[]) gettimeofday(&start, NULL); for (i = 0; i < num; i+=2) - htable_obj_add(ht, objs[i].self); + htable_obj_add(&ht, objs[i].self); gettimeofday(&stop, NULL); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Details: delete markers %zu, perfect %.0f%%\n", - count_deleted(htr), perfect(htr) * 100.0 / htr->elems); + count_deleted(&ht.raw), perfect(&ht.raw) * 100.0 / ht.raw.elems); return 0; } diff --git a/ccan/htable/tools/stringspeed.c b/ccan/htable/tools/stringspeed.c index 00ad2790..2bc1524e 100644 --- a/ccan/htable/tools/stringspeed.c +++ b/ccan/htable/tools/stringspeed.c @@ -31,7 +31,7 @@ static bool cmp(const char *obj, const char *key) return strcmp(obj, key) == 0; } -HTABLE_DEFINE_TYPE(char, strkey, hash_str, cmp, str); +HTABLE_DEFINE_TYPE(char, strkey, hash_str, cmp, htable_str); /* Nanoseconds per operation */ static size_t normalize(const struct timeval *start, @@ -51,13 +51,13 @@ int main(int argc, char *argv[]) { size_t i, j, num; struct timeval start, stop; - struct htable_str *ht; + struct htable_str ht; char **words, **misswords; words = strsplit(NULL, grab_file(NULL, argv[1] ? argv[1] : "/usr/share/dict/words", NULL), "\n"); - ht = htable_str_new(); + htable_str_init(&ht); num = talloc_array_length(words) - 1; printf("%zu words\n", num); @@ -77,19 +77,18 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0; i < num; i++) - htable_str_add(ht, words[i]); + htable_str_add(&ht, words[i]); stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); printf("Bytes allocated: %zu\n", - sizeof(((struct htable *)ht)->table[0]) - << ((struct htable *)ht)->bits); + sizeof(ht.raw.table[0]) << ht.raw.bits); printf("#02: Initial lookup (match): "); fflush(stdout); start = time_now(); for (i = 0; i < num; i++) - if (htable_str_get(ht, words[i]) != words[i]) + if (htable_str_get(&ht, words[i]) != words[i]) abort(); stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -98,7 +97,7 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0; i < num; i++) { - if (htable_str_get(ht, misswords[i])) + if (htable_str_get(&ht, misswords[i])) abort(); } stop = time_now(); @@ -109,7 +108,7 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) - if (htable_str_get(ht, words[j]) != words[j]) + if (htable_str_get(&ht, words[j]) != words[j]) abort(); stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -119,7 +118,7 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0; i < num; i++) - if (!htable_str_del(ht, words[i])) + if (!htable_str_del(&ht, words[i])) abort(); stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -128,7 +127,7 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0; i < num; i++) - htable_str_add(ht, words[i]); + htable_str_add(&ht, words[i]); stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -137,7 +136,7 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0; i < num; i+=2) - if (!htable_str_del(ht, words[i])) + if (!htable_str_del(&ht, words[i])) abort(); stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -147,7 +146,7 @@ int main(int argc, char *argv[]) start = time_now(); for (i = 0; i < num; i+=2) - htable_str_add(ht, misswords[i]); + htable_str_add(&ht, misswords[i]); stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -155,10 +154,10 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 1; i < num; i+=2) - if (htable_str_get(ht, words[i]) != words[i]) + if (htable_str_get(&ht, words[i]) != words[i]) abort(); for (i = 0; i < num; i+=2) { - if (htable_str_get(ht, misswords[i]) != misswords[i]) + if (htable_str_get(&ht, misswords[i]) != misswords[i]) abort(); } stop = time_now(); @@ -168,10 +167,10 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0; i < num; i+=2) - if (htable_str_get(ht, words[i])) + if (htable_str_get(&ht, words[i])) abort(); for (i = 1; i < num; i+=2) { - if (htable_str_get(ht, misswords[i])) + if (htable_str_get(&ht, misswords[i])) abort(); } stop = time_now(); @@ -182,9 +181,9 @@ int main(int argc, char *argv[]) printf("#11: Churn 1: "); start = time_now(); for (j = 0; j < num; j+=2) { - if (!htable_str_del(ht, misswords[j])) + if (!htable_str_del(&ht, misswords[j])) abort(); - if (!htable_str_add(ht, words[j])) + if (!htable_str_add(&ht, words[j])) abort(); } stop = time_now(); @@ -193,9 +192,9 @@ int main(int argc, char *argv[]) printf("#12: Churn 2: "); start = time_now(); for (j = 1; j < num; j+=2) { - if (!htable_str_del(ht, words[j])) + if (!htable_str_del(&ht, words[j])) abort(); - if (!htable_str_add(ht, misswords[j])) + if (!htable_str_add(&ht, misswords[j])) abort(); } stop = time_now(); @@ -204,9 +203,9 @@ int main(int argc, char *argv[]) printf("#13: Churn 3: "); start = time_now(); for (j = 1; j < num; j+=2) { - if (!htable_str_del(ht, misswords[j])) + if (!htable_str_del(&ht, misswords[j])) abort(); - if (!htable_str_add(ht, words[j])) + if (!htable_str_add(&ht, words[j])) abort(); } stop = time_now(); @@ -217,7 +216,7 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0; i < num; i++) - if (htable_str_get(ht, words[i]) != words[i]) + if (htable_str_get(&ht, words[i]) != words[i]) abort(); stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); @@ -226,7 +225,7 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0; i < num; i++) { - if (htable_str_get(ht, misswords[i])) + if (htable_str_get(&ht, misswords[i])) abort(); } stop = time_now(); @@ -237,7 +236,7 @@ int main(int argc, char *argv[]) fflush(stdout); start = time_now(); for (i = 0, j = 0; i < num; i++, j = (j + 10007) % num) - if (htable_str_get(ht, words[j]) != words[j]) + if (htable_str_get(&ht, words[j]) != words[j]) abort(); stop = time_now(); printf(" %zu ns\n", normalize(&start, &stop, num)); diff --git a/tools/ccanlint/file_analysis.c b/tools/ccanlint/file_analysis.c index a4282a96..63d22b8f 100644 --- a/tools/ccanlint/file_analysis.c +++ b/tools/ccanlint/file_analysis.c @@ -40,7 +40,8 @@ static bool dir_cmp(const struct manifest *m, const char *dir) return strcmp(m->dir, dir) == 0; } -HTABLE_DEFINE_TYPE(struct manifest, manifest_name, dir_hash, dir_cmp, manifest); +HTABLE_DEFINE_TYPE(struct manifest, manifest_name, dir_hash, dir_cmp, + htable_manifest); static struct htable_manifest *manifests; const char *get_ccan_file_contents(struct ccan_file *f) @@ -211,8 +212,10 @@ struct manifest *get_manifest(const void *ctx, const char *dir) unsigned int len; struct list_head *list; - if (!manifests) - manifests = htable_manifest_new(); + if (!manifests) { + manifests = talloc(NULL, struct htable_manifest); + htable_manifest_init(manifests); + } olddir = talloc_getcwd(NULL); if (!olddir) diff --git a/tools/ccanlint/tests/reduce_features.c b/tools/ccanlint/tests/reduce_features.c index 39a2bde0..de817d65 100644 --- a/tools/ccanlint/tests/reduce_features.c +++ b/tools/ccanlint/tests/reduce_features.c @@ -40,7 +40,20 @@ static bool option_cmp(const char *name1, const char *name2) return streq(name1, name2); } -HTABLE_DEFINE_TYPE(char, option_name, option_hash, option_cmp, option); +HTABLE_DEFINE_TYPE(char, option_name, option_hash, option_cmp, htable_option); + +static struct htable_option *htable_option_new(void) +{ + struct htable_option *opts = malloc(sizeof(*opts)); + htable_option_init(opts); + return opts; +} + +static void htable_option_free(struct htable_option *opts) +{ + htable_option_clear(opts); + free(opts); +} static unsigned int add_options(struct htable_option *opts, struct pp_conditions *cond)