1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2008, 2009 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 string_set_* routines defined in
18 string-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 string-set.c, except that one branch caused by hash collision is
21 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/string-set.h>
37 #include <libpspp/compiler.h>
39 /* Currently running test. */
40 static const char *test_name;
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 printf ("Check failed in %s test at %s, line %d\n",
58 test_name, __FILE__, line);
63 /* Verifies that EXPR evaluates to true.
64 If not, prints a message citing the calling line number and
66 #define check(EXPR) check_func ((EXPR), __LINE__)
68 /* Prints a message about memory exhaustion and exits with a
73 printf ("virtual memory exhausted\n");
77 static void *xmalloc (size_t n) MALLOC_LIKE;
78 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
79 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
81 /* Allocates and returns N bytes of memory. */
98 xmemdup (const void *p, size_t n)
100 void *q = xmalloc (n);
107 xstrdup (const char *string)
109 return xmemdup (string, strlen (string) + 1);
112 /* Allocates and returns N * M bytes of memory. */
114 xnmalloc (size_t n, size_t m)
116 if ((size_t) -1 / m <= n)
118 return xmalloc (n * m);
121 /* Support routines. */
123 enum { MAX_VALUE = 1024 };
125 static char *string_table[MAX_VALUE];
128 make_string (int value)
132 assert (value >= 0 && value < MAX_VALUE);
133 s = &string_table[value];
137 sprintf (*s, "%d", value);
147 for (i = 0; i < MAX_VALUE; i++)
148 free (string_table[i]);
151 /* Swaps *A and *B. */
153 swap (int *a, int *b)
160 /* Reverses the order of the CNT integers starting at VALUES. */
162 reverse (int *values, size_t cnt)
168 swap (&values[i++], &values[--j]);
171 /* Arranges the CNT elements in VALUES into the lexicographically
172 next greater permutation. Returns true if successful.
173 If VALUES is already the lexicographically greatest
174 permutation of its elements (i.e. ordered from greatest to
175 smallest), arranges them into the lexicographically least
176 permutation (i.e. ordered from smallest to largest) and
179 next_permutation (int *values, size_t cnt)
187 if (values[i] < values[i + 1])
190 for (j = cnt - 1; values[i] >= values[j]; j--)
192 swap (values + i, values + j);
193 reverse (values + (i + 1), cnt - (i + 1));
198 reverse (values, cnt);
206 factorial (unsigned int n)
208 unsigned int value = 1;
214 /* Randomly shuffles the CNT elements in ARRAY, each of which is
215 SIZE bytes in size. */
217 random_shuffle (void *array_, size_t cnt, size_t size)
219 char *array = array_;
220 char *tmp = xmalloc (size);
223 for (i = 0; i < cnt; i++)
225 size_t j = rand () % (cnt - i) + i;
228 memcpy (tmp, array + j * size, size);
229 memcpy (array + j * size, array + i * size, size);
230 memcpy (array + i * size, tmp, size);
237 /* Checks that SET contains the CNT strings in DATA, that its structure is
238 correct, and that certain operations on SET produce the expected results. */
240 check_string_set (struct string_set *set, const int data[], size_t cnt)
244 check (string_set_is_empty (set) == (cnt == 0));
245 check (string_set_count (set) == cnt);
247 for (i = 0; i < cnt; i++)
249 struct string_set_node *node;
250 const char *s = make_string (data[i]);
252 check (string_set_contains (set, s));
253 check (!string_set_insert (set, s));
254 check (!string_set_insert_nocopy (set, xstrdup (s)));
256 node = string_set_find_node (set, s);
257 check (node != NULL);
258 check (!strcmp (s, string_set_node_get_string (node)));
261 check (!string_set_contains (set, "xxx"));
262 check (string_set_find_node (set, "") == NULL);
265 check (string_set_first (set) == NULL);
268 const struct string_set_node *node;
272 data_copy = xmemdup (data, cnt * sizeof *data);
274 for (node = string_set_first (set), i = 0; i < cnt;
275 node = string_set_next (set, node), i++)
277 const char *s = string_set_node_get_string (node);
280 for (j = 0; j < left; j++)
281 if (!strcmp (s, make_string (data_copy[j])))
283 data_copy[j] = data_copy[--left];
290 check (node == NULL);
295 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a set in the
296 order specified by INSERTIONS, then deletes them in the order specified by
297 DELETIONS, checking the set's contents for correctness after each
300 test_insert_delete (const int insertions[],
301 const int deletions[],
304 struct string_set set;
307 string_set_init (&set);
308 check_string_set (&set, NULL, 0);
309 for (i = 0; i < cnt; i++)
311 check (string_set_insert (&set, make_string (insertions[i])));
312 check_string_set (&set, insertions, i + 1);
314 for (i = 0; i < cnt; i++)
316 check (string_set_delete (&set, make_string (deletions[i])));
317 check_string_set (&set, deletions + i + 1, cnt - i - 1);
319 string_set_destroy (&set);
322 /* Inserts strings into a set in each possible order, then removes them in each
323 possible order, up to a specified maximum size. */
325 test_insert_any_remove_any (void)
327 const int max_elems = 5;
330 for (cnt = 0; cnt <= max_elems; cnt++)
332 int *insertions, *deletions;
333 unsigned int ins_perm_cnt;
336 insertions = xnmalloc (cnt, sizeof *insertions);
337 deletions = xnmalloc (cnt, sizeof *deletions);
338 for (i = 0; i < cnt; i++)
341 for (ins_perm_cnt = 0;
342 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
345 unsigned int del_perm_cnt;
348 for (i = 0; i < cnt; i++)
351 for (del_perm_cnt = 0;
352 del_perm_cnt == 0 || next_permutation (deletions, cnt);
354 test_insert_delete (insertions, deletions, cnt);
356 check (del_perm_cnt == factorial (cnt));
358 check (ins_perm_cnt == factorial (cnt));
365 /* Inserts strings into a set in each possible order, then removes them in the
366 same order, up to a specified maximum size. */
368 test_insert_any_remove_same (void)
370 const int max_elems = 7;
373 for (cnt = 0; cnt <= max_elems; cnt++)
376 unsigned int permutation_cnt;
379 values = xnmalloc (cnt, sizeof *values);
380 for (i = 0; i < cnt; i++)
383 for (permutation_cnt = 0;
384 permutation_cnt == 0 || next_permutation (values, cnt);
386 test_insert_delete (values, values, cnt);
387 check (permutation_cnt == factorial (cnt));
393 /* Inserts strings into a set in each possible order, then
394 removes them in reverse order, up to a specified maximum
397 test_insert_any_remove_reverse (void)
399 const int max_elems = 7;
402 for (cnt = 0; cnt <= max_elems; cnt++)
404 int *insertions, *deletions;
405 unsigned int permutation_cnt;
408 insertions = xnmalloc (cnt, sizeof *insertions);
409 deletions = xnmalloc (cnt, sizeof *deletions);
410 for (i = 0; i < cnt; i++)
413 for (permutation_cnt = 0;
414 permutation_cnt == 0 || next_permutation (insertions, cnt);
417 memcpy (deletions, insertions, sizeof *insertions * cnt);
418 reverse (deletions, cnt);
420 test_insert_delete (insertions, deletions, cnt);
422 check (permutation_cnt == factorial (cnt));
429 /* Inserts and removes strings in a set, in random order. */
431 test_random_sequence (void)
433 const int max_elems = 64;
434 const int max_trials = 8;
437 for (cnt = 0; cnt <= max_elems; cnt += 2)
439 int *insertions, *deletions;
443 insertions = xnmalloc (cnt, sizeof *insertions);
444 deletions = xnmalloc (cnt, sizeof *deletions);
445 for (i = 0; i < cnt; i++)
447 for (i = 0; i < cnt; i++)
450 for (trial = 0; trial < max_trials; trial++)
452 random_shuffle (insertions, cnt, sizeof *insertions);
453 random_shuffle (deletions, cnt, sizeof *deletions);
455 test_insert_delete (insertions, deletions, cnt);
463 /* Inserts strings into a set in ascending order, then delete in ascending
466 test_insert_ordered (void)
468 const int max_elems = 64;
470 struct string_set set;
473 string_set_init (&set);
474 values = xnmalloc (max_elems, sizeof *values);
475 for (i = 0; i < max_elems; i++)
478 string_set_insert_nocopy (&set, xstrdup (make_string (i)));
479 check_string_set (&set, values, i + 1);
481 for (i = 0; i < max_elems; i++)
483 string_set_delete (&set, make_string (i));
484 check_string_set (&set, values + i + 1, max_elems - i - 1);
486 string_set_destroy (&set);
491 test_boolean_ops (void (*function)(struct string_set *a, struct string_set *b,
492 unsigned int *a_pat, unsigned int *b_pat))
494 enum { MAX_STRINGS = 7 };
495 unsigned int a_pat, b_pat;
497 for (a_pat = 0; a_pat < (1u << MAX_STRINGS); a_pat++)
498 for (b_pat = 0; b_pat < (1u << MAX_STRINGS); b_pat++)
500 unsigned int new_a_pat = a_pat;
501 unsigned int new_b_pat = b_pat;
502 struct string_set a, b;
503 int a_strings[MAX_STRINGS], b_strings[MAX_STRINGS];
506 string_set_init (&a);
507 string_set_init (&b);
508 for (i = 0; i < MAX_STRINGS; i++)
510 if (a_pat & (1u << i))
511 string_set_insert (&a, make_string (i));
512 if (b_pat & (1u << i))
513 string_set_insert (&b, make_string (i));
516 function (&a, &b, &new_a_pat, &new_b_pat);
519 for (i = 0; i < MAX_STRINGS; i++)
521 if (new_a_pat & (1u << i))
522 a_strings[n_a++] = i;
523 if (new_b_pat & (1u << i))
524 b_strings[n_b++] = i;
526 check_string_set (&a, a_strings, n_a);
527 check_string_set (&b, b_strings, n_b);
528 string_set_destroy (&a);
529 string_set_destroy (&b);
534 union_cb (struct string_set *a, struct string_set *b,
535 unsigned int *a_pat, unsigned int *b_pat)
537 string_set_union (a, b);
544 test_boolean_ops (union_cb);
548 union_and_intersection_cb (struct string_set *a, struct string_set *b,
549 unsigned int *a_pat, unsigned int *b_pat)
551 unsigned int orig_a_pat = *a_pat;
552 unsigned int orig_b_pat = *b_pat;
554 string_set_union_and_intersection (a, b);
555 *a_pat = orig_a_pat | orig_b_pat;
556 *b_pat = orig_a_pat & orig_b_pat;
560 test_union_and_intersection (void)
562 test_boolean_ops (union_and_intersection_cb);
566 intersect_cb (struct string_set *a, struct string_set *b,
567 unsigned int *a_pat, unsigned int *b_pat)
569 string_set_intersect (a, b);
574 test_intersect (void)
576 test_boolean_ops (intersect_cb);
580 subtract_cb (struct string_set *a, struct string_set *b,
581 unsigned int *a_pat, unsigned int *b_pat)
583 string_set_subtract (a, b);
590 test_boolean_ops (subtract_cb);
594 swap_cb (struct string_set *a, struct string_set *b,
595 unsigned int *a_pat, unsigned int *b_pat)
598 string_set_swap (a, b);
607 test_boolean_ops (swap_cb);
611 clear_cb (struct string_set *a, struct string_set *b UNUSED,
612 unsigned int *a_pat, unsigned int *b_pat UNUSED)
614 string_set_clear (a);
621 test_boolean_ops (clear_cb);
625 clone_cb (struct string_set *a, struct string_set *b,
626 unsigned int *a_pat, unsigned int *b_pat)
628 string_set_destroy (a);
629 string_set_clone (a, b);
636 test_boolean_ops (clone_cb);
640 test_destroy_null (void)
642 string_set_destroy (NULL);
647 /* Runs TEST_FUNCTION and prints a message about NAME. */
649 run_test (void (*test_function) (void), const char *name)
660 run_test (test_insert_any_remove_any, "insert any order, delete any order");
661 run_test (test_insert_any_remove_same,
662 "insert any order, delete same order");
663 run_test (test_insert_any_remove_reverse,
664 "insert any order, delete reverse order");
665 run_test (test_random_sequence, "insert and delete in random sequence");
666 run_test (test_insert_ordered, "insert in ascending order");
667 run_test (test_union, "union");
668 run_test (test_union_and_intersection, "union and intersection");
669 run_test (test_intersect, "intersect");
670 run_test (test_subtract, "subtract");
671 run_test (test_swap, "swap");
672 run_test (test_clear, "clear");
673 run_test (test_clone, "clone");
674 run_test (test_destroy_null, "destroying null table");