htable: start empty.
[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         ht = htable_new(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         htable_free(ht);
172
173         /* Corner cases: wipe out the perfect bit using bogus pointer. */
174         ht = htable_new(hash, NULL);
175         htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]));
176         ok1(ht->perfect_bit);
177         perfect_bit = ht->perfect_bit;
178         htable_add(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1]
179                                    | perfect_bit));
180         ok1(ht->perfect_bit == 0);
181         htable_del(ht, 0, (void *)((uintptr_t)&val[NUM_VALS-1] | perfect_bit));
182
183         /* Enlarging should restore it... */
184         add_vals(ht, val, 0, NUM_VALS-1);
185
186         ok1(ht->perfect_bit != 0);
187         htable_free(ht);
188
189         return exit_status();
190 }