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