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 hmap_* routines defined in
18 hmap.c. This test program aims to be as comprehensive as
19 possible. "gcov -a -b" should report 100% coverage of lines,
20 blocks and branches in hmap.c (when compiled with -DNDEBUG).
21 "valgrind --leak-check=yes --show-reachable=yes" should give a
24 /* GCC 4.3 miscompiles some of the tests below, so we do not run
25 these tests on GCC 4.3. This is a bug in GCC 4.3 triggered by
26 the test program, not a bug in the library under test. GCC
27 4.2 or earlier and GCC 4.4 or later do not have this bug.
29 Here is a minimal test program that demonstrates the same or a
30 similar bug in GCC 4.3:
54 check_list (struct list *list)
56 int i __attribute__((unused));
58 for (e = list->head; e != NULL; e = e->next)
59 if (e->data1 != e->data2)
67 struct node *elements = xmalloc (MAX_ELEMS * sizeof *elements);
68 int *values = xmalloc (MAX_ELEMS * sizeof *values);
73 for (i = 0; i < MAX_ELEMS; i++)
75 values[i] = elements[i].data2 = i;
76 elements[i].data1 = elements[i].data2;
77 elements[i].next = list.head;
78 list.head = &elements[i];
89 #include <libpspp/hmap.h>
100 #include <libpspp/compiler.h>
102 /* Currently running test. */
103 static const char *test_name;
105 /* Exit with a failure code.
106 (Place a breakpoint on this function while debugging.) */
113 /* If OK is not true, prints a message about failure on the
114 current source file and the given LINE and terminates. */
116 check_func (bool ok, int line)
120 printf ("Check failed in %s test at %s, line %d\n",
121 test_name, __FILE__, line);
126 /* Verifies that EXPR evaluates to true.
127 If not, prints a message citing the calling line number and
129 #define check(EXPR) check_func ((EXPR), __LINE__)
131 /* Prints a message about memory exhaustion and exits with a
136 printf ("virtual memory exhausted\n");
140 static void *xmalloc (size_t n) MALLOC_LIKE;
141 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
142 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
144 /* Allocates and returns N bytes of memory. */
150 void *p = malloc (n);
161 xmemdup (const void *p, size_t n)
163 void *q = xmalloc (n);
168 /* Allocates and returns N * M bytes of memory. */
170 xnmalloc (size_t n, size_t m)
172 if ((size_t) -1 / m <= n)
174 return xmalloc (n * m);
177 /* Node type and support routines. */
179 /* Test data element. */
182 struct hmap_node node; /* Embedded hash table element. */
183 int data; /* Primary value. */
186 /* Returns the `struct element' that NODE is embedded within. */
187 static struct element *
188 hmap_node_to_element (const struct hmap_node *node)
190 return HMAP_DATA (node, struct element, node);
193 /* Compares A and B and returns a strcmp-type return value. */
195 compare_ints (const void *a_, const void *b_)
200 return *a < *b ? -1 : *a > *b;
203 /* Swaps *A and *B. */
205 swap (int *a, int *b)
212 /* Reverses the order of the CNT integers starting at VALUES. */
214 reverse (int *values, size_t cnt)
220 swap (&values[i++], &values[--j]);
223 /* Arranges the CNT elements in VALUES into the lexicographically
224 next greater permutation. Returns true if successful.
225 If VALUES is already the lexicographically greatest
226 permutation of its elements (i.e. ordered from greatest to
227 smallest), arranges them into the lexicographically least
228 permutation (i.e. ordered from smallest to largest) and
231 next_permutation (int *values, size_t cnt)
239 if (values[i] < values[i + 1])
242 for (j = cnt - 1; values[i] >= values[j]; j--)
244 swap (values + i, values + j);
245 reverse (values + (i + 1), cnt - (i + 1));
250 reverse (values, cnt);
258 factorial (unsigned int n)
260 unsigned int value = 1;
266 /* Randomly shuffles the CNT elements in ARRAY, each of which is
267 SIZE bytes in size. */
269 random_shuffle (void *array_, size_t cnt, size_t size)
271 char *array = array_;
272 char *tmp = xmalloc (size);
275 for (i = 0; i < cnt; i++)
277 size_t j = rand () % (cnt - i) + i;
280 memcpy (tmp, array + j * size, size);
281 memcpy (array + j * size, array + i * size, size);
282 memcpy (array + i * size, tmp, size);
289 typedef size_t hash_function (int data);
292 identity_hash (int data)
298 constant_hash (int data UNUSED)
303 static inline uint32_t
304 md4_round (uint32_t a, uint32_t b, uint32_t c, uint32_t d,
305 uint32_t data, uint32_t n)
307 uint32_t x = a + (d ^ (b & (c ^ d))) + data;
308 return (x << n) | (x >> (32 - n));
312 random_hash (int data)
318 a = md4_round (a, b, c, d, 0, 3);
319 d = md4_round (d, a, b, c, 1, 7);
320 c = md4_round (c, d, a, b, 2, 11);
321 b = md4_round (b, c, d, a, 3, 19);
322 return a ^ b ^ c ^ d;
325 static struct hmap_node *
326 find_element (struct hmap *hmap, int data, hash_function *hash)
329 HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (data), hmap)
335 /* Checks that HMAP contains the CNT ints in DATA, that its
336 structure is correct, and that certain operations on HMAP
337 produce the expected results. */
339 check_hmap (struct hmap *hmap, const int data[], size_t cnt,
345 check (hmap_is_empty (hmap) == (cnt == 0));
346 check (hmap_count (hmap) == cnt);
347 check (cnt <= hmap_capacity (hmap));
349 order = xmemdup (data, cnt * sizeof *data);
350 qsort (order, cnt, sizeof *order, compare_ints);
352 for (i = 0; i < cnt; i = j)
357 for (j = i + 1; j < cnt; j++)
358 if (order[i] != order[j])
362 HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (order[i]), hmap)
363 if (e->data == order[i])
366 check (count == j - i);
369 check (find_element (hmap, -1, hash) == NULL);
372 check (hmap_first (hmap) == NULL);
379 for (p = hmap_first (hmap), i = 0; i < cnt; p = hmap_next (hmap, p), i++)
381 struct element *e = hmap_node_to_element (p);
383 check (hmap_node_hash (&e->node) == hash (e->data));
384 for (j = 0; j < left; j++)
385 if (order[j] == e->data)
387 order[j] = order[--left];
400 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
401 HMAP in the order specified by INSERTIONS, then deletes them in
402 the order specified by DELETIONS, checking the HMAP's contents
403 for correctness after each operation. Uses HASH as the hash
406 test_insert_delete (const int insertions[],
407 const int deletions[],
411 struct element *elements;
415 elements = xnmalloc (cnt, sizeof *elements);
416 for (i = 0; i < cnt; i++)
417 elements[i].data = i;
420 hmap_reserve (&hmap, 1);
421 check_hmap (&hmap, NULL, 0, hash);
422 for (i = 0; i < cnt; i++)
425 hmap_insert (&hmap, &elements[insertions[i]].node, hash (insertions[i]));
426 check_hmap (&hmap, insertions, i + 1, hash);
428 /* A series of insertions should not produce a shrinkable hmap. */
429 capacity = hmap_capacity (&hmap);
431 check (capacity == hmap_capacity (&hmap));
433 for (i = 0; i < cnt; i++)
435 hmap_delete (&hmap, &elements[deletions[i]].node);
436 check_hmap (&hmap, deletions + i + 1, cnt - i - 1, hash);
438 hmap_destroy (&hmap);
443 /* Inserts values into an HMAP in each possible order, then
444 removes them in each possible order, up to a specified maximum
445 size, using hash function HASH. */
447 test_insert_any_remove_any (hash_function *hash)
449 const int max_elems = 5;
452 for (cnt = 0; cnt <= max_elems; cnt++)
454 int *insertions, *deletions;
455 unsigned int ins_perm_cnt;
458 insertions = xnmalloc (cnt, sizeof *insertions);
459 deletions = xnmalloc (cnt, sizeof *deletions);
460 for (i = 0; i < cnt; i++)
463 for (ins_perm_cnt = 0;
464 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
467 unsigned int del_perm_cnt;
470 for (i = 0; i < cnt; i++)
473 for (del_perm_cnt = 0;
474 del_perm_cnt == 0 || next_permutation (deletions, cnt);
476 test_insert_delete (insertions, deletions, cnt, hash);
478 check (del_perm_cnt == factorial (cnt));
480 check (ins_perm_cnt == factorial (cnt));
488 test_insert_any_remove_any_random_hash (void)
490 test_insert_any_remove_any (random_hash);
494 test_insert_any_remove_any_identity_hash (void)
496 test_insert_any_remove_any (identity_hash);
500 test_insert_any_remove_any_constant_hash (void)
502 test_insert_any_remove_any (constant_hash);
505 /* Inserts values into an HMAP in each possible order, then
506 removes them in the same order, up to a specified maximum
507 size, using hash function HASH. */
509 test_insert_any_remove_same (hash_function *hash)
511 const int max_elems = 7;
514 for (cnt = 0; cnt <= max_elems; cnt++)
517 unsigned int permutation_cnt;
520 values = xnmalloc (cnt, sizeof *values);
521 for (i = 0; i < cnt; i++)
524 for (permutation_cnt = 0;
525 permutation_cnt == 0 || next_permutation (values, cnt);
527 test_insert_delete (values, values, cnt, hash);
528 check (permutation_cnt == factorial (cnt));
535 test_insert_any_remove_same_random_hash (void)
537 test_insert_any_remove_same (random_hash);
541 test_insert_any_remove_same_identity_hash (void)
543 test_insert_any_remove_same (identity_hash);
547 test_insert_any_remove_same_constant_hash (void)
549 test_insert_any_remove_same (constant_hash);
552 /* Inserts values into an HMAP in each possible order, then
553 removes them in reverse order, up to a specified maximum
554 size, using hash function HASH. */
556 test_insert_any_remove_reverse (hash_function *hash)
558 const int max_elems = 7;
561 for (cnt = 0; cnt <= max_elems; cnt++)
563 int *insertions, *deletions;
564 unsigned int permutation_cnt;
567 insertions = xnmalloc (cnt, sizeof *insertions);
568 deletions = xnmalloc (cnt, sizeof *deletions);
569 for (i = 0; i < cnt; i++)
572 for (permutation_cnt = 0;
573 permutation_cnt == 0 || next_permutation (insertions, cnt);
576 memcpy (deletions, insertions, sizeof *insertions * cnt);
577 reverse (deletions, cnt);
579 test_insert_delete (insertions, deletions, cnt, hash);
581 check (permutation_cnt == factorial (cnt));
589 test_insert_any_remove_reverse_random_hash (void)
591 test_insert_any_remove_reverse (random_hash);
595 test_insert_any_remove_reverse_identity_hash (void)
597 test_insert_any_remove_reverse (identity_hash);
601 test_insert_any_remove_reverse_constant_hash (void)
603 test_insert_any_remove_reverse (constant_hash);
606 /* Inserts and removes up to MAX_ELEMS values in an hmap, in
607 random order, using hash function HASH. */
609 test_random_sequence (int max_elems, hash_function *hash)
611 const int max_trials = 8;
614 for (cnt = 0; cnt <= max_elems; cnt += 2)
616 int *insertions, *deletions;
620 insertions = xnmalloc (cnt, sizeof *insertions);
621 deletions = xnmalloc (cnt, sizeof *deletions);
622 for (i = 0; i < cnt; i++)
624 for (i = 0; i < cnt; i++)
627 for (trial = 0; trial < max_trials; trial++)
629 random_shuffle (insertions, cnt, sizeof *insertions);
630 random_shuffle (deletions, cnt, sizeof *deletions);
632 test_insert_delete (insertions, deletions, cnt, hash);
641 test_random_sequence_random_hash (void)
643 test_random_sequence (64, random_hash);
647 test_random_sequence_identity_hash (void)
649 test_random_sequence (64, identity_hash);
653 test_random_sequence_constant_hash (void)
655 test_random_sequence (32, constant_hash);
658 /* Inserts MAX_ELEMS elements into an HMAP in ascending order,
659 then delete in ascending order and shrink the hmap at each
660 step, using hash function HASH. */
662 test_insert_ordered (int max_elems, hash_function *hash)
664 struct element *elements;
669 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
674 elements = xnmalloc (max_elems, sizeof *elements);
675 values = xnmalloc (max_elems, sizeof *values);
676 for (i = 0; i < max_elems; i++)
678 values[i] = elements[i].data = i;
679 hmap_insert (&hmap, &elements[i].node, hash (elements[i].data));
680 check_hmap (&hmap, values, i + 1, hash);
682 if (hash == identity_hash)
684 /* Check that every every hash bucket has (almost) the
685 same number of nodes in it. */
690 for (j = 0; j <= hmap.mask; j++)
693 struct hmap_node *node;
695 for (node = hmap.buckets[j]; node != NULL; node = node->next)
702 check (max - min <= 1);
705 for (i = 0; i < max_elems; i++)
707 hmap_delete (&hmap, &elements[i].node);
709 check_hmap (&hmap, values + i + 1, max_elems - i - 1, hash);
711 hmap_destroy (&hmap);
717 test_insert_ordered_random_hash (void)
719 test_insert_ordered (1024, random_hash);
723 test_insert_ordered_identity_hash (void)
725 test_insert_ordered (1024, identity_hash);
729 test_insert_ordered_constant_hash (void)
731 test_insert_ordered (128, constant_hash);
734 /* Inserts up to MAX_ELEMS elements into an HMAP, then moves the
735 nodes around in memory, using hash function HASH. */
737 test_moved (int max_elems, hash_function *hash)
739 struct element *e[2];
745 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
750 e[0] = xnmalloc (max_elems, sizeof *e[0]);
751 e[1] = xnmalloc (max_elems, sizeof *e[1]);
752 values = xnmalloc (max_elems, sizeof *values);
754 for (i = 0; i < max_elems; i++)
756 values[i] = e[cur][i].data = i;
757 hmap_insert (&hmap, &e[cur][i].node, hash (e[cur][i].data));
758 check_hmap (&hmap, values, i + 1, hash);
760 for (j = 0; j <= i; j++)
762 e[!cur][j] = e[cur][j];
763 hmap_moved (&hmap, &e[!cur][j].node, &e[cur][j].node);
764 check_hmap (&hmap, values, i + 1, hash);
768 hmap_destroy (&hmap);
775 test_moved_random_hash (void)
777 test_moved (128, random_hash);
781 test_moved_identity_hash (void)
783 test_moved (128, identity_hash);
787 test_moved_constant_hash (void)
789 test_moved (32, constant_hash);
792 /* Inserts values into an HMAP, then changes their values, using
793 hash function HASH. */
795 test_changed (hash_function *hash)
797 const int max_elems = 6;
800 for (cnt = 0; cnt <= max_elems; cnt++)
802 int *values, *changed_values;
803 struct element *elements;
804 unsigned int permutation_cnt;
807 values = xnmalloc (cnt, sizeof *values);
808 changed_values = xnmalloc (cnt, sizeof *changed_values);
809 elements = xnmalloc (cnt, sizeof *elements);
810 for (i = 0; i < cnt; i++)
813 for (permutation_cnt = 0;
814 permutation_cnt == 0 || next_permutation (values, cnt);
817 for (i = 0; i < cnt; i++)
820 for (j = 0; j <= cnt; j++)
826 /* Add to HMAP in order. */
827 for (k = 0; k < cnt; k++)
830 elements[n].data = n;
831 hmap_insert (&hmap, &elements[n].node,
832 hash (elements[n].data));
834 check_hmap (&hmap, values, cnt, hash);
836 /* Change value i to j. */
837 elements[i].data = j;
838 hmap_changed (&hmap, &elements[i].node,
839 hash (elements[i].data));
840 for (k = 0; k < cnt; k++)
841 changed_values[k] = k;
842 changed_values[i] = j;
843 check_hmap (&hmap, changed_values, cnt, hash);
845 hmap_destroy (&hmap);
849 check (permutation_cnt == factorial (cnt));
852 free (changed_values);
858 test_changed_random_hash (void)
860 test_changed (random_hash);
864 test_changed_identity_hash (void)
866 test_changed (identity_hash);
870 test_changed_constant_hash (void)
872 test_changed (constant_hash);
876 test_swap (int max_elems, hash_function *hash)
878 struct element *elements;
881 struct hmap *working, *empty;
884 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
892 elements = xnmalloc (max_elems, sizeof *elements);
893 values = xnmalloc (max_elems, sizeof *values);
894 for (i = 0; i < max_elems; i++)
897 values[i] = elements[i].data = i;
898 hmap_insert (working, &elements[i].node, hash (elements[i].data));
899 check_hmap (working, values, i + 1, hash);
900 check_hmap (empty, NULL, 0, hash);
913 test_swap_random_hash (void)
915 test_swap (128, random_hash);
918 /* Inserts elements into an hmap in ascending order, then clears the hash table
919 using hmap_clear(). */
923 const int max_elems = 128;
924 struct element *elements;
929 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
933 elements = xnmalloc (max_elems, sizeof *elements);
934 values = xnmalloc (max_elems, sizeof *values);
936 for (cnt = 0; cnt <= max_elems; cnt++)
941 for (i = 0; i < cnt; i++)
943 values[i] = elements[i].data = i;
944 hmap_insert (&hmap, &elements[i].node,
945 random_hash (elements[i].data));
946 check_hmap (&hmap, values, i + 1, random_hash);
949 check_hmap (&hmap, NULL, 0, random_hash);
950 hmap_destroy (&hmap);
958 test_destroy_null (void)
963 /* Test shrinking an empty hash table. */
965 test_shrink_empty (void)
970 hmap_reserve (&hmap, 123);
972 hmap_destroy (&hmap);
977 /* Runs TEST_FUNCTION and prints a message about NAME. */
979 run_test (void (*test_function) (void), const char *name)
990 run_test (test_insert_any_remove_any_random_hash,
991 "insert any order, delete any order (random hash)");
992 run_test (test_insert_any_remove_any_identity_hash,
993 "insert any order, delete any order (identity hash)");
994 run_test (test_insert_any_remove_any_constant_hash,
995 "insert any order, delete any order (constant hash)");
997 run_test (test_insert_any_remove_same_random_hash,
998 "insert any order, delete same order (random hash)");
999 run_test (test_insert_any_remove_same_identity_hash,
1000 "insert any order, delete same order (identity hash)");
1001 run_test (test_insert_any_remove_same_constant_hash,
1002 "insert any order, delete same order (constant hash)");
1004 run_test (test_insert_any_remove_reverse_random_hash,
1005 "insert any order, delete reverse order (random hash)");
1006 run_test (test_insert_any_remove_reverse_identity_hash,
1007 "insert any order, delete reverse order (identity hash)");
1008 run_test (test_insert_any_remove_reverse_constant_hash,
1009 "insert any order, delete reverse order (constant hash)");
1011 run_test (test_random_sequence_random_hash,
1012 "insert and delete in random sequence (random hash)");
1013 run_test (test_random_sequence_identity_hash,
1014 "insert and delete in random sequence (identity hash)");
1015 run_test (test_random_sequence_constant_hash,
1016 "insert and delete in random sequence (constant hash)");
1018 run_test (test_insert_ordered_random_hash,
1019 "insert in ascending order (random hash)");
1020 run_test (test_insert_ordered_identity_hash,
1021 "insert in ascending order (identity hash)");
1022 run_test (test_insert_ordered_constant_hash,
1023 "insert in ascending order (constant hash)");
1025 run_test (test_moved_random_hash,
1026 "move elements around in memory (random hash)");
1027 run_test (test_moved_identity_hash,
1028 "move elements around in memory (identity hash)");
1029 run_test (test_moved_constant_hash,
1030 "move elements around in memory (constant hash)");
1032 run_test (test_changed_random_hash,
1033 "change key data in nodes (random hash)");
1034 run_test (test_changed_identity_hash,
1035 "change key data in nodes (identity hash)");
1036 run_test (test_changed_constant_hash,
1037 "change key data in nodes (constant hash)");
1039 run_test (test_swap_random_hash, "test swapping tables");
1041 run_test (test_clear, "test clearing hash table");
1043 run_test (test_destroy_null, "test destroying null table");
1044 run_test (test_shrink_empty, "test shrinking an empty table");
1048 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
1049 /* We skipped some of the tests, so return a value that
1050 Automake will interpret as "skipped", instead of one that