tests/libpspp/tower-test.c

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