From: Rusty Russell Date: Mon, 6 Jun 2016 04:37:44 +0000 (+0930) Subject: htable: allow htable_type keys to be non-pointers. X-Git-Url: https://git.ozlabs.org/?p=ccan;a=commitdiff_plain;h=e0b86f0ca416d757684e6d98532e1fadf839b830 htable: allow htable_type keys to be non-pointers. Common case is mapping ints to structures. Signed-off-by: Rusty Russell --- diff --git a/ccan/htable/htable_type.h b/ccan/htable/htable_type.h index 9c20531f..14011676 100644 --- a/ccan/htable/htable_type.h +++ b/ccan/htable/htable_type.h @@ -90,13 +90,17 @@ static inline UNNEEDED type *name##_get(const struct name *ht, \ const HTABLE_KTYPE(keyof, type) 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 *))(eqfn), \ - 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, \ @@ -154,6 +158,9 @@ #if HAVE_TYPEOF #define HTABLE_KTYPE(keyof, type) typeof(keyof((const type *)NULL)) #else +/* Assumes keys are a pointer: if not, override. */ +#ifndef HTABLE_KTYPE #define HTABLE_KTYPE(keyof, type) void * #endif +#endif #endif /* CCAN_HTABLE_TYPE_H */ diff --git a/ccan/htable/test/run-type-int.c b/ccan/htable/test/run-type-int.c new file mode 100644 index 00000000..66346d0c --- /dev/null +++ b/ccan/htable/test/run-type-int.c @@ -0,0 +1,215 @@ +/* Key is an unsigned int, not a pointer. */ +#include "config.h" +#if !defined(HAVE_TYPEOF) || !HAVE_TYPEOF +#define HTABLE_KTYPE(keyof, type) unsigned int +#endif +#include +#include +#include +#include +#include + +#define NUM_BITS 7 +#define NUM_VALS (1 << NUM_BITS) + +struct obj { + /* Makes sure we don't try to treat and obj as a key or vice versa */ + unsigned char unused; + unsigned int key; +}; + +static const unsigned int objkey(const struct obj *obj) +{ + return obj->key; +} + +/* We use the number divided by two as the hash (for lots of + collisions), plus set all the higher bits so we can detect if they + don't get masked out. */ +static size_t objhash(const unsigned int key) +{ + size_t h = key / 2; + h |= -1UL << NUM_BITS; + return h; +} + +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); + +static void add_vals(struct htable_obj *ht, + struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (htable_obj_get(ht, i)) { + fail("%u already in hash", i); + return; + } + htable_obj_add(ht, &val[i]); + if (htable_obj_get(ht, i) != &val[i]) { + fail("%u not added to hash", i); + return; + } + } + pass("Added %u numbers to hash", i); +} + +static void find_vals(const struct htable_obj *ht, + const struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (htable_obj_get(ht, i) != &val[i]) { + fail("%u not found in hash", i); + return; + } + } + pass("Found %u numbers in hash", i); +} + +static void del_vals(struct htable_obj *ht, + const struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (!htable_obj_delkey(ht, val[i].key)) { + fail("%u not deleted from hash", i); + return; + } + } + pass("Deleted %u numbers in hash", i); +} + +static void del_vals_bykey(struct htable_obj *ht, + const struct obj val[], unsigned int num) +{ + unsigned int i; + + for (i = 0; i < num; i++) { + if (!htable_obj_delkey(ht, i)) { + fail("%u not deleted by key from hash", i); + return; + } + } + pass("Deleted %u numbers by key from hash", i); +} + +static bool check_mask(struct htable *ht, const struct obj val[], unsigned num) +{ + uint64_t i; + + for (i = 0; i < num; i++) { + if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits) + return false; + } + return true; +} + +int main(int argc, char *argv[]) +{ + unsigned int i; + struct htable_obj ht, ht2; + struct obj val[NUM_VALS], *result; + unsigned int dne; + void *p; + struct htable_obj_iter iter; + + plan_tests(29); + for (i = 0; i < NUM_VALS; i++) + val[i].key = i; + dne = i; + + 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)); + + /* Fill it, it should increase in size. */ + 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(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)); + + /* Walk once, should get them all. */ + i = 0; + for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter)) + i++; + ok1(i == NUM_VALS); + i = 0; + for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter)) + i++; + ok1(i == NUM_VALS); + + /* Delete all. */ + 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(&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(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]); + + /* Add the rest. */ + 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)); + + /* Check copy. */ + ok1(htable_obj_copy(&ht2, &ht)); + + /* Delete them all by key. */ + del_vals_bykey(&ht, val, NUM_VALS); + del_vals_bykey(&ht2, val, NUM_VALS); + + /* Write two of the same value. */ + val[1] = val[0]; + htable_obj_add(&ht, &val[0]); + htable_obj_add(&ht, &val[1]); + i = 0; + + result = htable_obj_getfirst(&ht, i, &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); + + /* 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); + } else { + ok1(htable_obj_getnext(&ht, i, &iter) == &val[0]); + ok1(htable_obj_getnext(&ht, i, &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); + } + + htable_obj_clear(&ht); + htable_obj_clear(&ht2); + return exit_status(); +}