From af04734dfb95fc2dbf78dc72011e71fda7c7c358 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 12 Aug 2024 15:04:00 +0930 Subject: [PATCH] htable: separate htable_type constructors to clarify duplicate keys. Most hash tables do not want duplicates, so specify this at declaration time. This way you crash should such a thing be inserted, not have some subtle behavior you didn't expect! Also disable the functions depending on the type. Signed-off-by: Rusty Russell --- ccan/failtest/failtest.c | 4 +- ccan/htable/htable_type.h | 132 +++++++++++++++---------- ccan/htable/test/run-type-int.c | 36 ++++--- ccan/htable/test/run-type.c | 40 +++++--- ccan/htable/tools/density.c | 2 +- ccan/htable/tools/speed.c | 2 +- ccan/htable/tools/stringspeed.c | 2 +- ccan/intmap/benchmark/speed.c | 2 +- ccan/likely/likely.c | 4 +- ccan/objset/objset.h | 2 +- tools/ccanlint/tests/reduce_features.c | 3 +- tools/manifest.c | 4 +- 12 files changed, 142 insertions(+), 91 deletions(-) diff --git a/ccan/failtest/failtest.c b/ccan/failtest/failtest.c index 205ded25..5494e172 100644 --- a/ccan/failtest/failtest.c +++ b/ccan/failtest/failtest.c @@ -79,8 +79,8 @@ static bool call_eq(const struct failtest_call *call1, } /* Defines struct failtable. */ -HTABLE_DEFINE_TYPE(struct failtest_call, (struct failtest_call *), hash_call, - call_eq, failtable); +HTABLE_DEFINE_NODUPS_TYPE(struct failtest_call, (struct failtest_call *), hash_call, + call_eq, failtable); bool (*failtest_exit_check)(struct tlist_calls *history); diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h index 0aacb7f3..103d2ff1 100644 --- a/ccan/htable/htable_type.h +++ b/ccan/htable/htable_type.h @@ -1,19 +1,23 @@ /* Licensed under LGPLv2+ - see LICENSE file for details */ #ifndef CCAN_HTABLE_TYPE_H #define CCAN_HTABLE_TYPE_H +#include "config.h" +#include #include #include -#include "config.h" /** - * HTABLE_DEFINE_TYPE - create a set of htable ops for a type + * HTABLE_DEFINE_NODUPS_TYPE/HTABLE_DEFINE_DUPS_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: @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. + * There are two variants, one of which allows duplicate keys, and one which + * does not. The defined functions differ in some cases, as shown below. + * + * NULL values may not be placed into the hash table (nor (void *)1). * * This defines the type hashtable type and an iterator type: * struct ; @@ -33,15 +37,18 @@ * * 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); + * bool _delkey(struct *ht, const *k) (NODUPS only); * * Delete by iterator: * bool _delval(struct *ht, struct _iter *i); * - * Find and return the (first) matching element, or NULL: - * type *_get(const struct @name *ht, const *k); + * Find and return the matching element, or NULL: + * type *_get(const struct @name *ht, const *k) (NODUPS only); * - * Find and return all matching elements, or NULL: + * Test for an element: + * bool _exists(const struct @name *ht, const *k); + * + * Find and return all matching elements, or NULL (DUPS only): * type *_getfirst(const struct @name *ht, const *k, * struct _iter *i); * type *_getnext(const struct @name *ht, const *k, @@ -59,7 +66,7 @@ * You can use HTABLE_INITIALIZER like so: * struct ht = { HTABLE_INITIALIZER(ht.raw, _hash, NULL) }; */ -#define HTABLE_DEFINE_TYPE(type, keyof, hashfn, eqfn, name) \ +#define HTABLE_DEFINE_TYPE_CORE(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) \ @@ -89,66 +96,33 @@ { \ return htable_copy(&dst->raw, &src->raw); \ } \ - static inline bool name##_add(struct name *ht, const type *elem) \ - { \ - return htable_add(&ht->raw, hashfn(keyof(elem)), elem); \ - } \ static inline UNNEEDED bool name##_del(struct name *ht, \ const type *elem) \ { \ return htable_del(&ht->raw, hashfn(keyof(elem)), elem); \ } \ - static inline UNNEEDED type *name##_get(const struct name *ht, \ - const HTABLE_KTYPE(keyof, type) k) \ - { \ - struct htable_iter i; \ - size_t h = hashfn(k); \ - void *c; \ - \ - for (c = htable_firstval(&ht->raw,&i,h); \ - c; \ - c = htable_nextval(&ht->raw,&i,h)) { \ - if (eqfn(c, k)) \ - return c; \ - } \ - return NULL; \ - } \ static inline UNNEEDED type *name##_getmatch_(const struct name *ht, \ const HTABLE_KTYPE(keyof, type) k, \ size_t h, \ type *v, \ - struct name##_iter *iter) \ + struct htable_iter *iter) \ { \ while (v) { \ if (eqfn(v, k)) \ break; \ - v = htable_nextval(&ht->raw, &iter->i, h); \ + v = htable_nextval(&ht->raw, iter, h); \ } \ return v; \ } \ - static inline UNNEEDED type *name##_getfirst(const struct name *ht, \ - const HTABLE_KTYPE(keyof, type) k, \ - struct name##_iter *iter) \ - { \ - size_t h = hashfn(k); \ - type *v = htable_firstval(&ht->raw, &iter->i, h); \ - return name##_getmatch_(ht, k, h, v, iter); \ - } \ - static inline UNNEEDED type *name##_getnext(const struct name *ht, \ - const HTABLE_KTYPE(keyof, type) k, \ - struct name##_iter *iter) \ + static inline UNNEEDED bool name##_exists(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ { \ + struct htable_iter i; \ size_t h = hashfn(k); \ - type *v = htable_nextval(&ht->raw, &iter->i, h); \ - return name##_getmatch_(ht, k, h, v, iter); \ - } \ - static inline UNNEEDED bool name##_delkey(struct name *ht, \ - const HTABLE_KTYPE(keyof, type) k) \ - { \ - type *elem = name##_get(ht, k); \ - if (elem) \ - return name##_del(ht, elem); \ - return false; \ + void *v; \ + \ + v = htable_firstval(&ht->raw, &i, h); \ + return name##_getmatch_(ht, k, h, v, &i) != NULL; \ } \ static inline UNNEEDED void name##_delval(struct name *ht, \ struct name##_iter *iter) \ @@ -177,6 +151,64 @@ return htable_prev(&ht->raw, &iter->i); \ } +#define HTABLE_DEFINE_NODUPS_TYPE(type, keyof, hashfn, eqfn, name) \ + HTABLE_DEFINE_TYPE_CORE(type, keyof, hashfn, eqfn, name) \ + static inline UNNEEDED type *name##_get(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ + { \ + struct htable_iter i; \ + size_t h = hashfn(k); \ + void *v; \ + \ + v = htable_firstval(&ht->raw, &i, h); \ + return name##_getmatch_(ht, k, h, v, &i); \ + } \ + static inline bool name##_add(struct name *ht, const type *elem) \ + { \ + /* Open-coded for slightly more efficiency */ \ + const HTABLE_KTYPE(keyof, type) k = keyof(elem); \ + struct htable_iter i; \ + size_t h = hashfn(k); \ + void *v; \ + \ + v = htable_firstval(&ht->raw, &i, h); \ + assert(!name##_getmatch_(ht, k, h, v, &i)); \ + return htable_add(&ht->raw, h, elem); \ + } \ + static inline UNNEEDED bool name##_delkey(struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k) \ + { \ + type *elem = name##_get(ht, k); \ + if (elem) \ + return name##_del(ht, elem); \ + return false; \ + } + +#define HTABLE_DEFINE_DUPS_TYPE(type, keyof, hashfn, eqfn, name) \ + HTABLE_DEFINE_TYPE_CORE(type, keyof, hashfn, eqfn, name) \ + static inline bool name##_add(struct name *ht, const type *elem) \ + { \ + const HTABLE_KTYPE(keyof, type) k = keyof(elem); \ + return htable_add(&ht->raw, hashfn(k), elem); \ + } \ + static inline UNNEEDED type *name##_getfirst(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + struct name##_iter *iter) \ + { \ + size_t h = hashfn(k); \ + type *v = htable_firstval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, &iter->i); \ + } \ + static inline UNNEEDED type *name##_getnext(const struct name *ht, \ + const HTABLE_KTYPE(keyof, type) k, \ + struct name##_iter *iter) \ + { \ + size_t h = hashfn(k); \ + type *v = htable_nextval(&ht->raw, &iter->i, h); \ + return name##_getmatch_(ht, k, h, v, &iter->i); \ + } + + #if HAVE_TYPEOF #define HTABLE_KTYPE(keyof, type) typeof(keyof((const type *)NULL)) #else diff --git a/ccan/htable/test/run-type-int.c b/ccan/htable/test/run-type-int.c index 16c4f56e..69142c7a 100644 --- a/ccan/htable/test/run-type-int.c +++ b/ccan/htable/test/run-type-int.c @@ -38,7 +38,7 @@ static bool cmp(const struct obj *obj, const unsigned int key) return obj->key == key; } -HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj); +HTABLE_DEFINE_NODUPS_TYPE(struct obj, objkey, objhash, cmp, htable_obj); static void add_vals(struct htable_obj *ht, struct obj val[], unsigned int num) @@ -112,14 +112,19 @@ static bool check_mask(struct htable *ht, const struct obj val[], unsigned num) return true; } +/* This variant allows duplicates! */ +HTABLE_DEFINE_DUPS_TYPE(struct obj, objkey, objhash, cmp, htable_obj_dups); + int main(void) { unsigned int i; struct htable_obj ht, ht2; + struct htable_obj_dups ht_dups; struct obj val[NUM_VALS], *result; unsigned int dne; void *p; struct htable_obj_iter iter; + struct htable_obj_dups_iter dups_iter; plan_tests(29); for (i = 0; i < NUM_VALS; i++) @@ -183,32 +188,35 @@ int main(void) del_vals_bykey(&ht, val, NUM_VALS); del_vals_bykey(&ht2, val, NUM_VALS); + /* Duplicates-allowed tests */ + htable_obj_dups_init(&ht_dups); /* Write two of the same value. */ val[1] = val[0]; - htable_obj_add(&ht, &val[0]); - htable_obj_add(&ht, &val[1]); + htable_obj_dups_add(&ht_dups, &val[0]); + htable_obj_dups_add(&ht_dups, &val[1]); i = 0; - result = htable_obj_getfirst(&ht, i, &iter); + result = htable_obj_dups_getfirst(&ht_dups, i, &dups_iter); ok1(result == &val[0] || result == &val[1]); if (result == &val[0]) { - ok1(htable_obj_getnext(&ht, i, &iter) == &val[1]); - ok1(htable_obj_getnext(&ht, i, &iter) == NULL); + ok1(htable_obj_dups_getnext(&ht_dups, i, &dups_iter) == &val[1]); + ok1(htable_obj_dups_getnext(&ht_dups, i, &dups_iter) == NULL); /* Deleting first should make us iterate over the other. */ - ok1(htable_obj_del(&ht, &val[0])); - ok1(htable_obj_getfirst(&ht, i, &iter) == &val[1]); - ok1(htable_obj_getnext(&ht, i, &iter) == NULL); + ok1(htable_obj_dups_del(&ht_dups, &val[0])); + ok1(htable_obj_dups_getfirst(&ht_dups, i, &dups_iter) == &val[1]); + ok1(htable_obj_dups_getnext(&ht_dups, i, &dups_iter) == NULL); } else { - ok1(htable_obj_getnext(&ht, i, &iter) == &val[0]); - ok1(htable_obj_getnext(&ht, i, &iter) == NULL); + ok1(htable_obj_dups_getnext(&ht_dups, i, &dups_iter) == &val[0]); + ok1(htable_obj_dups_getnext(&ht_dups, i, &dups_iter) == NULL); /* Deleting first should make us iterate over the other. */ - ok1(htable_obj_del(&ht, &val[1])); - ok1(htable_obj_getfirst(&ht, i, &iter) == &val[0]); - ok1(htable_obj_getnext(&ht, i, &iter) == NULL); + ok1(htable_obj_dups_del(&ht_dups, &val[1])); + ok1(htable_obj_dups_getfirst(&ht_dups, i, &dups_iter) == &val[0]); + ok1(htable_obj_dups_getnext(&ht_dups, i, &dups_iter) == NULL); } + htable_obj_dups_clear(&ht_dups); htable_obj_clear(&ht); htable_obj_clear(&ht2); return exit_status(); diff --git a/ccan/htable/test/run-type.c b/ccan/htable/test/run-type.c index c4201ed0..857bbbfb 100644 --- a/ccan/htable/test/run-type.c +++ b/ccan/htable/test/run-type.c @@ -33,7 +33,10 @@ static bool cmp(const struct obj *obj, const unsigned int *key) return obj->key == *key; } -HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj); +HTABLE_DEFINE_NODUPS_TYPE(struct obj, objkey, objhash, cmp, + htable_obj); +HTABLE_DEFINE_DUPS_TYPE(struct obj, objkey, objhash, cmp, + htable_obj_dups); static void add_vals(struct htable_obj *ht, struct obj val[], unsigned int num) @@ -111,12 +114,14 @@ int main(void) { unsigned int i; struct htable_obj ht, ht2; + struct htable_obj_dups ht_dups; struct obj val[NUM_VALS], *result; unsigned int dne; void *p; struct htable_obj_iter iter; + struct htable_obj_dups_iter dups_iter; - plan_tests(35); + plan_tests(36); for (i = 0; i < NUM_VALS; i++) val[i].key = i; dne = i; @@ -182,32 +187,37 @@ int main(void) del_vals_bykey(&ht, val, NUM_VALS); del_vals_bykey(&ht2, val, NUM_VALS); + /* Duplicates-allowed tests */ + htable_obj_dups_init(&ht_dups); + /* Write two of the same value. */ val[1] = val[0]; - htable_obj_add(&ht, &val[0]); - htable_obj_add(&ht, &val[1]); + htable_obj_dups_add(&ht_dups, &val[0]); + htable_obj_dups_add(&ht_dups, &val[1]); i = 0; - result = htable_obj_getfirst(&ht, &i, &iter); + result = htable_obj_dups_getfirst(&ht_dups, &i, &dups_iter); ok1(result == &val[0] || result == &val[1]); if (result == &val[0]) { - ok1(htable_obj_getnext(&ht, &i, &iter) == &val[1]); - ok1(htable_obj_getnext(&ht, &i, &iter) == NULL); + ok1(htable_obj_dups_getnext(&ht_dups, &i, &dups_iter) == &val[1]); + ok1(htable_obj_dups_getnext(&ht_dups, &i, &dups_iter) == NULL); /* Deleting first should make us iterate over the other. */ - ok1(htable_obj_del(&ht, &val[0])); - ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[1]); - ok1(htable_obj_getnext(&ht, &i, &iter) == NULL); + ok1(htable_obj_dups_del(&ht_dups, &val[0])); + ok1(htable_obj_dups_getfirst(&ht_dups, &i, &dups_iter) == &val[1]); + ok1(htable_obj_dups_getnext(&ht_dups, &i, &dups_iter) == NULL); } else { - ok1(htable_obj_getnext(&ht, &i, &iter) == &val[0]); - ok1(htable_obj_getnext(&ht, &i, &iter) == NULL); + ok1(htable_obj_dups_getnext(&ht_dups, &i, &dups_iter) == &val[0]); + ok1(htable_obj_dups_getnext(&ht_dups, &i, &dups_iter) == NULL); /* Deleting first should make us iterate over the other. */ - ok1(htable_obj_del(&ht, &val[1])); - ok1(htable_obj_getfirst(&ht, &i, &iter) == &val[0]); - ok1(htable_obj_getnext(&ht, &i, &iter) == NULL); + ok1(htable_obj_dups_del(&ht_dups, &val[1])); + ok1(htable_obj_dups_getfirst(&ht_dups, &i, &dups_iter) == &val[0]); + ok1(htable_obj_dups_getnext(&ht_dups, &i, &dups_iter) == NULL); } + htable_obj_dups_clear(&ht_dups); + ok1(htable_obj_dups_count(&ht_dups) == 0); htable_obj_clear(&ht); ok1(htable_obj_count(&ht) == 0); htable_obj_clear(&ht2); diff --git a/ccan/htable/tools/density.c b/ccan/htable/tools/density.c index 5f7400b9..df5afc51 100644 --- a/ccan/htable/tools/density.c +++ b/ccan/htable/tools/density.c @@ -26,7 +26,7 @@ static bool cmp(const ptrint_t *p, uintptr_t k) return key(p) == k; } -HTABLE_DEFINE_TYPE(ptrint_t, key, hash_uintptr, cmp, htable_ptrint); +HTABLE_DEFINE_NODUPS_TYPE(ptrint_t, key, hash_uintptr, cmp, htable_ptrint); /* Nanoseconds per operation */ static size_t normalize(const struct timeabs *start, diff --git a/ccan/htable/tools/speed.c b/ccan/htable/tools/speed.c index e185b6f6..a6198528 100644 --- a/ccan/htable/tools/speed.c +++ b/ccan/htable/tools/speed.c @@ -33,7 +33,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, htable_obj); +HTABLE_DEFINE_NODUPS_TYPE(struct object, objkey, hash_obj, cmp, htable_obj); static unsigned int popcount(unsigned long val) { diff --git a/ccan/htable/tools/stringspeed.c b/ccan/htable/tools/stringspeed.c index c6ca10f5..5f30359a 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, htable_str); +HTABLE_DEFINE_NODUPS_TYPE(char, strkey, hash_str, cmp, htable_str); /* Nanoseconds per operation */ static size_t normalize(const struct timeabs *start, diff --git a/ccan/intmap/benchmark/speed.c b/ccan/intmap/benchmark/speed.c index 16eb40f3..cf2dae7e 100644 --- a/ccan/intmap/benchmark/speed.c +++ b/ccan/intmap/benchmark/speed.c @@ -59,7 +59,7 @@ static bool eqfn(const struct htable_elem *elem, const uint64_t index) { return elem->index == index; } -HTABLE_DEFINE_TYPE(struct htable_elem, keyof, hashfn, eqfn, hash); +HTABLE_DEFINE_NODUPS_TYPE(struct htable_elem, keyof, hashfn, eqfn, hash); static bool check_val(intmap_index_t i, uint64_t *v, uint64_t *expected) { diff --git a/ccan/likely/likely.c b/ccan/likely/likely.c index 83e8d6fb..6b6e4aea 100644 --- a/ccan/likely/likely.c +++ b/ccan/likely/likely.c @@ -29,8 +29,8 @@ static bool trace_eq(const struct trace *t1, const struct trace *t2) } /* struct thash */ -HTABLE_DEFINE_TYPE(struct trace, (const struct trace *), hash_trace, trace_eq, - thash); +HTABLE_DEFINE_NODUPS_TYPE(struct trace, (const struct trace *), hash_trace, trace_eq, + thash); static struct thash htable = { HTABLE_INITIALIZER(htable.raw, thash_hash, NULL) }; diff --git a/ccan/objset/objset.h b/ccan/objset/objset.h index 03ec00f3..6464d913 100644 --- a/ccan/objset/objset.h +++ b/ccan/objset/objset.h @@ -20,7 +20,7 @@ static inline bool objset_eqfn_(const void *e1, const void *e2) { return e1 == e2; } -HTABLE_DEFINE_TYPE(void, objset_key_, objset_hashfn_, objset_eqfn_, objset_h); +HTABLE_DEFINE_NODUPS_TYPE(void, objset_key_, objset_hashfn_, objset_eqfn_, objset_h); /** * OBJSET_MEMBERS - declare members for a type-specific unordered objset. diff --git a/tools/ccanlint/tests/reduce_features.c b/tools/ccanlint/tests/reduce_features.c index 34a89706..89e61595 100644 --- a/tools/ccanlint/tests/reduce_features.c +++ b/tools/ccanlint/tests/reduce_features.c @@ -37,7 +37,8 @@ static bool option_cmp(const char *name1, const char *name2) return streq(name1, name2); } -HTABLE_DEFINE_TYPE(char, option_name, option_hash, option_cmp, htable_option); +HTABLE_DEFINE_NODUPS_TYPE(char, option_name, option_hash, option_cmp, + htable_option); static struct htable_option *htable_option_new(void) { diff --git a/tools/manifest.c b/tools/manifest.c index 82668acf..fcc2f15b 100644 --- a/tools/manifest.c +++ b/tools/manifest.c @@ -37,8 +37,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, - htable_manifest); +HTABLE_DEFINE_NODUPS_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) -- 2.39.5