pintos-os.org Git - pspp/blob - 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 height;         /* Expected height of bottom 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_is_empty (t) == (block_cnt == 0));
 263
 264   total_height = 0;
 265   for (i = 0; i < block_cnt; i++)
 266     {
 267       unsigned long int level;
 268       for (level = total_height;
 269            level < total_height + blocks[i].height;
 270            level++)
 271         {
 272           struct tower_node *found;
 273           unsigned long int block_start;
 274           found = tower_lookup (t, level, &block_start);
 275           check (found != NULL);
 276           check (tower_node_to_block (found)->x == blocks[i].x);
 277           check (block_start == total_height);
 278         }
 279       total_height += blocks[i].height;
 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_height (node) == blocks[i].height);
 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_height (node) == blocks[i].height);
 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 *heights;
 316       int block_cnt;
 317       int *order;
 318       struct block *blocks;
 319
 320       expected = xnmalloc (cnt, sizeof *expected);
 321       heights = xnmalloc (cnt, sizeof *heights);
 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, heights))
 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                  heights[] 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, heights[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].height = heights[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 (heights);
 379       free (order);
 380       free (blocks);
 381     }
 382 }
 383
 384 /* Tests deleting blocks from towers that initially contain all
 385    possible sets of block heights 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 *heights;
 398       int block_cnt;
 399       int *order;
 400       struct block *blocks;
 401
 402       expected = xnmalloc (cnt, sizeof *expected);
 403       heights = xnmalloc (cnt, sizeof *heights);
 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, heights))
 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, heights[i], &blocks[i].node, NULL);
 428                   expected[i].x = i;
 429                   expected[i].height = heights[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 (heights);
 463       free (order);
 464       free (blocks);
 465     }
 466 }
 467
 468 /* Tests towers containing all possible block heights, resizing
 469    the blocks to all possible heights 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 *heights, *new_heights;
 482       int block_cnt;
 483       int *order;
 484       struct block *blocks;
 485
 486       expected = xnmalloc (cnt, sizeof *expected);
 487       heights = xnmalloc (cnt, sizeof *heights);
 488       new_heights = xnmalloc (cnt, sizeof *new_heights);
 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, heights))
 495         {
 496           int i;
 497           unsigned int resizes = 0;
 498
 499           for (resizes = 0, first_k_composition (cnt, block_cnt, new_heights);
 500                (resizes == 0
 501                 || next_k_composition (cnt, block_cnt, new_heights));
 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, heights[i], &blocks[i].node, NULL);
 512                   expected[i].x = i;
 513                   expected[i].height = heights[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].height != new_heights[i] || rand () % 2)
 521                     tower_resize (&t, &blocks[i].node, new_heights[i]);
 522                   expected[i].height = new_heights[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_heights);
 534       free (heights);
 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 *heights, *new_heights;
 553       int block_cnt;
 554       int *order;
 555       struct block *blocks;
 556
 557       expected = xnmalloc (cnt, sizeof *expected);
 558       heights = xnmalloc (cnt, sizeof *heights);
 559       new_heights = xnmalloc (cnt, sizeof *new_heights);
 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, heights))
 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, heights[k], &blocks[k].node, NULL);
 583                     expected[k].x = k;
 584                     expected[k].height = heights[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_heights);
 602       free (heights);
 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 *heights, *new_heights;
 621       int block_cnt;
 622       int *order;
 623       struct block *blocks;
 624
 625       expected = xnmalloc (cnt, sizeof *expected);
 626       heights = xnmalloc (cnt, sizeof *heights);
 627       new_heights = xnmalloc (cnt, sizeof *new_heights);
 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, heights))
 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                                   heights[k], &blocks[k].node, NULL);
 652                     expected[k].x = k;
 653                     expected[k].height = heights[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_heights);
 667       free (heights);
 668       free (order);
 669       free (blocks);
 670     }
 671 }
 672
 673 \f
 674 /* Main program. */
 675
 676 /* Runs TEST_FUNCTION and prints a message about NAME. */
 677 static void
 678 run_test (void (*test_function) (void), const char *name)
 679 {
 680   test_name = name;
 681   putchar ('.');
 682   fflush (stdout);
 683   test_function ();
 684 }
 685
 686 int
 687 main (void)
 688 {
 689   run_test (test_insert, "insert");
 690   run_test (test_delete, "delete");
 691   run_test (test_resize, "resize");
 692   run_test (test_splice_out, "splice out");
 693   run_test (test_splice_in, "splice in");
 694   putchar ('\n');
 695
 696   return 0;
 697 }