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

   1 /* PSPP - a program for statistical analysis.
   2    Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation, either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>. */
  16
  17 /* This is a test program for the 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_count (hmap) == cnt);
 346   check (cnt <= hmap_capacity (hmap));
 347
 348   order = xmemdup (data, cnt * sizeof *data);
 349   qsort (order, cnt, sizeof *order, compare_ints);
 350
 351   for (i = 0; i < cnt; i = j)
 352     {
 353       struct element *e;
 354       int count;
 355
 356       for (j = i + 1; j < cnt; j++)
 357         if (order[i] != order[j])
 358           break;
 359
 360       count = 0;
 361       HMAP_FOR_EACH_WITH_HASH (e, struct element, node, hash (order[i]), hmap)
 362         if (e->data == order[i])
 363           count++;
 364
 365       check (count == j - i);
 366     }
 367
 368   check (find_element (hmap, -1, hash) == NULL);
 369
 370   if (cnt == 0)
 371     check (hmap_first (hmap) == NULL);
 372   else
 373     {
 374       struct hmap_node *p;
 375       int left;
 376
 377       left = cnt;
 378       for (p = hmap_first (hmap), i = 0; i < cnt; p = hmap_next (hmap, p), i++)
 379         {
 380           struct element *e = hmap_node_to_element (p);
 381
 382           check (hmap_node_hash (&e->node) == hash (e->data));
 383           for (j = 0; j < left; j++)
 384             if (order[j] == e->data)
 385               {
 386                 order[j] = order[--left];
 387                 goto next;
 388               }
 389           check_die ();
 390
 391         next: ;
 392         }
 393       check (p == NULL);
 394     }
 395
 396   free (order);
 397 }
 398
 399 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
 400    HMAP in the order specified by INSERTIONS, then deletes them in
 401    the order specified by DELETIONS, checking the HMAP's contents
 402    for correctness after each operation.  Uses HASH as the hash
 403    function. */
 404 static void
 405 test_insert_delete (const int insertions[],
 406                     const int deletions[],
 407                     size_t cnt,
 408                     hash_function *hash)
 409 {
 410   struct element *elements;
 411   struct hmap hmap;
 412   size_t i;
 413
 414   elements = xnmalloc (cnt, sizeof *elements);
 415   for (i = 0; i < cnt; i++)
 416     elements[i].data = i;
 417
 418   hmap_init (&hmap);
 419   hmap_reserve (&hmap, 1);
 420   check_hmap (&hmap, NULL, 0, hash);
 421   for (i = 0; i < cnt; i++)
 422     {
 423       size_t capacity;
 424       hmap_insert (&hmap, &elements[insertions[i]].node, hash (insertions[i]));
 425       check_hmap (&hmap, insertions, i + 1, hash);
 426
 427       /* A series of insertions should not produce a shrinkable hmap. */
 428       capacity = hmap_capacity (&hmap);
 429       hmap_shrink (&hmap);
 430       check (capacity == hmap_capacity (&hmap));
 431     }
 432   for (i = 0; i < cnt; i++)
 433     {
 434       hmap_delete (&hmap, &elements[deletions[i]].node);
 435       check_hmap (&hmap, deletions + i + 1, cnt - i - 1, hash);
 436     }
 437   hmap_destroy (&hmap);
 438
 439   free (elements);
 440 }
 441 \f
 442 /* Inserts values into an HMAP in each possible order, then
 443    removes them in each possible order, up to a specified maximum
 444    size, using hash function HASH. */
 445 static void
 446 test_insert_any_remove_any (hash_function *hash)
 447 {
 448   const int max_elems = 5;
 449   int cnt;
 450
 451   for (cnt = 0; cnt <= max_elems; cnt++)
 452     {
 453       int *insertions, *deletions;
 454       unsigned int ins_perm_cnt;
 455       int i;
 456
 457       insertions = xnmalloc (cnt, sizeof *insertions);
 458       deletions = xnmalloc (cnt, sizeof *deletions);
 459       for (i = 0; i < cnt; i++)
 460         insertions[i] = i;
 461
 462       for (ins_perm_cnt = 0;
 463            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
 464            ins_perm_cnt++)
 465         {
 466           unsigned int del_perm_cnt;
 467           int i;
 468
 469           for (i = 0; i < cnt; i++)
 470             deletions[i] = i;
 471
 472           for (del_perm_cnt = 0;
 473                del_perm_cnt == 0 || next_permutation (deletions, cnt);
 474                del_perm_cnt++)
 475             test_insert_delete (insertions, deletions, cnt, hash);
 476
 477           check (del_perm_cnt == factorial (cnt));
 478         }
 479       check (ins_perm_cnt == factorial (cnt));
 480
 481       free (insertions);
 482       free (deletions);
 483     }
 484 }
 485
 486 static void
 487 test_insert_any_remove_any_random_hash (void)
 488 {
 489   test_insert_any_remove_any (random_hash);
 490 }
 491
 492 static void
 493 test_insert_any_remove_any_identity_hash (void)
 494 {
 495   test_insert_any_remove_any (identity_hash);
 496 }
 497
 498 static void
 499 test_insert_any_remove_any_constant_hash (void)
 500 {
 501   test_insert_any_remove_any (constant_hash);
 502 }
 503
 504 /* Inserts values into an HMAP in each possible order, then
 505    removes them in the same order, up to a specified maximum
 506    size, using hash function HASH. */
 507 static void
 508 test_insert_any_remove_same (hash_function *hash)
 509 {
 510   const int max_elems = 7;
 511   int cnt;
 512
 513   for (cnt = 0; cnt <= max_elems; cnt++)
 514     {
 515       int *values;
 516       unsigned int permutation_cnt;
 517       int i;
 518
 519       values = xnmalloc (cnt, sizeof *values);
 520       for (i = 0; i < cnt; i++)
 521         values[i] = i;
 522
 523       for (permutation_cnt = 0;
 524            permutation_cnt == 0 || next_permutation (values, cnt);
 525            permutation_cnt++)
 526         test_insert_delete (values, values, cnt, hash);
 527       check (permutation_cnt == factorial (cnt));
 528
 529       free (values);
 530     }
 531 }
 532
 533 static void
 534 test_insert_any_remove_same_random_hash (void)
 535 {
 536   test_insert_any_remove_same (random_hash);
 537 }
 538
 539 static void
 540 test_insert_any_remove_same_identity_hash (void)
 541 {
 542   test_insert_any_remove_same (identity_hash);
 543 }
 544
 545 static void
 546 test_insert_any_remove_same_constant_hash (void)
 547 {
 548   test_insert_any_remove_same (constant_hash);
 549 }
 550
 551 /* Inserts values into an HMAP in each possible order, then
 552    removes them in reverse order, up to a specified maximum
 553    size, using hash function HASH. */
 554 static void
 555 test_insert_any_remove_reverse (hash_function *hash)
 556 {
 557   const int max_elems = 7;
 558   int cnt;
 559
 560   for (cnt = 0; cnt <= max_elems; cnt++)
 561     {
 562       int *insertions, *deletions;
 563       unsigned int permutation_cnt;
 564       int i;
 565
 566       insertions = xnmalloc (cnt, sizeof *insertions);
 567       deletions = xnmalloc (cnt, sizeof *deletions);
 568       for (i = 0; i < cnt; i++)
 569         insertions[i] = i;
 570
 571       for (permutation_cnt = 0;
 572            permutation_cnt == 0 || next_permutation (insertions, cnt);
 573            permutation_cnt++)
 574         {
 575           memcpy (deletions, insertions, sizeof *insertions * cnt);
 576           reverse (deletions, cnt);
 577
 578           test_insert_delete (insertions, deletions, cnt, hash);
 579         }
 580       check (permutation_cnt == factorial (cnt));
 581
 582       free (insertions);
 583       free (deletions);
 584     }
 585 }
 586
 587 static void
 588 test_insert_any_remove_reverse_random_hash (void)
 589 {
 590   test_insert_any_remove_reverse (random_hash);
 591 }
 592
 593 static void
 594 test_insert_any_remove_reverse_identity_hash (void)
 595 {
 596   test_insert_any_remove_reverse (identity_hash);
 597 }
 598
 599 static void
 600 test_insert_any_remove_reverse_constant_hash (void)
 601 {
 602   test_insert_any_remove_reverse (constant_hash);
 603 }
 604
 605 /* Inserts and removes up to MAX_ELEMS values in an hmap, in
 606    random order, using hash function HASH. */
 607 static void
 608 test_random_sequence (int max_elems, hash_function *hash)
 609 {
 610   const int max_trials = 8;
 611   int cnt;
 612
 613   for (cnt = 0; cnt <= max_elems; cnt += 2)
 614     {
 615       int *insertions, *deletions;
 616       int trial;
 617       int i;
 618
 619       insertions = xnmalloc (cnt, sizeof *insertions);
 620       deletions = xnmalloc (cnt, sizeof *deletions);
 621       for (i = 0; i < cnt; i++)
 622         insertions[i] = i;
 623       for (i = 0; i < cnt; i++)
 624         deletions[i] = i;
 625
 626       for (trial = 0; trial < max_trials; trial++)
 627         {
 628           random_shuffle (insertions, cnt, sizeof *insertions);
 629           random_shuffle (deletions, cnt, sizeof *deletions);
 630
 631           test_insert_delete (insertions, deletions, cnt, hash);
 632         }
 633
 634       free (insertions);
 635       free (deletions);
 636     }
 637 }
 638
 639 static void
 640 test_random_sequence_random_hash (void)
 641 {
 642   test_random_sequence (64, random_hash);
 643 }
 644
 645 static void
 646 test_random_sequence_identity_hash (void)
 647 {
 648   test_random_sequence (64, identity_hash);
 649 }
 650
 651 static void
 652 test_random_sequence_constant_hash (void)
 653 {
 654   test_random_sequence (32, constant_hash);
 655 }
 656
 657 /* Inserts MAX_ELEMS elements into an HMAP in ascending order,
 658    then delete in ascending order and shrink the hmap at each
 659    step, using hash function HASH. */
 660 static void
 661 test_insert_ordered (int max_elems, hash_function *hash)
 662 {
 663   struct element *elements;
 664   int *values;
 665   struct hmap hmap;
 666   int i;
 667
 668   hmap_init (&hmap);
 669   elements = xnmalloc (max_elems, sizeof *elements);
 670   values = xnmalloc (max_elems, sizeof *values);
 671   for (i = 0; i < max_elems; i++)
 672     {
 673       values[i] = elements[i].data = i;
 674       hmap_insert (&hmap, &elements[i].node, hash (elements[i].data));
 675       check_hmap (&hmap, values, i + 1, hash);
 676
 677       if (hash == identity_hash)
 678         {
 679           /* Check that every every hash bucket has (almost) the
 680              same number of nodes in it.  */
 681           int min = INT_MAX;
 682           int max = INT_MIN;
 683           int j;
 684
 685           for (j = 0; j <= hmap.mask; j++)
 686             {
 687               int count = 0;
 688               struct hmap_node *node;
 689
 690               for (node = hmap.buckets[j]; node != NULL; node = node->next)
 691                 count++;
 692               if (count < min)
 693                 min = count;
 694               if (count > max)
 695                 max = count;
 696             }
 697           check (max - min <= 1);
 698         }
 699     }
 700   for (i = 0; i < max_elems; i++)
 701     {
 702       hmap_delete (&hmap, &elements[i].node);
 703       hmap_shrink (&hmap);
 704       check_hmap (&hmap, values + i + 1, max_elems - i - 1, hash);
 705     }
 706   hmap_destroy (&hmap);
 707   free (elements);
 708   free (values);
 709 }
 710
 711 static void
 712 test_insert_ordered_random_hash (void)
 713 {
 714   test_insert_ordered (1024, random_hash);
 715 }
 716
 717 static void
 718 test_insert_ordered_identity_hash (void)
 719 {
 720   test_insert_ordered (1024, identity_hash);
 721 }
 722
 723 static void
 724 test_insert_ordered_constant_hash (void)
 725 {
 726   test_insert_ordered (128, constant_hash);
 727 }
 728
 729 /* Inserts up to MAX_ELEMS elements into an HMAP, then moves the
 730    nodes around in memory, using hash function HASH. */
 731 static void
 732 test_moved (int max_elems, hash_function *hash)
 733 {
 734   struct element *e[2];
 735   int cur;
 736   int *values;
 737   struct hmap hmap;
 738   int i, j;
 739
 740 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
 741   return;
 742 #endif  /* GCC 4.3 */
 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 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
 880   return;
 881 #endif  /* GCC 4.3 */
 882
 883   hmap_init (&a);
 884   hmap_init (&b);
 885   working = &a;
 886   empty = &b;
 887   elements = xnmalloc (max_elems, sizeof *elements);
 888   values = xnmalloc (max_elems, sizeof *values);
 889   for (i = 0; i < max_elems; i++)
 890     {
 891       struct hmap *tmp;
 892       values[i] = elements[i].data = i;
 893       hmap_insert (working, &elements[i].node, hash (elements[i].data));
 894       check_hmap (working, values, i + 1, hash);
 895       check_hmap (empty, NULL, 0, hash);
 896       hmap_swap (&a, &b);
 897       tmp = working;
 898       working = empty;
 899       empty = tmp;
 900     }
 901   hmap_destroy (&a);
 902   hmap_destroy (&b);
 903   free (elements);
 904   free (values);
 905 }
 906
 907 static void
 908 test_swap_random_hash (void)
 909 {
 910   test_swap (128, random_hash);
 911 }
 912
 913 static void
 914 test_destroy_null (void)
 915 {
 916   hmap_destroy (NULL);
 917 }
 918
 919 /* Test shrinking an empty hash table. */
 920 static void
 921 test_shrink_empty (void)
 922 {
 923   struct hmap hmap;
 924
 925   hmap_init (&hmap);
 926   hmap_reserve (&hmap, 123);
 927   hmap_shrink (&hmap);
 928   hmap_destroy (&hmap);
 929 }
 930 \f
 931 /* Main program. */
 932
 933 /* Runs TEST_FUNCTION and prints a message about NAME. */
 934 static void
 935 run_test (void (*test_function) (void), const char *name)
 936 {
 937   test_name = name;
 938   putchar ('.');
 939   fflush (stdout);
 940   test_function ();
 941 }
 942
 943 int
 944 main (void)
 945 {
 946   run_test (test_insert_any_remove_any_random_hash,
 947             "insert any order, delete any order (random hash)");
 948   run_test (test_insert_any_remove_any_identity_hash,
 949             "insert any order, delete any order (identity hash)");
 950   run_test (test_insert_any_remove_any_constant_hash,
 951             "insert any order, delete any order (constant hash)");
 952
 953   run_test (test_insert_any_remove_same_random_hash,
 954             "insert any order, delete same order (random hash)");
 955   run_test (test_insert_any_remove_same_identity_hash,
 956             "insert any order, delete same order (identity hash)");
 957   run_test (test_insert_any_remove_same_constant_hash,
 958             "insert any order, delete same order (constant hash)");
 959
 960   run_test (test_insert_any_remove_reverse_random_hash,
 961             "insert any order, delete reverse order (random hash)");
 962   run_test (test_insert_any_remove_reverse_identity_hash,
 963             "insert any order, delete reverse order (identity hash)");
 964   run_test (test_insert_any_remove_reverse_constant_hash,
 965             "insert any order, delete reverse order (constant hash)");
 966
 967   run_test (test_random_sequence_random_hash,
 968             "insert and delete in random sequence (random hash)");
 969   run_test (test_random_sequence_identity_hash,
 970             "insert and delete in random sequence (identity hash)");
 971   run_test (test_random_sequence_constant_hash,
 972             "insert and delete in random sequence (constant hash)");
 973
 974   run_test (test_insert_ordered_random_hash,
 975             "insert in ascending order (random hash)");
 976   run_test (test_insert_ordered_identity_hash,
 977             "insert in ascending order (identity hash)");
 978   run_test (test_insert_ordered_constant_hash,
 979             "insert in ascending order (constant hash)");
 980
 981   run_test (test_moved_random_hash,
 982             "move elements around in memory (random hash)");
 983   run_test (test_moved_identity_hash,
 984             "move elements around in memory (identity hash)");
 985   run_test (test_moved_constant_hash,
 986             "move elements around in memory (constant hash)");
 987
 988   run_test (test_changed_random_hash,
 989             "change key data in nodes (random hash)");
 990   run_test (test_changed_identity_hash,
 991             "change key data in nodes (identity hash)");
 992   run_test (test_changed_constant_hash,
 993             "change key data in nodes (constant hash)");
 994
 995   run_test (test_swap_random_hash, "test swapping tables");
 996
 997   run_test (test_destroy_null, "test destroying null table");
 998   run_test (test_shrink_empty, "test shrinking an empty table");
 999
1000   putchar ('\n');
1001
1002 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
1003   /* We skipped some of the tests, so return a value that
1004      Automake will interpret as "skipped", instead of one that
1005      means success. */
1006   return 77;
1007 #else
1008   return 0;
1009 #endif
1010 }