tests/libpspp/heap-test.c

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