/* PSPP - a program for statistical analysis.
- Copyright (C) 2007 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2010, 2011 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 <libpspp/abt.h>
-#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <libpspp/compiler.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 ();
}
}
static struct element *
abt_node_to_element (const struct abt_node *node)
{
- return abt_data (node, struct element, node);
+ return ABT_DATA (node, struct element, node);
}
/* Compares the `x' values in A and B and returns a strcmp-type
/* Recalculates the count for NODE's subtree by adding up the
counts for its LEFT and RIGHT child subtrees. */
static void
-reaugment_elements (struct abt_node *node_,
- const struct abt_node *left,
- const struct abt_node *right,
- const void *aux)
+reaugment_elements (struct abt_node *node_, const void *aux)
{
struct element *node = abt_node_to_element (node_);
check (aux == &aux_data);
node->count = 1;
- if (left != NULL)
- node->count += abt_node_to_element (left)->count;
- if (right != NULL)
- node->count += abt_node_to_element (right)->count;
+ if (node->node.down[0] != NULL)
+ node->count += abt_node_to_element (node->node.down[0])->count;
+ if (node->node.down[1] != NULL)
+ node->count += abt_node_to_element (node->node.down[1])->count;
}
/* Compares A and B and returns a strcmp-type return value. */
find_by_position (struct abt *abt, int position)
{
struct abt_node *p;
- for (p = abt->root; p != NULL; )
+ for (p = abt->root; p != NULL;)
{
int p_pos = p->down[0] ? abt_node_to_element (p->down[0])->count : 0;
if (position == p_pos)
check (abt_node_to_element (p)->data == order[cnt - i - 1]);
check (p == NULL);
}
+ check (abt_is_empty (abt) == (cnt == 0));
free (order);
}
for (cnt = 0; cnt <= max_elems; cnt++)
{
int *insertions, *deletions;
- unsigned int ins_perm_cnt;
+ unsigned int ins_n_perms;
int i;
insertions = xnmalloc (cnt, sizeof *insertions);
for (i = 0; i < cnt; i++)
insertions[i] = i;
- for (ins_perm_cnt = 0;
- ins_perm_cnt == 0 || next_permutation (insertions, cnt);
- ins_perm_cnt++)
+ for (ins_n_perms = 0;
+ ins_n_perms == 0 || next_permutation (insertions, cnt);
+ ins_n_perms++)
{
- unsigned int del_perm_cnt;
+ unsigned int del_n_perms;
int i;
for (i = 0; i < cnt; i++)
deletions[i] = i;
- for (del_perm_cnt = 0;
- del_perm_cnt == 0 || next_permutation (deletions, cnt);
- del_perm_cnt++)
+ for (del_n_perms = 0;
+ del_n_perms == 0 || next_permutation (deletions, cnt);
+ del_n_perms++)
test_insert_delete (insertions, deletions, cnt);
- check (del_perm_cnt == factorial (cnt));
+ check (del_n_perms == factorial (cnt));
}
- check (ins_perm_cnt == factorial (cnt));
+ check (ins_n_perms == factorial (cnt));
free (insertions);
free (deletions);
for (cnt = 0; cnt <= max_elems; cnt++)
{
int *values;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
int i;
values = xnmalloc (cnt, sizeof *values);
for (i = 0; i < cnt; i++)
values[i] = i;
- for (permutation_cnt = 0;
- permutation_cnt == 0 || next_permutation (values, cnt);
- permutation_cnt++)
+ for (n_permutations = 0;
+ n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations++)
test_insert_delete (values, values, cnt);
- check (permutation_cnt == factorial (cnt));
+ check (n_permutations == factorial (cnt));
free (values);
}
for (cnt = 0; cnt <= max_elems; cnt++)
{
int *insertions, *deletions;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
int i;
insertions = xnmalloc (cnt, sizeof *insertions);
for (i = 0; i < cnt; i++)
insertions[i] = i;
- for (permutation_cnt = 0;
- permutation_cnt == 0 || next_permutation (insertions, cnt);
- permutation_cnt++)
+ for (n_permutations = 0;
+ n_permutations == 0 || next_permutation (insertions, cnt);
+ n_permutations++)
{
memcpy (deletions, insertions, sizeof *insertions * cnt);
reverse (deletions, cnt);
test_insert_delete (insertions, deletions, cnt);
}
- check (permutation_cnt == factorial (cnt));
+ check (n_permutations == factorial (cnt));
free (insertions);
free (deletions);
{
int *values, *changed_values;
struct element *elements;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
int i;
values = xnmalloc (cnt, sizeof *values);
for (i = 0; i < cnt; i++)
values[i] = i;
- for (permutation_cnt = 0;
- permutation_cnt == 0 || next_permutation (values, cnt);
- permutation_cnt++)
+ for (n_permutations = 0;
+ n_permutations == 0 || next_permutation (values, cnt);
+ n_permutations++)
{
for (i = 0; i < cnt; i++)
{
}
}
}
- check (permutation_cnt == factorial (cnt));
+ check (n_permutations == factorial (cnt));
free (values);
free (changed_values);
\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-any-remove-any",
+ "insert any order, delete any order",
+ test_insert_any_remove_any
+ },
+ {
+ "insert-any-remove-same",
+ "insert any order, delete same order",
+ test_insert_any_remove_same
+ },
+ {
+ "insert-any-remove-reverse",
+ "insert any order, delete reverse order",
+ test_insert_any_remove_reverse
+ },
+ {
+ "random-sequence",
+ "insert and delete in random sequence",
+ test_random_sequence
+ },
+ {
+ "insert-ordered",
+ "insert in ascending order",
+ test_insert_ordered
+ },
+ {
+ "moved",
+ "move elements around in memory",
+ test_moved
+ },
+ {
+ "changed",
+ "change key data in nodes",
+ test_changed
+ }
+ };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };
int
-main (void)
+main (int argc, char *argv[])
{
- run_test (test_insert_any_remove_any,
- "insert any order, delete any order");
- run_test (test_insert_any_remove_same,
- "insert any order, delete same order");
- run_test (test_insert_any_remove_reverse,
- "insert any order, delete reverse order");
- run_test (test_random_sequence,
- "insert and delete in random sequence");
- run_test (test_insert_ordered,
- "insert in ascending order");
- run_test (test_moved, "move elements around in memory");
- run_test (test_changed, "change key data in nodes");
- 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 augmented binary tree\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;
+ }
}
projects / pspp / blobdiff