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