btree: spelling fix
[ccan] / ccan / btree / test / run-random-access.c
1 /* Include the main header first, to test it works */
2 #include <ccan/btree/btree.h>
3 /* Include the C files directly. */
4 #include <ccan/btree/btree.c>
5 #include <ccan/tap/tap.h>
6
7 #include <stdint.h>
8 #include <stdio.h>
9 #include <stdlib.h>
10 #include <string.h>
11
12 static uint32_t rand32_state = 0;
13
14 /*
15  * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
16  * Uses the BCPL linear congruential generator method.
17  */
18 static uint32_t rand32(void)
19 {
20         rand32_state *= (uint32_t)0x7FF8A3ED;
21         rand32_state += (uint32_t)0x2AA01D31;
22         return rand32_state;
23 }
24
25 /*
26  * Whether or not to add/remove multiple equal keys to the tree.
27  *
28  * Tests are run with multi set to 0 and 1.
29  */
30 static int multi = 0;
31
32 static struct {
33         struct {
34                 size_t success;
35                 size_t failure;
36         } insert, remove, find, traverse;
37 } stats;
38
39 static int check_stats(void) {
40         return
41                 stats.insert.failure == 0 &&
42                 stats.remove.failure == 0 &&
43                 stats.find.failure == 0 &&
44                 stats.traverse.failure == 0;
45 }
46
47 static int print_stats(void) {
48         printf("Insert:  %zu succeeded, %zu failed\n",
49                 stats.insert.success, stats.insert.failure);
50         
51         printf("Remove:  %zu succeeded, %zu failed\n",
52                 stats.remove.success, stats.remove.failure);
53         
54         printf("Find:  %zu succeeded, %zu failed\n",
55                 stats.find.success, stats.find.failure);
56         
57         printf("Traverse:  %zu succeeded, %zu failed\n",
58                 stats.traverse.success, stats.traverse.failure);
59         
60         return check_stats();
61 }
62
63 static void clear_stats(void)
64 {
65         memset(&stats, 0, sizeof(stats));
66 }
67
68 static int test_node_consistency(struct btree_node *node, struct btree_node *parent, size_t *count)
69 {
70         unsigned int i, j, e = node->count;
71         
72         /* Verify parent, depth, and k */
73         if (node->parent != parent)
74                 return 0;
75         if (parent) {
76                 if (node->depth != parent->depth - 1)
77                         return 0;
78                 if (node != parent->branch[node->k])
79                         return 0;
80         }
81         
82         /* Nodes must not be empty (unless the entire tree is empty). */
83         if (e == 0)
84                 return 0;
85         
86         if (node->depth) {
87                 /* Make sure child branches aren't duplicated or NULL. */
88                 for (i=0; i<=e; i++) {
89                         if (node->branch[i] == NULL)
90                                 return 0;
91                         for (j=i+1; j<=e; j++)
92                                 if (node->branch[i] == node->branch[j])
93                                         return 0;
94                 }
95                 
96                 /* Recursively check children. */
97                 for (i=0; i<=e; i++) {
98                         if (!test_node_consistency(node->branch[i], node, count))
99                                 return 0;
100                 }
101         }
102         
103         *count += node->count;
104         return 1;
105 }
106
107 static int test_consistency(const struct btree *btree)
108 {
109         size_t count = 0;
110         if (!btree->root)
111                 return 0;
112         if (btree->root->count == 0) {
113                 if (btree->count != 0)
114                         return 0;
115                 return 1;
116         }
117         if (btree->count == 0)
118                 return 0;
119         if (!test_node_consistency(btree->root, NULL, &count))
120                 return 0;
121         if (btree->count != count)
122                 return 0;
123         return 1;
124 }
125
126 static int test_traverse(struct btree *btree, size_t key[], size_t count)
127 {
128         btree_iterator iter;
129         size_t i, j;
130         
131         if (!test_consistency(btree))
132                 return 0;
133         
134         /* Forward */
135         i = 0;
136         btree_begin(btree, iter);
137         for (;;) {
138                 while (i < count && key[i] == 0)
139                         i++;
140                 if (i >= count) {
141                         if (btree_next(iter))
142                                 return 0;
143                         break;
144                 }
145                 for (j = 0; j < key[i] && btree_next(iter); j++) {
146                         if (iter->item != &key[i])
147                                 return 0;
148                 }
149                 if (j != key[i])
150                         return 0;
151                 i++;
152         }
153         
154         /* Backward */
155         i = count;
156         btree_end(btree, iter);
157         for (;;) {
158                 while (i > 0 && key[i-1] == 0)
159                         i--;
160                 if (i <= 0) {
161                         if (btree_prev(iter))
162                                 return 0;
163                         break;
164                 }
165                 for (j = 0; j < key[i-1] && btree_prev(iter); j++) {
166                         if (iter->item != &key[i-1])
167                                 return 0;
168                 }
169                 if (j != key[i-1])
170                         return 0;
171                 i--;
172         }
173         
174         return 1;
175 }
176
177 /*
178  * Finds and counts items matching &key[k], then makes sure the count
179  * equals key[k].  Also verifies that btree_find_... work as advertised.
180  */
181 static int find(struct btree *btree, size_t key[], size_t k)
182 {
183         btree_iterator iter, tmp;
184         size_t count;
185         int found;
186         
187         memset(iter, 0, sizeof(iter));
188         memset(tmp, 0, sizeof(tmp));
189         
190         found = btree_find_first(btree, &key[k], iter);
191         if (iter->btree != btree)
192                 return 0;
193         if (found != !!key[k])
194                 return 0;
195         if (key[k] && iter->item != &key[k])
196                 return 0;
197         
198         /* Make sure btree_find works exactly the same as btree_find_first. */
199         if (btree_find(btree, &key[k], tmp) != found)
200                 return 0;
201         if (memcmp(iter, tmp, sizeof(*iter)))
202                 return 0;
203         
204         /* Make sure previous item doesn't match. */
205         *tmp = *iter;
206         if (btree_prev(tmp)) {
207                 if (tmp->item == &key[k])
208                         return 0;
209         }
210         
211         /* Count going forward. */
212         for (count=0; btree_deref(iter) && iter->item == &key[k]; count++, btree_next(iter))
213                 {}
214         if (count != key[k])
215                 return 0;
216         
217         /* Make sure next item doesn't match. */
218         *tmp = *iter;
219         if (btree_deref(tmp)) {
220                 if (tmp->item == &key[k])
221                         return 0;
222         }
223         
224         /* Make sure iter is now equal to the end of matching items. */
225         btree_find_last(btree, &key[k], tmp);
226         if (tmp->btree != btree)
227                 return 0;
228         if (btree_cmp_iters(iter, tmp))
229                 return 0;
230         
231         /* Count going backward. */
232         for (count=0; btree_prev(iter); count++) {
233                 if (iter->item != &key[k]) {
234                         btree_next(iter);
235                         break;
236                 }
237         }
238         if (count != key[k])
239                 return 0;
240         
241         /* Make sure iter is now equal to the beginning of matching items. */
242         btree_find_first(btree, &key[k], tmp);
243         if (tmp->btree != btree)
244                 return 0;
245         if (btree_cmp_iters(iter, tmp))
246                 return 0;
247         
248         return 1;
249 }
250
251 static int test_find(struct btree *btree, size_t key[], size_t count)
252 {
253         size_t k = rand32() % count;
254         return find(btree, key, k);
255 }
256
257 static int test_remove(struct btree *btree, size_t key[], size_t count)
258 {
259         size_t prev_count = btree->count;
260         size_t k = rand32() % count;
261         btree_iterator iter;
262         
263         if (!find(btree, key, k))
264                 return 0;
265         
266         btree_find(btree, &key[k], iter);
267         
268         //remove (if present), and make sure removal status is correct
269         if (key[k]) {
270                 if (btree_remove_at(iter) != 1)
271                         return 0;
272                 if (btree->count != prev_count - 1)
273                         return 0;
274                 key[k]--;
275                 
276                 if (!find(btree, key, k))
277                         return 0;
278         }
279         
280         return 1;
281 }
282
283 static int test_insert(struct btree *btree, size_t key[], size_t count)
284 {
285         size_t k = rand32() % count;
286         btree_iterator iter;
287         size_t prev_count = btree->count;
288         int found;
289         
290         if (!find(btree, key, k))
291                 return 0;
292         
293         /* Make sure key's presence is consistent with our array. */
294         found = btree_find_first(btree, &key[k], iter);
295         if (key[k]) {
296                 if (!found || iter->item != &key[k])
297                         return 0;
298                 if (!btree_deref(iter))
299                         return 0;
300                 if (iter->k >= iter->node->count || iter->node->item[iter->k] != &key[k])
301                         return 0;
302         } else {
303                 if (found)
304                         return 0;
305         }
306         
307         /* Insert if item hasn't been yet (or if we're in multi mode). */
308         if (!key[k] || multi) {
309                 btree_insert_at(iter, &key[k]);
310                 key[k]++;
311                 if (btree->count != prev_count + 1)
312                         return 0;
313         }
314         
315         /* Check result iterator's ->item field. */
316         if (iter->item != &key[k])
317                 return 0;
318         
319         if (!find(btree, key, k))
320                 return 0;
321         
322         /* Make sure key is present and correct now. */
323         found = btree_find_first(btree, &key[k], iter);
324         if (!found || iter->item != &key[k])
325                 return 0;
326         
327         return 1;
328 }
329
330 static btree_search_implement(order_by_ptr, size_t*, , a == b, a < b)
331
332 static void stress(size_t count, size_t trials)
333 {
334         struct btree *btree = btree_new(order_by_ptr);
335         size_t *key = calloc(count, sizeof(*key));
336         size_t i;
337         
338         clear_stats();
339         
340         for (i=0; i<trials; i++) {
341                 unsigned int n = rand32() % 65536;
342                 unsigned int rib = btree->count * 43688 / count;
343                         //remove/insert boundary
344                 if (n >= 65534) {
345                         if (test_traverse(btree, key, count))
346                                 stats.traverse.success++;
347                         else
348                                 stats.traverse.failure++;
349                 } else if (n >= 46388) {
350                         if (test_find(btree, key, count))
351                                 stats.find.success++;
352                         else
353                                 stats.find.failure++;
354                 } else if (n < rib) {
355                         if (test_remove(btree, key, count))
356                                 stats.remove.success++;
357                         else
358                                 stats.remove.failure++;
359                 } else {
360                         if (test_insert(btree, key, count))
361                                 stats.insert.success++;
362                         else
363                                 stats.insert.failure++;
364                 }
365         }
366         
367         free(key);
368         btree_delete(btree);
369         
370         print_stats();
371         ok1(check_stats());
372 }
373
374 int main(void)
375 {
376         plan_tests(2);
377         
378         multi = 0;
379         printf("Running with multi = %d\n", multi);
380         stress(100000, 500000);
381         
382         multi = 1;
383         printf("Running with multi = %d\n", multi);
384         stress(100000, 500000);
385         
386         return exit_status();
387 }