tests/libpspp/bt-test.c

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