Mark unused arguments in many modules.
[ccan] / ccan / htable / test / run.c
1 #include <ccan/htable/htable.h>
2 #include <ccan/htable/htable.c>
3 #include <ccan/tap/tap.h>
4 #include <stdbool.h>
5 #include <string.h>
6
7 #define NUM_BITS 7
8 #define NUM_VALS (1 << NUM_BITS)
9
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)
14 {
15         size_t h = *(uint64_t *)elem / 2;
16         h |= -1UL << NUM_BITS;
17         return h;
18 }
19
20 static bool objcmp(const void *htelem, void *cmpdata)
21 {
22         return *(uint64_t *)htelem == *(uint64_t *)cmpdata;
23 }
24
25 static void add_vals(struct htable *ht,
26                      const uint64_t val[],
27                      unsigned int off, unsigned int num)
28 {
29         uint64_t i;
30
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);
34                         return;
35                 }
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);
39                         return;
40                 }
41         }
42         pass("Added %llu numbers to hash", (long long)i);
43 }
44
45 #if 0
46 static void refill_vals(struct htable *ht,
47                         const uint64_t val[], unsigned int num)
48 {
49         uint64_t i;
50
51         for (i = 0; i < num; i++) {
52                 if (htable_get(ht, hash(&i, NULL), objcmp, &i))
53                         continue;
54                 htable_add(ht, hash(&val[i], NULL), &val[i]);
55         }
56 }
57 #endif
58
59 static void find_vals(struct htable *ht,
60                       const uint64_t val[], unsigned int num)
61 {
62         uint64_t i;
63
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);
67                         return;
68                 }
69         }
70         pass("Found %llu numbers in hash", (long long)i);
71 }
72
73 static void del_vals(struct htable *ht,
74                      const uint64_t val[], unsigned int num)
75 {
76         uint64_t i;
77
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);
81                         return;
82                 }
83         }
84         pass("Deleted %llu numbers in hash", (long long)i);
85 }
86
87 static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
88 {
89         uint64_t i;
90
91         for (i = 0; i < num; i++) {
92                 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
93                         return false;
94         }
95         return true;
96 }
97
98 int main(void)
99 {
100         unsigned int i, weight;
101         uintptr_t perfect_bit;
102         struct htable ht;
103         uint64_t val[NUM_VALS];
104         uint64_t dne;
105         void *p;
106         struct htable_iter iter;
107
108         plan_tests(36);
109         for (i = 0; i < NUM_VALS; i++)
110                 val[i] = i;
111         dne = i;
112
113         htable_init(&ht, hash, NULL);
114         ok1(ht.max == 0);
115         ok1(ht.bits == 0);
116
117         /* We cannot find an entry which doesn't exist. */
118         ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
119
120         /* This should increase it once. */
121         add_vals(&ht, val, 0, 1);
122         ok1(ht.bits == 1);
123         ok1(ht.max == 1);
124         weight = 0;
125         for (i = 0; i < sizeof(ht.common_mask) * CHAR_BIT; i++) {
126                 if (ht.common_mask & ((uintptr_t)1 << i)) {
127                         weight++;
128                 }
129         }
130         /* Only one bit should be clear. */
131         ok1(weight == i-1);
132
133         /* Mask should be set. */
134         ok1(check_mask(&ht, val, 1));
135
136         /* This should increase it again. */
137         add_vals(&ht, val, 1, 1);
138         ok1(ht.bits == 2);
139         ok1(ht.max == 3);
140
141         /* Mask should be set. */
142         ok1(ht.common_mask != 0);
143         ok1(ht.common_mask != -1);
144         ok1(check_mask(&ht, val, 2));
145
146         /* Now do the rest. */
147         add_vals(&ht, val, 2, NUM_VALS - 2);
148
149         /* Find all. */
150         find_vals(&ht, val, NUM_VALS);
151         ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
152
153         /* Walk once, should get them all. */
154         i = 0;
155         for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
156                 i++;
157         ok1(i == NUM_VALS);
158
159         i = 0;
160         for (p = htable_prev(&ht, &iter); p; p = htable_prev(&ht, &iter))
161                 i++;
162         ok1(i == NUM_VALS);
163
164         /* Delete all. */
165         del_vals(&ht, val, NUM_VALS);
166         ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
167
168         /* Worst case, a "pointer" which doesn't have any matching bits. */
169         htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
170         htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
171         ok1(ht.common_mask == 0);
172         ok1(ht.common_bits == 0);
173         /* Get rid of bogus pointer before we trip over it! */
174         htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
175
176         /* Add the rest. */
177         add_vals(&ht, val, 0, NUM_VALS-1);
178
179         /* Check we can find them all. */
180         find_vals(&ht, val, NUM_VALS);
181         ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
182
183         /* Corner cases: wipe out the perfect bit using bogus pointer. */
184         htable_clear(&ht);
185         htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
186         ok1(ht.perfect_bit);
187         perfect_bit = ht.perfect_bit;
188         htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
189                                    | perfect_bit));
190         ok1(ht.perfect_bit == 0);
191         htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
192
193         /* Enlarging should restore it... */
194         add_vals(&ht, val, 0, NUM_VALS-1);
195
196         ok1(ht.perfect_bit != 0);
197         htable_clear(&ht);
198
199         ok1(htable_init_sized(&ht, hash, NULL, 1024));
200         ok1(ht.max >= 1024);
201         htable_clear(&ht);
202
203         ok1(htable_init_sized(&ht, hash, NULL, 1023));
204         ok1(ht.max >= 1023);
205         htable_clear(&ht);
206
207         ok1(htable_init_sized(&ht, hash, NULL, 1025));
208         ok1(ht.max >= 1025);
209         htable_clear(&ht);
210         
211         return exit_status();
212 }