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>
12 static uint32_t rand32_state = 0;
15 * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
16 * Uses the BCPL linear congruential generator method.
18 static uint32_t rand32(void)
20 rand32_state *= (uint32_t)0x7FF8A3ED;
21 rand32_state += (uint32_t)0x2AA01D31;
26 * Whether or not to add/remove multiple equal keys to the tree.
28 * Tests are run with multi set to 0 and 1.
36 } insert, remove, find, traverse;
39 static int check_stats(void) {
41 stats.insert.failure == 0 &&
42 stats.remove.failure == 0 &&
43 stats.find.failure == 0 &&
44 stats.traverse.failure == 0;
47 static int print_stats(void) {
48 printf("Insert: %zu succeeded, %zu failed\n",
49 stats.insert.success, stats.insert.failure);
51 printf("Remove: %zu succeeded, %zu failed\n",
52 stats.remove.success, stats.remove.failure);
54 printf("Find: %zu succeeded, %zu failed\n",
55 stats.find.success, stats.find.failure);
57 printf("Traverse: %zu succeeded, %zu failed\n",
58 stats.traverse.success, stats.traverse.failure);
63 static void clear_stats(void)
65 memset(&stats, 0, sizeof(stats));
68 static int test_node_consistency(struct btree_node *node, struct btree_node *parent, size_t *count)
70 unsigned int i, j, e = node->count;
72 /* Verify parent, depth, and k */
73 if (node->parent != parent)
76 if (node->depth != parent->depth - 1)
78 if (node != parent->branch[node->k])
82 /* Nodes must not be empty (unless the entire tree is empty). */
87 /* Make sure child branches aren't duplicated or NULL. */
88 for (i=0; i<=e; i++) {
89 if (node->branch[i] == NULL)
91 for (j=i+1; j<=e; j++)
92 if (node->branch[i] == node->branch[j])
96 /* Recursively check children. */
97 for (i=0; i<=e; i++) {
98 if (!test_node_consistency(node->branch[i], node, count))
103 *count += node->count;
107 static int test_consistency(const struct btree *btree)
112 if (btree->root->count == 0) {
113 if (btree->count != 0)
117 if (btree->count == 0)
119 if (!test_node_consistency(btree->root, NULL, &count))
121 if (btree->count != count)
126 static int test_traverse(struct btree *btree, size_t key[], size_t count)
131 if (!test_consistency(btree))
136 btree_begin(btree, iter);
138 while (i < count && key[i] == 0)
141 if (btree_next(iter))
145 for (j = 0; j < key[i] && btree_next(iter); j++) {
146 if (iter->item != &key[i])
156 btree_end(btree, iter);
158 while (i > 0 && key[i-1] == 0)
161 if (btree_prev(iter))
165 for (j = 0; j < key[i-1] && btree_prev(iter); j++) {
166 if (iter->item != &key[i-1])
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.
181 static int find(struct btree *btree, size_t key[], size_t k)
183 btree_iterator iter, tmp;
187 memset(iter, 0, sizeof(iter));
188 memset(tmp, 0, sizeof(tmp));
190 found = btree_find_first(btree, &key[k], iter);
191 if (iter->btree != btree)
193 if (found != !!key[k])
195 if (key[k] && iter->item != &key[k])
198 /* Make sure btree_find works exactly the same as btree_find_first. */
199 if (btree_find(btree, &key[k], tmp) != found)
201 if (memcmp(iter, tmp, sizeof(*iter)))
204 /* Make sure previous item doesn't match. */
206 if (btree_prev(tmp)) {
207 if (tmp->item == &key[k])
211 /* Count going forward. */
212 for (count=0; btree_deref(iter) && iter->item == &key[k]; count++, btree_next(iter))
217 /* Make sure next item doesn't match. */
219 if (btree_deref(tmp)) {
220 if (tmp->item == &key[k])
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)
228 if (btree_cmp_iters(iter, tmp))
231 /* Count going backward. */
232 for (count=0; btree_prev(iter); count++) {
233 if (iter->item != &key[k]) {
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)
245 if (btree_cmp_iters(iter, tmp))
251 static int test_find(struct btree *btree, size_t key[], size_t count)
253 size_t k = rand32() % count;
254 return find(btree, key, k);
257 static int test_remove(struct btree *btree, size_t key[], size_t count)
259 size_t prev_count = btree->count;
260 size_t k = rand32() % count;
263 if (!find(btree, key, k))
266 btree_find(btree, &key[k], iter);
268 //remove (if present), and make sure removal status is correct
270 if (btree_remove_at(iter) != 1)
272 if (btree->count != prev_count - 1)
276 if (!find(btree, key, k))
283 static int test_insert(struct btree *btree, size_t key[], size_t count)
285 size_t k = rand32() % count;
287 size_t prev_count = btree->count;
290 if (!find(btree, key, k))
293 /* Make sure key's presence is consistent with our array. */
294 found = btree_find_first(btree, &key[k], iter);
296 if (!found || iter->item != &key[k])
298 if (!btree_deref(iter))
300 if (iter->k >= iter->node->count || iter->node->item[iter->k] != &key[k])
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]);
311 if (btree->count != prev_count + 1)
315 /* Check result iterator's ->item field. */
316 if (iter->item != &key[k])
319 if (!find(btree, key, k))
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])
330 static btree_search_implement(order_by_ptr, size_t*, , a == b, a < b)
332 static void stress(size_t count, size_t trials)
334 struct btree *btree = btree_new(order_by_ptr);
335 size_t *key = calloc(count, sizeof(*key));
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
345 if (test_traverse(btree, key, count))
346 stats.traverse.success++;
348 stats.traverse.failure++;
349 } else if (n >= 46388) {
350 if (test_find(btree, key, count))
351 stats.find.success++;
353 stats.find.failure++;
354 } else if (n < rib) {
355 if (test_remove(btree, key, count))
356 stats.remove.success++;
358 stats.remove.failure++;
360 if (test_insert(btree, key, count))
361 stats.insert.success++;
363 stats.insert.failure++;
379 printf("Running with multi = %d\n", multi);
380 stress(100000, 500000);
383 printf("Running with multi = %d\n", multi);
384 stress(100000, 500000);
386 return exit_status();