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