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_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/str.h"
43 #include "libpspp/string-set.h"
44 #include "libpspp/stringi-set.h"
46 /* Currently running test. */
47 static const char *test_name;
49 /* Exit with a failure code.
50 (Place a breakpoint on this function while debugging.) */
57 /* If OK is not true, prints a message about failure on the
58 current source file and the given LINE and terminates. */
60 check_func (bool ok, int line)
64 printf ("Check failed in %s test at %s, line %d\n",
65 test_name, __FILE__, line);
70 /* Verifies that EXPR evaluates to true.
71 If not, prints a message citing the calling line number and
73 #define check(EXPR) check_func ((EXPR), __LINE__)
75 /* Prints a message about memory exhaustion and exits with a
80 printf ("virtual memory exhausted\n");
84 static void *xmalloc (size_t n) MALLOC_LIKE;
85 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
86 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
88 /* Allocates and returns N bytes of memory. */
105 xmemdup (const void *p, size_t n)
107 void *q = xmalloc (n);
114 xstrdup (const char *string)
116 return xmemdup (string, strlen (string) + 1);
119 /* Allocates and returns N * M bytes of memory. */
121 xnmalloc (size_t n, size_t m)
123 if ((size_t) -1 / m <= n)
125 return xmalloc (n * m);
128 /* Support routines. */
132 MAX_IDX = 1 << IDX_BITS,
133 KEY_MASK = (MAX_IDX - 1),
135 VALUE_MASK = (MAX_IDX - 1) << IDX_BITS,
136 VALUE_SHIFT = IDX_BITS
139 static char *string_table[MAX_IDX];
146 assert (idx >= 0 && idx < MAX_IDX);
147 s = &string_table[idx];
151 str_format_26adic (idx + 1, *s, 16);
161 for (i = 0; i < MAX_IDX; i++)
162 free (string_table[i]);
168 return get_string ((value & KEY_MASK) >> KEY_SHIFT);
172 make_value (int value)
174 return get_string ((value & VALUE_MASK) >> VALUE_SHIFT);
178 random_value (unsigned int seed, int basis)
180 return hash_int (seed, basis) & VALUE_MASK;
183 /* Swaps *A and *B. */
185 swap (int *a, int *b)
192 /* Reverses the order of the CNT integers starting at VALUES. */
194 reverse (int *values, size_t cnt)
200 swap (&values[i++], &values[--j]);
203 /* Arranges the CNT elements in VALUES into the lexicographically next greater
204 permutation. Returns true if successful. If VALUES is already the
205 lexicographically greatest permutation of its elements (i.e. ordered from
206 greatest to smallest), arranges them into the lexicographically least
207 permutation (i.e. ordered from smallest to largest) and returns false.
209 Comparisons among elements of VALUES consider only the bits in KEY_MASK. */
211 next_permutation (int *values, size_t cnt)
219 if ((values[i] & KEY_MASK) < (values[i + 1] & KEY_MASK))
223 (values[i] & KEY_MASK) >= (values[j] & KEY_MASK);
226 swap (values + i, values + j);
227 reverse (values + (i + 1), cnt - (i + 1));
232 reverse (values, cnt);
240 factorial (unsigned int n)
242 unsigned int value = 1;
248 /* Randomly shuffles the CNT elements in ARRAY, each of which is
249 SIZE bytes in size. */
251 random_shuffle (void *array_, size_t cnt, size_t size)
253 char *array = array_;
254 char *tmp = xmalloc (size);
257 for (i = 0; i < cnt; i++)
259 size_t j = rand () % (cnt - i) + i;
262 memcpy (tmp, array + j * size, size);
263 memcpy (array + j * size, array + i * size, size);
264 memcpy (array + i * size, tmp, size);
271 /* Checks that MAP has (KEY, VALUE) as a pair. */
273 check_map_contains (struct stringi_map *map,
274 const char *key, const char *value)
276 struct stringi_map_node *node;
277 const char *found_value;
279 check (stringi_map_contains (map, key));
281 node = stringi_map_find_node (map, key);
282 check (node != NULL);
283 check (!strcasecmp (key, stringi_map_node_get_key (node)));
284 check (!strcmp (value, stringi_map_node_get_value (node)));
286 check (node == stringi_map_insert (map, key, "012"));
287 check (!strcmp (value, stringi_map_node_get_value (node)));
289 check (node == stringi_map_insert_nocopy (map, xstrdup (key),
291 check (!strcmp (value, stringi_map_node_get_value (node)));
293 found_value = stringi_map_find (map, key);
294 check (found_value == stringi_map_node_get_value (node));
295 check (found_value != NULL);
296 check (!strcmp (found_value, value));
299 /* Checks that MAP contains the CNT strings in DATA, that its structure is
300 correct, and that certain operations on MAP produce the expected results. */
302 check_stringi_map (struct stringi_map *map, const int data[], size_t cnt)
306 check (stringi_map_is_empty (map) == (cnt == 0));
307 check (stringi_map_count (map) == cnt);
309 for (i = 0; i < cnt; i++)
311 const char *key = make_key (data[i]);
312 const char *value = make_value (data[i]);
316 check_map_contains (map, key, value);
319 for (p = copy; *p != '\0'; p++)
321 assert (isupper (*p));
323 check_map_contains (map, copy, value);
327 check (!stringi_map_contains (map, "xxx"));
328 check (stringi_map_find (map, "0") == NULL);
329 check (stringi_map_find_node (map, "") == NULL);
330 check (!stringi_map_delete (map, "xyz"));
333 check (stringi_map_first (map) == NULL);
336 const struct stringi_map_node *node;
340 data_copy = xmemdup (data, cnt * sizeof *data);
342 for (node = stringi_map_first (map), i = 0; i < cnt;
343 node = stringi_map_next (map, node), i++)
345 const char *key = stringi_map_node_get_key (node);
346 const char *value = stringi_map_node_get_value (node);
349 for (j = 0; j < left; j++)
350 if (!strcmp (key, make_key (data_copy[j]))
351 || !strcmp (value, make_value (data_copy[j])))
353 data_copy[j] = data_copy[--left];
360 check (node == NULL);
365 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a map in the
366 order specified by INSERTIONS, then deletes them in the order specified by
367 DELETIONS, checking the map's contents for correctness after each
370 test_insert_delete (const int insertions[],
371 const int deletions[],
374 struct stringi_map map;
377 stringi_map_init (&map);
378 check_stringi_map (&map, NULL, 0);
379 for (i = 0; i < cnt; i++)
381 check (stringi_map_insert (&map, make_key (insertions[i]),
382 make_value (insertions[i])));
383 check_stringi_map (&map, insertions, i + 1);
385 for (i = 0; i < cnt; i++)
387 check (stringi_map_delete (&map, make_key (deletions[i])));
388 check_stringi_map (&map, deletions + i + 1, cnt - i - 1);
390 stringi_map_destroy (&map);
393 /* Inserts strings into a map in each possible order, then removes them in each
394 possible order, up to a specified maximum size. */
396 test_insert_any_remove_any (void)
399 const int max_elems = 5;
402 for (cnt = 0; cnt <= max_elems; cnt++)
404 int *insertions, *deletions;
405 unsigned int ins_perm_cnt;
408 insertions = xnmalloc (cnt, sizeof *insertions);
409 deletions = xnmalloc (cnt, sizeof *deletions);
410 for (i = 0; i < cnt; i++)
411 insertions[i] = i | random_value (i, basis);
413 for (ins_perm_cnt = 0;
414 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
417 unsigned int del_perm_cnt;
420 for (i = 0; i < cnt; i++)
421 deletions[i] = i | random_value (i, basis);
423 for (del_perm_cnt = 0;
424 del_perm_cnt == 0 || next_permutation (deletions, cnt);
426 test_insert_delete (insertions, deletions, cnt);
428 check (del_perm_cnt == factorial (cnt));
430 check (ins_perm_cnt == factorial (cnt));
437 /* Inserts strings into a map in each possible order, then removes them in the
438 same order, up to a specified maximum size. */
440 test_insert_any_remove_same (void)
442 const int max_elems = 7;
445 for (cnt = 0; cnt <= max_elems; cnt++)
448 unsigned int permutation_cnt;
451 values = xnmalloc (cnt, sizeof *values);
452 for (i = 0; i < cnt; i++)
453 values[i] = i | random_value (i, 1);
455 for (permutation_cnt = 0;
456 permutation_cnt == 0 || next_permutation (values, cnt);
458 test_insert_delete (values, values, cnt);
459 check (permutation_cnt == factorial (cnt));
465 /* Inserts strings into a map in each possible order, then
466 removes them in reverse order, up to a specified maximum
469 test_insert_any_remove_reverse (void)
471 const int max_elems = 7;
474 for (cnt = 0; cnt <= max_elems; cnt++)
476 int *insertions, *deletions;
477 unsigned int permutation_cnt;
480 insertions = xnmalloc (cnt, sizeof *insertions);
481 deletions = xnmalloc (cnt, sizeof *deletions);
482 for (i = 0; i < cnt; i++)
483 insertions[i] = i | random_value (i, 2);
485 for (permutation_cnt = 0;
486 permutation_cnt == 0 || next_permutation (insertions, cnt);
489 memcpy (deletions, insertions, sizeof *insertions * cnt);
490 reverse (deletions, cnt);
492 test_insert_delete (insertions, deletions, cnt);
494 check (permutation_cnt == factorial (cnt));
501 /* Inserts and removes strings in a map, in random order. */
503 test_random_sequence (void)
506 const int max_elems = 64;
507 const int max_trials = 8;
510 for (cnt = 0; cnt <= max_elems; cnt += 2)
512 int *insertions, *deletions;
516 insertions = xnmalloc (cnt, sizeof *insertions);
517 deletions = xnmalloc (cnt, sizeof *deletions);
518 for (i = 0; i < cnt; i++)
519 insertions[i] = i | random_value (i, basis);
520 for (i = 0; i < cnt; i++)
521 deletions[i] = i | random_value (i, basis);
523 for (trial = 0; trial < max_trials; trial++)
525 random_shuffle (insertions, cnt, sizeof *insertions);
526 random_shuffle (deletions, cnt, sizeof *deletions);
528 test_insert_delete (insertions, deletions, cnt);
536 /* Inserts strings into a map in ascending order, then delete in ascending
539 test_insert_ordered (void)
541 const int max_elems = 64;
543 struct stringi_map map;
546 stringi_map_init (&map);
547 values = xnmalloc (max_elems, sizeof *values);
548 for (i = 0; i < max_elems; i++)
550 values[i] = i | random_value (i, 4);
551 stringi_map_insert_nocopy (&map, xstrdup (make_key (values[i])),
552 xstrdup (make_value (values[i])));
553 check_stringi_map (&map, values, i + 1);
555 for (i = 0; i < max_elems; i++)
557 stringi_map_delete (&map, make_key (i));
558 check_stringi_map (&map, values + i + 1, max_elems - i - 1);
560 stringi_map_destroy (&map);
564 /* Inserts and replaces strings in a map, in random order. */
568 const int basis = 15;
569 enum { MAX_ELEMS = 16 };
570 const int max_trials = 8;
573 for (cnt = 0; cnt <= MAX_ELEMS; cnt++)
575 int insertions[MAX_ELEMS];
579 for (i = 0; i < cnt; i++)
580 insertions[i] = (i / 2) | random_value (i, basis);
582 for (trial = 0; trial < max_trials; trial++)
584 struct stringi_map map;
588 /* Insert with replacement in random order. */
590 stringi_map_init (&map);
591 random_shuffle (insertions, cnt, sizeof *insertions);
592 for (i = 0; i < cnt; i++)
594 const char *key = make_key (insertions[i]);
595 const char *value = make_value (insertions[i]);
598 for (j = 0; j < n_data; j++)
599 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
601 data[j] = insertions[i];
604 data[n_data++] = insertions[i];
608 stringi_map_replace (&map, key, value);
610 stringi_map_replace_nocopy (&map,
611 xstrdup (key), xstrdup (value));
612 check_stringi_map (&map, data, n_data);
615 /* Delete in original order. */
616 for (i = 0; i < cnt; i++)
618 const char *expected_value;
622 expected_value = NULL;
623 for (j = 0; j < n_data; j++)
624 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
626 expected_value = make_value (data[j]);
627 data[j] = data[--n_data];
631 value = stringi_map_find_and_delete (&map,
632 make_key (insertions[i]));
633 check ((value != NULL) == (expected_value != NULL));
634 check (value == NULL || !strcmp (value, expected_value));
637 assert (stringi_map_is_empty (&map));
639 stringi_map_destroy (&map);
645 make_patterned_map (struct stringi_map *map, unsigned int pattern, int basis,
646 int insertions[], int *np)
651 stringi_map_init (map);
654 for (i = 0; pattern != 0; i++)
655 if (pattern & (1u << i))
657 pattern &= pattern - 1;
658 insertions[n] = i | random_value (i, basis);
659 check (stringi_map_insert (map, make_key (insertions[n]),
660 make_value (insertions[n])));
663 check_stringi_map (map, insertions, n);
669 for_each_map (void (*cb)(struct stringi_map *, int data[], int n),
672 enum { MAX_ELEMS = 5 };
673 unsigned int pattern;
675 for (pattern = 0; pattern < (1u << MAX_ELEMS); pattern++)
678 struct stringi_map map;
681 make_patterned_map (&map, pattern, basis, data, &n);
682 (*cb) (&map, data, n);
683 stringi_map_destroy (&map);
688 for_each_pair_of_maps (
689 void (*cb)(struct stringi_map *a, int a_data[], int n_a,
690 struct stringi_map *b, int b_data[], int n_b),
691 int a_basis, int b_basis)
693 enum { MAX_ELEMS = 5 };
694 unsigned int a_pattern, b_pattern;
696 for (a_pattern = 0; a_pattern < (1u << MAX_ELEMS); a_pattern++)
697 for (b_pattern = 0; b_pattern < (1u << MAX_ELEMS); b_pattern++)
699 int a_data[MAX_ELEMS], b_data[MAX_ELEMS];
700 struct stringi_map a_map, b_map;
703 make_patterned_map (&a_map, a_pattern, a_basis, a_data, &n_a);
704 make_patterned_map (&b_map, b_pattern, b_basis, b_data, &n_b);
705 (*cb) (&a_map, a_data, n_a, &b_map, b_data, n_b);
706 stringi_map_destroy (&a_map);
707 stringi_map_destroy (&b_map);
712 clear_cb (struct stringi_map *map, int data[] UNUSED, int n UNUSED)
714 stringi_map_clear (map);
715 check_stringi_map (map, NULL, 0);
721 for_each_map (clear_cb, 5);
725 clone_cb (struct stringi_map *map, int data[], int n)
727 struct stringi_map clone;
729 stringi_map_clone (&clone, map);
730 check_stringi_map (&clone, data, n);
731 stringi_map_destroy (&clone);
737 for_each_map (clone_cb, 6);
741 node_swap_value_cb (struct stringi_map *map, int data[], int n)
745 for (i = 0; i < n; i++)
747 const char *value = make_value (data[i]);
748 struct stringi_map_node *node;
751 node = stringi_map_find_node (map, make_key (data[i]));
752 check (node != NULL);
753 check (!strcmp (stringi_map_node_get_value (node), value));
754 data[i] = (data[i] & KEY_MASK) | random_value (i, 15);
755 old_value = stringi_map_node_swap_value (node, make_value (data[i]));
756 check (old_value != NULL);
757 check (!strcmp (value, old_value));
763 test_node_swap_value (void)
765 for_each_map (node_swap_value_cb, 14);
769 swap_cb (struct stringi_map *a, int a_data[], int n_a,
770 struct stringi_map *b, int b_data[], int n_b)
772 stringi_map_swap (a, b);
773 check_stringi_map (a, b_data, n_b);
774 check_stringi_map (b, a_data, n_a);
780 for_each_pair_of_maps (swap_cb, 7, 8);
784 insert_map_cb (struct stringi_map *a, int a_data[], int n_a,
785 struct stringi_map *b, int b_data[], int n_b)
789 stringi_map_insert_map (a, b);
791 for (i = 0; i < n_b; i++)
793 for (j = 0; j < n_a; j++)
794 if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
796 a_data[n_a++] = b_data[i];
799 check_stringi_map (a, a_data, n_a);
800 check_stringi_map (b, b_data, n_b);
804 test_insert_map (void)
806 for_each_pair_of_maps (insert_map_cb, 91, 10);
810 replace_map_cb (struct stringi_map *a, int a_data[], int n_a,
811 struct stringi_map *b, int b_data[], int n_b)
815 stringi_map_replace_map (a, b);
817 for (i = 0; i < n_b; i++)
819 for (j = 0; j < n_a; j++)
820 if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
822 a_data[j] = (a_data[j] & KEY_MASK) | (b_data[i] & VALUE_MASK);
825 a_data[n_a++] = b_data[i];
828 check_stringi_map (a, a_data, n_a);
829 check_stringi_map (b, b_data, n_b);
833 test_replace_map (void)
835 for_each_pair_of_maps (replace_map_cb, 11, 12);
839 check_iset (struct stringi_set *set, const int *data, int n_data,
847 unique = xmalloc (n_data * sizeof *unique);
848 for (i = 0; i < n_data; i++)
850 int idx = (data[i] & mask) >> shift;
853 for (j = 0; j < n_unique; j++)
854 if (unique[j] == idx)
856 unique[n_unique++] = idx;
860 check (stringi_set_count (set) == n_unique);
861 for (i = 0; i < n_unique; i++)
862 check (stringi_set_contains (set, get_string (unique[i])));
863 stringi_set_destroy (set);
868 check_set (struct string_set *set, const int *data, int n_data,
876 unique = xmalloc (n_data * sizeof *unique);
877 for (i = 0; i < n_data; i++)
879 int idx = (data[i] & mask) >> shift;
882 for (j = 0; j < n_unique; j++)
883 if (unique[j] == idx)
885 unique[n_unique++] = idx;
889 check (string_set_count (set) == n_unique);
890 for (i = 0; i < n_unique; i++)
891 check (string_set_contains (set, get_string (unique[i])));
892 string_set_destroy (set);
897 get_keys_and_values_cb (struct stringi_map *map, int data[], int n)
899 struct stringi_set keys;
900 struct string_set values;
902 stringi_set_init (&keys);
903 string_set_init (&values);
904 stringi_map_get_keys (map, &keys);
905 stringi_map_get_values (map, &values);
906 check_iset (&keys, data, n, KEY_MASK, KEY_SHIFT);
907 check_set (&values, data, n, VALUE_MASK, VALUE_SHIFT);
911 test_get_keys_and_values (void)
913 for_each_map (get_keys_and_values_cb, 13);
917 test_destroy_null (void)
919 stringi_map_destroy (NULL);
924 /* Runs TEST_FUNCTION and prints a message about NAME. */
926 run_test (void (*test_function) (void), const char *name)
937 run_test (test_insert_any_remove_any, "insert any order, delete any order");
938 run_test (test_insert_any_remove_same,
939 "insert any order, delete same order");
940 run_test (test_insert_any_remove_reverse,
941 "insert any order, delete reverse order");
942 run_test (test_random_sequence, "insert and delete in random sequence");
943 run_test (test_replace, "insert and replace in random sequence");
944 run_test (test_insert_ordered, "insert in ascending order");
945 run_test (test_clear, "clear");
946 run_test (test_clone, "clone");
947 run_test (test_swap, "swap");
948 run_test (test_node_swap_value, "node_swap_value");
949 run_test (test_insert_map, "insert_map");
950 run_test (test_replace_map, "replace_map");
951 run_test (test_get_keys_and_values, "get keys and values");
952 run_test (test_destroy_null, "destroying null table");