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
28 #include <libpspp/hmap.h>
39 #include <libpspp/compiler.h>
41 /* Currently running test. */
42 static const char *test_name;
44 /* Exit with a failure code.
45 (Place a breakpoint on this function while debugging.) */
52 /* If OK is not true, prints a message about failure on the
53 current source file and the given LINE and terminates. */
55 check_func (bool ok, int line)
59 printf ("Check failed in %s test at %s, line %d\n",
60 test_name, __FILE__, line);
65 /* Verifies that EXPR evaluates to true.
66 If not, prints a message citing the calling line number and
68 #define check(EXPR) check_func ((EXPR), __LINE__)
70 /* Prints a message about memory exhaustion and exits with a
75 printf ("virtual memory exhausted\n");
79 /* Allocates and returns N bytes of memory. */
96 xmemdup (const void *p, size_t n)
98 void *q = xmalloc (n);
103 /* Allocates and returns N * M bytes of memory. */
105 xnmalloc (size_t n, size_t m)
107 if ((size_t) -1 / m <= n)
109 return xmalloc (n * m);
112 /* Node type and support routines. */
114 /* Test data element. */
117 struct hmap_node node; /* Embedded hash table element. */
118 int data; /* Primary value. */
121 /* Returns the `struct element' that NODE is embedded within. */
122 static struct element *
123 hmap_node_to_element (const struct hmap_node *node)
125 return HMAP_DATA (node, struct element, node);
128 /* Compares A and B and returns a strcmp-type return value. */
130 compare_ints (const void *a_, const void *b_)
135 return *a < *b ? -1 : *a > *b;
138 /* Swaps *A and *B. */
140 swap (int *a, int *b)
147 /* Reverses the order of the CNT integers starting at VALUES. */
149 reverse (int *values, size_t cnt)
155 swap (&values[i++], &values[--j]);
158 /* Arranges the CNT elements in VALUES into the lexicographically
159 next greater permutation. Returns true if successful.
160 If VALUES is already the lexicographically greatest
161 permutation of its elements (i.e. ordered from greatest to
162 smallest), arranges them into the lexicographically least
163 permutation (i.e. ordered from smallest to largest) and
166 next_permutation (int *values, size_t cnt)
174 if (values[i] < values[i + 1])
177 for (j = cnt - 1; values[i] >= values[j]; j--)
179 swap (values + i, values + j);
180 reverse (values + (i + 1), cnt - (i + 1));
185 reverse (values, cnt);
193 factorial (unsigned int n)
195 unsigned int value = 1;
201 /* Randomly shuffles the CNT elements in ARRAY, each of which is
202 SIZE bytes in size. */
204 random_shuffle (void *array_, size_t cnt, size_t size)
206 char *array = array_;
207 char *tmp = xmalloc (size);
210 for (i = 0; i < cnt; i++)
212 size_t j = rand () % (cnt - i) + i;
215 memcpy (tmp, array + j * size, size);
216 memcpy (array + j * size, array + i * size, size);
217 memcpy (array + i * size, tmp, size);
224 typedef size_t hash_function (int data);
227 identity_hash (int data)
233 constant_hash (int data UNUSED)
238 static inline uint32_t
239 md4_round (uint32_t a, uint32_t b, uint32_t c, uint32_t d,
240 uint32_t data, uint32_t n)
242 uint32_t x = a + (d ^ (b & (c ^ d))) + data;
243 return (x << n) | (x >> (32 - n));
247 random_hash (int data)
253 a = md4_round (a, b, c, d, 0, 3);
254 d = md4_round (d, a, b, c, 1, 7);
255 c = md4_round (c, d, a, b, 2, 11);
256 b = md4_round (b, c, d, a, 3, 19);
257 return a ^ b ^ c ^ d;
260 static struct hmap_node *
261 find_element (struct hmap *hmap, int data, hash_function *hash)
264 HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (data), hmap)
270 /* Checks that HMAP contains the CNT ints in DATA, that its
271 structure is correct, and that certain operations on HMAP
272 produce the expected results. */
274 check_hmap (struct hmap *hmap, const int data[], size_t cnt,
280 check (hmap_count (hmap) == cnt);
281 check (cnt <= hmap_capacity (hmap));
283 order = xmemdup (data, cnt * sizeof *data);
284 qsort (order, cnt, sizeof *order, compare_ints);
286 for (i = 0; i < cnt; i = j)
291 for (j = i + 1; j < cnt; j++)
292 if (order[i] != order[j])
296 HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (order[i]), hmap)
297 if (e->data == order[i])
300 check (count == j - i);
303 check (find_element (hmap, -1, hash) == NULL);
306 check (hmap_first (hmap) == NULL);
313 for (p = hmap_first (hmap), i = 0; i < cnt; p = hmap_next (hmap, p), i++)
315 struct element *e = hmap_node_to_element (p);
318 check (hmap_node_hash (&e->node) == hash (e->data));
319 for (j = 0; j < left; j++)
320 if (order[j] == e->data)
322 order[j] = order[--left];
335 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
336 HMAP in the order specified by INSERTIONS, then deletes them in
337 the order specified by DELETIONS, checking the HMAP's contents
338 for correctness after each operation. Uses HASH as the hash
341 test_insert_delete (const int insertions[],
342 const int deletions[],
346 struct element *elements;
350 elements = xnmalloc (cnt, sizeof *elements);
351 for (i = 0; i < cnt; i++)
352 elements[i].data = i;
355 hmap_reserve (&hmap, 1);
356 check_hmap (&hmap, NULL, 0, hash);
357 for (i = 0; i < cnt; i++)
360 hmap_insert (&hmap, &elements[insertions[i]].node, hash (insertions[i]));
361 check_hmap (&hmap, insertions, i + 1, hash);
363 /* A series of insertions should not produce a shrinkable hmap. */
364 capacity = hmap_capacity (&hmap);
366 check (capacity == hmap_capacity (&hmap));
368 for (i = 0; i < cnt; i++)
370 hmap_delete (&hmap, &elements[deletions[i]].node);
371 check_hmap (&hmap, deletions + i + 1, cnt - i - 1, hash);
373 hmap_destroy (&hmap);
378 /* Inserts values into an HMAP 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);
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 HMAP 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);
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 HMAP 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);
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 hmap, 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);
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 HMAP in ascending order,
594 then delete in ascending order and shrink the hmap at each
595 step, using hash function HASH. */
597 test_insert_ordered (int max_elems, hash_function *hash)
599 struct element *elements;
605 elements = xnmalloc (max_elems, sizeof *elements);
606 values = xnmalloc (max_elems, sizeof *values);
607 for (i = 0; i < max_elems; i++)
609 values[i] = elements[i].data = i;
610 hmap_insert (&hmap, &elements[i].node, hash (elements[i].data));
611 check_hmap (&hmap, values, i + 1, hash);
613 if (hash == identity_hash)
615 /* Check that every every hash bucket has (almost) the
616 same number of nodes in it. */
621 for (j = 0; j <= hmap.mask; j++)
624 struct hmap_node *node;
626 for (node = hmap.buckets[j]; node != NULL; node = node->next)
633 check (max - min <= 1);
636 for (i = 0; i < max_elems; i++)
638 hmap_delete (&hmap, &elements[i].node);
640 check_hmap (&hmap, values + i + 1, max_elems - i - 1, hash);
642 hmap_destroy (&hmap);
648 test_insert_ordered_random_hash (void)
650 test_insert_ordered (1024, random_hash);
654 test_insert_ordered_identity_hash (void)
656 test_insert_ordered (1024, identity_hash);
660 test_insert_ordered_constant_hash (void)
662 test_insert_ordered (128, constant_hash);
665 /* Inserts up to MAX_ELEMS elements into an HMAP, then moves the
666 nodes around in memory, using hash function HASH. */
668 test_moved (int max_elems, hash_function *hash)
670 struct element *e[2];
677 e[0] = xnmalloc (max_elems, sizeof *e[0]);
678 e[1] = xnmalloc (max_elems, sizeof *e[1]);
679 values = xnmalloc (max_elems, sizeof *values);
681 for (i = 0; i < max_elems; i++)
683 values[i] = e[cur][i].data = i;
684 hmap_insert (&hmap, &e[cur][i].node, hash (e[cur][i].data));
685 check_hmap (&hmap, values, i + 1, hash);
687 for (j = 0; j <= i; j++)
689 e[!cur][j] = e[cur][j];
690 hmap_moved (&hmap, &e[!cur][j].node, &e[cur][j].node);
691 check_hmap (&hmap, values, i + 1, hash);
695 hmap_destroy (&hmap);
702 test_moved_random_hash (void)
704 test_moved (128, random_hash);
708 test_moved_identity_hash (void)
710 test_moved (128, identity_hash);
714 test_moved_constant_hash (void)
716 test_moved (32, constant_hash);
719 /* Inserts values into an HMAP, then changes their values, using
720 hash function HASH. */
722 test_changed (hash_function *hash)
724 const int max_elems = 6;
727 for (cnt = 0; cnt <= max_elems; cnt++)
729 int *values, *changed_values;
730 struct element *elements;
731 unsigned int permutation_cnt;
734 values = xnmalloc (cnt, sizeof *values);
735 changed_values = xnmalloc (cnt, sizeof *changed_values);
736 elements = xnmalloc (cnt, sizeof *elements);
737 for (i = 0; i < cnt; i++)
740 for (permutation_cnt = 0;
741 permutation_cnt == 0 || next_permutation (values, cnt);
744 for (i = 0; i < cnt; i++)
747 for (j = 0; j <= cnt; j++)
753 /* Add to HMAP in order. */
754 for (k = 0; k < cnt; k++)
757 elements[n].data = n;
758 hmap_insert (&hmap, &elements[n].node,
759 hash (elements[n].data));
761 check_hmap (&hmap, values, cnt, hash);
763 /* Change value i to j. */
764 elements[i].data = j;
765 hmap_changed (&hmap, &elements[i].node,
766 hash (elements[i].data));
767 for (k = 0; k < cnt; k++)
768 changed_values[k] = k;
769 changed_values[i] = j;
770 check_hmap (&hmap, changed_values, cnt, hash);
772 hmap_destroy (&hmap);
776 check (permutation_cnt == factorial (cnt));
779 free (changed_values);
785 test_changed_random_hash (void)
787 test_changed (random_hash);
791 test_changed_identity_hash (void)
793 test_changed (identity_hash);
797 test_changed_constant_hash (void)
799 test_changed (constant_hash);
803 test_swap (int max_elems, hash_function *hash)
805 struct element *elements;
808 struct hmap *working, *empty;
815 elements = xnmalloc (max_elems, sizeof *elements);
816 values = xnmalloc (max_elems, sizeof *values);
817 for (i = 0; i < max_elems; i++)
820 values[i] = elements[i].data = i;
821 hmap_insert (working, &elements[i].node, hash (elements[i].data));
822 check_hmap (working, values, i + 1, hash);
823 check_hmap (empty, NULL, 0, hash);
836 test_swap_random_hash (void)
838 test_swap (128, random_hash);
842 test_destroy_null (void)
847 /* Test shrinking an empty hash table. */
849 test_shrink_empty (void)
854 hmap_reserve (&hmap, 123);
856 hmap_destroy (&hmap);
861 /* Runs TEST_FUNCTION and prints a message about NAME. */
863 run_test (void (*test_function) (void), const char *name)
874 run_test (test_insert_any_remove_any_random_hash,
875 "insert any order, delete any order (random hash)");
876 run_test (test_insert_any_remove_any_identity_hash,
877 "insert any order, delete any order (identity hash)");
878 run_test (test_insert_any_remove_any_constant_hash,
879 "insert any order, delete any order (constant hash)");
881 run_test (test_insert_any_remove_same_random_hash,
882 "insert any order, delete same order (random hash)");
883 run_test (test_insert_any_remove_same_identity_hash,
884 "insert any order, delete same order (identity hash)");
885 run_test (test_insert_any_remove_same_constant_hash,
886 "insert any order, delete same order (constant hash)");
888 run_test (test_insert_any_remove_reverse_random_hash,
889 "insert any order, delete reverse order (random hash)");
890 run_test (test_insert_any_remove_reverse_identity_hash,
891 "insert any order, delete reverse order (identity hash)");
892 run_test (test_insert_any_remove_reverse_constant_hash,
893 "insert any order, delete reverse order (constant hash)");
895 run_test (test_random_sequence_random_hash,
896 "insert and delete in random sequence (random hash)");
897 run_test (test_random_sequence_identity_hash,
898 "insert and delete in random sequence (identity hash)");
899 run_test (test_random_sequence_constant_hash,
900 "insert and delete in random sequence (constant hash)");
902 run_test (test_insert_ordered_random_hash,
903 "insert in ascending order (random hash)");
904 run_test (test_insert_ordered_identity_hash,
905 "insert in ascending order (identity hash)");
906 run_test (test_insert_ordered_constant_hash,
907 "insert in ascending order (constant hash)");
909 run_test (test_moved_random_hash,
910 "move elements around in memory (random hash)");
911 run_test (test_moved_identity_hash,
912 "move elements around in memory (identity hash)");
913 run_test (test_moved_constant_hash,
914 "move elements around in memory (constant hash)");
916 run_test (test_changed_random_hash,
917 "change key data in nodes (random hash)");
918 run_test (test_changed_identity_hash,
919 "change key data in nodes (identity hash)");
920 run_test (test_changed_constant_hash,
921 "change key data in nodes (constant hash)");
923 run_test (test_swap_random_hash, "test swapping tables");
925 run_test (test_destroy_null, "test destroying null table");
926 run_test (test_shrink_empty, "test shrinking an empty table");