tests/libpspp/tower-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 tower.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 tower.c routines.  (Without -DNDEBUG, branches
  21    caused by failed assertions will not be taken.)  "valgrind
  22    --leak-check=yes --show-reachable=yes" should give a clean
  23    report, both with and without -DNDEBUG. */
  24
  25 #ifdef HAVE_CONFIG_H
  26 #include <config.h>
  27 #endif
  28
  29 #include <libpspp/tower.h>
  30
  31 #include <assert.h>
  32 #include <limits.h>
  33 #include <stdint.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 block. */
  74 struct block
  75   {
  76     struct tower_node node;     /* Embedded tower block. */
  77     int x;                      /* Primary value. */
  78   };
  79
  80 /* Returns the `struct block' that NODE is embedded within. */
  81 static struct block *
  82 tower_node_to_block (const struct tower_node *node)
  83 {
  84   return tower_data (node, struct block, node);
  85 }
  86
  87 /* Swaps *A and *B. */
  88 static void
  89 swap (int *a, int *b)
  90 {
  91   int t = *a;
  92   *a = *b;
  93   *b = t;
  94 }
  95
  96 /* Reverses the order of the CNT integers starting at VALUES. */
  97 static void
  98 reverse (int *values, size_t cnt)
  99 {
 100   size_t i = 0;
 101   size_t j = cnt;
 102
 103   while (j > i)
 104     swap (&values[i++], &values[--j]);
 105 }
 106
 107 /* Arranges the CNT blocks in VALUES into the lexicographically
 108    next greater permutation.  Returns true if successful.
 109    If VALUES is already the lexicographically greatest
 110    permutation of its blocks (i.e. ordered from greatest to
 111    smallest), arranges them into the lexicographically least
 112    permutation (i.e. ordered from smallest to largest) and
 113    returns false. */
 114 static bool
 115 next_permutation (int *values, size_t cnt)
 116 {
 117   if (cnt > 0)
 118     {
 119       size_t i = cnt - 1;
 120       while (i != 0)
 121         {
 122           i--;
 123           if (values[i] < values[i + 1])
 124             {
 125               size_t j;
 126               for (j = cnt - 1; values[i] >= values[j]; j--)
 127                 continue;
 128               swap (values + i, values + j);
 129               reverse (values + (i + 1), cnt - (i + 1));
 130               return true;
 131             }
 132         }
 133
 134       reverse (values, cnt);
 135     }
 136
 137   return false;
 138 }
 139
 140 /* Returns N!. */
 141 static unsigned int
 142 factorial (unsigned int n)
 143 {
 144   unsigned int value = 1;
 145   /* Disallow N values that overflow on 32-bit machines. */
 146   assert (n <= 12);
 147   for (; n > 1; )
 148     value *= n--;
 149   return value;
 150 }
 151
 152 /* Returns C(n, k), the number of ways that K choices can be made
 153    from N items when order is unimportant. */
 154 static unsigned int
 155 binomial_cofficient (unsigned int n, unsigned int k)
 156 {
 157   assert (n >= k);
 158   return factorial (n) / factorial (k) / factorial (n - k);
 159 }
 160
 161 /* Tests whether PARTS is a K-part integer composition of N.
 162    Returns true if so, false otherwise. */
 163 static bool UNUSED
 164 is_k_composition (int n, int k, const int parts[])
 165 {
 166   int sum;
 167   int i;
 168
 169   sum = 0;
 170   for (i = 0; i < k; i++)
 171     {
 172       if (parts[i] < 1 || parts[i] > n)
 173         return false;
 174       sum += parts[i];
 175     }
 176   return sum == n;
 177 }
 178
 179 /* Advances the K-part integer composition of N stored in PARTS
 180    to the next lexicographically greater one.
 181    Returns true if successful, false if the composition was
 182    already the greatest K-part composition of N (in which case
 183    PARTS is unaltered). */
 184 static bool
 185 next_k_composition (int n UNUSED, int k, int parts[])
 186 {
 187   int x, i;
 188
 189   assert (is_k_composition (n, k, parts));
 190   if (k == 1)
 191     return false;
 192
 193   for (i = k - 1; i > 0; i--)
 194     if (parts[i] > 1)
 195       break;
 196   if (i == 0)
 197     return false;
 198
 199   x = parts[i] - 1;
 200   parts[i] = 1;
 201   parts[i - 1]++;
 202   parts[k - 1] = x;
 203
 204   assert (is_k_composition (n, k, parts));
 205   return true;
 206 }
 207
 208 /* Sets the K integers in PARTS to the lexicographically first
 209    K-part composition of N. */
 210 static void
 211 first_k_composition (int n, int k, int parts[])
 212 {
 213   int i;
 214
 215   assert (n >= k);
 216
 217   for (i = 0; i < k; i++)
 218     parts[i] = 1;
 219   parts[k - 1] += n - k;
 220 }
 221
 222 /* Advances *K and PARTS to the next integer composition of N.
 223    Compositions are ordered from shortest to longest and in
 224    lexicographical order within a given length.
 225    Before the first call, initialize *K to 0.
 226    After each successful call, *K contains the length of the
 227    current composition and the *K blocks in PARTS contain its
 228    parts.
 229    Returns true if successful, false if the set of compositions
 230    has been exhausted. */
 231 static bool
 232 next_composition (int n, int *k, int parts[])
 233 {
 234   if (*k >= 1 && next_k_composition (n, *k, parts))
 235     return true;
 236   else if (*k < n)
 237     {
 238       first_k_composition (n, ++*k, parts);
 239       return true;
 240     }
 241   else
 242     return false;
 243 }
 244
 245 /* A block expected to be found in a tower. */
 246 struct expected_block
 247   {
 248     int size;           /* Expected thickness of block. */
 249     int x;              /* Expected value for `x' member. */
 250   };
 251
 252 /* Checks that tower T contains the BLOCK_CNT blocks described by
 253    BLOCKS[]. */
 254 static void
 255 check_tower (struct tower *t,
 256              struct expected_block blocks[], size_t block_cnt)
 257 {
 258   int total_height;
 259   struct tower_node *node;
 260   size_t i;
 261
 262   check (tower_count (t) == block_cnt);
 263   check (tower_is_empty (t) == (block_cnt == 0));
 264
 265   total_height = 0;
 266   for (i = 0; i < block_cnt; i++)
 267     {
 268       unsigned long int level;
 269       for (level = total_height;
 270            level < total_height + blocks[i].size;
 271            level++)
 272         {
 273           struct tower_node *found;
 274           unsigned long int block_start;
 275           found = tower_lookup (t, level, &block_start);
 276           check (found != NULL);
 277           check (tower_node_to_block (found)->x == blocks[i].x);
 278           check (block_start == total_height);
 279           check (tower_node_get_level (found) == total_height);
 280           check (tower_node_get_index (found) == i);
 281           check (tower_get (t, i) == found);
 282         }
 283       total_height += blocks[i].size;
 284     }
 285   check (tower_height (t) == total_height);
 286
 287   for (node = tower_first (t), i = 0;
 288        node != NULL;
 289        node = tower_next (t, node), i++)
 290     {
 291       check (tower_node_get_size (node) == blocks[i].size);
 292       check (tower_node_to_block (node)->x == blocks[i].x);
 293     }
 294   check (i == block_cnt);
 295
 296   for (node = tower_last (t), i = block_cnt - 1;
 297        node != NULL;
 298        node = tower_prev (t, node), i--)
 299     {
 300       check (tower_node_get_size (node) == blocks[i].size);
 301       check (tower_node_to_block (node)->x == blocks[i].x);
 302     }
 303   check (i == SIZE_MAX);
 304 }
 305 \f
 306 /* Tests inserting all possible sets of block heights into a
 307    tower in all possible orders, up to a specified maximum tower
 308    height. */
 309 static void
 310 test_insert (void)
 311 {
 312   const int max_height = 7;
 313   int cnt;
 314
 315   for (cnt = 1; cnt <= max_height; cnt++)
 316     {
 317       unsigned int composition_cnt;
 318       struct expected_block *expected;
 319       int *sizes;
 320       int block_cnt;
 321       int *order;
 322       struct block *blocks;
 323
 324       expected = xnmalloc (cnt, sizeof *expected);
 325       sizes = xnmalloc (cnt, sizeof *sizes);
 326       order = xnmalloc (cnt, sizeof *order);
 327       blocks = xnmalloc (cnt, sizeof *blocks);
 328
 329       block_cnt = 0;
 330       composition_cnt = 0;
 331       while (next_composition (cnt, &block_cnt, sizes))
 332         {
 333           int i, j;
 334           unsigned int permutation_cnt;
 335
 336           for (i = 0; i < block_cnt; i++)
 337             order[i] = i;
 338
 339           permutation_cnt = 0;
 340           while (permutation_cnt == 0 || next_permutation (order, block_cnt))
 341             {
 342               struct tower t;
 343
 344               /* Inserts the block_cnt blocks with the given
 345                  sizes[] into T in the order given by order[]. */
 346               tower_init (&t);
 347               for (i = 0; i < block_cnt; i++)
 348                 {
 349                   struct block *under;
 350                   int idx;
 351
 352                   idx = order[i];
 353                   blocks[idx].x = idx;
 354
 355                   under = NULL;
 356                   for (j = 0; j < i; j++)
 357                     if (idx < order[j]
 358                         && (under == NULL || under->x > order[j]))
 359                       under = &blocks[order[j]];
 360
 361                   tower_insert (&t, sizes[idx], &blocks[idx].node,
 362                                 under != NULL ? &under->node : NULL);
 363                 }
 364
 365               /* Check that the result is what we expect. */
 366               for (i = 0; i < block_cnt; i++)
 367                 {
 368                   expected[i].size = sizes[i];
 369                   expected[i].x = i;
 370                 }
 371               check_tower (&t, expected, block_cnt);
 372
 373               permutation_cnt++;
 374             }
 375           check (permutation_cnt == factorial (block_cnt));
 376
 377           composition_cnt++;
 378         }
 379       check (composition_cnt == 1 << (cnt - 1));
 380
 381       free (expected);
 382       free (sizes);
 383       free (order);
 384       free (blocks);
 385     }
 386 }
 387
 388 /* Tests deleting blocks from towers that initially contain all
 389    possible sets of block sizes into a tower in all possible
 390    orders, up to a specified maximum tower height. */
 391 static void
 392 test_delete (void)
 393 {
 394   const int max_height = 7;
 395   int cnt;
 396
 397   for (cnt = 1; cnt <= max_height; cnt++)
 398     {
 399       unsigned int composition_cnt;
 400       struct expected_block *expected;
 401       int *sizes;
 402       int block_cnt;
 403       int *order;
 404       struct block *blocks;
 405
 406       expected = xnmalloc (cnt, sizeof *expected);
 407       sizes = xnmalloc (cnt, sizeof *sizes);
 408       order = xnmalloc (cnt, sizeof *order);
 409       blocks = xnmalloc (cnt, sizeof *blocks);
 410
 411       block_cnt = 0;
 412       composition_cnt = 0;
 413       while (next_composition (cnt, &block_cnt, sizes))
 414         {
 415           int i;
 416           unsigned int permutation_cnt;
 417
 418           for (i = 0; i < block_cnt; i++)
 419             order[i] = i;
 420
 421           permutation_cnt = 0;
 422           while (permutation_cnt == 0 || next_permutation (order, block_cnt))
 423             {
 424               struct tower t;
 425
 426               /* Insert blocks into tower in ascending order. */
 427               tower_init (&t);
 428               for (i = 0; i < block_cnt; i++)
 429                 {
 430                   blocks[i].x = i;
 431                   tower_insert (&t, sizes[i], &blocks[i].node, NULL);
 432                   expected[i].x = i;
 433                   expected[i].size = sizes[i];
 434                 }
 435               check_tower (&t, expected, block_cnt);
 436
 437               /* Delete blocks from tower in the order of
 438                  order[]. */
 439               for (i = 0; i < block_cnt; i++)
 440                 {
 441                   int idx = order[i];
 442                   int j;
 443                   tower_delete (&t, &blocks[idx].node);
 444                   for (j = 0; ; j++)
 445                     {
 446                       assert (j < block_cnt - i);
 447                       if (expected[j].x == idx)
 448                         {
 449                           memcpy (&expected[j], &expected[j + 1],
 450                                   sizeof *expected * (block_cnt - i - j - 1));
 451                           break;
 452                         }
 453                     }
 454                   check_tower (&t, expected, block_cnt - i - 1);
 455                 }
 456
 457               permutation_cnt++;
 458             }
 459           check (permutation_cnt == factorial (block_cnt));
 460
 461           composition_cnt++;
 462         }
 463       check (composition_cnt == 1 << (cnt - 1));
 464
 465       free (expected);
 466       free (sizes);
 467       free (order);
 468       free (blocks);
 469     }
 470 }
 471
 472 /* Tests towers containing all possible block sizes, resizing
 473    the blocks to all possible sizes that conserve the total
 474    tower height, up to a maximum total tower height. */
 475 static void
 476 test_resize (void)
 477 {
 478   const int max_height = 9;
 479   int cnt;
 480
 481   for (cnt = 1; cnt <= max_height; cnt++)
 482     {
 483       unsigned int composition_cnt;
 484       struct expected_block *expected;
 485       int *sizes, *new_sizes;
 486       int block_cnt;
 487       int *order;
 488       struct block *blocks;
 489
 490       expected = xnmalloc (cnt, sizeof *expected);
 491       sizes = xnmalloc (cnt, sizeof *sizes);
 492       new_sizes = xnmalloc (cnt, sizeof *new_sizes);
 493       order = xnmalloc (cnt, sizeof *order);
 494       blocks = xnmalloc (cnt, sizeof *blocks);
 495
 496       block_cnt = 0;
 497       composition_cnt = 0;
 498       while (next_composition (cnt, &block_cnt, sizes))
 499         {
 500           int i;
 501           unsigned int resizes = 0;
 502
 503           for (resizes = 0, first_k_composition (cnt, block_cnt, new_sizes);
 504                (resizes == 0
 505                 || next_k_composition (cnt, block_cnt, new_sizes));
 506                resizes++)
 507             {
 508               struct tower t;
 509
 510               /* Insert blocks into tower in ascending order. */
 511               tower_init (&t);
 512               for (i = 0; i < block_cnt; i++)
 513                 {
 514                   blocks[i].x = i;
 515                   tower_insert (&t, sizes[i], &blocks[i].node, NULL);
 516                   expected[i].x = i;
 517                   expected[i].size = sizes[i];
 518                 }
 519               check_tower (&t, expected, block_cnt);
 520
 521               /* Resize all the blocks. */
 522               for (i = 0; i < block_cnt; i++)
 523                 {
 524                   if (expected[i].size != new_sizes[i] || rand () % 2)
 525                     tower_resize (&t, &blocks[i].node, new_sizes[i]);
 526                   expected[i].size = new_sizes[i];
 527                 }
 528               check_tower (&t, expected, block_cnt);
 529             }
 530           check (resizes == binomial_cofficient (cnt - 1, block_cnt - 1));
 531
 532           composition_cnt++;
 533         }
 534       check (composition_cnt == 1 << (cnt - 1));
 535
 536       free (expected);
 537       free (new_sizes);
 538       free (sizes);
 539       free (order);
 540       free (blocks);
 541     }
 542 }
 543
 544 /* Tests splicing all possible contiguous sets of blocks out of one
 545    tower into a second, initially empty tower. */
 546 static void
 547 test_splice_out (void)
 548 {
 549   const int max_height = 9;
 550   int cnt;
 551
 552   for (cnt = 1; cnt <= max_height; cnt++)
 553     {
 554       unsigned int composition_cnt;
 555       struct expected_block *expected;
 556       int *sizes, *new_sizes;
 557       int block_cnt;
 558       int *order;
 559       struct block *blocks;
 560
 561       expected = xnmalloc (cnt, sizeof *expected);
 562       sizes = xnmalloc (cnt, sizeof *sizes);
 563       new_sizes = xnmalloc (cnt, sizeof *new_sizes);
 564       order = xnmalloc (cnt, sizeof *order);
 565       blocks = xnmalloc (cnt, sizeof *blocks);
 566
 567       block_cnt = 0;
 568       composition_cnt = 0;
 569       while (next_composition (cnt, &block_cnt, sizes))
 570         {
 571           int i, j;
 572
 573           for (i = 0; i < block_cnt; i++)
 574             for (j = i; j <= block_cnt; j++)
 575               {
 576                 struct tower src, dst;
 577                 int k;
 578
 579                 tower_init (&src);
 580                 tower_init (&dst);
 581
 582                 /* Insert blocks into SRC and DST in ascending order. */
 583                 for (k = 0; k < block_cnt; k++)
 584                   {
 585                     blocks[k].x = k;
 586                     tower_insert (&src, sizes[k], &blocks[k].node, NULL);
 587                     expected[k].x = k;
 588                     expected[k].size = sizes[k];
 589                   }
 590                 check_tower (&src, expected, block_cnt);
 591
 592                 /* Splice blocks I...J into DST. */
 593                 tower_splice (&dst, NULL, &src, &blocks[i].node,
 594                               j < block_cnt ? &blocks[j].node : NULL);
 595                 check_tower (&dst, &expected[i], j - i);
 596                 memmove (&expected[i], &expected[j],
 597                          sizeof *expected * (block_cnt - j));
 598                 check_tower (&src, expected, block_cnt - (j - i));
 599               }
 600            composition_cnt++;
 601         }
 602       check (composition_cnt == 1 << (cnt - 1));
 603
 604       free (expected);
 605       free (new_sizes);
 606       free (sizes);
 607       free (order);
 608       free (blocks);
 609     }
 610 }
 611
 612 /* Tests splicing all of the contents of a tower into all
 613    possible positions in a second tower. */
 614 static void
 615 test_splice_in (void)
 616 {
 617   const int max_height = 9;
 618   int cnt;
 619
 620   for (cnt = 1; cnt <= max_height; cnt++)
 621     {
 622       unsigned int composition_cnt;
 623       struct expected_block *expected;
 624       int *sizes, *new_sizes;
 625       int block_cnt;
 626       int *order;
 627       struct block *blocks;
 628
 629       expected = xnmalloc (cnt, sizeof *expected);
 630       sizes = xnmalloc (cnt, sizeof *sizes);
 631       new_sizes = xnmalloc (cnt, sizeof *new_sizes);
 632       order = xnmalloc (cnt, sizeof *order);
 633       blocks = xnmalloc (cnt, sizeof *blocks);
 634
 635       block_cnt = 0;
 636       composition_cnt = 0;
 637       while (next_composition (cnt, &block_cnt, sizes))
 638         {
 639           int i, j;
 640
 641           for (i = 0; i < block_cnt; i++)
 642             for (j = i; j <= block_cnt; j++)
 643               {
 644                 struct tower src, dst;
 645                 int k;
 646
 647                 tower_init (&src);
 648                 tower_init (&dst);
 649
 650                 /* Insert blocks into SRC and DST in ascending order. */
 651                 for (k = 0; k < block_cnt; k++)
 652                   {
 653                     blocks[k].x = k;
 654                     tower_insert (k >= i && k < j ? &src : &dst,
 655                                   sizes[k], &blocks[k].node, NULL);
 656                     expected[k].x = k;
 657                     expected[k].size = sizes[k];
 658                   }
 659
 660                 /* Splice SRC into DST. */
 661                 tower_splice (&dst, j < block_cnt ? &blocks[j].node : NULL,
 662                               &src, i != j ? &blocks[i].node : NULL, NULL);
 663                 check_tower (&dst, expected, block_cnt);
 664               }
 665            composition_cnt++;
 666         }
 667       check (composition_cnt == 1 << (cnt - 1));
 668
 669       free (expected);
 670       free (new_sizes);
 671       free (sizes);
 672       free (order);
 673       free (blocks);
 674     }
 675 }
 676
 677 \f
 678 /* Main program. */
 679
 680 /* Runs TEST_FUNCTION and prints a message about NAME. */
 681 static void
 682 run_test (void (*test_function) (void), const char *name)
 683 {
 684   test_name = name;
 685   putchar ('.');
 686   fflush (stdout);
 687   test_function ();
 688 }
 689
 690 int
 691 main (void)
 692 {
 693   run_test (test_insert, "insert");
 694   run_test (test_delete, "delete");
 695   run_test (test_resize, "resize");
 696   run_test (test_splice_out, "splice out");
 697   run_test (test_splice_in, "splice in");
 698   putchar ('\n');
 699
 700   return 0;
 701 }