c_cpp/balancedTree/bt-tmp.c

   1 #include <libpspp/bt.h>
   2
   3 #include <assert.h>
   4 #include <stdbool.h>
   5 #include <stddef.h>
   6 #include <stdint.h>
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <string.h>
  10
  11
  12 /* Exit with a failure code.
  13    (Place a breakpoint on this function while debugging.) */
  14 static void
  15 check_die (void)
  16 {
  17   exit (EXIT_FAILURE);
  18 }
  19
  20 /* If OK is not true, prints a message about failure on the
  21    current source file and the given LINE and terminates. */
  22 static void
  23 check_func (bool ok, int line)
  24 {
  25   if (!ok)
  26     {
  27       fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
  28       check_die ();
  29     }
  30 }
  31
  32 /* Verifies that EXPR evaluates to true.
  33    If not, prints a message citing the calling line number and
  34    terminates. */
  35 #define check(EXPR) check_func ((EXPR), __LINE__)
  36
  37 /* Prints a message about memory exhaustion and exits with a
  38    failure code. */
  39 static void
  40 xalloc_die (void)
  41 {
  42   printf ("virtual memory exhausted\n");
  43   exit (EXIT_FAILURE);
  44 }
  45
  46 /* Allocates and returns N bytes of memory. */
  47 static void *
  48 xmalloc (size_t n)
  49 {
  50   if (n != 0)
  51     {
  52       void *p = malloc (n);
  53       if (p == NULL)
  54         xalloc_die ();
  55
  56       return p;
  57     }
  58   else
  59     return NULL;
  60 }
  61
  62 static void *
  63 xmemdup (const void *p, size_t n)
  64 {
  65   void *q = xmalloc (n);
  66   memcpy (q, p, n);
  67   return q;
  68 }
  69
  70 /* Allocates and returns N * M bytes of memory. */
  71 static void *
  72 xnmalloc (size_t n, size_t m)
  73 {
  74   if ((size_t) -1 / m <= n)
  75     xalloc_die ();
  76   return xmalloc (n * m);
  77 }
  78 \f
  79 /* Node type and support routines. */
  80
  81 /* Test data element. */
  82 struct element
  83   {
  84     struct bt_node node;        /* Embedded binary tree element. */
  85     int data;                   /* Primary value. */
  86   };
  87
  88 static int aux_data;
  89
  90 /* Returns the `struct element' that NODE is embedded within. */
  91 static struct element *
  92 bt_node_to_element (const struct bt_node *node)
  93 {
  94   return bt_data (node, struct element, node);
  95 }
  96
  97 /* Compares the `x' values in A and B and returns a strcmp-type
  98    return value.  Verifies that AUX points to aux_data. */
  99 static int
 100 compare_elements (const struct bt_node *a_, const struct bt_node *b_,
 101                   const void *aux)
 102 {
 103   const struct element *a = bt_node_to_element (a_);
 104   const struct element *b = bt_node_to_element (b_);
 105
 106   check (aux == &aux_data);
 107   return a->data < b->data ? -1 : a->data > b->data;
 108 }
 109
 110 /* Compares A and B and returns a strcmp-type return value. */
 111 static int
 112 compare_ints_noaux (const void *a_, const void *b_)
 113 {
 114   const int *a = a_;
 115   const int *b = b_;
 116
 117   return *a < *b ? -1 : *a > *b;
 118 }
 119
 120 /* Swaps *A and *B. */
 121 static void
 122 swap (int *a, int *b)
 123 {
 124   int t = *a;
 125   *a = *b;
 126   *b = t;
 127 }
 128
 129 /* Reverses the order of the CNT integers starting at VALUES. */
 130 static void
 131 reverse (int *values, size_t cnt)
 132 {
 133   size_t i = 0;
 134   size_t j = cnt;
 135
 136   while (j > i)
 137     swap (&values[i++], &values[--j]);
 138 }
 139
 140 /* Arranges the CNT elements in VALUES into the lexicographically
 141    next greater permutation.  Returns true if successful.
 142    If VALUES is already the lexicographically greatest
 143    permutation of its elements (i.e. ordered from greatest to
 144    smallest), arranges them into the lexicographically least
 145    permutation (i.e. ordered from smallest to largest) and
 146    returns false. */
 147 static bool
 148 next_permutation (int *values, size_t cnt)
 149 {
 150   if (cnt > 0)
 151     {
 152       size_t i = cnt - 1;
 153       while (i != 0)
 154         {
 155           i--;
 156           if (values[i] < values[i + 1])
 157             {
 158               size_t j;
 159               for (j = cnt - 1; values[i] >= values[j]; j--)
 160                 continue;
 161               swap (values + i, values + j);
 162               reverse (values + (i + 1), cnt - (i + 1));
 163               return true;
 164             }
 165         }
 166
 167       reverse (values, cnt);
 168     }
 169
 170   return false;
 171 }
 172
 173 /* Returns N!. */
 174 static unsigned int
 175 factorial (unsigned int n)
 176 {
 177   unsigned int value = 1;
 178   while (n > 1)
 179     value *= n--;
 180   return value;
 181 }
 182
 183 /* Randomly shuffles the CNT elements in ARRAY, each of which is
 184    SIZE bytes in size. */
 185 static void
 186 random_shuffle (void *array_, size_t cnt, size_t size)
 187 {
 188   char *array = array_;
 189   char *tmp = xmalloc (size);
 190   size_t i;
 191
 192   for (i = 0; i < cnt; i++)
 193     {
 194       size_t j = rand () % (cnt - i) + i;
 195       if (i != j)
 196         {
 197           memcpy (tmp, array + j * size, size);
 198           memcpy (array + j * size, array + i * size, size);
 199           memcpy (array + i * size, tmp, size);
 200         }
 201     }
 202
 203   free (tmp);
 204 }
 205
 206 /* Calculates floor(log(n)/log(sqrt(2))). */
 207 static int
 208 calculate_h_alpha (size_t n)
 209 {
 210   size_t thresholds[] =
 211     {
 212       0, 2, 2, 3, 4, 6, 8, 12, 16, 23, 32, 46, 64, 91, 128, 182, 256, 363,
 213       512, 725, 1024, 1449, 2048, 2897, 4096, 5793, 8192, 11586, 16384,
 214       23171, 32768, 46341, 65536, 92682, 131072, 185364, 262144, 370728,
 215       524288, 741456, 1048576, 1482911, 2097152, 2965821, 4194304, 5931642,
 216       8388608, 11863284, 16777216, 23726567, 33554432, 47453133, 67108864,
 217       94906266, 134217728, 189812532, 268435456, 379625063, 536870912,
 218       759250125, 1073741824, 1518500250, 2147483648, 3037000500,
 219     };
 220   size_t threshold_cnt = sizeof thresholds / sizeof *thresholds;
 221   size_t i;
 222
 223   for (i = 0; i < threshold_cnt; i++)
 224     if (thresholds[i] > n)
 225       break;
 226   return i - 1;
 227 }
 228
 229 /* Returns the height of the tree rooted at NODE. */
 230 static int
 231 get_height (struct bt_node *node)
 232 {
 233   if (node == NULL)
 234     return 0;
 235   else
 236     {
 237       int left = get_height (node->down[0]);
 238       int right = get_height (node->down[1]);
 239       return 1 + (left > right ? left : right);
 240     }
 241 }
 242
 243 /* Checks that BT is loosely alpha-height balanced, that is, that
 244    its height is no more than h_alpha(count) + 1, where
 245    h_alpha(n) = floor(log(n)/log(1/alpha)). */
 246 static void
 247 check_balance (struct bt *bt)
 248 {
 249   /* In the notation of the Galperin and Rivest paper (and of
 250      CLR), the height of a tree is the number of edges in the
 251      longest path from the root to a leaf, so we have to subtract
 252      1 from our measured height. */
 253   int height = get_height (bt->root) - 1;
 254   int max_height = calculate_h_alpha (bt_count (bt)) + 1;
 255   check (height <= max_height);
 256 }
 257
 258 /* Checks that BT contains the CNT ints in DATA, that its
 259    structure is correct, and that certain operations on BT
 260    produce the expected results. */
 261 static void
 262 check_bt (struct bt *bt, const int data[], size_t cnt)
 263 {
 264   struct element e;
 265   size_t i;
 266   int *order;
 267
 268   order = xmemdup (data, cnt * sizeof *data);
 269   qsort (order, cnt, sizeof *order, compare_ints_noaux);
 270
 271   for (i = 0; i < cnt; i++)
 272     {
 273       struct bt_node *p;
 274
 275       e.data = data[i];
 276       if (rand () % 2)
 277         p = bt_find (bt, &e.node);
 278       else
 279         p = bt_insert (bt, &e.node);
 280       check (p != NULL);
 281       check (p != &e.node);
 282       check (bt_node_to_element (p)->data == data[i]);
 283     }
 284
 285   e.data = -1;
 286   check (bt_find (bt, &e.node) == NULL);
 287
 288   check_balance (bt);
 289
 290   if (cnt == 0)
 291     {
 292       check (bt_first (bt) == NULL);
 293       check (bt_last (bt) == NULL);
 294       check (bt_next (bt, NULL) == NULL);
 295       check (bt_prev (bt, NULL) == NULL);
 296     }
 297   else
 298     {
 299       struct bt_node *p;
 300
 301       for (p = bt_first (bt), i = 0; i < cnt; p = bt_next (bt, p), i++)
 302         check (bt_node_to_element (p)->data == order[i]);
 303       check (p == NULL);
 304
 305       for (p = bt_last (bt), i = 0; i < cnt; p = bt_prev (bt, p), i++)
 306         check (bt_node_to_element (p)->data == order[cnt - i - 1]);
 307       check (p == NULL);
 308     }
 309
 310   free (order);
 311 }
 312
 313 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
 314    BT in the order specified by INSERTIONS, then deletes them in
 315    the order specified by DELETIONS, checking the BT's contents
 316    for correctness after each operation. */
 317 static void
 318 test_insert_delete (const int insertions[],
 319                     const int deletions[],
 320                     size_t cnt)
 321 {
 322   struct element *elements;
 323   struct bt bt;
 324   size_t i;
 325
 326   elements = xnmalloc (cnt, sizeof *elements);
 327   for (i = 0; i < cnt; i++)
 328     elements[i].data = i;
 329
 330   bt_init (&bt, compare_elements, &aux_data);
 331   check_bt (&bt, NULL, 0);
 332   for (i = 0; i < cnt; i++)
 333     {
 334       check (bt_insert (&bt, &elements[insertions[i]].node) == NULL);
 335       check_bt (&bt, insertions, i + 1);
 336     }
 337   for (i = 0; i < cnt; i++)
 338     {
 339       bt_delete (&bt, &elements[deletions[i]].node);
 340       check_bt (&bt, deletions + i + 1, cnt - i - 1);
 341     }
 342
 343   free (elements);
 344 }
 345 \f
 346 /* Inserts values into an BT in each possible order, then
 347    removes them in each possible order, up to a specified maximum
 348    size. */
 349 static void
 350 test_insert_any_remove_any (void)
 351 {
 352   const int max_elems = 5;
 353   int cnt;
 354
 355   for (cnt = 0; cnt <= max_elems; cnt++)
 356     {
 357       int *insertions, *deletions;
 358       unsigned int ins_perm_cnt;
 359       int i;
 360
 361       insertions = xnmalloc (cnt, sizeof *insertions);
 362       deletions = xnmalloc (cnt, sizeof *deletions);
 363       for (i = 0; i < cnt; i++)
 364         insertions[i] = i;
 365
 366       for (ins_perm_cnt = 0;
 367            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
 368            ins_perm_cnt++)
 369         {
 370           unsigned int del_perm_cnt;
 371           int i;
 372
 373           for (i = 0; i < cnt; i++)
 374             deletions[i] = i;
 375
 376           for (del_perm_cnt = 0;
 377                del_perm_cnt == 0 || next_permutation (deletions, cnt);
 378                del_perm_cnt++)
 379             test_insert_delete (insertions, deletions, cnt);
 380
 381           check (del_perm_cnt == factorial (cnt));
 382         }
 383       check (ins_perm_cnt == factorial (cnt));
 384
 385       free (insertions);
 386       free (deletions);
 387     }
 388 }
 389
 390 /* Inserts values into an BT in each possible order, then
 391    removes them in the same order, up to a specified maximum
 392    size. */
 393 static void
 394 test_insert_any_remove_same (void)
 395 {
 396   const int max_elems = 7;
 397   int cnt;
 398
 399   for (cnt = 0; cnt <= max_elems; cnt++)
 400     {
 401       int *values;
 402       unsigned int permutation_cnt;
 403       int i;
 404
 405       values = xnmalloc (cnt, sizeof *values);
 406       for (i = 0; i < cnt; i++)
 407         values[i] = i;
 408
 409       for (permutation_cnt = 0;
 410            permutation_cnt == 0 || next_permutation (values, cnt);
 411            permutation_cnt++)
 412         test_insert_delete (values, values, cnt);
 413       check (permutation_cnt == factorial (cnt));
 414
 415       free (values);
 416     }
 417 }
 418
 419 /* Inserts values into an BT in each possible order, then
 420    removes them in reverse order, up to a specified maximum
 421    size. */
 422 static void
 423 test_insert_any_remove_reverse (void)
 424 {
 425   const int max_elems = 7;
 426   int cnt;
 427
 428   for (cnt = 0; cnt <= max_elems; cnt++)
 429     {
 430       int *insertions, *deletions;
 431       unsigned int permutation_cnt;
 432       int i;
 433
 434       insertions = xnmalloc (cnt, sizeof *insertions);
 435       deletions = xnmalloc (cnt, sizeof *deletions);
 436       for (i = 0; i < cnt; i++)
 437         insertions[i] = i;
 438
 439       for (permutation_cnt = 0;
 440            permutation_cnt == 0 || next_permutation (insertions, cnt);
 441            permutation_cnt++)
 442         {
 443           memcpy (deletions, insertions, sizeof *insertions * cnt);
 444           reverse (deletions, cnt);
 445
 446           test_insert_delete (insertions, deletions, cnt);
 447         }
 448       check (permutation_cnt == factorial (cnt));
 449
 450       free (insertions);
 451       free (deletions);
 452     }
 453 }
 454
 455 /* Inserts and removes values in an BT in random orders. */
 456 static void
 457 test_random_sequence (void)
 458 {
 459   const int max_elems = 128;
 460   const int max_trials = 8;
 461   int cnt;
 462
 463   for (cnt = 0; cnt <= max_elems; cnt += 2)
 464     {
 465       int *insertions, *deletions;
 466       int trial;
 467       int i;
 468
 469       insertions = xnmalloc (cnt, sizeof *insertions);
 470       deletions = xnmalloc (cnt, sizeof *deletions);
 471       for (i = 0; i < cnt; i++)
 472         insertions[i] = i;
 473       for (i = 0; i < cnt; i++)
 474         deletions[i] = i;
 475
 476       for (trial = 0; trial < max_trials; trial++)
 477         {
 478           random_shuffle (insertions, cnt, sizeof *insertions);
 479           random_shuffle (deletions, cnt, sizeof *deletions);
 480
 481           test_insert_delete (insertions, deletions, cnt);
 482         }
 483
 484       free (insertions);
 485       free (deletions);
 486     }
 487 }
 488
 489 /* Inserts elements into an BT in ascending order. */
 490 static void
 491 test_insert_ordered (void)
 492 {
 493   const int max_elems = 1024;
 494   struct element *elements;
 495   int *values;
 496   struct bt bt;
 497   int i;
 498
 499   bt_init (&bt, compare_elements, &aux_data);
 500   elements = xnmalloc (max_elems, sizeof *elements);
 501   values = xnmalloc (max_elems, sizeof *values);
 502   for (i = 0; i < max_elems; i++)
 503     {
 504       values[i] = elements[i].data = i;
 505       check (bt_insert (&bt, &elements[i].node) == NULL);
 506       check_bt (&bt, values, i + 1);
 507     }
 508   free (elements);
 509   free (values);
 510 }
 511
 512 /* Tests bt_find_ge and bt_find_le. */
 513 static void
 514 test_find_ge_le (void)
 515 {
 516   const int max_elems = 10;
 517   struct element *elements;
 518   int *values;
 519   unsigned int inc_pat;
 520
 521   elements = xnmalloc (max_elems, sizeof *elements);
 522   values = xnmalloc (max_elems, sizeof *values);
 523   for (inc_pat = 0; inc_pat < (1u << max_elems); inc_pat++)
 524     {
 525       struct bt bt;
 526       int elem_cnt = 0;
 527       int i;
 528
 529       /* Insert the values in the pattern into BT. */
 530       bt_init (&bt, compare_elements, &aux_data);
 531       for (i = 0; i < max_elems; i++)
 532         if (inc_pat & (1u << i))
 533           {
 534             values[elem_cnt] = elements[elem_cnt].data = i;
 535             check (bt_insert (&bt, &elements[elem_cnt].node) == NULL);
 536             elem_cnt++;
 537           }
 538       check_bt (&bt, values, elem_cnt);
 539
 540       /* Try find_ge and find_le for each possible element value. */
 541       for (i = -1; i <= max_elems; i++)
 542         {
 543           struct element tmp;
 544           struct bt_node *ge, *le;
 545           int j;
 546
 547           ge = le = NULL;
 548           for (j = 0; j < elem_cnt; j++)
 549             {
 550               if (ge == NULL && values[j] >= i)
 551                 ge = &elements[j].node;
 552               if (values[j] <= i)
 553                 le = &elements[j].node;
 554             }
 555
 556           tmp.data = i;
 557           check (bt_find_ge (&bt, &tmp.node) == ge);
 558           check (bt_find_le (&bt, &tmp.node) == le);
 559         }
 560     }
 561   free (elements);
 562   free (values);
 563 }
 564
 565 /* Inserts elements into an BT, then moves the nodes around in
 566    memory. */
 567 static void
 568 test_moved (void)
 569 {
 570   const int max_elems = 128;
 571   struct element *e[2];
 572   int cur;
 573   int *values;
 574   struct bt bt;
 575   int i, j;
 576
 577   bt_init (&bt, compare_elements, &aux_data);
 578   e[0] = xnmalloc (max_elems, sizeof *e[0]);
 579   e[1] = xnmalloc (max_elems, sizeof *e[1]);
 580   values = xnmalloc (max_elems, sizeof *values);
 581   cur = 0;
 582   for (i = 0; i < max_elems; i++)
 583     {
 584       values[i] = e[cur][i].data = i;
 585       check (bt_insert (&bt, &e[cur][i].node) == NULL);
 586       check_bt (&bt, values, i + 1);
 587
 588       for (j = 0; j <= i; j++)
 589         {
 590           e[!cur][j] = e[cur][j];
 591           bt_moved (&bt, &e[!cur][j].node);
 592           check_bt (&bt, values, i + 1);
 593         }
 594       cur = !cur;
 595     }
 596   free (e[0]);
 597   free (e[1]);
 598   free (values);
 599 }
 600
 601 /* Inserts values into an BT, then changes their values. */
 602 static void
 603 test_changed (void)
 604 {
 605   const int max_elems = 6;
 606   int cnt;
 607
 608   for (cnt = 0; cnt <= max_elems; cnt++)
 609     {
 610       int *values, *changed_values;
 611       struct element *elements;
 612       unsigned int permutation_cnt;
 613       int i;
 614
 615       values = xnmalloc (cnt, sizeof *values);
 616       changed_values = xnmalloc (cnt, sizeof *changed_values);
 617       elements = xnmalloc (cnt, sizeof *elements);
 618       for (i = 0; i < cnt; i++)
 619         values[i] = i;
 620
 621       for (permutation_cnt = 0;
 622            permutation_cnt == 0 || next_permutation (values, cnt);
 623            permutation_cnt++)
 624         {
 625           for (i = 0; i < cnt; i++)
 626             {
 627               int j, k;
 628               for (j = 0; j <= cnt; j++)
 629                 {
 630                   struct bt bt;
 631                   struct bt_node *changed_retval;
 632
 633                   bt_init (&bt, compare_elements, &aux_data);
 634
 635                   /* Add to BT in order. */
 636                   for (k = 0; k < cnt; k++)
 637                     {
 638                       int n = values[k];
 639                       elements[n].data = n;
 640                       check (bt_insert (&bt, &elements[n].node) == NULL);
 641                     }
 642                   check_bt (&bt, values, cnt);
 643
 644                   /* Change value i to j. */
 645                   elements[i].data = j;
 646                   for (k = 0; k < cnt; k++)
 647                     changed_values[k] = k;
 648                   changed_retval = bt_changed (&bt, &elements[i].node);
 649                   if (i != j && j < cnt)
 650                     {
 651                       /* Will cause duplicate. */
 652                       check (changed_retval == &elements[j].node);
 653                       changed_values[i] = changed_values[cnt - 1];
 654                       check_bt (&bt, changed_values, cnt - 1);
 655                     }
 656                   else
 657                     {
 658                       /* Succeeds. */
 659                       check (changed_retval == NULL);
 660                       changed_values[i] = j;
 661                       check_bt (&bt, changed_values, cnt);
 662                     }
 663                 }
 664             }
 665         }
 666       check (permutation_cnt == factorial (cnt));
 667
 668       free (values);
 669       free (changed_values);
 670       free (elements);
 671     }
 672 }
 673 \f
 674 /* Main program. */
 675
 676 struct test
 677   {
 678     const char *name;
 679     const char *description;
 680     void (*function) (void);
 681   };
 682
 683 static const struct test tests[] =
 684   {
 685     {
 686       "insert-any-remove-any",
 687       "insert any order, delete any order",
 688       test_insert_any_remove_any
 689     },
 690     {
 691       "insert-any-remove-same",
 692       "insert any order, delete same order",
 693       test_insert_any_remove_same
 694     },
 695     {
 696       "insert-any-remove-reverse",
 697       "insert any order, delete reverse order",
 698       test_insert_any_remove_reverse
 699     },
 700     {
 701       "random-sequence",
 702       "insert and delete in random sequence",
 703       test_random_sequence
 704     },
 705     {
 706       "insert-ordered",
 707       "insert in ascending order",
 708       test_insert_ordered
 709     },
 710     {
 711       "find-ge-le",
 712       "find_ge and find_le",
 713       test_find_ge_le
 714     },
 715       {
 716       "moved",
 717       "move elements around in memory",
 718       test_moved
 719     },
 720     {
 721       "changed",
 722       "change key data in nodes",
 723       test_changed
 724     }
 725   };
 726
 727 enum { N_TESTS = sizeof tests / sizeof *tests };
 728
 729 int
 730 main (int argc, char *argv[])
 731 {
 732   int i;
 733
 734   if (argc != 2)
 735     {
 736       fprintf (stderr, "exactly one argument required; use --help for help\n");
 737       return EXIT_FAILURE;
 738     }
 739   else if (!strcmp (argv[1], "--help"))
 740     {
 741       printf ("%s: test balanced tree\n"
 742               "usage: %s TEST-NAME\n"
 743               "where TEST-NAME is one of the following:\n",
 744               argv[0], argv[0]);
 745       for (i = 0; i < N_TESTS; i++)
 746         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
 747       return 0;
 748     }
 749   else
 750     {
 751       for (i = 0; i < N_TESTS; i++)
 752         if (!strcmp (argv[1], tests[i].name))
 753           {
 754             tests[i].function ();
 755             return 0;
 756           }
 757
 758       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
 759       return EXIT_FAILURE;
 760     }
 761 }