htable: start empty.
[ccan] / ccan / htable / test / run-type.c
1 #include <ccan/htable/htable_type.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 struct obj {
11         /* Makes sure we don't try to treat and obj as a key or vice versa */
12         unsigned char unused;
13         unsigned int key;
14 };
15
16 static const unsigned int *objkey(const struct obj *obj)
17 {
18         return &obj->key;
19 }
20
21 /* We use the number divided by two as the hash (for lots of
22    collisions), plus set all the higher bits so we can detect if they
23    don't get masked out. */
24 static size_t objhash(const unsigned int *key)
25 {
26         size_t h = *key / 2;
27         h |= -1UL << NUM_BITS;
28         return h;
29 }
30
31 static bool cmp(const struct obj *obj, const unsigned int *key)
32 {
33         return obj->key == *key;
34 }
35
36 HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, obj);
37
38 static void add_vals(struct htable_obj *ht,
39                      struct obj val[], unsigned int num)
40 {
41         unsigned int i;
42
43         for (i = 0; i < num; i++) {
44                 if (htable_obj_get(ht, &i)) {
45                         fail("%u already in hash", i);
46                         return;
47                 }
48                 htable_obj_add(ht, &val[i]);
49                 if (htable_obj_get(ht, &i) != &val[i]) {
50                         fail("%u not added to hash", i);
51                         return;
52                 }
53         }
54         pass("Added %u numbers to hash", i);
55 }
56
57 static void find_vals(const struct htable_obj *ht,
58                       const struct obj val[], unsigned int num)
59 {
60         unsigned int i;
61
62         for (i = 0; i < num; i++) {
63                 if (htable_obj_get(ht, &i) != &val[i]) {
64                         fail("%u not found in hash", i);
65                         return;
66                 }
67         }
68         pass("Found %u numbers in hash", i);
69 }
70
71 static void del_vals(struct htable_obj *ht,
72                      const struct obj val[], unsigned int num)
73 {
74         unsigned int i;
75
76         for (i = 0; i < num; i++) {
77                 if (!htable_obj_delkey(ht, &val[i].key)) {
78                         fail("%u not deleted from hash", i);
79                         return;
80                 }
81         }
82         pass("Deleted %u numbers in hash", i);
83 }
84
85 static void del_vals_bykey(struct htable_obj *ht,
86                            const struct obj val[], unsigned int num)
87 {
88         unsigned int i;
89
90         for (i = 0; i < num; i++) {
91                 if (!htable_obj_delkey(ht, &i)) {
92                         fail("%u not deleted by key from hash", i);
93                         return;
94                 }
95         }
96         pass("Deleted %u numbers by key from hash", i);
97 }
98
99 static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
100 {
101         uint64_t i;
102
103         for (i = 0; i < num; i++) {
104                 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
105                         return false;
106         }
107         return true;
108 }
109
110 int main(int argc, char *argv[])
111 {
112         unsigned int i;
113         struct htable_obj *ht;
114         struct obj val[NUM_VALS];
115         unsigned int dne;
116         void *p;
117         struct htable_obj_iter iter;
118
119         plan_tests(20);
120         for (i = 0; i < NUM_VALS; i++)
121                 val[i].key = i;
122         dne = i;
123
124         ht = htable_obj_new();
125         ok1(((struct htable *)ht)->max == 0);
126         ok1(((struct htable *)ht)->bits == 0);
127
128         /* We cannot find an entry which doesn't exist. */
129         ok1(!htable_obj_get(ht, &dne));
130
131         /* Fill it, it should increase in size. */
132         add_vals(ht, val, NUM_VALS);
133         ok1(((struct htable *)ht)->bits == NUM_BITS + 1);
134         ok1(((struct htable *)ht)->max < (1 << ((struct htable *)ht)->bits));
135
136         /* Mask should be set. */
137         ok1(((struct htable *)ht)->common_mask != 0);
138         ok1(((struct htable *)ht)->common_mask != -1);
139         ok1(check_mask((struct htable *)ht, val, NUM_VALS));
140
141         /* Find all. */
142         find_vals(ht, val, NUM_VALS);
143         ok1(!htable_obj_get(ht, &dne));
144
145         /* Walk once, should get them all. */
146         i = 0;
147         for (p = htable_obj_first(ht,&iter); p; p = htable_obj_next(ht, &iter))
148                 i++;
149         ok1(i == NUM_VALS);
150
151         /* Delete all. */
152         del_vals(ht, val, NUM_VALS);
153         ok1(!htable_obj_get(ht, &val[0].key));
154
155         /* Worst case, a "pointer" which doesn't have any matching bits. */
156         htable_add((struct htable *)ht, 0,
157                    (void *)~(uintptr_t)&val[NUM_VALS-1]);
158         htable_obj_add(ht, &val[NUM_VALS-1]);
159         ok1(((struct htable *)ht)->common_mask == 0);
160         ok1(((struct htable *)ht)->common_bits == 0);
161         /* Delete the bogus one before we trip over it. */
162         htable_del((struct htable *)ht, 0,
163                    (void *)~(uintptr_t)&val[NUM_VALS-1]);
164
165         /* Add the rest. */
166         add_vals(ht, val, NUM_VALS-1);
167
168         /* Check we can find them all. */
169         find_vals(ht, val, NUM_VALS);
170         ok1(!htable_obj_get(ht, &dne));
171
172         /* Delete them all by key. */
173         del_vals_bykey(ht, val, NUM_VALS);
174         htable_obj_free(ht);
175
176         return exit_status();
177 }