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