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