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_test_item(const void *ap, const void *bp)
 136 {
 137         const struct test_item *a = *(void**)ap, *b = *(void**)bp;
 138
 139         if (a->key < b->key)
 140                 return -1;
 141         if (a->key > b->key)
 142                 return 1;
 143
 144         if (a->insert_id < b->insert_id)
 145                 return -1;
 146         if (a->insert_id > b->insert_id)
 147                 return 1;
 148
 149         return 0;
 150 }
 151
 152 static bool test_insert_item(AVL *avl, struct test_item *item)
 153 {
 154         avl_insert(avl, &item->key, &item->value);
 155         return true;
 156 }
 157
 158 static bool test_lookup_item(const AVL *avl, const struct test_item *item)
 159 {
 160         return avl_member(avl, &item->key) && avl_lookup(avl, &item->key) == &item->value;
 161 }
 162
 163 static bool test_remove_item(AVL *avl, struct test_item *item)
 164 {
 165         return avl_remove(avl, &item->key);
 166 }
 167
 168 static void test_foreach(AVL *avl, struct test_item **test_items, int count)
 169 {
 170         AvlIter iter;
 171         int     i;
 172
 173         i = 0;
 174         avl_foreach(iter, avl) {
 175                 if (i >= count) {
 176                         stats.excess++;
 177                         continue;
 178                 }
 179                 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
 180                         stats.success++;
 181                 else
 182                         stats.incorrect++;
 183                 i++;
 184         }
 185 }
 186
 187 static void test_foreach_reverse(AVL *avl, struct test_item **test_items, int count)
 188 {
 189         AvlIter iter;
 190         int     i;
 191
 192         i = count - 1;
 193         avl_foreach_reverse(iter, avl) {
 194                 if (i < 0) {
 195                         stats.excess++;
 196                         continue;
 197                 }
 198                 if (iter.key == &test_items[i]->key && iter.value == &test_items[i]->value)
 199                         stats.success++;
 200                 else
 201                         stats.incorrect++;
 202                 i--;
 203         }
 204 }
 205
 206 static void benchmark(size_t max_per_trial, size_t round_count, bool random_counts, int cardinality)
 207 {
 208         struct test_item **test_item;
 209         struct test_item *test_item_array;
 210         size_t i, o, count;
 211         size_t round = 0;
 212
 213         test_item = malloc(max_per_trial * sizeof(*test_item));
 214         test_item_array = malloc(max_per_trial * sizeof(*test_item_array));
 215
 216         if (!test_item || !test_item_array) {
 217                 fail("Not enough memory for %zu keys per trial\n",
 218                         max_per_trial);
 219                 return;
 220         }
 221
 222         /* Initialize test_item pointers. */
 223         for (i=0; i<max_per_trial; i++)
 224                 test_item[i] = &test_item_array[i];
 225
 226         /*
 227          * If round_count is not zero, run round_count trials.
 228          * Otherwise, run forever.
 229          */
 230         for (round = 1; round_count==0 || round <= round_count; round++) {
 231                 AVL *avl;
 232
 233                 if (cardinality)
 234                         printf("Round %zu (cardinality = %d)\n", round, cardinality);
 235                 else
 236                         printf("Round %zu\n", round);
 237
 238                 if (random_counts)
 239                         count = rand32() % (max_per_trial+1);
 240                 else
 241                         count = max_per_trial;
 242
 243                 /*
 244                  * Initialize test items by giving them sequential keys and
 245                  * random values. Scramble them so the order of insertion
 246                  * will be random.
 247                  */
 248                 for (i=0; i<count; i++) {
 249                         test_item[i]->key   = rand32();
 250                         test_item[i]->value = rand32();
 251
 252                         if (cardinality)
 253                                 test_item[i]->key %= cardinality;
 254                 }
 255                 scramble(test_item, count, sizeof(*test_item));
 256
 257                 avl = avl_new(order_u32_noctx);
 258
 259                 clear_stats();
 260                 printf("   Inserting %zu items...\n", count);
 261                 for (i=0; i<count; i++) {
 262                         if (test_insert_item(avl, test_item[i])) {
 263                                 stats.success++;
 264                                 test_item[i]->insert_id = i;
 265                         } else {
 266                                 printf("invariants check failed at insertion %zu\n", i);
 267                                 stats.failed++;
 268                         }
 269
 270                         /* Periodically do an invariants check */
 271                         if (count / 10 > 0 && i % (count / 10) == 0) {
 272                                 if (avl_check_invariants(avl))
 273                                         stats.passed_invariants_checks++;
 274                                 else
 275                                         stats.failed_invariants_checks++;
 276                         }
 277                 }
 278                 ok1(print_stats("Inserted", count));
 279                 ok1(avl_check_invariants(avl));
 280
 281                 /* remove early duplicates, as they are shadowed in insertions. */
 282                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
 283                 for (i = 0, o = 0; i < count;) {
 284                         uint32_t k = test_item[i]->key;
 285                         do i++; while (i < count && test_item[i]->key == k);
 286                         test_item[o++] = test_item[i-1];
 287                 }
 288                 count = o;
 289                 ok1(avl_count(avl) == count);
 290
 291                 scramble(test_item, count, sizeof(*test_item));
 292
 293                 printf("   Finding %zu items...\n", count);
 294                 clear_stats();
 295                 for (i=0; i<count; i++) {
 296                         if (!test_lookup_item(avl, test_item[i]))
 297                                 stats.missing++;
 298                         else
 299                                 stats.success++;
 300                 }
 301                 ok1(print_stats("Retrieved", count));
 302
 303                 qsort(test_item, count, sizeof(*test_item), compare_test_item);
 304
 305                 printf("   Traversing forward through %zu items...\n", count);
 306                 clear_stats();
 307                 test_foreach(avl, test_item, count);
 308                 ok1(print_stats("Traversed", count));
 309
 310                 printf("   Traversing backward through %zu items...\n", count);
 311                 clear_stats();
 312                 test_foreach_reverse(avl, test_item, count);
 313                 ok1(print_stats("Traversed", count));
 314
 315                 scramble(test_item, count, sizeof(*test_item));
 316
 317                 printf("   Deleting %zu items...\n", count);
 318                 clear_stats();
 319                 for (i=0; i<count; i++) {
 320                         if (test_remove_item(avl, test_item[i]))
 321                                 stats.success++;
 322                         else
 323                                 stats.missing++;
 324
 325                         /* Periodically do an invariants check */
 326                         if (count / 10 > 0 && i % (count / 10) == 0) {
 327                                 if (avl_check_invariants(avl))
 328                                         stats.passed_invariants_checks++;
 329                                 else
 330                                         stats.failed_invariants_checks++;
 331                         }
 332                 }
 333                 ok1(print_stats("Deleted", count));
 334                 ok1(avl_count(avl) == 0);
 335                 ok1(avl_check_invariants(avl));
 336
 337                 avl_free(avl);
 338         }
 339
 340         free(test_item);
 341         free(test_item_array);
 342 }
 343
 344 static int compare_ptr(const void *a, const void *b)
 345 {
 346         if (a < b)
 347                 return -1;
 348         if (a > b)
 349                 return 1;
 350         return 0;
 351 }
 352
 353 struct fail_total {
 354         int64_t fail;
 355         int64_t total;
 356 };
 357
 358 static bool print_pass_fail(struct fail_total *pf, const char *label)
 359 {
 360         long long fail  = pf->fail,
 361                   total = pf->total;
 362
 363         printf("%s:\t%lld / %lld\n", label, total - fail, total);
 364
 365         return fail == 0;
 366 }
 367
 368 static void test_random_access(uint32_t max, int64_t ops)
 369 {
 370         char       *in_tree;
 371         AVL        *avl;
 372         int64_t     i;
 373         struct {
 374                 struct fail_total
 375                         inserts, lookups, removes, checks;
 376         } s;
 377
 378         #if ANIMATE_RANDOM_ACCESS
 379         msec_t last_update, now;
 380         msec_t interval = 100;
 381         #endif
 382
 383         memset(&s, 0, sizeof(s));
 384
 385         in_tree = malloc(max);
 386         memset(in_tree, 0, max);
 387
 388         avl = avl_new(compare_ptr);
 389
 390         #if ANIMATE_RANDOM_ACCESS
 391         now = time_ms();
 392         last_update = now - interval;
 393         #endif
 394
 395         for (i = 0; i < ops; i++) {
 396                 char *item = &in_tree[rand32() % max];
 397                 char *found;
 398                 bool  inserted, removed;
 399
 400                 #if ANIMATE_RANDOM_ACCESS
 401                 now = time_ms();
 402                 if (now >= last_update + interval) {
 403                         last_update = now;
 404                         printf("\r%.2f%%\t%zu / %zu\033[K", (double)i * 100 / ops, avl_count(avl), max);
 405                         fflush(stdout);
 406                 }
 407                 #endif
 408
 409                 switch (rand32() % 3) {
 410                         case 0:
 411                                 inserted = avl_insert(avl, item, item);
 412
 413                                 if ((*item == 0 && !inserted) ||
 414                                     (*item == 1 && inserted))
 415                                         s.inserts.fail++;
 416
 417                                 if (inserted)
 418                                         *item = 1;
 419
 420                                 s.inserts.total++;
 421                                 break;
 422
 423                         case 1:
 424                                 found = avl_lookup(avl, item);
 425
 426                                 if ((*item == 0 && found != NULL) ||
 427                                     (*item == 1 && found != item) ||
 428                                     (avl_member(avl, item) != !!found))
 429                                         s.lookups.fail++;
 430
 431                                 s.lookups.total++;
 432                                 break;
 433
 434                         case 2:
 435                                 removed = avl_remove(avl, item);
 436
 437                                 if ((*item == 0 && removed) ||
 438                                     (*item == 1 && !removed))
 439                                         s.removes.fail++;
 440
 441                                 if (removed)
 442                                         *item = 0;
 443
 444                                 s.removes.total++;
 445                                 break;
 446                 }
 447
 448                 /* Periodically do an invariants check */
 449                 if (ops / 10 > 0 && i % (ops / 10) == 0) {
 450                         if (!avl_check_invariants(avl))
 451                                 s.checks.fail++;
 452                         s.checks.total++;
 453                 }
 454         }
 455
 456         #if ANIMATE_RANDOM_ACCESS
 457         printf("\r\033[K");
 458         #endif
 459
 460         avl_free(avl);
 461         free(in_tree);
 462
 463         ok1(print_pass_fail(&s.inserts, "Inserts"));
 464         ok1(print_pass_fail(&s.lookups, "Lookups"));
 465         ok1(print_pass_fail(&s.removes, "Removes"));
 466         ok1(print_pass_fail(&s.checks,  "Invariants checks"));
 467 }
 468
 469 int main(void)
 470 {
 471         plan_tests(18 * 3 + 4);
 472
 473         benchmark(100000, 2, false, 0);
 474         benchmark(100000, 2, false, 12345);
 475         benchmark(100000, 2, false, 100001);
 476
 477         printf("Running random access test\n");
 478         test_random_access(12345, 1234567);
 479
 480         return exit_status();
 481 }