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 UNNEEDED)
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 ok1(htable_count(ht) == 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)
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);
114 ok1(htable_count(&ht) == 0);
115 ok1(ht_max(&ht) == 0);
118 /* We cannot find an entry which doesn't exist. */
119 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
121 /* This should increase it once. */
122 add_vals(&ht, val, 0, 1);
124 ok1(ht_max(&ht) == 1);
126 for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
127 if (ht.common_mask & ((uintptr_t)1 << i)) {
131 /* Only one bit should be clear. */
134 /* Mask should be set. */
135 ok1(check_mask(&ht, val, 1));
137 /* This should increase it again. */
138 add_vals(&ht, val, 1, 1);
140 ok1(ht_max(&ht) == 3);
142 /* Mask should be set. */
143 ok1(ht.common_mask != 0);
144 ok1(ht.common_mask != -1);
145 ok1(check_mask(&ht, val, 2));
147 /* Now do the rest. */
148 add_vals(&ht, val, 2, NUM_VALS - 2);
151 find_vals(&ht, val, NUM_VALS);
152 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
154 /* Walk once, should get them all. */
156 for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
161 for (p = htable_prev(&ht, &iter); p; p = htable_prev(&ht, &iter))
166 del_vals(&ht, val, NUM_VALS);
167 ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
169 /* Worst case, a "pointer" which doesn't have any matching bits. */
170 htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
171 htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
172 ok1(ht.common_mask == 0);
173 ok1(ht.common_bits == 0);
174 /* Get rid of bogus pointer before we trip over it! */
175 htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
178 add_vals(&ht, val, 0, NUM_VALS-1);
180 /* Check we can find them all. */
181 find_vals(&ht, val, NUM_VALS);
182 ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
184 /* Corner cases: wipe out the perfect bit using bogus pointer. */
186 htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
187 ok1(ht_perfect_mask(&ht));
188 perfect_bit = ht_perfect_mask(&ht);
189 htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
191 ok1(ht_perfect_mask(&ht) == 0);
192 htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
194 /* Enlarging should restore it... */
195 add_vals(&ht, val, 0, NUM_VALS-1);
197 ok1(ht_perfect_mask(&ht) != 0);
200 ok1(htable_init_sized(&ht, hash, NULL, 1024));
201 ok1(ht_max(&ht) >= 1024);
204 ok1(htable_init_sized(&ht, hash, NULL, 1023));
205 ok1(ht_max(&ht) >= 1023);
208 ok1(htable_init_sized(&ht, hash, NULL, 1025));
209 ok1(ht_max(&ht) >= 1025);
212 ok1(htable_count(&ht) == 0);
214 return exit_status();