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_map_* routines defined in
18 stringi-map.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-map.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. */
28 #include "libpspp/stringi-map.h"
40 #include "libpspp/hash-functions.h"
41 #include "libpspp/compiler.h"
42 #include "libpspp/i18n.h"
43 #include "libpspp/str.h"
44 #include "libpspp/string-set.h"
45 #include "libpspp/stringi-set.h"
47 /* Exit with a failure code.
48 (Place a breakpoint on this function while debugging.) */
55 /* If OK is not true, prints a message about failure on the
56 current source file and the given LINE and terminates. */
58 check_func (bool ok, int line)
62 fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
67 /* Verifies that EXPR evaluates to true.
68 If not, prints a message citing the calling line number and
70 #define check(EXPR) check_func ((EXPR), __LINE__)
72 /* Prints a message about memory exhaustion and exits with a
77 printf ("virtual memory exhausted\n");
81 static void *xmalloc (size_t n) MALLOC_LIKE;
82 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
83 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
85 /* Allocates and returns N bytes of memory. */
102 xmemdup (const void *p, size_t n)
104 void *q = xmalloc (n);
111 xstrdup (const char *string)
113 return xmemdup (string, strlen (string) + 1);
116 /* Allocates and returns N * M bytes of memory. */
118 xnmalloc (size_t n, size_t m)
120 if ((size_t) -1 / m <= n)
122 return xmalloc (n * m);
125 /* Support routines. */
129 MAX_IDX = 1 << IDX_BITS,
130 KEY_MASK = (MAX_IDX - 1),
132 VALUE_MASK = (MAX_IDX - 1) << IDX_BITS,
133 VALUE_SHIFT = IDX_BITS
136 static char *string_table[MAX_IDX];
143 assert (idx >= 0 && idx < MAX_IDX);
144 s = &string_table[idx];
148 str_format_26adic (idx + 1, *s, 16);
158 for (i = 0; i < MAX_IDX; i++)
159 free (string_table[i]);
165 return get_string ((value & KEY_MASK) >> KEY_SHIFT);
169 make_value (int value)
171 return get_string ((value & VALUE_MASK) >> VALUE_SHIFT);
175 random_value (unsigned int seed, int basis)
177 return hash_int (seed, basis) & VALUE_MASK;
180 /* Swaps *A and *B. */
182 swap (int *a, int *b)
189 /* Reverses the order of the CNT integers starting at VALUES. */
191 reverse (int *values, size_t cnt)
197 swap (&values[i++], &values[--j]);
200 /* Arranges the CNT elements in VALUES into the lexicographically next greater
201 permutation. Returns true if successful. If VALUES is already the
202 lexicographically greatest permutation of its elements (i.e. ordered from
203 greatest to smallest), arranges them into the lexicographically least
204 permutation (i.e. ordered from smallest to largest) and returns false.
206 Comparisons among elements of VALUES consider only the bits in KEY_MASK. */
208 next_permutation (int *values, size_t cnt)
216 if ((values[i] & KEY_MASK) < (values[i + 1] & KEY_MASK))
220 (values[i] & KEY_MASK) >= (values[j] & KEY_MASK);
223 swap (values + i, values + j);
224 reverse (values + (i + 1), cnt - (i + 1));
229 reverse (values, cnt);
237 factorial (unsigned int n)
239 unsigned int value = 1;
245 /* Randomly shuffles the CNT elements in ARRAY, each of which is
246 SIZE bytes in size. */
248 random_shuffle (void *array_, size_t cnt, size_t size)
250 char *array = array_;
251 char *tmp = xmalloc (size);
254 for (i = 0; i < cnt; i++)
256 size_t j = rand () % (cnt - i) + i;
259 memcpy (tmp, array + j * size, size);
260 memcpy (array + j * size, array + i * size, size);
261 memcpy (array + i * size, tmp, size);
268 /* Checks that MAP has (KEY, VALUE) as a pair. */
270 check_map_contains (struct stringi_map *map,
271 const char *key, const char *value)
273 struct stringi_map_node *node;
274 const char *found_value;
276 check (stringi_map_contains (map, key));
278 node = stringi_map_find_node (map, key);
279 check (node != NULL);
280 check (!utf8_strcasecmp (key, stringi_map_node_get_key (node)));
281 check (!strcmp (value, stringi_map_node_get_value (node)));
283 check (node == stringi_map_insert (map, key, "012"));
284 check (!strcmp (value, stringi_map_node_get_value (node)));
286 check (node == stringi_map_insert_nocopy (map, xstrdup (key),
288 check (!strcmp (value, stringi_map_node_get_value (node)));
290 found_value = stringi_map_find (map, key);
291 check (found_value == stringi_map_node_get_value (node));
292 check (found_value != NULL);
293 check (!strcmp (found_value, value));
296 /* Checks that MAP contains the CNT strings in DATA, that its structure is
297 correct, and that certain operations on MAP produce the expected results. */
299 check_stringi_map (struct stringi_map *map, const int data[], size_t cnt)
303 check (stringi_map_is_empty (map) == (cnt == 0));
304 check (stringi_map_count (map) == cnt);
306 for (i = 0; i < cnt; i++)
308 const char *key = make_key (data[i]);
309 const char *value = make_value (data[i]);
313 check_map_contains (map, key, value);
316 for (p = copy; *p != '\0'; p++)
318 assert (isupper (*p));
320 check_map_contains (map, copy, value);
324 check (!stringi_map_contains (map, "xxx"));
325 check (stringi_map_find (map, "0") == NULL);
326 check (stringi_map_find_node (map, "") == NULL);
327 check (!stringi_map_delete (map, "xyz"));
330 check (stringi_map_first (map) == NULL);
333 const struct stringi_map_node *node;
337 data_copy = xmemdup (data, cnt * sizeof *data);
339 for (node = stringi_map_first (map), i = 0; i < cnt;
340 node = stringi_map_next (map, node), i++)
342 const char *key = stringi_map_node_get_key (node);
343 const char *value = stringi_map_node_get_value (node);
346 for (j = 0; j < left; j++)
347 if (!strcmp (key, make_key (data_copy[j]))
348 || !strcmp (value, make_value (data_copy[j])))
350 data_copy[j] = data_copy[--left];
357 check (node == NULL);
362 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a map in the
363 order specified by INSERTIONS, then deletes them in the order specified by
364 DELETIONS, checking the map's contents for correctness after each
367 test_insert_delete (const int insertions[],
368 const int deletions[],
371 struct stringi_map map;
374 stringi_map_init (&map);
375 check_stringi_map (&map, NULL, 0);
376 for (i = 0; i < cnt; i++)
378 check (stringi_map_insert (&map, make_key (insertions[i]),
379 make_value (insertions[i])));
380 check_stringi_map (&map, insertions, i + 1);
382 for (i = 0; i < cnt; i++)
384 check (stringi_map_delete (&map, make_key (deletions[i])));
385 check_stringi_map (&map, deletions + i + 1, cnt - i - 1);
387 stringi_map_destroy (&map);
390 /* Inserts strings into a map in each possible order, then removes them in each
391 possible order, up to a specified maximum size. */
393 test_insert_any_remove_any (void)
396 const int max_elems = 5;
399 for (cnt = 0; cnt <= max_elems; cnt++)
401 int *insertions, *deletions;
402 unsigned int ins_perm_cnt;
405 insertions = xnmalloc (cnt, sizeof *insertions);
406 deletions = xnmalloc (cnt, sizeof *deletions);
407 for (i = 0; i < cnt; i++)
408 insertions[i] = i | random_value (i, basis);
410 for (ins_perm_cnt = 0;
411 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
414 unsigned int del_perm_cnt;
417 for (i = 0; i < cnt; i++)
418 deletions[i] = i | random_value (i, basis);
420 for (del_perm_cnt = 0;
421 del_perm_cnt == 0 || next_permutation (deletions, cnt);
423 test_insert_delete (insertions, deletions, cnt);
425 check (del_perm_cnt == factorial (cnt));
427 check (ins_perm_cnt == factorial (cnt));
434 /* Inserts strings into a map in each possible order, then removes them in the
435 same order, up to a specified maximum size. */
437 test_insert_any_remove_same (void)
439 const int max_elems = 7;
442 for (cnt = 0; cnt <= max_elems; cnt++)
445 unsigned int permutation_cnt;
448 values = xnmalloc (cnt, sizeof *values);
449 for (i = 0; i < cnt; i++)
450 values[i] = i | random_value (i, 1);
452 for (permutation_cnt = 0;
453 permutation_cnt == 0 || next_permutation (values, cnt);
455 test_insert_delete (values, values, cnt);
456 check (permutation_cnt == factorial (cnt));
462 /* Inserts strings into a map in each possible order, then
463 removes them in reverse order, up to a specified maximum
466 test_insert_any_remove_reverse (void)
468 const int max_elems = 7;
471 for (cnt = 0; cnt <= max_elems; cnt++)
473 int *insertions, *deletions;
474 unsigned int permutation_cnt;
477 insertions = xnmalloc (cnt, sizeof *insertions);
478 deletions = xnmalloc (cnt, sizeof *deletions);
479 for (i = 0; i < cnt; i++)
480 insertions[i] = i | random_value (i, 2);
482 for (permutation_cnt = 0;
483 permutation_cnt == 0 || next_permutation (insertions, cnt);
486 memcpy (deletions, insertions, sizeof *insertions * cnt);
487 reverse (deletions, cnt);
489 test_insert_delete (insertions, deletions, cnt);
491 check (permutation_cnt == factorial (cnt));
498 /* Inserts and removes strings in a map, in random order. */
500 test_random_sequence (void)
503 const int max_elems = 64;
504 const int max_trials = 8;
507 for (cnt = 0; cnt <= max_elems; cnt += 2)
509 int *insertions, *deletions;
513 insertions = xnmalloc (cnt, sizeof *insertions);
514 deletions = xnmalloc (cnt, sizeof *deletions);
515 for (i = 0; i < cnt; i++)
516 insertions[i] = i | random_value (i, basis);
517 for (i = 0; i < cnt; i++)
518 deletions[i] = i | random_value (i, basis);
520 for (trial = 0; trial < max_trials; trial++)
522 random_shuffle (insertions, cnt, sizeof *insertions);
523 random_shuffle (deletions, cnt, sizeof *deletions);
525 test_insert_delete (insertions, deletions, cnt);
533 /* Inserts strings into a map in ascending order, then delete in ascending
536 test_insert_ordered (void)
538 const int max_elems = 64;
540 struct stringi_map map;
543 stringi_map_init (&map);
544 values = xnmalloc (max_elems, sizeof *values);
545 for (i = 0; i < max_elems; i++)
547 values[i] = i | random_value (i, 4);
548 stringi_map_insert_nocopy (&map, xstrdup (make_key (values[i])),
549 xstrdup (make_value (values[i])));
550 check_stringi_map (&map, values, i + 1);
552 for (i = 0; i < max_elems; i++)
554 stringi_map_delete (&map, make_key (i));
555 check_stringi_map (&map, values + i + 1, max_elems - i - 1);
557 stringi_map_destroy (&map);
561 /* Inserts and replaces strings in a map, in random order. */
565 const int basis = 15;
566 enum { MAX_ELEMS = 16 };
567 const int max_trials = 8;
570 for (cnt = 0; cnt <= MAX_ELEMS; cnt++)
572 int insertions[MAX_ELEMS];
576 for (i = 0; i < cnt; i++)
577 insertions[i] = (i / 2) | random_value (i, basis);
579 for (trial = 0; trial < max_trials; trial++)
581 struct stringi_map map;
585 /* Insert with replacement in random order. */
587 stringi_map_init (&map);
588 random_shuffle (insertions, cnt, sizeof *insertions);
589 for (i = 0; i < cnt; i++)
591 const char *key = make_key (insertions[i]);
592 const char *value = make_value (insertions[i]);
595 for (j = 0; j < n_data; j++)
596 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
598 data[j] = insertions[i];
601 data[n_data++] = insertions[i];
605 stringi_map_replace (&map, key, value);
607 stringi_map_replace_nocopy (&map,
608 xstrdup (key), xstrdup (value));
609 check_stringi_map (&map, data, n_data);
612 /* Delete in original order. */
613 for (i = 0; i < cnt; i++)
615 const char *expected_value;
619 expected_value = NULL;
620 for (j = 0; j < n_data; j++)
621 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
623 expected_value = make_value (data[j]);
624 data[j] = data[--n_data];
628 value = stringi_map_find_and_delete (&map,
629 make_key (insertions[i]));
630 check ((value != NULL) == (expected_value != NULL));
631 check (value == NULL || !strcmp (value, expected_value));
634 assert (stringi_map_is_empty (&map));
636 stringi_map_destroy (&map);
642 make_patterned_map (struct stringi_map *map, unsigned int pattern, int basis,
643 int insertions[], int *np)
648 stringi_map_init (map);
651 for (i = 0; pattern != 0; i++)
652 if (pattern & (1u << i))
654 pattern &= pattern - 1;
655 insertions[n] = i | random_value (i, basis);
656 check (stringi_map_insert (map, make_key (insertions[n]),
657 make_value (insertions[n])));
660 check_stringi_map (map, insertions, n);
666 for_each_map (void (*cb)(struct stringi_map *, int data[], int n),
669 enum { MAX_ELEMS = 5 };
670 unsigned int pattern;
672 for (pattern = 0; pattern < (1u << MAX_ELEMS); pattern++)
675 struct stringi_map map;
678 make_patterned_map (&map, pattern, basis, data, &n);
679 (*cb) (&map, data, n);
680 stringi_map_destroy (&map);
685 for_each_pair_of_maps (
686 void (*cb)(struct stringi_map *a, int a_data[], int n_a,
687 struct stringi_map *b, int b_data[], int n_b),
688 int a_basis, int b_basis)
690 enum { MAX_ELEMS = 5 };
691 unsigned int a_pattern, b_pattern;
693 for (a_pattern = 0; a_pattern < (1u << MAX_ELEMS); a_pattern++)
694 for (b_pattern = 0; b_pattern < (1u << MAX_ELEMS); b_pattern++)
696 int a_data[MAX_ELEMS], b_data[MAX_ELEMS];
697 struct stringi_map a_map, b_map;
700 make_patterned_map (&a_map, a_pattern, a_basis, a_data, &n_a);
701 make_patterned_map (&b_map, b_pattern, b_basis, b_data, &n_b);
702 (*cb) (&a_map, a_data, n_a, &b_map, b_data, n_b);
703 stringi_map_destroy (&a_map);
704 stringi_map_destroy (&b_map);
709 clear_cb (struct stringi_map *map, int data[] UNUSED, int n UNUSED)
711 stringi_map_clear (map);
712 check_stringi_map (map, NULL, 0);
718 for_each_map (clear_cb, 5);
722 clone_cb (struct stringi_map *map, int data[], int n)
724 struct stringi_map clone;
726 stringi_map_clone (&clone, map);
727 check_stringi_map (&clone, data, n);
728 stringi_map_destroy (&clone);
734 for_each_map (clone_cb, 6);
738 node_swap_value_cb (struct stringi_map *map, int data[], int n)
742 for (i = 0; i < n; i++)
744 const char *value = make_value (data[i]);
745 struct stringi_map_node *node;
748 node = stringi_map_find_node (map, make_key (data[i]));
749 check (node != NULL);
750 check (!strcmp (stringi_map_node_get_value (node), value));
751 data[i] = (data[i] & KEY_MASK) | random_value (i, 15);
752 old_value = stringi_map_node_swap_value (node, make_value (data[i]));
753 check (old_value != NULL);
754 check (!strcmp (value, old_value));
760 test_node_swap_value (void)
762 for_each_map (node_swap_value_cb, 14);
766 swap_cb (struct stringi_map *a, int a_data[], int n_a,
767 struct stringi_map *b, int b_data[], int n_b)
769 stringi_map_swap (a, b);
770 check_stringi_map (a, b_data, n_b);
771 check_stringi_map (b, a_data, n_a);
777 for_each_pair_of_maps (swap_cb, 7, 8);
781 insert_map_cb (struct stringi_map *a, int a_data[], int n_a,
782 struct stringi_map *b, int b_data[], int n_b)
786 stringi_map_insert_map (a, b);
788 for (i = 0; i < n_b; i++)
790 for (j = 0; j < n_a; j++)
791 if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
793 a_data[n_a++] = b_data[i];
796 check_stringi_map (a, a_data, n_a);
797 check_stringi_map (b, b_data, n_b);
801 test_insert_map (void)
803 for_each_pair_of_maps (insert_map_cb, 91, 10);
807 replace_map_cb (struct stringi_map *a, int a_data[], int n_a,
808 struct stringi_map *b, int b_data[], int n_b)
812 stringi_map_replace_map (a, b);
814 for (i = 0; i < n_b; i++)
816 for (j = 0; j < n_a; j++)
817 if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
819 a_data[j] = (a_data[j] & KEY_MASK) | (b_data[i] & VALUE_MASK);
822 a_data[n_a++] = b_data[i];
825 check_stringi_map (a, a_data, n_a);
826 check_stringi_map (b, b_data, n_b);
830 test_replace_map (void)
832 for_each_pair_of_maps (replace_map_cb, 11, 12);
836 check_iset (struct stringi_set *set, const int *data, int n_data,
844 unique = xmalloc (n_data * sizeof *unique);
845 for (i = 0; i < n_data; i++)
847 int idx = (data[i] & mask) >> shift;
850 for (j = 0; j < n_unique; j++)
851 if (unique[j] == idx)
853 unique[n_unique++] = idx;
857 check (stringi_set_count (set) == n_unique);
858 for (i = 0; i < n_unique; i++)
859 check (stringi_set_contains (set, get_string (unique[i])));
860 stringi_set_destroy (set);
865 check_set (struct string_set *set, const int *data, int n_data,
873 unique = xmalloc (n_data * sizeof *unique);
874 for (i = 0; i < n_data; i++)
876 int idx = (data[i] & mask) >> shift;
879 for (j = 0; j < n_unique; j++)
880 if (unique[j] == idx)
882 unique[n_unique++] = idx;
886 check (string_set_count (set) == n_unique);
887 for (i = 0; i < n_unique; i++)
888 check (string_set_contains (set, get_string (unique[i])));
889 string_set_destroy (set);
894 get_keys_and_values_cb (struct stringi_map *map, int data[], int n)
896 struct stringi_set keys;
897 struct string_set values;
899 stringi_set_init (&keys);
900 string_set_init (&values);
901 stringi_map_get_keys (map, &keys);
902 stringi_map_get_values (map, &values);
903 check_iset (&keys, data, n, KEY_MASK, KEY_SHIFT);
904 check_set (&values, data, n, VALUE_MASK, VALUE_SHIFT);
908 test_get_keys_and_values (void)
910 for_each_map (get_keys_and_values_cb, 13);
914 test_destroy_null (void)
916 stringi_map_destroy (NULL);
924 const char *description;
925 void (*function) (void);
928 static const struct test tests[] =
931 "insert-any-remove-any",
932 "insert any order, delete any order",
933 test_insert_any_remove_any
936 "insert-any-remove-same",
937 "insert any order, delete same order",
938 test_insert_any_remove_same
941 "insert-any-remove-reverse",
942 "insert any order, delete reverse order",
943 test_insert_any_remove_reverse
947 "insert and delete in random sequence",
952 "insert and replace in random sequence",
957 "insert in ascending order",
991 "get-keys-and-values",
992 "get keys and values",
993 test_get_keys_and_values
997 "destroying null table",
1002 enum { N_TESTS = sizeof tests / sizeof *tests };
1005 main (int argc, char *argv[])
1011 fprintf (stderr, "exactly one argument required; use --help for help\n");
1012 return EXIT_FAILURE;
1014 else if (!strcmp (argv[1], "--help"))
1016 printf ("%s: test case-insensitive string map library\n"
1017 "usage: %s TEST-NAME\n"
1018 "where TEST-NAME is one of the following:\n",
1020 for (i = 0; i < N_TESTS; i++)
1021 printf (" %s\n %s\n", tests[i].name, tests[i].description);
1026 for (i = 0; i < N_TESTS; i++)
1027 if (!strcmp (argv[1], tests[i].name))
1029 tests[i].function ();
1034 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
1035 return EXIT_FAILURE;