pintos-os.org Git - pspp/blob - tests/libpspp/hmapx-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 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_is_empty (hmapx) == (cnt == 0));
 266   check (hmapx_count (hmapx) == cnt);
 267   check (cnt <= hmapx_capacity (hmapx));
 268
 269   order = xmemdup (data, cnt * sizeof *data);
 270   qsort (order, cnt, sizeof *order, compare_ints);
 271
 272   for (i = 0; i < cnt; i = j)
 273     {
 274       struct hmapx_node *node;
 275       struct element *e;
 276       int count;
 277
 278       for (j = i + 1; j < cnt; j++)
 279         if (order[i] != order[j])
 280           break;
 281
 282       count = 0;
 283       HMAPX_FOR_EACH_WITH_HASH (e, node, hash (order[i]), hmapx)
 284         if (e->data == order[i])
 285           count++;
 286
 287       check (count == j - i);
 288     }
 289
 290   check (find_element (hmapx, -1, hash) == NULL);
 291
 292   if (cnt == 0)
 293     check (hmapx_first (hmapx) == NULL);
 294   else
 295     {
 296       struct hmapx_node *p;
 297       int left;
 298
 299       left = cnt;
 300       for (p = hmapx_first (hmapx), i = 0; i < cnt;
 301            p = hmapx_next (hmapx, p), i++)
 302         {
 303           struct element *e = hmapx_node_data (p);
 304           size_t j;
 305
 306           check (hmapx_node_hash (p) == hash (e->data));
 307           for (j = 0; j < left; j++)
 308             if (order[j] == e->data)
 309               {
 310                 order[j] = order[--left];
 311                 goto next;
 312               }
 313           abort ();
 314
 315         next: ;
 316         }
 317       check (p == NULL);
 318     }
 319
 320   free (order);
 321 }
 322
 323 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
 324    HMAPX in the order specified by INSERTIONS, then deletes them in
 325    the order specified by DELETIONS, checking the HMAPX's contents
 326    for correctness after each operation.  Uses HASH as the hash
 327    function. */
 328 static void
 329 test_insert_delete (const int insertions[],
 330                     const int deletions[],
 331                     size_t cnt,
 332                     hash_function *hash,
 333                     size_t reserve)
 334 {
 335   struct element *elements;
 336   struct hmapx_node **nodes;
 337   struct hmapx hmapx;
 338   size_t i;
 339
 340   elements = xnmalloc (cnt, sizeof *elements);
 341   nodes = xnmalloc (cnt, sizeof *nodes);
 342   for (i = 0; i < cnt; i++)
 343     elements[i].data = i;
 344
 345   hmapx_init (&hmapx);
 346   hmapx_reserve (&hmapx, reserve);
 347   check_hmapx (&hmapx, NULL, 0, hash);
 348   for (i = 0; i < cnt; i++)
 349     {
 350       struct hmapx_node *(*insert) (struct hmapx *, void *, size_t hash);
 351       size_t capacity;
 352
 353       /* Insert the node.  Use hmapx_insert_fast if we have not
 354          yet exceeded the reserve. */
 355       insert = i < reserve ? hmapx_insert_fast : hmapx_insert;
 356       nodes[insertions[i]] = insert (&hmapx, &elements[insertions[i]],
 357                                      hash (insertions[i]));
 358       check_hmapx (&hmapx, insertions, i + 1, hash);
 359
 360       /* A series of insertions should not produce a shrinkable hmapx. */
 361       if (i >= reserve)
 362         {
 363           capacity = hmapx_capacity (&hmapx);
 364           hmapx_shrink (&hmapx);
 365           check (capacity == hmapx_capacity (&hmapx));
 366         }
 367     }
 368   for (i = 0; i < cnt; i++)
 369     {
 370       hmapx_delete (&hmapx, nodes[deletions[i]]);
 371       check_hmapx (&hmapx, deletions + i + 1, cnt - i - 1, hash);
 372     }
 373   hmapx_destroy (&hmapx);
 374
 375   free (elements);
 376   free (nodes);
 377 }
 378 \f
 379 /* Inserts values into an HMAPX in each possible order, then
 380    removes them in each possible order, up to a specified maximum
 381    size, using hash function HASH. */
 382 static void
 383 test_insert_any_remove_any (hash_function *hash)
 384 {
 385   const int max_elems = 5;
 386   int cnt;
 387
 388   for (cnt = 0; cnt <= max_elems; cnt++)
 389     {
 390       int *insertions, *deletions;
 391       unsigned int ins_perm_cnt;
 392       int i;
 393
 394       insertions = xnmalloc (cnt, sizeof *insertions);
 395       deletions = xnmalloc (cnt, sizeof *deletions);
 396       for (i = 0; i < cnt; i++)
 397         insertions[i] = i;
 398
 399       for (ins_perm_cnt = 0;
 400            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
 401            ins_perm_cnt++)
 402         {
 403           unsigned int del_perm_cnt;
 404           int i;
 405
 406           for (i = 0; i < cnt; i++)
 407             deletions[i] = i;
 408
 409           for (del_perm_cnt = 0;
 410                del_perm_cnt == 0 || next_permutation (deletions, cnt);
 411                del_perm_cnt++)
 412             test_insert_delete (insertions, deletions, cnt, hash, 1);
 413
 414           check (del_perm_cnt == factorial (cnt));
 415         }
 416       check (ins_perm_cnt == factorial (cnt));
 417
 418       free (insertions);
 419       free (deletions);
 420     }
 421 }
 422
 423 static void
 424 test_insert_any_remove_any_random_hash (void)
 425 {
 426   test_insert_any_remove_any (random_hash);
 427 }
 428
 429 static void
 430 test_insert_any_remove_any_identity_hash (void)
 431 {
 432   test_insert_any_remove_any (identity_hash);
 433 }
 434
 435 static void
 436 test_insert_any_remove_any_constant_hash (void)
 437 {
 438   test_insert_any_remove_any (constant_hash);
 439 }
 440
 441 /* Inserts values into an HMAPX in each possible order, then
 442    removes them in the same order, up to a specified maximum
 443    size, using hash function HASH. */
 444 static void
 445 test_insert_any_remove_same (hash_function *hash)
 446 {
 447   const int max_elems = 7;
 448   int cnt;
 449
 450   for (cnt = 0; cnt <= max_elems; cnt++)
 451     {
 452       int *values;
 453       unsigned int permutation_cnt;
 454       int i;
 455
 456       values = xnmalloc (cnt, sizeof *values);
 457       for (i = 0; i < cnt; i++)
 458         values[i] = i;
 459
 460       for (permutation_cnt = 0;
 461            permutation_cnt == 0 || next_permutation (values, cnt);
 462            permutation_cnt++)
 463         test_insert_delete (values, values, cnt, hash, cnt / 2);
 464       check (permutation_cnt == factorial (cnt));
 465
 466       free (values);
 467     }
 468 }
 469
 470 static void
 471 test_insert_any_remove_same_random_hash (void)
 472 {
 473   test_insert_any_remove_same (random_hash);
 474 }
 475
 476 static void
 477 test_insert_any_remove_same_identity_hash (void)
 478 {
 479   test_insert_any_remove_same (identity_hash);
 480 }
 481
 482 static void
 483 test_insert_any_remove_same_constant_hash (void)
 484 {
 485   test_insert_any_remove_same (constant_hash);
 486 }
 487
 488 /* Inserts values into an HMAPX in each possible order, then
 489    removes them in reverse order, up to a specified maximum
 490    size, using hash function HASH. */
 491 static void
 492 test_insert_any_remove_reverse (hash_function *hash)
 493 {
 494   const int max_elems = 7;
 495   int cnt;
 496
 497   for (cnt = 0; cnt <= max_elems; cnt++)
 498     {
 499       int *insertions, *deletions;
 500       unsigned int permutation_cnt;
 501       int i;
 502
 503       insertions = xnmalloc (cnt, sizeof *insertions);
 504       deletions = xnmalloc (cnt, sizeof *deletions);
 505       for (i = 0; i < cnt; i++)
 506         insertions[i] = i;
 507
 508       for (permutation_cnt = 0;
 509            permutation_cnt == 0 || next_permutation (insertions, cnt);
 510            permutation_cnt++)
 511         {
 512           memcpy (deletions, insertions, sizeof *insertions * cnt);
 513           reverse (deletions, cnt);
 514
 515           test_insert_delete (insertions, deletions, cnt, hash, cnt);
 516         }
 517       check (permutation_cnt == factorial (cnt));
 518
 519       free (insertions);
 520       free (deletions);
 521     }
 522 }
 523
 524 static void
 525 test_insert_any_remove_reverse_random_hash (void)
 526 {
 527   test_insert_any_remove_reverse (random_hash);
 528 }
 529
 530 static void
 531 test_insert_any_remove_reverse_identity_hash (void)
 532 {
 533   test_insert_any_remove_reverse (identity_hash);
 534 }
 535
 536 static void
 537 test_insert_any_remove_reverse_constant_hash (void)
 538 {
 539   test_insert_any_remove_reverse (constant_hash);
 540 }
 541
 542 /* Inserts and removes up to MAX_ELEMS values in an hmapx, in
 543    random order, using hash function HASH. */
 544 static void
 545 test_random_sequence (int max_elems, hash_function *hash)
 546 {
 547   const int max_trials = 8;
 548   int cnt;
 549
 550   for (cnt = 0; cnt <= max_elems; cnt += 2)
 551     {
 552       int *insertions, *deletions;
 553       int trial;
 554       int i;
 555
 556       insertions = xnmalloc (cnt, sizeof *insertions);
 557       deletions = xnmalloc (cnt, sizeof *deletions);
 558       for (i = 0; i < cnt; i++)
 559         insertions[i] = i;
 560       for (i = 0; i < cnt; i++)
 561         deletions[i] = i;
 562
 563       for (trial = 0; trial < max_trials; trial++)
 564         {
 565           random_shuffle (insertions, cnt, sizeof *insertions);
 566           random_shuffle (deletions, cnt, sizeof *deletions);
 567
 568           test_insert_delete (insertions, deletions, cnt, hash, 0);
 569         }
 570
 571       free (insertions);
 572       free (deletions);
 573     }
 574 }
 575
 576 static void
 577 test_random_sequence_random_hash (void)
 578 {
 579   test_random_sequence (64, random_hash);
 580 }
 581
 582 static void
 583 test_random_sequence_identity_hash (void)
 584 {
 585   test_random_sequence (64, identity_hash);
 586 }
 587
 588 static void
 589 test_random_sequence_constant_hash (void)
 590 {
 591   test_random_sequence (32, constant_hash);
 592 }
 593
 594 /* Inserts MAX_ELEMS elements into an HMAPX in ascending order,
 595    then delete in ascending order and shrink the hmapx at each
 596    step, using hash function HASH. */
 597 static void
 598 test_insert_ordered (int max_elems, hash_function *hash)
 599 {
 600   struct element *elements;
 601   struct hmapx_node **nodes;
 602   int *values;
 603   struct hmapx hmapx;
 604   int i;
 605
 606   hmapx_init (&hmapx);
 607   elements = xnmalloc (max_elems, sizeof *elements);
 608   nodes = xnmalloc (max_elems, sizeof *nodes);
 609   values = xnmalloc (max_elems, sizeof *values);
 610   for (i = 0; i < max_elems; i++)
 611     {
 612       values[i] = elements[i].data = i;
 613       nodes[i] = hmapx_insert (&hmapx, &elements[i], hash (elements[i].data));
 614       check_hmapx (&hmapx, values, i + 1, hash);
 615
 616       if (hash == identity_hash)
 617         {
 618           /* Check that every every hash bucket has (almost) the
 619              same number of nodes in it.  */
 620           int min = INT_MAX;
 621           int max = INT_MIN;
 622           int j;
 623
 624           for (j = 0; j <= hmapx.hmap.mask; j++)
 625             {
 626               int count = 0;
 627               struct hmap_node *node;
 628
 629               for (node = hmapx.hmap.buckets[j]; node != NULL;
 630                    node = node->next)
 631                 count++;
 632               if (count < min)
 633                 min = count;
 634               if (count > max)
 635                 max = count;
 636             }
 637           check (max - min <= 1);
 638         }
 639     }
 640   for (i = 0; i < max_elems; i++)
 641     {
 642       hmapx_delete (&hmapx, nodes[i]);
 643       hmapx_shrink (&hmapx);
 644       check_hmapx (&hmapx, values + i + 1, max_elems - i - 1, hash);
 645     }
 646   hmapx_destroy (&hmapx);
 647   free (elements);
 648   free (nodes);
 649   free (values);
 650 }
 651
 652 static void
 653 test_insert_ordered_random_hash (void)
 654 {
 655   test_insert_ordered (1024, random_hash);
 656 }
 657
 658 static void
 659 test_insert_ordered_identity_hash (void)
 660 {
 661   test_insert_ordered (1024, identity_hash);
 662 }
 663
 664 static void
 665 test_insert_ordered_constant_hash (void)
 666 {
 667   test_insert_ordered (128, constant_hash);
 668 }
 669
 670 /* Inserts up to MAX_ELEMS elements into an HMAPX, then moves the
 671    nodes around in memory, using hash function HASH. */
 672 static void
 673 test_moved (int max_elems, hash_function *hash)
 674 {
 675   struct element *e[2];
 676   int cur;
 677   int *values;
 678   struct hmapx_node **nodes;
 679   struct hmapx hmapx;
 680   int i, j;
 681
 682   hmapx_init (&hmapx);
 683   e[0] = xnmalloc (max_elems, sizeof *e[0]);
 684   e[1] = xnmalloc (max_elems, sizeof *e[1]);
 685   values = xnmalloc (max_elems, sizeof *values);
 686   nodes = xnmalloc (max_elems, sizeof *nodes);
 687   cur = 0;
 688   for (i = 0; i < max_elems; i++)
 689     {
 690       values[i] = e[cur][i].data = i;
 691       nodes[i] = hmapx_insert (&hmapx, &e[cur][i], hash (e[cur][i].data));
 692       check_hmapx (&hmapx, values, i + 1, hash);
 693
 694       for (j = 0; j <= i; j++)
 695         {
 696           e[!cur][j] = e[cur][j];
 697           hmapx_move (nodes[j], &e[cur][j]);
 698           check_hmapx (&hmapx, values, i + 1, hash);
 699         }
 700       cur = !cur;
 701     }
 702   hmapx_destroy (&hmapx);
 703   free (e[0]);
 704   free (e[1]);
 705   free (values);
 706   free (nodes);
 707 }
 708
 709 static void
 710 test_moved_random_hash (void)
 711 {
 712   test_moved (128, random_hash);
 713 }
 714
 715 static void
 716 test_moved_identity_hash (void)
 717 {
 718   test_moved (128, identity_hash);
 719 }
 720
 721 static void
 722 test_moved_constant_hash (void)
 723 {
 724   test_moved (32, constant_hash);
 725 }
 726
 727 /* Inserts values into an HMAPX, then changes their values, using
 728    hash function HASH. */
 729 static void
 730 test_changed (hash_function *hash)
 731 {
 732   const int max_elems = 6;
 733   int cnt;
 734
 735   for (cnt = 0; cnt <= max_elems; cnt++)
 736     {
 737       int *values, *changed_values;
 738       struct hmapx_node **nodes;
 739       struct element *elements;
 740       unsigned int permutation_cnt;
 741       int i;
 742
 743       values = xnmalloc (cnt, sizeof *values);
 744       changed_values = xnmalloc (cnt, sizeof *changed_values);
 745       elements = xnmalloc (cnt, sizeof *elements);
 746       nodes = xnmalloc (cnt, sizeof *nodes);
 747       for (i = 0; i < cnt; i++)
 748         values[i] = i;
 749
 750       for (permutation_cnt = 0;
 751            permutation_cnt == 0 || next_permutation (values, cnt);
 752            permutation_cnt++)
 753         {
 754           for (i = 0; i < cnt; i++)
 755             {
 756               int j, k;
 757               for (j = 0; j <= cnt; j++)
 758                 {
 759                   struct hmapx hmapx;
 760
 761                   hmapx_init (&hmapx);
 762
 763                   /* Add to HMAPX in order. */
 764                   for (k = 0; k < cnt; k++)
 765                     {
 766                       int n = values[k];
 767                       elements[n].data = n;
 768                       nodes[n] = hmapx_insert (&hmapx, &elements[n],
 769                                                hash (elements[n].data));
 770                     }
 771                   check_hmapx (&hmapx, values, cnt, hash);
 772
 773                   /* Change value i to j. */
 774                   elements[i].data = j;
 775                   hmapx_changed (&hmapx, nodes[i],
 776                                  hash (elements[i].data));
 777                   for (k = 0; k < cnt; k++)
 778                     changed_values[k] = k;
 779                   changed_values[i] = j;
 780                   check_hmapx (&hmapx, changed_values, cnt, hash);
 781
 782                   hmapx_destroy (&hmapx);
 783                 }
 784             }
 785         }
 786       check (permutation_cnt == factorial (cnt));
 787
 788       free (values);
 789       free (changed_values);
 790       free (elements);
 791       free (nodes);
 792     }
 793 }
 794
 795 static void
 796 test_changed_random_hash (void)
 797 {
 798   test_changed (random_hash);
 799 }
 800
 801 static void
 802 test_changed_identity_hash (void)
 803 {
 804   test_changed (identity_hash);
 805 }
 806
 807 static void
 808 test_changed_constant_hash (void)
 809 {
 810   test_changed (constant_hash);
 811 }
 812
 813 /* Inserts values into an HMAPX, then changes and moves their
 814    values, using hash function HASH. */
 815 static void
 816 test_change (hash_function *hash)
 817 {
 818   const int max_elems = 6;
 819   int cnt;
 820
 821   for (cnt = 0; cnt <= max_elems; cnt++)
 822     {
 823       int *values, *changed_values;
 824       struct hmapx_node **nodes;
 825       struct element *elements;
 826       struct element replacement;
 827       unsigned int permutation_cnt;
 828       int i;
 829
 830       values = xnmalloc (cnt, sizeof *values);
 831       changed_values = xnmalloc (cnt, sizeof *changed_values);
 832       elements = xnmalloc (cnt, sizeof *elements);
 833       nodes = xnmalloc (cnt, sizeof *nodes);
 834       for (i = 0; i < cnt; i++)
 835         values[i] = i;
 836
 837       for (permutation_cnt = 0;
 838            permutation_cnt == 0 || next_permutation (values, cnt);
 839            permutation_cnt++)
 840         {
 841           for (i = 0; i < cnt; i++)
 842             {
 843               int j, k;
 844               for (j = 0; j <= cnt; j++)
 845                 {
 846                   struct hmapx hmapx;
 847
 848                   hmapx_init (&hmapx);
 849
 850                   /* Add to HMAPX in order. */
 851                   for (k = 0; k < cnt; k++)
 852                     {
 853                       int n = values[k];
 854                       elements[n].data = n;
 855                       nodes[n] = hmapx_insert (&hmapx, &elements[n],
 856                                                hash (elements[n].data));
 857                     }
 858                   check_hmapx (&hmapx, values, cnt, hash);
 859
 860                   /* Change value i to j. */
 861                   replacement.data = j;
 862                   hmapx_change (&hmapx, nodes[i], &replacement, hash (j));
 863                   for (k = 0; k < cnt; k++)
 864                     changed_values[k] = k;
 865                   changed_values[i] = j;
 866                   check_hmapx (&hmapx, changed_values, cnt, hash);
 867
 868                   hmapx_destroy (&hmapx);
 869                 }
 870             }
 871         }
 872       check (permutation_cnt == factorial (cnt));
 873
 874       free (values);
 875       free (changed_values);
 876       free (elements);
 877       free (nodes);
 878     }
 879 }
 880
 881 static void
 882 test_change_random_hash (void)
 883 {
 884   test_change (random_hash);
 885 }
 886
 887 static void
 888 test_change_identity_hash (void)
 889 {
 890   test_change (identity_hash);
 891 }
 892
 893 static void
 894 test_change_constant_hash (void)
 895 {
 896   test_change (constant_hash);
 897 }
 898
 899 static void
 900 test_swap (int max_elems, hash_function *hash)
 901 {
 902   struct element *elements;
 903   int *values;
 904   struct hmapx a, b;
 905   struct hmapx *working, *empty;
 906   int i;
 907
 908   hmapx_init (&a);
 909   hmapx_init (&b);
 910   working = &a;
 911   empty = &b;
 912   elements = xnmalloc (max_elems, sizeof *elements);
 913   values = xnmalloc (max_elems, sizeof *values);
 914   for (i = 0; i < max_elems; i++)
 915     {
 916       struct hmapx *tmp;
 917       values[i] = elements[i].data = i;
 918       hmapx_insert (working, &elements[i], hash (elements[i].data));
 919       check_hmapx (working, values, i + 1, hash);
 920       check_hmapx (empty, NULL, 0, hash);
 921       hmapx_swap (&a, &b);
 922       tmp = working;
 923       working = empty;
 924       empty = tmp;
 925     }
 926   hmapx_destroy (&a);
 927   hmapx_destroy (&b);
 928   free (elements);
 929   free (values);
 930 }
 931
 932 static void
 933 test_swap_random_hash (void)
 934 {
 935   test_swap (128, random_hash);
 936 }
 937
 938 static void
 939 test_destroy_null (void)
 940 {
 941   hmapx_destroy (NULL);
 942 }
 943
 944 /* Test shrinking an empty hash table. */
 945 static void
 946 test_shrink_empty (void)
 947 {
 948   struct hmapx hmapx;
 949
 950   hmapx_init (&hmapx);
 951   hmapx_reserve (&hmapx, 123);
 952   hmapx_shrink (&hmapx);
 953   hmapx_destroy (&hmapx);
 954 }
 955 \f
 956 /* Main program. */
 957
 958 /* Runs TEST_FUNCTION and prints a message about NAME. */
 959 static void
 960 run_test (void (*test_function) (void), const char *name)
 961 {
 962   test_name = name;
 963   putchar ('.');
 964   fflush (stdout);
 965   test_function ();
 966 }
 967
 968 int
 969 main (void)
 970 {
 971   run_test (test_insert_any_remove_any_random_hash,
 972             "insert any order, delete any order (random hash)");
 973   run_test (test_insert_any_remove_any_identity_hash,
 974             "insert any order, delete any order (identity hash)");
 975   run_test (test_insert_any_remove_any_constant_hash,
 976             "insert any order, delete any order (constant hash)");
 977
 978   run_test (test_insert_any_remove_same_random_hash,
 979             "insert any order, delete same order (random hash)");
 980   run_test (test_insert_any_remove_same_identity_hash,
 981             "insert any order, delete same order (identity hash)");
 982   run_test (test_insert_any_remove_same_constant_hash,
 983             "insert any order, delete same order (constant hash)");
 984
 985   run_test (test_insert_any_remove_reverse_random_hash,
 986             "insert any order, delete reverse order (random hash)");
 987   run_test (test_insert_any_remove_reverse_identity_hash,
 988             "insert any order, delete reverse order (identity hash)");
 989   run_test (test_insert_any_remove_reverse_constant_hash,
 990             "insert any order, delete reverse order (constant hash)");
 991
 992   run_test (test_random_sequence_random_hash,
 993             "insert and delete in random sequence (random hash)");
 994   run_test (test_random_sequence_identity_hash,
 995             "insert and delete in random sequence (identity hash)");
 996   run_test (test_random_sequence_constant_hash,
 997             "insert and delete in random sequence (constant hash)");
 998
 999   run_test (test_insert_ordered_random_hash,
1000             "insert in ascending order (random hash)");
1001   run_test (test_insert_ordered_identity_hash,
1002             "insert in ascending order (identity hash)");
1003   run_test (test_insert_ordered_constant_hash,
1004             "insert in ascending order (constant hash)");
1005
1006   run_test (test_moved_random_hash,
1007             "move elements around in memory (random hash)");
1008   run_test (test_moved_identity_hash,
1009             "move elements around in memory (identity hash)");
1010   run_test (test_moved_constant_hash,
1011             "move elements around in memory (constant hash)");
1012
1013   run_test (test_changed_random_hash,
1014             "change key data in nodes (random hash)");
1015   run_test (test_changed_identity_hash,
1016             "change key data in nodes (identity hash)");
1017   run_test (test_changed_constant_hash,
1018             "change key data in nodes (constant hash)");
1019
1020   run_test (test_change_random_hash,
1021             "change and move key data in nodes (random hash)");
1022   run_test (test_change_identity_hash,
1023             "change and move key data in nodes (identity hash)");
1024   run_test (test_change_constant_hash,
1025             "change and move key data in nodes (constant hash)");
1026
1027   run_test (test_swap_random_hash, "test swapping tables");
1028
1029   run_test (test_destroy_null, "test destroying null table");
1030   run_test (test_shrink_empty, "test shrinking an empty table");
1031
1032   putchar ('\n');
1033
1034   return 0;
1035 }