1 #include <ccan/htable/htable.h>
2 #include <ccan/htable/htable.c>
3 #include <ccan/tap/tap.h>
7 #define NUM_VALS (1 << HTABLE_BASE_BITS)
9 /* We use the number divided by two as the hash (for lots of
10 collisions), plus set all the higher bits so we can detect if they
11 don't get masked out. */
12 static size_t hash(const void *elem, void *unused)
14 size_t h = *(uint64_t *)elem / 2;
15 h |= -1UL << HTABLE_BASE_BITS;
19 static bool objcmp(const void *htelem, void *cmpdata)
21 return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
24 static void add_vals(struct htable *ht,
25 const uint64_t val[], unsigned int num)
29 for (i = 0; i < num; i++) {
30 if (htable_get(ht, hash(&i, NULL), objcmp, &i)) {
31 fail("%llu already in hash", (long long)i);
34 htable_add(ht, hash(&val[i], NULL), &val[i]);
35 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
36 fail("%llu not added to hash", (long long)i);
40 pass("Added %llu numbers to hash", (long long)i);
44 static void refill_vals(struct htable *ht,
45 const uint64_t val[], unsigned int num)
49 for (i = 0; i < num; i++) {
50 if (htable_get(ht, hash(&i, NULL), objcmp, &i))
52 htable_add(ht, hash(&val[i], NULL), &val[i]);
57 static void find_vals(struct htable *ht,
58 const uint64_t val[], unsigned int num)
62 for (i = 0; i < num; i++) {
63 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
64 fail("%llu not found in hash", (long long)i);
68 pass("Found %llu numbers in hash", (long long)i);
71 static void del_vals(struct htable *ht,
72 const uint64_t val[], unsigned int num)
76 for (i = 0; i < num; i++) {
77 if (!htable_del(ht, hash(&val[i], NULL), &val[i])) {
78 fail("%llu not deleted from hash", (long long)i);
82 pass("Deleted %llu numbers in hash", (long long)i);
85 static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
89 for (i = 0; i < num; i++) {
90 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
96 int main(int argc, char *argv[])
100 uint64_t val[NUM_VALS];
103 struct htable_iter iter;
106 for (i = 0; i < NUM_VALS; i++)
110 ht = htable_new(hash, NULL);
111 ok1(ht->max < (1 << ht->bits));
112 ok1(ht->bits == HTABLE_BASE_BITS);
114 /* We cannot find an entry which doesn't exist. */
115 ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
117 /* Fill it, it should increase in size (once). */
118 add_vals(ht, val, NUM_VALS);
119 ok1(ht->bits == HTABLE_BASE_BITS + 1);
120 ok1(ht->max < (1 << ht->bits));
122 /* Mask should be set. */
123 ok1(ht->common_mask != 0);
124 ok1(ht->common_mask != -1);
125 ok1(check_mask(ht, val, NUM_VALS));
128 find_vals(ht, val, NUM_VALS);
129 ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
131 /* Walk once, should get them all. */
133 for (p = htable_first(ht,&iter); p; p = htable_next(ht, &iter))
138 del_vals(ht, val, NUM_VALS);
139 ok1(!htable_get(ht, hash(&val[0], NULL), objcmp, &val[0]));
141 /* Worst case, a "pointer" which doesn't have any matching bits. */
142 htable_add(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
143 htable_add(ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
144 ok1(ht->common_mask == 0);
145 ok1(ht->common_bits == 0);
148 add_vals(ht, val, NUM_VALS-1);
150 /* Check we can find them all. */
151 find_vals(ht, val, NUM_VALS);
152 ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
154 return exit_status();