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