tests/libpspp/heap-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 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 CNT integers starting at VALUES. */
 122 static void
 123 reverse (int *values, size_t cnt)
 124 {
 125   size_t i = 0;
 126   size_t j = cnt;
 127
 128   while (j > i)
 129     swap (&values[i++], &values[--j]);
 130 }
 131
 132 /* Arranges the CNT 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 cnt)
 141 {
 142   if (cnt > 0)
 143     {
 144       size_t i = cnt - 1;
 145       while (i != 0)
 146         {
 147           i--;
 148           if (values[i] < values[i + 1])
 149             {
 150               size_t j;
 151               for (j = cnt - 1; values[i] >= values[j]; j--)
 152                 continue;
 153               swap (values + i, values + j);
 154               reverse (values + (i + 1), cnt - (i + 1));
 155               return true;
 156             }
 157         }
 158
 159       reverse (values, cnt);
 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 CNT values in
 176    VALUES.  If VALUES contains duplicates, they must be
 177    adjacent. */
 178 static unsigned int
 179 expected_perms (int *values, size_t cnt)
 180 {
 181   size_t i, j;
 182   unsigned int perm_cnt;
 183
 184   perm_cnt = factorial (cnt);
 185   for (i = 0; i < cnt; i = j)
 186     {
 187       for (j = i + 1; j < cnt; j++)
 188         if (values[i] != values[j])
 189           break;
 190       perm_cnt /= factorial (j - i);
 191     }
 192   return perm_cnt;
 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 cnt;
 278
 279   for (cnt = 0; cnt <= max_elems; cnt++)
 280     {
 281       struct heap *h;
 282       struct element *elements;
 283       int *values;
 284       unsigned int permutation_cnt;
 285       int i;
 286
 287       values = xnmalloc (cnt, sizeof *values);
 288       elements = xnmalloc (cnt, sizeof *elements);
 289       for (i = 0; i < cnt; i++)
 290         values[i] = i;
 291
 292       h = heap_create (compare_elements, &aux_data);
 293       permutation_cnt = 0;
 294       while (permutation_cnt == 0 || next_permutation (values, cnt))
 295         {
 296           int i;
 297
 298           for (i = 0; i < cnt; i++)
 299             elements[i].x = values[i];
 300
 301           check (heap_is_empty (h));
 302           for (i = 0; i < cnt; 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 < cnt; 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           permutation_cnt++;
 317         }
 318       check (permutation_cnt == factorial (cnt));
 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   int cnt;
 337
 338   for (cnt = 1; cnt <= max_elems; cnt++)
 339     {
 340       unsigned int composition_cnt;
 341       int *dups;
 342       int unique_cnt;
 343       int *values;
 344       int *sorted_values;
 345       struct element *elements;
 346       int n = 0;
 347
 348       dups = xnmalloc (cnt, sizeof *dups);
 349       values = xnmalloc (cnt, sizeof *values);
 350       sorted_values = xnmalloc (cnt, sizeof *sorted_values);
 351       elements = xnmalloc (cnt, sizeof *elements);
 352
 353       unique_cnt = 0;
 354       composition_cnt = 0;
 355       while (next_composition (cnt, &unique_cnt, dups))
 356         {
 357           struct heap *h;
 358           int i, j, k;
 359           unsigned int permutation_cnt;
 360
 361           k = 0;
 362           for (i = 0; i < unique_cnt; i++)
 363             for (j = 0; j < dups[i]; j++)
 364               {
 365                 values[k] = i;
 366                 sorted_values[k] = i;
 367                 k++;
 368               }
 369           check (k == cnt);
 370
 371           h = heap_create (compare_elements, &aux_data);
 372           permutation_cnt = 0;
 373           while (permutation_cnt == 0 || next_permutation (values, cnt))
 374             {
 375               int min = INT_MAX;
 376
 377               for (i = 0; i < cnt; i++)
 378                 elements[i].x = values[i];
 379               n++;
 380
 381               check (heap_is_empty (h));
 382               for (i = 0; i < cnt; i++)
 383                 {
 384                   heap_insert (h, &elements[i].node);
 385                   if (values[i] < min)
 386                     min = values[i];
 387                   check (heap_node_to_element (heap_minimum (h))->x == min);
 388                   check (heap_count (h) == i + 1);
 389                 }
 390
 391               for (i = 0; i < cnt; i++)
 392                 {
 393                   struct element *min = heap_node_to_element (heap_minimum (h));
 394                   check (min->x == sorted_values[i]);
 395                   heap_delete (h, heap_minimum (h));
 396                 }
 397               check (heap_is_empty (h));
 398               permutation_cnt++;
 399             }
 400           check (permutation_cnt == expected_perms (values, cnt));
 401           heap_destroy (h);
 402
 403           composition_cnt++;
 404         }
 405       check (composition_cnt == 1 << (cnt - 1));
 406
 407       free (dups);
 408       free (values);
 409       free (sorted_values);
 410       free (elements);
 411     }
 412 }
 413
 414 /* Inserts a sequence without duplicates into a heap, then
 415    deletes them in a different order. */
 416 static void
 417 test_insert_no_dups_delete_random (void)
 418 {
 419   const int max_elems = 5;
 420   int cnt;
 421
 422   for (cnt = 0; cnt <= max_elems; cnt++)
 423     {
 424       struct heap *h;
 425       struct element *elements;
 426       int *insert, *delete;
 427       unsigned int insert_perm_cnt;
 428       int i;
 429
 430       insert = xnmalloc (cnt, sizeof *insert);
 431       delete = xnmalloc (cnt, sizeof *delete);
 432       elements = xnmalloc (cnt, sizeof *elements);
 433       for (i = 0; i < cnt; i++)
 434         {
 435           insert[i] = i;
 436           delete[i] = i;
 437           elements[i].x = i;
 438         }
 439
 440       h = heap_create (compare_elements, &aux_data);
 441       insert_perm_cnt = 0;
 442       while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
 443         {
 444           unsigned int delete_perm_cnt = 0;
 445
 446           while (delete_perm_cnt == 0 || next_permutation (delete, cnt))
 447             {
 448               int min;
 449               int i;
 450
 451               check (heap_is_empty (h));
 452               min = INT_MAX;
 453               for (i = 0; i < cnt; i++)
 454                 {
 455                   heap_insert (h, &elements[insert[i]].node);
 456                   if (insert[i] < min)
 457                     min = insert[i];
 458                   check (heap_node_to_element (heap_minimum (h))->x == min);
 459                   check (heap_count (h) == i + 1);
 460                 }
 461
 462               for (i = 0; i < cnt; i++)
 463                 {
 464                   int new_min = min_int (delete + i + 1, cnt - i - 1);
 465                   heap_delete (h, &elements[delete[i]].node);
 466                   check (heap_count (h) == cnt - i - 1);
 467                   if (!heap_is_empty (h))
 468                     check (heap_node_to_element (heap_minimum (h))->x == new_min);
 469                 }
 470               check (heap_is_empty (h));
 471               delete_perm_cnt++;
 472             }
 473           check (delete_perm_cnt == factorial (cnt));
 474           insert_perm_cnt++;
 475         }
 476       check (insert_perm_cnt == factorial (cnt));
 477       heap_destroy (h);
 478       free (insert);
 479       free (delete);
 480       free (elements);
 481     }
 482 }
 483
 484 /* Inserts a set of values into a heap, then changes them to a
 485    different random set of values, then removes them in sorted
 486    order. */
 487 static void
 488 test_inc_dec (void)
 489 {
 490   const int max_elems = 8;
 491   int cnt;
 492
 493   for (cnt = 0; cnt <= max_elems; cnt++)
 494     {
 495       struct heap *h;
 496       struct element *elements;
 497       int *insert, *delete;
 498       unsigned int insert_perm_cnt;
 499       int i;
 500
 501       insert = xnmalloc (cnt, sizeof *insert);
 502       delete = xnmalloc (cnt, sizeof *delete);
 503       elements = xnmalloc (cnt, sizeof *elements);
 504       for (i = 0; i < cnt; i++)
 505         insert[i] = i;
 506
 507       h = heap_create (compare_elements, &aux_data);
 508       insert_perm_cnt = 0;
 509       while (insert_perm_cnt == 0 || next_permutation (insert, cnt))
 510         {
 511           for (i = 0; i < cnt; i++)
 512             elements[i].x = insert[i];
 513
 514           check (heap_is_empty (h));
 515           for (i = 0; i < cnt; i++)
 516             {
 517               int new_min = min_int (insert, i + 1);
 518               heap_insert (h, &elements[i].node);
 519               check (heap_node_to_element (heap_minimum (h))->x == new_min);
 520               check (heap_count (h) == i + 1);
 521             }
 522
 523           for (i = 0; i < cnt; i++)
 524             delete[i] = insert[i];
 525           for (i = 0; i < cnt; i++)
 526             {
 527               int old_value, old_min, new_min;
 528               old_min = min_int (delete, cnt);
 529               old_value = delete[i];
 530               elements[i].x = delete[i] = rand () % (cnt + 2) - 1;
 531               new_min = min_int (delete, cnt);
 532               heap_changed (h, &elements[i].node);
 533               check (heap_node_to_element (heap_minimum (h))->x
 534                      == min_int (delete, cnt));
 535             }
 536
 537           for (i = 0; i < cnt; i++)
 538             {
 539               int new_min = min_int (delete + i + 1, cnt - i - 1);
 540               heap_delete (h, &elements[i].node);
 541               check (heap_count (h) == cnt - i - 1);
 542               if (!heap_is_empty (h))
 543                 check (heap_node_to_element (heap_minimum (h))->x == new_min);
 544             }
 545           check (heap_is_empty (h));
 546           insert_perm_cnt++;
 547         }
 548       check (insert_perm_cnt == factorial (cnt));
 549       heap_destroy (h);
 550       free (insert);
 551       free (delete);
 552       free (elements);
 553     }
 554 }
 555
 556 /* Performs a random sequence of insertions and deletions in a
 557    heap. */
 558 static void
 559 test_random_insert_delete (void)
 560 {
 561   const int max_elems = 64;
 562   const int num_actions = 250000;
 563   struct heap *h;
 564   int *values;
 565   struct element *elements;
 566   int cnt;
 567   int insert_chance;
 568   int i;
 569
 570   values = xnmalloc (max_elems, sizeof *values);
 571   elements = xnmalloc (max_elems, sizeof *elements);
 572   cnt = 0;
 573   insert_chance = 5;
 574
 575   h = heap_create (compare_elements, &aux_data);
 576   for (i = 0; i < num_actions; i++)
 577     {
 578       enum { INSERT, DELETE } action;
 579
 580       if (cnt == 0)
 581         {
 582           action = INSERT;
 583           if (insert_chance < 9)
 584             insert_chance++;
 585         }
 586       else if (cnt == max_elems)
 587         {
 588           action = DELETE;
 589           if (insert_chance > 0)
 590             insert_chance--;
 591         }
 592       else
 593         action = rand () % 10 < insert_chance ? INSERT : DELETE;
 594
 595       if (action == INSERT)
 596         {
 597           int new_value;
 598           int old_min;
 599
 600           new_value = rand () % max_elems;
 601           values[cnt] = new_value;
 602           elements[cnt].x = new_value;
 603
 604           heap_insert (h, &elements[cnt].node);
 605
 606           old_min = min_int (values, cnt);
 607
 608           cnt++;
 609         }
 610       else if (action == DELETE)
 611         {
 612           int del_idx;
 613           int del_value;
 614           int old_min, new_min;
 615
 616           old_min = min_int (values, cnt);
 617
 618           del_idx = rand () % cnt;
 619           del_value = values[del_idx];
 620           heap_delete (h, &elements[del_idx].node);
 621
 622           cnt--;
 623           if (del_idx != cnt)
 624             {
 625               values[del_idx] = values[cnt];
 626               elements[del_idx] = elements[cnt];
 627               heap_moved (h, &elements[del_idx].node);
 628             }
 629
 630           new_min = min_int (values, cnt);
 631         }
 632       else
 633         abort ();
 634
 635       check (heap_count (h) == cnt);
 636       check (heap_is_empty (h) == (cnt == 0));
 637       if (cnt > 0)
 638         check (heap_node_to_element (heap_minimum (h))->x
 639                == min_int (values, cnt));
 640     }
 641   heap_destroy (h);
 642   free (elements);
 643   free (values);
 644 }
 645 \f
 646 /* Main program. */
 647
 648 struct test
 649   {
 650     const char *name;
 651     const char *description;
 652     void (*function) (void);
 653   };
 654
 655 static const struct test tests[] =
 656   {
 657     {
 658       "insert-no-dups-delete-min",
 659       "insert (no dups), delete minimum values",
 660       test_insert_no_dups_delete_min
 661     },
 662     {
 663       "insert-with-dups-delete-min",
 664       "insert with dups, delete minimum values",
 665       test_insert_with_dups_delete_min
 666     },
 667     {
 668       "insert-no-dups-delete-random",
 669       "insert (no dups), delete in random order",
 670       test_insert_no_dups_delete_random
 671     },
 672     {
 673       "inc-dec",
 674       "increase and decrease values",
 675       test_inc_dec
 676     },
 677     {
 678       "random-insert-delete",
 679       "random insertions and deletions",
 680       test_random_insert_delete
 681     }
 682   };
 683
 684 enum { N_TESTS = sizeof tests / sizeof *tests };
 685
 686 int
 687 main (int argc, char *argv[])
 688 {
 689   int i;
 690
 691   if (argc != 2)
 692     {
 693       fprintf (stderr, "exactly one argument required; use --help for help\n");
 694       return EXIT_FAILURE;
 695     }
 696   else if (!strcmp (argv[1], "--help"))
 697     {
 698       printf ("%s: test heap library\n"
 699               "usage: %s TEST-NAME\n"
 700               "where TEST-NAME is one of the following:\n",
 701               argv[0], argv[0]);
 702       for (i = 0; i < N_TESTS; i++)
 703         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
 704       return 0;
 705     }
 706   else
 707     {
 708       for (i = 0; i < N_TESTS; i++)
 709         if (!strcmp (argv[1], tests[i].name))
 710           {
 711             tests[i].function ();
 712             return 0;
 713           }
 714
 715       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
 716       return EXIT_FAILURE;
 717     }
 718 }