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 hmapx_* routines defined in
18 hmapx.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 hmapx.c (when compiled with -DNDEBUG).
21 "valgrind --leak-check=yes --show-reachable=yes" should give a
28 #include <libpspp/hmapx.h>
39 #include <libpspp/compiler.h>
41 /* Currently running test. */
42 static const char *test_name;
44 /* If OK is not true, prints a message about failure on the
45 current source file and the given LINE and terminates. */
47 check_func (bool ok, int line)
51 printf ("Check failed in %s test at %s, line %d\n",
52 test_name, __FILE__, line);
57 /* Verifies that EXPR evaluates to true.
58 If not, prints a message citing the calling line number and
60 #define check(EXPR) check_func ((EXPR), __LINE__)
62 /* Prints a message about memory exhaustion and exits with a
67 printf ("virtual memory exhausted\n");
71 /* Allocates and returns N bytes of memory. */
88 xmemdup (const void *p, size_t n)
90 void *q = xmalloc (n);
95 /* Allocates and returns N * M bytes of memory. */
97 xnmalloc (size_t n, size_t m)
99 if ((size_t) -1 / m <= n)
101 return xmalloc (n * m);
104 /* Node type and support routines. */
106 /* Test data element. */
109 int data; /* Primary value. */
112 /* Compares A and B and returns a strcmp-type return value. */
114 compare_ints (const void *a_, const void *b_)
119 return *a < *b ? -1 : *a > *b;
122 /* Swaps *A and *B. */
124 swap (int *a, int *b)
131 /* Reverses the order of the CNT integers starting at VALUES. */
133 reverse (int *values, size_t cnt)
139 swap (&values[i++], &values[--j]);
142 /* Arranges the CNT elements in VALUES into the lexicographically
143 next greater permutation. Returns true if successful.
144 If VALUES is already the lexicographically greatest
145 permutation of its elements (i.e. ordered from greatest to
146 smallest), arranges them into the lexicographically least
147 permutation (i.e. ordered from smallest to largest) and
150 next_permutation (int *values, size_t cnt)
158 if (values[i] < values[i + 1])
161 for (j = cnt - 1; values[i] >= values[j]; j--)
163 swap (values + i, values + j);
164 reverse (values + (i + 1), cnt - (i + 1));
169 reverse (values, cnt);
177 factorial (unsigned int n)
179 unsigned int value = 1;
185 /* Randomly shuffles the CNT elements in ARRAY, each of which is
186 SIZE bytes in size. */
188 random_shuffle (void *array_, size_t cnt, size_t size)
190 char *array = array_;
191 char *tmp = xmalloc (size);
194 for (i = 0; i < cnt; i++)
196 size_t j = rand () % (cnt - i) + i;
199 memcpy (tmp, array + j * size, size);
200 memcpy (array + j * size, array + i * size, size);
201 memcpy (array + i * size, tmp, size);
208 typedef size_t hash_function (int data);
211 identity_hash (int data)
217 constant_hash (int data UNUSED)
222 static inline uint32_t
223 md4_round (uint32_t a, uint32_t b, uint32_t c, uint32_t d,
224 uint32_t data, uint32_t n)
226 uint32_t x = a + (d ^ (b & (c ^ d))) + data;
227 return (x << n) | (x >> (32 - n));
231 random_hash (int data)
237 a = md4_round (a, b, c, d, 0, 3);
238 d = md4_round (d, a, b, c, 1, 7);
239 c = md4_round (c, d, a, b, 2, 11);
240 b = md4_round (b, c, d, a, 3, 19);
241 return a ^ b ^ c ^ d;
244 static struct hmapx_node *
245 find_element (struct hmapx *hmapx, int data, hash_function *hash)
247 struct hmapx_node *node;
249 HMAPX_FOR_EACH_WITH_HASH (e, node, hash (data), hmapx)
255 /* Checks that HMAPX contains the CNT ints in DATA, that its
256 structure is correct, and that certain operations on HMAPX
257 produce the expected results. */
259 check_hmapx (struct hmapx *hmapx, const int data[], size_t cnt,
265 check (hmapx_is_empty (hmapx) == (cnt == 0));
266 check (hmapx_count (hmapx) == cnt);
267 check (cnt <= hmapx_capacity (hmapx));
269 order = xmemdup (data, cnt * sizeof *data);
270 qsort (order, cnt, sizeof *order, compare_ints);
272 for (i = 0; i < cnt; i = j)
274 struct hmapx_node *node;
278 for (j = i + 1; j < cnt; j++)
279 if (order[i] != order[j])
283 HMAPX_FOR_EACH_WITH_HASH (e, node, hash (order[i]), hmapx)
284 if (e->data == order[i])
287 check (count == j - i);
290 check (find_element (hmapx, -1, hash) == NULL);
293 check (hmapx_first (hmapx) == NULL);
296 struct hmapx_node *p;
300 for (p = hmapx_first (hmapx), i = 0; i < cnt;
301 p = hmapx_next (hmapx, p), i++)
303 struct element *e = hmapx_node_data (p);
306 check (hmapx_node_hash (p) == hash (e->data));
307 for (j = 0; j < left; j++)
308 if (order[j] == e->data)
310 order[j] = order[--left];
323 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
324 HMAPX in the order specified by INSERTIONS, then deletes them in
325 the order specified by DELETIONS, checking the HMAPX's contents
326 for correctness after each operation. Uses HASH as the hash
329 test_insert_delete (const int insertions[],
330 const int deletions[],
335 struct element *elements;
336 struct hmapx_node **nodes;
340 elements = xnmalloc (cnt, sizeof *elements);
341 nodes = xnmalloc (cnt, sizeof *nodes);
342 for (i = 0; i < cnt; i++)
343 elements[i].data = i;
346 hmapx_reserve (&hmapx, reserve);
347 check_hmapx (&hmapx, NULL, 0, hash);
348 for (i = 0; i < cnt; i++)
350 struct hmapx_node *(*insert) (struct hmapx *, void *, size_t hash);
353 /* Insert the node. Use hmapx_insert_fast if we have not
354 yet exceeded the reserve. */
355 insert = i < reserve ? hmapx_insert_fast : hmapx_insert;
356 nodes[insertions[i]] = insert (&hmapx, &elements[insertions[i]],
357 hash (insertions[i]));
358 check_hmapx (&hmapx, insertions, i + 1, hash);
360 /* A series of insertions should not produce a shrinkable hmapx. */
363 capacity = hmapx_capacity (&hmapx);
364 hmapx_shrink (&hmapx);
365 check (capacity == hmapx_capacity (&hmapx));
368 for (i = 0; i < cnt; i++)
370 hmapx_delete (&hmapx, nodes[deletions[i]]);
371 check_hmapx (&hmapx, deletions + i + 1, cnt - i - 1, hash);
373 hmapx_destroy (&hmapx);
379 /* Inserts values into an HMAPX in each possible order, then
380 removes them in each possible order, up to a specified maximum
381 size, using hash function HASH. */
383 test_insert_any_remove_any (hash_function *hash)
385 const int max_elems = 5;
388 for (cnt = 0; cnt <= max_elems; cnt++)
390 int *insertions, *deletions;
391 unsigned int ins_perm_cnt;
394 insertions = xnmalloc (cnt, sizeof *insertions);
395 deletions = xnmalloc (cnt, sizeof *deletions);
396 for (i = 0; i < cnt; i++)
399 for (ins_perm_cnt = 0;
400 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
403 unsigned int del_perm_cnt;
406 for (i = 0; i < cnt; i++)
409 for (del_perm_cnt = 0;
410 del_perm_cnt == 0 || next_permutation (deletions, cnt);
412 test_insert_delete (insertions, deletions, cnt, hash, 1);
414 check (del_perm_cnt == factorial (cnt));
416 check (ins_perm_cnt == factorial (cnt));
424 test_insert_any_remove_any_random_hash (void)
426 test_insert_any_remove_any (random_hash);
430 test_insert_any_remove_any_identity_hash (void)
432 test_insert_any_remove_any (identity_hash);
436 test_insert_any_remove_any_constant_hash (void)
438 test_insert_any_remove_any (constant_hash);
441 /* Inserts values into an HMAPX in each possible order, then
442 removes them in the same order, up to a specified maximum
443 size, using hash function HASH. */
445 test_insert_any_remove_same (hash_function *hash)
447 const int max_elems = 7;
450 for (cnt = 0; cnt <= max_elems; cnt++)
453 unsigned int permutation_cnt;
456 values = xnmalloc (cnt, sizeof *values);
457 for (i = 0; i < cnt; i++)
460 for (permutation_cnt = 0;
461 permutation_cnt == 0 || next_permutation (values, cnt);
463 test_insert_delete (values, values, cnt, hash, cnt / 2);
464 check (permutation_cnt == factorial (cnt));
471 test_insert_any_remove_same_random_hash (void)
473 test_insert_any_remove_same (random_hash);
477 test_insert_any_remove_same_identity_hash (void)
479 test_insert_any_remove_same (identity_hash);
483 test_insert_any_remove_same_constant_hash (void)
485 test_insert_any_remove_same (constant_hash);
488 /* Inserts values into an HMAPX in each possible order, then
489 removes them in reverse order, up to a specified maximum
490 size, using hash function HASH. */
492 test_insert_any_remove_reverse (hash_function *hash)
494 const int max_elems = 7;
497 for (cnt = 0; cnt <= max_elems; cnt++)
499 int *insertions, *deletions;
500 unsigned int permutation_cnt;
503 insertions = xnmalloc (cnt, sizeof *insertions);
504 deletions = xnmalloc (cnt, sizeof *deletions);
505 for (i = 0; i < cnt; i++)
508 for (permutation_cnt = 0;
509 permutation_cnt == 0 || next_permutation (insertions, cnt);
512 memcpy (deletions, insertions, sizeof *insertions * cnt);
513 reverse (deletions, cnt);
515 test_insert_delete (insertions, deletions, cnt, hash, cnt);
517 check (permutation_cnt == factorial (cnt));
525 test_insert_any_remove_reverse_random_hash (void)
527 test_insert_any_remove_reverse (random_hash);
531 test_insert_any_remove_reverse_identity_hash (void)
533 test_insert_any_remove_reverse (identity_hash);
537 test_insert_any_remove_reverse_constant_hash (void)
539 test_insert_any_remove_reverse (constant_hash);
542 /* Inserts and removes up to MAX_ELEMS values in an hmapx, in
543 random order, using hash function HASH. */
545 test_random_sequence (int max_elems, hash_function *hash)
547 const int max_trials = 8;
550 for (cnt = 0; cnt <= max_elems; cnt += 2)
552 int *insertions, *deletions;
556 insertions = xnmalloc (cnt, sizeof *insertions);
557 deletions = xnmalloc (cnt, sizeof *deletions);
558 for (i = 0; i < cnt; i++)
560 for (i = 0; i < cnt; i++)
563 for (trial = 0; trial < max_trials; trial++)
565 random_shuffle (insertions, cnt, sizeof *insertions);
566 random_shuffle (deletions, cnt, sizeof *deletions);
568 test_insert_delete (insertions, deletions, cnt, hash, 0);
577 test_random_sequence_random_hash (void)
579 test_random_sequence (64, random_hash);
583 test_random_sequence_identity_hash (void)
585 test_random_sequence (64, identity_hash);
589 test_random_sequence_constant_hash (void)
591 test_random_sequence (32, constant_hash);
594 /* Inserts MAX_ELEMS elements into an HMAPX in ascending order,
595 then delete in ascending order and shrink the hmapx at each
596 step, using hash function HASH. */
598 test_insert_ordered (int max_elems, hash_function *hash)
600 struct element *elements;
601 struct hmapx_node **nodes;
607 elements = xnmalloc (max_elems, sizeof *elements);
608 nodes = xnmalloc (max_elems, sizeof *nodes);
609 values = xnmalloc (max_elems, sizeof *values);
610 for (i = 0; i < max_elems; i++)
612 values[i] = elements[i].data = i;
613 nodes[i] = hmapx_insert (&hmapx, &elements[i], hash (elements[i].data));
614 check_hmapx (&hmapx, values, i + 1, hash);
616 if (hash == identity_hash)
618 /* Check that every every hash bucket has (almost) the
619 same number of nodes in it. */
624 for (j = 0; j <= hmapx.hmap.mask; j++)
627 struct hmap_node *node;
629 for (node = hmapx.hmap.buckets[j]; node != NULL;
637 check (max - min <= 1);
640 for (i = 0; i < max_elems; i++)
642 hmapx_delete (&hmapx, nodes[i]);
643 hmapx_shrink (&hmapx);
644 check_hmapx (&hmapx, values + i + 1, max_elems - i - 1, hash);
646 hmapx_destroy (&hmapx);
653 test_insert_ordered_random_hash (void)
655 test_insert_ordered (1024, random_hash);
659 test_insert_ordered_identity_hash (void)
661 test_insert_ordered (1024, identity_hash);
665 test_insert_ordered_constant_hash (void)
667 test_insert_ordered (128, constant_hash);
670 /* Inserts up to MAX_ELEMS elements into an HMAPX, then moves the
671 nodes around in memory, using hash function HASH. */
673 test_moved (int max_elems, hash_function *hash)
675 struct element *e[2];
678 struct hmapx_node **nodes;
683 e[0] = xnmalloc (max_elems, sizeof *e[0]);
684 e[1] = xnmalloc (max_elems, sizeof *e[1]);
685 values = xnmalloc (max_elems, sizeof *values);
686 nodes = xnmalloc (max_elems, sizeof *nodes);
688 for (i = 0; i < max_elems; i++)
690 values[i] = e[cur][i].data = i;
691 nodes[i] = hmapx_insert (&hmapx, &e[cur][i], hash (e[cur][i].data));
692 check_hmapx (&hmapx, values, i + 1, hash);
694 for (j = 0; j <= i; j++)
696 e[!cur][j] = e[cur][j];
697 hmapx_move (nodes[j], &e[cur][j]);
698 check_hmapx (&hmapx, values, i + 1, hash);
702 hmapx_destroy (&hmapx);
710 test_moved_random_hash (void)
712 test_moved (128, random_hash);
716 test_moved_identity_hash (void)
718 test_moved (128, identity_hash);
722 test_moved_constant_hash (void)
724 test_moved (32, constant_hash);
727 /* Inserts values into an HMAPX, then changes their values, using
728 hash function HASH. */
730 test_changed (hash_function *hash)
732 const int max_elems = 6;
735 for (cnt = 0; cnt <= max_elems; cnt++)
737 int *values, *changed_values;
738 struct hmapx_node **nodes;
739 struct element *elements;
740 unsigned int permutation_cnt;
743 values = xnmalloc (cnt, sizeof *values);
744 changed_values = xnmalloc (cnt, sizeof *changed_values);
745 elements = xnmalloc (cnt, sizeof *elements);
746 nodes = xnmalloc (cnt, sizeof *nodes);
747 for (i = 0; i < cnt; i++)
750 for (permutation_cnt = 0;
751 permutation_cnt == 0 || next_permutation (values, cnt);
754 for (i = 0; i < cnt; i++)
757 for (j = 0; j <= cnt; j++)
763 /* Add to HMAPX in order. */
764 for (k = 0; k < cnt; k++)
767 elements[n].data = n;
768 nodes[n] = hmapx_insert (&hmapx, &elements[n],
769 hash (elements[n].data));
771 check_hmapx (&hmapx, values, cnt, hash);
773 /* Change value i to j. */
774 elements[i].data = j;
775 hmapx_changed (&hmapx, nodes[i],
776 hash (elements[i].data));
777 for (k = 0; k < cnt; k++)
778 changed_values[k] = k;
779 changed_values[i] = j;
780 check_hmapx (&hmapx, changed_values, cnt, hash);
782 hmapx_destroy (&hmapx);
786 check (permutation_cnt == factorial (cnt));
789 free (changed_values);
796 test_changed_random_hash (void)
798 test_changed (random_hash);
802 test_changed_identity_hash (void)
804 test_changed (identity_hash);
808 test_changed_constant_hash (void)
810 test_changed (constant_hash);
813 /* Inserts values into an HMAPX, then changes and moves their
814 values, using hash function HASH. */
816 test_change (hash_function *hash)
818 const int max_elems = 6;
821 for (cnt = 0; cnt <= max_elems; cnt++)
823 int *values, *changed_values;
824 struct hmapx_node **nodes;
825 struct element *elements;
826 struct element replacement;
827 unsigned int permutation_cnt;
830 values = xnmalloc (cnt, sizeof *values);
831 changed_values = xnmalloc (cnt, sizeof *changed_values);
832 elements = xnmalloc (cnt, sizeof *elements);
833 nodes = xnmalloc (cnt, sizeof *nodes);
834 for (i = 0; i < cnt; i++)
837 for (permutation_cnt = 0;
838 permutation_cnt == 0 || next_permutation (values, cnt);
841 for (i = 0; i < cnt; i++)
844 for (j = 0; j <= cnt; j++)
850 /* Add to HMAPX in order. */
851 for (k = 0; k < cnt; k++)
854 elements[n].data = n;
855 nodes[n] = hmapx_insert (&hmapx, &elements[n],
856 hash (elements[n].data));
858 check_hmapx (&hmapx, values, cnt, hash);
860 /* Change value i to j. */
861 replacement.data = j;
862 hmapx_change (&hmapx, nodes[i], &replacement, hash (j));
863 for (k = 0; k < cnt; k++)
864 changed_values[k] = k;
865 changed_values[i] = j;
866 check_hmapx (&hmapx, changed_values, cnt, hash);
868 hmapx_destroy (&hmapx);
872 check (permutation_cnt == factorial (cnt));
875 free (changed_values);
882 test_change_random_hash (void)
884 test_change (random_hash);
888 test_change_identity_hash (void)
890 test_change (identity_hash);
894 test_change_constant_hash (void)
896 test_change (constant_hash);
900 test_swap (int max_elems, hash_function *hash)
902 struct element *elements;
905 struct hmapx *working, *empty;
912 elements = xnmalloc (max_elems, sizeof *elements);
913 values = xnmalloc (max_elems, sizeof *values);
914 for (i = 0; i < max_elems; i++)
917 values[i] = elements[i].data = i;
918 hmapx_insert (working, &elements[i], hash (elements[i].data));
919 check_hmapx (working, values, i + 1, hash);
920 check_hmapx (empty, NULL, 0, hash);
933 test_swap_random_hash (void)
935 test_swap (128, random_hash);
938 /* Inserts elements into an HMAPX in ascending order, then clears the hash
939 table using hmapx_clear(). */
943 const int max_elems = 128;
944 struct element *elements;
945 struct hmapx_node **nodes;
950 elements = xnmalloc (max_elems, sizeof *elements);
951 nodes = xnmalloc (max_elems, sizeof *nodes);
952 values = xnmalloc (max_elems, sizeof *values);
955 for (cnt = 0; cnt <= max_elems; cnt++)
959 for (i = 0; i < cnt; i++)
961 values[i] = elements[i].data = i;
962 nodes[i] = hmapx_insert (&hmapx, &elements[i],
963 random_hash (elements[i].data));
964 check_hmapx (&hmapx, values, i + 1, random_hash);
966 hmapx_clear (&hmapx);
967 check_hmapx (&hmapx, NULL, 0, random_hash);
969 hmapx_destroy (&hmapx);
977 test_destroy_null (void)
979 hmapx_destroy (NULL);
982 /* Test shrinking an empty hash table. */
984 test_shrink_empty (void)
989 hmapx_reserve (&hmapx, 123);
990 hmapx_shrink (&hmapx);
991 hmapx_destroy (&hmapx);
996 /* Runs TEST_FUNCTION and prints a message about NAME. */
998 run_test (void (*test_function) (void), const char *name)
1009 run_test (test_insert_any_remove_any_random_hash,
1010 "insert any order, delete any order (random hash)");
1011 run_test (test_insert_any_remove_any_identity_hash,
1012 "insert any order, delete any order (identity hash)");
1013 run_test (test_insert_any_remove_any_constant_hash,
1014 "insert any order, delete any order (constant hash)");
1016 run_test (test_insert_any_remove_same_random_hash,
1017 "insert any order, delete same order (random hash)");
1018 run_test (test_insert_any_remove_same_identity_hash,
1019 "insert any order, delete same order (identity hash)");
1020 run_test (test_insert_any_remove_same_constant_hash,
1021 "insert any order, delete same order (constant hash)");
1023 run_test (test_insert_any_remove_reverse_random_hash,
1024 "insert any order, delete reverse order (random hash)");
1025 run_test (test_insert_any_remove_reverse_identity_hash,
1026 "insert any order, delete reverse order (identity hash)");
1027 run_test (test_insert_any_remove_reverse_constant_hash,
1028 "insert any order, delete reverse order (constant hash)");
1030 run_test (test_random_sequence_random_hash,
1031 "insert and delete in random sequence (random hash)");
1032 run_test (test_random_sequence_identity_hash,
1033 "insert and delete in random sequence (identity hash)");
1034 run_test (test_random_sequence_constant_hash,
1035 "insert and delete in random sequence (constant hash)");
1037 run_test (test_insert_ordered_random_hash,
1038 "insert in ascending order (random hash)");
1039 run_test (test_insert_ordered_identity_hash,
1040 "insert in ascending order (identity hash)");
1041 run_test (test_insert_ordered_constant_hash,
1042 "insert in ascending order (constant hash)");
1044 run_test (test_moved_random_hash,
1045 "move elements around in memory (random hash)");
1046 run_test (test_moved_identity_hash,
1047 "move elements around in memory (identity hash)");
1048 run_test (test_moved_constant_hash,
1049 "move elements around in memory (constant hash)");
1051 run_test (test_changed_random_hash,
1052 "change key data in nodes (random hash)");
1053 run_test (test_changed_identity_hash,
1054 "change key data in nodes (identity hash)");
1055 run_test (test_changed_constant_hash,
1056 "change key data in nodes (constant hash)");
1058 run_test (test_change_random_hash,
1059 "change and move key data in nodes (random hash)");
1060 run_test (test_change_identity_hash,
1061 "change and move key data in nodes (identity hash)");
1062 run_test (test_change_constant_hash,
1063 "change and move key data in nodes (constant hash)");
1065 run_test (test_swap_random_hash, "test swapping tables");
1067 run_test (test_clear, "test clearing hash table");
1069 run_test (test_destroy_null, "test destroying null table");
1070 run_test (test_shrink_empty, "test shrinking an empty table");