/* PSPP - a program for statistical analysis.
- Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
+ Copyright (C) 2007, 2008, 2009, 2010, 2012, 2014 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/hash-functions.h"
#include "libpspp/compiler.h"
+#include "libpspp/i18n.h"
#include "libpspp/str.h"
#include "libpspp/string-set.h"
#include "libpspp/stringi-set.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 ();
}
}
terminates. */
#define check(EXPR) check_func ((EXPR), __LINE__)
-/* Prints a message about memory exhaustion and exits with a
- failure code. */
-static void
-xalloc_die (void)
-{
- printf ("virtual memory exhausted\n");
- exit (EXIT_FAILURE);
-}
-
-static void *xmalloc (size_t n) MALLOC_LIKE;
-static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
-static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
-
-/* Allocates and returns N bytes of memory. */
-static void *
-xmalloc (size_t n)
-{
- if (n != 0)
- {
- void *p = malloc (n);
- if (p == NULL)
- xalloc_die ();
-
- return p;
- }
- else
- return NULL;
-}
-
-static void *
-xmemdup (const void *p, size_t n)
-{
- void *q = xmalloc (n);
- memcpy (q, p, n);
- return q;
-}
-
-/* Clone STRING. */
-static char *
-xstrdup (const char *string)
-{
- return xmemdup (string, strlen (string) + 1);
-}
-
-/* Allocates and returns N * M bytes of memory. */
-static void *
-xnmalloc (size_t n, size_t m)
-{
- if ((size_t) -1 / m <= n)
- xalloc_die ();
- return xmalloc (n * m);
-}
\f
/* Support routines. */
if (*s == NULL)
{
*s = xmalloc (16);
- str_format_26adic (idx + 1, *s, 16);
+ str_format_26adic (idx + 1, true, *s, 16);
}
return *s;
}
*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 elements in VALUES into the lexicographically next greater
+/* Arranges the N elements in VALUES into the lexicographically next greater
permutation. Returns true if successful. If VALUES is already the
lexicographically greatest permutation of its elements (i.e. ordered from
greatest to smallest), arranges them into the lexicographically least
Comparisons among elements of VALUES consider only the bits in KEY_MASK. */
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] & KEY_MASK) < (values[i + 1] & KEY_MASK))
{
size_t j;
- for (j = cnt - 1;
+ for (j = n - 1;
(values[i] & KEY_MASK) >= (values[j] & KEY_MASK);
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;
return value;
}
-/* Randomly shuffles the CNT elements in ARRAY, each of which is
+/* Randomly shuffles the N elements in ARRAY, each of which is
SIZE bytes in size. */
static void
-random_shuffle (void *array_, size_t cnt, size_t size)
+random_shuffle (void *array_, size_t n, size_t size)
{
char *array = array_;
char *tmp = xmalloc (size);
size_t i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
- size_t j = rand () % (cnt - i) + i;
+ size_t j = rand () % (n - i) + i;
if (i != j)
{
memcpy (tmp, array + j * size, size);
check (stringi_map_contains (map, key));
- node = stringi_map_find_node (map, key);
+ node = stringi_map_find_node (map, key, strlen (key));
check (node != NULL);
- check (!strcasecmp (key, stringi_map_node_get_key (node)));
+ check (!utf8_strcasecmp (key, stringi_map_node_get_key (node)));
check (!strcmp (value, stringi_map_node_get_value (node)));
check (node == stringi_map_insert (map, key, "012"));
check (!strcmp (found_value, value));
}
-/* Checks that MAP contains the CNT strings in DATA, that its structure is
+/* Checks that MAP contains the N strings in DATA, that its structure is
correct, and that certain operations on MAP produce the expected results. */
static void
-check_stringi_map (struct stringi_map *map, const int data[], size_t cnt)
+check_stringi_map (struct stringi_map *map, const int data[], size_t n)
{
size_t i;
- check (stringi_map_is_empty (map) == (cnt == 0));
- check (stringi_map_count (map) == cnt);
+ check (stringi_map_is_empty (map) == (n == 0));
+ check (stringi_map_count (map) == n);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
const char *key = make_key (data[i]);
const char *value = make_value (data[i]);
check (!stringi_map_contains (map, "xxx"));
check (stringi_map_find (map, "0") == NULL);
- check (stringi_map_find_node (map, "") == NULL);
+ check (stringi_map_find_node (map, "", 0) == NULL);
check (!stringi_map_delete (map, "xyz"));
- if (cnt == 0)
+ if (n == 0)
check (stringi_map_first (map) == NULL);
else
{
int *data_copy;
int left;
- data_copy = xmemdup (data, cnt * sizeof *data);
- left = cnt;
- for (node = stringi_map_first (map), i = 0; i < cnt;
+ data_copy = xmemdup (data, n * sizeof *data);
+ left = n;
+ for (node = stringi_map_first (map), i = 0; i < n;
node = stringi_map_next (map, node), i++)
{
const char *key = stringi_map_node_get_key (node);
}
}
-/* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a map in the
+/* Inserts the N strings from 0 to N - 1 (inclusive) into a map in the
order specified by INSERTIONS, then deletes them in the order specified by
DELETIONS, checking the map's contents for correctness after each
operation. */
static void
test_insert_delete (const int insertions[],
const int deletions[],
- size_t cnt)
+ size_t n)
{
struct stringi_map map;
size_t i;
stringi_map_init (&map);
check_stringi_map (&map, NULL, 0);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (stringi_map_insert (&map, make_key (insertions[i]),
make_value (insertions[i])));
check_stringi_map (&map, insertions, i + 1);
}
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
check (stringi_map_delete (&map, make_key (deletions[i])));
- check_stringi_map (&map, deletions + i + 1, cnt - i - 1);
+ check_stringi_map (&map, deletions + i + 1, n - i - 1);
}
stringi_map_destroy (&map);
}
{
const int basis = 0;
const int max_elems = 5;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
- unsigned int ins_perm_cnt;
+ unsigned int ins_n_perms;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i | random_value (i, basis);
- 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, n);
+ ins_n_perms++)
{
- unsigned int del_perm_cnt;
+ unsigned int del_n_perms;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i | random_value (i, basis);
- for (del_perm_cnt = 0;
- del_perm_cnt == 0 || next_permutation (deletions, cnt);
- del_perm_cnt++)
- test_insert_delete (insertions, deletions, cnt);
+ for (del_n_perms = 0;
+ del_n_perms == 0 || next_permutation (deletions, n);
+ del_n_perms++)
+ test_insert_delete (insertions, deletions, n);
- check (del_perm_cnt == factorial (cnt));
+ check (del_n_perms == factorial (n));
}
- check (ins_perm_cnt == factorial (cnt));
+ check (ins_n_perms == factorial (n));
free (insertions);
free (deletions);
test_insert_any_remove_same (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *values;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
int i;
- values = xnmalloc (cnt, sizeof *values);
- for (i = 0; i < cnt; i++)
+ values = xnmalloc (n, sizeof *values);
+ for (i = 0; i < n; i++)
values[i] = i | random_value (i, 1);
- for (permutation_cnt = 0;
- permutation_cnt == 0 || next_permutation (values, cnt);
- permutation_cnt++)
- test_insert_delete (values, values, cnt);
- check (permutation_cnt == factorial (cnt));
+ for (n_permutations = 0;
+ n_permutations == 0 || next_permutation (values, n);
+ n_permutations++)
+ test_insert_delete (values, values, n);
+ check (n_permutations == factorial (n));
free (values);
}
test_insert_any_remove_reverse (void)
{
const int max_elems = 7;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt++)
+ for (n = 0; n <= max_elems; n++)
{
int *insertions, *deletions;
- unsigned int permutation_cnt;
+ unsigned int n_permutations;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i | random_value (i, 2);
- for (permutation_cnt = 0;
- permutation_cnt == 0 || next_permutation (insertions, cnt);
- permutation_cnt++)
+ for (n_permutations = 0;
+ n_permutations == 0 || next_permutation (insertions, n);
+ n_permutations++)
{
- memcpy (deletions, insertions, sizeof *insertions * cnt);
- reverse (deletions, cnt);
+ memcpy (deletions, insertions, sizeof *insertions * n);
+ reverse (deletions, n);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
- check (permutation_cnt == factorial (cnt));
+ check (n_permutations == factorial (n));
free (insertions);
free (deletions);
const int basis = 3;
const int max_elems = 64;
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= max_elems; cnt += 2)
+ for (n = 0; n <= max_elems; n += 2)
{
int *insertions, *deletions;
int trial;
int i;
- insertions = xnmalloc (cnt, sizeof *insertions);
- deletions = xnmalloc (cnt, sizeof *deletions);
- for (i = 0; i < cnt; i++)
+ insertions = xnmalloc (n, sizeof *insertions);
+ deletions = xnmalloc (n, sizeof *deletions);
+ for (i = 0; i < n; i++)
insertions[i] = i | random_value (i, basis);
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
deletions[i] = i | random_value (i, basis);
for (trial = 0; trial < max_trials; trial++)
{
- random_shuffle (insertions, cnt, sizeof *insertions);
- random_shuffle (deletions, cnt, sizeof *deletions);
+ random_shuffle (insertions, n, sizeof *insertions);
+ random_shuffle (deletions, n, sizeof *deletions);
- test_insert_delete (insertions, deletions, cnt);
+ test_insert_delete (insertions, deletions, n);
}
free (insertions);
const int basis = 15;
enum { MAX_ELEMS = 16 };
const int max_trials = 8;
- int cnt;
+ int n;
- for (cnt = 0; cnt <= MAX_ELEMS; cnt++)
+ for (n = 0; n <= MAX_ELEMS; n++)
{
int insertions[MAX_ELEMS];
int trial;
int i;
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
insertions[i] = (i / 2) | random_value (i, basis);
for (trial = 0; trial < max_trials; trial++)
/* Insert with replacement in random order. */
n_data = 0;
stringi_map_init (&map);
- random_shuffle (insertions, cnt, sizeof *insertions);
- for (i = 0; i < cnt; i++)
+ random_shuffle (insertions, n, sizeof *insertions);
+ for (i = 0; i < n; i++)
{
const char *key = make_key (insertions[i]);
const char *value = make_value (insertions[i]);
}
/* Delete in original order. */
- for (i = 0; i < cnt; i++)
+ for (i = 0; i < n; i++)
{
const char *expected_value;
char *value;
for (i = 0; i < n; i++)
{
+ const char *key = make_key (data[i]);
const char *value = make_value (data[i]);
struct stringi_map_node *node;
char *old_value;
- node = stringi_map_find_node (map, make_key (data[i]));
+ node = stringi_map_find_node (map, key, strlen (key));
check (node != NULL);
check (!strcmp (stringi_map_node_get_value (node), value));
data[i] = (data[i] & KEY_MASK) | random_value (i, 15);
\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
+ },
+ {
+ "replace",
+ "insert and replace in random sequence",
+ test_replace
+ },
+ {
+ "insert-ordered",
+ "insert in ascending order",
+ test_insert_ordered
+ },
+ {
+ "clear",
+ "clear",
+ test_clear
+ },
+ {
+ "clone",
+ "clone",
+ test_clone
+ },
+ {
+ "swap",
+ "swap",
+ test_swap
+ },
+ {
+ "node-swap-value",
+ "node_swap_value",
+ test_node_swap_value
+ },
+ {
+ "insert-map",
+ "insert_map",
+ test_insert_map
+ },
+ {
+ "replace-map",
+ "replace_map",
+ test_replace_map
+ },
+ {
+ "get-keys-and-values",
+ "get keys and values",
+ test_get_keys_and_values
+ },
+ {
+ "destroy-null",
+ "destroying null table",
+ test_destroy_null
+ },
+ };
+
+enum { N_TESTS = sizeof tests / sizeof *tests };
int
-main (void)
-{
- 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_replace, "insert and replace in random sequence");
- run_test (test_insert_ordered, "insert in ascending order");
- run_test (test_clear, "clear");
- run_test (test_clone, "clone");
- run_test (test_swap, "swap");
- run_test (test_node_swap_value, "node_swap_value");
- run_test (test_insert_map, "insert_map");
- run_test (test_replace_map, "replace_map");
- run_test (test_get_keys_and_values, "get keys and values");
- run_test (test_destroy_null, "destroying null table");
-
- putchar ('\n');
-
- free_strings ();
-
- return 0;
+main (int argc, char *argv[])
+{
+ 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 case-insensitive string 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 ();
+ free_strings ();
+ return 0;
+ }
+
+ fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
+ return EXIT_FAILURE;
+ }
}
projects / pspp / blobdiff