1 #include <ccan/htable/htable.h>
2 #include <ccan/htable/htable.c>
3 #include <ccan/tap/tap.h>
8 #define NUM_VALS (1 << NUM_BITS)
10 /* We use the number divided by two as the hash (for lots of
11 collisions), plus set all the higher bits so we can detect if they
12 don't get masked out. */
13 static size_t hash(const void *elem, void *unused)
15 size_t h = *(uint64_t *)elem / 2;
16 h |= -1UL << NUM_BITS;
20 static bool objcmp(const void *htelem, void *cmpdata)
22 return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
25 static void add_vals(struct htable *ht,
27 unsigned int off, unsigned int num)
31 for (i = off; i < off+num; i++) {
32 if (htable_get(ht, hash(&i, NULL), objcmp, &i)) {
33 fail("%llu already in hash", (long long)i);
36 htable_add(ht, hash(&val[i], NULL), &val[i]);
37 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
38 fail("%llu not added to hash", (long long)i);
42 pass("Added %llu numbers to hash", (long long)i);
46 static void refill_vals(struct htable *ht,
47 const uint64_t val[], unsigned int num)
51 for (i = 0; i < num; i++) {
52 if (htable_get(ht, hash(&i, NULL), objcmp, &i))
54 htable_add(ht, hash(&val[i], NULL), &val[i]);
59 static void find_vals(struct htable *ht,
60 const uint64_t val[], unsigned int num)
64 for (i = 0; i < num; i++) {
65 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
66 fail("%llu not found in hash", (long long)i);
70 pass("Found %llu numbers in hash", (long long)i);
73 static void del_vals(struct htable *ht,
74 const uint64_t val[], unsigned int num)
78 for (i = 0; i < num; i++) {
79 if (!htable_del(ht, hash(&val[i], NULL), &val[i])) {
80 fail("%llu not deleted from hash", (long long)i);
84 pass("Deleted %llu numbers in hash", (long long)i);
87 static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
91 for (i = 0; i < num; i++) {
92 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
98 int main(int argc, char *argv[])
100 unsigned int i, weight;
101 uintptr_t perfect_bit;
103 uint64_t val[NUM_VALS];
106 struct htable_iter iter;
109 for (i = 0; i < NUM_VALS; i++)
113 htable_init(&ht, hash, NULL);
117 /* We cannot find an entry which doesn't exist. */
118 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
120 /* This should increase it once. */
121 add_vals(&ht, val, 0, 1);
125 for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
126 if (ht.common_mask & ((uintptr_t)1 << i)) {
130 /* Only one bit should be clear. */
133 /* Mask should be set. */
134 ok1(check_mask(&ht, val, 1));
136 /* This should increase it again. */
137 add_vals(&ht, val, 1, 1);
141 /* Mask should be set. */
142 ok1(ht.common_mask != 0);
143 ok1(ht.common_mask != -1);
144 ok1(check_mask(&ht, val, 2));
146 /* Now do the rest. */
147 add_vals(&ht, val, 2, NUM_VALS - 2);
150 find_vals(&ht, val, NUM_VALS);
151 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
153 /* Walk once, should get them all. */
155 for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
160 del_vals(&ht, val, NUM_VALS);
161 ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
163 /* Worst case, a "pointer" which doesn't have any matching bits. */
164 htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
165 htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
166 ok1(ht.common_mask == 0);
167 ok1(ht.common_bits == 0);
168 /* Get rid of bogus pointer before we trip over it! */
169 htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
172 add_vals(&ht, val, 0, NUM_VALS-1);
174 /* Check we can find them all. */
175 find_vals(&ht, val, NUM_VALS);
176 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
178 /* Corner cases: wipe out the perfect bit using bogus pointer. */
180 htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
182 perfect_bit = ht.perfect_bit;
183 htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
185 ok1(ht.perfect_bit == 0);
186 htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
188 /* Enlarging should restore it... */
189 add_vals(&ht, val, 0, NUM_VALS-1);
191 ok1(ht.perfect_bit != 0);
194 ok1(htable_init_sized(&ht, hash, NULL, 1024));
198 ok1(htable_init_sized(&ht, hash, NULL, 1023));
202 ok1(htable_init_sized(&ht, hash, NULL, 1025));
206 return exit_status();