/* 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;
}
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_count (t) == block_cnt);
- 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;
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--)
{
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 *sizes;
- int block_cnt;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- 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, sizes))
+ 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
+ /* 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;
}
/* Check that the result is what we expect. */
- for (i = 0; i < block_cnt; i++)
+ for (i = 0; i < n_blocks; 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 (sizes);
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 *sizes;
- int block_cnt;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- 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, sizes))
+ 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, sizes[i], &blocks[i].node, NULL);
expected[i].x = 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 (sizes);
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 *sizes, *new_sizes;
- int block_cnt;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- new_sizes = xnmalloc (cnt, sizeof *new_sizes);
- 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, sizes))
+ 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_sizes);
+ for (resizes = 0, first_k_composition (n, n_blocks, new_sizes);
(resizes == 0
- || next_k_composition (cnt, block_cnt, new_sizes));
+ || 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, sizes[i], &blocks[i].node, NULL);
expected[i].x = 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].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_sizes);
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 *sizes, *new_sizes;
- int block_cnt;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- new_sizes = xnmalloc (cnt, sizeof *new_sizes);
- 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, sizes))
+ 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, sizes[k], &blocks[k].node, NULL);
expected[k].x = 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_sizes);
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 *sizes, *new_sizes;
- int block_cnt;
+ int n_blocks;
int *order;
struct block *blocks;
- expected = xnmalloc (cnt, sizeof *expected);
- sizes = xnmalloc (cnt, sizeof *sizes);
- new_sizes = xnmalloc (cnt, sizeof *new_sizes);
- 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, sizes))
+ 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,
}
/* 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_sizes);
\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;
+ }
}