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 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_count (hmapx) == cnt);
266 check (cnt <= hmapx_capacity (hmapx));
268 order = xmemdup (data, cnt * sizeof *data);
269 qsort (order, cnt, sizeof *order, compare_ints);
271 for (i = 0; i < cnt; i = j)
273 struct hmapx_node *node;
277 for (j = i + 1; j < cnt; j++)
278 if (order[i] != order[j])
282 HMAPX_FOR_EACH_WITH_HASH (e, node, hash (order[i]), hmapx)
283 if (e->data == order[i])
286 check (count == j - i);
289 check (find_element (hmapx, -1, hash) == NULL);
292 check (hmapx_first (hmapx) == NULL);
295 struct hmapx_node *p;
299 for (p = hmapx_first (hmapx), i = 0; i < cnt;
300 p = hmapx_next (hmapx, p), i++)
302 struct element *e = hmapx_node_data (p);
305 check (hmapx_node_hash (p) == hash (e->data));
306 for (j = 0; j < left; j++)
307 if (order[j] == e->data)
309 order[j] = order[--left];
322 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
323 HMAPX in the order specified by INSERTIONS, then deletes them in
324 the order specified by DELETIONS, checking the HMAPX's contents
325 for correctness after each operation. Uses HASH as the hash
328 test_insert_delete (const int insertions[],
329 const int deletions[],
334 struct element *elements;
335 struct hmapx_node **nodes;
339 elements = xnmalloc (cnt, sizeof *elements);
340 nodes = xnmalloc (cnt, sizeof *nodes);
341 for (i = 0; i < cnt; i++)
342 elements[i].data = i;
345 hmapx_reserve (&hmapx, reserve);
346 check_hmapx (&hmapx, NULL, 0, hash);
347 for (i = 0; i < cnt; i++)
349 struct hmapx_node *(*insert) (struct hmapx *, void *, size_t hash);
352 /* Insert the node. Use hmapx_insert_fast if we have not
353 yet exceeded the reserve. */
354 insert = i < reserve ? hmapx_insert_fast : hmapx_insert;
355 nodes[insertions[i]] = insert (&hmapx, &elements[insertions[i]],
356 hash (insertions[i]));
357 check_hmapx (&hmapx, insertions, i + 1, hash);
359 /* A series of insertions should not produce a shrinkable hmapx. */
362 capacity = hmapx_capacity (&hmapx);
363 hmapx_shrink (&hmapx);
364 check (capacity == hmapx_capacity (&hmapx));
367 for (i = 0; i < cnt; i++)
369 hmapx_delete (&hmapx, nodes[deletions[i]]);
370 check_hmapx (&hmapx, deletions + i + 1, cnt - i - 1, hash);
372 hmapx_destroy (&hmapx);
378 /* Inserts values into an HMAPX in each possible order, then
379 removes them in each possible order, up to a specified maximum
380 size, using hash function HASH. */
382 test_insert_any_remove_any (hash_function *hash)
384 const int max_elems = 5;
387 for (cnt = 0; cnt <= max_elems; cnt++)
389 int *insertions, *deletions;
390 unsigned int ins_perm_cnt;
393 insertions = xnmalloc (cnt, sizeof *insertions);
394 deletions = xnmalloc (cnt, sizeof *deletions);
395 for (i = 0; i < cnt; i++)
398 for (ins_perm_cnt = 0;
399 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
402 unsigned int del_perm_cnt;
405 for (i = 0; i < cnt; i++)
408 for (del_perm_cnt = 0;
409 del_perm_cnt == 0 || next_permutation (deletions, cnt);
411 test_insert_delete (insertions, deletions, cnt, hash, 1);
413 check (del_perm_cnt == factorial (cnt));
415 check (ins_perm_cnt == factorial (cnt));
423 test_insert_any_remove_any_random_hash (void)
425 test_insert_any_remove_any (random_hash);
429 test_insert_any_remove_any_identity_hash (void)
431 test_insert_any_remove_any (identity_hash);
435 test_insert_any_remove_any_constant_hash (void)
437 test_insert_any_remove_any (constant_hash);
440 /* Inserts values into an HMAPX in each possible order, then
441 removes them in the same order, up to a specified maximum
442 size, using hash function HASH. */
444 test_insert_any_remove_same (hash_function *hash)
446 const int max_elems = 7;
449 for (cnt = 0; cnt <= max_elems; cnt++)
452 unsigned int permutation_cnt;
455 values = xnmalloc (cnt, sizeof *values);
456 for (i = 0; i < cnt; i++)
459 for (permutation_cnt = 0;
460 permutation_cnt == 0 || next_permutation (values, cnt);
462 test_insert_delete (values, values, cnt, hash, cnt / 2);
463 check (permutation_cnt == factorial (cnt));
470 test_insert_any_remove_same_random_hash (void)
472 test_insert_any_remove_same (random_hash);
476 test_insert_any_remove_same_identity_hash (void)
478 test_insert_any_remove_same (identity_hash);
482 test_insert_any_remove_same_constant_hash (void)
484 test_insert_any_remove_same (constant_hash);
487 /* Inserts values into an HMAPX in each possible order, then
488 removes them in reverse order, up to a specified maximum
489 size, using hash function HASH. */
491 test_insert_any_remove_reverse (hash_function *hash)
493 const int max_elems = 7;
496 for (cnt = 0; cnt <= max_elems; cnt++)
498 int *insertions, *deletions;
499 unsigned int permutation_cnt;
502 insertions = xnmalloc (cnt, sizeof *insertions);
503 deletions = xnmalloc (cnt, sizeof *deletions);
504 for (i = 0; i < cnt; i++)
507 for (permutation_cnt = 0;
508 permutation_cnt == 0 || next_permutation (insertions, cnt);
511 memcpy (deletions, insertions, sizeof *insertions * cnt);
512 reverse (deletions, cnt);
514 test_insert_delete (insertions, deletions, cnt, hash, cnt);
516 check (permutation_cnt == factorial (cnt));
524 test_insert_any_remove_reverse_random_hash (void)
526 test_insert_any_remove_reverse (random_hash);
530 test_insert_any_remove_reverse_identity_hash (void)
532 test_insert_any_remove_reverse (identity_hash);
536 test_insert_any_remove_reverse_constant_hash (void)
538 test_insert_any_remove_reverse (constant_hash);
541 /* Inserts and removes up to MAX_ELEMS values in an hmapx, in
542 random order, using hash function HASH. */
544 test_random_sequence (int max_elems, hash_function *hash)
546 const int max_trials = 8;
549 for (cnt = 0; cnt <= max_elems; cnt += 2)
551 int *insertions, *deletions;
555 insertions = xnmalloc (cnt, sizeof *insertions);
556 deletions = xnmalloc (cnt, sizeof *deletions);
557 for (i = 0; i < cnt; i++)
559 for (i = 0; i < cnt; i++)
562 for (trial = 0; trial < max_trials; trial++)
564 random_shuffle (insertions, cnt, sizeof *insertions);
565 random_shuffle (deletions, cnt, sizeof *deletions);
567 test_insert_delete (insertions, deletions, cnt, hash, 0);
576 test_random_sequence_random_hash (void)
578 test_random_sequence (64, random_hash);
582 test_random_sequence_identity_hash (void)
584 test_random_sequence (64, identity_hash);
588 test_random_sequence_constant_hash (void)
590 test_random_sequence (32, constant_hash);
593 /* Inserts MAX_ELEMS elements into an HMAPX in ascending order,
594 then delete in ascending order and shrink the hmapx at each
595 step, using hash function HASH. */
597 test_insert_ordered (int max_elems, hash_function *hash)
599 struct element *elements;
600 struct hmapx_node **nodes;
606 elements = xnmalloc (max_elems, sizeof *elements);
607 nodes = xnmalloc (max_elems, sizeof *nodes);
608 values = xnmalloc (max_elems, sizeof *values);
609 for (i = 0; i < max_elems; i++)
611 values[i] = elements[i].data = i;
612 nodes[i] = hmapx_insert (&hmapx, &elements[i], hash (elements[i].data));
613 check_hmapx (&hmapx, values, i + 1, hash);
615 if (hash == identity_hash)
617 /* Check that every every hash bucket has (almost) the
618 same number of nodes in it. */
623 for (j = 0; j <= hmapx.hmap.mask; j++)
626 struct hmap_node *node;
628 for (node = hmapx.hmap.buckets[j]; node != NULL;
636 check (max - min <= 1);
639 for (i = 0; i < max_elems; i++)
641 hmapx_delete (&hmapx, nodes[i]);
642 hmapx_shrink (&hmapx);
643 check_hmapx (&hmapx, values + i + 1, max_elems - i - 1, hash);
645 hmapx_destroy (&hmapx);
652 test_insert_ordered_random_hash (void)
654 test_insert_ordered (1024, random_hash);
658 test_insert_ordered_identity_hash (void)
660 test_insert_ordered (1024, identity_hash);
664 test_insert_ordered_constant_hash (void)
666 test_insert_ordered (128, constant_hash);
669 /* Inserts up to MAX_ELEMS elements into an HMAPX, then moves the
670 nodes around in memory, using hash function HASH. */
672 test_moved (int max_elems, hash_function *hash)
674 struct element *e[2];
677 struct hmapx_node **nodes;
682 e[0] = xnmalloc (max_elems, sizeof *e[0]);
683 e[1] = xnmalloc (max_elems, sizeof *e[1]);
684 values = xnmalloc (max_elems, sizeof *values);
685 nodes = xnmalloc (max_elems, sizeof *nodes);
687 for (i = 0; i < max_elems; i++)
689 values[i] = e[cur][i].data = i;
690 nodes[i] = hmapx_insert (&hmapx, &e[cur][i], hash (e[cur][i].data));
691 check_hmapx (&hmapx, values, i + 1, hash);
693 for (j = 0; j <= i; j++)
695 e[!cur][j] = e[cur][j];
696 hmapx_move (nodes[j], &e[cur][j]);
697 check_hmapx (&hmapx, values, i + 1, hash);
701 hmapx_destroy (&hmapx);
709 test_moved_random_hash (void)
711 test_moved (128, random_hash);
715 test_moved_identity_hash (void)
717 test_moved (128, identity_hash);
721 test_moved_constant_hash (void)
723 test_moved (32, constant_hash);
726 /* Inserts values into an HMAPX, then changes their values, using
727 hash function HASH. */
729 test_changed (hash_function *hash)
731 const int max_elems = 6;
734 for (cnt = 0; cnt <= max_elems; cnt++)
736 int *values, *changed_values;
737 struct hmapx_node **nodes;
738 struct element *elements;
739 unsigned int permutation_cnt;
742 values = xnmalloc (cnt, sizeof *values);
743 changed_values = xnmalloc (cnt, sizeof *changed_values);
744 elements = xnmalloc (cnt, sizeof *elements);
745 nodes = xnmalloc (cnt, sizeof *nodes);
746 for (i = 0; i < cnt; i++)
749 for (permutation_cnt = 0;
750 permutation_cnt == 0 || next_permutation (values, cnt);
753 for (i = 0; i < cnt; i++)
756 for (j = 0; j <= cnt; j++)
762 /* Add to HMAPX in order. */
763 for (k = 0; k < cnt; k++)
766 elements[n].data = n;
767 nodes[n] = hmapx_insert (&hmapx, &elements[n],
768 hash (elements[n].data));
770 check_hmapx (&hmapx, values, cnt, hash);
772 /* Change value i to j. */
773 elements[i].data = j;
774 hmapx_changed (&hmapx, nodes[i],
775 hash (elements[i].data));
776 for (k = 0; k < cnt; k++)
777 changed_values[k] = k;
778 changed_values[i] = j;
779 check_hmapx (&hmapx, changed_values, cnt, hash);
781 hmapx_destroy (&hmapx);
785 check (permutation_cnt == factorial (cnt));
788 free (changed_values);
795 test_changed_random_hash (void)
797 test_changed (random_hash);
801 test_changed_identity_hash (void)
803 test_changed (identity_hash);
807 test_changed_constant_hash (void)
809 test_changed (constant_hash);
812 /* Inserts values into an HMAPX, then changes and moves their
813 values, using hash function HASH. */
815 test_change (hash_function *hash)
817 const int max_elems = 6;
820 for (cnt = 0; cnt <= max_elems; cnt++)
822 int *values, *changed_values;
823 struct hmapx_node **nodes;
824 struct element *elements;
825 struct element replacement;
826 unsigned int permutation_cnt;
829 values = xnmalloc (cnt, sizeof *values);
830 changed_values = xnmalloc (cnt, sizeof *changed_values);
831 elements = xnmalloc (cnt, sizeof *elements);
832 nodes = xnmalloc (cnt, sizeof *nodes);
833 for (i = 0; i < cnt; i++)
836 for (permutation_cnt = 0;
837 permutation_cnt == 0 || next_permutation (values, cnt);
840 for (i = 0; i < cnt; i++)
843 for (j = 0; j <= cnt; j++)
849 /* Add to HMAPX in order. */
850 for (k = 0; k < cnt; k++)
853 elements[n].data = n;
854 nodes[n] = hmapx_insert (&hmapx, &elements[n],
855 hash (elements[n].data));
857 check_hmapx (&hmapx, values, cnt, hash);
859 /* Change value i to j. */
860 replacement.data = j;
861 hmapx_change (&hmapx, nodes[i], &replacement, hash (j));
862 for (k = 0; k < cnt; k++)
863 changed_values[k] = k;
864 changed_values[i] = j;
865 check_hmapx (&hmapx, changed_values, cnt, hash);
867 hmapx_destroy (&hmapx);
871 check (permutation_cnt == factorial (cnt));
874 free (changed_values);
881 test_change_random_hash (void)
883 test_change (random_hash);
887 test_change_identity_hash (void)
889 test_change (identity_hash);
893 test_change_constant_hash (void)
895 test_change (constant_hash);
899 test_swap (int max_elems, hash_function *hash)
901 struct element *elements;
904 struct hmapx *working, *empty;
911 elements = xnmalloc (max_elems, sizeof *elements);
912 values = xnmalloc (max_elems, sizeof *values);
913 for (i = 0; i < max_elems; i++)
916 values[i] = elements[i].data = i;
917 hmapx_insert (working, &elements[i], hash (elements[i].data));
918 check_hmapx (working, values, i + 1, hash);
919 check_hmapx (empty, NULL, 0, hash);
932 test_swap_random_hash (void)
934 test_swap (128, random_hash);
938 test_destroy_null (void)
940 hmapx_destroy (NULL);
943 /* Test shrinking an empty hash table. */
945 test_shrink_empty (void)
950 hmapx_reserve (&hmapx, 123);
951 hmapx_shrink (&hmapx);
952 hmapx_destroy (&hmapx);
957 /* Runs TEST_FUNCTION and prints a message about NAME. */
959 run_test (void (*test_function) (void), const char *name)
970 run_test (test_insert_any_remove_any_random_hash,
971 "insert any order, delete any order (random hash)");
972 run_test (test_insert_any_remove_any_identity_hash,
973 "insert any order, delete any order (identity hash)");
974 run_test (test_insert_any_remove_any_constant_hash,
975 "insert any order, delete any order (constant hash)");
977 run_test (test_insert_any_remove_same_random_hash,
978 "insert any order, delete same order (random hash)");
979 run_test (test_insert_any_remove_same_identity_hash,
980 "insert any order, delete same order (identity hash)");
981 run_test (test_insert_any_remove_same_constant_hash,
982 "insert any order, delete same order (constant hash)");
984 run_test (test_insert_any_remove_reverse_random_hash,
985 "insert any order, delete reverse order (random hash)");
986 run_test (test_insert_any_remove_reverse_identity_hash,
987 "insert any order, delete reverse order (identity hash)");
988 run_test (test_insert_any_remove_reverse_constant_hash,
989 "insert any order, delete reverse order (constant hash)");
991 run_test (test_random_sequence_random_hash,
992 "insert and delete in random sequence (random hash)");
993 run_test (test_random_sequence_identity_hash,
994 "insert and delete in random sequence (identity hash)");
995 run_test (test_random_sequence_constant_hash,
996 "insert and delete in random sequence (constant hash)");
998 run_test (test_insert_ordered_random_hash,
999 "insert in ascending order (random hash)");
1000 run_test (test_insert_ordered_identity_hash,
1001 "insert in ascending order (identity hash)");
1002 run_test (test_insert_ordered_constant_hash,
1003 "insert in ascending order (constant hash)");
1005 run_test (test_moved_random_hash,
1006 "move elements around in memory (random hash)");
1007 run_test (test_moved_identity_hash,
1008 "move elements around in memory (identity hash)");
1009 run_test (test_moved_constant_hash,
1010 "move elements around in memory (constant hash)");
1012 run_test (test_changed_random_hash,
1013 "change key data in nodes (random hash)");
1014 run_test (test_changed_identity_hash,
1015 "change key data in nodes (identity hash)");
1016 run_test (test_changed_constant_hash,
1017 "change key data in nodes (constant hash)");
1019 run_test (test_change_random_hash,
1020 "change and move key data in nodes (random hash)");
1021 run_test (test_change_identity_hash,
1022 "change and move key data in nodes (identity hash)");
1023 run_test (test_change_constant_hash,
1024 "change and move key data in nodes (constant hash)");
1026 run_test (test_swap_random_hash, "test swapping tables");
1028 run_test (test_destroy_null, "test destroying null table");
1029 run_test (test_shrink_empty, "test shrinking an empty table");