psppire-import-assistant (struct _PsppireImportAssistant): Remove unused member.
[pspp] / tests / libpspp / string-map-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 string_map_* routines defined in
18    string-map.c.  This test program aims to be as comprehensive as possible.
19    "gcov -a -b" should report almost complete coverage of lines, blocks and
20    branches in string-map.c, except that one branch caused by hash collision is
21    not exercised because our hash function has so few collisions.  "valgrind
22    --leak-check=yes --show-reachable=yes" should give a clean report. */
23
24 #ifdef HAVE_CONFIG_H
25 #include <config.h>
26 #endif
27
28 #include <libpspp/string-map.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/hash-functions.h>
40 #include <libpspp/compiler.h>
41 #include <libpspp/string-set.h>
42 \f
43 /* Exit with a failure code.
44    (Place a breakpoint on this function while debugging.) */
45 static void
46 check_die (void)
47 {
48   exit (EXIT_FAILURE);
49 }
50
51 /* If OK is not true, prints a message about failure on the
52    current source file and the given LINE and terminates. */
53 static void
54 check_func (bool ok, int line)
55 {
56   if (!ok)
57     {
58       fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
59       check_die ();
60     }
61 }
62
63 /* Verifies that EXPR evaluates to true.
64    If not, prints a message citing the calling line number and
65    terminates. */
66 #define check(EXPR) check_func ((EXPR), __LINE__)
67
68 /* Prints a message about memory exhaustion and exits with a
69    failure code. */
70 static void
71 xalloc_die (void)
72 {
73   printf ("virtual memory exhausted\n");
74   exit (EXIT_FAILURE);
75 }
76
77 static void *xmalloc (size_t n) MALLOC_LIKE;
78 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
79 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
80
81 /* Allocates and returns N bytes of memory. */
82 static void *
83 xmalloc (size_t n)
84 {
85   if (n != 0)
86     {
87       void *p = malloc (n);
88       if (p == NULL)
89         xalloc_die ();
90
91       return p;
92     }
93   else
94     return NULL;
95 }
96
97 static void *
98 xmemdup (const void *p, size_t n)
99 {
100   void *q = xmalloc (n);
101   memcpy (q, p, n);
102   return q;
103 }
104
105 /* Clone STRING.  */
106 static char *
107 xstrdup (const char *string)
108 {
109   return xmemdup (string, strlen (string) + 1);
110 }
111
112 /* Allocates and returns N * M bytes of memory. */
113 static void *
114 xnmalloc (size_t n, size_t m)
115 {
116   if ((size_t) -1 / m <= n)
117     xalloc_die ();
118   return xmalloc (n * m);
119 }
120 \f
121 /* Support routines. */
122
123 enum {
124   IDX_BITS = 10,
125   MAX_IDX = 1 << IDX_BITS,
126   KEY_MASK = (MAX_IDX - 1),
127   KEY_SHIFT = 0,
128   VALUE_MASK = (MAX_IDX - 1) << IDX_BITS,
129   VALUE_SHIFT = IDX_BITS
130 };
131
132 static char *string_table[MAX_IDX];
133
134 static const char *
135 get_string (int idx)
136 {
137   char **s;
138
139   assert (idx >= 0 && idx < MAX_IDX);
140   s = &string_table[idx];
141   if (*s == NULL)
142     {
143       *s = xmalloc (16);
144       sprintf (*s, "%d", idx);
145     }
146   return *s;
147 }
148
149 static void
150 free_strings (void)
151 {
152   int i;
153
154   for (i = 0; i < MAX_IDX; i++)
155     free (string_table[i]);
156 }
157
158 static const char *
159 make_key (int value)
160 {
161   return get_string ((value & KEY_MASK) >> KEY_SHIFT);
162 }
163
164 static const char *
165 make_value (int value)
166 {
167   return get_string ((value & VALUE_MASK) >> VALUE_SHIFT);
168 }
169
170 static int
171 random_value (unsigned int seed, int basis)
172 {
173   return hash_int (seed, basis) & VALUE_MASK;
174 }
175
176 /* Swaps *A and *B. */
177 static void
178 swap (int *a, int *b)
179 {
180   int t = *a;
181   *a = *b;
182   *b = t;
183 }
184
185 /* Reverses the order of the CNT integers starting at VALUES. */
186 static void
187 reverse (int *values, size_t cnt)
188 {
189   size_t i = 0;
190   size_t j = cnt;
191
192   while (j > i)
193     swap (&values[i++], &values[--j]);
194 }
195
196 /* Arranges the CNT elements in VALUES into the lexicographically next greater
197    permutation.  Returns true if successful.  If VALUES is already the
198    lexicographically greatest permutation of its elements (i.e. ordered from
199    greatest to smallest), arranges them into the lexicographically least
200    permutation (i.e. ordered from smallest to largest) and returns false.
201
202    Comparisons among elements of VALUES consider only the bits in KEY_MASK. */
203 static bool
204 next_permutation (int *values, size_t cnt)
205 {
206   if (cnt > 0)
207     {
208       size_t i = cnt - 1;
209       while (i != 0)
210         {
211           i--;
212           if ((values[i] & KEY_MASK) < (values[i + 1] & KEY_MASK))
213             {
214               size_t j;
215               for (j = cnt - 1;
216                    (values[i] & KEY_MASK) >= (values[j] & KEY_MASK);
217                    j--)
218                 continue;
219               swap (values + i, values + j);
220               reverse (values + (i + 1), cnt - (i + 1));
221               return true;
222             }
223         }
224
225       reverse (values, cnt);
226     }
227
228   return false;
229 }
230
231 /* Returns N!. */
232 static unsigned int
233 factorial (unsigned int n)
234 {
235   unsigned int value = 1;
236   while (n > 1)
237     value *= n--;
238   return value;
239 }
240
241 /* Randomly shuffles the CNT elements in ARRAY, each of which is
242    SIZE bytes in size. */
243 static void
244 random_shuffle (void *array_, size_t cnt, size_t size)
245 {
246   char *array = array_;
247   char *tmp = xmalloc (size);
248   size_t i;
249
250   for (i = 0; i < cnt; i++)
251     {
252       size_t j = rand () % (cnt - i) + i;
253       if (i != j)
254         {
255           memcpy (tmp, array + j * size, size);
256           memcpy (array + j * size, array + i * size, size);
257           memcpy (array + i * size, tmp, size);
258         }
259     }
260
261   free (tmp);
262 }
263
264 /* Checks that MAP contains the CNT strings in DATA, that its structure is
265    correct, and that certain operations on MAP produce the expected results. */
266 static void
267 check_string_map (struct string_map *map, const int data[], size_t cnt)
268 {
269   size_t i;
270
271   check (string_map_is_empty (map) == (cnt == 0));
272   check (string_map_count (map) == cnt);
273
274   for (i = 0; i < cnt; i++)
275     {
276       struct string_map_node *node;
277       const char *key = make_key (data[i]);
278       const char *value = make_value (data[i]);
279       const char *found_value;
280
281       check (string_map_contains (map, key));
282
283       node = string_map_find_node (map, key);
284       check (node != NULL);
285       check (!strcmp (key, string_map_node_get_key (node)));
286       check (!strcmp (value, string_map_node_get_value (node)));
287
288       check (node == string_map_insert (map, key, "abc"));
289       check (!strcmp (value, string_map_node_get_value (node)));
290
291       check (node == string_map_insert_nocopy (map, xstrdup (key),
292                                                xstrdup ("def")));
293       check (!strcmp (value, string_map_node_get_value (node)));
294
295       found_value = string_map_find (map, key);
296       check (found_value != NULL);
297       check (!strcmp (found_value, value));
298     }
299
300   check (!string_map_contains (map, "xxx"));
301   check (string_map_find (map, "z") == NULL);
302   check (string_map_find_node (map, "") == NULL);
303   check (!string_map_delete (map, "xyz"));
304
305   if (cnt == 0)
306     check (string_map_first (map) == NULL);
307   else
308     {
309       const struct string_map_node *node;
310       int *data_copy;
311       int left;
312
313       data_copy = xmemdup (data, cnt * sizeof *data);
314       left = cnt;
315       for (node = string_map_first (map), i = 0; i < cnt;
316            node = string_map_next (map, node), i++)
317         {
318           const char *key = string_map_node_get_key (node);
319           const char *value = string_map_node_get_value (node);
320           size_t j;
321
322           for (j = 0; j < left; j++)
323             if (!strcmp (key, make_key (data_copy[j]))
324                 || !strcmp (value, make_value (data_copy[j])))
325               {
326                 data_copy[j] = data_copy[--left];
327                 goto next;
328               }
329           check_die ();
330
331         next: ;
332         }
333       check (node == NULL);
334       free (data_copy);
335     }
336 }
337
338 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a map in the
339    order specified by INSERTIONS, then deletes them in the order specified by
340    DELETIONS, checking the map's contents for correctness after each
341    operation.  */
342 static void
343 test_insert_delete (const int insertions[],
344                     const int deletions[],
345                     size_t cnt)
346 {
347   struct string_map map;
348   size_t i;
349
350   string_map_init (&map);
351   check_string_map (&map, NULL, 0);
352   for (i = 0; i < cnt; i++)
353     {
354       check (string_map_insert (&map, make_key (insertions[i]),
355                                 make_value (insertions[i])));
356       check_string_map (&map, insertions, i + 1);
357     }
358   for (i = 0; i < cnt; i++)
359     {
360       check (string_map_delete (&map, make_key (deletions[i])));
361       check_string_map (&map, deletions + i + 1, cnt - i - 1);
362     }
363   string_map_destroy (&map);
364 }
365 \f
366 /* Inserts strings into a map in each possible order, then removes them in each
367    possible order, up to a specified maximum size. */
368 static void
369 test_insert_any_remove_any (void)
370 {
371   const int basis = 0;
372   const int max_elems = 5;
373   int cnt;
374
375   for (cnt = 0; cnt <= max_elems; cnt++)
376     {
377       int *insertions, *deletions;
378       unsigned int ins_perm_cnt;
379       int i;
380
381       insertions = xnmalloc (cnt, sizeof *insertions);
382       deletions = xnmalloc (cnt, sizeof *deletions);
383       for (i = 0; i < cnt; i++)
384         insertions[i] = i | random_value (i, basis);
385
386       for (ins_perm_cnt = 0;
387            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
388            ins_perm_cnt++)
389         {
390           unsigned int del_perm_cnt;
391           int i;
392
393           for (i = 0; i < cnt; i++)
394             deletions[i] = i | random_value (i, basis);
395
396           for (del_perm_cnt = 0;
397                del_perm_cnt == 0 || next_permutation (deletions, cnt);
398                del_perm_cnt++)
399             test_insert_delete (insertions, deletions, cnt);
400
401           check (del_perm_cnt == factorial (cnt));
402         }
403       check (ins_perm_cnt == factorial (cnt));
404
405       free (insertions);
406       free (deletions);
407     }
408 }
409
410 /* Inserts strings into a map in each possible order, then removes them in the
411    same order, up to a specified maximum size. */
412 static void
413 test_insert_any_remove_same (void)
414 {
415   const int max_elems = 7;
416   int cnt;
417
418   for (cnt = 0; cnt <= max_elems; cnt++)
419     {
420       int *values;
421       unsigned int permutation_cnt;
422       int i;
423
424       values = xnmalloc (cnt, sizeof *values);
425       for (i = 0; i < cnt; i++)
426         values[i] = i | random_value (i, 1);
427
428       for (permutation_cnt = 0;
429            permutation_cnt == 0 || next_permutation (values, cnt);
430            permutation_cnt++)
431         test_insert_delete (values, values, cnt);
432       check (permutation_cnt == factorial (cnt));
433
434       free (values);
435     }
436 }
437
438 /* Inserts strings into a map in each possible order, then
439    removes them in reverse order, up to a specified maximum
440    size. */
441 static void
442 test_insert_any_remove_reverse (void)
443 {
444   const int max_elems = 7;
445   int cnt;
446
447   for (cnt = 0; cnt <= max_elems; cnt++)
448     {
449       int *insertions, *deletions;
450       unsigned int permutation_cnt;
451       int i;
452
453       insertions = xnmalloc (cnt, sizeof *insertions);
454       deletions = xnmalloc (cnt, sizeof *deletions);
455       for (i = 0; i < cnt; i++)
456         insertions[i] = i | random_value (i, 2);
457
458       for (permutation_cnt = 0;
459            permutation_cnt == 0 || next_permutation (insertions, cnt);
460            permutation_cnt++)
461         {
462           memcpy (deletions, insertions, sizeof *insertions * cnt);
463           reverse (deletions, cnt);
464
465           test_insert_delete (insertions, deletions, cnt);
466         }
467       check (permutation_cnt == factorial (cnt));
468
469       free (insertions);
470       free (deletions);
471     }
472 }
473
474 /* Inserts and removes strings in a map, in random order. */
475 static void
476 test_random_sequence (void)
477 {
478   const int basis = 3;
479   const int max_elems = 64;
480   const int max_trials = 8;
481   int cnt;
482
483   for (cnt = 0; cnt <= max_elems; cnt += 2)
484     {
485       int *insertions, *deletions;
486       int trial;
487       int i;
488
489       insertions = xnmalloc (cnt, sizeof *insertions);
490       deletions = xnmalloc (cnt, sizeof *deletions);
491       for (i = 0; i < cnt; i++)
492         insertions[i] = i | random_value (i, basis);
493       for (i = 0; i < cnt; i++)
494         deletions[i] = i | random_value (i, basis);
495
496       for (trial = 0; trial < max_trials; trial++)
497         {
498           random_shuffle (insertions, cnt, sizeof *insertions);
499           random_shuffle (deletions, cnt, sizeof *deletions);
500
501           test_insert_delete (insertions, deletions, cnt);
502         }
503
504       free (insertions);
505       free (deletions);
506     }
507 }
508
509 /* Inserts strings into a map in ascending order, then delete in ascending
510    order. */
511 static void
512 test_insert_ordered (void)
513 {
514   const int max_elems = 64;
515   int *values;
516   struct string_map map;
517   int i;
518
519   string_map_init (&map);
520   values = xnmalloc (max_elems, sizeof *values);
521   for (i = 0; i < max_elems; i++)
522     {
523       values[i] = i | random_value (i, 4);
524       string_map_insert_nocopy (&map, xstrdup (make_key (values[i])),
525                                 xstrdup (make_value (values[i])));
526       check_string_map (&map, values, i + 1);
527     }
528   for (i = 0; i < max_elems; i++)
529     {
530       string_map_delete (&map, make_key (i));
531       check_string_map (&map, values + i + 1, max_elems - i - 1);
532     }
533   string_map_destroy (&map);
534   free (values);
535 }
536
537 /* Inserts and replaces strings in a map, in random order. */
538 static void
539 test_replace (void)
540 {
541   const int basis = 15;
542   enum { MAX_ELEMS = 16 };
543   const int max_trials = 8;
544   int cnt;
545
546   for (cnt = 0; cnt <= MAX_ELEMS; cnt++)
547     {
548       int insertions[MAX_ELEMS];
549       int trial;
550       int i;
551
552       for (i = 0; i < cnt; i++)
553         insertions[i] = (i / 2) | random_value (i, basis);
554
555       for (trial = 0; trial < max_trials; trial++)
556         {
557           struct string_map map;
558           int data[MAX_ELEMS];
559           int n_data;
560
561           /* Insert with replacement in random order. */
562           n_data = 0;
563           string_map_init (&map);
564           random_shuffle (insertions, cnt, sizeof *insertions);
565           for (i = 0; i < cnt; i++)
566             {
567               const char *key = make_key (insertions[i]);
568               const char *value = make_value (insertions[i]);
569               int j;
570
571               for (j = 0; j < n_data; j++)
572                 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
573                   {
574                     data[j] = insertions[i];
575                     goto found;
576                   }
577               data[n_data++] = insertions[i];
578             found:
579
580               if (i % 2)
581                 string_map_replace (&map, key, value);
582               else
583                 string_map_replace_nocopy (&map,
584                                            xstrdup (key), xstrdup (value));
585               check_string_map (&map, data, n_data);
586             }
587
588           /* Delete in original order. */
589           for (i = 0; i < cnt; i++)
590             {
591               const char *expected_value;
592               char *value;
593               int j;
594
595               expected_value = NULL;
596               for (j = 0; j < n_data; j++)
597                 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
598                   {
599                     expected_value = make_value (data[j]);
600                     data[j] = data[--n_data];
601                     break;
602                   }
603
604               value = string_map_find_and_delete (&map,
605                                                   make_key (insertions[i]));
606               check ((value != NULL) == (expected_value != NULL));
607               check (value == NULL || !strcmp (value, expected_value));
608               free (value);
609             }
610           assert (string_map_is_empty (&map));
611
612           string_map_destroy (&map);
613         }
614     }
615 }
616
617 static void
618 make_patterned_map (struct string_map *map, unsigned int pattern, int basis,
619                     int insertions[], int *np)
620 {
621   int n;
622   int i;
623
624   string_map_init (map);
625
626   n = 0;
627   for (i = 0; pattern != 0; i++)
628     if (pattern & (1u << i))
629       {
630         pattern &= pattern - 1;
631         insertions[n] = i | random_value (i, basis);
632         check (string_map_insert (map, make_key (insertions[n]),
633                                   make_value (insertions[n])));
634         n++;
635       }
636   check_string_map (map, insertions, n);
637
638   *np = n;
639 }
640
641 static void
642 for_each_map (void (*cb)(struct string_map *, int data[], int n),
643               int basis)
644 {
645   enum { MAX_ELEMS = 5 };
646   unsigned int pattern;
647
648   for (pattern = 0; pattern < (1u << MAX_ELEMS); pattern++)
649     {
650       int data[MAX_ELEMS];
651       struct string_map map;
652       int n;
653
654       make_patterned_map (&map, pattern, basis, data, &n);
655       (*cb) (&map, data, n);
656       string_map_destroy (&map);
657     }
658 }
659
660 static void
661 for_each_pair_of_maps (
662   void (*cb)(struct string_map *a, int a_data[], int n_a,
663              struct string_map *b, int b_data[], int n_b),
664   int a_basis, int b_basis)
665 {
666   enum { MAX_ELEMS = 5 };
667   unsigned int a_pattern, b_pattern;
668
669   for (a_pattern = 0; a_pattern < (1u << MAX_ELEMS); a_pattern++)
670     for (b_pattern = 0; b_pattern < (1u << MAX_ELEMS); b_pattern++)
671       {
672         int a_data[MAX_ELEMS], b_data[MAX_ELEMS];
673         struct string_map a_map, b_map;
674         int n_a, n_b;
675
676         make_patterned_map (&a_map, a_pattern, a_basis, a_data, &n_a);
677         make_patterned_map (&b_map, b_pattern, b_basis, b_data, &n_b);
678         (*cb) (&a_map, a_data, n_a, &b_map, b_data, n_b);
679         string_map_destroy (&a_map);
680         string_map_destroy (&b_map);
681       }
682 }
683
684 static void
685 clear_cb (struct string_map *map, int data[] UNUSED, int n UNUSED)
686 {
687   string_map_clear (map);
688   check_string_map (map, NULL, 0);
689 }
690
691 static void
692 test_clear (void)
693 {
694   for_each_map (clear_cb, 5);
695 }
696
697 static void
698 clone_cb (struct string_map *map, int data[], int n)
699 {
700   struct string_map clone;
701
702   string_map_clone (&clone, map);
703   check_string_map (&clone, data, n);
704   string_map_destroy (&clone);
705 }
706
707 static void
708 test_clone (void)
709 {
710   for_each_map (clone_cb, 6);
711 }
712
713 static void
714 node_swap_value_cb (struct string_map *map, int data[], int n)
715 {
716   int i;
717
718   for (i = 0; i < n; i++)
719     {
720       const char *value = make_value (data[i]);
721       struct string_map_node *node;
722       char *old_value;
723
724       node = string_map_find_node (map, make_key (data[i]));
725       check (node != NULL);
726       check (!strcmp (string_map_node_get_value (node), value));
727       data[i] = (data[i] & KEY_MASK) | random_value (i, 15);
728       old_value = string_map_node_swap_value (node, make_value (data[i]));
729       check (old_value != NULL);
730       check (!strcmp (value, old_value));
731       free (old_value);
732     }
733 }
734
735 static void
736 test_node_swap_value (void)
737 {
738   for_each_map (node_swap_value_cb, 14);
739 }
740
741 static void
742 swap_cb (struct string_map *a, int a_data[], int n_a,
743          struct string_map *b, int b_data[], int n_b)
744 {
745   string_map_swap (a, b);
746   check_string_map (a, b_data, n_b);
747   check_string_map (b, a_data, n_a);
748 }
749
750 static void
751 test_swap (void)
752 {
753   for_each_pair_of_maps (swap_cb, 7, 8);
754 }
755
756 static void
757 insert_map_cb (struct string_map *a, int a_data[], int n_a,
758                struct string_map *b, int b_data[], int n_b)
759 {
760   int i, j;
761
762   string_map_insert_map (a, b);
763
764   for (i = 0; i < n_b; i++)
765     {
766       for (j = 0; j < n_a; j++)
767         if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
768           goto found;
769       a_data[n_a++] = b_data[i];
770     found:;
771     }
772   check_string_map (a, a_data, n_a);
773   check_string_map (b, b_data, n_b);
774 }
775
776 static void
777 test_insert_map (void)
778 {
779   for_each_pair_of_maps (insert_map_cb, 91, 10);
780 }
781
782 static void
783 replace_map_cb (struct string_map *a, int a_data[], int n_a,
784                struct string_map *b, int b_data[], int n_b)
785 {
786   int i, j;
787
788   string_map_replace_map (a, b);
789
790   for (i = 0; i < n_b; i++)
791     {
792       for (j = 0; j < n_a; j++)
793         if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
794           {
795             a_data[j] = (a_data[j] & KEY_MASK) | (b_data[i] & VALUE_MASK);
796             goto found;
797           }
798       a_data[n_a++] = b_data[i];
799     found:;
800     }
801   check_string_map (a, a_data, n_a);
802   check_string_map (b, b_data, n_b);
803 }
804
805 static void
806 test_replace_map (void)
807 {
808   for_each_pair_of_maps (replace_map_cb, 11, 12);
809 }
810
811 static void
812 check_set (struct string_set *set, const int *data, int n_data,
813            int mask, int shift)
814 {
815   int *unique;
816   int n_unique;
817   int i;
818
819   n_unique = 0;
820   unique = xmalloc (n_data * sizeof *unique);
821   for (i = 0; i < n_data; i++)
822     {
823       int idx = (data[i] & mask) >> shift;
824       int j;
825
826       for (j = 0; j < n_unique; j++)
827         if (unique[j] == idx)
828           goto found;
829       unique[n_unique++] = idx;
830     found:;
831     }
832
833   check (string_set_count (set) == n_unique);
834   for (i = 0; i < n_unique; i++)
835     check (string_set_contains (set, get_string (unique[i])));
836   string_set_destroy (set);
837   free (unique);
838 }
839
840 static void
841 get_keys_and_values_cb (struct string_map *map, int data[], int n)
842 {
843   struct string_set keys, values;
844
845   string_set_init (&keys);
846   string_set_init (&values);
847   string_map_get_keys (map, &keys);
848   string_map_get_values (map, &values);
849   check_set (&keys, data, n, KEY_MASK, KEY_SHIFT);
850   check_set (&values, data, n, VALUE_MASK, VALUE_SHIFT);
851 }
852
853 static void
854 test_get_keys_and_values (void)
855 {
856   for_each_map (get_keys_and_values_cb, 13);
857 }
858
859 static void
860 test_destroy_null (void)
861 {
862   string_map_destroy (NULL);
863 }
864 \f
865 /* Main program. */
866
867 struct test
868   {
869     const char *name;
870     const char *description;
871     void (*function) (void);
872   };
873
874 static const struct test tests[] =
875   {
876     {
877       "insert-any-remove-any",
878       "insert any order, delete any order",
879       test_insert_any_remove_any
880     },
881     {
882       "insert-any-remove-same",
883       "insert any order, delete same order",
884       test_insert_any_remove_same
885     },
886     {
887       "insert-any-remove-reverse",
888       "insert any order, delete reverse order",
889       test_insert_any_remove_reverse
890     },
891     {
892       "random-sequence",
893       "insert and delete in random sequence",
894       test_random_sequence
895     },
896     {
897       "replace",
898       "insert and replace in random sequence",
899       test_replace
900     },
901     {
902       "insert-ordered",
903       "insert in ascending order",
904       test_insert_ordered
905     },
906     {
907       "clear",
908       "clear",
909       test_clear
910     },
911     {
912       "clone",
913       "clone",
914       test_clone
915     },
916     {
917       "swap",
918       "swap",
919       test_swap
920     },
921     {
922       "node-swap-value",
923       "node_swap_value",
924       test_node_swap_value
925     },
926     {
927       "insert-map",
928       "insert_map",
929       test_insert_map
930     },
931     {
932       "replace-map",
933       "replace_map",
934       test_replace_map
935     },
936     {
937       "get-keys-and-values",
938       "get keys and values",
939       test_get_keys_and_values
940     },
941     {
942       "destroy-null",
943       "destroying null table",
944       test_destroy_null
945     },
946   };
947
948 enum { N_TESTS = sizeof tests / sizeof *tests };
949
950 int
951 main (int argc, char *argv[])
952 {
953   int i;
954
955   if (argc != 2)
956     {
957       fprintf (stderr, "exactly one argument required; use --help for help\n");
958       return EXIT_FAILURE;
959     }
960   else if (!strcmp (argv[1], "--help"))
961     {
962       printf ("%s: test string map library\n"
963               "usage: %s TEST-NAME\n"
964               "where TEST-NAME is one of the following:\n",
965               argv[0], argv[0]);
966       for (i = 0; i < N_TESTS; i++)
967         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
968       return 0;
969     }
970   else
971     {
972       for (i = 0; i < N_TESTS; i++)
973         if (!strcmp (argv[1], tests[i].name))
974           {
975             tests[i].function ();
976             free_strings ();
977             return 0;
978           }
979
980       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
981       return EXIT_FAILURE;
982     }
983 }