-/* PSPP - computes sample statistics.
- Copyright (C) 2007 Free Software Foundation, Inc.
+/* PSPP - a program for statistical analysis.
+ Copyright (C) 2007, 2010 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 the Free Software Foundation; either version 2 of the
- License, or (at your option) any later version.
+ 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
+ the Free Software Foundation, either version 3 of the License, or
+ (at your option) any later version.
- This program is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software
- Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
- 02110-1301, USA. */
+ along with this program. If not, see <http://www.gnu.org/licenses/>. */
/* This is a test program for the routines defined in
range-map.c. This test program aims to be as comprehensive as
#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
-check_die (void)
+check_die (void)
{
- exit (EXIT_FAILURE);
+ exit (EXIT_FAILURE);
}
/* If OK is not true, prints a message about failure on the
current source file and the given LINE and terminates. */
static void
-check_func (bool ok, int line)
+check_func (bool ok, int line)
{
- if (!ok)
+ 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 ();
}
}
\f
/* Swaps *A and *B. */
static void
-swap (int *a, int *b)
+swap (int *a, int *b)
{
int t = *a;
*a = *b;
*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;
- while (i != 0)
+ 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;
}
/* Returns N!. */
static unsigned int
-factorial (unsigned int n)
+factorial (unsigned int n)
{
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;
}
/* Tests whether PARTS is a K-part integer composition of N.
Returns true if so, false otherwise. */
static bool UNUSED
-is_k_composition (int n, int k, const int parts[])
+is_k_composition (int n, int k, const int parts[])
{
int sum;
int i;
already the greatest K-part composition of N (in which case
PARTS is unaltered). */
static bool
-next_k_composition (int n UNUSED, int k, int parts[])
+next_k_composition (int n UNUSED, int k, int parts[])
{
int x, i;
/* Sets the K integers in PARTS to the lexicographically first
K-part composition of N. */
static void
-first_k_composition (int n, int k, int parts[])
+first_k_composition (int n, int k, int parts[])
{
int i;
Returns true if successful, false if the set of compositions
has been exhausted. */
static bool
-next_composition (int n, int *k, int parts[])
+next_composition (int n, int *k, int parts[])
{
if (*k >= 1 && next_k_composition (n, *k, parts))
return true;
};
static struct element *
-range_map_node_to_element (struct range_map_node *node)
+range_map_node_to_element (struct range_map_node *node)
{
return range_map_data (node, struct element, node);
}
/* Element we expect to find. */
-struct expected_element
+struct expected_element
{
int x; /* Primary value. */
unsigned long int start; /* Start of region. */
/* Compares expected_element A and B and returns a strcmp()-type
result. */
static int
-compare_expected_element (const void *a_, const void *b_)
+compare_expected_element (const void *a_, const void *b_)
{
const struct expected_element *a = (const struct expected_element *) a_;
const struct expected_element *b = (const struct expected_element *) b_;
return a->start < b->start ? -1 : a->start > b->start;
}
-/* Checks that RM contains the ELEM_CNT elements described by
+/* Checks that RM contains the ELEM_N elements described by
ELEMENTS[]. */
static void
check_range_map (struct range_map *rm,
- struct expected_element elements[], size_t elem_cnt)
+ struct expected_element elements[], size_t n_elems)
{
struct expected_element *sorted;
struct range_map_node *node;
size_t i;
- sorted = xnmalloc (elem_cnt, sizeof *sorted);
- memcpy (sorted, elements, elem_cnt * sizeof *elements);
- qsort (sorted, elem_cnt, sizeof *sorted, compare_expected_element);
-
- check (range_map_is_empty (rm) == (elem_cnt == 0));
+ sorted = xnmalloc (n_elems, sizeof *sorted);
+ memcpy (sorted, elements, n_elems * sizeof *elements);
+ qsort (sorted, n_elems, sizeof *sorted, compare_expected_element);
- for (i = 0; i < elem_cnt; i++)
+ check (range_map_is_empty (rm) == (n_elems == 0));
+
+ for (i = 0; i < n_elems; i++)
{
struct expected_element *e = &sorted[i];
unsigned long int position;
/* Check that range_map_lookup finds all the positions
within the element. */
- for (position = e->start; position < e->end; position++)
+ for (position = e->start; position < e->end; position++)
{
struct range_map_node *found = range_map_lookup (rm, position);
check (found != NULL);
range_map_lookup doesn't find any there. */
if (e->start > 0 && (i == 0 || e[-1].end < e->start))
check (range_map_lookup (rm, e->start - 1) == NULL);
- if (i == elem_cnt - 1 || e->end < e[1].start)
+ if (i == n_elems - 1 || e->end < e[1].start)
check (range_map_lookup (rm, e->end) == NULL);
}
for (node = (rand () % 2 ? range_map_first (rm) : range_map_next (rm, NULL)),
i = 0;
node != NULL;
- node = range_map_next (rm, node), i++)
+ node = range_map_next (rm, node), i++)
{
struct expected_element *e = &sorted[i];
check (range_map_node_to_element (node)->x == e->x);
}
- check (i == elem_cnt);
+ check (i == n_elems);
free (sorted);
}
in all possible orders, up to a specified maximum overall
range. */
static void
-test_insert (void)
+test_insert (void)
{
const int max_range = 7;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_range; cnt++)
+ for (n = 1; n <= max_range; n++)
{
- unsigned int composition_cnt;
+ unsigned int n_compositions;
struct expected_element *expected;
int *widths;
- int elem_cnt;
+ int n_elems;
int *order;
struct element *elements;
-
- expected = xnmalloc (cnt, sizeof *expected);
- widths = xnmalloc (cnt, sizeof *widths);
- order = xnmalloc (cnt, sizeof *order);
- elements = xnmalloc (cnt, sizeof *elements);
-
- elem_cnt = 0;
- composition_cnt = 0;
- while (next_composition (cnt, &elem_cnt, widths))
+
+ expected = xnmalloc (n, sizeof *expected);
+ widths = xnmalloc (n, sizeof *widths);
+ order = xnmalloc (n, sizeof *order);
+ elements = xnmalloc (n, sizeof *elements);
+
+ n_elems = 0;
+ n_compositions = 0;
+ while (next_composition (n, &n_elems, widths))
{
int i, j;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
- for (i = 0; i < elem_cnt; i++)
+ for (i = 0; i < n_elems; i++)
order[i] = i;
- permutation_cnt = 0;
- while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
+ n_permutations = 0;
+ while (n_permutations == 0 || next_permutation (order, n_elems))
{
struct range_map rm;
- /* Inserts the elem_cnt elements with the given
+ /* Inserts the n_elems elements with the given
widths[] into T in the order given by order[]. */
range_map_init (&rm);
- for (i = 0; i < elem_cnt; i++)
+ for (i = 0; i < n_elems; i++)
{
unsigned long int start, end;
int idx;
expected[i].end = end;
check_range_map (&rm, expected, i + 1);
}
- permutation_cnt++;
+ n_permutations++;
}
- check (permutation_cnt == factorial (elem_cnt));
-
- composition_cnt++;
+ check (n_permutations == factorial (n_elems));
+
+ n_compositions++;
}
- check (composition_cnt == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
free (widths);
/* Tests deleting ranges from a range map in all possible orders,
up to a specified maximum overall range. */
static void
-test_delete (int gap)
+test_delete (int gap)
{
const int max_range = 7;
- int cnt;
+ int n;
- for (cnt = 1; cnt <= max_range; cnt++)
+ for (n = 1; n <= max_range; n++)
{
- unsigned int composition_cnt;
+ unsigned int n_compositions;
struct expected_element *expected;
int *widths;
- int elem_cnt;
+ int n_elems;
int *order;
struct element *elements;
-
- expected = xnmalloc (cnt, sizeof *expected);
- widths = xnmalloc (cnt, sizeof *widths);
- order = xnmalloc (cnt, sizeof *order);
- elements = xnmalloc (cnt, sizeof *elements);
-
- elem_cnt = 0;
- composition_cnt = 0;
- while (next_composition (cnt, &elem_cnt, widths))
+
+ expected = xnmalloc (n, sizeof *expected);
+ widths = xnmalloc (n, sizeof *widths);
+ order = xnmalloc (n, sizeof *order);
+ elements = xnmalloc (n, sizeof *elements);
+
+ n_elems = 0;
+ n_compositions = 0;
+ while (next_composition (n, &n_elems, widths))
{
int i, j;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
- for (i = 0; i < elem_cnt; i++)
+ for (i = 0; i < n_elems; i++)
order[i] = i;
- permutation_cnt = 0;
- while (permutation_cnt == 0 || next_permutation (order, elem_cnt))
+ n_permutations = 0;
+ while (n_permutations == 0 || next_permutation (order, n_elems))
{
struct range_map rm;
unsigned long int start;
/* Insert all the elements. */
range_map_init (&rm);
start = 0;
- for (i = 0; i < elem_cnt; i++)
+ for (i = 0; i < n_elems; i++)
{
int width = widths[i] > gap ? widths[i] - gap : widths[i];
unsigned long int end = start + width;
range_map_insert (&rm, start, end - start,
&elements[i].node);
- for (j = 0; ; j++)
+ for (j = 0; ; j++)
{
- assert (j < elem_cnt);
- if (order[j] == i)
+ assert (j < n_elems);
+ if (order[j] == i)
{
expected[j].x = i;
expected[j].start = start;
break;
}
}
-
+
start += widths[i];
}
- check_range_map (&rm, expected, elem_cnt);
+ check_range_map (&rm, expected, n_elems);
/* Delete the elements in the specified order. */
- for (i = 0; i < elem_cnt; i++)
+ for (i = 0; i < n_elems; i++)
{
range_map_delete (&rm, &elements[order[i]].node);
- check_range_map (&rm, expected + i + 1, elem_cnt - i - 1);
+ check_range_map (&rm, expected + i + 1, n_elems - i - 1);
}
- permutation_cnt++;
+ n_permutations++;
}
- check (permutation_cnt == factorial (elem_cnt));
-
- composition_cnt++;
+ check (n_permutations == factorial (n_elems));
+
+ n_compositions++;
}
- check (composition_cnt == 1 << (cnt - 1));
+ check (n_compositions == 1 << (n - 1));
free (expected);
free (widths);
ranges in all possible orders, up to a specified maximum
overall range. */
static void
-test_delete_contiguous (void)
+test_delete_contiguous (void)
{
test_delete (0);
}
sometimes separated by gaps in all possible orders, up to a
specified maximum overall range. */
static void
-test_delete_gaps (void)
+test_delete_gaps (void)
{
test_delete (1);
}
\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-contiguous",
+ "delete from contiguous ranges",
+ test_delete_contiguous
+ },
+ {
+ "delete-gaps",
+ "delete from ranges separated by gaps",
+ test_delete_gaps
+ },
+ };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };
int
-main (void)
+main (int argc, char *argv[])
{
- run_test (test_insert, "insert");
- run_test (test_delete_contiguous, "delete from contiguous ranges");
- run_test (test_delete_gaps, "delete from ranges separated by gaps");
- putchar ('\n');
+ int i;
- return 0;
+ 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 range map 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;
+ }
}