2 * Copyright (C) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to deal
6 * in the Software without restriction, including without limitation the rights
7 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 * copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 #include <ccan/avl/avl.h>
25 #define remove remove_
26 #include <ccan/avl/avl.c>
29 #include <ccan/tap/tap.h>
36 #define ANIMATE_RANDOM_ACCESS 0
38 #if ANIMATE_RANDOM_ACCESS
42 typedef int64_t msec_t;
44 static msec_t time_ms(void)
47 gettimeofday(&tv, NULL);
48 return (msec_t)tv.tv_sec * 1000 + tv.tv_usec / 1000;
53 uint32_t rand32_state = 0;
56 * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
57 * Uses the BCPL linear congruential generator method.
59 * Note: this method (or maybe just this implementation) seems to
60 * go back and forth between odd and even exactly, which can
61 * affect low-cardinality testing if the cardinality given is even.
63 static uint32_t rand32(void)
65 rand32_state *= (uint32_t)0x7FF8A3ED;
66 rand32_state += (uint32_t)0x2AA01D31;
70 static void scramble(void *base, size_t nmemb, size_t size)
75 for (;nmemb>1;nmemb--) {
76 o = i + size*(rand32()%nmemb);
87 size_t passed_invariants_checks;
94 size_t failed_invariants_checks;
97 static void clear_stats(void)
99 memset(&stats, 0, sizeof(stats));
102 static bool print_stats(const char *success_label, size_t expected_success)
106 printf(" %s: \t%zu\n", success_label, stats.success);
107 if (stats.success != expected_success)
110 if (stats.passed_invariants_checks)
111 printf(" Passed invariants checks: %zu\n", stats.passed_invariants_checks);
114 failed = 1, printf(" Excess: \t%zu\n", stats.excess);
116 failed = 1, printf(" Duplicate: \t%zu\n", stats.duplicate);
118 failed = 1, printf(" Missing: \t%zu\n", stats.missing);
120 failed = 1, printf(" Incorrect: \t%zu\n", stats.incorrect);
122 failed = 1, printf(" Failed: \t%zu\n", stats.failed);
123 if (stats.failed_invariants_checks)
124 failed = 1, printf(" Failed invariants checks: %zu\n", stats.failed_invariants_checks);
132 size_t insert_id; /* needed because qsort is not a stable sort */
135 static int compare_uint32_t(const void *ap, const void *bp)
137 uint32_t a = *(const uint32_t *)ap;
138 uint32_t b = *(const uint32_t *)bp;
147 static int compare_test_item(const void *ap, const void *bp)
149 const struct test_item *a = *(void**)ap, *b = *(void**)bp;
156 if (a->insert_id < b->insert_id)
158 if (a->insert_id > b->insert_id)
164 static bool test_insert_item(AVL *avl, struct test_item *item)
166 avl_insert(avl, &item->key, &item->value);
170 static bool test_lookup_item(const AVL *avl, const struct test_item *item)
172 return avl_member(avl, &item->key) && avl_lookup(avl, &item->key) == &item->value;
175 static bool test_remove_item(AVL *avl, struct test_item *item)
177 return avl_remove(avl, &item->key);
180 static void test_foreach(AVL *avl, struct test_item **test_items, int count)
186 avl_foreach(iter, avl) {
191 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
199 static void test_foreach_reverse(AVL *avl, struct test_item **test_items, int count)
205 avl_foreach_reverse(iter, avl) {
210 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
218 static void benchmark(size_t max_per_trial, size_t round_count, bool random_counts, int cardinality)
220 struct test_item **test_item;
221 struct test_item *test_item_array;
225 test_item = malloc(max_per_trial * sizeof(*test_item));
226 test_item_array = malloc(max_per_trial * sizeof(*test_item_array));
228 if (!test_item || !test_item_array) {
229 fail("Not enough memory for %zu keys per trial\n",
234 /* Initialize test_item pointers. */
235 for (i=0; i<max_per_trial; i++)
236 test_item[i] = &test_item_array[i];
239 * If round_count is not zero, run round_count trials.
240 * Otherwise, run forever.
242 for (round = 1; round_count==0 || round <= round_count; round++) {
246 printf("Round %zu (cardinality = %d)\n", round, cardinality);
248 printf("Round %zu\n", round);
251 count = rand32() % (max_per_trial+1);
253 count = max_per_trial;
256 * Initialize test items by giving them sequential keys and
257 * random values. Scramble them so the order of insertion
260 for (i=0; i<count; i++) {
261 test_item[i]->key = rand32();
262 test_item[i]->value = rand32();
265 test_item[i]->key %= cardinality;
267 scramble(test_item, count, sizeof(*test_item));
269 avl = avl_new(compare_uint32_t);
272 printf(" Inserting %zu items...\n", count);
273 for (i=0; i<count; i++) {
274 if (test_insert_item(avl, test_item[i])) {
276 test_item[i]->insert_id = i;
278 printf("invariants check failed at insertion %zu\n", i);
282 /* Periodically do an invariants check */
283 if (count / 10 > 0 && i % (count / 10) == 0) {
284 if (avl_check_invariants(avl))
285 stats.passed_invariants_checks++;
287 stats.failed_invariants_checks++;
290 ok1(print_stats("Inserted", count));
291 ok1(avl_check_invariants(avl));
293 /* remove early duplicates, as they are shadowed in insertions. */
294 qsort(test_item, count, sizeof(*test_item), compare_test_item);
295 for (i = 0, o = 0; i < count;) {
296 uint32_t k = test_item[i]->key;
297 do i++; while (i < count && test_item[i]->key == k);
298 test_item[o++] = test_item[i-1];
301 ok1(avl_count(avl) == count);
303 scramble(test_item, count, sizeof(*test_item));
305 printf(" Finding %zu items...\n", count);
307 for (i=0; i<count; i++) {
308 if (!test_lookup_item(avl, test_item[i]))
313 ok1(print_stats("Retrieved", count));
315 qsort(test_item, count, sizeof(*test_item), compare_test_item);
317 printf(" Traversing forward through %zu items...\n", count);
319 test_foreach(avl, test_item, count);
320 ok1(print_stats("Traversed", count));
322 printf(" Traversing backward through %zu items...\n", count);
324 test_foreach_reverse(avl, test_item, count);
325 ok1(print_stats("Traversed", count));
327 scramble(test_item, count, sizeof(*test_item));
329 printf(" Deleting %zu items...\n", count);
331 for (i=0; i<count; i++) {
332 if (test_remove_item(avl, test_item[i]))
337 /* Periodically do an invariants check */
338 if (count / 10 > 0 && i % (count / 10) == 0) {
339 if (avl_check_invariants(avl))
340 stats.passed_invariants_checks++;
342 stats.failed_invariants_checks++;
345 ok1(print_stats("Deleted", count));
346 ok1(avl_count(avl) == 0);
347 ok1(avl_check_invariants(avl));
353 free(test_item_array);
356 static int compare_ptr(const void *a, const void *b)
370 static bool print_pass_fail(struct fail_total *pf, const char *label)
372 long long fail = pf->fail,
375 printf("%s:\t%lld / %lld\n", label, total - fail, total);
380 static void test_random_access(uint32_t max, int64_t ops)
387 inserts, lookups, removes, checks;
390 #if ANIMATE_RANDOM_ACCESS
391 msec_t last_update, now;
392 msec_t interval = 100;
395 memset(&s, 0, sizeof(s));
397 in_tree = malloc(max);
398 memset(in_tree, 0, max);
400 avl = avl_new(compare_ptr);
402 #if ANIMATE_RANDOM_ACCESS
404 last_update = now - interval;
407 for (i = 0; i < ops; i++) {
408 char *item = &in_tree[rand32() % max];
410 bool inserted, removed;
412 #if ANIMATE_RANDOM_ACCESS
414 if (now >= last_update + interval) {
416 printf("\r%.2f%%\t%zu / %zu\033[K", (double)i * 100 / ops, avl_count(avl), max);
421 switch (rand32() % 3) {
423 inserted = avl_insert(avl, item, item);
425 if ((*item == 0 && !inserted) ||
426 (*item == 1 && inserted))
436 found = avl_lookup(avl, item);
438 if ((*item == 0 && found != NULL) ||
439 (*item == 1 && found != item) ||
440 (avl_member(avl, item) != !!found))
447 removed = avl_remove(avl, item);
449 if ((*item == 0 && removed) ||
450 (*item == 1 && !removed))
460 /* Periodically do an invariants check */
461 if (ops / 10 > 0 && i % (ops / 10) == 0) {
462 if (!avl_check_invariants(avl))
468 #if ANIMATE_RANDOM_ACCESS
475 ok1(print_pass_fail(&s.inserts, "Inserts"));
476 ok1(print_pass_fail(&s.lookups, "Lookups"));
477 ok1(print_pass_fail(&s.removes, "Removes"));
478 ok1(print_pass_fail(&s.checks, "Invariants checks"));
483 plan_tests(18 * 3 + 4);
485 benchmark(100000, 2, false, 0);
486 benchmark(100000, 2, false, 12345);
487 benchmark(100000, 2, false, 100001);
489 printf("Running random access test\n");
490 test_random_access(12345, 1234567);
492 return exit_status();