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