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 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_count (hmap) == cnt);
346 check (cnt <= hmap_capacity (hmap));
348 order = xmemdup (data, cnt * sizeof *data);
349 qsort (order, cnt, sizeof *order, compare_ints);
351 for (i = 0; i < cnt; i = j)
356 for (j = i + 1; j < cnt; j++)
357 if (order[i] != order[j])
361 HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (order[i]), hmap)
362 if (e->data == order[i])
365 check (count == j - i);
368 check (find_element (hmap, -1, hash) == NULL);
371 check (hmap_first (hmap) == NULL);
378 for (p = hmap_first (hmap), i = 0; i < cnt; p = hmap_next (hmap, p), i++)
380 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;
670 elements = xnmalloc (max_elems, sizeof *elements);
671 values = xnmalloc (max_elems, sizeof *values);
672 for (i = 0; i < max_elems; i++)
674 values[i] = elements[i].data = i;
675 hmap_insert (&hmap, &elements[i].node, hash (elements[i].data));
676 check_hmap (&hmap, values, i + 1, hash);
678 if (hash == identity_hash)
680 /* Check that every every hash bucket has (almost) the
681 same number of nodes in it. */
686 for (j = 0; j <= hmap.mask; j++)
689 struct hmap_node *node;
691 for (node = hmap.buckets[j]; node != NULL; node = node->next)
698 check (max - min <= 1);
701 for (i = 0; i < max_elems; i++)
703 hmap_delete (&hmap, &elements[i].node);
705 check_hmap (&hmap, values + i + 1, max_elems - i - 1, hash);
707 hmap_destroy (&hmap);
713 test_insert_ordered_random_hash (void)
715 test_insert_ordered (1024, random_hash);
719 test_insert_ordered_identity_hash (void)
721 test_insert_ordered (1024, identity_hash);
725 test_insert_ordered_constant_hash (void)
727 test_insert_ordered (128, constant_hash);
730 /* Inserts up to MAX_ELEMS elements into an HMAP, then moves the
731 nodes around in memory, using hash function HASH. */
733 test_moved (int max_elems, hash_function *hash)
735 struct element *e[2];
741 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
746 e[0] = xnmalloc (max_elems, sizeof *e[0]);
747 e[1] = xnmalloc (max_elems, sizeof *e[1]);
748 values = xnmalloc (max_elems, sizeof *values);
750 for (i = 0; i < max_elems; i++)
752 values[i] = e[cur][i].data = i;
753 hmap_insert (&hmap, &e[cur][i].node, hash (e[cur][i].data));
754 check_hmap (&hmap, values, i + 1, hash);
756 for (j = 0; j <= i; j++)
758 e[!cur][j] = e[cur][j];
759 hmap_moved (&hmap, &e[!cur][j].node, &e[cur][j].node);
760 check_hmap (&hmap, values, i + 1, hash);
764 hmap_destroy (&hmap);
771 test_moved_random_hash (void)
773 test_moved (128, random_hash);
777 test_moved_identity_hash (void)
779 test_moved (128, identity_hash);
783 test_moved_constant_hash (void)
785 test_moved (32, constant_hash);
788 /* Inserts values into an HMAP, then changes their values, using
789 hash function HASH. */
791 test_changed (hash_function *hash)
793 const int max_elems = 6;
796 for (cnt = 0; cnt <= max_elems; cnt++)
798 int *values, *changed_values;
799 struct element *elements;
800 unsigned int permutation_cnt;
803 values = xnmalloc (cnt, sizeof *values);
804 changed_values = xnmalloc (cnt, sizeof *changed_values);
805 elements = xnmalloc (cnt, sizeof *elements);
806 for (i = 0; i < cnt; i++)
809 for (permutation_cnt = 0;
810 permutation_cnt == 0 || next_permutation (values, cnt);
813 for (i = 0; i < cnt; i++)
816 for (j = 0; j <= cnt; j++)
822 /* Add to HMAP in order. */
823 for (k = 0; k < cnt; k++)
826 elements[n].data = n;
827 hmap_insert (&hmap, &elements[n].node,
828 hash (elements[n].data));
830 check_hmap (&hmap, values, cnt, hash);
832 /* Change value i to j. */
833 elements[i].data = j;
834 hmap_changed (&hmap, &elements[i].node,
835 hash (elements[i].data));
836 for (k = 0; k < cnt; k++)
837 changed_values[k] = k;
838 changed_values[i] = j;
839 check_hmap (&hmap, changed_values, cnt, hash);
841 hmap_destroy (&hmap);
845 check (permutation_cnt == factorial (cnt));
848 free (changed_values);
854 test_changed_random_hash (void)
856 test_changed (random_hash);
860 test_changed_identity_hash (void)
862 test_changed (identity_hash);
866 test_changed_constant_hash (void)
868 test_changed (constant_hash);
872 test_swap (int max_elems, hash_function *hash)
874 struct element *elements;
877 struct hmap *working, *empty;
880 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
888 elements = xnmalloc (max_elems, sizeof *elements);
889 values = xnmalloc (max_elems, sizeof *values);
890 for (i = 0; i < max_elems; i++)
893 values[i] = elements[i].data = i;
894 hmap_insert (working, &elements[i].node, hash (elements[i].data));
895 check_hmap (working, values, i + 1, hash);
896 check_hmap (empty, NULL, 0, hash);
909 test_swap_random_hash (void)
911 test_swap (128, random_hash);
915 test_destroy_null (void)
920 /* Test shrinking an empty hash table. */
922 test_shrink_empty (void)
927 hmap_reserve (&hmap, 123);
929 hmap_destroy (&hmap);
934 /* Runs TEST_FUNCTION and prints a message about NAME. */
936 run_test (void (*test_function) (void), const char *name)
947 run_test (test_insert_any_remove_any_random_hash,
948 "insert any order, delete any order (random hash)");
949 run_test (test_insert_any_remove_any_identity_hash,
950 "insert any order, delete any order (identity hash)");
951 run_test (test_insert_any_remove_any_constant_hash,
952 "insert any order, delete any order (constant hash)");
954 run_test (test_insert_any_remove_same_random_hash,
955 "insert any order, delete same order (random hash)");
956 run_test (test_insert_any_remove_same_identity_hash,
957 "insert any order, delete same order (identity hash)");
958 run_test (test_insert_any_remove_same_constant_hash,
959 "insert any order, delete same order (constant hash)");
961 run_test (test_insert_any_remove_reverse_random_hash,
962 "insert any order, delete reverse order (random hash)");
963 run_test (test_insert_any_remove_reverse_identity_hash,
964 "insert any order, delete reverse order (identity hash)");
965 run_test (test_insert_any_remove_reverse_constant_hash,
966 "insert any order, delete reverse order (constant hash)");
968 run_test (test_random_sequence_random_hash,
969 "insert and delete in random sequence (random hash)");
970 run_test (test_random_sequence_identity_hash,
971 "insert and delete in random sequence (identity hash)");
972 run_test (test_random_sequence_constant_hash,
973 "insert and delete in random sequence (constant hash)");
975 run_test (test_insert_ordered_random_hash,
976 "insert in ascending order (random hash)");
977 run_test (test_insert_ordered_identity_hash,
978 "insert in ascending order (identity hash)");
979 run_test (test_insert_ordered_constant_hash,
980 "insert in ascending order (constant hash)");
982 run_test (test_moved_random_hash,
983 "move elements around in memory (random hash)");
984 run_test (test_moved_identity_hash,
985 "move elements around in memory (identity hash)");
986 run_test (test_moved_constant_hash,
987 "move elements around in memory (constant hash)");
989 run_test (test_changed_random_hash,
990 "change key data in nodes (random hash)");
991 run_test (test_changed_identity_hash,
992 "change key data in nodes (identity hash)");
993 run_test (test_changed_constant_hash,
994 "change key data in nodes (constant hash)");
996 run_test (test_swap_random_hash, "test swapping tables");
998 run_test (test_destroy_null, "test destroying null table");
999 run_test (test_shrink_empty, "test shrinking an empty table");
1003 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
1004 /* We skipped some of the tests, so return a value that
1005 Automake will interpret as "skipped", instead of one that