1 #define CCAN_HTABLE_DEBUG
2 #include <ccan/htable/htable.h>
3 #include <ccan/htable/htable.c>
4 #include <ccan/tap/tap.h>
9 #define NUM_VALS (1 << NUM_BITS)
11 static void *bad_pointer;
13 /* We use the number divided by two as the hash (for lots of
14 collisions), plus set all the higher bits so we can detect if they
15 don't get masked out. */
16 static size_t hash(const void *elem, void *unused UNNEEDED)
20 /* With CCAN_HTABLE_DEBUG enabled, it will try to hash each element,
21 * including this one... */
22 if (elem == bad_pointer)
25 h = *(uint64_t *)elem / 2;
26 h |= -1UL << NUM_BITS;
30 static bool objcmp(const void *htelem, void *cmpdata)
32 return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
35 static void add_vals(struct htable *ht,
37 unsigned int off, unsigned int num)
41 for (i = off; i < off+num; i++) {
42 if (htable_get(ht, hash(&i, NULL), objcmp, &i)) {
43 fail("%llu already in hash", (long long)i);
46 htable_add(ht, hash(&val[i], NULL), &val[i]);
47 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
48 fail("%llu not added to hash", (long long)i);
52 pass("Added %llu numbers to hash", (long long)i);
56 static void refill_vals(struct htable *ht,
57 const uint64_t val[], unsigned int num)
61 for (i = 0; i < num; i++) {
62 if (htable_get(ht, hash(&i, NULL), objcmp, &i))
64 htable_add(ht, hash(&val[i], NULL), &val[i]);
69 static void find_vals(struct htable *ht,
70 const uint64_t val[], unsigned int num)
74 for (i = 0; i < num; i++) {
75 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
76 fail("%llu not found in hash", (long long)i);
80 pass("Found %llu numbers in hash", (long long)i);
83 static void del_vals(struct htable *ht,
84 const uint64_t val[], unsigned int num)
88 for (i = 0; i < num; i++) {
89 if (!htable_del(ht, hash(&val[i], NULL), &val[i])) {
90 fail("%llu not deleted from hash", (long long)i);
94 pass("Deleted %llu numbers in hash", (long long)i);
97 static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
101 for (i = 0; i < num; i++) {
102 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
111 uintptr_t perfect_bit;
113 uint64_t val[NUM_VALS];
116 struct htable_iter iter;
119 for (i = 0; i < NUM_VALS; i++)
123 htable_init(&ht, hash, NULL);
124 ok1(ht_max(&ht) == 0);
127 /* We cannot find an entry which doesn't exist. */
128 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
130 /* This should increase it once. */
131 add_vals(&ht, val, 0, 1);
133 ok1(ht_max(&ht) == 1);
134 ok1(ht.common_mask == -1);
136 /* Mask should be set. */
137 ok1(check_mask(&ht, val, 1));
139 /* This should increase it again. */
140 add_vals(&ht, val, 1, 1);
142 ok1(ht_max(&ht) == 3);
144 /* Mask should be set. */
145 ok1(ht.common_mask != 0);
146 ok1(ht.common_mask != -1);
147 ok1(check_mask(&ht, val, 2));
149 /* Now do the rest. */
150 add_vals(&ht, val, 2, NUM_VALS - 2);
153 find_vals(&ht, val, NUM_VALS);
154 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
156 /* Walk once, should get them all. */
158 for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
163 for (p = htable_prev(&ht, &iter); p; p = htable_prev(&ht, &iter))
168 del_vals(&ht, val, NUM_VALS);
169 ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
171 /* Worst case, a "pointer" which doesn't have any matching bits. */
172 bad_pointer = (void *)~(uintptr_t)&val[NUM_VALS-1];
173 htable_add(&ht, 0, bad_pointer);
174 htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
175 ok1(ht.common_mask == 0);
176 ok1(ht.common_bits == 0);
177 /* Get rid of bogus pointer before we trip over it! */
178 htable_del(&ht, 0, bad_pointer);
181 add_vals(&ht, val, 0, NUM_VALS-1);
183 /* Check we can find them all. */
184 find_vals(&ht, val, NUM_VALS);
185 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
187 /* Corner cases: wipe out the perfect bit using bogus pointer. */
189 htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
190 ok1(ht_perfect_mask(&ht));
191 perfect_bit = ht_perfect_mask(&ht);
192 bad_pointer = (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit);
193 htable_add(&ht, 0, bad_pointer);
194 ok1(ht_perfect_mask(&ht) == 0);
195 htable_del(&ht, 0, bad_pointer);
197 /* Enlarging should restore it... */
198 add_vals(&ht, val, 0, NUM_VALS-1);
200 ok1(ht_perfect_mask(&ht) != 0);
203 ok1(htable_init_sized(&ht, hash, NULL, 1024));
204 ok1(ht_max(&ht) >= 1024);
207 ok1(htable_init_sized(&ht, hash, NULL, 1023));
208 ok1(ht_max(&ht) >= 1023);
211 ok1(htable_init_sized(&ht, hash, NULL, 1025));
212 ok1(ht_max(&ht) >= 1025);
215 return exit_status();