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>
11 uint32_t rand32_state = 0;
14 * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
15 * Uses the BCPL linear congruential generator method.
17 static uint32_t rand32(void)
19 rand32_state *= (uint32_t)0x7FF8A3ED;
20 rand32_state += (uint32_t)0x2AA01D31;
24 static void scramble(void *base, size_t nmemb, size_t size)
29 for (;nmemb>1;nmemb--) {
30 o = i + size*(rand32()%nmemb);
44 /* For ordering a btree of test_item pointers. */
45 static btree_search_implement (
47 const struct test_item *,
53 /* For qsorting an array of test_item pointers. */
54 static int compare_test_item(const void *ap, const void *bp)
56 const struct test_item *a = *(const struct test_item * const*)ap;
57 const struct test_item *b = *(const struct test_item * const*)bp;
66 * If lr == 0, make sure iter points to the item given.
67 * If lr == 1, make sure iter points to after the item given.
69 static int check_iter(btree_iterator iter_orig, const void *item, int lr)
71 btree_iterator iter = {*iter_orig};
72 if (iter->item != item)
75 if (!btree_prev(iter))
78 if (!btree_deref(iter))
81 if (iter->item != item)
83 if (iter->node->item[iter->k] != iter->item)
90 * Returns 1 on insert, 0 on duplicate,
91 * -1 on bad iterator returned by find, and
92 * -2 on bad iterator returned by insert.
94 static int insert_test_item(struct btree *btree, struct test_item *item)
99 /* Find the first or last matching item, randomly choosing between the two. */
101 if (btree_find_lr(btree, item, iter, lr)) {
102 if (!check_iter(iter, item, lr))
107 btree_insert_at(iter, item);
109 if (iter->item != item)
116 * Returns 1 on remove, 0 on missing,
117 * -1 on bad iterator returned by find, and
118 * -2 on bad iterator returned by remove.
120 static int remove_test_item(struct btree *btree, struct test_item *item)
124 if (!btree_find(btree, item, iter))
127 if (!check_iter(iter, item, 0))
130 btree_remove_at(iter);
132 if (iter->item != item)
147 size_t bad_iter_find;
148 size_t bad_iter_insert;
149 size_t bad_iter_remove;
150 size_t bad_iter_next;
153 static void clear_stats(void) {
154 memset(&stats, 0, sizeof(stats));
157 static int print_stats(const char *success_label, size_t expected_success) {
160 printf(" %s: \t%zu\n", success_label, stats.success);
161 if (stats.success != expected_success)
165 failed = 1, printf(" Excess: \t%zu\n", stats.excess);
167 failed = 1, printf(" Duplicate: \t%zu\n", stats.duplicate);
169 failed = 1, printf(" Missing: \t%zu\n", stats.missing);
171 failed = 1, printf(" Incorrect: \t%zu\n", stats.incorrect);
173 failed = 1, printf(" Failed: \t%zu\n", stats.failed);
175 if (stats.bad_iter_find || stats.bad_iter_insert ||
176 stats.bad_iter_remove || stats.bad_iter_next) {
178 printf(" Bad iterators yielded by:\n");
179 if (stats.bad_iter_find)
180 printf(" btree_find_lr(): %zu\n", stats.bad_iter_find);
181 if (stats.bad_iter_insert)
182 printf(" btree_insert_at(): %zu\n", stats.bad_iter_insert);
183 if (stats.bad_iter_remove)
184 printf(" btree_remove_at(): %zu\n", stats.bad_iter_remove);
185 if (stats.bad_iter_next)
186 printf(" btree_next(): %zu\n", stats.bad_iter_next);
192 static void benchmark(size_t max_per_trial, size_t round_count, int random_counts)
194 struct test_item **test_item;
195 struct test_item *test_item_array;
199 test_item = malloc(max_per_trial * sizeof(*test_item));
200 test_item_array = malloc(max_per_trial * sizeof(*test_item_array));
202 if (!test_item || !test_item_array) {
203 fail("Not enough memory for %zu keys per trial\n",
208 /* Initialize test_item pointers. */
209 for (i=0; i<max_per_trial; i++)
210 test_item[i] = &test_item_array[i];
213 * If round_count is not zero, run round_count trials.
214 * Otherwise, run forever.
216 for (round = 1; round_count==0 || round <= round_count; round++) {
220 printf("Round %zu\n", round);
223 count = rand32() % (max_per_trial+1);
225 count = max_per_trial;
228 * Initialize test items by giving them sequential keys and
229 * random values. Scramble them so the order of insertion
232 for (i=0; i<count; i++) {
233 test_item[i]->key = i;
234 test_item[i]->value = rand32();
236 scramble(test_item, count, sizeof(*test_item));
238 btree = btree_new(order_by_key);
241 printf(" Inserting %zu items...\n", count);
242 for (i=0; i<count; i++) {
243 switch (insert_test_item(btree, test_item[i])) {
244 case 1: stats.success++; break;
245 case 0: stats.duplicate++; break;
246 case -1: stats.bad_iter_find++; break;
247 case -2: stats.bad_iter_insert++; break;
248 default: stats.failed++; break;
251 ok1(print_stats("Inserted", count));
253 scramble(test_item, count, sizeof(*test_item));
255 printf(" Finding %zu items...\n", count);
257 for (i=0; i<count; i++) {
258 int lr = rand32() & 1;
260 if (!btree_find_lr(btree, test_item[i], iter, lr)) {
265 if (!check_iter(iter, test_item[i], lr)) {
266 stats.bad_iter_find++;
272 ok1(print_stats("Retrieved", count));
274 qsort(test_item, count, sizeof(*test_item), compare_test_item);
276 printf(" Traversing forward through %zu items...\n", count);
279 for (btree_begin(btree, iter); btree_next(iter);) {
285 if (iter->item == test_item[i])
292 ok1(print_stats("Retrieved", count));
294 printf(" Traversing backward through %zu items...\n", count);
297 for (btree_end(btree, iter); btree_prev(iter);) {
304 if (iter->item == test_item[i])
309 ok1(print_stats("Retrieved", count));
311 ok1(btree->count == count);
313 //static int remove_test_item(struct btree *btree, struct test_item *item);
314 scramble(test_item, count, sizeof(*test_item));
316 printf(" Deleting %zu items...\n", count);
318 for (i=0; i<count; i++) {
319 int s = remove_test_item(btree, test_item[i]);
321 printf("remove_test_item failed\n");
323 case 1: stats.success++; break;
324 case 0: stats.missing++; break;
325 case -1: stats.bad_iter_find++; break;
326 case -2: stats.bad_iter_remove++; break;
327 default: stats.failed++; break;
330 ok1(btree->count == 0);
331 ok1(print_stats("Deleted", count));
332 ok1(btree->root->depth == 0 && btree->root->count == 0);
338 free(test_item_array);
345 benchmark(300000, 4, 0);
347 return exit_status();