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