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