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[])
99 uintptr_t perfect_bit;
101 uint64_t val[NUM_VALS];
104 struct htable_iter iter;
107 for (i = 0; i < NUM_VALS; i++)
111 ht = htable_new(hash, NULL);
112 ok1(ht->max < (1 << ht->bits));
113 ok1(ht->bits == HTABLE_BASE_BITS);
115 /* We cannot find an entry which doesn't exist. */
116 ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
118 /* Fill it, it should increase in size (once). */
119 add_vals(ht, val, NUM_VALS);
120 ok1(ht->bits == HTABLE_BASE_BITS + 1);
121 ok1(ht->max < (1 << ht->bits));
123 /* Mask should be set. */
124 ok1(ht->common_mask != 0);
125 ok1(ht->common_mask != -1);
126 ok1(check_mask(ht, val, NUM_VALS));
129 find_vals(ht, val, NUM_VALS);
130 ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
132 /* Walk once, should get them all. */
134 for (p = htable_first(ht,&iter); p; p = htable_next(ht, &iter))
139 del_vals(ht, val, NUM_VALS);
140 ok1(!htable_get(ht, hash(&val[0], NULL), objcmp, &val[0]));
142 /* Worst case, a "pointer" which doesn't have any matching bits. */
143 htable_add(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
144 htable_add(ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
145 ok1(ht->common_mask == 0);
146 ok1(ht->common_bits == 0);
147 /* Get rid of bogus pointer before we trip over it! */
148 htable_del(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
151 add_vals(ht, val, NUM_VALS-1);
153 /* Check we can find them all. */
154 find_vals(ht, val, NUM_VALS);
155 ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
159 /* Corner cases: wipe out the perfect bit using bogus pointer. */
160 ht = htable_new(hash, NULL);
161 htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
162 ok1(ht->perfect_bit);
163 perfect_bit = ht->perfect_bit;
164 htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
166 ok1(ht->perfect_bit == 0);
167 htable_del(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
169 /* Enlarging should restore it... */
170 add_vals(ht, val, NUM_VALS-1);
172 ok1(ht->perfect_bit != 0);
175 return exit_status();