htable: first implementation
[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_VALS (1 << HTABLE_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 size_t hash(const void *elem, void *unused)
13 {
14         size_t h = *(uint64_t *)elem / 2;
15         h |= -1UL << HTABLE_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 htable *ht,
25                      const uint64_t val[], unsigned int num)
26 {
27         uint64_t i;
28
29         for (i = 0; i < num; i++) {
30                 if (htable_get(ht, hash(&i, NULL), objcmp, &i)) {
31                         fail("%llu already in hash", (long long)i);
32                         return;
33                 }
34                 htable_add(ht, hash(&val[i], NULL), &val[i]);
35                 if (htable_get(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 #if 0
44 static void refill_vals(struct htable *ht,
45                         const uint64_t val[], unsigned int num)
46 {
47         uint64_t i;
48
49         for (i = 0; i < num; i++) {
50                 if (htable_get(ht, hash(&i, NULL), objcmp, &i))
51                         continue;
52                 htable_add(ht, hash(&val[i], NULL), &val[i]);
53         }
54 }
55 #endif
56
57 static void find_vals(struct htable *ht,
58                       const uint64_t val[], unsigned int num)
59 {
60         uint64_t i;
61
62         for (i = 0; i < num; i++) {
63                 if (htable_get(ht, hash(&i, NULL), objcmp, &i) != &val[i]) {
64                         fail("%llu not found in hash", (long long)i);
65                         return;
66                 }
67         }
68         pass("Found %llu numbers in hash", (long long)i);
69 }
70
71 static void del_vals(struct htable *ht,
72                      const uint64_t val[], unsigned int num)
73 {
74         uint64_t i;
75
76         for (i = 0; i < num; i++) {
77                 if (!htable_del(ht, hash(&val[i], NULL), &val[i])) {
78                         fail("%llu not deleted from hash", (long long)i);
79                         return;
80                 }
81         }
82         pass("Deleted %llu numbers in hash", (long long)i);
83 }
84
85 static bool check_mask(struct htable *ht, uint64_t val[], unsigned num)
86 {
87         uint64_t i;
88
89         for (i = 0; i < num; i++) {
90                 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
91                         return false;
92         }
93         return true;
94 }
95
96 int main(int argc, char *argv[])
97 {
98         unsigned int i;
99         struct htable *ht;
100         uint64_t val[NUM_VALS];
101         uint64_t dne;
102         void *p;
103         struct htable_iter iter;
104
105         plan_tests(19);
106         for (i = 0; i < NUM_VALS; i++)
107                 val[i] = i;
108         dne = i;
109
110         ht = htable_new(hash, NULL);
111         ok1(ht->max < (1 << ht->bits));
112         ok1(ht->bits == HTABLE_BASE_BITS);
113
114         /* We cannot find an entry which doesn't exist. */
115         ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
116
117         /* Fill it, it should increase in size (once). */
118         add_vals(ht, val, NUM_VALS);
119         ok1(ht->bits == HTABLE_BASE_BITS + 1);
120         ok1(ht->max < (1 << ht->bits));
121
122         /* Mask should be set. */
123         ok1(ht->common_mask != 0);
124         ok1(ht->common_mask != -1);
125         ok1(check_mask(ht, val, NUM_VALS));
126
127         /* Find all. */
128         find_vals(ht, val, NUM_VALS);
129         ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
130
131         /* Walk once, should get them all. */
132         i = 0;
133         for (p = htable_first(ht,&iter); p; p = htable_next(ht, &iter))
134                 i++;
135         ok1(i == NUM_VALS);
136
137         /* Delete all. */
138         del_vals(ht, val, NUM_VALS);
139         ok1(!htable_get(ht, hash(&val[0], NULL), objcmp, &val[0]));
140
141         /* Worst case, a "pointer" which doesn't have any matching bits. */
142         htable_add(ht, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
143         htable_add(ht, hash(&val[NUM_VALS-1], NULL), &val[NUM_VALS-1]);
144         ok1(ht->common_mask == 0);
145         ok1(ht->common_bits == 0);
146
147         /* Add the rest. */
148         add_vals(ht, val, NUM_VALS-1);
149
150         /* Check we can find them all. */
151         find_vals(ht, val, NUM_VALS);
152         ok1(!htable_get(ht, hash(&dne, NULL), objcmp, &dne));
153
154         return exit_status();
155 }