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)
110 unsigned int i, weight;
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);
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);
135 for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
136 if (ht.common_mask & ((uintptr_t)1 << i)) {
140 /* Only one bit should be clear. */
143 /* Mask should be set. */
144 ok1(check_mask(&ht, val, 1));
146 /* This should increase it again. */
147 add_vals(&ht, val, 1, 1);
151 /* Mask should be set. */
152 ok1(ht.common_mask != 0);
153 ok1(ht.common_mask != -1);
154 ok1(check_mask(&ht, val, 2));
156 /* Now do the rest. */
157 add_vals(&ht, val, 2, NUM_VALS - 2);
160 find_vals(&ht, val, NUM_VALS);
161 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
163 /* Walk once, should get them all. */
165 for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
170 for (p = htable_prev(&ht, &iter); p; p = htable_prev(&ht, &iter))
175 del_vals(&ht, val, NUM_VALS);
176 ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
178 /* Worst case, a "pointer" which doesn't have any matching bits. */
179 bad_pointer = (void *)~(uintptr_t)&val[NUM_VALS-1];
180 htable_add(&ht, 0, bad_pointer);
181 htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
182 ok1(ht.common_mask == 0);
183 ok1(ht.common_bits == 0);
184 /* Get rid of bogus pointer before we trip over it! */
185 htable_del(&ht, 0, bad_pointer);
188 add_vals(&ht, val, 0, NUM_VALS-1);
190 /* Check we can find them all. */
191 find_vals(&ht, val, NUM_VALS);
192 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
194 /* Corner cases: wipe out the perfect bit using bogus pointer. */
196 htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
198 perfect_bit = ht.perfect_bit;
199 bad_pointer = (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit);
200 htable_add(&ht, 0, bad_pointer);
201 ok1(ht.perfect_bit == 0);
202 htable_del(&ht, 0, bad_pointer);
204 /* Enlarging should restore it... */
205 add_vals(&ht, val, 0, NUM_VALS-1);
207 ok1(ht.perfect_bit != 0);
210 ok1(htable_init_sized(&ht, hash, NULL, 1024));
214 ok1(htable_init_sized(&ht, hash, NULL, 1023));
218 ok1(htable_init_sized(&ht, hash, NULL, 1025));
222 return exit_status();