/* PSPP - a program for statistical analysis.
- Copyright (C) 2007, 2008 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2008, 2009, 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
#include <libpspp/hmapx.h>
-#include <assert.h>
#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include <libpspp/compiler.h>
\f
-/* Currently running test. */
-static const char *test_name;
-
/* If OK is not true, prints a message about failure on the
current source file and the given LINE and terminates. */
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);
abort ();
}
}
typedef size_t hash_function (int data);
static size_t
-identity_hash (int data)
+identity_hash (int data)
{
return data;
}
static size_t
-constant_hash (int data UNUSED)
+constant_hash (int data UNUSED)
{
return 0x12345678u;
}
size_t i, j;
int *order;
+ check (hmapx_is_empty (hmapx) == (cnt == 0));
check (hmapx_count (hmapx) == cnt);
check (cnt <= hmapx_capacity (hmapx));
count = 0;
HMAPX_FOR_EACH_WITH_HASH (e, node, hash (order[i]), hmapx)
- if (e->data == order[i])
- count++;
+ if (e->data == order[i])
+ count++;
check (count == j - i);
}
check (hmapx_node_hash (p) == hash (e->data));
for (j = 0; j < left; j++)
- if (order[j] == e->data)
+ if (order[j] == e->data)
{
order[j] = order[--left];
goto next;
check_hmapx (&hmapx, insertions, i + 1, hash);
/* A series of insertions should not produce a shrinkable hmapx. */
- if (i >= reserve)
+ if (i >= reserve)
{
capacity = hmapx_capacity (&hmapx);
hmapx_shrink (&hmapx);
- check (capacity == hmapx_capacity (&hmapx));
+ check (capacity == hmapx_capacity (&hmapx));
}
}
for (i = 0; i < cnt; i++)
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, hash, 1);
- 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);
}
static void
-test_insert_any_remove_any_random_hash (void)
+test_insert_any_remove_any_random_hash (void)
{
test_insert_any_remove_any (random_hash);
}
static void
-test_insert_any_remove_any_identity_hash (void)
+test_insert_any_remove_any_identity_hash (void)
{
test_insert_any_remove_any (identity_hash);
}
static void
-test_insert_any_remove_any_constant_hash (void)
+test_insert_any_remove_any_constant_hash (void)
{
test_insert_any_remove_any (constant_hash);
}
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, hash, cnt / 2);
- check (permutation_cnt == factorial (cnt));
+ check (n_permutations == factorial (cnt));
free (values);
}
}
static void
-test_insert_any_remove_same_random_hash (void)
+test_insert_any_remove_same_random_hash (void)
{
test_insert_any_remove_same (random_hash);
}
static void
-test_insert_any_remove_same_identity_hash (void)
+test_insert_any_remove_same_identity_hash (void)
{
test_insert_any_remove_same (identity_hash);
}
static void
-test_insert_any_remove_same_constant_hash (void)
+test_insert_any_remove_same_constant_hash (void)
{
test_insert_any_remove_same (constant_hash);
}
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, hash, cnt);
}
- check (permutation_cnt == factorial (cnt));
+ check (n_permutations == factorial (cnt));
free (insertions);
free (deletions);
}
static void
-test_random_sequence_random_hash (void)
+test_random_sequence_random_hash (void)
{
test_random_sequence (64, random_hash);
}
static void
-test_random_sequence_identity_hash (void)
+test_random_sequence_identity_hash (void)
{
test_random_sequence (64, identity_hash);
}
static void
-test_random_sequence_constant_hash (void)
+test_random_sequence_constant_hash (void)
{
test_random_sequence (32, constant_hash);
}
nodes[i] = hmapx_insert (&hmapx, &elements[i], hash (elements[i].data));
check_hmapx (&hmapx, values, i + 1, hash);
- if (hash == identity_hash)
+ if (hash == identity_hash)
{
/* Check that every every hash bucket has (almost) the
same number of nodes in it. */
int max = INT_MIN;
int j;
- for (j = 0; j <= hmapx.hmap.mask; j++)
+ for (j = 0; j <= hmapx.hmap.mask; j++)
{
int count = 0;
struct hmap_node *node;
}
static void
-test_moved_random_hash (void)
+test_moved_random_hash (void)
{
test_moved (128, random_hash);
}
static void
-test_moved_identity_hash (void)
+test_moved_identity_hash (void)
{
test_moved (128, identity_hash);
}
static void
-test_moved_constant_hash (void)
+test_moved_constant_hash (void)
{
test_moved (32, constant_hash);
}
int *values, *changed_values;
struct hmapx_node **nodes;
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++)
{
/* Change value i to j. */
elements[i].data = j;
- hmapx_changed (&hmapx, nodes[i],
+ hmapx_changed (&hmapx, nodes[i],
hash (elements[i].data));
for (k = 0; k < cnt; k++)
changed_values[k] = k;
}
}
}
- check (permutation_cnt == factorial (cnt));
+ check (n_permutations == factorial (cnt));
free (values);
free (changed_values);
struct hmapx_node **nodes;
struct element *elements;
struct element replacement;
- 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);
}
static void
-test_swap (int max_elems, hash_function *hash)
+test_swap (int max_elems, hash_function *hash)
{
struct element *elements;
int *values;
}
static void
-test_swap_random_hash (void)
+test_swap_random_hash (void)
{
test_swap (128, random_hash);
}
+/* Inserts elements into an HMAPX in ascending order, then clears the hash
+ table using hmapx_clear(). */
+static void
+test_clear (void)
+{
+ const int max_elems = 128;
+ struct element *elements;
+ struct hmapx_node **nodes;
+ int *values;
+ struct hmapx hmapx;
+ int cnt;
+
+ elements = xnmalloc (max_elems, sizeof *elements);
+ nodes = xnmalloc (max_elems, sizeof *nodes);
+ values = xnmalloc (max_elems, sizeof *values);
+
+ hmapx_init (&hmapx);
+ for (cnt = 0; cnt <= max_elems; cnt++)
+ {
+ int i;
+
+ for (i = 0; i < cnt; i++)
+ {
+ values[i] = elements[i].data = i;
+ nodes[i] = hmapx_insert (&hmapx, &elements[i],
+ random_hash (elements[i].data));
+ check_hmapx (&hmapx, values, i + 1, random_hash);
+ }
+ hmapx_clear (&hmapx);
+ check_hmapx (&hmapx, NULL, 0, random_hash);
+ }
+ hmapx_destroy (&hmapx);
+
+ free (elements);
+ free (nodes);
+ free (values);
+}
+
static void
-test_destroy_null (void)
+test_destroy_null (void)
{
hmapx_destroy (NULL);
}
\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-random-hash",
+ "insert any order, delete any order (random hash)",
+ test_insert_any_remove_any_random_hash
+ },
+ {
+ "insert-any-remove-any-identity-hash",
+ "insert any order, delete any order (identity hash)",
+ test_insert_any_remove_any_identity_hash
+ },
+ {
+ "insert-any-remove-any-constant-hash",
+ "insert any order, delete any order (constant hash)",
+ test_insert_any_remove_any_constant_hash
+ },
+ {
+ "insert-any-remove-same-random-hash",
+ "insert any order, delete same order (random hash)",
+ test_insert_any_remove_same_random_hash
+ },
+ {
+ "insert-any-remove-same-identity-hash",
+ "insert any order, delete same order (identity hash)",
+ test_insert_any_remove_same_identity_hash
+ },
+ {
+ "insert-any-remove-same-constant-hash",
+ "insert any order, delete same order (constant hash)",
+ test_insert_any_remove_same_constant_hash
+ },
+ {
+ "insert-any-remove-reverse-random-hash",
+ "insert any order, delete reverse order (random hash)",
+ test_insert_any_remove_reverse_random_hash
+ },
+ {
+ "insert-any-remove-reverse-identity-hash",
+ "insert any order, delete reverse order (identity hash)",
+ test_insert_any_remove_reverse_identity_hash
+ },
+ {
+ "insert-any-remove-reverse-constant-hash",
+ "insert any order, delete reverse order (constant hash)",
+ test_insert_any_remove_reverse_constant_hash
+ },
+ {
+ "random-sequence-random-hash",
+ "insert and delete in random sequence (random hash)",
+ test_random_sequence_random_hash
+ },
+ {
+ "random-sequence-identity-hash",
+ "insert and delete in random sequence (identity hash)",
+ test_random_sequence_identity_hash
+ },
+ {
+ "random-sequence-constant-hash",
+ "insert and delete in random sequence (constant hash)",
+ test_random_sequence_constant_hash
+ },
+ {
+ "insert-ordered-random-hash",
+ "insert in ascending order (random hash)",
+ test_insert_ordered_random_hash
+ },
+ {
+ "insert-ordered-identity-hash",
+ "insert in ascending order (identity hash)",
+ test_insert_ordered_identity_hash
+ },
+ {
+ "insert-ordered-constant-hash",
+ "insert in ascending order (constant hash)",
+ test_insert_ordered_constant_hash
+ },
+ {
+ "moved-random-hash",
+ "move elements around in memory (random hash)",
+ test_moved_random_hash
+ },
+ {
+ "moved-identity-hash",
+ "move elements around in memory (identity hash)",
+ test_moved_identity_hash
+ },
+ {
+ "moved-constant-hash",
+ "move elements around in memory (constant hash)",
+ test_moved_constant_hash
+ },
+ {
+ "changed-random-hash",
+ "change key data in nodes (random hash)",
+ test_changed_random_hash
+ },
+ {
+ "changed-identity-hash",
+ "change key data in nodes (identity hash)",
+ test_changed_identity_hash
+ },
+ {
+ "changed-constant-hash",
+ "change key data in nodes (constant hash)",
+ test_changed_constant_hash
+ },
+ {
+ "change-random-hash",
+ "change and move key data in nodes (random hash)",
+ test_change_random_hash
+ },
+ {
+ "change-identity-hash",
+ "change and move key data in nodes (identity hash)",
+ test_change_identity_hash
+ },
+ {
+ "change-constant-hash",
+ "change and move key data in nodes (constant hash)",
+ test_change_constant_hash
+ },
+ {
+ "swap-random-hash",
+ "test swapping tables",
+ test_swap_random_hash
+ },
+ {
+ "clear",
+ "test clearing hash table",
+ test_clear
+ },
+ {
+ "destroy-null",
+ "test destroying null table",
+ test_destroy_null
+ },
+ {
+ "shrink-empty",
+ "test shrinking an empty table",
+ test_shrink_empty
+ },
+ };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };
int
-main (void)
+main (int argc, char *argv[])
{
- run_test (test_insert_any_remove_any_random_hash,
- "insert any order, delete any order (random hash)");
- run_test (test_insert_any_remove_any_identity_hash,
- "insert any order, delete any order (identity hash)");
- run_test (test_insert_any_remove_any_constant_hash,
- "insert any order, delete any order (constant hash)");
-
- run_test (test_insert_any_remove_same_random_hash,
- "insert any order, delete same order (random hash)");
- run_test (test_insert_any_remove_same_identity_hash,
- "insert any order, delete same order (identity hash)");
- run_test (test_insert_any_remove_same_constant_hash,
- "insert any order, delete same order (constant hash)");
-
- run_test (test_insert_any_remove_reverse_random_hash,
- "insert any order, delete reverse order (random hash)");
- run_test (test_insert_any_remove_reverse_identity_hash,
- "insert any order, delete reverse order (identity hash)");
- run_test (test_insert_any_remove_reverse_constant_hash,
- "insert any order, delete reverse order (constant hash)");
-
- run_test (test_random_sequence_random_hash,
- "insert and delete in random sequence (random hash)");
- run_test (test_random_sequence_identity_hash,
- "insert and delete in random sequence (identity hash)");
- run_test (test_random_sequence_constant_hash,
- "insert and delete in random sequence (constant hash)");
-
- run_test (test_insert_ordered_random_hash,
- "insert in ascending order (random hash)");
- run_test (test_insert_ordered_identity_hash,
- "insert in ascending order (identity hash)");
- run_test (test_insert_ordered_constant_hash,
- "insert in ascending order (constant hash)");
-
- run_test (test_moved_random_hash,
- "move elements around in memory (random hash)");
- run_test (test_moved_identity_hash,
- "move elements around in memory (identity hash)");
- run_test (test_moved_constant_hash,
- "move elements around in memory (constant hash)");
-
- run_test (test_changed_random_hash,
- "change key data in nodes (random hash)");
- run_test (test_changed_identity_hash,
- "change key data in nodes (identity hash)");
- run_test (test_changed_constant_hash,
- "change key data in nodes (constant hash)");
-
- run_test (test_change_random_hash,
- "change and move key data in nodes (random hash)");
- run_test (test_change_identity_hash,
- "change and move key data in nodes (identity hash)");
- run_test (test_change_constant_hash,
- "change and move key data in nodes (constant hash)");
-
- run_test (test_swap_random_hash, "test swapping tables");
-
- run_test (test_destroy_null, "test destroying null table");
- run_test (test_shrink_empty, "test shrinking an empty table");
-
- 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 hash map of pointers\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