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 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 }