htable: reduce size of htable by calculating max every time.
[ccan] / ccan / htable / test / run-type-int.c
1 /* Key is an unsigned int, not a pointer. */
2 #include "config.h"
3 #if !defined(HAVE_TYPEOF) || !HAVE_TYPEOF
4 #define HTABLE_KTYPE(keyof, type) unsigned int
5 #endif
6 #include <ccan/htable/htable_type.h>
7 #include <ccan/htable/htable.c>
8 #include <ccan/tap/tap.h>
9 #include <stdbool.h>
10 #include <string.h>
11
12 #define NUM_BITS 7
13 #define NUM_VALS (1 << NUM_BITS)
14
15 struct obj {
16         /* Makes sure we don't try to treat and obj as a key or vice versa */
17         unsigned char unused;
18         unsigned int key;
19 };
20
21 static const unsigned int objkey(const struct obj *obj)
22 {
23         return obj->key;
24 }
25
26 /* We use the number divided by two as the hash (for lots of
27    collisions), plus set all the higher bits so we can detect if they
28    don't get masked out. */
29 static size_t objhash(const unsigned int key)
30 {
31         size_t h = key / 2;
32         h |= -1UL << NUM_BITS;
33         return h;
34 }
35
36 static bool cmp(const struct obj *obj, const unsigned int key)
37 {
38         return obj->key == key;
39 }
40
41 HTABLE_DEFINE_TYPE(struct obj, objkey, objhash, cmp, htable_obj);
42
43 static void add_vals(struct htable_obj *ht,
44                      struct obj val[], unsigned int num)
45 {
46         unsigned int i;
47
48         for (i = 0; i < num; i++) {
49                 if (htable_obj_get(ht, i)) {
50                         fail("%u already in hash", i);
51                         return;
52                 }
53                 htable_obj_add(ht, &val[i]);
54                 if (htable_obj_get(ht, i) != &val[i]) {
55                         fail("%u not added to hash", i);
56                         return;
57                 }
58         }
59         pass("Added %u numbers to hash", i);
60 }
61
62 static void find_vals(const struct htable_obj *ht,
63                       const struct obj val[], unsigned int num)
64 {
65         unsigned int i;
66
67         for (i = 0; i < num; i++) {
68                 if (htable_obj_get(ht, i) != &val[i]) {
69                         fail("%u not found in hash", i);
70                         return;
71                 }
72         }
73         pass("Found %u numbers in hash", i);
74 }
75
76 static void del_vals(struct htable_obj *ht,
77                      const struct obj val[], unsigned int num)
78 {
79         unsigned int i;
80
81         for (i = 0; i < num; i++) {
82                 if (!htable_obj_delkey(ht, val[i].key)) {
83                         fail("%u not deleted from hash", i);
84                         return;
85                 }
86         }
87         pass("Deleted %u numbers in hash", i);
88 }
89
90 static void del_vals_bykey(struct htable_obj *ht,
91                            const struct obj val[] UNNEEDED, unsigned int num)
92 {
93         unsigned int i;
94
95         for (i = 0; i < num; i++) {
96                 if (!htable_obj_delkey(ht, i)) {
97                         fail("%u not deleted by key from hash", i);
98                         return;
99                 }
100         }
101         pass("Deleted %u numbers by key from hash", i);
102 }
103
104 static bool check_mask(struct htable *ht, const struct obj val[], unsigned num)
105 {
106         uint64_t i;
107
108         for (i = 0; i < num; i++) {
109                 if (((uintptr_t)&val[i] & ht->common_mask) != ht->common_bits)
110                         return false;
111         }
112         return true;
113 }
114
115 int main(void)
116 {
117         unsigned int i;
118         struct htable_obj ht, ht2;
119         struct obj val[NUM_VALS], *result;
120         unsigned int dne;
121         void *p;
122         struct htable_obj_iter iter;
123
124         plan_tests(29);
125         for (i = 0; i < NUM_VALS; i++)
126                 val[i].key = i;
127         dne = i;
128
129         htable_obj_init(&ht);
130         ok1(ht_max(&ht.raw) == 0);
131         ok1(ht.raw.bits == 0);
132
133         /* We cannot find an entry which doesn't exist. */
134         ok1(!htable_obj_get(&ht, dne));
135
136         /* Fill it, it should increase in size. */
137         add_vals(&ht, val, NUM_VALS);
138         ok1(ht.raw.bits == NUM_BITS + 1);
139         ok1(ht_max(&ht.raw) < (1 << ht.raw.bits));
140
141         /* Mask should be set. */
142         ok1(ht.raw.common_mask != 0);
143         ok1(ht.raw.common_mask != -1);
144         ok1(check_mask(&ht.raw, val, NUM_VALS));
145
146         /* Find all. */
147         find_vals(&ht, val, NUM_VALS);
148         ok1(!htable_obj_get(&ht, dne));
149
150         /* Walk once, should get them all. */
151         i = 0;
152         for (p = htable_obj_first(&ht,&iter); p; p = htable_obj_next(&ht, &iter))
153                 i++;
154         ok1(i == NUM_VALS);
155         i = 0;
156         for (p = htable_obj_prev(&ht,&iter); p; p = htable_obj_prev(&ht, &iter))
157                 i++;
158         ok1(i == NUM_VALS);
159
160         /* Delete all. */
161         del_vals(&ht, val, NUM_VALS);
162         ok1(!htable_obj_get(&ht, val[0].key));
163
164         /* Worst case, a "pointer" which doesn't have any matching bits. */
165         htable_add(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
166         htable_obj_add(&ht, &val[NUM_VALS-1]);
167         ok1(ht.raw.common_mask == 0);
168         ok1(ht.raw.common_bits == 0);
169         /* Delete the bogus one before we trip over it. */
170         htable_del(&ht.raw, 0, (void *)~(uintptr_t)&val[NUM_VALS-1]);
171
172         /* Add the rest. */
173         add_vals(&ht, val, NUM_VALS-1);
174
175         /* Check we can find them all. */
176         find_vals(&ht, val, NUM_VALS);
177         ok1(!htable_obj_get(&ht, dne));
178
179         /* Check copy. */
180         ok1(htable_obj_copy(&ht2, &ht));
181
182         /* Delete them all by key. */
183         del_vals_bykey(&ht, val, NUM_VALS);
184         del_vals_bykey(&ht2, val, NUM_VALS);
185
186         /* Write two of the same value. */
187         val[1] = val[0];
188         htable_obj_add(&ht, &val[0]);
189         htable_obj_add(&ht, &val[1]);
190         i = 0;
191
192         result = htable_obj_getfirst(&ht, i, &iter);
193         ok1(result == &val[0] || result == &val[1]);
194         if (result == &val[0]) {
195                 ok1(htable_obj_getnext(&ht, i, &iter) == &val[1]);
196                 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
197
198                 /* Deleting first should make us iterate over the other. */
199                 ok1(htable_obj_del(&ht, &val[0]));
200                 ok1(htable_obj_getfirst(&ht, i, &iter) == &val[1]);
201                 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
202         } else {
203                 ok1(htable_obj_getnext(&ht, i, &iter) == &val[0]);
204                 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
205
206                 /* Deleting first should make us iterate over the other. */
207                 ok1(htable_obj_del(&ht, &val[1]));
208                 ok1(htable_obj_getfirst(&ht, i, &iter) == &val[0]);
209                 ok1(htable_obj_getnext(&ht, i, &iter) == NULL);
210         }
211
212         htable_obj_clear(&ht);
213         htable_obj_clear(&ht2);
214         return exit_status();
215 }