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