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