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, struct travarg *travarg)
93 travarg->touched[*(uint64_t *)p]++;
97 static bool delete_self(uint64_t *p, struct travarg *travarg)
100 travarg->touched[*p]++;
101 return !hashtable_del(travarg->ht, hash(p, NULL), p);
104 static bool delete_next(uint64_t *p, struct travarg *travarg)
106 uint64_t *next = &travarg->val[((*p) + 1) % NUM_VALS];
109 travarg->touched[*p]++;
110 return !hashtable_del(travarg->ht, hash(next, NULL), next);
113 static bool delete_prev(uint64_t *p, struct travarg *travarg)
115 uint64_t *prev = &travarg->val[((*p) - 1) % NUM_VALS];
118 travarg->touched[*p]++;
119 return !hashtable_del(travarg->ht, hash(prev, NULL), prev);
122 static bool stop_halfway(void *p, struct travarg *travarg)
125 travarg->touched[*(uint64_t *)p]++;
127 return (travarg->count == NUM_VALS / 2);
130 static void check_all_touched_once(struct travarg *travarg)
134 for (i = 0; i < NUM_VALS; i++) {
135 if (travarg->touched[i] != 1) {
136 fail("Value %u touched %u times",
137 i, travarg->touched[i]);
141 pass("All values touched once");
144 static void check_only_touched_once(struct travarg *travarg)
148 for (i = 0; i < NUM_VALS; i++) {
149 if (travarg->touched[i] > 1) {
150 fail("Value %u touched multiple (%u) times",
151 i, travarg->touched[i]);
155 pass("No value touched twice");
158 int main(int argc, char *argv[])
161 struct hashtable *ht;
162 uint64_t val[NUM_VALS];
163 struct travarg travarg;
167 for (i = 0; i < NUM_VALS; i++)
171 ht = hashtable_new(hash, NULL);
172 ok1(ht->max < (1 << ht->bits));
173 ok1(ht->bits == HASHTABLE_BASE_BITS);
175 /* We cannot find an entry which doesn't exist. */
176 ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
178 /* Fill it, it should increase in size (once). */
179 add_vals(ht, val, NUM_VALS);
180 ok1(ht->bits == HASHTABLE_BASE_BITS + 1);
181 ok1(ht->max < (1 << ht->bits));
184 find_vals(ht, val, NUM_VALS);
185 ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
188 del_vals(ht, val, NUM_VALS);
189 ok1(!hashtable_find(ht, hash(&val[0], NULL), objcmp, &val[0]));
192 refill_vals(ht, val, NUM_VALS);
194 /* Traverse tests. */
197 memset(travarg.touched, 0, sizeof(travarg.touched));
201 hashtable_traverse(ht, void, count, &travarg);
202 ok1(travarg.count == NUM_VALS);
203 check_all_touched_once(&travarg);
205 memset(travarg.touched, 0, sizeof(travarg.touched));
207 hashtable_traverse(ht, void, stop_halfway, &travarg);
208 ok1(travarg.count == NUM_VALS / 2);
209 check_only_touched_once(&travarg);
211 memset(travarg.touched, 0, sizeof(travarg.touched));
214 /* Delete until we make no more progress. */
216 hashtable_traverse(ht, uint64_t, delete_self, &travarg);
217 if (travarg.count == i || travarg.count > NUM_VALS)
221 ok1(travarg.count == NUM_VALS);
222 check_all_touched_once(&travarg);
224 memset(travarg.touched, 0, sizeof(travarg.touched));
226 refill_vals(ht, val, NUM_VALS);
227 hashtable_traverse(ht, uint64_t, delete_next, &travarg);
228 ok1(travarg.count <= NUM_VALS);
229 check_only_touched_once(&travarg);
231 memset(travarg.touched, 0, sizeof(travarg.touched));
233 refill_vals(ht, val, NUM_VALS);
234 hashtable_traverse(ht, uint64_t, delete_prev, &travarg);
235 ok1(travarg.count <= NUM_VALS);
236 check_only_touched_once(&travarg);
238 return exit_status();