Increment version to 0.7.9 to send to Translation Project.
[pspp-builds.git] / tests / libpspp / hmapx-test.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2007, 2008, 2009, 2010 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 /* If OK is not true, prints a message about failure on the
42    current source file and the given LINE and terminates. */
43 static void
44 check_func (bool ok, int line)
45 {
46   if (!ok)
47     {
48       fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
49       abort ();
50     }
51 }
52
53 /* Verifies that EXPR evaluates to true.
54    If not, prints a message citing the calling line number and
55    terminates. */
56 #define check(EXPR) check_func ((EXPR), __LINE__)
57
58 /* Prints a message about memory exhaustion and exits with a
59    failure code. */
60 static void
61 xalloc_die (void)
62 {
63   printf ("virtual memory exhausted\n");
64   exit (EXIT_FAILURE);
65 }
66
67 /* Allocates and returns N bytes of memory. */
68 static void *
69 xmalloc (size_t n)
70 {
71   if (n != 0)
72     {
73       void *p = malloc (n);
74       if (p == NULL)
75         xalloc_die ();
76
77       return p;
78     }
79   else
80     return NULL;
81 }
82
83 static void *
84 xmemdup (const void *p, size_t n)
85 {
86   void *q = xmalloc (n);
87   memcpy (q, p, n);
88   return q;
89 }
90
91 /* Allocates and returns N * M bytes of memory. */
92 static void *
93 xnmalloc (size_t n, size_t m)
94 {
95   if ((size_t) -1 / m <= n)
96     xalloc_die ();
97   return xmalloc (n * m);
98 }
99 \f
100 /* Node type and support routines. */
101
102 /* Test data element. */
103 struct element
104   {
105     int data;                 /* Primary value. */
106   };
107
108 /* Compares A and B and returns a strcmp-type return value. */
109 static int
110 compare_ints (const void *a_, const void *b_)
111 {
112   const int *a = a_;
113   const int *b = b_;
114
115   return *a < *b ? -1 : *a > *b;
116 }
117
118 /* Swaps *A and *B. */
119 static void
120 swap (int *a, int *b)
121 {
122   int t = *a;
123   *a = *b;
124   *b = t;
125 }
126
127 /* Reverses the order of the CNT integers starting at VALUES. */
128 static void
129 reverse (int *values, size_t cnt)
130 {
131   size_t i = 0;
132   size_t j = cnt;
133
134   while (j > i)
135     swap (&values[i++], &values[--j]);
136 }
137
138 /* Arranges the CNT elements in VALUES into the lexicographically
139    next greater permutation.  Returns true if successful.
140    If VALUES is already the lexicographically greatest
141    permutation of its elements (i.e. ordered from greatest to
142    smallest), arranges them into the lexicographically least
143    permutation (i.e. ordered from smallest to largest) and
144    returns false. */
145 static bool
146 next_permutation (int *values, size_t cnt)
147 {
148   if (cnt > 0)
149     {
150       size_t i = cnt - 1;
151       while (i != 0)
152         {
153           i--;
154           if (values[i] < values[i + 1])
155             {
156               size_t j;
157               for (j = cnt - 1; values[i] >= values[j]; j--)
158                 continue;
159               swap (values + i, values + j);
160               reverse (values + (i + 1), cnt - (i + 1));
161               return true;
162             }
163         }
164
165       reverse (values, cnt);
166     }
167
168   return false;
169 }
170
171 /* Returns N!. */
172 static unsigned int
173 factorial (unsigned int n)
174 {
175   unsigned int value = 1;
176   while (n > 1)
177     value *= n--;
178   return value;
179 }
180
181 /* Randomly shuffles the CNT elements in ARRAY, each of which is
182    SIZE bytes in size. */
183 static void
184 random_shuffle (void *array_, size_t cnt, size_t size)
185 {
186   char *array = array_;
187   char *tmp = xmalloc (size);
188   size_t i;
189
190   for (i = 0; i < cnt; i++)
191     {
192       size_t j = rand () % (cnt - i) + i;
193       if (i != j)
194         {
195           memcpy (tmp, array + j * size, size);
196           memcpy (array + j * size, array + i * size, size);
197           memcpy (array + i * size, tmp, size);
198         }
199     }
200
201   free (tmp);
202 }
203
204 typedef size_t hash_function (int data);
205
206 static size_t
207 identity_hash (int data) 
208 {
209   return data;
210 }
211
212 static size_t
213 constant_hash (int data UNUSED) 
214 {
215   return 0x12345678u;
216 }
217
218 static inline uint32_t
219 md4_round (uint32_t a, uint32_t b, uint32_t c, uint32_t d,
220            uint32_t data, uint32_t n)
221 {
222   uint32_t x = a + (d ^ (b & (c ^ d))) + data;
223   return (x << n) | (x >> (32 - n));
224 }
225
226 static size_t
227 random_hash (int data)
228 {
229   uint32_t a = data;
230   uint32_t b = data;
231   uint32_t c = data;
232   uint32_t d = data;
233   a = md4_round (a, b, c, d, 0, 3);
234   d = md4_round (d, a, b, c, 1, 7);
235   c = md4_round (c, d, a, b, 2, 11);
236   b = md4_round (b, c, d, a, 3, 19);
237   return a ^ b ^ c ^ d;
238 }
239
240 static struct hmapx_node *
241 find_element (struct hmapx *hmapx, int data, hash_function *hash)
242 {
243   struct hmapx_node *node;
244   struct element *e;
245   HMAPX_FOR_EACH_WITH_HASH (e, node, hash (data), hmapx)
246     if (e->data == data)
247       break;
248   return node;
249 }
250
251 /* Checks that HMAPX contains the CNT ints in DATA, that its
252    structure is correct, and that certain operations on HMAPX
253    produce the expected results. */
254 static void
255 check_hmapx (struct hmapx *hmapx, const int data[], size_t cnt,
256             hash_function *hash)
257 {
258   size_t i, j;
259   int *order;
260
261   check (hmapx_is_empty (hmapx) == (cnt == 0));
262   check (hmapx_count (hmapx) == cnt);
263   check (cnt <= hmapx_capacity (hmapx));
264
265   order = xmemdup (data, cnt * sizeof *data);
266   qsort (order, cnt, sizeof *order, compare_ints);
267
268   for (i = 0; i < cnt; i = j)
269     {
270       struct hmapx_node *node;
271       struct element *e;
272       int count;
273
274       for (j = i + 1; j < cnt; j++)
275         if (order[i] != order[j])
276           break;
277
278       count = 0;
279       HMAPX_FOR_EACH_WITH_HASH (e, node, hash (order[i]), hmapx)
280         if (e->data == order[i]) 
281           count++; 
282
283       check (count == j - i);
284     }
285
286   check (find_element (hmapx, -1, hash) == NULL);
287
288   if (cnt == 0)
289     check (hmapx_first (hmapx) == NULL);
290   else
291     {
292       struct hmapx_node *p;
293       int left;
294
295       left = cnt;
296       for (p = hmapx_first (hmapx), i = 0; i < cnt;
297            p = hmapx_next (hmapx, p), i++)
298         {
299           struct element *e = hmapx_node_data (p);
300           size_t j;
301
302           check (hmapx_node_hash (p) == hash (e->data));
303           for (j = 0; j < left; j++)
304             if (order[j] == e->data) 
305               {
306                 order[j] = order[--left];
307                 goto next;
308               }
309           abort ();
310
311         next: ;
312         }
313       check (p == NULL);
314     }
315
316   free (order);
317 }
318
319 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
320    HMAPX in the order specified by INSERTIONS, then deletes them in
321    the order specified by DELETIONS, checking the HMAPX's contents
322    for correctness after each operation.  Uses HASH as the hash
323    function. */
324 static void
325 test_insert_delete (const int insertions[],
326                     const int deletions[],
327                     size_t cnt,
328                     hash_function *hash,
329                     size_t reserve)
330 {
331   struct element *elements;
332   struct hmapx_node **nodes;
333   struct hmapx hmapx;
334   size_t i;
335
336   elements = xnmalloc (cnt, sizeof *elements);
337   nodes = xnmalloc (cnt, sizeof *nodes);
338   for (i = 0; i < cnt; i++)
339     elements[i].data = i;
340
341   hmapx_init (&hmapx);
342   hmapx_reserve (&hmapx, reserve);
343   check_hmapx (&hmapx, NULL, 0, hash);
344   for (i = 0; i < cnt; i++)
345     {
346       struct hmapx_node *(*insert) (struct hmapx *, void *, size_t hash);
347       size_t capacity;
348
349       /* Insert the node.  Use hmapx_insert_fast if we have not
350          yet exceeded the reserve. */
351       insert = i < reserve ? hmapx_insert_fast : hmapx_insert;
352       nodes[insertions[i]] = insert (&hmapx, &elements[insertions[i]],
353                                      hash (insertions[i]));
354       check_hmapx (&hmapx, insertions, i + 1, hash);
355
356       /* A series of insertions should not produce a shrinkable hmapx. */
357       if (i >= reserve) 
358         {
359           capacity = hmapx_capacity (&hmapx);
360           hmapx_shrink (&hmapx);
361           check (capacity == hmapx_capacity (&hmapx)); 
362         }
363     }
364   for (i = 0; i < cnt; i++)
365     {
366       hmapx_delete (&hmapx, nodes[deletions[i]]);
367       check_hmapx (&hmapx, deletions + i + 1, cnt - i - 1, hash);
368     }
369   hmapx_destroy (&hmapx);
370
371   free (elements);
372   free (nodes);
373 }
374 \f
375 /* Inserts values into an HMAPX in each possible order, then
376    removes them in each possible order, up to a specified maximum
377    size, using hash function HASH. */
378 static void
379 test_insert_any_remove_any (hash_function *hash)
380 {
381   const int max_elems = 5;
382   int cnt;
383
384   for (cnt = 0; cnt <= max_elems; cnt++)
385     {
386       int *insertions, *deletions;
387       unsigned int ins_perm_cnt;
388       int i;
389
390       insertions = xnmalloc (cnt, sizeof *insertions);
391       deletions = xnmalloc (cnt, sizeof *deletions);
392       for (i = 0; i < cnt; i++)
393         insertions[i] = i;
394
395       for (ins_perm_cnt = 0;
396            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
397            ins_perm_cnt++)
398         {
399           unsigned int del_perm_cnt;
400           int i;
401
402           for (i = 0; i < cnt; i++)
403             deletions[i] = i;
404
405           for (del_perm_cnt = 0;
406                del_perm_cnt == 0 || next_permutation (deletions, cnt);
407                del_perm_cnt++)
408             test_insert_delete (insertions, deletions, cnt, hash, 1);
409
410           check (del_perm_cnt == factorial (cnt));
411         }
412       check (ins_perm_cnt == factorial (cnt));
413
414       free (insertions);
415       free (deletions);
416     }
417 }
418
419 static void
420 test_insert_any_remove_any_random_hash (void) 
421 {
422   test_insert_any_remove_any (random_hash);
423 }
424
425 static void
426 test_insert_any_remove_any_identity_hash (void) 
427 {
428   test_insert_any_remove_any (identity_hash);
429 }
430
431 static void
432 test_insert_any_remove_any_constant_hash (void) 
433 {
434   test_insert_any_remove_any (constant_hash);
435 }
436
437 /* Inserts values into an HMAPX in each possible order, then
438    removes them in the same order, up to a specified maximum
439    size, using hash function HASH. */
440 static void
441 test_insert_any_remove_same (hash_function *hash)
442 {
443   const int max_elems = 7;
444   int cnt;
445
446   for (cnt = 0; cnt <= max_elems; cnt++)
447     {
448       int *values;
449       unsigned int permutation_cnt;
450       int i;
451
452       values = xnmalloc (cnt, sizeof *values);
453       for (i = 0; i < cnt; i++)
454         values[i] = i;
455
456       for (permutation_cnt = 0;
457            permutation_cnt == 0 || next_permutation (values, cnt);
458            permutation_cnt++)
459         test_insert_delete (values, values, cnt, hash, cnt / 2);
460       check (permutation_cnt == factorial (cnt));
461
462       free (values);
463     }
464 }
465
466 static void
467 test_insert_any_remove_same_random_hash (void) 
468 {
469   test_insert_any_remove_same (random_hash);
470 }
471
472 static void
473 test_insert_any_remove_same_identity_hash (void) 
474 {
475   test_insert_any_remove_same (identity_hash);
476 }
477
478 static void
479 test_insert_any_remove_same_constant_hash (void) 
480 {
481   test_insert_any_remove_same (constant_hash);
482 }
483
484 /* Inserts values into an HMAPX in each possible order, then
485    removes them in reverse order, up to a specified maximum
486    size, using hash function HASH. */
487 static void
488 test_insert_any_remove_reverse (hash_function *hash)
489 {
490   const int max_elems = 7;
491   int cnt;
492
493   for (cnt = 0; cnt <= max_elems; cnt++)
494     {
495       int *insertions, *deletions;
496       unsigned int permutation_cnt;
497       int i;
498
499       insertions = xnmalloc (cnt, sizeof *insertions);
500       deletions = xnmalloc (cnt, sizeof *deletions);
501       for (i = 0; i < cnt; i++)
502         insertions[i] = i;
503
504       for (permutation_cnt = 0;
505            permutation_cnt == 0 || next_permutation (insertions, cnt);
506            permutation_cnt++)
507         {
508           memcpy (deletions, insertions, sizeof *insertions * cnt);
509           reverse (deletions, cnt);
510
511           test_insert_delete (insertions, deletions, cnt, hash, cnt);
512         }
513       check (permutation_cnt == factorial (cnt));
514
515       free (insertions);
516       free (deletions);
517     }
518 }
519
520 static void
521 test_insert_any_remove_reverse_random_hash (void)
522 {
523   test_insert_any_remove_reverse (random_hash);
524 }
525
526 static void
527 test_insert_any_remove_reverse_identity_hash (void)
528 {
529   test_insert_any_remove_reverse (identity_hash);
530 }
531
532 static void
533 test_insert_any_remove_reverse_constant_hash (void)
534 {
535   test_insert_any_remove_reverse (constant_hash);
536 }
537
538 /* Inserts and removes up to MAX_ELEMS values in an hmapx, in
539    random order, using hash function HASH. */
540 static void
541 test_random_sequence (int max_elems, hash_function *hash)
542 {
543   const int max_trials = 8;
544   int cnt;
545
546   for (cnt = 0; cnt <= max_elems; cnt += 2)
547     {
548       int *insertions, *deletions;
549       int trial;
550       int i;
551
552       insertions = xnmalloc (cnt, sizeof *insertions);
553       deletions = xnmalloc (cnt, sizeof *deletions);
554       for (i = 0; i < cnt; i++)
555         insertions[i] = i;
556       for (i = 0; i < cnt; i++)
557         deletions[i] = i;
558
559       for (trial = 0; trial < max_trials; trial++)
560         {
561           random_shuffle (insertions, cnt, sizeof *insertions);
562           random_shuffle (deletions, cnt, sizeof *deletions);
563
564           test_insert_delete (insertions, deletions, cnt, hash, 0);
565         }
566
567       free (insertions);
568       free (deletions);
569     }
570 }
571
572 static void
573 test_random_sequence_random_hash (void) 
574 {
575   test_random_sequence (64, random_hash);
576 }
577
578 static void
579 test_random_sequence_identity_hash (void) 
580 {
581   test_random_sequence (64, identity_hash);
582 }
583
584 static void
585 test_random_sequence_constant_hash (void) 
586 {
587   test_random_sequence (32, constant_hash);
588 }
589
590 /* Inserts MAX_ELEMS elements into an HMAPX in ascending order,
591    then delete in ascending order and shrink the hmapx at each
592    step, using hash function HASH. */
593 static void
594 test_insert_ordered (int max_elems, hash_function *hash)
595 {
596   struct element *elements;
597   struct hmapx_node **nodes;
598   int *values;
599   struct hmapx hmapx;
600   int i;
601
602   hmapx_init (&hmapx);
603   elements = xnmalloc (max_elems, sizeof *elements);
604   nodes = xnmalloc (max_elems, sizeof *nodes);
605   values = xnmalloc (max_elems, sizeof *values);
606   for (i = 0; i < max_elems; i++)
607     {
608       values[i] = elements[i].data = i;
609       nodes[i] = hmapx_insert (&hmapx, &elements[i], hash (elements[i].data));
610       check_hmapx (&hmapx, values, i + 1, hash);
611
612       if (hash == identity_hash) 
613         {
614           /* Check that every every hash bucket has (almost) the
615              same number of nodes in it.  */
616           int min = INT_MAX;
617           int max = INT_MIN;
618           int j;
619
620           for (j = 0; j <= hmapx.hmap.mask; j++) 
621             {
622               int count = 0;
623               struct hmap_node *node;
624
625               for (node = hmapx.hmap.buckets[j]; node != NULL;
626                    node = node->next)
627                 count++;
628               if (count < min)
629                 min = count;
630               if (count > max)
631                 max = count;
632             }
633           check (max - min <= 1);
634         }
635     }
636   for (i = 0; i < max_elems; i++)
637     {
638       hmapx_delete (&hmapx, nodes[i]);
639       hmapx_shrink (&hmapx);
640       check_hmapx (&hmapx, values + i + 1, max_elems - i - 1, hash);
641     }
642   hmapx_destroy (&hmapx);
643   free (elements);
644   free (nodes);
645   free (values);
646 }
647
648 static void
649 test_insert_ordered_random_hash (void)
650 {
651   test_insert_ordered (1024, random_hash);
652 }
653
654 static void
655 test_insert_ordered_identity_hash (void)
656 {
657   test_insert_ordered (1024, identity_hash);
658 }
659
660 static void
661 test_insert_ordered_constant_hash (void)
662 {
663   test_insert_ordered (128, constant_hash);
664 }
665
666 /* Inserts up to MAX_ELEMS elements into an HMAPX, then moves the
667    nodes around in memory, using hash function HASH. */
668 static void
669 test_moved (int max_elems, hash_function *hash)
670 {
671   struct element *e[2];
672   int cur;
673   int *values;
674   struct hmapx_node **nodes;
675   struct hmapx hmapx;
676   int i, j;
677
678   hmapx_init (&hmapx);
679   e[0] = xnmalloc (max_elems, sizeof *e[0]);
680   e[1] = xnmalloc (max_elems, sizeof *e[1]);
681   values = xnmalloc (max_elems, sizeof *values);
682   nodes = xnmalloc (max_elems, sizeof *nodes);
683   cur = 0;
684   for (i = 0; i < max_elems; i++)
685     {
686       values[i] = e[cur][i].data = i;
687       nodes[i] = hmapx_insert (&hmapx, &e[cur][i], hash (e[cur][i].data));
688       check_hmapx (&hmapx, values, i + 1, hash);
689
690       for (j = 0; j <= i; j++)
691         {
692           e[!cur][j] = e[cur][j];
693           hmapx_move (nodes[j], &e[cur][j]);
694           check_hmapx (&hmapx, values, i + 1, hash);
695         }
696       cur = !cur;
697     }
698   hmapx_destroy (&hmapx);
699   free (e[0]);
700   free (e[1]);
701   free (values);
702   free (nodes);
703 }
704
705 static void
706 test_moved_random_hash (void) 
707 {
708   test_moved (128, random_hash);
709 }
710
711 static void
712 test_moved_identity_hash (void) 
713 {
714   test_moved (128, identity_hash);
715 }
716
717 static void
718 test_moved_constant_hash (void) 
719 {
720   test_moved (32, constant_hash);
721 }
722
723 /* Inserts values into an HMAPX, then changes their values, using
724    hash function HASH. */
725 static void
726 test_changed (hash_function *hash)
727 {
728   const int max_elems = 6;
729   int cnt;
730
731   for (cnt = 0; cnt <= max_elems; cnt++)
732     {
733       int *values, *changed_values;
734       struct hmapx_node **nodes;
735       struct element *elements;
736       unsigned int permutation_cnt;
737       int i;
738
739       values = xnmalloc (cnt, sizeof *values);
740       changed_values = xnmalloc (cnt, sizeof *changed_values);
741       elements = xnmalloc (cnt, sizeof *elements);
742       nodes = xnmalloc (cnt, sizeof *nodes);
743       for (i = 0; i < cnt; i++)
744         values[i] = i;
745
746       for (permutation_cnt = 0;
747            permutation_cnt == 0 || next_permutation (values, cnt);
748            permutation_cnt++)
749         {
750           for (i = 0; i < cnt; i++)
751             {
752               int j, k;
753               for (j = 0; j <= cnt; j++)
754                 {
755                   struct hmapx hmapx;
756
757                   hmapx_init (&hmapx);
758
759                   /* Add to HMAPX in order. */
760                   for (k = 0; k < cnt; k++)
761                     {
762                       int n = values[k];
763                       elements[n].data = n;
764                       nodes[n] = hmapx_insert (&hmapx, &elements[n],
765                                                hash (elements[n].data));
766                     }
767                   check_hmapx (&hmapx, values, cnt, hash);
768
769                   /* Change value i to j. */
770                   elements[i].data = j;
771                   hmapx_changed (&hmapx, nodes[i], 
772                                  hash (elements[i].data));
773                   for (k = 0; k < cnt; k++)
774                     changed_values[k] = k;
775                   changed_values[i] = j;
776                   check_hmapx (&hmapx, changed_values, cnt, hash);
777
778                   hmapx_destroy (&hmapx);
779                 }
780             }
781         }
782       check (permutation_cnt == factorial (cnt));
783
784       free (values);
785       free (changed_values);
786       free (elements);
787       free (nodes);
788     }
789 }
790
791 static void
792 test_changed_random_hash (void)
793 {
794   test_changed (random_hash);
795 }
796
797 static void
798 test_changed_identity_hash (void)
799 {
800   test_changed (identity_hash);
801 }
802
803 static void
804 test_changed_constant_hash (void)
805 {
806   test_changed (constant_hash);
807 }
808
809 /* Inserts values into an HMAPX, then changes and moves their
810    values, using hash function HASH. */
811 static void
812 test_change (hash_function *hash)
813 {
814   const int max_elems = 6;
815   int cnt;
816
817   for (cnt = 0; cnt <= max_elems; cnt++)
818     {
819       int *values, *changed_values;
820       struct hmapx_node **nodes;
821       struct element *elements;
822       struct element replacement;
823       unsigned int permutation_cnt;
824       int i;
825
826       values = xnmalloc (cnt, sizeof *values);
827       changed_values = xnmalloc (cnt, sizeof *changed_values);
828       elements = xnmalloc (cnt, sizeof *elements);
829       nodes = xnmalloc (cnt, sizeof *nodes);
830       for (i = 0; i < cnt; i++)
831         values[i] = i;
832
833       for (permutation_cnt = 0;
834            permutation_cnt == 0 || next_permutation (values, cnt);
835            permutation_cnt++)
836         {
837           for (i = 0; i < cnt; i++)
838             {
839               int j, k;
840               for (j = 0; j <= cnt; j++)
841                 {
842                   struct hmapx hmapx;
843
844                   hmapx_init (&hmapx);
845
846                   /* Add to HMAPX in order. */
847                   for (k = 0; k < cnt; k++)
848                     {
849                       int n = values[k];
850                       elements[n].data = n;
851                       nodes[n] = hmapx_insert (&hmapx, &elements[n],
852                                                hash (elements[n].data));
853                     }
854                   check_hmapx (&hmapx, values, cnt, hash);
855
856                   /* Change value i to j. */
857                   replacement.data = j;
858                   hmapx_change (&hmapx, nodes[i], &replacement, hash (j));
859                   for (k = 0; k < cnt; k++)
860                     changed_values[k] = k;
861                   changed_values[i] = j;
862                   check_hmapx (&hmapx, changed_values, cnt, hash);
863
864                   hmapx_destroy (&hmapx);
865                 }
866             }
867         }
868       check (permutation_cnt == factorial (cnt));
869
870       free (values);
871       free (changed_values);
872       free (elements);
873       free (nodes);
874     }
875 }
876
877 static void
878 test_change_random_hash (void)
879 {
880   test_change (random_hash);
881 }
882
883 static void
884 test_change_identity_hash (void)
885 {
886   test_change (identity_hash);
887 }
888
889 static void
890 test_change_constant_hash (void)
891 {
892   test_change (constant_hash);
893 }
894
895 static void
896 test_swap (int max_elems, hash_function *hash) 
897 {
898   struct element *elements;
899   int *values;
900   struct hmapx a, b;
901   struct hmapx *working, *empty;
902   int i;
903
904   hmapx_init (&a);
905   hmapx_init (&b);
906   working = &a;
907   empty = &b;
908   elements = xnmalloc (max_elems, sizeof *elements);
909   values = xnmalloc (max_elems, sizeof *values);
910   for (i = 0; i < max_elems; i++)
911     {
912       struct hmapx *tmp;
913       values[i] = elements[i].data = i;
914       hmapx_insert (working, &elements[i], hash (elements[i].data));
915       check_hmapx (working, values, i + 1, hash);
916       check_hmapx (empty, NULL, 0, hash);
917       hmapx_swap (&a, &b);
918       tmp = working;
919       working = empty;
920       empty = tmp;
921     }
922   hmapx_destroy (&a);
923   hmapx_destroy (&b);
924   free (elements);
925   free (values);
926 }
927
928 static void
929 test_swap_random_hash (void) 
930 {
931   test_swap (128, random_hash);
932 }
933
934 /* Inserts elements into an HMAPX in ascending order, then clears the hash
935    table using hmapx_clear(). */
936 static void
937 test_clear (void)
938 {
939   const int max_elems = 128;
940   struct element *elements;
941   struct hmapx_node **nodes;
942   int *values;
943   struct hmapx hmapx;
944   int cnt;
945
946   elements = xnmalloc (max_elems, sizeof *elements);
947   nodes = xnmalloc (max_elems, sizeof *nodes);
948   values = xnmalloc (max_elems, sizeof *values);
949
950   hmapx_init (&hmapx);
951   for (cnt = 0; cnt <= max_elems; cnt++)
952     {
953       int i;
954
955       for (i = 0; i < cnt; i++)
956         {
957           values[i] = elements[i].data = i;
958           nodes[i] = hmapx_insert (&hmapx, &elements[i],
959                                    random_hash (elements[i].data));
960           check_hmapx (&hmapx, values, i + 1, random_hash);
961         }
962       hmapx_clear (&hmapx);
963       check_hmapx (&hmapx, NULL, 0, random_hash);
964     }
965   hmapx_destroy (&hmapx);
966
967   free (elements);
968   free (nodes);
969   free (values);
970 }
971
972 static void
973 test_destroy_null (void) 
974 {
975   hmapx_destroy (NULL);
976 }
977
978 /* Test shrinking an empty hash table. */
979 static void
980 test_shrink_empty (void)
981 {
982   struct hmapx hmapx;
983
984   hmapx_init (&hmapx);
985   hmapx_reserve (&hmapx, 123);
986   hmapx_shrink (&hmapx);
987   hmapx_destroy (&hmapx);
988 }
989 \f
990 /* Main program. */
991
992 struct test
993   {
994     const char *name;
995     const char *description;
996     void (*function) (void);
997   };
998
999 static const struct test tests[] =
1000   {
1001     {
1002       "insert-any-remove-any-random-hash",
1003       "insert any order, delete any order (random hash)",
1004       test_insert_any_remove_any_random_hash
1005     },
1006     {
1007       "insert-any-remove-any-identity-hash",
1008       "insert any order, delete any order (identity hash)",
1009       test_insert_any_remove_any_identity_hash
1010     },
1011     {
1012       "insert-any-remove-any-constant-hash",
1013       "insert any order, delete any order (constant hash)",
1014       test_insert_any_remove_any_constant_hash
1015     },
1016     {
1017       "insert-any-remove-same-random-hash",
1018       "insert any order, delete same order (random hash)",
1019       test_insert_any_remove_same_random_hash
1020     },
1021     {
1022       "insert-any-remove-same-identity-hash",
1023       "insert any order, delete same order (identity hash)",
1024       test_insert_any_remove_same_identity_hash
1025     },
1026     {
1027       "insert-any-remove-same-constant-hash",
1028       "insert any order, delete same order (constant hash)",
1029       test_insert_any_remove_same_constant_hash
1030     },
1031     {
1032       "insert-any-remove-reverse-random-hash",
1033       "insert any order, delete reverse order (random hash)",
1034       test_insert_any_remove_reverse_random_hash
1035     },
1036     {
1037       "insert-any-remove-reverse-identity-hash",
1038       "insert any order, delete reverse order (identity hash)",
1039       test_insert_any_remove_reverse_identity_hash
1040     },
1041     {
1042       "insert-any-remove-reverse-constant-hash",
1043       "insert any order, delete reverse order (constant hash)",
1044       test_insert_any_remove_reverse_constant_hash
1045     },
1046     {
1047       "random-sequence-random-hash",
1048       "insert and delete in random sequence (random hash)",
1049       test_random_sequence_random_hash
1050     },
1051     {
1052       "random-sequence-identity-hash",
1053       "insert and delete in random sequence (identity hash)",
1054       test_random_sequence_identity_hash
1055     },
1056     {
1057       "random-sequence-constant-hash",
1058       "insert and delete in random sequence (constant hash)",
1059       test_random_sequence_constant_hash
1060     },
1061     {
1062       "insert-ordered-random-hash",
1063       "insert in ascending order (random hash)",
1064       test_insert_ordered_random_hash
1065     },
1066     {
1067       "insert-ordered-identity-hash",
1068       "insert in ascending order (identity hash)",
1069       test_insert_ordered_identity_hash
1070     },
1071     {
1072       "insert-ordered-constant-hash",
1073       "insert in ascending order (constant hash)",
1074       test_insert_ordered_constant_hash
1075     },
1076     {
1077       "moved-random-hash",
1078       "move elements around in memory (random hash)",
1079       test_moved_random_hash
1080     },
1081     {
1082       "moved-identity-hash",
1083       "move elements around in memory (identity hash)",
1084       test_moved_identity_hash
1085     },
1086     {
1087       "moved-constant-hash",
1088       "move elements around in memory (constant hash)",
1089       test_moved_constant_hash
1090     },
1091     {
1092       "changed-random-hash",
1093       "change key data in nodes (random hash)",
1094       test_changed_random_hash
1095     },
1096     {
1097       "changed-identity-hash",
1098       "change key data in nodes (identity hash)",
1099       test_changed_identity_hash
1100     },
1101     {
1102       "changed-constant-hash",
1103       "change key data in nodes (constant hash)",
1104       test_changed_constant_hash
1105     },
1106     {
1107       "change-random-hash",
1108       "change and move key data in nodes (random hash)",
1109       test_change_random_hash
1110     },
1111     {
1112       "change-identity-hash",
1113       "change and move key data in nodes (identity hash)",
1114       test_change_identity_hash
1115     },
1116     {
1117       "change-constant-hash",
1118       "change and move key data in nodes (constant hash)",
1119       test_change_constant_hash
1120     },
1121     {
1122       "swap-random-hash",
1123       "test swapping tables",
1124       test_swap_random_hash
1125     },
1126     {
1127       "clear",
1128       "test clearing hash table",
1129       test_clear
1130     },
1131     {
1132       "destroy-null",
1133       "test destroying null table",
1134       test_destroy_null
1135     },
1136     {
1137       "shrink-empty",
1138       "test shrinking an empty table",
1139       test_shrink_empty
1140     },
1141   };
1142
1143 enum { N_TESTS = sizeof tests / sizeof *tests };
1144
1145 int
1146 main (int argc, char *argv[])
1147 {
1148   int i;
1149
1150   if (argc != 2)
1151     {
1152       fprintf (stderr, "exactly one argument required; use --help for help\n");
1153       return EXIT_FAILURE;
1154     }
1155   else if (!strcmp (argv[1], "--help"))
1156     {
1157       printf ("%s: test hash map of pointers\n"
1158               "usage: %s TEST-NAME\n"
1159               "where TEST-NAME is one of the following:\n",
1160               argv[0], argv[0]);
1161       for (i = 0; i < N_TESTS; i++)
1162         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
1163       return 0;
1164     }
1165   else
1166     {
1167       for (i = 0; i < N_TESTS; i++)
1168         if (!strcmp (argv[1], tests[i].name))
1169           {
1170             tests[i].function ();
1171             return 0;
1172           }
1173
1174       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
1175       return EXIT_FAILURE;
1176     }
1177 }