tests/libpspp/hmap-test.c

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2008 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 hmap_* routines defined in
  18    hmap.c.  This test program aims to be as comprehensive as
  19    possible.  "gcov -a -b" should report 100% coverage of lines,
  20    blocks and branches in hmap.c (when compiled with -DNDEBUG).
  21    "valgrind --leak-check=yes --show-reachable=yes" should give a
  22    clean report. */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include <config.h>
  26 #endif
  27
  28 #include <libpspp/hmap.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/compiler.h>
  40 \f
  41 /* Currently running test. */
  42 static const char *test_name;
  43
  44 /* Exit with a failure code.
  45    (Place a breakpoint on this function while debugging.) */
  46 static void
  47 check_die (void)
  48 {
  49   exit (EXIT_FAILURE);
  50 }
  51
  52 /* If OK is not true, prints a message about failure on the
  53    current source file and the given LINE and terminates. */
  54 static void
  55 check_func (bool ok, int line)
  56 {
  57   if (!ok)
  58     {
  59       printf ("Check failed in %s test at %s, line %d\n",
  60               test_name, __FILE__, line);
  61       check_die ();
  62     }
  63 }
  64
  65 /* Verifies that EXPR evaluates to true.
  66    If not, prints a message citing the calling line number and
  67    terminates. */
  68 #define check(EXPR) check_func ((EXPR), __LINE__)
  69
  70 /* Prints a message about memory exhaustion and exits with a
  71    failure code. */
  72 static void
  73 xalloc_die (void)
  74 {
  75   printf ("virtual memory exhausted\n");
  76   exit (EXIT_FAILURE);
  77 }
  78
  79 /* Allocates and returns N bytes of memory. */
  80 static void *
  81 xmalloc (size_t n)
  82 {
  83   if (n != 0)
  84     {
  85       void *p = malloc (n);
  86       if (p == NULL)
  87         xalloc_die ();
  88
  89       return p;
  90     }
  91   else
  92     return NULL;
  93 }
  94
  95 static void *
  96 xmemdup (const void *p, size_t n)
  97 {
  98   void *q = xmalloc (n);
  99   memcpy (q, p, n);
 100   return q;
 101 }
 102
 103 /* Allocates and returns N * M bytes of memory. */
 104 static void *
 105 xnmalloc (size_t n, size_t m)
 106 {
 107   if ((size_t) -1 / m <= n)
 108     xalloc_die ();
 109   return xmalloc (n * m);
 110 }
 111 \f
 112 /* Node type and support routines. */
 113
 114 /* Test data element. */
 115 struct element
 116   {
 117     struct hmap_node node;    /* Embedded hash table element. */
 118     int data;                 /* Primary value. */
 119   };
 120
 121 /* Returns the `struct element' that NODE is embedded within. */
 122 static struct element *
 123 hmap_node_to_element (const struct hmap_node *node)
 124 {
 125   return HMAP_DATA (node, struct element, node);
 126 }
 127
 128 /* Compares A and B and returns a strcmp-type return value. */
 129 static int
 130 compare_ints (const void *a_, const void *b_)
 131 {
 132   const int *a = a_;
 133   const int *b = b_;
 134
 135   return *a < *b ? -1 : *a > *b;
 136 }
 137
 138 /* Swaps *A and *B. */
 139 static void
 140 swap (int *a, int *b)
 141 {
 142   int t = *a;
 143   *a = *b;
 144   *b = t;
 145 }
 146
 147 /* Reverses the order of the CNT integers starting at VALUES. */
 148 static void
 149 reverse (int *values, size_t cnt)
 150 {
 151   size_t i = 0;
 152   size_t j = cnt;
 153
 154   while (j > i)
 155     swap (&values[i++], &values[--j]);
 156 }
 157
 158 /* Arranges the CNT elements in VALUES into the lexicographically
 159    next greater permutation.  Returns true if successful.
 160    If VALUES is already the lexicographically greatest
 161    permutation of its elements (i.e. ordered from greatest to
 162    smallest), arranges them into the lexicographically least
 163    permutation (i.e. ordered from smallest to largest) and
 164    returns false. */
 165 static bool
 166 next_permutation (int *values, size_t cnt)
 167 {
 168   if (cnt > 0)
 169     {
 170       size_t i = cnt - 1;
 171       while (i != 0)
 172         {
 173           i--;
 174           if (values[i] < values[i + 1])
 175             {
 176               size_t j;
 177               for (j = cnt - 1; values[i] >= values[j]; j--)
 178                 continue;
 179               swap (values + i, values + j);
 180               reverse (values + (i + 1), cnt - (i + 1));
 181               return true;
 182             }
 183         }
 184
 185       reverse (values, cnt);
 186     }
 187
 188   return false;
 189 }
 190
 191 /* Returns N!. */
 192 static unsigned int
 193 factorial (unsigned int n)
 194 {
 195   unsigned int value = 1;
 196   while (n > 1)
 197     value *= n--;
 198   return value;
 199 }
 200
 201 /* Randomly shuffles the CNT elements in ARRAY, each of which is
 202    SIZE bytes in size. */
 203 static void
 204 random_shuffle (void *array_, size_t cnt, size_t size)
 205 {
 206   char *array = array_;
 207   char *tmp = xmalloc (size);
 208   size_t i;
 209
 210   for (i = 0; i < cnt; i++)
 211     {
 212       size_t j = rand () % (cnt - i) + i;
 213       if (i != j)
 214         {
 215           memcpy (tmp, array + j * size, size);
 216           memcpy (array + j * size, array + i * size, size);
 217           memcpy (array + i * size, tmp, size);
 218         }
 219     }
 220
 221   free (tmp);
 222 }
 223
 224 typedef size_t hash_function (int data);
 225
 226 static size_t
 227 identity_hash (int data)
 228 {
 229   return data;
 230 }
 231
 232 static size_t
 233 constant_hash (int data UNUSED)
 234 {
 235   return 0x12345678u;
 236 }
 237
 238 static inline uint32_t
 239 md4_round (uint32_t a, uint32_t b, uint32_t c, uint32_t d,
 240            uint32_t data, uint32_t n)
 241 {
 242   uint32_t x = a + (d ^ (b & (c ^ d))) + data;
 243   return (x << n) | (x >> (32 - n));
 244 }
 245
 246 static size_t
 247 random_hash (int data)
 248 {
 249   uint32_t a = data;
 250   uint32_t b = data;
 251   uint32_t c = data;
 252   uint32_t d = data;
 253   a = md4_round (a, b, c, d, 0, 3);
 254   d = md4_round (d, a, b, c, 1, 7);
 255   c = md4_round (c, d, a, b, 2, 11);
 256   b = md4_round (b, c, d, a, 3, 19);
 257   return a ^ b ^ c ^ d;
 258 }
 259
 260 static struct hmap_node *
 261 find_element (struct hmap *hmap, int data, hash_function *hash)
 262 {
 263   struct element *e;
 264   HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (data), hmap)
 265     if (e->data == data)
 266       break;
 267   return &e->node;
 268 }
 269
 270 /* Checks that HMAP contains the CNT ints in DATA, that its
 271    structure is correct, and that certain operations on HMAP
 272    produce the expected results. */
 273 static void
 274 check_hmap (struct hmap *hmap, const int data[], size_t cnt,
 275             hash_function *hash)
 276 {
 277   size_t i, j;
 278   int *order;
 279
 280   check (hmap_count (hmap) == cnt);
 281   check (cnt <= hmap_capacity (hmap));
 282
 283   order = xmemdup (data, cnt * sizeof *data);
 284   qsort (order, cnt, sizeof *order, compare_ints);
 285
 286   for (i = 0; i < cnt; i = j)
 287     {
 288       struct element *e;
 289       int count;
 290
 291       for (j = i + 1; j < cnt; j++)
 292         if (order[i] != order[j])
 293           break;
 294
 295       count = 0;
 296       HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (order[i]), hmap)
 297         if (e->data == order[i])
 298           count++;
 299
 300       check (count == j - i);
 301     }
 302
 303   check (find_element (hmap, -1, hash) == NULL);
 304
 305   if (cnt == 0)
 306     check (hmap_first (hmap) == NULL);
 307   else
 308     {
 309       struct hmap_node *p;
 310       int left;
 311
 312       left = cnt;
 313       for (p = hmap_first (hmap), i = 0; i < cnt; p = hmap_next (hmap, p), i++)
 314         {
 315           struct element *e = hmap_node_to_element (p);
 316           size_t j;
 317
 318           check (hmap_node_hash (&e->node) == hash (e->data));
 319           for (j = 0; j < left; j++)
 320             if (order[j] == e->data)
 321               {
 322                 order[j] = order[--left];
 323                 goto next;
 324               }
 325           check_die ();
 326
 327         next: ;
 328         }
 329       check (p == NULL);
 330     }
 331
 332   free (order);
 333 }
 334
 335 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
 336    HMAP in the order specified by INSERTIONS, then deletes them in
 337    the order specified by DELETIONS, checking the HMAP's contents
 338    for correctness after each operation.  Uses HASH as the hash
 339    function. */
 340 static void
 341 test_insert_delete (const int insertions[],
 342                     const int deletions[],
 343                     size_t cnt,
 344                     hash_function *hash)
 345 {
 346   struct element *elements;
 347   struct hmap hmap;
 348   size_t i;
 349
 350   elements = xnmalloc (cnt, sizeof *elements);
 351   for (i = 0; i < cnt; i++)
 352     elements[i].data = i;
 353
 354   hmap_init (&hmap);
 355   hmap_reserve (&hmap, 1);
 356   check_hmap (&hmap, NULL, 0, hash);
 357   for (i = 0; i < cnt; i++)
 358     {
 359       size_t capacity;
 360       hmap_insert (&hmap, &elements[insertions[i]].node, hash (insertions[i]));
 361       check_hmap (&hmap, insertions, i + 1, hash);
 362
 363       /* A series of insertions should not produce a shrinkable hmap. */
 364       capacity = hmap_capacity (&hmap);
 365       hmap_shrink (&hmap);
 366       check (capacity == hmap_capacity (&hmap));
 367     }
 368   for (i = 0; i < cnt; i++)
 369     {
 370       hmap_delete (&hmap, &elements[deletions[i]].node);
 371       check_hmap (&hmap, deletions + i + 1, cnt - i - 1, hash);
 372     }
 373   hmap_destroy (&hmap);
 374
 375   free (elements);
 376 }
 377 \f
 378 /* Inserts values into an HMAP in each possible order, then
 379    removes them in each possible order, up to a specified maximum
 380    size, using hash function HASH. */
 381 static void
 382 test_insert_any_remove_any (hash_function *hash)
 383 {
 384   const int max_elems = 5;
 385   int cnt;
 386
 387   for (cnt = 0; cnt <= max_elems; cnt++)
 388     {
 389       int *insertions, *deletions;
 390       unsigned int ins_perm_cnt;
 391       int i;
 392
 393       insertions = xnmalloc (cnt, sizeof *insertions);
 394       deletions = xnmalloc (cnt, sizeof *deletions);
 395       for (i = 0; i < cnt; i++)
 396         insertions[i] = i;
 397
 398       for (ins_perm_cnt = 0;
 399            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
 400            ins_perm_cnt++)
 401         {
 402           unsigned int del_perm_cnt;
 403           int i;
 404
 405           for (i = 0; i < cnt; i++)
 406             deletions[i] = i;
 407
 408           for (del_perm_cnt = 0;
 409                del_perm_cnt == 0 || next_permutation (deletions, cnt);
 410                del_perm_cnt++)
 411             test_insert_delete (insertions, deletions, cnt, hash);
 412
 413           check (del_perm_cnt == factorial (cnt));
 414         }
 415       check (ins_perm_cnt == factorial (cnt));
 416
 417       free (insertions);
 418       free (deletions);
 419     }
 420 }
 421
 422 static void
 423 test_insert_any_remove_any_random_hash (void)
 424 {
 425   test_insert_any_remove_any (random_hash);
 426 }
 427
 428 static void
 429 test_insert_any_remove_any_identity_hash (void)
 430 {
 431   test_insert_any_remove_any (identity_hash);
 432 }
 433
 434 static void
 435 test_insert_any_remove_any_constant_hash (void)
 436 {
 437   test_insert_any_remove_any (constant_hash);
 438 }
 439
 440 /* Inserts values into an HMAP in each possible order, then
 441    removes them in the same order, up to a specified maximum
 442    size, using hash function HASH. */
 443 static void
 444 test_insert_any_remove_same (hash_function *hash)
 445 {
 446   const int max_elems = 7;
 447   int cnt;
 448
 449   for (cnt = 0; cnt <= max_elems; cnt++)
 450     {
 451       int *values;
 452       unsigned int permutation_cnt;
 453       int i;
 454
 455       values = xnmalloc (cnt, sizeof *values);
 456       for (i = 0; i < cnt; i++)
 457         values[i] = i;
 458
 459       for (permutation_cnt = 0;
 460            permutation_cnt == 0 || next_permutation (values, cnt);
 461            permutation_cnt++)
 462         test_insert_delete (values, values, cnt, hash);
 463       check (permutation_cnt == factorial (cnt));
 464
 465       free (values);
 466     }
 467 }
 468
 469 static void
 470 test_insert_any_remove_same_random_hash (void)
 471 {
 472   test_insert_any_remove_same (random_hash);
 473 }
 474
 475 static void
 476 test_insert_any_remove_same_identity_hash (void)
 477 {
 478   test_insert_any_remove_same (identity_hash);
 479 }
 480
 481 static void
 482 test_insert_any_remove_same_constant_hash (void)
 483 {
 484   test_insert_any_remove_same (constant_hash);
 485 }
 486
 487 /* Inserts values into an HMAP in each possible order, then
 488    removes them in reverse order, up to a specified maximum
 489    size, using hash function HASH. */
 490 static void
 491 test_insert_any_remove_reverse (hash_function *hash)
 492 {
 493   const int max_elems = 7;
 494   int cnt;
 495
 496   for (cnt = 0; cnt <= max_elems; cnt++)
 497     {
 498       int *insertions, *deletions;
 499       unsigned int permutation_cnt;
 500       int i;
 501
 502       insertions = xnmalloc (cnt, sizeof *insertions);
 503       deletions = xnmalloc (cnt, sizeof *deletions);
 504       for (i = 0; i < cnt; i++)
 505         insertions[i] = i;
 506
 507       for (permutation_cnt = 0;
 508            permutation_cnt == 0 || next_permutation (insertions, cnt);
 509            permutation_cnt++)
 510         {
 511           memcpy (deletions, insertions, sizeof *insertions * cnt);
 512           reverse (deletions, cnt);
 513
 514           test_insert_delete (insertions, deletions, cnt, hash);
 515         }
 516       check (permutation_cnt == factorial (cnt));
 517
 518       free (insertions);
 519       free (deletions);
 520     }
 521 }
 522
 523 static void
 524 test_insert_any_remove_reverse_random_hash (void)
 525 {
 526   test_insert_any_remove_reverse (random_hash);
 527 }
 528
 529 static void
 530 test_insert_any_remove_reverse_identity_hash (void)
 531 {
 532   test_insert_any_remove_reverse (identity_hash);
 533 }
 534
 535 static void
 536 test_insert_any_remove_reverse_constant_hash (void)
 537 {
 538   test_insert_any_remove_reverse (constant_hash);
 539 }
 540
 541 /* Inserts and removes up to MAX_ELEMS values in an hmap, in
 542    random order, using hash function HASH. */
 543 static void
 544 test_random_sequence (int max_elems, hash_function *hash)
 545 {
 546   const int max_trials = 8;
 547   int cnt;
 548
 549   for (cnt = 0; cnt <= max_elems; cnt += 2)
 550     {
 551       int *insertions, *deletions;
 552       int trial;
 553       int i;
 554
 555       insertions = xnmalloc (cnt, sizeof *insertions);
 556       deletions = xnmalloc (cnt, sizeof *deletions);
 557       for (i = 0; i < cnt; i++)
 558         insertions[i] = i;
 559       for (i = 0; i < cnt; i++)
 560         deletions[i] = i;
 561
 562       for (trial = 0; trial < max_trials; trial++)
 563         {
 564           random_shuffle (insertions, cnt, sizeof *insertions);
 565           random_shuffle (deletions, cnt, sizeof *deletions);
 566
 567           test_insert_delete (insertions, deletions, cnt, hash);
 568         }
 569
 570       free (insertions);
 571       free (deletions);
 572     }
 573 }
 574
 575 static void
 576 test_random_sequence_random_hash (void)
 577 {
 578   test_random_sequence (64, random_hash);
 579 }
 580
 581 static void
 582 test_random_sequence_identity_hash (void)
 583 {
 584   test_random_sequence (64, identity_hash);
 585 }
 586
 587 static void
 588 test_random_sequence_constant_hash (void)
 589 {
 590   test_random_sequence (32, constant_hash);
 591 }
 592
 593 /* Inserts MAX_ELEMS elements into an HMAP in ascending order,
 594    then delete in ascending order and shrink the hmap at each
 595    step, using hash function HASH. */
 596 static void
 597 test_insert_ordered (int max_elems, hash_function *hash)
 598 {
 599   struct element *elements;
 600   int *values;
 601   struct hmap hmap;
 602   int i;
 603
 604   hmap_init (&hmap);
 605   elements = xnmalloc (max_elems, sizeof *elements);
 606   values = xnmalloc (max_elems, sizeof *values);
 607   for (i = 0; i < max_elems; i++)
 608     {
 609       values[i] = elements[i].data = i;
 610       hmap_insert (&hmap, &elements[i].node, hash (elements[i].data));
 611       check_hmap (&hmap, values, i + 1, hash);
 612
 613       if (hash == identity_hash)
 614         {
 615           /* Check that every every hash bucket has (almost) the
 616              same number of nodes in it.  */
 617           int min = INT_MAX;
 618           int max = INT_MIN;
 619           int j;
 620
 621           for (j = 0; j <= hmap.mask; j++)
 622             {
 623               int count = 0;
 624               struct hmap_node *node;
 625
 626               for (node = hmap.buckets[j]; node != NULL; node = node->next)
 627                 count++;
 628               if (count < min)
 629                 min = count;
 630               if (count > max)
 631                 max = count;
 632             }
 633           check (max - min <= 1);
 634         }
 635     }
 636   for (i = 0; i < max_elems; i++)
 637     {
 638       hmap_delete (&hmap, &elements[i].node);
 639       hmap_shrink (&hmap);
 640       check_hmap (&hmap, values + i + 1, max_elems - i - 1, hash);
 641     }
 642   hmap_destroy (&hmap);
 643   free (elements);
 644   free (values);
 645 }
 646
 647 static void
 648 test_insert_ordered_random_hash (void)
 649 {
 650   test_insert_ordered (1024, random_hash);
 651 }
 652
 653 static void
 654 test_insert_ordered_identity_hash (void)
 655 {
 656   test_insert_ordered (1024, identity_hash);
 657 }
 658
 659 static void
 660 test_insert_ordered_constant_hash (void)
 661 {
 662   test_insert_ordered (128, constant_hash);
 663 }
 664
 665 /* Inserts up to MAX_ELEMS elements into an HMAP, then moves the
 666    nodes around in memory, using hash function HASH. */
 667 static void
 668 test_moved (int max_elems, hash_function *hash)
 669 {
 670   struct element *e[2];
 671   int cur;
 672   int *values;
 673   struct hmap hmap;
 674   int i, j;
 675
 676   hmap_init (&hmap);
 677   e[0] = xnmalloc (max_elems, sizeof *e[0]);
 678   e[1] = xnmalloc (max_elems, sizeof *e[1]);
 679   values = xnmalloc (max_elems, sizeof *values);
 680   cur = 0;
 681   for (i = 0; i < max_elems; i++)
 682     {
 683       values[i] = e[cur][i].data = i;
 684       hmap_insert (&hmap, &e[cur][i].node, hash (e[cur][i].data));
 685       check_hmap (&hmap, values, i + 1, hash);
 686
 687       for (j = 0; j <= i; j++)
 688         {
 689           e[!cur][j] = e[cur][j];
 690           hmap_moved (&hmap, &e[!cur][j].node, &e[cur][j].node);
 691           check_hmap (&hmap, values, i + 1, hash);
 692         }
 693       cur = !cur;
 694     }
 695   hmap_destroy (&hmap);
 696   free (e[0]);
 697   free (e[1]);
 698   free (values);
 699 }
 700
 701 static void
 702 test_moved_random_hash (void)
 703 {
 704   test_moved (128, random_hash);
 705 }
 706
 707 static void
 708 test_moved_identity_hash (void)
 709 {
 710   test_moved (128, identity_hash);
 711 }
 712
 713 static void
 714 test_moved_constant_hash (void)
 715 {
 716   test_moved (32, constant_hash);
 717 }
 718
 719 /* Inserts values into an HMAP, then changes their values, using
 720    hash function HASH. */
 721 static void
 722 test_changed (hash_function *hash)
 723 {
 724   const int max_elems = 6;
 725   int cnt;
 726
 727   for (cnt = 0; cnt <= max_elems; cnt++)
 728     {
 729       int *values, *changed_values;
 730       struct element *elements;
 731       unsigned int permutation_cnt;
 732       int i;
 733
 734       values = xnmalloc (cnt, sizeof *values);
 735       changed_values = xnmalloc (cnt, sizeof *changed_values);
 736       elements = xnmalloc (cnt, sizeof *elements);
 737       for (i = 0; i < cnt; i++)
 738         values[i] = i;
 739
 740       for (permutation_cnt = 0;
 741            permutation_cnt == 0 || next_permutation (values, cnt);
 742            permutation_cnt++)
 743         {
 744           for (i = 0; i < cnt; i++)
 745             {
 746               int j, k;
 747               for (j = 0; j <= cnt; j++)
 748                 {
 749                   struct hmap hmap;
 750
 751                   hmap_init (&hmap);
 752
 753                   /* Add to HMAP in order. */
 754                   for (k = 0; k < cnt; k++)
 755                     {
 756                       int n = values[k];
 757                       elements[n].data = n;
 758                       hmap_insert (&hmap, &elements[n].node,
 759                                    hash (elements[n].data));
 760                     }
 761                   check_hmap (&hmap, values, cnt, hash);
 762
 763                   /* Change value i to j. */
 764                   elements[i].data = j;
 765                   hmap_changed (&hmap, &elements[i].node,
 766                                 hash (elements[i].data));
 767                   for (k = 0; k < cnt; k++)
 768                     changed_values[k] = k;
 769                   changed_values[i] = j;
 770                   check_hmap (&hmap, changed_values, cnt, hash);
 771
 772                   hmap_destroy (&hmap);
 773                 }
 774             }
 775         }
 776       check (permutation_cnt == factorial (cnt));
 777
 778       free (values);
 779       free (changed_values);
 780       free (elements);
 781     }
 782 }
 783
 784 static void
 785 test_changed_random_hash (void)
 786 {
 787   test_changed (random_hash);
 788 }
 789
 790 static void
 791 test_changed_identity_hash (void)
 792 {
 793   test_changed (identity_hash);
 794 }
 795
 796 static void
 797 test_changed_constant_hash (void)
 798 {
 799   test_changed (constant_hash);
 800 }
 801
 802 static void
 803 test_swap (int max_elems, hash_function *hash)
 804 {
 805   struct element *elements;
 806   int *values;
 807   struct hmap a, b;
 808   struct hmap *working, *empty;
 809   int i;
 810
 811   hmap_init (&a);
 812   hmap_init (&b);
 813   working = &a;
 814   empty = &b;
 815   elements = xnmalloc (max_elems, sizeof *elements);
 816   values = xnmalloc (max_elems, sizeof *values);
 817   for (i = 0; i < max_elems; i++)
 818     {
 819       struct hmap *tmp;
 820       values[i] = elements[i].data = i;
 821       hmap_insert (working, &elements[i].node, hash (elements[i].data));
 822       check_hmap (working, values, i + 1, hash);
 823       check_hmap (empty, NULL, 0, hash);
 824       hmap_swap (&a, &b);
 825       tmp = working;
 826       working = empty;
 827       empty = tmp;
 828     }
 829   hmap_destroy (&a);
 830   hmap_destroy (&b);
 831   free (elements);
 832   free (values);
 833 }
 834
 835 static void
 836 test_swap_random_hash (void)
 837 {
 838   test_swap (128, random_hash);
 839 }
 840
 841 static void
 842 test_destroy_null (void)
 843 {
 844   hmap_destroy (NULL);
 845 }
 846
 847 /* Test shrinking an empty hash table. */
 848 static void
 849 test_shrink_empty (void)
 850 {
 851   struct hmap hmap;
 852
 853   hmap_init (&hmap);
 854   hmap_reserve (&hmap, 123);
 855   hmap_shrink (&hmap);
 856   hmap_destroy (&hmap);
 857 }
 858 \f
 859 /* Main program. */
 860
 861 /* Runs TEST_FUNCTION and prints a message about NAME. */
 862 static void
 863 run_test (void (*test_function) (void), const char *name)
 864 {
 865   test_name = name;
 866   putchar ('.');
 867   fflush (stdout);
 868   test_function ();
 869 }
 870
 871 int
 872 main (void)
 873 {
 874   run_test (test_insert_any_remove_any_random_hash,
 875             "insert any order, delete any order (random hash)");
 876   run_test (test_insert_any_remove_any_identity_hash,
 877             "insert any order, delete any order (identity hash)");
 878   run_test (test_insert_any_remove_any_constant_hash,
 879             "insert any order, delete any order (constant hash)");
 880
 881   run_test (test_insert_any_remove_same_random_hash,
 882             "insert any order, delete same order (random hash)");
 883   run_test (test_insert_any_remove_same_identity_hash,
 884             "insert any order, delete same order (identity hash)");
 885   run_test (test_insert_any_remove_same_constant_hash,
 886             "insert any order, delete same order (constant hash)");
 887
 888   run_test (test_insert_any_remove_reverse_random_hash,
 889             "insert any order, delete reverse order (random hash)");
 890   run_test (test_insert_any_remove_reverse_identity_hash,
 891             "insert any order, delete reverse order (identity hash)");
 892   run_test (test_insert_any_remove_reverse_constant_hash,
 893             "insert any order, delete reverse order (constant hash)");
 894
 895   run_test (test_random_sequence_random_hash,
 896             "insert and delete in random sequence (random hash)");
 897   run_test (test_random_sequence_identity_hash,
 898             "insert and delete in random sequence (identity hash)");
 899   run_test (test_random_sequence_constant_hash,
 900             "insert and delete in random sequence (constant hash)");
 901
 902   run_test (test_insert_ordered_random_hash,
 903             "insert in ascending order (random hash)");
 904   run_test (test_insert_ordered_identity_hash,
 905             "insert in ascending order (identity hash)");
 906   run_test (test_insert_ordered_constant_hash,
 907             "insert in ascending order (constant hash)");
 908
 909   run_test (test_moved_random_hash,
 910             "move elements around in memory (random hash)");
 911   run_test (test_moved_identity_hash,
 912             "move elements around in memory (identity hash)");
 913   run_test (test_moved_constant_hash,
 914             "move elements around in memory (constant hash)");
 915
 916   run_test (test_changed_random_hash,
 917             "change key data in nodes (random hash)");
 918   run_test (test_changed_identity_hash,
 919             "change key data in nodes (identity hash)");
 920   run_test (test_changed_constant_hash,
 921             "change key data in nodes (constant hash)");
 922
 923   run_test (test_swap_random_hash, "test swapping tables");
 924
 925   run_test (test_destroy_null, "test destroying null table");
 926   run_test (test_shrink_empty, "test shrinking an empty table");
 927
 928   putchar ('\n');
 929
 930   return 0;
 931 }