git.ozlabs.org Git - ccan/blob - ccan/avl/test/run.c

   1 /*
   2  * Copyright (c) 2010 Joseph Adams <joeyadams3.14159@gmail.com>
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
   9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 #include <ccan/avl/avl.h>
  18
  19 #define remove remove_
  20 #include <ccan/avl/avl.c>
  21 #undef remove
  22
  23 #include <ccan/tap/tap.h>
  24
  25 #include <stdint.h>
  26 #include <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 #define ANIMATE_RANDOM_ACCESS 0
  31
  32 #if ANIMATE_RANDOM_ACCESS
  33
  34 #include <sys/time.h>
  35
  36 typedef int64_t msec_t;
  37
  38 static msec_t time_ms(void)
  39 {
  40         struct timeval tv;
  41         gettimeofday(&tv, NULL);
  42         return (msec_t)tv.tv_sec * 1000 + tv.tv_usec / 1000;
  43 }
  44
  45 #endif
  46
  47 uint32_t rand32_state = 0;
  48
  49 /*
  50  * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
  51  * Uses the BCPL linear congruential generator method.
  52  *
  53  * Note: this method (or maybe just this implementation) seems to
  54  *       go back and forth between odd and even exactly, which can
  55  *       affect low-cardinality testing if the cardinality given is even.
  56  */
  57 static uint32_t rand32(void)
  58 {
  59         rand32_state *= (uint32_t)0x7FF8A3ED;
  60         rand32_state += (uint32_t)0x2AA01D31;
  61         return rand32_state;
  62 }
  63
  64 static void scramble(void *base, size_t nmemb, size_t size)
  65 {
  66         char *i = base;
  67         char *o;
  68         size_t sd;
  69         for (;nmemb>1;nmemb--) {
  70                 o = i + size*(rand32()%nmemb);
  71                 for (sd=size;sd--;) {
  72                         char tmp = *o;
  73                         *o++ = *i;
  74                         *i++ = tmp;
  75                 }
  76         }
  77 }
  78
  79 static struct {
  80         size_t success;
  81         size_t passed_invariants_checks;
  82
  83         size_t excess;
  84         size_t duplicate;
  85         size_t missing;
  86         size_t incorrect;
  87         size_t failed;
  88         size_t failed_invariants_checks;
  89 } stats;
  90
  91 static void clear_stats(void)
  92 {
  93         memset(&stats, 0, sizeof(stats));
  94 }
  95
  96 static bool print_stats(const char *success_label, size_t expected_success)
  97 {
  98         int failed = 0;
  99
 100         printf("      %s:  \t%zu\n", success_label, stats.success);
 101         if (stats.success != expected_success)
 102                 failed = 1;
 103
 104         if (stats.passed_invariants_checks)
 105                 printf("      Passed invariants checks: %zu\n", stats.passed_invariants_checks);
 106
 107         if (stats.excess)
 108                 failed = 1, printf("      Excess:     \t%zu\n", stats.excess);
 109         if (stats.duplicate)
 110                 failed = 1, printf("      Duplicate:  \t%zu\n", stats.duplicate);
 111         if (stats.missing)
 112                 failed = 1, printf("      Missing:    \t%zu\n", stats.missing);
 113         if (stats.incorrect)
 114                 failed = 1, printf("      Incorrect:  \t%zu\n", stats.incorrect);
 115         if (stats.failed)
 116                 failed = 1, printf("      Failed:     \t%zu\n", stats.failed);
 117         if (stats.failed_invariants_checks)
 118                 failed = 1, printf("      Failed invariants checks: %zu\n", stats.failed_invariants_checks);
 119
 120         return !failed;
 121 }
 122
 123 struct test_item {
 124         uint32_t key;
 125         uint32_t value;
 126         size_t   insert_id; /* needed because qsort is not a stable sort */
 127 };
 128
 129 static int compare_uint32_t(const void *ap, const void *bp)
 130 {
 131         uint32_t a = *(const uint32_t *)ap;
 132         uint32_t b = *(const uint32_t *)bp;
 133
 134         if (a < b)
 135                 return -1;
 136         if (a > b)
 137                 return 1;
 138         return 0;
 139 }
 140
 141 static int compare_test_item(const void *ap, const void *bp)
 142 {
 143         const struct test_item *a = *(void**)ap, *b = *(void**)bp;
 144
 145         if (a->key < b->key)
 146                 return -1;
 147         if (a->key > b->key)
 148                 return 1;
 149
 150         if (a->insert_id < b->insert_id)
 151                 return -1;
 152         if (a->insert_id > b->insert_id)
 153                 return 1;
 154
 155         return 0;
 156 }
 157
 158 static bool test_insert_item(AVL *avl, struct test_item *item)
 159 {
 160         avl_insert(avl, &item->key, &item->value);
 161         return true;
 162 }
 163
 164 static bool test_lookup_item(const AVL *avl, const struct test_item *item)
 165 {
 166         return avl_member(avl, &item->key) && avl_lookup(avl, &item->key) == &item->value;
 167 }
 168
 169 static bool test_remove_item(AVL *avl, struct test_item *item)
 170 {
 171         return avl_remove(avl, &item->key);
 172 }
 173
 174 static void test_foreach(AVL *avl, struct test_item **test_items, int count)
 175 {
 176         AvlIter iter;
 177         int     i;
 178
 179         i = 0;
 180         avl_foreach(iter, avl) {
 181                 if (i >= count) {
 182                         stats.excess++;
 183                         continue;
 184                 }
 185                 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
 186                         stats.success++;
 187                 else
 188                         stats.incorrect++;
 189                 i++;
 190         }
 191 }
 192
 193 static void test_foreach_reverse(AVL *avl, struct test_item **test_items, int count)
 194 {
 195         AvlIter iter;
 196         int     i;
 197
 198         i = count - 1;
 199         avl_foreach_reverse(iter, avl) {
 200                 if (i < 0) {
 201                         stats.excess++;
 202                         continue;
 203                 }
 204                 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
 205                         stats.success++;
 206                 else
 207                         stats.incorrect++;
 208                 i--;
 209         }
 210 }
 211
 212 static void benchmark(size_t max_per_trial, size_t round_count, bool random_counts, int cardinality)
 213 {
 214         struct test_item **test_item;
 215         struct test_item *test_item_array;
 216         size_t i, o, count;
 217         size_t round = 0;
 218
 219         test_item = malloc(max_per_trial * sizeof(*test_item));
 220         test_item_array = malloc(max_per_trial * sizeof(*test_item_array));
 221
 222         if (!test_item || !test_item_array) {
 223                 fail("Not enough memory for %zu keys per trial\n",
 224                         max_per_trial);
 225                 return;
 226         }
 227
 228         /* Initialize test_item pointers. */
 229         for (i=0; i<max_per_trial; i++)
 230                 test_item[i] = &test_item_array[i];
 231
 232         /*
 233          * If round_count is not zero, run round_count trials.
 234          * Otherwise, run forever.
 235          */
 236         for (round = 1; round_count==0 || round <= round_count; round++) {
 237                 AVL *avl;
 238
 239                 if (cardinality)
 240                         printf("Round %zu (cardinality = %d)\n", round, cardinality);
 241                 else
 242                         printf("Round %zu\n", round);
 243
 244                 if (random_counts)
 245                         count = rand32() % (max_per_trial+1);
 246                 else
 247                         count = max_per_trial;
 248
 249                 /*
 250                  * Initialize test items by giving them sequential keys and
 251                  * random values. Scramble them so the order of insertion
 252                  * will be random.
 253                  */
 254                 for (i=0; i<count; i++) {
 255                         test_item[i]->key   = rand32();
 256                         test_item[i]->value = rand32();
 257
 258                         if (cardinality)
 259                                 test_item[i]->key %= cardinality;
 260                 }
 261                 scramble(test_item, count, sizeof(*test_item));
 262
 263                 avl = avl_new(compare_uint32_t);
 264
 265                 clear_stats();
 266                 printf("   Inserting %zu items...\n", count);
 267                 for (i=0; i<count; i++) {
 268                         if (test_insert_item(avl, test_item[i])) {
 269                                 stats.success++;
 270                                 test_item[i]->insert_id = i;
 271                         } else {
 272                                 printf("invariants check failed at insertion %zu\n", i);
 273                                 stats.failed++;
 274                         }
 275
 276                         /* Periodically do an invariants check */
 277                         if (count / 10 > 0 && i % (count / 10) == 0) {
 278                                 if (avl_check_invariants(avl))
 279                                         stats.passed_invariants_checks++;
 280                                 else
 281                                         stats.failed_invariants_checks++;
 282                         }
 283                 }
 284                 ok1(print_stats("Inserted", count));
 285                 ok1(avl_check_invariants(avl));
 286
 287                 /* remove early duplicates, as they are shadowed in insertions. */
 288                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
 289                 for (i = 0, o = 0; i < count;) {
 290                         uint32_t k = test_item[i]->key;
 291                         do i++; while (i < count && test_item[i]->key == k);
 292                         test_item[o++] = test_item[i-1];
 293                 }
 294                 count = o;
 295                 ok1(avl_count(avl) == count);
 296
 297                 scramble(test_item, count, sizeof(*test_item));
 298
 299                 printf("   Finding %zu items...\n", count);
 300                 clear_stats();
 301                 for (i=0; i<count; i++) {
 302                         if (!test_lookup_item(avl, test_item[i]))
 303                                 stats.missing++;
 304                         else
 305                                 stats.success++;
 306                 }
 307                 ok1(print_stats("Retrieved", count));
 308
 309                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
 310
 311                 printf("   Traversing forward through %zu items...\n", count);
 312                 clear_stats();
 313                 test_foreach(avl, test_item, count);
 314                 ok1(print_stats("Traversed", count));
 315
 316                 printf("   Traversing backward through %zu items...\n", count);
 317                 clear_stats();
 318                 test_foreach_reverse(avl, test_item, count);
 319                 ok1(print_stats("Traversed", count));
 320
 321                 scramble(test_item, count, sizeof(*test_item));
 322
 323                 printf("   Deleting %zu items...\n", count);
 324                 clear_stats();
 325                 for (i=0; i<count; i++) {
 326                         if (test_remove_item(avl, test_item[i]))
 327                                 stats.success++;
 328                         else
 329                                 stats.missing++;
 330
 331                         /* Periodically do an invariants check */
 332                         if (count / 10 > 0 && i % (count / 10) == 0) {
 333                                 if (avl_check_invariants(avl))
 334                                         stats.passed_invariants_checks++;
 335                                 else
 336                                         stats.failed_invariants_checks++;
 337                         }
 338                 }
 339                 ok1(print_stats("Deleted", count));
 340                 ok1(avl_count(avl) == 0);
 341                 ok1(avl_check_invariants(avl));
 342
 343                 avl_free(avl);
 344         }
 345
 346         free(test_item);
 347         free(test_item_array);
 348 }
 349
 350 static int compare_ptr(const void *a, const void *b)
 351 {
 352         if (a < b)
 353                 return -1;
 354         if (a > b)
 355                 return 1;
 356         return 0;
 357 }
 358
 359 struct fail_total {
 360         int64_t fail;
 361         int64_t total;
 362 };
 363
 364 static bool print_pass_fail(struct fail_total *pf, const char *label)
 365 {
 366         long long fail  = pf->fail,
 367                   total = pf->total;
 368
 369         printf("%s:\t%lld / %lld\n", label, total - fail, total);
 370
 371         return fail == 0;
 372 }
 373
 374 static void test_random_access(uint32_t max, int64_t ops)
 375 {
 376         char       *in_tree;
 377         AVL        *avl;
 378         int64_t     i;
 379         struct {
 380                 struct fail_total
 381                         inserts, lookups, removes, checks;
 382         } s;
 383
 384         #if ANIMATE_RANDOM_ACCESS
 385         msec_t last_update, now;
 386         msec_t interval = 100;
 387         #endif
 388
 389         memset(&s, 0, sizeof(s));
 390
 391         in_tree = malloc(max);
 392         memset(in_tree, 0, max);
 393
 394         avl = avl_new(compare_ptr);
 395
 396         #if ANIMATE_RANDOM_ACCESS
 397         now = time_ms();
 398         last_update = now - interval;
 399         #endif
 400
 401         for (i = 0; i < ops; i++) {
 402                 char *item = &in_tree[rand32() % max];
 403                 char *found;
 404                 bool  inserted, removed;
 405
 406                 #if ANIMATE_RANDOM_ACCESS
 407                 now = time_ms();
 408                 if (now >= last_update + interval) {
 409                         last_update = now;
 410                         printf("\r%.2f%%\t%zu / %zu\033[K", (double)i * 100 / ops, avl_count(avl), max);
 411                         fflush(stdout);
 412                 }
 413                 #endif
 414
 415                 switch (rand32() % 3) {
 416                         case 0:
 417                                 inserted = avl_insert(avl, item, item);
 418
 419                                 if ((*item == 0 && !inserted) ||
 420                                     (*item == 1 && inserted))
 421                                         s.inserts.fail++;
 422
 423                                 if (inserted)
 424                                         *item = 1;
 425
 426                                 s.inserts.total++;
 427                                 break;
 428
 429                         case 1:
 430                                 found = avl_lookup(avl, item);
 431
 432                                 if ((*item == 0 && found != NULL) ||
 433                                     (*item == 1 && found != item) ||
 434                                     (avl_member(avl, item) != !!found))
 435                                         s.lookups.fail++;
 436
 437                                 s.lookups.total++;
 438                                 break;
 439
 440                         case 2:
 441                                 removed = avl_remove(avl, item);
 442
 443                                 if ((*item == 0 && removed) ||
 444                                     (*item == 1 && !removed))
 445                                         s.removes.fail++;
 446
 447                                 if (removed)
 448                                         *item = 0;
 449
 450                                 s.removes.total++;
 451                                 break;
 452                 }
 453
 454                 /* Periodically do an invariants check */
 455                 if (ops / 10 > 0 && i % (ops / 10) == 0) {
 456                         if (!avl_check_invariants(avl))
 457                                 s.checks.fail++;
 458                         s.checks.total++;
 459                 }
 460         }
 461
 462         #if ANIMATE_RANDOM_ACCESS
 463         printf("\r\033[K");
 464         #endif
 465
 466         avl_free(avl);
 467         free(in_tree);
 468
 469         ok1(print_pass_fail(&s.inserts, "Inserts"));
 470         ok1(print_pass_fail(&s.lookups, "Lookups"));
 471         ok1(print_pass_fail(&s.removes, "Removes"));
 472         ok1(print_pass_fail(&s.checks,  "Invariants checks"));
 473 }
 474
 475 int main(void)
 476 {
 477         plan_tests(18 * 3 + 4);
 478
 479         benchmark(100000, 2, false, 0);
 480         benchmark(100000, 2, false, 12345);
 481         benchmark(100000, 2, false, 100001);
 482
 483         printf("Running random access test\n");
 484         test_random_access(12345, 1234567);
 485
 486         return exit_status();
 487 }