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           size_t j;
 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   hmap_init (&hmap);
 670   elements = xnmalloc (max_elems, sizeof *elements);
 671   values = xnmalloc (max_elems, sizeof *values);
 672   for (i = 0; i < max_elems; i++)
 673     {
 674       values[i] = elements[i].data = i;
 675       hmap_insert (&hmap, &elements[i].node, hash (elements[i].data));
 676       check_hmap (&hmap, values, i + 1, hash);
 677
 678       if (hash == identity_hash)
 679         {
 680           /* Check that every every hash bucket has (almost) the
 681              same number of nodes in it.  */
 682           int min = INT_MAX;
 683           int max = INT_MIN;
 684           int j;
 685
 686           for (j = 0; j <= hmap.mask; j++)
 687             {
 688               int count = 0;
 689               struct hmap_node *node;
 690
 691               for (node = hmap.buckets[j]; node != NULL; node = node->next)
 692                 count++;
 693               if (count < min)
 694                 min = count;
 695               if (count > max)
 696                 max = count;
 697             }
 698           check (max - min <= 1);
 699         }
 700     }
 701   for (i = 0; i < max_elems; i++)
 702     {
 703       hmap_delete (&hmap, &elements[i].node);
 704       hmap_shrink (&hmap);
 705       check_hmap (&hmap, values + i + 1, max_elems - i - 1, hash);
 706     }
 707   hmap_destroy (&hmap);
 708   free (elements);
 709   free (values);
 710 }
 711
 712 static void
 713 test_insert_ordered_random_hash (void)
 714 {
 715   test_insert_ordered (1024, random_hash);
 716 }
 717
 718 static void
 719 test_insert_ordered_identity_hash (void)
 720 {
 721   test_insert_ordered (1024, identity_hash);
 722 }
 723
 724 static void
 725 test_insert_ordered_constant_hash (void)
 726 {
 727   test_insert_ordered (128, constant_hash);
 728 }
 729
 730 /* Inserts up to MAX_ELEMS elements into an HMAP, then moves the
 731    nodes around in memory, using hash function HASH. */
 732 static void
 733 test_moved (int max_elems, hash_function *hash)
 734 {
 735   struct element *e[2];
 736   int cur;
 737   int *values;
 738   struct hmap hmap;
 739   int i, j;
 740
 741 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
 742   return;
 743 #endif  /* GCC 4.3 */
 744
 745   hmap_init (&hmap);
 746   e[0] = xnmalloc (max_elems, sizeof *e[0]);
 747   e[1] = xnmalloc (max_elems, sizeof *e[1]);
 748   values = xnmalloc (max_elems, sizeof *values);
 749   cur = 0;
 750   for (i = 0; i < max_elems; i++)
 751     {
 752       values[i] = e[cur][i].data = i;
 753       hmap_insert (&hmap, &e[cur][i].node, hash (e[cur][i].data));
 754       check_hmap (&hmap, values, i + 1, hash);
 755
 756       for (j = 0; j <= i; j++)
 757         {
 758           e[!cur][j] = e[cur][j];
 759           hmap_moved (&hmap, &e[!cur][j].node, &e[cur][j].node);
 760           check_hmap (&hmap, values, i + 1, hash);
 761         }
 762       cur = !cur;
 763     }
 764   hmap_destroy (&hmap);
 765   free (e[0]);
 766   free (e[1]);
 767   free (values);
 768 }
 769
 770 static void
 771 test_moved_random_hash (void)
 772 {
 773   test_moved (128, random_hash);
 774 }
 775
 776 static void
 777 test_moved_identity_hash (void)
 778 {
 779   test_moved (128, identity_hash);
 780 }
 781
 782 static void
 783 test_moved_constant_hash (void)
 784 {
 785   test_moved (32, constant_hash);
 786 }
 787
 788 /* Inserts values into an HMAP, then changes their values, using
 789    hash function HASH. */
 790 static void
 791 test_changed (hash_function *hash)
 792 {
 793   const int max_elems = 6;
 794   int cnt;
 795
 796   for (cnt = 0; cnt <= max_elems; cnt++)
 797     {
 798       int *values, *changed_values;
 799       struct element *elements;
 800       unsigned int permutation_cnt;
 801       int i;
 802
 803       values = xnmalloc (cnt, sizeof *values);
 804       changed_values = xnmalloc (cnt, sizeof *changed_values);
 805       elements = xnmalloc (cnt, sizeof *elements);
 806       for (i = 0; i < cnt; i++)
 807         values[i] = i;
 808
 809       for (permutation_cnt = 0;
 810            permutation_cnt == 0 || next_permutation (values, cnt);
 811            permutation_cnt++)
 812         {
 813           for (i = 0; i < cnt; i++)
 814             {
 815               int j, k;
 816               for (j = 0; j <= cnt; j++)
 817                 {
 818                   struct hmap hmap;
 819
 820                   hmap_init (&hmap);
 821
 822                   /* Add to HMAP in order. */
 823                   for (k = 0; k < cnt; k++)
 824                     {
 825                       int n = values[k];
 826                       elements[n].data = n;
 827                       hmap_insert (&hmap, &elements[n].node,
 828                                    hash (elements[n].data));
 829                     }
 830                   check_hmap (&hmap, values, cnt, hash);
 831
 832                   /* Change value i to j. */
 833                   elements[i].data = j;
 834                   hmap_changed (&hmap, &elements[i].node,
 835                                 hash (elements[i].data));
 836                   for (k = 0; k < cnt; k++)
 837                     changed_values[k] = k;
 838                   changed_values[i] = j;
 839                   check_hmap (&hmap, changed_values, cnt, hash);
 840
 841                   hmap_destroy (&hmap);
 842                 }
 843             }
 844         }
 845       check (permutation_cnt == factorial (cnt));
 846
 847       free (values);
 848       free (changed_values);
 849       free (elements);
 850     }
 851 }
 852
 853 static void
 854 test_changed_random_hash (void)
 855 {
 856   test_changed (random_hash);
 857 }
 858
 859 static void
 860 test_changed_identity_hash (void)
 861 {
 862   test_changed (identity_hash);
 863 }
 864
 865 static void
 866 test_changed_constant_hash (void)
 867 {
 868   test_changed (constant_hash);
 869 }
 870
 871 static void
 872 test_swap (int max_elems, hash_function *hash)
 873 {
 874   struct element *elements;
 875   int *values;
 876   struct hmap a, b;
 877   struct hmap *working, *empty;
 878   int i;
 879
 880 #if __GNUC__ == 4 && __GNUC_MINOR__ == 3
 881   return;
 882 #endif  /* GCC 4.3 */
 883
 884   hmap_init (&a);
 885   hmap_init (&b);
 886   working = &a;
 887   empty = &b;
 888   elements = xnmalloc (max_elems, sizeof *elements);
 889   values = xnmalloc (max_elems, sizeof *values);
 890   for (i = 0; i < max_elems; i++)
 891     {
 892       struct hmap *tmp;
 893       values[i] = elements[i].data = i;
 894       hmap_insert (working, &elements[i].node, hash (elements[i].data));
 895       check_hmap (working, values, i + 1, hash);
 896       check_hmap (empty, NULL, 0, hash);
 897       hmap_swap (&a, &b);
 898       tmp = working;
 899       working = empty;
 900       empty = tmp;
 901     }
 902   hmap_destroy (&a);
 903   hmap_destroy (&b);
 904   free (elements);
 905   free (values);
 906 }
 907
 908 static void
 909 test_swap_random_hash (void)
 910 {
 911   test_swap (128, random_hash);
 912 }
 913
 914 static void
 915 test_destroy_null (void)
 916 {
 917   hmap_destroy (NULL);
 918 }
 919
 920 /* Test shrinking an empty hash table. */
 921 static void
 922 test_shrink_empty (void)
 923 {
 924   struct hmap hmap;
 925
 926   hmap_init (&hmap);
 927   hmap_reserve (&hmap, 123);
 928   hmap_shrink (&hmap);
 929   hmap_destroy (&hmap);
 930 }
 931 \f
 932 /* Main program. */
 933
 934 /* Runs TEST_FUNCTION and prints a message about NAME. */
 935 static void
 936 run_test (void (*test_function) (void), const char *name)
 937 {
 938   test_name = name;
 939   putchar ('.');
 940   fflush (stdout);
 941   test_function ();
 942 }
 943
 944 int
 945 main (void)
 946 {
 947   run_test (test_insert_any_remove_any_random_hash,
 948             "insert any order, delete any order (random hash)");
 949   run_test (test_insert_any_remove_any_identity_hash,
 950             "insert any order, delete any order (identity hash)");
 951   run_test (test_insert_any_remove_any_constant_hash,
 952             "insert any order, delete any order (constant hash)");
 953
 954   run_test (test_insert_any_remove_same_random_hash,
 955             "insert any order, delete same order (random hash)");
 956   run_test (test_insert_any_remove_same_identity_hash,
 957             "insert any order, delete same order (identity hash)");
 958   run_test (test_insert_any_remove_same_constant_hash,
 959             "insert any order, delete same order (constant hash)");
 960
 961   run_test (test_insert_any_remove_reverse_random_hash,
 962             "insert any order, delete reverse order (random hash)");
 963   run_test (test_insert_any_remove_reverse_identity_hash,
 964             "insert any order, delete reverse order (identity hash)");
 965   run_test (test_insert_any_remove_reverse_constant_hash,
 966             "insert any order, delete reverse order (constant hash)");
 967
 968   run_test (test_random_sequence_random_hash,
 969             "insert and delete in random sequence (random hash)");
 970   run_test (test_random_sequence_identity_hash,
 971             "insert and delete in random sequence (identity hash)");
 972   run_test (test_random_sequence_constant_hash,
 973             "insert and delete in random sequence (constant hash)");
 974
 975   run_test (test_insert_ordered_random_hash,
 976             "insert in ascending order (random hash)");
 977   run_test (test_insert_ordered_identity_hash,
 978             "insert in ascending order (identity hash)");
 979   run_test (test_insert_ordered_constant_hash,
 980             "insert in ascending order (constant hash)");
 981
 982   run_test (test_moved_random_hash,
 983             "move elements around in memory (random hash)");
 984   run_test (test_moved_identity_hash,
 985             "move elements around in memory (identity hash)");
 986   run_test (test_moved_constant_hash,
 987             "move elements around in memory (constant hash)");
 988
 989   run_test (test_changed_random_hash,
 990             "change key data in nodes (random hash)");
 991   run_test (test_changed_identity_hash,
 992             "change key data in nodes (identity hash)");
 993   run_test (test_changed_constant_hash,
 994             "change key data in nodes (constant hash)");
 995
 996   run_test (test_swap_random_hash, "test swapping tables");
 997
 998   run_test (test_destroy_null, "test destroying null table");
 999   run_test (test_shrink_empty, "test shrinking an empty table");
1000
1001   putchar ('\n');
1002
1003   return 0;
1004 }