Hashtable routines.
[ccan] / ccan / hashtable / test / run.c
1 #include <ccan/hashtable/hashtable.h>
2 #include <ccan/hashtable/hashtable.c>
3 #include <ccan/tap/tap.h>
4 #include <stdbool.h>
5 #include <string.h>
6
7 #define NUM_VALS (1 << HASHTABLE_BASE_BITS)
8
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)
13 {
14         unsigned long h = *(uint64_t *)elem / 2;
15         h |= -1UL << HASHTABLE_BASE_BITS;
16         return h;
17 }
18
19 static bool objcmp(const void *htelem, void *cmpdata)
20 {
21         return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
22 }
23
24 static void add_vals(struct hashtable *ht,
25                      const uint64_t val[], unsigned int num)
26 {
27         uint64_t i;
28
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);
32                         return;
33                 }
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);
37                         return;
38                 }
39         }
40         pass("Added %llu numbers to hash", (long long)i);
41 }
42
43 static void refill_vals(struct hashtable *ht,
44                         const uint64_t val[], unsigned int num)
45 {
46         uint64_t i;
47
48         for (i = 0; i < num; i++) {
49                 if (hashtable_find(ht, hash(&i, NULL), objcmp, &i))
50                         continue;
51                 hashtable_add(ht, hash(&val[i], NULL), &val[i]);
52         }
53 }
54
55 static void find_vals(struct hashtable *ht,
56                       const uint64_t val[], unsigned int num)
57 {
58         uint64_t i;
59
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);
63                         return;
64                 }
65         }
66         pass("Found %llu numbers in hash", (long long)i);
67 }
68
69 static void del_vals(struct hashtable *ht,
70                      const uint64_t val[], unsigned int num)
71 {
72         uint64_t i;
73
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);
77                         return;
78                 }
79         }
80         pass("Deleted %llu numbers in hash", (long long)i);
81 }
82
83 struct travarg {
84         unsigned int count;
85         struct hashtable *ht;
86         char touched[NUM_VALS];
87         uint64_t *val;
88 };
89
90 static bool count(void *p, void *cbarg)
91 {
92         struct travarg *travarg = cbarg;
93         travarg->count++;
94         travarg->touched[*(uint64_t *)p]++;
95         return false;
96 }
97
98 static bool delete_self(void *p, void *cbarg)
99 {
100         struct travarg *travarg = cbarg;
101         uint64_t val = *(uint64_t *)p;
102
103         travarg->count++;
104         travarg->touched[val]++;
105         return !hashtable_del(travarg->ht, hash(p, NULL), p);
106 }
107
108 static bool delete_next(void *p, void *cbarg)
109 {
110         struct travarg *travarg = cbarg;
111         uint64_t val = *(uint64_t *)p;
112         uint64_t *next = &travarg->val[(val + 1) % NUM_VALS];
113
114         travarg->count++;
115         travarg->touched[val]++;
116         return !hashtable_del(travarg->ht, hash(next, NULL), next);
117 }
118
119 static bool delete_prev(void *p, void *cbarg)
120 {
121         struct travarg *travarg = cbarg;
122         uint64_t val = *(uint64_t *)p;
123         uint64_t *prev = &travarg->val[(val - 1) % NUM_VALS];
124
125         travarg->count++;
126         travarg->touched[val]++;
127         return !hashtable_del(travarg->ht, hash(prev, NULL), prev);
128 }
129
130 static bool stop_halfway(void *p, void *cbarg)
131 {
132         struct travarg *travarg = cbarg;
133         travarg->count++;
134         travarg->touched[*(uint64_t *)p]++;
135
136         return (travarg->count == NUM_VALS / 2);
137 }
138
139 static void check_all_touched_once(struct travarg *travarg)
140 {
141         unsigned int i;
142
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]);
147                         return;
148                 }
149         }
150         pass("All values touched once");
151 }
152
153 static void check_only_touched_once(struct travarg *travarg)
154 {
155         unsigned int i;
156
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]);
161                         return;
162                 }
163         }
164         pass("No value touched twice");
165 }
166
167 int main(int argc, char *argv[])
168 {
169         unsigned int i;
170         struct hashtable *ht;
171         uint64_t val[NUM_VALS];
172         struct travarg travarg;
173         uint64_t dne;
174
175         plan_tests(20);
176         for (i = 0; i < NUM_VALS; i++)
177                 val[i] = i;
178         dne = i;
179
180         ht = hashtable_new(hash, NULL);
181         ok1(ht->max < (1 << ht->bits));
182         ok1(ht->bits == HASHTABLE_BASE_BITS);
183
184         /* We cannot find an entry which doesn't exist. */
185         ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
186
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));
191
192         /* Find all. */
193         find_vals(ht, val, NUM_VALS);
194         ok1(!hashtable_find(ht, hash(&dne, NULL), objcmp, &dne));
195
196         /* Delete all. */
197         del_vals(ht, val, NUM_VALS);
198         ok1(!hashtable_find(ht, hash(&val[0], NULL), objcmp, &val[0]));
199
200         /* Refill. */
201         refill_vals(ht, val, NUM_VALS);
202
203         /* Traverse tests. */
204         travarg.ht = ht;
205         travarg.val = val;
206         memset(travarg.touched, 0, sizeof(travarg.touched));
207         travarg.count = 0;
208
209         /* Traverse. */
210         hashtable_traverse(ht, count, &travarg);
211         ok1(travarg.count == NUM_VALS);
212         check_all_touched_once(&travarg);
213
214         memset(travarg.touched, 0, sizeof(travarg.touched));
215         travarg.count = 0;
216         hashtable_traverse(ht, stop_halfway, &travarg);
217         ok1(travarg.count == NUM_VALS / 2);
218         check_only_touched_once(&travarg);
219
220         memset(travarg.touched, 0, sizeof(travarg.touched));
221         travarg.count = 0;
222         i = 0;
223         /* Delete until we make no more progress. */
224         for (;;) {
225                 hashtable_traverse(ht, delete_self, &travarg);
226                 if (travarg.count == i || travarg.count > NUM_VALS)
227                         break;
228                 i = travarg.count;
229         }
230         ok1(travarg.count == NUM_VALS);
231         check_all_touched_once(&travarg);
232
233         memset(travarg.touched, 0, sizeof(travarg.touched));
234         travarg.count = 0;
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);
239
240         memset(travarg.touched, 0, sizeof(travarg.touched));
241         travarg.count = 0;
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);
246
247         return exit_status();
248 }