/* PSPP - a program for statistical analysis.
- Copyright (C) 2007 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2010, 2013 Free Software Foundation, Inc.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
#include "xalloc.h"
\f
-/* Currently running test. */
-static const char *test_name;
-
/* Exit with a failure code.
(Place a breakpoint on this function while debugging.) */
static void
{
if (!ok)
{
- printf ("Check failed in %s test at %s, line %d\n",
- test_name, __FILE__, line);
+ fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
check_die ();
}
}
*b = t;
}
-/* Reverses the order of the CNT integers starting at VALUES. */
+/* Reverses the order of the N integers starting at VALUES. */
static void
-reverse (int *values, size_t cnt)
+reverse (int *values, size_t n)
{
size_t i = 0;
- size_t j = cnt;
+ size_t j = n;
while (j > i)
swap (&values[i++], &values[--j]);
}
-/* Arranges the CNT blocks in VALUES into the lexicographically
+/* Arranges the N blocks in VALUES into the lexicographically
next greater permutation. Returns true if successful.
If VALUES is already the lexicographically greatest
permutation of its blocks (i.e. ordered from greatest to
permutation (i.e. ordered from smallest to largest) and
returns false. */
static bool
-next_permutation (int *values, size_t cnt)
+next_permutation (int *values, size_t n)
{
- if (cnt > 0)
+ if (n > 0)
{
- size_t i = cnt - 1;
+ size_t i = n - 1;
while (i != 0)
{
i--;
if (values[i] < values[i + 1])
{
size_t j;
- for (j = cnt - 1; values[i] >= values[j]; j--)
+ for (j = n - 1; values[i] >= values[j]; j--)
continue;
swap (values + i, values + j);
- reverse (values + (i + 1), cnt - (i + 1));
+ reverse (values + (i + 1), n - (i + 1));
return true;
}
}
- reverse (values, cnt);
+ reverse (values, n);
}
return false;
unsigned int value = 1;
/* Disallow N values that overflow on 32-bit machines. */
assert (n <= 12);
- for (; n > 1; )
+ for (; n > 1;)
value *= n--;
return value;
}
/* A block expected to be found in a tower. */
struct expected_block
{
- int height; /* Expected height of bottom of block. */
+ int size; /* Expected thickness of block. */
int x; /* Expected value for `x' member. */
};
-/* Checks that tower T contains the BLOCK_CNT blocks described by
+/* Checks that tower T contains the BLOCK_N blocks described by
BLOCKS[]. */
static void
check_tower (struct tower *t,
- struct expected_block blocks[], size_t block_cnt)
+ struct expected_block blocks[], size_t n_blocks)
{
int total_height;
struct tower_node *node;
size_t i;
- check (tower_is_empty (t) == (block_cnt == 0));
+ check (tower_count (t) == n_blocks);
+ check (tower_is_empty (t) == (n_blocks == 0));
total_height = 0;
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; i++)
{
unsigned long int level;
for (level = total_height;
- level < total_height + blocks[i].height;
+ level < total_height + blocks[i].size;
level++)
{
struct tower_node *found;
check (found != NULL);
check (tower_node_to_block (found)->x == blocks[i].x);
check (block_start == total_height);
+ check (tower_node_get_level (found) == total_height);
+ check (tower_node_get_index (found) == i);
+ check (tower_get (t, i) == found);
}
- total_height += blocks[i].height;
+ total_height += blocks[i].size;
}
check (tower_height (t) == total_height);
node != NULL;
node = tower_next (t, node), i++)
{
- check (tower_node_get_height (node) == blocks[i].height);
+ check (tower_node_get_size (node) == blocks[i].size);
check (tower_node_to_block (node)->x == blocks[i].x);
}
- check (i == block_cnt);
+ check (i == n_blocks);
- for (node = tower_last (t), i = block_cnt - 1;
+ for (node = tower_last (t), i = n_blocks - 1;
node != NULL;
node = tower_prev (t, node), i--)
{
- check (tower_node_get_height (node) == blocks[i].height);
+ check (tower_node_get_size (node) == blocks[i].size);
check (tower_node_to_block (node)->x == blocks[i].x);
}
check (i == SIZE_MAX);
test_insert (void)
{
const int max_height = 7;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
- unsigned int composition_cnt;
+ unsigned int n_compositions;
struct expected_block *expected;
- int *heights;
- int block_cnt;
+ int *sizes;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
- block_cnt = 0;
- composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ n_blocks = 0;
+ n_compositions = 0;
+ while (next_composition (n, &n_blocks, sizes))
{
int i, j;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; i++)
order[i] = i;
- permutation_cnt = 0;
- while (permutation_cnt == 0 || next_permutation (order, block_cnt))
+ n_permutations = 0;
+ while (n_permutations == 0 || next_permutation (order, n_blocks))
{
struct tower t;
- /* Inserts the block_cnt blocks with the given
- heights[] into T in the order given by order[]. */
+ /* Inserts the n_blocks blocks with the given
+ sizes[] into T in the order given by order[]. */
tower_init (&t);
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; i++)
{
struct block *under;
int idx;
&& (under == NULL || under->x > order[j]))
under = &blocks[order[j]];
- tower_insert (&t, heights[idx], &blocks[idx].node,
+ tower_insert (&t, sizes[idx], &blocks[idx].node,
under != NULL ? &under->node : NULL);
}
/* Check that the result is what we expect. */
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; i++)
{
- expected[i].height = heights[i];
+ expected[i].size = sizes[i];
expected[i].x = i;
}
- check_tower (&t, expected, block_cnt);
+ check_tower (&t, expected, n_blocks);
- permutation_cnt++;
+ n_permutations++;
}
- check (permutation_cnt == factorial (block_cnt));
+ check (n_permutations == factorial (n_blocks));
- composition_cnt++;
+ n_compositions++;
}
- check (composition_cnt == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
- free (heights);
+ free (sizes);
free (order);
free (blocks);
}
}
/* Tests deleting blocks from towers that initially contain all
- possible sets of block heights into a tower in all possible
+ possible sets of block sizes into a tower in all possible
orders, up to a specified maximum tower height. */
static void
test_delete (void)
{
const int max_height = 7;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
- unsigned int composition_cnt;
+ unsigned int n_compositions;
struct expected_block *expected;
- int *heights;
- int block_cnt;
+ int *sizes;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
- block_cnt = 0;
- composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ n_blocks = 0;
+ n_compositions = 0;
+ while (next_composition (n, &n_blocks, sizes))
{
int i;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; i++)
order[i] = i;
- permutation_cnt = 0;
- while (permutation_cnt == 0 || next_permutation (order, block_cnt))
+ n_permutations = 0;
+ while (n_permutations == 0 || next_permutation (order, n_blocks))
{
struct tower t;
/* Insert blocks into tower in ascending order. */
tower_init (&t);
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; i++)
{
blocks[i].x = i;
- tower_insert (&t, heights[i], &blocks[i].node, NULL);
+ tower_insert (&t, sizes[i], &blocks[i].node, NULL);
expected[i].x = i;
- expected[i].height = heights[i];
+ expected[i].size = sizes[i];
}
- check_tower (&t, expected, block_cnt);
+ check_tower (&t, expected, n_blocks);
/* Delete blocks from tower in the order of
order[]. */
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; i++)
{
int idx = order[i];
int j;
tower_delete (&t, &blocks[idx].node);
for (j = 0; ; j++)
{
- assert (j < block_cnt - i);
+ assert (j < n_blocks - i);
if (expected[j].x == idx)
{
- memcpy (&expected[j], &expected[j + 1],
- sizeof *expected * (block_cnt - i - j - 1));
+ memmove (&expected[j], &expected[j + 1],
+ sizeof *expected * (n_blocks - i - j - 1));
break;
}
}
- check_tower (&t, expected, block_cnt - i - 1);
+ check_tower (&t, expected, n_blocks - i - 1);
}
- permutation_cnt++;
+ n_permutations++;
}
- check (permutation_cnt == factorial (block_cnt));
+ check (n_permutations == factorial (n_blocks));
- composition_cnt++;
+ n_compositions++;
}
- check (composition_cnt == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
- free (heights);
+ free (sizes);
free (order);
free (blocks);
}
}
-/* Tests towers containing all possible block heights, resizing
- the blocks to all possible heights that conserve the total
+/* Tests towers containing all possible block sizes, resizing
+ the blocks to all possible sizes that conserve the total
tower height, up to a maximum total tower height. */
static void
test_resize (void)
{
const int max_height = 9;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
- unsigned int composition_cnt;
+ unsigned int n_compositions;
struct expected_block *expected;
- int *heights, *new_heights;
- int block_cnt;
+ int *sizes, *new_sizes;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
- new_heights = xnmalloc (cnt, sizeof *new_heights);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ new_sizes = xnmalloc (n, sizeof *new_sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
- block_cnt = 0;
- composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ n_blocks = 0;
+ n_compositions = 0;
+ while (next_composition (n, &n_blocks, sizes))
{
int i;
unsigned int resizes = 0;
- for (resizes = 0, first_k_composition (cnt, block_cnt, new_heights);
+ for (resizes = 0, first_k_composition (n, n_blocks, new_sizes);
(resizes == 0
- || next_k_composition (cnt, block_cnt, new_heights));
+ || next_k_composition (n, n_blocks, new_sizes));
resizes++)
{
struct tower t;
/* Insert blocks into tower in ascending order. */
tower_init (&t);
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; i++)
{
blocks[i].x = i;
- tower_insert (&t, heights[i], &blocks[i].node, NULL);
+ tower_insert (&t, sizes[i], &blocks[i].node, NULL);
expected[i].x = i;
- expected[i].height = heights[i];
+ expected[i].size = sizes[i];
}
- check_tower (&t, expected, block_cnt);
+ check_tower (&t, expected, n_blocks);
/* Resize all the blocks. */
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; i++)
{
- if (expected[i].height != new_heights[i] || rand () % 2)
- tower_resize (&t, &blocks[i].node, new_heights[i]);
- expected[i].height = new_heights[i];
+ if (expected[i].size != new_sizes[i] || rand () % 2)
+ tower_resize (&t, &blocks[i].node, new_sizes[i]);
+ expected[i].size = new_sizes[i];
}
- check_tower (&t, expected, block_cnt);
+ check_tower (&t, expected, n_blocks);
}
- check (resizes == binomial_cofficient (cnt - 1, block_cnt - 1));
+ check (resizes == binomial_cofficient (n - 1, n_blocks - 1));
- composition_cnt++;
+ n_compositions++;
}
- check (composition_cnt == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
- free (new_heights);
- free (heights);
+ free (new_sizes);
+ free (sizes);
free (order);
free (blocks);
}
test_splice_out (void)
{
const int max_height = 9;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
- unsigned int composition_cnt;
+ unsigned int n_compositions;
struct expected_block *expected;
- int *heights, *new_heights;
- int block_cnt;
+ int *sizes, *new_sizes;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
- new_heights = xnmalloc (cnt, sizeof *new_heights);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ new_sizes = xnmalloc (n, sizeof *new_sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
- block_cnt = 0;
- composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ n_blocks = 0;
+ n_compositions = 0;
+ while (next_composition (n, &n_blocks, sizes))
{
int i, j;
- for (i = 0; i < block_cnt; i++)
- for (j = i; j <= block_cnt; j++)
+ for (i = 0; i < n_blocks; i++)
+ for (j = i; j <= n_blocks; j++)
{
struct tower src, dst;
int k;
tower_init (&dst);
/* Insert blocks into SRC and DST in ascending order. */
- for (k = 0; k < block_cnt; k++)
+ for (k = 0; k < n_blocks; k++)
{
blocks[k].x = k;
- tower_insert (&src, heights[k], &blocks[k].node, NULL);
+ tower_insert (&src, sizes[k], &blocks[k].node, NULL);
expected[k].x = k;
- expected[k].height = heights[k];
+ expected[k].size = sizes[k];
}
- check_tower (&src, expected, block_cnt);
+ check_tower (&src, expected, n_blocks);
/* Splice blocks I...J into DST. */
tower_splice (&dst, NULL, &src, &blocks[i].node,
- j < block_cnt ? &blocks[j].node : NULL);
+ j < n_blocks ? &blocks[j].node : NULL);
check_tower (&dst, &expected[i], j - i);
memmove (&expected[i], &expected[j],
- sizeof *expected * (block_cnt - j));
- check_tower (&src, expected, block_cnt - (j - i));
+ sizeof *expected * (n_blocks - j));
+ check_tower (&src, expected, n_blocks - (j - i));
}
- composition_cnt++;
+ n_compositions++;
}
- check (composition_cnt == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
- free (new_heights);
- free (heights);
+ free (new_sizes);
+ free (sizes);
free (order);
free (blocks);
}
test_splice_in (void)
{
const int max_height = 9;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_height; cnt++)
+ for (n = 1; n <= max_height; n++)
{
- unsigned int composition_cnt;
+ unsigned int n_compositions;
struct expected_block *expected;
- int *heights, *new_heights;
- int block_cnt;
+ int *sizes, *new_sizes;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- heights = xnmalloc (cnt, sizeof *heights);
- new_heights = xnmalloc (cnt, sizeof *new_heights);
- order = xnmalloc (cnt, sizeof *order);
- blocks = xnmalloc (cnt, sizeof *blocks);
+ expected = xnmalloc (n, sizeof *expected);
+ sizes = xnmalloc (n, sizeof *sizes);
+ new_sizes = xnmalloc (n, sizeof *new_sizes);
+ order = xnmalloc (n, sizeof *order);
+ blocks = xnmalloc (n, sizeof *blocks);
- block_cnt = 0;
- composition_cnt = 0;
- while (next_composition (cnt, &block_cnt, heights))
+ n_blocks = 0;
+ n_compositions = 0;
+ while (next_composition (n, &n_blocks, sizes))
{
int i, j;
- for (i = 0; i < block_cnt; i++)
- for (j = i; j <= block_cnt; j++)
+ for (i = 0; i < n_blocks; i++)
+ for (j = i; j <= n_blocks; j++)
{
struct tower src, dst;
int k;
tower_init (&dst);
/* Insert blocks into SRC and DST in ascending order. */
- for (k = 0; k < block_cnt; k++)
+ for (k = 0; k < n_blocks; k++)
{
blocks[k].x = k;
tower_insert (k >= i && k < j ? &src : &dst,
- heights[k], &blocks[k].node, NULL);
+ sizes[k], &blocks[k].node, NULL);
expected[k].x = k;
- expected[k].height = heights[k];
+ expected[k].size = sizes[k];
}
/* Splice SRC into DST. */
- tower_splice (&dst, j < block_cnt ? &blocks[j].node : NULL,
+ tower_splice (&dst, j < n_blocks ? &blocks[j].node : NULL,
&src, i != j ? &blocks[i].node : NULL, NULL);
- check_tower (&dst, expected, block_cnt);
+ check_tower (&dst, expected, n_blocks);
}
- composition_cnt++;
+ n_compositions++;
}
- check (composition_cnt == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
- free (new_heights);
- free (heights);
+ free (new_sizes);
+ free (sizes);
free (order);
free (blocks);
}
\f
/* Main program. */
-/* Runs TEST_FUNCTION and prints a message about NAME. */
-static void
-run_test (void (*test_function) (void), const char *name)
-{
- test_name = name;
- putchar ('.');
- fflush (stdout);
- test_function ();
-}
+struct test
+ {
+ const char *name;
+ const char *description;
+ void (*function) (void);
+ };
+
+static const struct test tests[] =
+ {
+ {
+ "insert",
+ "insert",
+ test_insert
+ },
+ {
+ "delete",
+ "delete",
+ test_delete
+ },
+ {
+ "resize",
+ "resize",
+ test_resize
+ },
+ {
+ "splice-out",
+ "splice out",
+ test_splice_out
+ },
+ {
+ "splice-in",
+ "splice in",
+ test_splice_in
+ },
+ };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };
int
-main (void)
+main (int argc, char *argv[])
{
- run_test (test_insert, "insert");
- run_test (test_delete, "delete");
- run_test (test_resize, "resize");
- run_test (test_splice_out, "splice out");
- run_test (test_splice_in, "splice in");
- putchar ('\n');
-
- return 0;
+ int i;
+
+ if (argc != 2)
+ {
+ fprintf (stderr, "exactly one argument required; use --help for help\n");
+ return EXIT_FAILURE;
+ }
+ else if (!strcmp (argv[1], "--help"))
+ {
+ printf ("%s: test tower library\n"
+ "usage: %s TEST-NAME\n"
+ "where TEST-NAME is one of the following:\n",
+ argv[0], argv[0]);
+ for (i = 0; i < N_TESTS; i++)
+ printf (" %s\n %s\n", tests[i].name, tests[i].description);
+ return 0;
+ }
+ else
+ {
+ for (i = 0; i < N_TESTS; i++)
+ if (!strcmp (argv[1], tests[i].name))
+ {
+ tests[i].function ();
+ return 0;
+ }
+
+ fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
+ return EXIT_FAILURE;
+ }
}