tests/libpspp/bt-test.c

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