1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2008, 2009, 2010 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/str.h"
41 /* Currently running test. */
42 static const char *test_name;
44 /* Exit with a failure code.
45 (Place a breakpoint on this function while debugging.) */
52 /* If OK is not true, prints a message about failure on the
53 current source file and the given LINE and terminates. */
55 check_func (bool ok, int line)
59 printf ("Check failed in %s test at %s, line %d\n",
60 test_name, __FILE__, line);
65 /* Verifies that EXPR evaluates to true.
66 If not, prints a message citing the calling line number and
68 #define check(EXPR) check_func ((EXPR), __LINE__)
70 /* Prints a message about memory exhaustion and exits with a
75 printf ("virtual memory exhausted\n");
79 static void *xmalloc (size_t n) MALLOC_LIKE;
80 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
81 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
83 /* Allocates and returns N bytes of memory. */
100 xmemdup (const void *p, size_t n)
102 void *q = xmalloc (n);
109 xstrdup (const char *string)
111 return xmemdup (string, strlen (string) + 1);
114 /* Allocates and returns N * M bytes of memory. */
116 xnmalloc (size_t n, size_t m)
118 if ((size_t) -1 / m <= n)
120 return xmalloc (n * m);
123 /* Support routines. */
125 enum { MAX_VALUE = 1024 };
127 static char *string_table[MAX_VALUE];
130 make_string (int value)
134 assert (value >= 0 && value < MAX_VALUE);
135 s = &string_table[value];
139 str_format_26adic (value + 1, *s, 16);
149 for (i = 0; i < MAX_VALUE; i++)
150 free (string_table[i]);
153 /* Swaps *A and *B. */
155 swap (int *a, int *b)
162 /* Reverses the order of the CNT integers starting at VALUES. */
164 reverse (int *values, size_t cnt)
170 swap (&values[i++], &values[--j]);
173 /* Arranges the CNT elements in VALUES into the lexicographically
174 next greater permutation. Returns true if successful.
175 If VALUES is already the lexicographically greatest
176 permutation of its elements (i.e. ordered from greatest to
177 smallest), arranges them into the lexicographically least
178 permutation (i.e. ordered from smallest to largest) and
181 next_permutation (int *values, size_t cnt)
189 if (values[i] < values[i + 1])
192 for (j = cnt - 1; values[i] >= values[j]; j--)
194 swap (values + i, values + j);
195 reverse (values + (i + 1), cnt - (i + 1));
200 reverse (values, cnt);
208 factorial (unsigned int n)
210 unsigned int value = 1;
216 /* Randomly shuffles the CNT elements in ARRAY, each of which is
217 SIZE bytes in size. */
219 random_shuffle (void *array_, size_t cnt, size_t size)
221 char *array = array_;
222 char *tmp = xmalloc (size);
225 for (i = 0; i < cnt; i++)
227 size_t j = rand () % (cnt - i) + i;
230 memcpy (tmp, array + j * size, size);
231 memcpy (array + j * size, array + i * size, size);
232 memcpy (array + i * size, tmp, size);
239 /* Checks that SET contains STRING. */
241 check_set_contains (struct stringi_set *set, const char *string)
243 struct stringi_set_node *node;
245 check (stringi_set_contains (set, string));
246 check (!stringi_set_insert (set, string));
247 check (!stringi_set_insert_nocopy (set, xstrdup (string)));
249 node = stringi_set_find_node (set, string);
250 check (node != NULL);
251 check (!strcasecmp (string, stringi_set_node_get_string (node)));
254 /* Checks that SET contains the CNT strings in DATA, that its structure is
255 correct, and that certain operations on SET produce the expected results. */
257 check_stringi_set (struct stringi_set *set, const int data[], size_t cnt)
261 check (stringi_set_is_empty (set) == (cnt == 0));
262 check (stringi_set_count (set) == cnt);
264 for (i = 0; i < cnt; i++)
270 s = make_string (data[i]);
271 check_set_contains (set, s);
274 for (p = copy; *p != '\0'; p++)
276 assert (isupper (*p));
278 check_set_contains (set, copy);
282 check (!stringi_set_contains (set, "xxx"));
283 check (stringi_set_find_node (set, "") == NULL);
287 check (stringi_set_first (set) == NULL);
288 free (stringi_set_get_array (set));
292 const struct stringi_set_node *node;
297 array = stringi_set_get_array (set);
298 data_copy = xmemdup (data, cnt * sizeof *data);
300 for (node = stringi_set_first (set), i = 0; i < cnt;
301 node = stringi_set_next (set, node), i++)
303 const char *s = stringi_set_node_get_string (node);
306 check (s == array[i]);
308 for (j = 0; j < left; j++)
309 if (!strcasecmp (s, make_string (data_copy[j])))
311 data_copy[j] = data_copy[--left];
318 check (node == NULL);
322 array = stringi_set_get_sorted_array (set);
323 for (i = 0; i < cnt; i++)
326 check (strcasecmp (array[i - 1], array[i]) < 0);
327 check (stringi_set_contains (set, array[i]));
333 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a set in the
334 order specified by INSERTIONS, then deletes them in the order specified by
335 DELETIONS, checking the set's contents for correctness after each
338 test_insert_delete (const int insertions[],
339 const int deletions[],
342 struct stringi_set set;
345 stringi_set_init (&set);
346 check_stringi_set (&set, NULL, 0);
347 for (i = 0; i < cnt; i++)
349 check (stringi_set_insert (&set, make_string (insertions[i])));
350 check_stringi_set (&set, insertions, i + 1);
352 for (i = 0; i < cnt; i++)
354 check (stringi_set_delete (&set, make_string (deletions[i])));
355 check_stringi_set (&set, deletions + i + 1, cnt - i - 1);
357 stringi_set_destroy (&set);
360 /* Inserts strings into a set in each possible order, then removes them in each
361 possible order, up to a specified maximum size. */
363 test_insert_any_remove_any (void)
365 const int max_elems = 5;
368 for (cnt = 0; cnt <= max_elems; cnt++)
370 int *insertions, *deletions;
371 unsigned int ins_perm_cnt;
374 insertions = xnmalloc (cnt, sizeof *insertions);
375 deletions = xnmalloc (cnt, sizeof *deletions);
376 for (i = 0; i < cnt; i++)
379 for (ins_perm_cnt = 0;
380 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
383 unsigned int del_perm_cnt;
386 for (i = 0; i < cnt; i++)
389 for (del_perm_cnt = 0;
390 del_perm_cnt == 0 || next_permutation (deletions, cnt);
392 test_insert_delete (insertions, deletions, cnt);
394 check (del_perm_cnt == factorial (cnt));
396 check (ins_perm_cnt == factorial (cnt));
403 /* Inserts strings into a set in each possible order, then removes them in the
404 same order, up to a specified maximum size. */
406 test_insert_any_remove_same (void)
408 const int max_elems = 7;
411 for (cnt = 0; cnt <= max_elems; cnt++)
414 unsigned int permutation_cnt;
417 values = xnmalloc (cnt, sizeof *values);
418 for (i = 0; i < cnt; i++)
421 for (permutation_cnt = 0;
422 permutation_cnt == 0 || next_permutation (values, cnt);
424 test_insert_delete (values, values, cnt);
425 check (permutation_cnt == factorial (cnt));
431 /* Inserts strings into a set in each possible order, then
432 removes them in reverse order, up to a specified maximum
435 test_insert_any_remove_reverse (void)
437 const int max_elems = 7;
440 for (cnt = 0; cnt <= max_elems; cnt++)
442 int *insertions, *deletions;
443 unsigned int permutation_cnt;
446 insertions = xnmalloc (cnt, sizeof *insertions);
447 deletions = xnmalloc (cnt, sizeof *deletions);
448 for (i = 0; i < cnt; i++)
451 for (permutation_cnt = 0;
452 permutation_cnt == 0 || next_permutation (insertions, cnt);
455 memcpy (deletions, insertions, sizeof *insertions * cnt);
456 reverse (deletions, cnt);
458 test_insert_delete (insertions, deletions, cnt);
460 check (permutation_cnt == factorial (cnt));
467 /* Inserts and removes strings in a set, in random order. */
469 test_random_sequence (void)
471 const int max_elems = 64;
472 const int max_trials = 8;
475 for (cnt = 0; cnt <= max_elems; cnt += 2)
477 int *insertions, *deletions;
481 insertions = xnmalloc (cnt, sizeof *insertions);
482 deletions = xnmalloc (cnt, sizeof *deletions);
483 for (i = 0; i < cnt; i++)
485 for (i = 0; i < cnt; i++)
488 for (trial = 0; trial < max_trials; trial++)
490 random_shuffle (insertions, cnt, sizeof *insertions);
491 random_shuffle (deletions, cnt, sizeof *deletions);
493 test_insert_delete (insertions, deletions, cnt);
501 /* Inserts strings into a set in ascending order, then delete in ascending
504 test_insert_ordered (void)
506 const int max_elems = 64;
508 struct stringi_set set;
511 stringi_set_init (&set);
512 values = xnmalloc (max_elems, sizeof *values);
513 for (i = 0; i < max_elems; i++)
516 stringi_set_insert_nocopy (&set, xstrdup (make_string (i)));
517 check_stringi_set (&set, values, i + 1);
519 for (i = 0; i < max_elems; i++)
521 stringi_set_delete (&set, make_string (i));
522 check_stringi_set (&set, values + i + 1, max_elems - i - 1);
524 stringi_set_destroy (&set);
529 test_boolean_ops (void (*function)(struct stringi_set *a, struct stringi_set *b,
530 unsigned int *a_pat, unsigned int *b_pat))
532 enum { MAX_STRINGS = 7 };
533 unsigned int a_pat, b_pat;
535 for (a_pat = 0; a_pat < (1u << MAX_STRINGS); a_pat++)
536 for (b_pat = 0; b_pat < (1u << MAX_STRINGS); b_pat++)
538 unsigned int new_a_pat = a_pat;
539 unsigned int new_b_pat = b_pat;
540 struct stringi_set a, b;
541 int a_strings[MAX_STRINGS], b_strings[MAX_STRINGS];
544 stringi_set_init (&a);
545 stringi_set_init (&b);
546 for (i = 0; i < MAX_STRINGS; i++)
548 if (a_pat & (1u << i))
549 stringi_set_insert (&a, make_string (i));
550 if (b_pat & (1u << i))
551 stringi_set_insert (&b, make_string (i));
554 function (&a, &b, &new_a_pat, &new_b_pat);
557 for (i = 0; i < MAX_STRINGS; i++)
559 if (new_a_pat & (1u << i))
560 a_strings[n_a++] = i;
561 if (new_b_pat & (1u << i))
562 b_strings[n_b++] = i;
564 check_stringi_set (&a, a_strings, n_a);
565 check_stringi_set (&b, b_strings, n_b);
566 stringi_set_destroy (&a);
567 stringi_set_destroy (&b);
572 union_cb (struct stringi_set *a, struct stringi_set *b,
573 unsigned int *a_pat, unsigned int *b_pat)
575 stringi_set_union (a, b);
582 test_boolean_ops (union_cb);
586 union_and_intersection_cb (struct stringi_set *a, struct stringi_set *b,
587 unsigned int *a_pat, unsigned int *b_pat)
589 unsigned int orig_a_pat = *a_pat;
590 unsigned int orig_b_pat = *b_pat;
592 stringi_set_union_and_intersection (a, b);
593 *a_pat = orig_a_pat | orig_b_pat;
594 *b_pat = orig_a_pat & orig_b_pat;
598 test_union_and_intersection (void)
600 test_boolean_ops (union_and_intersection_cb);
604 intersect_cb (struct stringi_set *a, struct stringi_set *b,
605 unsigned int *a_pat, unsigned int *b_pat)
607 stringi_set_intersect (a, b);
612 test_intersect (void)
614 test_boolean_ops (intersect_cb);
618 subtract_cb (struct stringi_set *a, struct stringi_set *b,
619 unsigned int *a_pat, unsigned int *b_pat)
621 stringi_set_subtract (a, b);
628 test_boolean_ops (subtract_cb);
632 swap_cb (struct stringi_set *a, struct stringi_set *b,
633 unsigned int *a_pat, unsigned int *b_pat)
636 stringi_set_swap (a, b);
645 test_boolean_ops (swap_cb);
649 clear_cb (struct stringi_set *a, struct stringi_set *b UNUSED,
650 unsigned int *a_pat, unsigned int *b_pat UNUSED)
652 stringi_set_clear (a);
659 test_boolean_ops (clear_cb);
663 clone_cb (struct stringi_set *a, struct stringi_set *b,
664 unsigned int *a_pat, unsigned int *b_pat)
666 stringi_set_destroy (a);
667 stringi_set_clone (a, b);
674 test_boolean_ops (clone_cb);
678 test_destroy_null (void)
680 stringi_set_destroy (NULL);
685 /* Runs TEST_FUNCTION and prints a message about NAME. */
687 run_test (void (*test_function) (void), const char *name)
698 run_test (test_insert_any_remove_any, "insert any order, delete any order");
699 run_test (test_insert_any_remove_same,
700 "insert any order, delete same order");
701 run_test (test_insert_any_remove_reverse,
702 "insert any order, delete reverse order");
703 run_test (test_random_sequence, "insert and delete in random sequence");
704 run_test (test_insert_ordered, "insert in ascending order");
705 run_test (test_union, "union");
706 run_test (test_union_and_intersection, "union and intersection");
707 run_test (test_intersect, "intersect");
708 run_test (test_subtract, "subtract");
709 run_test (test_swap, "swap");
710 run_test (test_clear, "clear");
711 run_test (test_clone, "clone");
712 run_test (test_destroy_null, "destroying null table");