Added a dict parameter to data_in and dealt with the consequences.
[pspp-builds.git] / tests / libpspp / hmapx-test.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007, 2008 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
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
22    clean report. */
23
24 #ifdef HAVE_CONFIG_H
25 #include <config.h>
26 #endif
27
28 #include <libpspp/hmapx.h>
29
30 #include <assert.h>
31 #include <limits.h>
32 #include <stdbool.h>
33 #include <stddef.h>
34 #include <stdint.h>
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38
39 #include <libpspp/compiler.h>
40 \f
41 /* Currently running test. */
42 static const char *test_name;
43
44 /* If OK is not true, prints a message about failure on the
45    current source file and the given LINE and terminates. */
46 static void
47 check_func (bool ok, int line)
48 {
49   if (!ok)
50     {
51       printf ("Check failed in %s test at %s, line %d\n",
52               test_name, __FILE__, line);
53       abort ();
54     }
55 }
56
57 /* Verifies that EXPR evaluates to true.
58    If not, prints a message citing the calling line number and
59    terminates. */
60 #define check(EXPR) check_func ((EXPR), __LINE__)
61
62 /* Prints a message about memory exhaustion and exits with a
63    failure code. */
64 static void
65 xalloc_die (void)
66 {
67   printf ("virtual memory exhausted\n");
68   exit (EXIT_FAILURE);
69 }
70
71 /* Allocates and returns N bytes of memory. */
72 static void *
73 xmalloc (size_t n)
74 {
75   if (n != 0)
76     {
77       void *p = malloc (n);
78       if (p == NULL)
79         xalloc_die ();
80
81       return p;
82     }
83   else
84     return NULL;
85 }
86
87 static void *
88 xmemdup (const void *p, size_t n)
89 {
90   void *q = xmalloc (n);
91   memcpy (q, p, n);
92   return q;
93 }
94
95 /* Allocates and returns N * M bytes of memory. */
96 static void *
97 xnmalloc (size_t n, size_t m)
98 {
99   if ((size_t) -1 / m <= n)
100     xalloc_die ();
101   return xmalloc (n * m);
102 }
103 \f
104 /* Node type and support routines. */
105
106 /* Test data element. */
107 struct element
108   {
109     int data;                 /* Primary value. */
110   };
111
112 /* Compares A and B and returns a strcmp-type return value. */
113 static int
114 compare_ints (const void *a_, const void *b_)
115 {
116   const int *a = a_;
117   const int *b = b_;
118
119   return *a < *b ? -1 : *a > *b;
120 }
121
122 /* Swaps *A and *B. */
123 static void
124 swap (int *a, int *b)
125 {
126   int t = *a;
127   *a = *b;
128   *b = t;
129 }
130
131 /* Reverses the order of the CNT integers starting at VALUES. */
132 static void
133 reverse (int *values, size_t cnt)
134 {
135   size_t i = 0;
136   size_t j = cnt;
137
138   while (j > i)
139     swap (&values[i++], &values[--j]);
140 }
141
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
148    returns false. */
149 static bool
150 next_permutation (int *values, size_t cnt)
151 {
152   if (cnt > 0)
153     {
154       size_t i = cnt - 1;
155       while (i != 0)
156         {
157           i--;
158           if (values[i] < values[i + 1])
159             {
160               size_t j;
161               for (j = cnt - 1; values[i] >= values[j]; j--)
162                 continue;
163               swap (values + i, values + j);
164               reverse (values + (i + 1), cnt - (i + 1));
165               return true;
166             }
167         }
168
169       reverse (values, cnt);
170     }
171
172   return false;
173 }
174
175 /* Returns N!. */
176 static unsigned int
177 factorial (unsigned int n)
178 {
179   unsigned int value = 1;
180   while (n > 1)
181     value *= n--;
182   return value;
183 }
184
185 /* Randomly shuffles the CNT elements in ARRAY, each of which is
186    SIZE bytes in size. */
187 static void
188 random_shuffle (void *array_, size_t cnt, size_t size)
189 {
190   char *array = array_;
191   char *tmp = xmalloc (size);
192   size_t i;
193
194   for (i = 0; i < cnt; i++)
195     {
196       size_t j = rand () % (cnt - i) + i;
197       if (i != j)
198         {
199           memcpy (tmp, array + j * size, size);
200           memcpy (array + j * size, array + i * size, size);
201           memcpy (array + i * size, tmp, size);
202         }
203     }
204
205   free (tmp);
206 }
207
208 typedef size_t hash_function (int data);
209
210 static size_t
211 identity_hash (int data) 
212 {
213   return data;
214 }
215
216 static size_t
217 constant_hash (int data UNUSED) 
218 {
219   return 0x12345678u;
220 }
221
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)
225 {
226   uint32_t x = a + (d ^ (b & (c ^ d))) + data;
227   return (x << n) | (x >> (32 - n));
228 }
229
230 static size_t
231 random_hash (int data)
232 {
233   uint32_t a = data;
234   uint32_t b = data;
235   uint32_t c = data;
236   uint32_t d = 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;
242 }
243
244 static struct hmapx_node *
245 find_element (struct hmapx *hmapx, int data, hash_function *hash)
246 {
247   struct hmapx_node *node;
248   struct element *e;
249   HMAPX_FOR_EACH_WITH_HASH (e, node, hash (data), hmapx)
250     if (e->data == data)
251       break;
252   return node;
253 }
254
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. */
258 static void
259 check_hmapx (struct hmapx *hmapx, const int data[], size_t cnt,
260             hash_function *hash)
261 {
262   size_t i, j;
263   int *order;
264
265   check (hmapx_count (hmapx) == cnt);
266   check (cnt <= hmapx_capacity (hmapx));
267
268   order = xmemdup (data, cnt * sizeof *data);
269   qsort (order, cnt, sizeof *order, compare_ints);
270
271   for (i = 0; i < cnt; i = j)
272     {
273       struct hmapx_node *node;
274       struct element *e;
275       int count;
276
277       for (j = i + 1; j < cnt; j++)
278         if (order[i] != order[j])
279           break;
280
281       count = 0;
282       HMAPX_FOR_EACH_WITH_HASH (e, node, hash (order[i]), hmapx)
283         if (e->data == order[i]) 
284           count++; 
285
286       check (count == j - i);
287     }
288
289   check (find_element (hmapx, -1, hash) == NULL);
290
291   if (cnt == 0)
292     check (hmapx_first (hmapx) == NULL);
293   else
294     {
295       struct hmapx_node *p;
296       int left;
297
298       left = cnt;
299       for (p = hmapx_first (hmapx), i = 0; i < cnt;
300            p = hmapx_next (hmapx, p), i++)
301         {
302           struct element *e = hmapx_node_data (p);
303           size_t j;
304
305           check (hmapx_node_hash (p) == hash (e->data));
306           for (j = 0; j < left; j++)
307             if (order[j] == e->data) 
308               {
309                 order[j] = order[--left];
310                 goto next;
311               }
312           abort ();
313
314         next: ;
315         }
316       check (p == NULL);
317     }
318
319   free (order);
320 }
321
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
326    function. */
327 static void
328 test_insert_delete (const int insertions[],
329                     const int deletions[],
330                     size_t cnt,
331                     hash_function *hash,
332                     size_t reserve)
333 {
334   struct element *elements;
335   struct hmapx_node **nodes;
336   struct hmapx hmapx;
337   size_t i;
338
339   elements = xnmalloc (cnt, sizeof *elements);
340   nodes = xnmalloc (cnt, sizeof *nodes);
341   for (i = 0; i < cnt; i++)
342     elements[i].data = i;
343
344   hmapx_init (&hmapx);
345   hmapx_reserve (&hmapx, reserve);
346   check_hmapx (&hmapx, NULL, 0, hash);
347   for (i = 0; i < cnt; i++)
348     {
349       struct hmapx_node *(*insert) (struct hmapx *, void *, size_t hash);
350       size_t capacity;
351
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);
358
359       /* A series of insertions should not produce a shrinkable hmapx. */
360       if (i >= reserve) 
361         {
362           capacity = hmapx_capacity (&hmapx);
363           hmapx_shrink (&hmapx);
364           check (capacity == hmapx_capacity (&hmapx)); 
365         }
366     }
367   for (i = 0; i < cnt; i++)
368     {
369       hmapx_delete (&hmapx, nodes[deletions[i]]);
370       check_hmapx (&hmapx, deletions + i + 1, cnt - i - 1, hash);
371     }
372   hmapx_destroy (&hmapx);
373
374   free (elements);
375   free (nodes);
376 }
377 \f
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. */
381 static void
382 test_insert_any_remove_any (hash_function *hash)
383 {
384   const int max_elems = 5;
385   int cnt;
386
387   for (cnt = 0; cnt <= max_elems; cnt++)
388     {
389       int *insertions, *deletions;
390       unsigned int ins_perm_cnt;
391       int i;
392
393       insertions = xnmalloc (cnt, sizeof *insertions);
394       deletions = xnmalloc (cnt, sizeof *deletions);
395       for (i = 0; i < cnt; i++)
396         insertions[i] = i;
397
398       for (ins_perm_cnt = 0;
399            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
400            ins_perm_cnt++)
401         {
402           unsigned int del_perm_cnt;
403           int i;
404
405           for (i = 0; i < cnt; i++)
406             deletions[i] = i;
407
408           for (del_perm_cnt = 0;
409                del_perm_cnt == 0 || next_permutation (deletions, cnt);
410                del_perm_cnt++)
411             test_insert_delete (insertions, deletions, cnt, hash, 1);
412
413           check (del_perm_cnt == factorial (cnt));
414         }
415       check (ins_perm_cnt == factorial (cnt));
416
417       free (insertions);
418       free (deletions);
419     }
420 }
421
422 static void
423 test_insert_any_remove_any_random_hash (void) 
424 {
425   test_insert_any_remove_any (random_hash);
426 }
427
428 static void
429 test_insert_any_remove_any_identity_hash (void) 
430 {
431   test_insert_any_remove_any (identity_hash);
432 }
433
434 static void
435 test_insert_any_remove_any_constant_hash (void) 
436 {
437   test_insert_any_remove_any (constant_hash);
438 }
439
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. */
443 static void
444 test_insert_any_remove_same (hash_function *hash)
445 {
446   const int max_elems = 7;
447   int cnt;
448
449   for (cnt = 0; cnt <= max_elems; cnt++)
450     {
451       int *values;
452       unsigned int permutation_cnt;
453       int i;
454
455       values = xnmalloc (cnt, sizeof *values);
456       for (i = 0; i < cnt; i++)
457         values[i] = i;
458
459       for (permutation_cnt = 0;
460            permutation_cnt == 0 || next_permutation (values, cnt);
461            permutation_cnt++)
462         test_insert_delete (values, values, cnt, hash, cnt / 2);
463       check (permutation_cnt == factorial (cnt));
464
465       free (values);
466     }
467 }
468
469 static void
470 test_insert_any_remove_same_random_hash (void) 
471 {
472   test_insert_any_remove_same (random_hash);
473 }
474
475 static void
476 test_insert_any_remove_same_identity_hash (void) 
477 {
478   test_insert_any_remove_same (identity_hash);
479 }
480
481 static void
482 test_insert_any_remove_same_constant_hash (void) 
483 {
484   test_insert_any_remove_same (constant_hash);
485 }
486
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. */
490 static void
491 test_insert_any_remove_reverse (hash_function *hash)
492 {
493   const int max_elems = 7;
494   int cnt;
495
496   for (cnt = 0; cnt <= max_elems; cnt++)
497     {
498       int *insertions, *deletions;
499       unsigned int permutation_cnt;
500       int i;
501
502       insertions = xnmalloc (cnt, sizeof *insertions);
503       deletions = xnmalloc (cnt, sizeof *deletions);
504       for (i = 0; i < cnt; i++)
505         insertions[i] = i;
506
507       for (permutation_cnt = 0;
508            permutation_cnt == 0 || next_permutation (insertions, cnt);
509            permutation_cnt++)
510         {
511           memcpy (deletions, insertions, sizeof *insertions * cnt);
512           reverse (deletions, cnt);
513
514           test_insert_delete (insertions, deletions, cnt, hash, cnt);
515         }
516       check (permutation_cnt == factorial (cnt));
517
518       free (insertions);
519       free (deletions);
520     }
521 }
522
523 static void
524 test_insert_any_remove_reverse_random_hash (void)
525 {
526   test_insert_any_remove_reverse (random_hash);
527 }
528
529 static void
530 test_insert_any_remove_reverse_identity_hash (void)
531 {
532   test_insert_any_remove_reverse (identity_hash);
533 }
534
535 static void
536 test_insert_any_remove_reverse_constant_hash (void)
537 {
538   test_insert_any_remove_reverse (constant_hash);
539 }
540
541 /* Inserts and removes up to MAX_ELEMS values in an hmapx, in
542    random order, using hash function HASH. */
543 static void
544 test_random_sequence (int max_elems, hash_function *hash)
545 {
546   const int max_trials = 8;
547   int cnt;
548
549   for (cnt = 0; cnt <= max_elems; cnt += 2)
550     {
551       int *insertions, *deletions;
552       int trial;
553       int i;
554
555       insertions = xnmalloc (cnt, sizeof *insertions);
556       deletions = xnmalloc (cnt, sizeof *deletions);
557       for (i = 0; i < cnt; i++)
558         insertions[i] = i;
559       for (i = 0; i < cnt; i++)
560         deletions[i] = i;
561
562       for (trial = 0; trial < max_trials; trial++)
563         {
564           random_shuffle (insertions, cnt, sizeof *insertions);
565           random_shuffle (deletions, cnt, sizeof *deletions);
566
567           test_insert_delete (insertions, deletions, cnt, hash, 0);
568         }
569
570       free (insertions);
571       free (deletions);
572     }
573 }
574
575 static void
576 test_random_sequence_random_hash (void) 
577 {
578   test_random_sequence (64, random_hash);
579 }
580
581 static void
582 test_random_sequence_identity_hash (void) 
583 {
584   test_random_sequence (64, identity_hash);
585 }
586
587 static void
588 test_random_sequence_constant_hash (void) 
589 {
590   test_random_sequence (32, constant_hash);
591 }
592
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. */
596 static void
597 test_insert_ordered (int max_elems, hash_function *hash)
598 {
599   struct element *elements;
600   struct hmapx_node **nodes;
601   int *values;
602   struct hmapx hmapx;
603   int i;
604
605   hmapx_init (&hmapx);
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++)
610     {
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);
614
615       if (hash == identity_hash) 
616         {
617           /* Check that every every hash bucket has (almost) the
618              same number of nodes in it.  */
619           int min = INT_MAX;
620           int max = INT_MIN;
621           int j;
622
623           for (j = 0; j <= hmapx.hmap.mask; j++) 
624             {
625               int count = 0;
626               struct hmap_node *node;
627
628               for (node = hmapx.hmap.buckets[j]; node != NULL;
629                    node = node->next)
630                 count++;
631               if (count < min)
632                 min = count;
633               if (count > max)
634                 max = count;
635             }
636           check (max - min <= 1);
637         }
638     }
639   for (i = 0; i < max_elems; i++)
640     {
641       hmapx_delete (&hmapx, nodes[i]);
642       hmapx_shrink (&hmapx);
643       check_hmapx (&hmapx, values + i + 1, max_elems - i - 1, hash);
644     }
645   hmapx_destroy (&hmapx);
646   free (elements);
647   free (nodes);
648   free (values);
649 }
650
651 static void
652 test_insert_ordered_random_hash (void)
653 {
654   test_insert_ordered (1024, random_hash);
655 }
656
657 static void
658 test_insert_ordered_identity_hash (void)
659 {
660   test_insert_ordered (1024, identity_hash);
661 }
662
663 static void
664 test_insert_ordered_constant_hash (void)
665 {
666   test_insert_ordered (128, constant_hash);
667 }
668
669 /* Inserts up to MAX_ELEMS elements into an HMAPX, then moves the
670    nodes around in memory, using hash function HASH. */
671 static void
672 test_moved (int max_elems, hash_function *hash)
673 {
674   struct element *e[2];
675   int cur;
676   int *values;
677   struct hmapx_node **nodes;
678   struct hmapx hmapx;
679   int i, j;
680
681   hmapx_init (&hmapx);
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);
686   cur = 0;
687   for (i = 0; i < max_elems; i++)
688     {
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);
692
693       for (j = 0; j <= i; j++)
694         {
695           e[!cur][j] = e[cur][j];
696           hmapx_move (nodes[j], &e[cur][j]);
697           check_hmapx (&hmapx, values, i + 1, hash);
698         }
699       cur = !cur;
700     }
701   hmapx_destroy (&hmapx);
702   free (e[0]);
703   free (e[1]);
704   free (values);
705   free (nodes);
706 }
707
708 static void
709 test_moved_random_hash (void) 
710 {
711   test_moved (128, random_hash);
712 }
713
714 static void
715 test_moved_identity_hash (void) 
716 {
717   test_moved (128, identity_hash);
718 }
719
720 static void
721 test_moved_constant_hash (void) 
722 {
723   test_moved (32, constant_hash);
724 }
725
726 /* Inserts values into an HMAPX, then changes their values, using
727    hash function HASH. */
728 static void
729 test_changed (hash_function *hash)
730 {
731   const int max_elems = 6;
732   int cnt;
733
734   for (cnt = 0; cnt <= max_elems; cnt++)
735     {
736       int *values, *changed_values;
737       struct hmapx_node **nodes;
738       struct element *elements;
739       unsigned int permutation_cnt;
740       int i;
741
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++)
747         values[i] = i;
748
749       for (permutation_cnt = 0;
750            permutation_cnt == 0 || next_permutation (values, cnt);
751            permutation_cnt++)
752         {
753           for (i = 0; i < cnt; i++)
754             {
755               int j, k;
756               for (j = 0; j <= cnt; j++)
757                 {
758                   struct hmapx hmapx;
759
760                   hmapx_init (&hmapx);
761
762                   /* Add to HMAPX in order. */
763                   for (k = 0; k < cnt; k++)
764                     {
765                       int n = values[k];
766                       elements[n].data = n;
767                       nodes[n] = hmapx_insert (&hmapx, &elements[n],
768                                                hash (elements[n].data));
769                     }
770                   check_hmapx (&hmapx, values, cnt, hash);
771
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);
780
781                   hmapx_destroy (&hmapx);
782                 }
783             }
784         }
785       check (permutation_cnt == factorial (cnt));
786
787       free (values);
788       free (changed_values);
789       free (elements);
790       free (nodes);
791     }
792 }
793
794 static void
795 test_changed_random_hash (void)
796 {
797   test_changed (random_hash);
798 }
799
800 static void
801 test_changed_identity_hash (void)
802 {
803   test_changed (identity_hash);
804 }
805
806 static void
807 test_changed_constant_hash (void)
808 {
809   test_changed (constant_hash);
810 }
811
812 /* Inserts values into an HMAPX, then changes and moves their
813    values, using hash function HASH. */
814 static void
815 test_change (hash_function *hash)
816 {
817   const int max_elems = 6;
818   int cnt;
819
820   for (cnt = 0; cnt <= max_elems; cnt++)
821     {
822       int *values, *changed_values;
823       struct hmapx_node **nodes;
824       struct element *elements;
825       struct element replacement;
826       unsigned int permutation_cnt;
827       int i;
828
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++)
834         values[i] = i;
835
836       for (permutation_cnt = 0;
837            permutation_cnt == 0 || next_permutation (values, cnt);
838            permutation_cnt++)
839         {
840           for (i = 0; i < cnt; i++)
841             {
842               int j, k;
843               for (j = 0; j <= cnt; j++)
844                 {
845                   struct hmapx hmapx;
846
847                   hmapx_init (&hmapx);
848
849                   /* Add to HMAPX in order. */
850                   for (k = 0; k < cnt; k++)
851                     {
852                       int n = values[k];
853                       elements[n].data = n;
854                       nodes[n] = hmapx_insert (&hmapx, &elements[n],
855                                                hash (elements[n].data));
856                     }
857                   check_hmapx (&hmapx, values, cnt, hash);
858
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);
866
867                   hmapx_destroy (&hmapx);
868                 }
869             }
870         }
871       check (permutation_cnt == factorial (cnt));
872
873       free (values);
874       free (changed_values);
875       free (elements);
876       free (nodes);
877     }
878 }
879
880 static void
881 test_change_random_hash (void)
882 {
883   test_change (random_hash);
884 }
885
886 static void
887 test_change_identity_hash (void)
888 {
889   test_change (identity_hash);
890 }
891
892 static void
893 test_change_constant_hash (void)
894 {
895   test_change (constant_hash);
896 }
897
898 static void
899 test_swap (int max_elems, hash_function *hash) 
900 {
901   struct element *elements;
902   int *values;
903   struct hmapx a, b;
904   struct hmapx *working, *empty;
905   int i;
906
907   hmapx_init (&a);
908   hmapx_init (&b);
909   working = &a;
910   empty = &b;
911   elements = xnmalloc (max_elems, sizeof *elements);
912   values = xnmalloc (max_elems, sizeof *values);
913   for (i = 0; i < max_elems; i++)
914     {
915       struct hmapx *tmp;
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);
920       hmapx_swap (&a, &b);
921       tmp = working;
922       working = empty;
923       empty = tmp;
924     }
925   hmapx_destroy (&a);
926   hmapx_destroy (&b);
927   free (elements);
928   free (values);
929 }
930
931 static void
932 test_swap_random_hash (void) 
933 {
934   test_swap (128, random_hash);
935 }
936
937 static void
938 test_destroy_null (void) 
939 {
940   hmapx_destroy (NULL);
941 }
942
943 /* Test shrinking an empty hash table. */
944 static void
945 test_shrink_empty (void)
946 {
947   struct hmapx hmapx;
948
949   hmapx_init (&hmapx);
950   hmapx_reserve (&hmapx, 123);
951   hmapx_shrink (&hmapx);
952   hmapx_destroy (&hmapx);
953 }
954 \f
955 /* Main program. */
956
957 /* Runs TEST_FUNCTION and prints a message about NAME. */
958 static void
959 run_test (void (*test_function) (void), const char *name)
960 {
961   test_name = name;
962   putchar ('.');
963   fflush (stdout);
964   test_function ();
965 }
966
967 int
968 main (void)
969 {
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)");
976
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)");
983
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)");
990
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)");
997
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)");
1004
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)");
1011
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)");
1018
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)");
1025
1026   run_test (test_swap_random_hash, "test swapping tables");
1027
1028   run_test (test_destroy_null, "test destroying null table");
1029   run_test (test_shrink_empty, "test shrinking an empty table");
1030
1031   putchar ('\n');
1032
1033   return 0;
1034 }