pintos-os.org Git - pspp/blob - tests/libpspp/string-map-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2008, 2009 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 /* Currently running test. */
  44 static const char *test_name;
  45
  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       printf ("Check failed in %s test at %s, line %d\n",
  62               test_name, __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       sprintf (*s, "%d", idx);
 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 contains the CNT strings in DATA, that its structure is
 269    correct, and that certain operations on MAP produce the expected results. */
 270 static void
 271 check_string_map (struct string_map *map, const int data[], size_t cnt)
 272 {
 273   size_t i;
 274
 275   check (string_map_is_empty (map) == (cnt == 0));
 276   check (string_map_count (map) == cnt);
 277
 278   for (i = 0; i < cnt; i++)
 279     {
 280       struct string_map_node *node;
 281       const char *key = make_key (data[i]);
 282       const char *value = make_value (data[i]);
 283       const char *found_value;
 284
 285       check (string_map_contains (map, key));
 286
 287       node = string_map_find_node (map, key);
 288       check (node != NULL);
 289       check (!strcmp (key, string_map_node_get_key (node)));
 290       check (!strcmp (value, string_map_node_get_value (node)));
 291
 292       check (node == string_map_insert (map, key, "abc"));
 293       check (!strcmp (value, string_map_node_get_value (node)));
 294
 295       check (node == string_map_insert_nocopy (map, xstrdup (key),
 296                                                xstrdup ("def")));
 297       check (!strcmp (value, string_map_node_get_value (node)));
 298
 299       found_value = string_map_find (map, key);
 300       check (found_value != NULL);
 301       check (!strcmp (found_value, value));
 302     }
 303
 304   check (!string_map_contains (map, "xxx"));
 305   check (string_map_find (map, "z") == NULL);
 306   check (string_map_find_node (map, "") == NULL);
 307   check (!string_map_delete (map, "xyz"));
 308
 309   if (cnt == 0)
 310     check (string_map_first (map) == NULL);
 311   else
 312     {
 313       const struct string_map_node *node;
 314       int *data_copy;
 315       int left;
 316
 317       data_copy = xmemdup (data, cnt * sizeof *data);
 318       left = cnt;
 319       for (node = string_map_first (map), i = 0; i < cnt;
 320            node = string_map_next (map, node), i++)
 321         {
 322           const char *key = string_map_node_get_key (node);
 323           const char *value = string_map_node_get_value (node);
 324           size_t j;
 325
 326           for (j = 0; j < left; j++)
 327             if (!strcmp (key, make_key (data_copy[j]))
 328                 || !strcmp (value, make_value (data_copy[j])))
 329               {
 330                 data_copy[j] = data_copy[--left];
 331                 goto next;
 332               }
 333           check_die ();
 334
 335         next: ;
 336         }
 337       check (node == NULL);
 338       free (data_copy);
 339     }
 340 }
 341
 342 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a map in the
 343    order specified by INSERTIONS, then deletes them in the order specified by
 344    DELETIONS, checking the map's contents for correctness after each
 345    operation.  */
 346 static void
 347 test_insert_delete (const int insertions[],
 348                     const int deletions[],
 349                     size_t cnt)
 350 {
 351   struct string_map map;
 352   size_t i;
 353
 354   string_map_init (&map);
 355   check_string_map (&map, NULL, 0);
 356   for (i = 0; i < cnt; i++)
 357     {
 358       check (string_map_insert (&map, make_key (insertions[i]),
 359                                 make_value (insertions[i])));
 360       check_string_map (&map, insertions, i + 1);
 361     }
 362   for (i = 0; i < cnt; i++)
 363     {
 364       check (string_map_delete (&map, make_key (deletions[i])));
 365       check_string_map (&map, deletions + i + 1, cnt - i - 1);
 366     }
 367   string_map_destroy (&map);
 368 }
 369 \f
 370 /* Inserts strings into a map in each possible order, then removes them in each
 371    possible order, up to a specified maximum size. */
 372 static void
 373 test_insert_any_remove_any (void)
 374 {
 375   const int basis = 0;
 376   const int max_elems = 5;
 377   int cnt;
 378
 379   for (cnt = 0; cnt <= max_elems; cnt++)
 380     {
 381       int *insertions, *deletions;
 382       unsigned int ins_perm_cnt;
 383       int i;
 384
 385       insertions = xnmalloc (cnt, sizeof *insertions);
 386       deletions = xnmalloc (cnt, sizeof *deletions);
 387       for (i = 0; i < cnt; i++)
 388         insertions[i] = i | random_value (i, basis);
 389
 390       for (ins_perm_cnt = 0;
 391            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
 392            ins_perm_cnt++)
 393         {
 394           unsigned int del_perm_cnt;
 395           int i;
 396
 397           for (i = 0; i < cnt; i++)
 398             deletions[i] = i | random_value (i, basis);
 399
 400           for (del_perm_cnt = 0;
 401                del_perm_cnt == 0 || next_permutation (deletions, cnt);
 402                del_perm_cnt++)
 403             test_insert_delete (insertions, deletions, cnt);
 404
 405           check (del_perm_cnt == factorial (cnt));
 406         }
 407       check (ins_perm_cnt == factorial (cnt));
 408
 409       free (insertions);
 410       free (deletions);
 411     }
 412 }
 413
 414 /* Inserts strings into a map in each possible order, then removes them in the
 415    same order, up to a specified maximum size. */
 416 static void
 417 test_insert_any_remove_same (void)
 418 {
 419   const int max_elems = 7;
 420   int cnt;
 421
 422   for (cnt = 0; cnt <= max_elems; cnt++)
 423     {
 424       int *values;
 425       unsigned int permutation_cnt;
 426       int i;
 427
 428       values = xnmalloc (cnt, sizeof *values);
 429       for (i = 0; i < cnt; i++)
 430         values[i] = i | random_value (i, 1);
 431
 432       for (permutation_cnt = 0;
 433            permutation_cnt == 0 || next_permutation (values, cnt);
 434            permutation_cnt++)
 435         test_insert_delete (values, values, cnt);
 436       check (permutation_cnt == factorial (cnt));
 437
 438       free (values);
 439     }
 440 }
 441
 442 /* Inserts strings into a map in each possible order, then
 443    removes them in reverse order, up to a specified maximum
 444    size. */
 445 static void
 446 test_insert_any_remove_reverse (void)
 447 {
 448   const int max_elems = 7;
 449   int cnt;
 450
 451   for (cnt = 0; cnt <= max_elems; cnt++)
 452     {
 453       int *insertions, *deletions;
 454       unsigned int permutation_cnt;
 455       int i;
 456
 457       insertions = xnmalloc (cnt, sizeof *insertions);
 458       deletions = xnmalloc (cnt, sizeof *deletions);
 459       for (i = 0; i < cnt; i++)
 460         insertions[i] = i | random_value (i, 2);
 461
 462       for (permutation_cnt = 0;
 463            permutation_cnt == 0 || next_permutation (insertions, cnt);
 464            permutation_cnt++)
 465         {
 466           memcpy (deletions, insertions, sizeof *insertions * cnt);
 467           reverse (deletions, cnt);
 468
 469           test_insert_delete (insertions, deletions, cnt);
 470         }
 471       check (permutation_cnt == factorial (cnt));
 472
 473       free (insertions);
 474       free (deletions);
 475     }
 476 }
 477
 478 /* Inserts and removes strings in a map, in random order. */
 479 static void
 480 test_random_sequence (void)
 481 {
 482   const int basis = 3;
 483   const int max_elems = 64;
 484   const int max_trials = 8;
 485   int cnt;
 486
 487   for (cnt = 0; cnt <= max_elems; cnt += 2)
 488     {
 489       int *insertions, *deletions;
 490       int trial;
 491       int i;
 492
 493       insertions = xnmalloc (cnt, sizeof *insertions);
 494       deletions = xnmalloc (cnt, sizeof *deletions);
 495       for (i = 0; i < cnt; i++)
 496         insertions[i] = i | random_value (i, basis);
 497       for (i = 0; i < cnt; i++)
 498         deletions[i] = i | random_value (i, basis);
 499
 500       for (trial = 0; trial < max_trials; trial++)
 501         {
 502           random_shuffle (insertions, cnt, sizeof *insertions);
 503           random_shuffle (deletions, cnt, sizeof *deletions);
 504
 505           test_insert_delete (insertions, deletions, cnt);
 506         }
 507
 508       free (insertions);
 509       free (deletions);
 510     }
 511 }
 512
 513 /* Inserts strings into a map in ascending order, then delete in ascending
 514    order. */
 515 static void
 516 test_insert_ordered (void)
 517 {
 518   const int max_elems = 64;
 519   int *values;
 520   struct string_map map;
 521   int i;
 522
 523   string_map_init (&map);
 524   values = xnmalloc (max_elems, sizeof *values);
 525   for (i = 0; i < max_elems; i++)
 526     {
 527       values[i] = i | random_value (i, 4);
 528       string_map_insert_nocopy (&map, xstrdup (make_key (values[i])),
 529                                 xstrdup (make_value (values[i])));
 530       check_string_map (&map, values, i + 1);
 531     }
 532   for (i = 0; i < max_elems; i++)
 533     {
 534       string_map_delete (&map, make_key (i));
 535       check_string_map (&map, values + i + 1, max_elems - i - 1);
 536     }
 537   string_map_destroy (&map);
 538   free (values);
 539 }
 540
 541 /* Inserts and replaces strings in a map, in random order. */
 542 static void
 543 test_replace (void)
 544 {
 545   const int basis = 15;
 546   enum { MAX_ELEMS = 16 };
 547   const int max_trials = 8;
 548   int cnt;
 549
 550   for (cnt = 0; cnt <= MAX_ELEMS; cnt++)
 551     {
 552       int insertions[MAX_ELEMS];
 553       int trial;
 554       int i;
 555
 556       for (i = 0; i < cnt; i++)
 557         insertions[i] = (i / 2) | random_value (i, basis);
 558
 559       for (trial = 0; trial < max_trials; trial++)
 560         {
 561           struct string_map map;
 562           int data[MAX_ELEMS];
 563           int n_data;
 564
 565           /* Insert with replacement in random order. */
 566           n_data = 0;
 567           string_map_init (&map);
 568           random_shuffle (insertions, cnt, sizeof *insertions);
 569           for (i = 0; i < cnt; i++)
 570             {
 571               const char *key = make_key (insertions[i]);
 572               const char *value = make_value (insertions[i]);
 573               int j;
 574
 575               for (j = 0; j < n_data; j++)
 576                 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
 577                   {
 578                     data[j] = insertions[i];
 579                     goto found;
 580                   }
 581               data[n_data++] = insertions[i];
 582             found:
 583
 584               if (i % 2)
 585                 string_map_replace (&map, key, value);
 586               else
 587                 string_map_replace_nocopy (&map,
 588                                            xstrdup (key), xstrdup (value));
 589               check_string_map (&map, data, n_data);
 590             }
 591
 592           /* Delete in original order. */
 593           for (i = 0; i < cnt; i++)
 594             {
 595               const char *expected_value;
 596               char *value;
 597               int j;
 598
 599               expected_value = NULL;
 600               for (j = 0; j < n_data; j++)
 601                 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
 602                   {
 603                     expected_value = make_value (data[j]);
 604                     data[j] = data[--n_data];
 605                     break;
 606                   }
 607
 608               value = string_map_find_and_delete (&map,
 609                                                   make_key (insertions[i]));
 610               check ((value != NULL) == (expected_value != NULL));
 611               check (value == NULL || !strcmp (value, expected_value));
 612               free (value);
 613             }
 614           assert (string_map_is_empty (&map));
 615
 616           string_map_destroy (&map);
 617         }
 618     }
 619 }
 620
 621 static void
 622 make_patterned_map (struct string_map *map, unsigned int pattern, int basis,
 623                     int insertions[], int *np)
 624 {
 625   int n;
 626   int i;
 627
 628   string_map_init (map);
 629
 630   n = 0;
 631   for (i = 0; pattern != 0; i++)
 632     if (pattern & (1u << i))
 633       {
 634         pattern &= pattern - 1;
 635         insertions[n] = i | random_value (i, basis);
 636         check (string_map_insert (map, make_key (insertions[n]),
 637                                   make_value (insertions[n])));
 638         n++;
 639       }
 640   check_string_map (map, insertions, n);
 641
 642   *np = n;
 643 }
 644
 645 static void
 646 for_each_map (void (*cb)(struct string_map *, int data[], int n),
 647               int basis)
 648 {
 649   enum { MAX_ELEMS = 5 };
 650   unsigned int pattern;
 651
 652   for (pattern = 0; pattern < (1u << MAX_ELEMS); pattern++)
 653     {
 654       int data[MAX_ELEMS];
 655       struct string_map map;
 656       int n;
 657
 658       make_patterned_map (&map, pattern, basis, data, &n);
 659       (*cb) (&map, data, n);
 660       string_map_destroy (&map);
 661     }
 662 }
 663
 664 static void
 665 for_each_pair_of_maps (
 666   void (*cb)(struct string_map *a, int a_data[], int n_a,
 667              struct string_map *b, int b_data[], int n_b),
 668   int a_basis, int b_basis)
 669 {
 670   enum { MAX_ELEMS = 5 };
 671   unsigned int a_pattern, b_pattern;
 672
 673   for (a_pattern = 0; a_pattern < (1u << MAX_ELEMS); a_pattern++)
 674     for (b_pattern = 0; b_pattern < (1u << MAX_ELEMS); b_pattern++)
 675       {
 676         int a_data[MAX_ELEMS], b_data[MAX_ELEMS];
 677         struct string_map a_map, b_map;
 678         int n_a, n_b;
 679
 680         make_patterned_map (&a_map, a_pattern, a_basis, a_data, &n_a);
 681         make_patterned_map (&b_map, b_pattern, b_basis, b_data, &n_b);
 682         (*cb) (&a_map, a_data, n_a, &b_map, b_data, n_b);
 683         string_map_destroy (&a_map);
 684         string_map_destroy (&b_map);
 685       }
 686 }
 687
 688 static void
 689 clear_cb (struct string_map *map, int data[] UNUSED, int n UNUSED)
 690 {
 691   string_map_clear (map);
 692   check_string_map (map, NULL, 0);
 693 }
 694
 695 static void
 696 test_clear (void)
 697 {
 698   for_each_map (clear_cb, 5);
 699 }
 700
 701 static void
 702 clone_cb (struct string_map *map, int data[], int n)
 703 {
 704   struct string_map clone;
 705
 706   string_map_clone (&clone, map);
 707   check_string_map (&clone, data, n);
 708   string_map_destroy (&clone);
 709 }
 710
 711 static void
 712 test_clone (void)
 713 {
 714   for_each_map (clone_cb, 6);
 715 }
 716
 717 static void
 718 node_swap_value_cb (struct string_map *map, int data[], int n)
 719 {
 720   int i;
 721
 722   for (i = 0; i < n; i++)
 723     {
 724       const char *value = make_value (data[i]);
 725       struct string_map_node *node;
 726       char *old_value;
 727
 728       node = string_map_find_node (map, make_key (data[i]));
 729       check (node != NULL);
 730       check (!strcmp (string_map_node_get_value (node), value));
 731       data[i] = (data[i] & KEY_MASK) | random_value (i, 15);
 732       old_value = string_map_node_swap_value (node, make_value (data[i]));
 733       check (old_value != NULL);
 734       check (!strcmp (value, old_value));
 735       free (old_value);
 736     }
 737 }
 738
 739 static void
 740 test_node_swap_value (void)
 741 {
 742   for_each_map (node_swap_value_cb, 14);
 743 }
 744
 745 static void
 746 swap_cb (struct string_map *a, int a_data[], int n_a,
 747          struct string_map *b, int b_data[], int n_b)
 748 {
 749   string_map_swap (a, b);
 750   check_string_map (a, b_data, n_b);
 751   check_string_map (b, a_data, n_a);
 752 }
 753
 754 static void
 755 test_swap (void)
 756 {
 757   for_each_pair_of_maps (swap_cb, 7, 8);
 758 }
 759
 760 static void
 761 insert_map_cb (struct string_map *a, int a_data[], int n_a,
 762                struct string_map *b, int b_data[], int n_b)
 763 {
 764   int i, j;
 765
 766   string_map_insert_map (a, b);
 767
 768   for (i = 0; i < n_b; i++)
 769     {
 770       for (j = 0; j < n_a; j++)
 771         if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
 772           goto found;
 773       a_data[n_a++] = b_data[i];
 774     found:;
 775     }
 776   check_string_map (a, a_data, n_a);
 777   check_string_map (b, b_data, n_b);
 778 }
 779
 780 static void
 781 test_insert_map (void)
 782 {
 783   for_each_pair_of_maps (insert_map_cb, 91, 10);
 784 }
 785
 786 static void
 787 replace_map_cb (struct string_map *a, int a_data[], int n_a,
 788                struct string_map *b, int b_data[], int n_b)
 789 {
 790   int i, j;
 791
 792   string_map_replace_map (a, b);
 793
 794   for (i = 0; i < n_b; i++)
 795     {
 796       for (j = 0; j < n_a; j++)
 797         if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
 798           {
 799             a_data[j] = (a_data[j] & KEY_MASK) | (b_data[i] & VALUE_MASK);
 800             goto found;
 801           }
 802       a_data[n_a++] = b_data[i];
 803     found:;
 804     }
 805   check_string_map (a, a_data, n_a);
 806   check_string_map (b, b_data, n_b);
 807 }
 808
 809 static void
 810 test_replace_map (void)
 811 {
 812   for_each_pair_of_maps (replace_map_cb, 11, 12);
 813 }
 814
 815 static void
 816 check_set (struct string_set *set, const int *data, int n_data,
 817            int mask, int shift)
 818 {
 819   int *unique;
 820   int n_unique;
 821   int i;
 822
 823   n_unique = 0;
 824   unique = xmalloc (n_data * sizeof *unique);
 825   for (i = 0; i < n_data; i++)
 826     {
 827       int idx = (data[i] & mask) >> shift;
 828       int j;
 829
 830       for (j = 0; j < n_unique; j++)
 831         if (unique[j] == idx)
 832           goto found;
 833       unique[n_unique++] = idx;
 834     found:;
 835     }
 836
 837   check (string_set_count (set) == n_unique);
 838   for (i = 0; i < n_unique; i++)
 839     check (string_set_contains (set, get_string (unique[i])));
 840   string_set_destroy (set);
 841   free (unique);
 842 }
 843
 844 static void
 845 get_keys_and_values_cb (struct string_map *map, int data[], int n)
 846 {
 847   struct string_set keys, values;
 848
 849   string_set_init (&keys);
 850   string_set_init (&values);
 851   string_map_get_keys (map, &keys);
 852   string_map_get_values (map, &values);
 853   check_set (&keys, data, n, KEY_MASK, KEY_SHIFT);
 854   check_set (&values, data, n, VALUE_MASK, VALUE_SHIFT);
 855 }
 856
 857 static void
 858 test_get_keys_and_values (void)
 859 {
 860   for_each_map (get_keys_and_values_cb, 13);
 861 }
 862
 863 static void
 864 test_destroy_null (void)
 865 {
 866   string_map_destroy (NULL);
 867 }
 868 \f
 869 /* Main program. */
 870
 871 /* Runs TEST_FUNCTION and prints a message about NAME. */
 872 static void
 873 run_test (void (*test_function) (void), const char *name)
 874 {
 875   test_name = name;
 876   putchar ('.');
 877   fflush (stdout);
 878   test_function ();
 879 }
 880
 881 int
 882 main (void)
 883 {
 884   run_test (test_insert_any_remove_any, "insert any order, delete any order");
 885   run_test (test_insert_any_remove_same,
 886             "insert any order, delete same order");
 887   run_test (test_insert_any_remove_reverse,
 888             "insert any order, delete reverse order");
 889   run_test (test_random_sequence, "insert and delete in random sequence");
 890   run_test (test_replace, "insert and replace in random sequence");
 891   run_test (test_insert_ordered, "insert in ascending order");
 892   run_test (test_clear, "clear");
 893   run_test (test_clone, "clone");
 894   run_test (test_swap, "swap");
 895   run_test (test_node_swap_value, "node_swap_value");
 896   run_test (test_insert_map, "insert_map");
 897   run_test (test_replace_map, "replace_map");
 898   run_test (test_get_keys_and_values, "get keys and values");
 899   run_test (test_destroy_null, "destroying null table");
 900
 901   putchar ('\n');
 902
 903   free_strings ();
 904
 905   return 0;
 906 }