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 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 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 CNT integers starting at VALUES. */ 208 static void 209 reverse (int *values, size_t cnt) 210 { 211 size_t i = 0; 212 size_t j = cnt; 213 214 while (j > i) 215 swap (&values[i++], &values[--j]); 216 } 217 218 /* Arranges the CNT 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 cnt) 227 { 228 if (cnt > 0) 229 { 230 size_t i = cnt - 1; 231 while (i != 0) 232 { 233 i--; 234 if (values[i] < values[i + 1]) 235 { 236 size_t j; 237 for (j = cnt - 1; values[i] >= values[j]; j--) 238 continue; 239 swap (values + i, values + j); 240 reverse (values + (i + 1), cnt - (i + 1)); 241 return true; 242 } 243 } 244 245 reverse (values, cnt); 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 CNT elements in ARRAY, each of which is 262 SIZE bytes in size. */ 263 static void 264 random_shuffle (void *array_, size_t cnt, size_t size) 265 { 266 char *array = array_; 267 char *tmp = xmalloc (size); 268 size_t i; 269 270 for (i = 0; i < cnt; i++) 271 { 272 size_t j = rand () % (cnt - 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 CNT 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 cnt, 335 hash_function *hash) 336 { 337 size_t i, j; 338 int *order; 339 340 check (hmap_is_empty (hmap) == (cnt == 0)); 341 check (hmap_count (hmap) == cnt); 342 check (cnt <= hmap_capacity (hmap)); 343 344 order = xmemdup (data, cnt * sizeof *data); 345 qsort (order, cnt, sizeof *order, compare_ints); 346 347 for (i = 0; i < cnt; i = j) 348 { 349 struct element *e; 350 int count; 351 352 for (j = i + 1; j < cnt; 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 (cnt == 0) 367 check (hmap_first (hmap) == NULL); 368 else 369 { 370 struct hmap_node *p; 371 int left; 372 373 left = cnt; 374 for (p = hmap_first (hmap), i = 0; i < cnt; 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 CNT values from 0 to CNT - 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 cnt, 404 hash_function *hash) 405 { 406 struct element *elements; 407 struct hmap hmap; 408 size_t i; 409 410 elements = xnmalloc (cnt, sizeof *elements); 411 for (i = 0; i < cnt; 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 < cnt; 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 < cnt; i++) 429 { 430 hmap_delete (&hmap, &elements[deletions[i]].node); 431 check_hmap (&hmap, deletions + i + 1, cnt - i - 1, hash); 432 } 433 hmap_destroy (&hmap); 434 435 free (elements); 436 } 437 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 cnt; 446 447 for (cnt = 0; cnt <= max_elems; cnt++) 448 { 449 int *insertions, *deletions; 450 unsigned int ins_perm_cnt; 451 int i; 452 453 insertions = xnmalloc (cnt, sizeof *insertions); 454 deletions = xnmalloc (cnt, sizeof *deletions); 455 for (i = 0; i < cnt; i++) 456 insertions[i] = i; 457 458 for (ins_perm_cnt = 0; 459 ins_perm_cnt == 0 || next_permutation (insertions, cnt); 460 ins_perm_cnt++) 461 { 462 unsigned int del_perm_cnt; 463 int i; 464 465 for (i = 0; i < cnt; i++) 466 deletions[i] = i; 467 468 for (del_perm_cnt = 0; 469 del_perm_cnt == 0 || next_permutation (deletions, cnt); 470 del_perm_cnt++) 471 test_insert_delete (insertions, deletions, cnt, hash); 472 473 check (del_perm_cnt == factorial (cnt)); 474 } 475 check (ins_perm_cnt == factorial (cnt)); 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 cnt; 508 509 for (cnt = 0; cnt <= max_elems; cnt++) 510 { 511 int *values; 512 unsigned int permutation_cnt; 513 int i; 514 515 values = xnmalloc (cnt, sizeof *values); 516 for (i = 0; i < cnt; i++) 517 values[i] = i; 518 519 for (permutation_cnt = 0; 520 permutation_cnt == 0 || next_permutation (values, cnt); 521 permutation_cnt++) 522 test_insert_delete (values, values, cnt, hash); 523 check (permutation_cnt == factorial (cnt)); 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 cnt; 555 556 for (cnt = 0; cnt <= max_elems; cnt++) 557 { 558 int *insertions, *deletions; 559 unsigned int permutation_cnt; 560 int i; 561 562 insertions = xnmalloc (cnt, sizeof *insertions); 563 deletions = xnmalloc (cnt, sizeof *deletions); 564 for (i = 0; i < cnt; i++) 565 insertions[i] = i; 566 567 for (permutation_cnt = 0; 568 permutation_cnt == 0 || next_permutation (insertions, cnt); 569 permutation_cnt++) 570 { 571 memcpy (deletions, insertions, sizeof *insertions * cnt); 572 reverse (deletions, cnt); 573 574 test_insert_delete (insertions, deletions, cnt, hash); 575 } 576 check (permutation_cnt == factorial (cnt)); 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 cnt; 608 609 for (cnt = 0; cnt <= max_elems; cnt += 2) 610 { 611 int *insertions, *deletions; 612 int trial; 613 int i; 614 615 insertions = xnmalloc (cnt, sizeof *insertions); 616 deletions = xnmalloc (cnt, sizeof *deletions); 617 for (i = 0; i < cnt; i++) 618 insertions[i] = i; 619 for (i = 0; i < cnt; i++) 620 deletions[i] = i; 621 622 for (trial = 0; trial < max_trials; trial++) 623 { 624 random_shuffle (insertions, cnt, sizeof *insertions); 625 random_shuffle (deletions, cnt, sizeof *deletions); 626 627 test_insert_delete (insertions, deletions, cnt, 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 cnt; 796 797 for (cnt = 0; cnt <= max_elems; cnt++) 798 { 799 int *values, *changed_values; 800 struct element *elements; 801 unsigned int permutation_cnt; 802 int i; 803 804 values = xnmalloc (cnt, sizeof *values); 805 changed_values = xnmalloc (cnt, sizeof *changed_values); 806 elements = xnmalloc (cnt, sizeof *elements); 807 for (i = 0; i < cnt; i++) 808 values[i] = i; 809 810 for (permutation_cnt = 0; 811 permutation_cnt == 0 || next_permutation (values, cnt); 812 permutation_cnt++) 813 { 814 for (i = 0; i < cnt; i++) 815 { 816 int j, k; 817 for (j = 0; j <= cnt; j++) 818 { 819 struct hmap hmap; 820 821 hmap_init (&hmap); 822 823 /* Add to HMAP in order. */ 824 for (k = 0; k < cnt; 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, cnt, 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 < cnt; k++) 838 changed_values[k] = k; 839 changed_values[i] = j; 840 check_hmap (&hmap, changed_values, cnt, hash); 841 842 hmap_destroy (&hmap); 843 } 844 } 845 } 846 check (permutation_cnt == factorial (cnt)); 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 cnt; 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 (cnt = 0; cnt <= max_elems; cnt++) 936 { 937 int i; 938 939 hmap_init (&hmap); 940 for (i = 0; i < cnt; 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 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 } 1154