1 #include <ccan/hashtable/hashtable.h>
2 #include <ccan/hashtable/hashtable.c>
3 #include <ccan/tap/tap.h>
7 #define NUM_VALS (1 << HASHTABLE_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 unsigned long hash(const void *elem, void *unused)
14 unsigned long h = *(uint64_t *)elem / 2;
15 h |= -1UL << HASHTABLE_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 hashtable *ht,
25 const uint64_t val[], unsigned int num)
29 for (i = 0; i < num; i++) {
30 if (hashtable_find(ht, hash(&i, NULL), objcmp, &i)) {
31 fail("%llu already in hash", (long long)i);
34 hashtable_add(ht, hash(&val[i], NULL), &val[i]);
35 if (hashtable_find(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);
43 static void refill_vals(struct hashtable *ht,
44 const uint64_t val[], unsigned int num)
48 for (i = 0; i < num; i++) {
49 if (hashtable_find(ht, hash(&i, NULL), objcmp, &i))
51 hashtable_add(ht, hash(&val[i], NULL), &val[i]);
55 static void find_vals(struct hashtable *ht,
56 const uint64_t val[], unsigned int num)
60 for (i = 0; i < num; i++) {
61 if (hashtable_find(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
62 fail("%llu not found in hash", (long long)i);
66 pass("Found %llu numbers in hash", (long long)i);
69 static void del_vals(struct hashtable *ht,
70 const uint64_t val[], unsigned int num)
74 for (i = 0; i < num; i++) {
75 if (!hashtable_del(ht, hash(&val[i], NULL), &val[i])) {
76 fail("%llu not deleted from hash", (long long)i);
80 pass("Deleted %llu numbers in hash", (long long)i);
86 char touched[NUM_VALS];
90 static bool count(void *p, void *cbarg)
92 struct travarg *travarg = cbarg;
94 travarg->touched[*(uint64_t *)p]++;
98 static bool delete_self(void *p, void *cbarg)
100 struct travarg *travarg = cbarg;
101 uint64_t val = *(uint64_t *)p;
104 travarg->touched[val]++;
105 return !hashtable_del(travarg->ht, hash(p, NULL), p);
108 static bool delete_next(void *p, void *cbarg)
110 struct travarg *travarg = cbarg;
111 uint64_t val = *(uint64_t *)p;
112 uint64_t *next = &travarg->val[(val + 1) % NUM_VALS];
115 travarg->touched[val]++;
116 return !hashtable_del(travarg->ht, hash(next, NULL), next);
119 static bool delete_prev(void *p, void *cbarg)
121 struct travarg *travarg = cbarg;
122 uint64_t val = *(uint64_t *)p;
123 uint64_t *prev = &travarg->val[(val - 1) % NUM_VALS];
126 travarg->touched[val]++;
127 return !hashtable_del(travarg->ht, hash(prev, NULL), prev);
130 static bool stop_halfway(void *p, void *cbarg)
132 struct travarg *travarg = cbarg;
134 travarg->touched[*(uint64_t *)p]++;
136 return (travarg->count == NUM_VALS / 2);
139 static void check_all_touched_once(struct travarg *travarg)
143 for (i = 0; i < NUM_VALS; i++) {
144 if (travarg->touched[i] != 1) {
145 fail("Value %u touched %u times",
146 i, travarg->touched[i]);
150 pass("All values touched once");
153 static void check_only_touched_once(struct travarg *travarg)
157 for (i = 0; i < NUM_VALS; i++) {
158 if (travarg->touched[i] > 1) {
159 fail("Value %u touched multiple (%u) times",
160 i, travarg->touched[i]);
164 pass("No value touched twice");
167 int main(int argc, char *argv[])
170 struct hashtable *ht;
171 uint64_t val[NUM_VALS];
172 struct travarg travarg;
176 for (i = 0; i < NUM_VALS; i++)
180 ht = hashtable_new(hash, NULL);
181 ok1(ht->max < (1 << ht->bits));
182 ok1(ht->bits == HASHTABLE_BASE_BITS);
184 /* We cannot find an entry which doesn't exist. */
185 ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
187 /* Fill it, it should increase in size (once). */
188 add_vals(ht, val, NUM_VALS);
189 ok1(ht->bits == HASHTABLE_BASE_BITS + 1);
190 ok1(ht->max < (1 << ht->bits));
193 find_vals(ht, val, NUM_VALS);
194 ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
197 del_vals(ht, val, NUM_VALS);
198 ok1(!hashtable_find(ht, hash(&val[0], NULL), objcmp, &val[0]));
201 refill_vals(ht, val, NUM_VALS);
203 /* Traverse tests. */
206 memset(travarg.touched, 0, sizeof(travarg.touched));
210 hashtable_traverse(ht, count, &travarg);
211 ok1(travarg.count == NUM_VALS);
212 check_all_touched_once(&travarg);
214 memset(travarg.touched, 0, sizeof(travarg.touched));
216 hashtable_traverse(ht, stop_halfway, &travarg);
217 ok1(travarg.count == NUM_VALS / 2);
218 check_only_touched_once(&travarg);
220 memset(travarg.touched, 0, sizeof(travarg.touched));
223 /* Delete until we make no more progress. */
225 hashtable_traverse(ht, delete_self, &travarg);
226 if (travarg.count == i || travarg.count > NUM_VALS)
230 ok1(travarg.count == NUM_VALS);
231 check_all_touched_once(&travarg);
233 memset(travarg.touched, 0, sizeof(travarg.touched));
235 refill_vals(ht, val, NUM_VALS);
236 hashtable_traverse(ht, delete_next, &travarg);
237 ok1(travarg.count <= NUM_VALS);
238 check_only_touched_once(&travarg);
240 memset(travarg.touched, 0, sizeof(travarg.touched));
242 refill_vals(ht, val, NUM_VALS);
243 hashtable_traverse(ht, delete_prev, &travarg);
244 ok1(travarg.count <= NUM_VALS);
245 check_only_touched_once(&travarg);
247 return exit_status();