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