tests/libpspp/hmapx-test.c

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