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