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