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);
286 check (stringi_set_first (set) == NULL);
289 const struct stringi_set_node *node;
293 data_copy = xmemdup (data, cnt * sizeof *data);
295 for (node = stringi_set_first (set), i = 0; i < cnt;
296 node = stringi_set_next (set, node), i++)
298 const char *s = stringi_set_node_get_string (node);
301 for (j = 0; j < left; j++)
302 if (!strcasecmp (s, make_string (data_copy[j])))
304 data_copy[j] = data_copy[--left];
311 check (node == NULL);
316 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a set in the
317 order specified by INSERTIONS, then deletes them in the order specified by
318 DELETIONS, checking the set's contents for correctness after each
321 test_insert_delete (const int insertions[],
322 const int deletions[],
325 struct stringi_set set;
328 stringi_set_init (&set);
329 check_stringi_set (&set, NULL, 0);
330 for (i = 0; i < cnt; i++)
332 check (stringi_set_insert (&set, make_string (insertions[i])));
333 check_stringi_set (&set, insertions, i + 1);
335 for (i = 0; i < cnt; i++)
337 check (stringi_set_delete (&set, make_string (deletions[i])));
338 check_stringi_set (&set, deletions + i + 1, cnt - i - 1);
340 stringi_set_destroy (&set);
343 /* Inserts strings into a set in each possible order, then removes them in each
344 possible order, up to a specified maximum size. */
346 test_insert_any_remove_any (void)
348 const int max_elems = 5;
351 for (cnt = 0; cnt <= max_elems; cnt++)
353 int *insertions, *deletions;
354 unsigned int ins_perm_cnt;
357 insertions = xnmalloc (cnt, sizeof *insertions);
358 deletions = xnmalloc (cnt, sizeof *deletions);
359 for (i = 0; i < cnt; i++)
362 for (ins_perm_cnt = 0;
363 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
366 unsigned int del_perm_cnt;
369 for (i = 0; i < cnt; i++)
372 for (del_perm_cnt = 0;
373 del_perm_cnt == 0 || next_permutation (deletions, cnt);
375 test_insert_delete (insertions, deletions, cnt);
377 check (del_perm_cnt == factorial (cnt));
379 check (ins_perm_cnt == factorial (cnt));
386 /* Inserts strings into a set in each possible order, then removes them in the
387 same order, up to a specified maximum size. */
389 test_insert_any_remove_same (void)
391 const int max_elems = 7;
394 for (cnt = 0; cnt <= max_elems; cnt++)
397 unsigned int permutation_cnt;
400 values = xnmalloc (cnt, sizeof *values);
401 for (i = 0; i < cnt; i++)
404 for (permutation_cnt = 0;
405 permutation_cnt == 0 || next_permutation (values, cnt);
407 test_insert_delete (values, values, cnt);
408 check (permutation_cnt == factorial (cnt));
414 /* Inserts strings into a set in each possible order, then
415 removes them in reverse order, up to a specified maximum
418 test_insert_any_remove_reverse (void)
420 const int max_elems = 7;
423 for (cnt = 0; cnt <= max_elems; cnt++)
425 int *insertions, *deletions;
426 unsigned int permutation_cnt;
429 insertions = xnmalloc (cnt, sizeof *insertions);
430 deletions = xnmalloc (cnt, sizeof *deletions);
431 for (i = 0; i < cnt; i++)
434 for (permutation_cnt = 0;
435 permutation_cnt == 0 || next_permutation (insertions, cnt);
438 memcpy (deletions, insertions, sizeof *insertions * cnt);
439 reverse (deletions, cnt);
441 test_insert_delete (insertions, deletions, cnt);
443 check (permutation_cnt == factorial (cnt));
450 /* Inserts and removes strings in a set, in random order. */
452 test_random_sequence (void)
454 const int max_elems = 64;
455 const int max_trials = 8;
458 for (cnt = 0; cnt <= max_elems; cnt += 2)
460 int *insertions, *deletions;
464 insertions = xnmalloc (cnt, sizeof *insertions);
465 deletions = xnmalloc (cnt, sizeof *deletions);
466 for (i = 0; i < cnt; i++)
468 for (i = 0; i < cnt; i++)
471 for (trial = 0; trial < max_trials; trial++)
473 random_shuffle (insertions, cnt, sizeof *insertions);
474 random_shuffle (deletions, cnt, sizeof *deletions);
476 test_insert_delete (insertions, deletions, cnt);
484 /* Inserts strings into a set in ascending order, then delete in ascending
487 test_insert_ordered (void)
489 const int max_elems = 64;
491 struct stringi_set set;
494 stringi_set_init (&set);
495 values = xnmalloc (max_elems, sizeof *values);
496 for (i = 0; i < max_elems; i++)
499 stringi_set_insert_nocopy (&set, xstrdup (make_string (i)));
500 check_stringi_set (&set, values, i + 1);
502 for (i = 0; i < max_elems; i++)
504 stringi_set_delete (&set, make_string (i));
505 check_stringi_set (&set, values + i + 1, max_elems - i - 1);
507 stringi_set_destroy (&set);
512 test_boolean_ops (void (*function)(struct stringi_set *a, struct stringi_set *b,
513 unsigned int *a_pat, unsigned int *b_pat))
515 enum { MAX_STRINGS = 7 };
516 unsigned int a_pat, b_pat;
518 for (a_pat = 0; a_pat < (1u << MAX_STRINGS); a_pat++)
519 for (b_pat = 0; b_pat < (1u << MAX_STRINGS); b_pat++)
521 unsigned int new_a_pat = a_pat;
522 unsigned int new_b_pat = b_pat;
523 struct stringi_set a, b;
524 int a_strings[MAX_STRINGS], b_strings[MAX_STRINGS];
527 stringi_set_init (&a);
528 stringi_set_init (&b);
529 for (i = 0; i < MAX_STRINGS; i++)
531 if (a_pat & (1u << i))
532 stringi_set_insert (&a, make_string (i));
533 if (b_pat & (1u << i))
534 stringi_set_insert (&b, make_string (i));
537 function (&a, &b, &new_a_pat, &new_b_pat);
540 for (i = 0; i < MAX_STRINGS; i++)
542 if (new_a_pat & (1u << i))
543 a_strings[n_a++] = i;
544 if (new_b_pat & (1u << i))
545 b_strings[n_b++] = i;
547 check_stringi_set (&a, a_strings, n_a);
548 check_stringi_set (&b, b_strings, n_b);
549 stringi_set_destroy (&a);
550 stringi_set_destroy (&b);
555 union_cb (struct stringi_set *a, struct stringi_set *b,
556 unsigned int *a_pat, unsigned int *b_pat)
558 stringi_set_union (a, b);
565 test_boolean_ops (union_cb);
569 union_and_intersection_cb (struct stringi_set *a, struct stringi_set *b,
570 unsigned int *a_pat, unsigned int *b_pat)
572 unsigned int orig_a_pat = *a_pat;
573 unsigned int orig_b_pat = *b_pat;
575 stringi_set_union_and_intersection (a, b);
576 *a_pat = orig_a_pat | orig_b_pat;
577 *b_pat = orig_a_pat & orig_b_pat;
581 test_union_and_intersection (void)
583 test_boolean_ops (union_and_intersection_cb);
587 intersect_cb (struct stringi_set *a, struct stringi_set *b,
588 unsigned int *a_pat, unsigned int *b_pat)
590 stringi_set_intersect (a, b);
595 test_intersect (void)
597 test_boolean_ops (intersect_cb);
601 subtract_cb (struct stringi_set *a, struct stringi_set *b,
602 unsigned int *a_pat, unsigned int *b_pat)
604 stringi_set_subtract (a, b);
611 test_boolean_ops (subtract_cb);
615 swap_cb (struct stringi_set *a, struct stringi_set *b,
616 unsigned int *a_pat, unsigned int *b_pat)
619 stringi_set_swap (a, b);
628 test_boolean_ops (swap_cb);
632 clear_cb (struct stringi_set *a, struct stringi_set *b UNUSED,
633 unsigned int *a_pat, unsigned int *b_pat UNUSED)
635 stringi_set_clear (a);
642 test_boolean_ops (clear_cb);
646 clone_cb (struct stringi_set *a, struct stringi_set *b,
647 unsigned int *a_pat, unsigned int *b_pat)
649 stringi_set_destroy (a);
650 stringi_set_clone (a, b);
657 test_boolean_ops (clone_cb);
661 test_destroy_null (void)
663 stringi_set_destroy (NULL);
668 /* Runs TEST_FUNCTION and prints a message about NAME. */
670 run_test (void (*test_function) (void), const char *name)
681 run_test (test_insert_any_remove_any, "insert any order, delete any order");
682 run_test (test_insert_any_remove_same,
683 "insert any order, delete same order");
684 run_test (test_insert_any_remove_reverse,
685 "insert any order, delete reverse order");
686 run_test (test_random_sequence, "insert and delete in random sequence");
687 run_test (test_insert_ordered, "insert in ascending order");
688 run_test (test_union, "union");
689 run_test (test_union_and_intersection, "union and intersection");
690 run_test (test_intersect, "intersect");
691 run_test (test_subtract, "subtract");
692 run_test (test_swap, "swap");
693 run_test (test_clear, "clear");
694 run_test (test_clone, "clone");
695 run_test (test_destroy_null, "destroying null table");