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