pintos-os.org Git - pspp/blob - 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 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               elements[i].x = delete[i] = rand () % (cnt + 2) - 1;
 528               heap_changed (h, &elements[i].node);
 529               check (heap_node_to_element (heap_minimum (h))->x
 530                      == min_int (delete, cnt));
 531             }
 532
 533           for (i = 0; i < cnt; i++)
 534             {
 535               int new_min = min_int (delete + i + 1, cnt - i - 1);
 536               heap_delete (h, &elements[i].node);
 537               check (heap_count (h) == cnt - i - 1);
 538               if (!heap_is_empty (h))
 539                 check (heap_node_to_element (heap_minimum (h))->x == new_min);
 540             }
 541           check (heap_is_empty (h));
 542           insert_perm_cnt++;
 543         }
 544       check (insert_perm_cnt == factorial (cnt));
 545       heap_destroy (h);
 546       free (insert);
 547       free (delete);
 548       free (elements);
 549     }
 550 }
 551
 552 /* Performs a random sequence of insertions and deletions in a
 553    heap. */
 554 static void
 555 test_random_insert_delete (void)
 556 {
 557   const int max_elems = 64;
 558   const int num_actions = 250000;
 559   struct heap *h;
 560   int *values;
 561   struct element *elements;
 562   int cnt;
 563   int insert_chance;
 564   int i;
 565
 566   values = xnmalloc (max_elems, sizeof *values);
 567   elements = xnmalloc (max_elems, sizeof *elements);
 568   cnt = 0;
 569   insert_chance = 5;
 570
 571   h = heap_create (compare_elements, &aux_data);
 572   for (i = 0; i < num_actions; i++)
 573     {
 574       enum { INSERT, DELETE } action;
 575
 576       if (cnt == 0)
 577         {
 578           action = INSERT;
 579           if (insert_chance < 9)
 580             insert_chance++;
 581         }
 582       else if (cnt == max_elems)
 583         {
 584           action = DELETE;
 585           if (insert_chance > 0)
 586             insert_chance--;
 587         }
 588       else
 589         action = rand () % 10 < insert_chance ? INSERT : DELETE;
 590
 591       if (action == INSERT)
 592         {
 593           int new_value;
 594
 595           new_value = rand () % max_elems;
 596           values[cnt] = new_value;
 597           elements[cnt].x = new_value;
 598
 599           heap_insert (h, &elements[cnt].node);
 600
 601           cnt++;
 602         }
 603       else if (action == DELETE)
 604         {
 605           int del_idx;
 606
 607           del_idx = rand () % cnt;
 608           heap_delete (h, &elements[del_idx].node);
 609
 610           cnt--;
 611           if (del_idx != cnt)
 612             {
 613               values[del_idx] = values[cnt];
 614               elements[del_idx] = elements[cnt];
 615               heap_moved (h, &elements[del_idx].node);
 616             }
 617         }
 618       else
 619         abort ();
 620
 621       check (heap_count (h) == cnt);
 622       check (heap_is_empty (h) == (cnt == 0));
 623       if (cnt > 0)
 624         check (heap_node_to_element (heap_minimum (h))->x
 625                == min_int (values, cnt));
 626     }
 627   heap_destroy (h);
 628   free (elements);
 629   free (values);
 630 }
 631 \f
 632 /* Main program. */
 633
 634 struct test
 635   {
 636     const char *name;
 637     const char *description;
 638     void (*function) (void);
 639   };
 640
 641 static const struct test tests[] =
 642   {
 643     {
 644       "insert-no-dups-delete-min",
 645       "insert (no dups), delete minimum values",
 646       test_insert_no_dups_delete_min
 647     },
 648     {
 649       "insert-with-dups-delete-min",
 650       "insert with dups, delete minimum values",
 651       test_insert_with_dups_delete_min
 652     },
 653     {
 654       "insert-no-dups-delete-random",
 655       "insert (no dups), delete in random order",
 656       test_insert_no_dups_delete_random
 657     },
 658     {
 659       "inc-dec",
 660       "increase and decrease values",
 661       test_inc_dec
 662     },
 663     {
 664       "random-insert-delete",
 665       "random insertions and deletions",
 666       test_random_insert_delete
 667     }
 668   };
 669
 670 enum { N_TESTS = sizeof tests / sizeof *tests };
 671
 672 int
 673 main (int argc, char *argv[])
 674 {
 675   int i;
 676
 677   if (argc != 2)
 678     {
 679       fprintf (stderr, "exactly one argument required; use --help for help\n");
 680       return EXIT_FAILURE;
 681     }
 682   else if (!strcmp (argv[1], "--help"))
 683     {
 684       printf ("%s: test heap library\n"
 685               "usage: %s TEST-NAME\n"
 686               "where TEST-NAME is one of the following:\n",
 687               argv[0], argv[0]);
 688       for (i = 0; i < N_TESTS; i++)
 689         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
 690       return 0;
 691     }
 692   else
 693     {
 694       for (i = 0; i < N_TESTS; i++)
 695         if (!strcmp (argv[1], tests[i].name))
 696           {
 697             tests[i].function ();
 698             return 0;
 699           }
 700
 701       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
 702       return EXIT_FAILURE;
 703     }
 704 }