diff options
Diffstat (limited to 'lib/ccan/htable/test/run-type.c')
-rw-r--r-- | lib/ccan/htable/test/run-type.c | 176 |
1 files changed, 176 insertions, 0 deletions
diff --git a/lib/ccan/htable/test/run-type.c b/lib/ccan/htable/test/run-type.c new file mode 100644 index 0000000000..02dac29e10 --- /dev/null +++ b/lib/ccan/htable/test/run-type.c @@ -0,0 +1,176 @@ +#include <ccan/htable/htable_type.h> +#include <ccan/htable/htable.c> +#include <ccan/tap/tap.h> +#include <stdbool.h> +#include <string.h> + +#define NUM_VALS (1 << HTABLE_BASE_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 << HTABLE_BASE_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, 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; + struct obj val[NUM_VALS]; + unsigned int dne; + void *p; + struct htable_obj_iter iter; + + plan_tests(20); + for (i = 0; i < NUM_VALS; i++) + val[i].key = i; + dne = i; + + ht = htable_obj_new(); + ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits)); + ok1(((struct htable *)ht)->bits == HTABLE_BASE_BITS); + + /* We cannot find an entry which doesn't exist. */ + ok1(!htable_obj_get(ht, &dne)); + + /* Fill it, it should increase in size (once). */ + add_vals(ht, val, NUM_VALS); + ok1(((struct htable *)ht)->bits == HTABLE_BASE_BITS + 1); + ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->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)); + + /* 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); + + /* 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((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); + /* Delete the bogus one before we trip over it. */ + htable_del((struct htable *)ht, 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)); + + /* Delete them all by key. */ + del_vals_bykey(ht, val, NUM_VALS); + htable_obj_free(ht); + + return exit_status(); +} |