htable: clean up interface, document htable_type better.
[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)
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(int argc, char *argv[])
99 {
100         unsigned int i;
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(29);
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         ok1(ht.common_mask == -1);
125
126         /* Mask should be set. */
127         ok1(check_mask(&ht, val, 1));
128
129         /* This should increase it again. */
130         add_vals(&ht, val, 1, 1);
131         ok1(ht.bits == 2);
132         ok1(ht.max == 3);
133
134         /* Mask should be set. */
135         ok1(ht.common_mask != 0);
136         ok1(ht.common_mask != -1);
137         ok1(check_mask(&ht, val, 2));
138
139         /* Now do the rest. */
140         add_vals(&ht, val, 2, NUM_VALS - 2);
141
142         /* Find all. */
143         find_vals(&ht, val, NUM_VALS);
144         ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
145
146         /* Walk once, should get them all. */
147         i = 0;
148         for (p = htable_first(&ht,&iter); p; p = htable_next(&ht, &iter))
149                 i++;
150         ok1(i == NUM_VALS);
151
152         /* Delete all. */
153         del_vals(&ht, val, NUM_VALS);
154         ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
155
156         /* Worst case, a "pointer" which doesn't have any matching bits. */
157         htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
158         htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
159         ok1(ht.common_mask == 0);
160         ok1(ht.common_bits == 0);
161         /* Get rid of bogus pointer before we trip over it! */
162         htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
163
164         /* Add the rest. */
165         add_vals(&ht, val, 0, NUM_VALS-1);
166
167         /* Check we can find them all. */
168         find_vals(&ht, val, NUM_VALS);
169         ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
170
171         /* Corner cases: wipe out the perfect bit using bogus pointer. */
172         htable_clear(&ht);
173         htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
174         ok1(ht.perfect_bit);
175         perfect_bit = ht.perfect_bit;
176         htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
177                                    | perfect_bit));
178         ok1(ht.perfect_bit == 0);
179         htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
180
181         /* Enlarging should restore it... */
182         add_vals(&ht, val, 0, NUM_VALS-1);
183
184         ok1(ht.perfect_bit != 0);
185         htable_clear(&ht);
186
187         return exit_status();
188 }