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