1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2008, 2009, 2010, 2012, 2014 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
17 /* This is a test program for the stringi_set_* routines defined in
18 stringi-set.c. This test program aims to be as comprehensive as possible.
19 "gcov -a -b" should report almost complete coverage of lines, blocks and
20 branches in stringi-set.c, except that one branch caused by hash collision
21 is not exercised because our hash function has so few collisions. "valgrind
22 --leak-check=yes --show-reachable=yes" should give a clean report. */
26 #include "libpspp/stringi-set.h"
38 #include "libpspp/compiler.h"
39 #include "libpspp/i18n.h"
40 #include "libpspp/str.h"
42 /* Exit with a failure code.
43 (Place a breakpoint on this function while debugging.) */
50 /* If OK is not true, prints a message about failure on the
51 current source file and the given LINE and terminates. */
53 check_func (bool ok, int line)
57 fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
62 /* Verifies that EXPR evaluates to true.
63 If not, prints a message citing the calling line number and
65 #define check(EXPR) check_func ((EXPR), __LINE__)
67 /* Support routines. */
69 enum { MAX_VALUE = 1024 };
71 static char *string_table[MAX_VALUE];
74 make_string (int value)
78 assert (value >= 0 && value < MAX_VALUE);
79 s = &string_table[value];
83 str_format_26adic (value + 1, true, *s, 16);
93 for (i = 0; i < MAX_VALUE; i++)
94 free (string_table[i]);
97 /* Swaps *A and *B. */
106 /* Reverses the order of the N integers starting at VALUES. */
108 reverse (int *values, size_t n)
114 swap (&values[i++], &values[--j]);
117 /* Arranges the N elements in VALUES into the lexicographically
118 next greater permutation. Returns true if successful.
119 If VALUES is already the lexicographically greatest
120 permutation of its elements (i.e. ordered from greatest to
121 smallest), arranges them into the lexicographically least
122 permutation (i.e. ordered from smallest to largest) and
125 next_permutation (int *values, size_t n)
133 if (values[i] < values[i + 1])
136 for (j = n - 1; values[i] >= values[j]; j--)
138 swap (values + i, values + j);
139 reverse (values + (i + 1), n - (i + 1));
152 factorial (unsigned int n)
154 unsigned int value = 1;
160 /* Randomly shuffles the N elements in ARRAY, each of which is
161 SIZE bytes in size. */
163 random_shuffle (void *array_, size_t n, size_t size)
165 char *array = array_;
166 char *tmp = xmalloc (size);
169 for (i = 0; i < n; i++)
171 size_t j = rand () % (n - i) + i;
174 memcpy (tmp, array + j * size, size);
175 memcpy (array + j * size, array + i * size, size);
176 memcpy (array + i * size, tmp, size);
183 /* Checks that SET contains STRING. */
185 check_set_contains (struct stringi_set *set, const char *string)
187 struct stringi_set_node *node;
189 check (stringi_set_contains (set, string));
190 check (!stringi_set_insert (set, string));
191 check (!stringi_set_insert_nocopy (set, xstrdup (string)));
193 node = stringi_set_find_node (set, string);
194 check (node != NULL);
195 check (!utf8_strcasecmp (string, stringi_set_node_get_string (node)));
198 /* Checks that SET contains the N strings in DATA, that its structure is
199 correct, and that certain operations on SET produce the expected results. */
201 check_stringi_set (struct stringi_set *set, const int data[], size_t n)
205 check (stringi_set_is_empty (set) == (n == 0));
206 check (stringi_set_count (set) == n);
208 for (i = 0; i < n; i++)
214 s = make_string (data[i]);
215 check_set_contains (set, s);
218 for (p = copy; *p != '\0'; p++)
220 assert (isupper (*p));
222 check_set_contains (set, copy);
226 check (!stringi_set_contains (set, "xxx"));
227 check (stringi_set_find_node (set, "") == NULL);
231 check (stringi_set_first (set) == NULL);
232 free (stringi_set_get_array (set));
236 const struct stringi_set_node *node;
241 array = stringi_set_get_array (set);
242 data_copy = xmemdup (data, n * sizeof *data);
244 for (node = stringi_set_first (set), i = 0; i < n;
245 node = stringi_set_next (set, node), i++)
247 const char *s = stringi_set_node_get_string (node);
250 check (s == array[i]);
252 for (j = 0; j < left; j++)
253 if (!utf8_strcasecmp (s, make_string (data_copy[j])))
255 data_copy[j] = data_copy[--left];
262 check (node == NULL);
266 array = stringi_set_get_sorted_array (set);
267 for (i = 0; i < n; i++)
270 check (utf8_strcasecmp (array[i - 1], array[i]) < 0);
271 check (stringi_set_contains (set, array[i]));
277 /* Inserts the N strings from 0 to N - 1 (inclusive) into a set in the
278 order specified by INSERTIONS, then deletes them in the order specified by
279 DELETIONS, checking the set's contents for correctness after each
282 test_insert_delete (const int insertions[],
283 const int deletions[],
286 struct stringi_set set;
289 stringi_set_init (&set);
290 check_stringi_set (&set, NULL, 0);
291 for (i = 0; i < n; i++)
293 check (stringi_set_insert (&set, make_string (insertions[i])));
294 check_stringi_set (&set, insertions, i + 1);
296 for (i = 0; i < n; i++)
298 check (stringi_set_delete (&set, make_string (deletions[i])));
299 check_stringi_set (&set, deletions + i + 1, n - i - 1);
301 stringi_set_destroy (&set);
304 /* Inserts strings into a set in each possible order, then removes them in each
305 possible order, up to a specified maximum size. */
307 test_insert_any_remove_any (void)
309 const int max_elems = 5;
312 for (n = 0; n <= max_elems; n++)
314 int *insertions, *deletions;
315 unsigned int ins_n_perms;
318 insertions = xnmalloc (n, sizeof *insertions);
319 deletions = xnmalloc (n, sizeof *deletions);
320 for (i = 0; i < n; i++)
323 for (ins_n_perms = 0;
324 ins_n_perms == 0 || next_permutation (insertions, n);
327 unsigned int del_n_perms;
330 for (i = 0; i < n; i++)
333 for (del_n_perms = 0;
334 del_n_perms == 0 || next_permutation (deletions, n);
336 test_insert_delete (insertions, deletions, n);
338 check (del_n_perms == factorial (n));
340 check (ins_n_perms == factorial (n));
347 /* Inserts strings into a set in each possible order, then removes them in the
348 same order, up to a specified maximum size. */
350 test_insert_any_remove_same (void)
352 const int max_elems = 7;
355 for (n = 0; n <= max_elems; n++)
358 unsigned int n_permutations;
361 values = xnmalloc (n, sizeof *values);
362 for (i = 0; i < n; i++)
365 for (n_permutations = 0;
366 n_permutations == 0 || next_permutation (values, n);
368 test_insert_delete (values, values, n);
369 check (n_permutations == factorial (n));
375 /* Inserts strings into a set in each possible order, then
376 removes them in reverse order, up to a specified maximum
379 test_insert_any_remove_reverse (void)
381 const int max_elems = 7;
384 for (n = 0; n <= max_elems; n++)
386 int *insertions, *deletions;
387 unsigned int n_permutations;
390 insertions = xnmalloc (n, sizeof *insertions);
391 deletions = xnmalloc (n, sizeof *deletions);
392 for (i = 0; i < n; i++)
395 for (n_permutations = 0;
396 n_permutations == 0 || next_permutation (insertions, n);
399 memcpy (deletions, insertions, sizeof *insertions * n);
400 reverse (deletions, n);
402 test_insert_delete (insertions, deletions, n);
404 check (n_permutations == factorial (n));
411 /* Inserts and removes strings in a set, in random order. */
413 test_random_sequence (void)
415 const int max_elems = 64;
416 const int max_trials = 8;
419 for (n = 0; n <= max_elems; n += 2)
421 int *insertions, *deletions;
425 insertions = xnmalloc (n, sizeof *insertions);
426 deletions = xnmalloc (n, sizeof *deletions);
427 for (i = 0; i < n; i++)
429 for (i = 0; i < n; i++)
432 for (trial = 0; trial < max_trials; trial++)
434 random_shuffle (insertions, n, sizeof *insertions);
435 random_shuffle (deletions, n, sizeof *deletions);
437 test_insert_delete (insertions, deletions, n);
445 /* Inserts strings into a set in ascending order, then delete in ascending
448 test_insert_ordered (void)
450 const int max_elems = 64;
452 struct stringi_set set;
455 stringi_set_init (&set);
456 values = xnmalloc (max_elems, sizeof *values);
457 for (i = 0; i < max_elems; i++)
460 stringi_set_insert_nocopy (&set, xstrdup (make_string (i)));
461 check_stringi_set (&set, values, i + 1);
463 for (i = 0; i < max_elems; i++)
465 stringi_set_delete (&set, make_string (i));
466 check_stringi_set (&set, values + i + 1, max_elems - i - 1);
468 stringi_set_destroy (&set);
473 test_boolean_ops (void (*function)(struct stringi_set *a, struct stringi_set *b,
474 unsigned int *a_pat, unsigned int *b_pat))
476 enum { MAX_STRINGS = 7 };
477 unsigned int a_pat, b_pat;
479 for (a_pat = 0; a_pat < (1u << MAX_STRINGS); a_pat++)
480 for (b_pat = 0; b_pat < (1u << MAX_STRINGS); b_pat++)
482 unsigned int new_a_pat = a_pat;
483 unsigned int new_b_pat = b_pat;
484 struct stringi_set a, b;
485 int a_strings[MAX_STRINGS], b_strings[MAX_STRINGS];
488 stringi_set_init (&a);
489 stringi_set_init (&b);
490 for (i = 0; i < MAX_STRINGS; i++)
492 if (a_pat & (1u << i))
493 stringi_set_insert (&a, make_string (i));
494 if (b_pat & (1u << i))
495 stringi_set_insert (&b, make_string (i));
498 function (&a, &b, &new_a_pat, &new_b_pat);
501 for (i = 0; i < MAX_STRINGS; i++)
503 if (new_a_pat & (1u << i))
504 a_strings[n_a++] = i;
505 if (new_b_pat & (1u << i))
506 b_strings[n_b++] = i;
508 check_stringi_set (&a, a_strings, n_a);
509 check_stringi_set (&b, b_strings, n_b);
510 stringi_set_destroy (&a);
511 stringi_set_destroy (&b);
516 union_cb (struct stringi_set *a, struct stringi_set *b,
517 unsigned int *a_pat, unsigned int *b_pat)
519 stringi_set_union (a, b);
526 test_boolean_ops (union_cb);
530 union_and_intersection_cb (struct stringi_set *a, struct stringi_set *b,
531 unsigned int *a_pat, unsigned int *b_pat)
533 unsigned int orig_a_pat = *a_pat;
534 unsigned int orig_b_pat = *b_pat;
536 stringi_set_union_and_intersection (a, b);
537 *a_pat = orig_a_pat | orig_b_pat;
538 *b_pat = orig_a_pat & orig_b_pat;
542 test_union_and_intersection (void)
544 test_boolean_ops (union_and_intersection_cb);
548 intersect_cb (struct stringi_set *a, struct stringi_set *b,
549 unsigned int *a_pat, unsigned int *b_pat)
551 stringi_set_intersect (a, b);
556 test_intersect (void)
558 test_boolean_ops (intersect_cb);
562 subtract_cb (struct stringi_set *a, struct stringi_set *b,
563 unsigned int *a_pat, unsigned int *b_pat)
565 stringi_set_subtract (a, b);
572 test_boolean_ops (subtract_cb);
576 swap_cb (struct stringi_set *a, struct stringi_set *b,
577 unsigned int *a_pat, unsigned int *b_pat)
580 stringi_set_swap (a, b);
589 test_boolean_ops (swap_cb);
593 clear_cb (struct stringi_set *a, struct stringi_set *b UNUSED,
594 unsigned int *a_pat, unsigned int *b_pat UNUSED)
596 stringi_set_clear (a);
603 test_boolean_ops (clear_cb);
607 clone_cb (struct stringi_set *a, struct stringi_set *b,
608 unsigned int *a_pat, unsigned int *b_pat)
610 stringi_set_destroy (a);
611 stringi_set_clone (a, b);
618 test_boolean_ops (clone_cb);
622 test_destroy_null (void)
624 stringi_set_destroy (NULL);
632 const char *description;
633 void (*function) (void);
636 static const struct test tests[] =
639 "insert-any-remove-any",
640 "insert any order, delete any order",
641 test_insert_any_remove_any
644 "insert-any-remove-same",
645 "insert any order, delete same order",
646 test_insert_any_remove_same
649 "insert-any-remove-reverse",
650 "insert any order, delete reverse order",
651 test_insert_any_remove_reverse
655 "insert and delete in random sequence",
660 "insert in ascending order",
669 "union-and-intersection",
670 "union and intersection",
671 test_union_and_intersection
700 "destroying null table",
705 enum { N_TESTS = sizeof tests / sizeof *tests };
708 main (int argc, char *argv[])
714 fprintf (stderr, "exactly one argument required; use --help for help\n");
717 else if (!strcmp (argv[1], "--help"))
719 printf ("%s: test case-insensitive string set library\n"
720 "usage: %s TEST-NAME\n"
721 "where TEST-NAME is one of the following:\n",
723 for (i = 0; i < N_TESTS; i++)
724 printf (" %s\n %s\n", tests[i].name, tests[i].description);
729 for (i = 0; i < N_TESTS; i++)
730 if (!strcmp (argv[1], tests[i].name))
732 tests[i].function ();
737 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);