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_map_* routines defined in
18 string-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 string-map.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. */
28 #include <libpspp/string-map.h>
39 #include <libpspp/hash-functions.h>
40 #include <libpspp/compiler.h>
41 #include <libpspp/string-set.h>
43 /* Currently running test. */
44 static const char *test_name;
46 /* Exit with a failure code.
47 (Place a breakpoint on this function while debugging.) */
54 /* If OK is not true, prints a message about failure on the
55 current source file and the given LINE and terminates. */
57 check_func (bool ok, int line)
61 printf ("Check failed in %s test at %s, line %d\n",
62 test_name, __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 sprintf (*s, "%d", idx);
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 contains the CNT strings in DATA, that its structure is
269 correct, and that certain operations on MAP produce the expected results. */
271 check_string_map (struct string_map *map, const int data[], size_t cnt)
275 check (string_map_is_empty (map) == (cnt == 0));
276 check (string_map_count (map) == cnt);
278 for (i = 0; i < cnt; i++)
280 struct string_map_node *node;
281 const char *key = make_key (data[i]);
282 const char *value = make_value (data[i]);
283 const char *found_value;
285 check (string_map_contains (map, key));
287 node = string_map_find_node (map, key);
288 check (node != NULL);
289 check (!strcmp (key, string_map_node_get_key (node)));
290 check (!strcmp (value, string_map_node_get_value (node)));
292 check (node == string_map_insert (map, key, "abc"));
293 check (!strcmp (value, string_map_node_get_value (node)));
295 check (node == string_map_insert_nocopy (map, xstrdup (key),
297 check (!strcmp (value, string_map_node_get_value (node)));
299 found_value = string_map_find (map, key);
300 check (found_value != NULL);
301 check (!strcmp (found_value, value));
304 check (!string_map_contains (map, "xxx"));
305 check (string_map_find (map, "z") == NULL);
306 check (string_map_find_node (map, "") == NULL);
307 check (!string_map_delete (map, "xyz"));
310 check (string_map_first (map) == NULL);
313 const struct string_map_node *node;
317 data_copy = xmemdup (data, cnt * sizeof *data);
319 for (node = string_map_first (map), i = 0; i < cnt;
320 node = string_map_next (map, node), i++)
322 const char *key = string_map_node_get_key (node);
323 const char *value = string_map_node_get_value (node);
326 for (j = 0; j < left; j++)
327 if (!strcmp (key, make_key (data_copy[j]))
328 || !strcmp (value, make_value (data_copy[j])))
330 data_copy[j] = data_copy[--left];
337 check (node == NULL);
342 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a map in the
343 order specified by INSERTIONS, then deletes them in the order specified by
344 DELETIONS, checking the map's contents for correctness after each
347 test_insert_delete (const int insertions[],
348 const int deletions[],
351 struct string_map map;
354 string_map_init (&map);
355 check_string_map (&map, NULL, 0);
356 for (i = 0; i < cnt; i++)
358 check (string_map_insert (&map, make_key (insertions[i]),
359 make_value (insertions[i])));
360 check_string_map (&map, insertions, i + 1);
362 for (i = 0; i < cnt; i++)
364 check (string_map_delete (&map, make_key (deletions[i])));
365 check_string_map (&map, deletions + i + 1, cnt - i - 1);
367 string_map_destroy (&map);
370 /* Inserts strings into a map in each possible order, then removes them in each
371 possible order, up to a specified maximum size. */
373 test_insert_any_remove_any (void)
376 const int max_elems = 5;
379 for (cnt = 0; cnt <= max_elems; cnt++)
381 int *insertions, *deletions;
382 unsigned int ins_perm_cnt;
385 insertions = xnmalloc (cnt, sizeof *insertions);
386 deletions = xnmalloc (cnt, sizeof *deletions);
387 for (i = 0; i < cnt; i++)
388 insertions[i] = i | random_value (i, basis);
390 for (ins_perm_cnt = 0;
391 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
394 unsigned int del_perm_cnt;
397 for (i = 0; i < cnt; i++)
398 deletions[i] = i | random_value (i, basis);
400 for (del_perm_cnt = 0;
401 del_perm_cnt == 0 || next_permutation (deletions, cnt);
403 test_insert_delete (insertions, deletions, cnt);
405 check (del_perm_cnt == factorial (cnt));
407 check (ins_perm_cnt == factorial (cnt));
414 /* Inserts strings into a map in each possible order, then removes them in the
415 same order, up to a specified maximum size. */
417 test_insert_any_remove_same (void)
419 const int max_elems = 7;
422 for (cnt = 0; cnt <= max_elems; cnt++)
425 unsigned int permutation_cnt;
428 values = xnmalloc (cnt, sizeof *values);
429 for (i = 0; i < cnt; i++)
430 values[i] = i | random_value (i, 1);
432 for (permutation_cnt = 0;
433 permutation_cnt == 0 || next_permutation (values, cnt);
435 test_insert_delete (values, values, cnt);
436 check (permutation_cnt == factorial (cnt));
442 /* Inserts strings into a map in each possible order, then
443 removes them in reverse order, up to a specified maximum
446 test_insert_any_remove_reverse (void)
448 const int max_elems = 7;
451 for (cnt = 0; cnt <= max_elems; cnt++)
453 int *insertions, *deletions;
454 unsigned int permutation_cnt;
457 insertions = xnmalloc (cnt, sizeof *insertions);
458 deletions = xnmalloc (cnt, sizeof *deletions);
459 for (i = 0; i < cnt; i++)
460 insertions[i] = i | random_value (i, 2);
462 for (permutation_cnt = 0;
463 permutation_cnt == 0 || next_permutation (insertions, cnt);
466 memcpy (deletions, insertions, sizeof *insertions * cnt);
467 reverse (deletions, cnt);
469 test_insert_delete (insertions, deletions, cnt);
471 check (permutation_cnt == factorial (cnt));
478 /* Inserts and removes strings in a map, in random order. */
480 test_random_sequence (void)
483 const int max_elems = 64;
484 const int max_trials = 8;
487 for (cnt = 0; cnt <= max_elems; cnt += 2)
489 int *insertions, *deletions;
493 insertions = xnmalloc (cnt, sizeof *insertions);
494 deletions = xnmalloc (cnt, sizeof *deletions);
495 for (i = 0; i < cnt; i++)
496 insertions[i] = i | random_value (i, basis);
497 for (i = 0; i < cnt; i++)
498 deletions[i] = i | random_value (i, basis);
500 for (trial = 0; trial < max_trials; trial++)
502 random_shuffle (insertions, cnt, sizeof *insertions);
503 random_shuffle (deletions, cnt, sizeof *deletions);
505 test_insert_delete (insertions, deletions, cnt);
513 /* Inserts strings into a map in ascending order, then delete in ascending
516 test_insert_ordered (void)
518 const int max_elems = 64;
520 struct string_map map;
523 string_map_init (&map);
524 values = xnmalloc (max_elems, sizeof *values);
525 for (i = 0; i < max_elems; i++)
527 values[i] = i | random_value (i, 4);
528 string_map_insert_nocopy (&map, xstrdup (make_key (values[i])),
529 xstrdup (make_value (values[i])));
530 check_string_map (&map, values, i + 1);
532 for (i = 0; i < max_elems; i++)
534 string_map_delete (&map, make_key (i));
535 check_string_map (&map, values + i + 1, max_elems - i - 1);
537 string_map_destroy (&map);
541 /* Inserts and replaces strings in a map, in random order. */
545 const int basis = 15;
546 enum { MAX_ELEMS = 16 };
547 const int max_trials = 8;
550 for (cnt = 0; cnt <= MAX_ELEMS; cnt++)
552 int insertions[MAX_ELEMS];
556 for (i = 0; i < cnt; i++)
557 insertions[i] = (i / 2) | random_value (i, basis);
559 for (trial = 0; trial < max_trials; trial++)
561 struct string_map map;
565 /* Insert with replacement in random order. */
567 string_map_init (&map);
568 random_shuffle (insertions, cnt, sizeof *insertions);
569 for (i = 0; i < cnt; i++)
571 const char *key = make_key (insertions[i]);
572 const char *value = make_value (insertions[i]);
575 for (j = 0; j < n_data; j++)
576 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
578 data[j] = insertions[i];
581 data[n_data++] = insertions[i];
585 string_map_replace (&map, key, value);
587 string_map_replace_nocopy (&map,
588 xstrdup (key), xstrdup (value));
589 check_string_map (&map, data, n_data);
592 /* Delete in original order. */
593 for (i = 0; i < cnt; i++)
595 const char *expected_value;
599 expected_value = NULL;
600 for (j = 0; j < n_data; j++)
601 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
603 expected_value = make_value (data[j]);
604 data[j] = data[--n_data];
608 value = string_map_find_and_delete (&map,
609 make_key (insertions[i]));
610 check ((value != NULL) == (expected_value != NULL));
611 check (value == NULL || !strcmp (value, expected_value));
614 assert (string_map_is_empty (&map));
616 string_map_destroy (&map);
622 make_patterned_map (struct string_map *map, unsigned int pattern, int basis,
623 int insertions[], int *np)
628 string_map_init (map);
631 for (i = 0; pattern != 0; i++)
632 if (pattern & (1u << i))
634 pattern &= pattern - 1;
635 insertions[n] = i | random_value (i, basis);
636 check (string_map_insert (map, make_key (insertions[n]),
637 make_value (insertions[n])));
640 check_string_map (map, insertions, n);
646 for_each_map (void (*cb)(struct string_map *, int data[], int n),
649 enum { MAX_ELEMS = 5 };
650 unsigned int pattern;
652 for (pattern = 0; pattern < (1u << MAX_ELEMS); pattern++)
655 struct string_map map;
658 make_patterned_map (&map, pattern, basis, data, &n);
659 (*cb) (&map, data, n);
660 string_map_destroy (&map);
665 for_each_pair_of_maps (
666 void (*cb)(struct string_map *a, int a_data[], int n_a,
667 struct string_map *b, int b_data[], int n_b),
668 int a_basis, int b_basis)
670 enum { MAX_ELEMS = 5 };
671 unsigned int a_pattern, b_pattern;
673 for (a_pattern = 0; a_pattern < (1u << MAX_ELEMS); a_pattern++)
674 for (b_pattern = 0; b_pattern < (1u << MAX_ELEMS); b_pattern++)
676 int a_data[MAX_ELEMS], b_data[MAX_ELEMS];
677 struct string_map a_map, b_map;
680 make_patterned_map (&a_map, a_pattern, a_basis, a_data, &n_a);
681 make_patterned_map (&b_map, b_pattern, b_basis, b_data, &n_b);
682 (*cb) (&a_map, a_data, n_a, &b_map, b_data, n_b);
683 string_map_destroy (&a_map);
684 string_map_destroy (&b_map);
689 clear_cb (struct string_map *map, int data[] UNUSED, int n UNUSED)
691 string_map_clear (map);
692 check_string_map (map, NULL, 0);
698 for_each_map (clear_cb, 5);
702 clone_cb (struct string_map *map, int data[], int n)
704 struct string_map clone;
706 string_map_clone (&clone, map);
707 check_string_map (&clone, data, n);
708 string_map_destroy (&clone);
714 for_each_map (clone_cb, 6);
718 node_swap_value_cb (struct string_map *map, int data[], int n)
722 for (i = 0; i < n; i++)
724 const char *value = make_value (data[i]);
725 struct string_map_node *node;
728 node = string_map_find_node (map, make_key (data[i]));
729 check (node != NULL);
730 check (!strcmp (string_map_node_get_value (node), value));
731 data[i] = (data[i] & KEY_MASK) | random_value (i, 15);
732 old_value = string_map_node_swap_value (node, make_value (data[i]));
733 check (old_value != NULL);
734 check (!strcmp (value, old_value));
740 test_node_swap_value (void)
742 for_each_map (node_swap_value_cb, 14);
746 swap_cb (struct string_map *a, int a_data[], int n_a,
747 struct string_map *b, int b_data[], int n_b)
749 string_map_swap (a, b);
750 check_string_map (a, b_data, n_b);
751 check_string_map (b, a_data, n_a);
757 for_each_pair_of_maps (swap_cb, 7, 8);
761 insert_map_cb (struct string_map *a, int a_data[], int n_a,
762 struct string_map *b, int b_data[], int n_b)
766 string_map_insert_map (a, b);
768 for (i = 0; i < n_b; i++)
770 for (j = 0; j < n_a; j++)
771 if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
773 a_data[n_a++] = b_data[i];
776 check_string_map (a, a_data, n_a);
777 check_string_map (b, b_data, n_b);
781 test_insert_map (void)
783 for_each_pair_of_maps (insert_map_cb, 91, 10);
787 replace_map_cb (struct string_map *a, int a_data[], int n_a,
788 struct string_map *b, int b_data[], int n_b)
792 string_map_replace_map (a, b);
794 for (i = 0; i < n_b; i++)
796 for (j = 0; j < n_a; j++)
797 if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
799 a_data[j] = (a_data[j] & KEY_MASK) | (b_data[i] & VALUE_MASK);
802 a_data[n_a++] = b_data[i];
805 check_string_map (a, a_data, n_a);
806 check_string_map (b, b_data, n_b);
810 test_replace_map (void)
812 for_each_pair_of_maps (replace_map_cb, 11, 12);
816 check_set (struct string_set *set, const int *data, int n_data,
824 unique = xmalloc (n_data * sizeof *unique);
825 for (i = 0; i < n_data; i++)
827 int idx = (data[i] & mask) >> shift;
830 for (j = 0; j < n_unique; j++)
831 if (unique[j] == idx)
833 unique[n_unique++] = idx;
837 check (string_set_count (set) == n_unique);
838 for (i = 0; i < n_unique; i++)
839 check (string_set_contains (set, get_string (unique[i])));
840 string_set_destroy (set);
845 get_keys_and_values_cb (struct string_map *map, int data[], int n)
847 struct string_set keys, values;
849 string_set_init (&keys);
850 string_set_init (&values);
851 string_map_get_keys (map, &keys);
852 string_map_get_values (map, &values);
853 check_set (&keys, data, n, KEY_MASK, KEY_SHIFT);
854 check_set (&values, data, n, VALUE_MASK, VALUE_SHIFT);
858 test_get_keys_and_values (void)
860 for_each_map (get_keys_and_values_cb, 13);
864 test_destroy_null (void)
866 string_map_destroy (NULL);
871 /* Runs TEST_FUNCTION and prints a message about NAME. */
873 run_test (void (*test_function) (void), const char *name)
884 run_test (test_insert_any_remove_any, "insert any order, delete any order");
885 run_test (test_insert_any_remove_same,
886 "insert any order, delete same order");
887 run_test (test_insert_any_remove_reverse,
888 "insert any order, delete reverse order");
889 run_test (test_random_sequence, "insert and delete in random sequence");
890 run_test (test_replace, "insert and replace in random sequence");
891 run_test (test_insert_ordered, "insert in ascending order");
892 run_test (test_clear, "clear");
893 run_test (test_clone, "clone");
894 run_test (test_swap, "swap");
895 run_test (test_node_swap_value, "node_swap_value");
896 run_test (test_insert_map, "insert_map");
897 run_test (test_replace_map, "replace_map");
898 run_test (test_get_keys_and_values, "get keys and values");
899 run_test (test_destroy_null, "destroying null table");