1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2008, 2009, 2010, 2012 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 /* Prints a message about memory exhaustion and exits with a
72 printf ("virtual memory exhausted\n");
76 static void *xmalloc (size_t n) MALLOC_LIKE;
77 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
78 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
80 /* Allocates and returns N bytes of memory. */
97 xmemdup (const void *p, size_t n)
99 void *q = xmalloc (n);
106 xstrdup (const char *string)
108 return xmemdup (string, strlen (string) + 1);
111 /* Allocates and returns N * M bytes of memory. */
113 xnmalloc (size_t n, size_t m)
115 if ((size_t) -1 / m <= n)
117 return xmalloc (n * m);
120 /* Support routines. */
122 enum { MAX_VALUE = 1024 };
124 static char *string_table[MAX_VALUE];
127 make_string (int value)
131 assert (value >= 0 && value < MAX_VALUE);
132 s = &string_table[value];
136 str_format_26adic (value + 1, *s, 16);
146 for (i = 0; i < MAX_VALUE; i++)
147 free (string_table[i]);
150 /* Swaps *A and *B. */
152 swap (int *a, int *b)
159 /* Reverses the order of the CNT integers starting at VALUES. */
161 reverse (int *values, size_t cnt)
167 swap (&values[i++], &values[--j]);
170 /* Arranges the CNT elements in VALUES into the lexicographically
171 next greater permutation. Returns true if successful.
172 If VALUES is already the lexicographically greatest
173 permutation of its elements (i.e. ordered from greatest to
174 smallest), arranges them into the lexicographically least
175 permutation (i.e. ordered from smallest to largest) and
178 next_permutation (int *values, size_t cnt)
186 if (values[i] < values[i + 1])
189 for (j = cnt - 1; values[i] >= values[j]; j--)
191 swap (values + i, values + j);
192 reverse (values + (i + 1), cnt - (i + 1));
197 reverse (values, cnt);
205 factorial (unsigned int n)
207 unsigned int value = 1;
213 /* Randomly shuffles the CNT elements in ARRAY, each of which is
214 SIZE bytes in size. */
216 random_shuffle (void *array_, size_t cnt, size_t size)
218 char *array = array_;
219 char *tmp = xmalloc (size);
222 for (i = 0; i < cnt; i++)
224 size_t j = rand () % (cnt - i) + i;
227 memcpy (tmp, array + j * size, size);
228 memcpy (array + j * size, array + i * size, size);
229 memcpy (array + i * size, tmp, size);
236 /* Checks that SET contains STRING. */
238 check_set_contains (struct stringi_set *set, const char *string)
240 struct stringi_set_node *node;
242 check (stringi_set_contains (set, string));
243 check (!stringi_set_insert (set, string));
244 check (!stringi_set_insert_nocopy (set, xstrdup (string)));
246 node = stringi_set_find_node (set, string);
247 check (node != NULL);
248 check (!utf8_strcasecmp (string, stringi_set_node_get_string (node)));
251 /* Checks that SET contains the CNT strings in DATA, that its structure is
252 correct, and that certain operations on SET produce the expected results. */
254 check_stringi_set (struct stringi_set *set, const int data[], size_t cnt)
258 check (stringi_set_is_empty (set) == (cnt == 0));
259 check (stringi_set_count (set) == cnt);
261 for (i = 0; i < cnt; i++)
267 s = make_string (data[i]);
268 check_set_contains (set, s);
271 for (p = copy; *p != '\0'; p++)
273 assert (isupper (*p));
275 check_set_contains (set, copy);
279 check (!stringi_set_contains (set, "xxx"));
280 check (stringi_set_find_node (set, "") == NULL);
284 check (stringi_set_first (set) == NULL);
285 free (stringi_set_get_array (set));
289 const struct stringi_set_node *node;
294 array = stringi_set_get_array (set);
295 data_copy = xmemdup (data, cnt * sizeof *data);
297 for (node = stringi_set_first (set), i = 0; i < cnt;
298 node = stringi_set_next (set, node), i++)
300 const char *s = stringi_set_node_get_string (node);
303 check (s == array[i]);
305 for (j = 0; j < left; j++)
306 if (!utf8_strcasecmp (s, make_string (data_copy[j])))
308 data_copy[j] = data_copy[--left];
315 check (node == NULL);
319 array = stringi_set_get_sorted_array (set);
320 for (i = 0; i < cnt; i++)
323 check (utf8_strcasecmp (array[i - 1], array[i]) < 0);
324 check (stringi_set_contains (set, array[i]));
330 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a set in the
331 order specified by INSERTIONS, then deletes them in the order specified by
332 DELETIONS, checking the set's contents for correctness after each
335 test_insert_delete (const int insertions[],
336 const int deletions[],
339 struct stringi_set set;
342 stringi_set_init (&set);
343 check_stringi_set (&set, NULL, 0);
344 for (i = 0; i < cnt; i++)
346 check (stringi_set_insert (&set, make_string (insertions[i])));
347 check_stringi_set (&set, insertions, i + 1);
349 for (i = 0; i < cnt; i++)
351 check (stringi_set_delete (&set, make_string (deletions[i])));
352 check_stringi_set (&set, deletions + i + 1, cnt - i - 1);
354 stringi_set_destroy (&set);
357 /* Inserts strings into a set in each possible order, then removes them in each
358 possible order, up to a specified maximum size. */
360 test_insert_any_remove_any (void)
362 const int max_elems = 5;
365 for (cnt = 0; cnt <= max_elems; cnt++)
367 int *insertions, *deletions;
368 unsigned int ins_perm_cnt;
371 insertions = xnmalloc (cnt, sizeof *insertions);
372 deletions = xnmalloc (cnt, sizeof *deletions);
373 for (i = 0; i < cnt; i++)
376 for (ins_perm_cnt = 0;
377 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
380 unsigned int del_perm_cnt;
383 for (i = 0; i < cnt; i++)
386 for (del_perm_cnt = 0;
387 del_perm_cnt == 0 || next_permutation (deletions, cnt);
389 test_insert_delete (insertions, deletions, cnt);
391 check (del_perm_cnt == factorial (cnt));
393 check (ins_perm_cnt == factorial (cnt));
400 /* Inserts strings into a set in each possible order, then removes them in the
401 same order, up to a specified maximum size. */
403 test_insert_any_remove_same (void)
405 const int max_elems = 7;
408 for (cnt = 0; cnt <= max_elems; cnt++)
411 unsigned int permutation_cnt;
414 values = xnmalloc (cnt, sizeof *values);
415 for (i = 0; i < cnt; i++)
418 for (permutation_cnt = 0;
419 permutation_cnt == 0 || next_permutation (values, cnt);
421 test_insert_delete (values, values, cnt);
422 check (permutation_cnt == factorial (cnt));
428 /* Inserts strings into a set in each possible order, then
429 removes them in reverse order, up to a specified maximum
432 test_insert_any_remove_reverse (void)
434 const int max_elems = 7;
437 for (cnt = 0; cnt <= max_elems; cnt++)
439 int *insertions, *deletions;
440 unsigned int permutation_cnt;
443 insertions = xnmalloc (cnt, sizeof *insertions);
444 deletions = xnmalloc (cnt, sizeof *deletions);
445 for (i = 0; i < cnt; i++)
448 for (permutation_cnt = 0;
449 permutation_cnt == 0 || next_permutation (insertions, cnt);
452 memcpy (deletions, insertions, sizeof *insertions * cnt);
453 reverse (deletions, cnt);
455 test_insert_delete (insertions, deletions, cnt);
457 check (permutation_cnt == factorial (cnt));
464 /* Inserts and removes strings in a set, in random order. */
466 test_random_sequence (void)
468 const int max_elems = 64;
469 const int max_trials = 8;
472 for (cnt = 0; cnt <= max_elems; cnt += 2)
474 int *insertions, *deletions;
478 insertions = xnmalloc (cnt, sizeof *insertions);
479 deletions = xnmalloc (cnt, sizeof *deletions);
480 for (i = 0; i < cnt; i++)
482 for (i = 0; i < cnt; i++)
485 for (trial = 0; trial < max_trials; trial++)
487 random_shuffle (insertions, cnt, sizeof *insertions);
488 random_shuffle (deletions, cnt, sizeof *deletions);
490 test_insert_delete (insertions, deletions, cnt);
498 /* Inserts strings into a set in ascending order, then delete in ascending
501 test_insert_ordered (void)
503 const int max_elems = 64;
505 struct stringi_set set;
508 stringi_set_init (&set);
509 values = xnmalloc (max_elems, sizeof *values);
510 for (i = 0; i < max_elems; i++)
513 stringi_set_insert_nocopy (&set, xstrdup (make_string (i)));
514 check_stringi_set (&set, values, i + 1);
516 for (i = 0; i < max_elems; i++)
518 stringi_set_delete (&set, make_string (i));
519 check_stringi_set (&set, values + i + 1, max_elems - i - 1);
521 stringi_set_destroy (&set);
526 test_boolean_ops (void (*function)(struct stringi_set *a, struct stringi_set *b,
527 unsigned int *a_pat, unsigned int *b_pat))
529 enum { MAX_STRINGS = 7 };
530 unsigned int a_pat, b_pat;
532 for (a_pat = 0; a_pat < (1u << MAX_STRINGS); a_pat++)
533 for (b_pat = 0; b_pat < (1u << MAX_STRINGS); b_pat++)
535 unsigned int new_a_pat = a_pat;
536 unsigned int new_b_pat = b_pat;
537 struct stringi_set a, b;
538 int a_strings[MAX_STRINGS], b_strings[MAX_STRINGS];
541 stringi_set_init (&a);
542 stringi_set_init (&b);
543 for (i = 0; i < MAX_STRINGS; i++)
545 if (a_pat & (1u << i))
546 stringi_set_insert (&a, make_string (i));
547 if (b_pat & (1u << i))
548 stringi_set_insert (&b, make_string (i));
551 function (&a, &b, &new_a_pat, &new_b_pat);
554 for (i = 0; i < MAX_STRINGS; i++)
556 if (new_a_pat & (1u << i))
557 a_strings[n_a++] = i;
558 if (new_b_pat & (1u << i))
559 b_strings[n_b++] = i;
561 check_stringi_set (&a, a_strings, n_a);
562 check_stringi_set (&b, b_strings, n_b);
563 stringi_set_destroy (&a);
564 stringi_set_destroy (&b);
569 union_cb (struct stringi_set *a, struct stringi_set *b,
570 unsigned int *a_pat, unsigned int *b_pat)
572 stringi_set_union (a, b);
579 test_boolean_ops (union_cb);
583 union_and_intersection_cb (struct stringi_set *a, struct stringi_set *b,
584 unsigned int *a_pat, unsigned int *b_pat)
586 unsigned int orig_a_pat = *a_pat;
587 unsigned int orig_b_pat = *b_pat;
589 stringi_set_union_and_intersection (a, b);
590 *a_pat = orig_a_pat | orig_b_pat;
591 *b_pat = orig_a_pat & orig_b_pat;
595 test_union_and_intersection (void)
597 test_boolean_ops (union_and_intersection_cb);
601 intersect_cb (struct stringi_set *a, struct stringi_set *b,
602 unsigned int *a_pat, unsigned int *b_pat)
604 stringi_set_intersect (a, b);
609 test_intersect (void)
611 test_boolean_ops (intersect_cb);
615 subtract_cb (struct stringi_set *a, struct stringi_set *b,
616 unsigned int *a_pat, unsigned int *b_pat)
618 stringi_set_subtract (a, b);
625 test_boolean_ops (subtract_cb);
629 swap_cb (struct stringi_set *a, struct stringi_set *b,
630 unsigned int *a_pat, unsigned int *b_pat)
633 stringi_set_swap (a, b);
642 test_boolean_ops (swap_cb);
646 clear_cb (struct stringi_set *a, struct stringi_set *b UNUSED,
647 unsigned int *a_pat, unsigned int *b_pat UNUSED)
649 stringi_set_clear (a);
656 test_boolean_ops (clear_cb);
660 clone_cb (struct stringi_set *a, struct stringi_set *b,
661 unsigned int *a_pat, unsigned int *b_pat)
663 stringi_set_destroy (a);
664 stringi_set_clone (a, b);
671 test_boolean_ops (clone_cb);
675 test_destroy_null (void)
677 stringi_set_destroy (NULL);
685 const char *description;
686 void (*function) (void);
689 static const struct test tests[] =
692 "insert-any-remove-any",
693 "insert any order, delete any order",
694 test_insert_any_remove_any
697 "insert-any-remove-same",
698 "insert any order, delete same order",
699 test_insert_any_remove_same
702 "insert-any-remove-reverse",
703 "insert any order, delete reverse order",
704 test_insert_any_remove_reverse
708 "insert and delete in random sequence",
713 "insert in ascending order",
722 "union-and-intersection",
723 "union and intersection",
724 test_union_and_intersection
753 "destroying null table",
758 enum { N_TESTS = sizeof tests / sizeof *tests };
761 main (int argc, char *argv[])
767 fprintf (stderr, "exactly one argument required; use --help for help\n");
770 else if (!strcmp (argv[1], "--help"))
772 printf ("%s: test case-insensitive string set library\n"
773 "usage: %s TEST-NAME\n"
774 "where TEST-NAME is one of the following:\n",
776 for (i = 0; i < N_TESTS; i++)
777 printf (" %s\n %s\n", tests[i].name, tests[i].description);
782 for (i = 0; i < N_TESTS; i++)
783 if (!strcmp (argv[1], tests[i].name))
785 tests[i].function ();
790 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);