tests/libpspp/bt-test.c

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