1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2008 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
26 GCC 4.3 will miscompile this test program, specifically
27 test_moved(), given small changes. This is a bug in GCC
28 triggered by the test program, not by the library under test,
29 so you may safely ignore it. To avoid miscompilation, compile
30 this file with GCC 4.2 or earlier or GCC 4.4 or later.
32 Here is a minimal test program that demonstrates the same or a
33 similar bug in GCC 4.3:
57 check_list (struct list *list)
59 int i __attribute__((unused));
61 for (e = list->head; e != NULL; e = e->next)
62 if (e->data1 != e->data2)
70 struct node *elements = xmalloc (MAX_ELEMS * sizeof *elements);
71 int *values = xmalloc (MAX_ELEMS * sizeof *values);
76 for (i = 0; i < MAX_ELEMS; i++)
78 values[i] = elements[i].data2 = i;
79 elements[i].data1 = elements[i].data2;
80 elements[i].next = list.head;
81 list.head = &elements[i];
92 #include <libpspp/hmap.h>
103 #include <libpspp/compiler.h>
105 /* Currently running test. */
106 static const char *test_name;
108 /* Exit with a failure code.
109 (Place a breakpoint on this function while debugging.) */
116 /* If OK is not true, prints a message about failure on the
117 current source file and the given LINE and terminates. */
119 check_func (bool ok, int line)
123 printf ("Check failed in %s test at %s, line %d\n",
124 test_name, __FILE__, line);
129 /* Verifies that EXPR evaluates to true.
130 If not, prints a message citing the calling line number and
132 #define check(EXPR) check_func ((EXPR), __LINE__)
134 /* Prints a message about memory exhaustion and exits with a
139 printf ("virtual memory exhausted\n");
143 static void *xmalloc (size_t n) MALLOC_LIKE;
144 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
145 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
147 /* Allocates and returns N bytes of memory. */
153 void *p = malloc (n);
164 xmemdup (const void *p, size_t n)
166 void *q = xmalloc (n);
171 /* Allocates and returns N * M bytes of memory. */
173 xnmalloc (size_t n, size_t m)
175 if ((size_t) -1 / m <= n)
177 return xmalloc (n * m);
180 /* Node type and support routines. */
182 /* Test data element. */
185 struct hmap_node node; /* Embedded hash table element. */
186 int data; /* Primary value. */
189 /* Returns the `struct element' that NODE is embedded within. */
190 static struct element *
191 hmap_node_to_element (const struct hmap_node *node)
193 return HMAP_DATA (node, struct element, node);
196 /* Compares A and B and returns a strcmp-type return value. */
198 compare_ints (const void *a_, const void *b_)
203 return *a < *b ? -1 : *a > *b;
206 /* Swaps *A and *B. */
208 swap (int *a, int *b)
215 /* Reverses the order of the CNT integers starting at VALUES. */
217 reverse (int *values, size_t cnt)
223 swap (&values[i++], &values[--j]);
226 /* Arranges the CNT elements in VALUES into the lexicographically
227 next greater permutation. Returns true if successful.
228 If VALUES is already the lexicographically greatest
229 permutation of its elements (i.e. ordered from greatest to
230 smallest), arranges them into the lexicographically least
231 permutation (i.e. ordered from smallest to largest) and
234 next_permutation (int *values, size_t cnt)
242 if (values[i] < values[i + 1])
245 for (j = cnt - 1; values[i] >= values[j]; j--)
247 swap (values + i, values + j);
248 reverse (values + (i + 1), cnt - (i + 1));
253 reverse (values, cnt);
261 factorial (unsigned int n)
263 unsigned int value = 1;
269 /* Randomly shuffles the CNT elements in ARRAY, each of which is
270 SIZE bytes in size. */
272 random_shuffle (void *array_, size_t cnt, size_t size)
274 char *array = array_;
275 char *tmp = xmalloc (size);
278 for (i = 0; i < cnt; i++)
280 size_t j = rand () % (cnt - i) + i;
283 memcpy (tmp, array + j * size, size);
284 memcpy (array + j * size, array + i * size, size);
285 memcpy (array + i * size, tmp, size);
292 typedef size_t hash_function (int data);
295 identity_hash (int data)
301 constant_hash (int data UNUSED)
306 static inline uint32_t
307 md4_round (uint32_t a, uint32_t b, uint32_t c, uint32_t d,
308 uint32_t data, uint32_t n)
310 uint32_t x = a + (d ^ (b & (c ^ d))) + data;
311 return (x << n) | (x >> (32 - n));
315 random_hash (int data)
321 a = md4_round (a, b, c, d, 0, 3);
322 d = md4_round (d, a, b, c, 1, 7);
323 c = md4_round (c, d, a, b, 2, 11);
324 b = md4_round (b, c, d, a, 3, 19);
325 return a ^ b ^ c ^ d;
328 static struct hmap_node *
329 find_element (struct hmap *hmap, int data, hash_function *hash)
332 HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (data), hmap)
338 /* Checks that HMAP contains the CNT ints in DATA, that its
339 structure is correct, and that certain operations on HMAP
340 produce the expected results. */
342 check_hmap (struct hmap *hmap, const int data[], size_t cnt,
348 check (hmap_count (hmap) == cnt);
349 check (cnt <= hmap_capacity (hmap));
351 order = xmemdup (data, cnt * sizeof *data);
352 qsort (order, cnt, sizeof *order, compare_ints);
354 for (i = 0; i < cnt; i = j)
359 for (j = i + 1; j < cnt; j++)
360 if (order[i] != order[j])
364 HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (order[i]), hmap)
365 if (e->data == order[i])
368 check (count == j - i);
371 check (find_element (hmap, -1, hash) == NULL);
374 check (hmap_first (hmap) == NULL);
381 for (p = hmap_first (hmap), i = 0; i < cnt; p = hmap_next (hmap, p), i++)
383 struct element *e = hmap_node_to_element (p);
386 check (hmap_node_hash (&e->node) == hash (e->data));
387 for (j = 0; j < left; j++)
388 if (order[j] == e->data)
390 order[j] = order[--left];
403 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
404 HMAP in the order specified by INSERTIONS, then deletes them in
405 the order specified by DELETIONS, checking the HMAP's contents
406 for correctness after each operation. Uses HASH as the hash
409 test_insert_delete (const int insertions[],
410 const int deletions[],
414 struct element *elements;
418 elements = xnmalloc (cnt, sizeof *elements);
419 for (i = 0; i < cnt; i++)
420 elements[i].data = i;
423 hmap_reserve (&hmap, 1);
424 check_hmap (&hmap, NULL, 0, hash);
425 for (i = 0; i < cnt; i++)
428 hmap_insert (&hmap, &elements[insertions[i]].node, hash (insertions[i]));
429 check_hmap (&hmap, insertions, i + 1, hash);
431 /* A series of insertions should not produce a shrinkable hmap. */
432 capacity = hmap_capacity (&hmap);
434 check (capacity == hmap_capacity (&hmap));
436 for (i = 0; i < cnt; i++)
438 hmap_delete (&hmap, &elements[deletions[i]].node);
439 check_hmap (&hmap, deletions + i + 1, cnt - i - 1, hash);
441 hmap_destroy (&hmap);
446 /* Inserts values into an HMAP in each possible order, then
447 removes them in each possible order, up to a specified maximum
448 size, using hash function HASH. */
450 test_insert_any_remove_any (hash_function *hash)
452 const int max_elems = 5;
455 for (cnt = 0; cnt <= max_elems; cnt++)
457 int *insertions, *deletions;
458 unsigned int ins_perm_cnt;
461 insertions = xnmalloc (cnt, sizeof *insertions);
462 deletions = xnmalloc (cnt, sizeof *deletions);
463 for (i = 0; i < cnt; i++)
466 for (ins_perm_cnt = 0;
467 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
470 unsigned int del_perm_cnt;
473 for (i = 0; i < cnt; i++)
476 for (del_perm_cnt = 0;
477 del_perm_cnt == 0 || next_permutation (deletions, cnt);
479 test_insert_delete (insertions, deletions, cnt, hash);
481 check (del_perm_cnt == factorial (cnt));
483 check (ins_perm_cnt == factorial (cnt));
491 test_insert_any_remove_any_random_hash (void)
493 test_insert_any_remove_any (random_hash);
497 test_insert_any_remove_any_identity_hash (void)
499 test_insert_any_remove_any (identity_hash);
503 test_insert_any_remove_any_constant_hash (void)
505 test_insert_any_remove_any (constant_hash);
508 /* Inserts values into an HMAP in each possible order, then
509 removes them in the same order, up to a specified maximum
510 size, using hash function HASH. */
512 test_insert_any_remove_same (hash_function *hash)
514 const int max_elems = 7;
517 for (cnt = 0; cnt <= max_elems; cnt++)
520 unsigned int permutation_cnt;
523 values = xnmalloc (cnt, sizeof *values);
524 for (i = 0; i < cnt; i++)
527 for (permutation_cnt = 0;
528 permutation_cnt == 0 || next_permutation (values, cnt);
530 test_insert_delete (values, values, cnt, hash);
531 check (permutation_cnt == factorial (cnt));
538 test_insert_any_remove_same_random_hash (void)
540 test_insert_any_remove_same (random_hash);
544 test_insert_any_remove_same_identity_hash (void)
546 test_insert_any_remove_same (identity_hash);
550 test_insert_any_remove_same_constant_hash (void)
552 test_insert_any_remove_same (constant_hash);
555 /* Inserts values into an HMAP in each possible order, then
556 removes them in reverse order, up to a specified maximum
557 size, using hash function HASH. */
559 test_insert_any_remove_reverse (hash_function *hash)
561 const int max_elems = 7;
564 for (cnt = 0; cnt <= max_elems; cnt++)
566 int *insertions, *deletions;
567 unsigned int permutation_cnt;
570 insertions = xnmalloc (cnt, sizeof *insertions);
571 deletions = xnmalloc (cnt, sizeof *deletions);
572 for (i = 0; i < cnt; i++)
575 for (permutation_cnt = 0;
576 permutation_cnt == 0 || next_permutation (insertions, cnt);
579 memcpy (deletions, insertions, sizeof *insertions * cnt);
580 reverse (deletions, cnt);
582 test_insert_delete (insertions, deletions, cnt, hash);
584 check (permutation_cnt == factorial (cnt));
592 test_insert_any_remove_reverse_random_hash (void)
594 test_insert_any_remove_reverse (random_hash);
598 test_insert_any_remove_reverse_identity_hash (void)
600 test_insert_any_remove_reverse (identity_hash);
604 test_insert_any_remove_reverse_constant_hash (void)
606 test_insert_any_remove_reverse (constant_hash);
609 /* Inserts and removes up to MAX_ELEMS values in an hmap, in
610 random order, using hash function HASH. */
612 test_random_sequence (int max_elems, hash_function *hash)
614 const int max_trials = 8;
617 for (cnt = 0; cnt <= max_elems; cnt += 2)
619 int *insertions, *deletions;
623 insertions = xnmalloc (cnt, sizeof *insertions);
624 deletions = xnmalloc (cnt, sizeof *deletions);
625 for (i = 0; i < cnt; i++)
627 for (i = 0; i < cnt; i++)
630 for (trial = 0; trial < max_trials; trial++)
632 random_shuffle (insertions, cnt, sizeof *insertions);
633 random_shuffle (deletions, cnt, sizeof *deletions);
635 test_insert_delete (insertions, deletions, cnt, hash);
644 test_random_sequence_random_hash (void)
646 test_random_sequence (64, random_hash);
650 test_random_sequence_identity_hash (void)
652 test_random_sequence (64, identity_hash);
656 test_random_sequence_constant_hash (void)
658 test_random_sequence (32, constant_hash);
661 /* Inserts MAX_ELEMS elements into an HMAP in ascending order,
662 then delete in ascending order and shrink the hmap at each
663 step, using hash function HASH. */
665 test_insert_ordered (int max_elems, hash_function *hash)
667 struct element *elements;
673 elements = xnmalloc (max_elems, sizeof *elements);
674 values = xnmalloc (max_elems, sizeof *values);
675 for (i = 0; i < max_elems; i++)
677 values[i] = elements[i].data = i;
678 hmap_insert (&hmap, &elements[i].node, hash (elements[i].data));
679 check_hmap (&hmap, values, i + 1, hash);
681 if (hash == identity_hash)
683 /* Check that every every hash bucket has (almost) the
684 same number of nodes in it. */
689 for (j = 0; j <= hmap.mask; j++)
692 struct hmap_node *node;
694 for (node = hmap.buckets[j]; node != NULL; node = node->next)
701 check (max - min <= 1);
704 for (i = 0; i < max_elems; i++)
706 hmap_delete (&hmap, &elements[i].node);
708 check_hmap (&hmap, values + i + 1, max_elems - i - 1, hash);
710 hmap_destroy (&hmap);
716 test_insert_ordered_random_hash (void)
718 test_insert_ordered (1024, random_hash);
722 test_insert_ordered_identity_hash (void)
724 test_insert_ordered (1024, identity_hash);
728 test_insert_ordered_constant_hash (void)
730 test_insert_ordered (128, constant_hash);
733 /* Inserts up to MAX_ELEMS elements into an HMAP, then moves the
734 nodes around in memory, using hash function HASH. */
736 test_moved (int max_elems, hash_function *hash)
738 struct element *e[2];
745 e[0] = xnmalloc (max_elems, sizeof *e[0]);
746 e[1] = xnmalloc (max_elems, sizeof *e[1]);
747 values = xnmalloc (max_elems, sizeof *values);
749 for (i = 0; i < max_elems; i++)
751 values[i] = e[cur][i].data = i;
752 hmap_insert (&hmap, &e[cur][i].node, hash (e[cur][i].data));
753 check_hmap (&hmap, values, i + 1, hash);
755 for (j = 0; j <= i; j++)
757 e[!cur][j] = e[cur][j];
758 hmap_moved (&hmap, &e[!cur][j].node, &e[cur][j].node);
759 check_hmap (&hmap, values, i + 1, hash);
763 hmap_destroy (&hmap);
770 test_moved_random_hash (void)
772 test_moved (128, random_hash);
776 test_moved_identity_hash (void)
778 test_moved (128, identity_hash);
782 test_moved_constant_hash (void)
784 test_moved (32, constant_hash);
787 /* Inserts values into an HMAP, then changes their values, using
788 hash function HASH. */
790 test_changed (hash_function *hash)
792 const int max_elems = 6;
795 for (cnt = 0; cnt <= max_elems; cnt++)
797 int *values, *changed_values;
798 struct element *elements;
799 unsigned int permutation_cnt;
802 values = xnmalloc (cnt, sizeof *values);
803 changed_values = xnmalloc (cnt, sizeof *changed_values);
804 elements = xnmalloc (cnt, sizeof *elements);
805 for (i = 0; i < cnt; i++)
808 for (permutation_cnt = 0;
809 permutation_cnt == 0 || next_permutation (values, cnt);
812 for (i = 0; i < cnt; i++)
815 for (j = 0; j <= cnt; j++)
821 /* Add to HMAP in order. */
822 for (k = 0; k < cnt; k++)
825 elements[n].data = n;
826 hmap_insert (&hmap, &elements[n].node,
827 hash (elements[n].data));
829 check_hmap (&hmap, values, cnt, hash);
831 /* Change value i to j. */
832 elements[i].data = j;
833 hmap_changed (&hmap, &elements[i].node,
834 hash (elements[i].data));
835 for (k = 0; k < cnt; k++)
836 changed_values[k] = k;
837 changed_values[i] = j;
838 check_hmap (&hmap, changed_values, cnt, hash);
840 hmap_destroy (&hmap);
844 check (permutation_cnt == factorial (cnt));
847 free (changed_values);
853 test_changed_random_hash (void)
855 test_changed (random_hash);
859 test_changed_identity_hash (void)
861 test_changed (identity_hash);
865 test_changed_constant_hash (void)
867 test_changed (constant_hash);
871 test_swap (int max_elems, hash_function *hash)
873 struct element *elements;
876 struct hmap *working, *empty;
883 elements = xnmalloc (max_elems, sizeof *elements);
884 values = xnmalloc (max_elems, sizeof *values);
885 for (i = 0; i < max_elems; i++)
888 values[i] = elements[i].data = i;
889 hmap_insert (working, &elements[i].node, hash (elements[i].data));
890 check_hmap (working, values, i + 1, hash);
891 check_hmap (empty, NULL, 0, hash);
904 test_swap_random_hash (void)
906 test_swap (128, random_hash);
910 test_destroy_null (void)
915 /* Test shrinking an empty hash table. */
917 test_shrink_empty (void)
922 hmap_reserve (&hmap, 123);
924 hmap_destroy (&hmap);
929 /* Runs TEST_FUNCTION and prints a message about NAME. */
931 run_test (void (*test_function) (void), const char *name)
942 run_test (test_insert_any_remove_any_random_hash,
943 "insert any order, delete any order (random hash)");
944 run_test (test_insert_any_remove_any_identity_hash,
945 "insert any order, delete any order (identity hash)");
946 run_test (test_insert_any_remove_any_constant_hash,
947 "insert any order, delete any order (constant hash)");
949 run_test (test_insert_any_remove_same_random_hash,
950 "insert any order, delete same order (random hash)");
951 run_test (test_insert_any_remove_same_identity_hash,
952 "insert any order, delete same order (identity hash)");
953 run_test (test_insert_any_remove_same_constant_hash,
954 "insert any order, delete same order (constant hash)");
956 run_test (test_insert_any_remove_reverse_random_hash,
957 "insert any order, delete reverse order (random hash)");
958 run_test (test_insert_any_remove_reverse_identity_hash,
959 "insert any order, delete reverse order (identity hash)");
960 run_test (test_insert_any_remove_reverse_constant_hash,
961 "insert any order, delete reverse order (constant hash)");
963 run_test (test_random_sequence_random_hash,
964 "insert and delete in random sequence (random hash)");
965 run_test (test_random_sequence_identity_hash,
966 "insert and delete in random sequence (identity hash)");
967 run_test (test_random_sequence_constant_hash,
968 "insert and delete in random sequence (constant hash)");
970 run_test (test_insert_ordered_random_hash,
971 "insert in ascending order (random hash)");
972 run_test (test_insert_ordered_identity_hash,
973 "insert in ascending order (identity hash)");
974 run_test (test_insert_ordered_constant_hash,
975 "insert in ascending order (constant hash)");
977 run_test (test_moved_random_hash,
978 "move elements around in memory (random hash)");
979 run_test (test_moved_identity_hash,
980 "move elements around in memory (identity hash)");
981 run_test (test_moved_constant_hash,
982 "move elements around in memory (constant hash)");
984 run_test (test_changed_random_hash,
985 "change key data in nodes (random hash)");
986 run_test (test_changed_identity_hash,
987 "change key data in nodes (identity hash)");
988 run_test (test_changed_constant_hash,
989 "change key data in nodes (constant hash)");
991 run_test (test_swap_random_hash, "test swapping tables");
993 run_test (test_destroy_null, "test destroying null table");
994 run_test (test_shrink_empty, "test shrinking an empty table");