tests/libpspp/heap-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2010, 2012 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 routines defined in heap.c.
  18    This test program aims to be as comprehensive as possible.
  19    With -DNDEBUG, "gcov -b" should report 100% coverage of lines
  20    and branches in heap.c routines, except for the is_heap
  21    function, which is not called at all with -DNDEBUG.  (Without
  22    -DNDEBUG, branches caused by failed assertions will also not
  23    be taken.)  "valgrind --leak-check=yes --show-reachable=yes"
  24    should give a clean report, both with and without -DNDEBUG. */
  25
  26 #ifdef HAVE_CONFIG_H
  27 #include <config.h>
  28 #endif
  29
  30 #include <libpspp/heap.h>
  31
  32 #include <assert.h>
  33 #include <limits.h>
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <string.h>
  37
  38 #include <libpspp/compiler.h>
  39
  40 #include "xalloc.h"
  41 \f
  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       fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
  58       check_die ();
  59     }
  60 }
  61
  62 /* Verifies that EXPR evaluates to true.
  63    If not, prints a message citing the calling line number and
  64    terminates. */
  65 #define check(EXPR) check_func ((EXPR), __LINE__)
  66 \f
  67 /* Node type and support routines. */
  68
  69 /* Test data element. */
  70 struct element
  71   {
  72     struct heap_node node;      /* Embedded heap element. */
  73     int x;                      /* Primary value. */
  74   };
  75
  76 static int aux_data;
  77
  78 /* Returns the `struct element' that NODE is embedded within. */
  79 static struct element *
  80 heap_node_to_element (const struct heap_node *node)
  81 {
  82   return heap_data (node, struct element, node);
  83 }
  84
  85 /* Compares the `x' values in A and B and returns a strcmp-type
  86    return value.  Verifies that AUX points to aux_data. */
  87 static int
  88 compare_elements (const struct heap_node *a_, const struct heap_node *b_,
  89                   const void *aux)
  90 {
  91   const struct element *a = heap_node_to_element (a_);
  92   const struct element *b = heap_node_to_element (b_);
  93
  94   check (aux == &aux_data);
  95   return a->x < b->x ? -1 : a->x > b->x;
  96 }
  97
  98 /* Returns the smallest of the N integers in ARRAY. */
  99 static int
 100 min_int (int *array, size_t n)
 101 {
 102   int min;
 103   size_t i;
 104
 105   min = INT_MAX;
 106   for (i = 0; i < n; i++)
 107     if (array[i] < min)
 108       min = array[i];
 109   return min;
 110 }
 111
 112 /* Swaps *A and *B. */
 113 static void
 114 swap (int *a, int *b)
 115 {
 116   int t = *a;
 117   *a = *b;
 118   *b = t;
 119 }
 120
 121 /* Reverses the order of the N integers starting at VALUES. */
 122 static void
 123 reverse (int *values, size_t n)
 124 {
 125   size_t i = 0;
 126   size_t j = n;
 127
 128   while (j > i)
 129     swap (&values[i++], &values[--j]);
 130 }
 131
 132 /* Arranges the N elements in VALUES into the lexicographically
 133    next greater permutation.  Returns true if successful.
 134    If VALUES is already the lexicographically greatest
 135    permutation of its elements (i.e. ordered from greatest to
 136    smallest), arranges them into the lexicographically least
 137    permutation (i.e. ordered from smallest to largest) and
 138    returns false. */
 139 static bool
 140 next_permutation (int *values, size_t n)
 141 {
 142   if (n > 0)
 143     {
 144       size_t i = n - 1;
 145       while (i != 0)
 146         {
 147           i--;
 148           if (values[i] < values[i + 1])
 149             {
 150               size_t j;
 151               for (j = n - 1; values[i] >= values[j]; j--)
 152                 continue;
 153               swap (values + i, values + j);
 154               reverse (values + (i + 1), n - (i + 1));
 155               return true;
 156             }
 157         }
 158
 159       reverse (values, n);
 160     }
 161
 162   return false;
 163 }
 164
 165 /* Returns N!. */
 166 static unsigned int
 167 factorial (unsigned int n)
 168 {
 169   unsigned int value = 1;
 170   while (n > 1)
 171     value *= n--;
 172   return value;
 173 }
 174
 175 /* Returns the number of permutations of the N values in
 176    VALUES.  If VALUES contains duplicates, they must be
 177    adjacent. */
 178 static unsigned int
 179 expected_perms (int *values, size_t n)
 180 {
 181   size_t i, j;
 182   unsigned int n_perms;
 183
 184   n_perms = factorial (n);
 185   for (i = 0; i < n; i = j)
 186     {
 187       for (j = i + 1; j < n; j++)
 188         if (values[i] != values[j])
 189           break;
 190       n_perms /= factorial (j - i);
 191     }
 192   return n_perms;
 193 }
 194
 195 /* Tests whether PARTS is a K-part integer composition of N.
 196    Returns true if so, false otherwise. */
 197 static bool UNUSED
 198 is_k_composition (int n, int k, const int parts[])
 199 {
 200   int sum;
 201   int i;
 202
 203   sum = 0;
 204   for (i = 0; i < k; i++)
 205     {
 206       if (parts[i] < 1 || parts[i] > n)
 207         return false;
 208       sum += parts[i];
 209     }
 210   return sum == n;
 211 }
 212
 213 /* Advances the K-part integer composition of N stored in PARTS
 214    to the next lexicographically greater one.
 215    Returns true if successful, false if the composition was
 216    already the greatest K-part composition of N (in which case
 217    PARTS is unaltered). */
 218 static bool
 219 next_k_composition (int n UNUSED, int k, int parts[])
 220 {
 221   int x, i;
 222
 223   assert (is_k_composition (n, k, parts));
 224   if (k == 1)
 225     return false;
 226
 227   for (i = k - 1; i > 0; i--)
 228     if (parts[i] > 1)
 229       break;
 230   if (i == 0)
 231     return false;
 232
 233   x = parts[i] - 1;
 234   parts[i] = 1;
 235   parts[i - 1]++;
 236   parts[k - 1] = x;
 237
 238   assert (is_k_composition (n, k, parts));
 239   return true;
 240 }
 241
 242 /* Advances *K and PARTS to the next integer composition of N.
 243    Compositions are ordered from shortest to longest and in
 244    lexicographical order within a given length.
 245    Before the first call, initialize *K to 0.
 246    After each successful call, *K contains the length of the
 247    current composition and the *K elements in PARTS contain its
 248    parts.
 249    Returns true if successful, false if the set of compositions
 250    has been exhausted. */
 251 static bool
 252 next_composition (int n, int *k, int parts[])
 253 {
 254   if (*k >= 1 && next_k_composition (n, *k, parts))
 255     return true;
 256   else if (*k < n)
 257     {
 258       int i;
 259       for (i = 0; i < *k; i++)
 260         parts[i] = 1;
 261       parts[i] = n - *k;
 262       (*k)++;
 263       return true;
 264     }
 265   else
 266     return false;
 267 }
 268 \f
 269 /* Inserts sequences without duplicates into a heap, and then
 270    ensures that they appear as the minimum element in the correct
 271    order as we delete them.  Exhaustively tests every input
 272    permutation up to 'max_elems' elements. */
 273 static void
 274 test_insert_no_dups_delete_min (void)
 275 {
 276   const int max_elems = 8;
 277   int n;
 278
 279   for (n = 0; n <= max_elems; n++)
 280     {
 281       struct heap *h;
 282       struct element *elements;
 283       int *values;
 284       unsigned int n_permutations;
 285       int i;
 286
 287       values = xnmalloc (n, sizeof *values);
 288       elements = xnmalloc (n, sizeof *elements);
 289       for (i = 0; i < n; i++)
 290         values[i] = i;
 291
 292       h = heap_create (compare_elements, &aux_data);
 293       n_permutations = 0;
 294       while (n_permutations == 0 || next_permutation (values, n))
 295         {
 296           int i;
 297
 298           for (i = 0; i < n; i++)
 299             elements[i].x = values[i];
 300
 301           check (heap_is_empty (h));
 302           for (i = 0; i < n; i++)
 303             {
 304               heap_insert (h, &elements[i].node);
 305               check (heap_node_to_element (heap_minimum (h))->x
 306                      == min_int (values, i + 1));
 307               check (heap_count (h) == i + 1);
 308             }
 309
 310           for (i = 0; i < n; i++)
 311             {
 312               check (heap_node_to_element (heap_minimum (h))->x == i);
 313               heap_delete (h, heap_minimum (h));
 314             }
 315           check (heap_is_empty (h));
 316           n_permutations++;
 317         }
 318       check (n_permutations == factorial (n));
 319       heap_destroy (h);
 320       free (values);
 321       free (elements);
 322     }
 323 }
 324
 325 /* Inserts sequences with duplicates into a heap, and then
 326    ensures that they appear as the minimum element in the correct
 327    order as we delete them.  Exhaustively tests every input
 328    permutation up to 'max_elems' elements.
 329
 330    See Usenet article <87mz4utika.fsf@blp.benpfaff.org> for
 331    details of the algorithm used here. */
 332 static void
 333 test_insert_with_dups_delete_min (void)
 334 {
 335   const int max_elems = 7;
 336   for (int n_elems = 1; n_elems <= max_elems; n_elems++)
 337     {
 338       unsigned int n_compositions;
 339       int *dups;
 340       int n_uniques;
 341       int *values;
 342       int *sorted_values;
 343       struct element *elements;
 344       int n = 0;
 345
 346       dups = xnmalloc (n_elems, sizeof *dups);
 347       values = xnmalloc (n_elems, sizeof *values);
 348       sorted_values = xnmalloc (n_elems, sizeof *sorted_values);
 349       elements = xnmalloc (n_elems, sizeof *elements);
 350
 351       n_uniques = 0;
 352       n_compositions = 0;
 353       while (next_composition (n_elems, &n_uniques, dups))
 354         {
 355           struct heap *h;
 356           int i, j, k;
 357           unsigned int n_permutations;
 358
 359           k = 0;
 360           for (i = 0; i < n_uniques; i++)
 361             for (j = 0; j < dups[i]; j++)
 362               {
 363                 values[k] = i;
 364                 sorted_values[k] = i;
 365                 k++;
 366               }
 367           check (k == n_elems);
 368
 369           h = heap_create (compare_elements, &aux_data);
 370           n_permutations = 0;
 371           while (n_permutations == 0 || next_permutation (values, n_elems))
 372             {
 373               int min = INT_MAX;
 374
 375               for (i = 0; i < n_elems; i++)
 376                 elements[i].x = values[i];
 377               n++;
 378
 379               check (heap_is_empty (h));
 380               for (i = 0; i < n_elems; i++)
 381                 {
 382                   heap_insert (h, &elements[i].node);
 383                   if (values[i] < min)
 384                     min = values[i];
 385                   check (heap_node_to_element (heap_minimum (h))->x == min);
 386                   check (heap_count (h) == i + 1);
 387                 }
 388
 389               for (i = 0; i < n_elems; i++)
 390                 {
 391                   struct element *min = heap_node_to_element (heap_minimum (h));
 392                   check (min->x == sorted_values[i]);
 393                   heap_delete (h, heap_minimum (h));
 394                 }
 395               check (heap_is_empty (h));
 396               n_permutations++;
 397             }
 398           check (n_permutations == expected_perms (values, n_elems));
 399           heap_destroy (h);
 400
 401           n_compositions++;
 402         }
 403       check (n_compositions == 1 << (n_elems - 1));
 404
 405       free (dups);
 406       free (values);
 407       free (sorted_values);
 408       free (elements);
 409     }
 410 }
 411
 412 /* Inserts a sequence without duplicates into a heap, then
 413    deletes them in a different order. */
 414 static void
 415 test_insert_no_dups_delete_random (void)
 416 {
 417   const int max_elems = 5;
 418   int n;
 419
 420   for (n = 0; n <= max_elems; n++)
 421     {
 422       struct heap *h;
 423       struct element *elements;
 424       int *insert, *delete;
 425       unsigned int insert_n_perms;
 426       int i;
 427
 428       insert = xnmalloc (n, sizeof *insert);
 429       delete = xnmalloc (n, sizeof *delete);
 430       elements = xnmalloc (n, sizeof *elements);
 431       for (i = 0; i < n; i++)
 432         {
 433           insert[i] = i;
 434           delete[i] = i;
 435           elements[i].x = i;
 436         }
 437
 438       h = heap_create (compare_elements, &aux_data);
 439       insert_n_perms = 0;
 440       while (insert_n_perms == 0 || next_permutation (insert, n))
 441         {
 442           unsigned int delete_n_perms = 0;
 443
 444           while (delete_n_perms == 0 || next_permutation (delete, n))
 445             {
 446               int min;
 447               int i;
 448
 449               check (heap_is_empty (h));
 450               min = INT_MAX;
 451               for (i = 0; i < n; i++)
 452                 {
 453                   heap_insert (h, &elements[insert[i]].node);
 454                   if (insert[i] < min)
 455                     min = insert[i];
 456                   check (heap_node_to_element (heap_minimum (h))->x == min);
 457                   check (heap_count (h) == i + 1);
 458                 }
 459
 460               for (i = 0; i < n; i++)
 461                 {
 462                   int new_min = min_int (delete + i + 1, n - i - 1);
 463                   heap_delete (h, &elements[delete[i]].node);
 464                   check (heap_count (h) == n - i - 1);
 465                   if (!heap_is_empty (h))
 466                     check (heap_node_to_element (heap_minimum (h))->x == new_min);
 467                 }
 468               check (heap_is_empty (h));
 469               delete_n_perms++;
 470             }
 471           check (delete_n_perms == factorial (n));
 472           insert_n_perms++;
 473         }
 474       check (insert_n_perms == factorial (n));
 475       heap_destroy (h);
 476       free (insert);
 477       free (delete);
 478       free (elements);
 479     }
 480 }
 481
 482 /* Inserts a set of values into a heap, then changes them to a
 483    different random set of values, then removes them in sorted
 484    order. */
 485 static void
 486 test_inc_dec (void)
 487 {
 488   const int max_elems = 8;
 489   int n;
 490
 491   for (n = 0; n <= max_elems; n++)
 492     {
 493       struct heap *h;
 494       struct element *elements;
 495       int *insert, *delete;
 496       unsigned int insert_n_perms;
 497       int i;
 498
 499       insert = xnmalloc (n, sizeof *insert);
 500       delete = xnmalloc (n, sizeof *delete);
 501       elements = xnmalloc (n, sizeof *elements);
 502       for (i = 0; i < n; i++)
 503         insert[i] = i;
 504
 505       h = heap_create (compare_elements, &aux_data);
 506       insert_n_perms = 0;
 507       while (insert_n_perms == 0 || next_permutation (insert, n))
 508         {
 509           for (i = 0; i < n; i++)
 510             elements[i].x = insert[i];
 511
 512           check (heap_is_empty (h));
 513           for (i = 0; i < n; i++)
 514             {
 515               int new_min = min_int (insert, i + 1);
 516               heap_insert (h, &elements[i].node);
 517               check (heap_node_to_element (heap_minimum (h))->x == new_min);
 518               check (heap_count (h) == i + 1);
 519             }
 520
 521           for (i = 0; i < n; i++)
 522             delete[i] = insert[i];
 523           for (i = 0; i < n; i++)
 524             {
 525               elements[i].x = delete[i] = rand () % (n + 2) - 1;
 526               heap_changed (h, &elements[i].node);
 527               check (heap_node_to_element (heap_minimum (h))->x
 528                      == min_int (delete, n));
 529             }
 530
 531           for (i = 0; i < n; i++)
 532             {
 533               int new_min = min_int (delete + i + 1, n - i - 1);
 534               heap_delete (h, &elements[i].node);
 535               check (heap_count (h) == n - i - 1);
 536               if (!heap_is_empty (h))
 537                 check (heap_node_to_element (heap_minimum (h))->x == new_min);
 538             }
 539           check (heap_is_empty (h));
 540           insert_n_perms++;
 541         }
 542       check (insert_n_perms == factorial (n));
 543       heap_destroy (h);
 544       free (insert);
 545       free (delete);
 546       free (elements);
 547     }
 548 }
 549
 550 /* Performs a random sequence of insertions and deletions in a
 551    heap. */
 552 static void
 553 test_random_insert_delete (void)
 554 {
 555   const int max_elems = 64;
 556   const int num_actions = 250000;
 557   struct heap *h;
 558   int *values;
 559   struct element *elements;
 560   int n;
 561   int insert_chance;
 562   int i;
 563
 564   values = xnmalloc (max_elems, sizeof *values);
 565   elements = xnmalloc (max_elems, sizeof *elements);
 566   n = 0;
 567   insert_chance = 5;
 568
 569   h = heap_create (compare_elements, &aux_data);
 570   for (i = 0; i < num_actions; i++)
 571     {
 572       enum { INSERT, DELETE } action;
 573
 574       if (n == 0)
 575         {
 576           action = INSERT;
 577           if (insert_chance < 9)
 578             insert_chance++;
 579         }
 580       else if (n == max_elems)
 581         {
 582           action = DELETE;
 583           if (insert_chance > 0)
 584             insert_chance--;
 585         }
 586       else
 587         action = rand () % 10 < insert_chance ? INSERT : DELETE;
 588
 589       if (action == INSERT)
 590         {
 591           int new_value;
 592
 593           new_value = rand () % max_elems;
 594           values[n] = new_value;
 595           elements[n].x = new_value;
 596
 597           heap_insert (h, &elements[n].node);
 598
 599           n++;
 600         }
 601       else if (action == DELETE)
 602         {
 603           int del_idx;
 604
 605           del_idx = rand () % n;
 606           heap_delete (h, &elements[del_idx].node);
 607
 608           n--;
 609           if (del_idx != n)
 610             {
 611               values[del_idx] = values[n];
 612               elements[del_idx] = elements[n];
 613               heap_moved (h, &elements[del_idx].node);
 614             }
 615         }
 616       else
 617         abort ();
 618
 619       check (heap_count (h) == n);
 620       check (heap_is_empty (h) == (n == 0));
 621       if (n > 0)
 622         check (heap_node_to_element (heap_minimum (h))->x
 623                == min_int (values, n));
 624     }
 625   heap_destroy (h);
 626   free (elements);
 627   free (values);
 628 }
 629 \f
 630 /* Main program. */
 631
 632 struct test
 633   {
 634     const char *name;
 635     const char *description;
 636     void (*function) (void);
 637   };
 638
 639 static const struct test tests[] =
 640   {
 641     {
 642       "insert-no-dups-delete-min",
 643       "insert (no dups), delete minimum values",
 644       test_insert_no_dups_delete_min
 645     },
 646     {
 647       "insert-with-dups-delete-min",
 648       "insert with dups, delete minimum values",
 649       test_insert_with_dups_delete_min
 650     },
 651     {
 652       "insert-no-dups-delete-random",
 653       "insert (no dups), delete in random order",
 654       test_insert_no_dups_delete_random
 655     },
 656     {
 657       "inc-dec",
 658       "increase and decrease values",
 659       test_inc_dec
 660     },
 661     {
 662       "random-insert-delete",
 663       "random insertions and deletions",
 664       test_random_insert_delete
 665     }
 666   };
 667
 668 enum { N_TESTS = sizeof tests / sizeof *tests };
 669
 670 int
 671 main (int argc, char *argv[])
 672 {
 673   int i;
 674
 675   if (argc != 2)
 676     {
 677       fprintf (stderr, "exactly one argument required; use --help for help\n");
 678       return EXIT_FAILURE;
 679     }
 680   else if (!strcmp (argv[1], "--help"))
 681     {
 682       printf ("%s: test heap library\n"
 683               "usage: %s TEST-NAME\n"
 684               "where TEST-NAME is one of the following:\n",
 685               argv[0], argv[0]);
 686       for (i = 0; i < N_TESTS; i++)
 687         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
 688       return 0;
 689     }
 690   else
 691     {
 692       for (i = 0; i < N_TESTS; i++)
 693         if (!strcmp (argv[1], tests[i].name))
 694           {
 695             tests[i].function ();
 696             return 0;
 697           }
 698
 699       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
 700       return EXIT_FAILURE;
 701     }
 702 }