1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007 Free Software Foundation, Inc.
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.
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.
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/>. */
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. */
29 #include <libpspp/tower.h>
38 #include <libpspp/compiler.h>
42 /* Currently running test. */
43 static const char *test_name;
45 /* Exit with a failure code.
46 (Place a breakpoint on this function while debugging.) */
53 /* If OK is not true, prints a message about failure on the
54 current source file and the given LINE and terminates. */
56 check_func (bool ok, int line)
60 printf ("Check failed in %s test at %s, line %d\n",
61 test_name, __FILE__, line);
66 /* Verifies that EXPR evaluates to true.
67 If not, prints a message citing the calling line number and
69 #define check(EXPR) check_func ((EXPR), __LINE__)
71 /* Node type and support routines. */
73 /* Test data block. */
76 struct tower_node node; /* Embedded tower block. */
77 int x; /* Primary value. */
80 /* Returns the `struct block' that NODE is embedded within. */
82 tower_node_to_block (const struct tower_node *node)
84 return tower_data (node, struct block, node);
87 /* Swaps *A and *B. */
96 /* Reverses the order of the CNT integers starting at VALUES. */
98 reverse (int *values, size_t cnt)
104 swap (&values[i++], &values[--j]);
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
115 next_permutation (int *values, size_t cnt)
123 if (values[i] < values[i + 1])
126 for (j = cnt - 1; values[i] >= values[j]; j--)
128 swap (values + i, values + j);
129 reverse (values + (i + 1), cnt - (i + 1));
134 reverse (values, cnt);
142 factorial (unsigned int n)
144 unsigned int value = 1;
145 /* Disallow N values that overflow on 32-bit machines. */
152 /* Returns C(n, k), the number of ways that K choices can be made
153 from N items when order is unimportant. */
155 binomial_cofficient (unsigned int n, unsigned int k)
158 return factorial (n) / factorial (k) / factorial (n - k);
161 /* Tests whether PARTS is a K-part integer composition of N.
162 Returns true if so, false otherwise. */
164 is_k_composition (int n, int k, const int parts[])
170 for (i = 0; i < k; i++)
172 if (parts[i] < 1 || parts[i] > n)
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). */
185 next_k_composition (int n UNUSED, int k, int parts[])
189 assert (is_k_composition (n, k, parts));
193 for (i = k - 1; i > 0; i--)
204 assert (is_k_composition (n, k, parts));
208 /* Sets the K integers in PARTS to the lexicographically first
209 K-part composition of N. */
211 first_k_composition (int n, int k, int parts[])
217 for (i = 0; i < k; i++)
219 parts[k - 1] += n - k;
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
229 Returns true if successful, false if the set of compositions
230 has been exhausted. */
232 next_composition (int n, int *k, int parts[])
234 if (*k >= 1 && next_k_composition (n, *k, parts))
238 first_k_composition (n, ++*k, parts);
245 /* A block expected to be found in a tower. */
246 struct expected_block
248 int size; /* Expected thickness of block. */
249 int x; /* Expected value for `x' member. */
252 /* Checks that tower T contains the BLOCK_CNT blocks described by
255 check_tower (struct tower *t,
256 struct expected_block blocks[], size_t block_cnt)
259 struct tower_node *node;
262 check (tower_count (t) == block_cnt);
263 check (tower_is_empty (t) == (block_cnt == 0));
266 for (i = 0; i < block_cnt; i++)
268 unsigned long int level;
269 for (level = total_height;
270 level < total_height + blocks[i].size;
273 struct tower_node *found;
274 unsigned long int block_start;
275 found = tower_lookup (t, level, &block_start);
276 check (found != NULL);
277 check (tower_node_to_block (found)->x == blocks[i].x);
278 check (block_start == total_height);
279 check (tower_node_get_level (found) == total_height);
280 check (tower_node_get_index (found) == i);
281 check (tower_get (t, i) == found);
283 total_height += blocks[i].size;
285 check (tower_height (t) == total_height);
287 for (node = tower_first (t), i = 0;
289 node = tower_next (t, node), i++)
291 check (tower_node_get_size (node) == blocks[i].size);
292 check (tower_node_to_block (node)->x == blocks[i].x);
294 check (i == block_cnt);
296 for (node = tower_last (t), i = block_cnt - 1;
298 node = tower_prev (t, node), i--)
300 check (tower_node_get_size (node) == blocks[i].size);
301 check (tower_node_to_block (node)->x == blocks[i].x);
303 check (i == SIZE_MAX);
306 /* Tests inserting all possible sets of block heights into a
307 tower in all possible orders, up to a specified maximum tower
312 const int max_height = 7;
315 for (cnt = 1; cnt <= max_height; cnt++)
317 unsigned int composition_cnt;
318 struct expected_block *expected;
322 struct block *blocks;
324 expected = xnmalloc (cnt, sizeof *expected);
325 sizes = xnmalloc (cnt, sizeof *sizes);
326 order = xnmalloc (cnt, sizeof *order);
327 blocks = xnmalloc (cnt, sizeof *blocks);
331 while (next_composition (cnt, &block_cnt, sizes))
334 unsigned int permutation_cnt;
336 for (i = 0; i < block_cnt; i++)
340 while (permutation_cnt == 0 || next_permutation (order, block_cnt))
344 /* Inserts the block_cnt blocks with the given
345 sizes[] into T in the order given by order[]. */
347 for (i = 0; i < block_cnt; i++)
356 for (j = 0; j < i; j++)
358 && (under == NULL || under->x > order[j]))
359 under = &blocks[order[j]];
361 tower_insert (&t, sizes[idx], &blocks[idx].node,
362 under != NULL ? &under->node : NULL);
365 /* Check that the result is what we expect. */
366 for (i = 0; i < block_cnt; i++)
368 expected[i].size = sizes[i];
371 check_tower (&t, expected, block_cnt);
375 check (permutation_cnt == factorial (block_cnt));
379 check (composition_cnt == 1 << (cnt - 1));
388 /* Tests deleting blocks from towers that initially contain all
389 possible sets of block sizes into a tower in all possible
390 orders, up to a specified maximum tower height. */
394 const int max_height = 7;
397 for (cnt = 1; cnt <= max_height; cnt++)
399 unsigned int composition_cnt;
400 struct expected_block *expected;
404 struct block *blocks;
406 expected = xnmalloc (cnt, sizeof *expected);
407 sizes = xnmalloc (cnt, sizeof *sizes);
408 order = xnmalloc (cnt, sizeof *order);
409 blocks = xnmalloc (cnt, sizeof *blocks);
413 while (next_composition (cnt, &block_cnt, sizes))
416 unsigned int permutation_cnt;
418 for (i = 0; i < block_cnt; i++)
422 while (permutation_cnt == 0 || next_permutation (order, block_cnt))
426 /* Insert blocks into tower in ascending order. */
428 for (i = 0; i < block_cnt; i++)
431 tower_insert (&t, sizes[i], &blocks[i].node, NULL);
433 expected[i].size = sizes[i];
435 check_tower (&t, expected, block_cnt);
437 /* Delete blocks from tower in the order of
439 for (i = 0; i < block_cnt; i++)
443 tower_delete (&t, &blocks[idx].node);
446 assert (j < block_cnt - i);
447 if (expected[j].x == idx)
449 memcpy (&expected[j], &expected[j + 1],
450 sizeof *expected * (block_cnt - i - j - 1));
454 check_tower (&t, expected, block_cnt - i - 1);
459 check (permutation_cnt == factorial (block_cnt));
463 check (composition_cnt == 1 << (cnt - 1));
472 /* Tests towers containing all possible block sizes, resizing
473 the blocks to all possible sizes that conserve the total
474 tower height, up to a maximum total tower height. */
478 const int max_height = 9;
481 for (cnt = 1; cnt <= max_height; cnt++)
483 unsigned int composition_cnt;
484 struct expected_block *expected;
485 int *sizes, *new_sizes;
488 struct block *blocks;
490 expected = xnmalloc (cnt, sizeof *expected);
491 sizes = xnmalloc (cnt, sizeof *sizes);
492 new_sizes = xnmalloc (cnt, sizeof *new_sizes);
493 order = xnmalloc (cnt, sizeof *order);
494 blocks = xnmalloc (cnt, sizeof *blocks);
498 while (next_composition (cnt, &block_cnt, sizes))
501 unsigned int resizes = 0;
503 for (resizes = 0, first_k_composition (cnt, block_cnt, new_sizes);
505 || next_k_composition (cnt, block_cnt, new_sizes));
510 /* Insert blocks into tower in ascending order. */
512 for (i = 0; i < block_cnt; i++)
515 tower_insert (&t, sizes[i], &blocks[i].node, NULL);
517 expected[i].size = sizes[i];
519 check_tower (&t, expected, block_cnt);
521 /* Resize all the blocks. */
522 for (i = 0; i < block_cnt; i++)
524 if (expected[i].size != new_sizes[i] || rand () % 2)
525 tower_resize (&t, &blocks[i].node, new_sizes[i]);
526 expected[i].size = new_sizes[i];
528 check_tower (&t, expected, block_cnt);
530 check (resizes == binomial_cofficient (cnt - 1, block_cnt - 1));
534 check (composition_cnt == 1 << (cnt - 1));
544 /* Tests splicing all possible contiguous sets of blocks out of one
545 tower into a second, initially empty tower. */
547 test_splice_out (void)
549 const int max_height = 9;
552 for (cnt = 1; cnt <= max_height; cnt++)
554 unsigned int composition_cnt;
555 struct expected_block *expected;
556 int *sizes, *new_sizes;
559 struct block *blocks;
561 expected = xnmalloc (cnt, sizeof *expected);
562 sizes = xnmalloc (cnt, sizeof *sizes);
563 new_sizes = xnmalloc (cnt, sizeof *new_sizes);
564 order = xnmalloc (cnt, sizeof *order);
565 blocks = xnmalloc (cnt, sizeof *blocks);
569 while (next_composition (cnt, &block_cnt, sizes))
573 for (i = 0; i < block_cnt; i++)
574 for (j = i; j <= block_cnt; j++)
576 struct tower src, dst;
582 /* Insert blocks into SRC and DST in ascending order. */
583 for (k = 0; k < block_cnt; k++)
586 tower_insert (&src, sizes[k], &blocks[k].node, NULL);
588 expected[k].size = sizes[k];
590 check_tower (&src, expected, block_cnt);
592 /* Splice blocks I...J into DST. */
593 tower_splice (&dst, NULL, &src, &blocks[i].node,
594 j < block_cnt ? &blocks[j].node : NULL);
595 check_tower (&dst, &expected[i], j - i);
596 memmove (&expected[i], &expected[j],
597 sizeof *expected * (block_cnt - j));
598 check_tower (&src, expected, block_cnt - (j - i));
602 check (composition_cnt == 1 << (cnt - 1));
612 /* Tests splicing all of the contents of a tower into all
613 possible positions in a second tower. */
615 test_splice_in (void)
617 const int max_height = 9;
620 for (cnt = 1; cnt <= max_height; cnt++)
622 unsigned int composition_cnt;
623 struct expected_block *expected;
624 int *sizes, *new_sizes;
627 struct block *blocks;
629 expected = xnmalloc (cnt, sizeof *expected);
630 sizes = xnmalloc (cnt, sizeof *sizes);
631 new_sizes = xnmalloc (cnt, sizeof *new_sizes);
632 order = xnmalloc (cnt, sizeof *order);
633 blocks = xnmalloc (cnt, sizeof *blocks);
637 while (next_composition (cnt, &block_cnt, sizes))
641 for (i = 0; i < block_cnt; i++)
642 for (j = i; j <= block_cnt; j++)
644 struct tower src, dst;
650 /* Insert blocks into SRC and DST in ascending order. */
651 for (k = 0; k < block_cnt; k++)
654 tower_insert (k >= i && k < j ? &src : &dst,
655 sizes[k], &blocks[k].node, NULL);
657 expected[k].size = sizes[k];
660 /* Splice SRC into DST. */
661 tower_splice (&dst, j < block_cnt ? &blocks[j].node : NULL,
662 &src, i != j ? &blocks[i].node : NULL, NULL);
663 check_tower (&dst, expected, block_cnt);
667 check (composition_cnt == 1 << (cnt - 1));
680 /* Runs TEST_FUNCTION and prints a message about NAME. */
682 run_test (void (*test_function) (void), const char *name)
693 run_test (test_insert, "insert");
694 run_test (test_delete, "delete");
695 run_test (test_resize, "resize");
696 run_test (test_splice_out, "splice out");
697 run_test (test_splice_in, "splice in");