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