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