htable: add pre-sized option.
[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, 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(35);
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         /* Delete all. */
160         del_vals(&ht, val, NUM_VALS);
161         ok1(!htable_get(&ht, hash(&val[0], NULL), objcmp, &val[0]));
162
163         /* Worst case, a "pointer" which doesn't have any matching bits. */
164         htable_add(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
165         htable_add(&ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
166         ok1(ht.common_mask == 0);
167         ok1(ht.common_bits == 0);
168         /* Get rid of bogus pointer before we trip over it! */
169         htable_del(&ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
170
171         /* Add the rest. */
172         add_vals(&ht, val, 0, NUM_VALS-1);
173
174         /* Check we can find them all. */
175         find_vals(&ht, val, NUM_VALS);
176         ok1(!htable_get(&ht, hash(&dne, NULL), objcmp, &dne));
177
178         /* Corner cases: wipe out the perfect bit using bogus pointer. */
179         htable_clear(&ht);
180         htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
181         ok1(ht.perfect_bit);
182         perfect_bit = ht.perfect_bit;
183         htable_add(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
184                                    | perfect_bit));
185         ok1(ht.perfect_bit == 0);
186         htable_del(&ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
187
188         /* Enlarging should restore it... */
189         add_vals(&ht, val, 0, NUM_VALS-1);
190
191         ok1(ht.perfect_bit != 0);
192         htable_clear(&ht);
193
194         ok1(htable_init_sized(&ht, hash, NULL, 1024));
195         ok1(ht.max >= 1024);
196         htable_clear(&ht);
197
198         ok1(htable_init_sized(&ht, hash, NULL, 1023));
199         ok1(ht.max >= 1023);
200         htable_clear(&ht);
201
202         ok1(htable_init_sized(&ht, hash, NULL, 1025));
203         ok1(ht.max >= 1025);
204         htable_clear(&ht);
205         
206         return exit_status();
207 }