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