pintos-os.org Git - pspp/blob - 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 }