1 /* hash - hashing table processing. 2 3 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004 Free 4 Software Foundation, Inc. 5 6 Written by Jim Meyering, 1992. 7 8 This program is free software; you can redistribute it and/or modify 9 it under the terms of the GNU General Public License as published by 10 the Free Software Foundation; either version 2, or (at your option) 11 any later version. 12 13 This program is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public License 19 along with this program; if not, write to the Free Software Foundation, 20 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 21 22 /* A generic hash table package. */ 23 24 /* Define USE_OBSTACK to 1 if you want the allocator to use obstacks instead 25 of malloc. If you change USE_OBSTACK, you have to recompile! */ 26 27 #ifdef HAVE_CONFIG_H 28 # include <config.h> 29 #endif 30 31 #include "hash.h" 32 #include "xalloc.h" 33 34 #include <limits.h> 35 #include <stdio.h> 36 #include <stdlib.h> 37 38 #if USE_OBSTACK 39 # include "obstack.h" 40 # ifndef obstack_chunk_alloc 41 # define obstack_chunk_alloc malloc 42 # endif 43 # ifndef obstack_chunk_free 44 # define obstack_chunk_free free 45 # endif 46 #endif 47 48 #ifndef SIZE_MAX 49 # define SIZE_MAX ((size_t) -1) 50 #endif 51 52 struct hash_table 53 { 54 /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1, 55 for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets 56 are not empty, there are N_ENTRIES active entries in the table. */ 57 struct hash_entry *bucket; 58 struct hash_entry const *bucket_limit; 59 size_t n_buckets; 60 size_t n_buckets_used; 61 size_t n_entries; 62 63 /* Tuning arguments, kept in a physicaly separate structure. */ 64 const Hash_tuning *tuning; 65 66 /* Three functions are given to `hash_initialize', see the documentation 67 block for this function. In a word, HASHER randomizes a user entry 68 into a number up from 0 up to some maximum minus 1; COMPARATOR returns 69 true if two user entries compare equally; and DATA_FREER is the cleanup 70 function for a user entry. */ 71 Hash_hasher hasher; 72 Hash_comparator comparator; 73 Hash_data_freer data_freer; 74 75 /* A linked list of freed struct hash_entry structs. */ 76 struct hash_entry *free_entry_list; 77 78 #if USE_OBSTACK 79 /* Whenever obstacks are used, it is possible to allocate all overflowed 80 entries into a single stack, so they all can be freed in a single 81 operation. It is not clear if the speedup is worth the trouble. */ 82 struct obstack entry_stack; 83 #endif 84 }; 85 86 /* A hash table contains many internal entries, each holding a pointer to 87 some user provided data (also called a user entry). An entry indistinctly 88 refers to both the internal entry and its associated user entry. A user 89 entry contents may be hashed by a randomization function (the hashing 90 function, or just `hasher' for short) into a number (or `slot') between 0 91 and the current table size. At each slot position in the hash table, 92 starts a linked chain of entries for which the user data all hash to this 93 slot. A bucket is the collection of all entries hashing to the same slot. 94 95 A good `hasher' function will distribute entries rather evenly in buckets. 96 In the ideal case, the length of each bucket is roughly the number of 97 entries divided by the table size. Finding the slot for a data is usually 98 done in constant time by the `hasher', and the later finding of a precise 99 entry is linear in time with the size of the bucket. Consequently, a 100 larger hash table size (that is, a larger number of buckets) is prone to 101 yielding shorter chains, *given* the `hasher' function behaves properly. 102 103 Long buckets slow down the lookup algorithm. One might use big hash table 104 sizes in hope to reduce the average length of buckets, but this might 105 become inordinate, as unused slots in the hash table take some space. The 106 best bet is to make sure you are using a good `hasher' function (beware 107 that those are not that easy to write! :-), and to use a table size 108 larger than the actual number of entries. */ 109 110 /* If an insertion makes the ratio of nonempty buckets to table size larger 111 than the growth threshold (a number between 0.0 and 1.0), then increase 112 the table size by multiplying by the growth factor (a number greater than 113 1.0). The growth threshold defaults to 0.8, and the growth factor 114 defaults to 1.414, meaning that the table will have doubled its size 115 every second time 80% of the buckets get used. */ 116 #define DEFAULT_GROWTH_THRESHOLD 0.8 117 #define DEFAULT_GROWTH_FACTOR 1.414 118 119 /* If a deletion empties a bucket and causes the ratio of used buckets to 120 table size to become smaller than the shrink threshold (a number between 121 0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a 122 number greater than the shrink threshold but smaller than 1.0). The shrink 123 threshold and factor default to 0.0 and 1.0, meaning that the table never 124 shrinks. */ 125 #define DEFAULT_SHRINK_THRESHOLD 0.0 126 #define DEFAULT_SHRINK_FACTOR 1.0 127 128 /* Use this to initialize or reset a TUNING structure to 129 some sensible values. */ 130 static const Hash_tuning default_tuning = 131 { 132 DEFAULT_SHRINK_THRESHOLD, 133 DEFAULT_SHRINK_FACTOR, 134 DEFAULT_GROWTH_THRESHOLD, 135 DEFAULT_GROWTH_FACTOR, 136 false 137 }; 138 139 /* Information and lookup. */ 140 141 /* The following few functions provide information about the overall hash 142 table organization: the number of entries, number of buckets and maximum 143 length of buckets. */ 144 145 /* Return the number of buckets in the hash table. The table size, the total 146 number of buckets (used plus unused), or the maximum number of slots, are 147 the same quantity. */ 148 149 size_t 150 hash_get_n_buckets (const Hash_table *table) 151 { 152 return table->n_buckets; 153 } 154 155 /* Return the number of slots in use (non-empty buckets). */ 156 157 size_t 158 hash_get_n_buckets_used (const Hash_table *table) 159 { 160 return table->n_buckets_used; 161 } 162 163 /* Return the number of active entries. */ 164 165 size_t 166 hash_get_n_entries (const Hash_table *table) 167 { 168 return table->n_entries; 169 } 170 171 /* Return the length of the longest chain (bucket). */ 172 173 size_t 174 hash_get_max_bucket_length (const Hash_table *table) 175 { 176 struct hash_entry const *bucket; 177 size_t max_bucket_length = 0; 178 179 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 180 { 181 if (bucket->data) 182 { 183 struct hash_entry const *cursor = bucket; 184 size_t bucket_length = 1; 185 186 while (cursor = cursor->next, cursor) 187 bucket_length++; 188 189 if (bucket_length > max_bucket_length) 190 max_bucket_length = bucket_length; 191 } 192 } 193 194 return max_bucket_length; 195 } 196 197 /* Do a mild validation of a hash table, by traversing it and checking two 198 statistics. */ 199 200 bool 201 hash_table_ok (const Hash_table *table) 202 { 203 struct hash_entry const *bucket; 204 size_t n_buckets_used = 0; 205 size_t n_entries = 0; 206 207 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 208 { 209 if (bucket->data) 210 { 211 struct hash_entry const *cursor = bucket; 212 213 /* Count bucket head. */ 214 n_buckets_used++; 215 n_entries++; 216 217 /* Count bucket overflow. */ 218 while (cursor = cursor->next, cursor) 219 n_entries++; 220 } 221 } 222 223 if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries) 224 return true; 225 226 return false; 227 } 228 229 void 230 hash_print_statistics (const Hash_table *table, FILE *stream) 231 { 232 size_t n_entries = hash_get_n_entries (table); 233 size_t n_buckets = hash_get_n_buckets (table); 234 size_t n_buckets_used = hash_get_n_buckets_used (table); 235 size_t max_bucket_length = hash_get_max_bucket_length (table); 236 237 fprintf (stream, "# entries: %lu\n", (unsigned long int) n_entries); 238 fprintf (stream, "# buckets: %lu\n", (unsigned long int) n_buckets); 239 fprintf (stream, "# buckets used: %lu (%.2f%%)\n", 240 (unsigned long int) n_buckets_used, 241 (100.0 * n_buckets_used) / n_buckets); 242 fprintf (stream, "max bucket length: %lu\n", 243 (unsigned long int) max_bucket_length); 244 } 245 246 /* If ENTRY matches an entry already in the hash table, return the 247 entry from the table. Otherwise, return NULL. */ 248 249 void * 250 hash_lookup (const Hash_table *table, const void *entry) 251 { 252 struct hash_entry const *bucket 253 = table->bucket + table->hasher (entry, table->n_buckets); 254 struct hash_entry const *cursor; 255 256 if (! (bucket < table->bucket_limit)) 257 abort (); 258 259 if (bucket->data == NULL) 260 return NULL; 261 262 for (cursor = bucket; cursor; cursor = cursor->next) 263 if (table->comparator (entry, cursor->data)) 264 return cursor->data; 265 266 return NULL; 267 } 268 269 /* Walking. */ 270 271 /* The functions in this page traverse the hash table and process the 272 contained entries. For the traversal to work properly, the hash table 273 should not be resized nor modified while any particular entry is being 274 processed. In particular, entries should not be added or removed. */ 275 276 /* Return the first data in the table, or NULL if the table is empty. */ 277 278 void * 279 hash_get_first (const Hash_table *table) 280 { 281 struct hash_entry const *bucket; 282 283 if (table->n_entries == 0) 284 return NULL; 285 286 for (bucket = table->bucket; ; bucket++) 287 if (! (bucket < table->bucket_limit)) 288 abort (); 289 else if (bucket->data) 290 return bucket->data; 291 } 292 293 /* Return the user data for the entry following ENTRY, where ENTRY has been 294 returned by a previous call to either `hash_get_first' or `hash_get_next'. 295 Return NULL if there are no more entries. */ 296 297 void * 298 hash_get_next (const Hash_table *table, const void *entry) 299 { 300 struct hash_entry const *bucket 301 = table->bucket + table->hasher (entry, table->n_buckets); 302 struct hash_entry const *cursor; 303 304 if (! (bucket < table->bucket_limit)) 305 abort (); 306 307 /* Find next entry in the same bucket. */ 308 for (cursor = bucket; cursor; cursor = cursor->next) 309 if (cursor->data == entry && cursor->next) 310 return cursor->next->data; 311 312 /* Find first entry in any subsequent bucket. */ 313 while (++bucket < table->bucket_limit) 314 if (bucket->data) 315 return bucket->data; 316 317 /* None found. */ 318 return NULL; 319 } 320 321 /* Fill BUFFER with pointers to active user entries in the hash table, then 322 return the number of pointers copied. Do not copy more than BUFFER_SIZE 323 pointers. */ 324 325 size_t 326 hash_get_entries (const Hash_table *table, void **buffer, 327 size_t buffer_size) 328 { 329 size_t counter = 0; 330 struct hash_entry const *bucket; 331 struct hash_entry const *cursor; 332 333 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 334 { 335 if (bucket->data) 336 { 337 for (cursor = bucket; cursor; cursor = cursor->next) 338 { 339 if (counter >= buffer_size) 340 return counter; 341 buffer[counter++] = cursor->data; 342 } 343 } 344 } 345 346 return counter; 347 } 348 349 /* Call a PROCESSOR function for each entry of a hash table, and return the 350 number of entries for which the processor function returned success. A 351 pointer to some PROCESSOR_DATA which will be made available to each call to 352 the processor function. The PROCESSOR accepts two arguments: the first is 353 the user entry being walked into, the second is the value of PROCESSOR_DATA 354 as received. The walking continue for as long as the PROCESSOR function 355 returns nonzero. When it returns zero, the walking is interrupted. */ 356 357 size_t 358 hash_do_for_each (const Hash_table *table, Hash_processor processor, 359 void *processor_data) 360 { 361 size_t counter = 0; 362 struct hash_entry const *bucket; 363 struct hash_entry const *cursor; 364 365 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 366 { 367 if (bucket->data) 368 { 369 for (cursor = bucket; cursor; cursor = cursor->next) 370 { 371 if (!(*processor) (cursor->data, processor_data)) 372 return counter; 373 counter++; 374 } 375 } 376 } 377 378 return counter; 379 } 380 381 /* Allocation and clean-up. */ 382 383 /* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1. 384 This is a convenience routine for constructing other hashing functions. */ 385 386 #if USE_DIFF_HASH 387 388 /* About hashings, Paul Eggert writes to me (FP), on 1994-01-01: "Please see 389 B. J. McKenzie, R. Harries & T. Bell, Selecting a hashing algorithm, 390 Software--practice & experience 20, 2 (Feb 1990), 209-224. Good hash 391 algorithms tend to be domain-specific, so what's good for [diffutils'] io.c 392 may not be good for your application." */ 393 394 size_t 395 hash_string (const char *string, size_t n_buckets) 396 { 397 # define ROTATE_LEFT(Value, Shift) \ 398 ((Value) << (Shift) | (Value) >> ((sizeof (size_t) * CHAR_BIT) - (Shift))) 399 # define HASH_ONE_CHAR(Value, Byte) \ 400 ((Byte) + ROTATE_LEFT (Value, 7)) 401 402 size_t value = 0; 403 unsigned char ch; 404 405 for (; (ch = *string); string++) 406 value = HASH_ONE_CHAR (value, ch); 407 return value % n_buckets; 408 409 # undef ROTATE_LEFT 410 # undef HASH_ONE_CHAR 411 } 412 413 #else /* not USE_DIFF_HASH */ 414 415 /* This one comes from `recode', and performs a bit better than the above as 416 per a few experiments. It is inspired from a hashing routine found in the 417 very old Cyber `snoop', itself written in typical Greg Mansfield style. 418 (By the way, what happened to this excellent man? Is he still alive?) */ 419 420 size_t 421 hash_string (const char *string, size_t n_buckets) 422 { 423 size_t value = 0; 424 unsigned char ch; 425 426 for (; (ch = *string); string++) 427 value = (value * 31 + ch) % n_buckets; 428 return value; 429 } 430 431 #endif /* not USE_DIFF_HASH */ 432 433 /* Return true if CANDIDATE is a prime number. CANDIDATE should be an odd 434 number at least equal to 11. */ 435 436 static bool 437 is_prime (size_t candidate) 438 { 439 size_t divisor = 3; 440 size_t square = divisor * divisor; 441 442 while (square < candidate && (candidate % divisor)) 443 { 444 divisor++; 445 square += 4 * divisor; 446 divisor++; 447 } 448 449 return (candidate % divisor ? true : false); 450 } 451 452 /* Round a given CANDIDATE number up to the nearest prime, and return that 453 prime. Primes lower than 10 are merely skipped. */ 454 455 static size_t 456 next_prime (size_t candidate) 457 { 458 /* Skip small primes. */ 459 if (candidate < 10) 460 candidate = 10; 461 462 /* Make it definitely odd. */ 463 candidate |= 1; 464 465 while (!is_prime (candidate)) 466 candidate += 2; 467 468 return candidate; 469 } 470 471 void 472 hash_reset_tuning (Hash_tuning *tuning) 473 { 474 *tuning = default_tuning; 475 } 476 477 /* For the given hash TABLE, check the user supplied tuning structure for 478 reasonable values, and return true if there is no gross error with it. 479 Otherwise, definitively reset the TUNING field to some acceptable default 480 in the hash table (that is, the user loses the right of further modifying 481 tuning arguments), and return false. */ 482 483 static bool 484 check_tuning (Hash_table *table) 485 { 486 const Hash_tuning *tuning = table->tuning; 487 488 /* Be a bit stricter than mathematics would require, so that 489 rounding errors in size calculations do not cause allocations to 490 fail to grow or shrink as they should. The smallest allocation 491 is 11 (due to next_prime's algorithm), so an epsilon of 0.1 492 should be good enough. */ 493 float epsilon = 0.1f; 494 495 if (epsilon < tuning->growth_threshold 496 && tuning->growth_threshold < 1 - epsilon 497 && 1 + epsilon < tuning->growth_factor 498 && 0 <= tuning->shrink_threshold 499 && tuning->shrink_threshold + epsilon < tuning->shrink_factor 500 && tuning->shrink_factor <= 1 501 && tuning->shrink_threshold + epsilon < tuning->growth_threshold) 502 return true; 503 504 table->tuning = &default_tuning; 505 return false; 506 } 507 508 /* Allocate and return a new hash table, or NULL upon failure. The initial 509 number of buckets is automatically selected so as to _guarantee_ that you 510 may insert at least CANDIDATE different user entries before any growth of 511 the hash table size occurs. So, if have a reasonably tight a-priori upper 512 bound on the number of entries you intend to insert in the hash table, you 513 may save some table memory and insertion time, by specifying it here. If 514 the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE 515 argument has its meaning changed to the wanted number of buckets. 516 517 TUNING points to a structure of user-supplied values, in case some fine 518 tuning is wanted over the default behavior of the hasher. If TUNING is 519 NULL, the default tuning parameters are used instead. 520 521 The user-supplied HASHER function should be provided. It accepts two 522 arguments ENTRY and TABLE_SIZE. It computes, by hashing ENTRY contents, a 523 slot number for that entry which should be in the range 0..TABLE_SIZE-1. 524 This slot number is then returned. 525 526 The user-supplied COMPARATOR function should be provided. It accepts two 527 arguments pointing to user data, it then returns true for a pair of entries 528 that compare equal, or false otherwise. This function is internally called 529 on entries which are already known to hash to the same bucket index. 530 531 The user-supplied DATA_FREER function, when not NULL, may be later called 532 with the user data as an argument, just before the entry containing the 533 data gets freed. This happens from within `hash_free' or `hash_clear'. 534 You should specify this function only if you want these functions to free 535 all of your `data' data. This is typically the case when your data is 536 simply an auxiliary struct that you have malloc'd to aggregate several 537 values. */ 538 539 Hash_table * 540 hash_initialize (size_t candidate, const Hash_tuning *tuning, 541 Hash_hasher hasher, Hash_comparator comparator, 542 Hash_data_freer data_freer) 543 { 544 Hash_table *table; 545 546 if (hasher == NULL || comparator == NULL) 547 return NULL; 548 549 table = malloc (sizeof *table); 550 if (table == NULL) 551 return NULL; 552 553 if (!tuning) 554 tuning = &default_tuning; 555 table->tuning = tuning; 556 if (!check_tuning (table)) 557 { 558 /* Fail if the tuning options are invalid. This is the only occasion 559 when the user gets some feedback about it. Once the table is created, 560 if the user provides invalid tuning options, we silently revert to 561 using the defaults, and ignore further request to change the tuning 562 options. */ 563 goto fail; 564 } 565 566 if (!tuning->is_n_buckets) 567 { 568 float new_candidate = candidate / tuning->growth_threshold; 569 if (SIZE_MAX <= new_candidate) 570 goto fail; 571 candidate = new_candidate; 572 } 573 574 if (xalloc_oversized (candidate, sizeof *table->bucket)) 575 goto fail; 576 table->n_buckets = next_prime (candidate); 577 if (xalloc_oversized (table->n_buckets, sizeof *table->bucket)) 578 goto fail; 579 580 table->bucket = calloc (table->n_buckets, sizeof *table->bucket); 581 table->bucket_limit = table->bucket + table->n_buckets; 582 table->n_buckets_used = 0; 583 table->n_entries = 0; 584 585 table->hasher = hasher; 586 table->comparator = comparator; 587 table->data_freer = data_freer; 588 589 table->free_entry_list = NULL; 590 #if USE_OBSTACK 591 obstack_init (&table->entry_stack); 592 #endif 593 return table; 594 595 fail: 596 free (table); 597 return NULL; 598 } 599 600 /* Make all buckets empty, placing any chained entries on the free list. 601 Apply the user-specified function data_freer (if any) to the datas of any 602 affected entries. */ 603 604 void 605 hash_clear (Hash_table *table) 606 { 607 struct hash_entry *bucket; 608 609 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 610 { 611 if (bucket->data) 612 { 613 struct hash_entry *cursor; 614 struct hash_entry *next; 615 616 /* Free the bucket overflow. */ 617 for (cursor = bucket->next; cursor; cursor = next) 618 { 619 if (table->data_freer) 620 (*table->data_freer) (cursor->data); 621 cursor->data = NULL; 622 623 next = cursor->next; 624 /* Relinking is done one entry at a time, as it is to be expected 625 that overflows are either rare or short. */ 626 cursor->next = table->free_entry_list; 627 table->free_entry_list = cursor; 628 } 629 630 /* Free the bucket head. */ 631 if (table->data_freer) 632 (*table->data_freer) (bucket->data); 633 bucket->data = NULL; 634 bucket->next = NULL; 635 } 636 } 637 638 table->n_buckets_used = 0; 639 table->n_entries = 0; 640 } 641 642 /* Reclaim all storage associated with a hash table. If a data_freer 643 function has been supplied by the user when the hash table was created, 644 this function applies it to the data of each entry before freeing that 645 entry. */ 646 647 void 648 hash_free (Hash_table *table) 649 { 650 struct hash_entry *bucket; 651 struct hash_entry *cursor; 652 struct hash_entry *next; 653 654 /* Call the user data_freer function. */ 655 if (table->data_freer && table->n_entries) 656 { 657 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 658 { 659 if (bucket->data) 660 { 661 for (cursor = bucket; cursor; cursor = cursor->next) 662 { 663 (*table->data_freer) (cursor->data); 664 } 665 } 666 } 667 } 668 669 #if USE_OBSTACK 670 671 obstack_free (&table->entry_stack, NULL); 672 673 #else 674 675 /* Free all bucket overflowed entries. */ 676 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 677 { 678 for (cursor = bucket->next; cursor; cursor = next) 679 { 680 next = cursor->next; 681 free (cursor); 682 } 683 } 684 685 /* Also reclaim the internal list of previously freed entries. */ 686 for (cursor = table->free_entry_list; cursor; cursor = next) 687 { 688 next = cursor->next; 689 free (cursor); 690 } 691 692 #endif 693 694 /* Free the remainder of the hash table structure. */ 695 free (table->bucket); 696 free (table); 697 } 698 699 /* Insertion and deletion. */ 700 701 /* Get a new hash entry for a bucket overflow, possibly by reclying a 702 previously freed one. If this is not possible, allocate a new one. */ 703 704 static struct hash_entry * 705 allocate_entry (Hash_table *table) 706 { 707 struct hash_entry *new; 708 709 if (table->free_entry_list) 710 { 711 new = table->free_entry_list; 712 table->free_entry_list = new->next; 713 } 714 else 715 { 716 #if USE_OBSTACK 717 new = obstack_alloc (&table->entry_stack, sizeof *new); 718 #else 719 new = malloc (sizeof *new); 720 #endif 721 } 722 723 return new; 724 } 725 726 /* Free a hash entry which was part of some bucket overflow, 727 saving it for later recycling. */ 728 729 static void 730 free_entry (Hash_table *table, struct hash_entry *entry) 731 { 732 entry->data = NULL; 733 entry->next = table->free_entry_list; 734 table->free_entry_list = entry; 735 } 736 737 /* This private function is used to help with insertion and deletion. When 738 ENTRY matches an entry in the table, return a pointer to the corresponding 739 user data and set *BUCKET_HEAD to the head of the selected bucket. 740 Otherwise, return NULL. When DELETE is true and ENTRY matches an entry in 741 the table, unlink the matching entry. */ 742 743 static void * 744 hash_find_entry (Hash_table *table, const void *entry, 745 struct hash_entry **bucket_head, bool delete) 746 { 747 struct hash_entry *bucket 748 = table->bucket + table->hasher (entry, table->n_buckets); 749 struct hash_entry *cursor; 750 751 if (! (bucket < table->bucket_limit)) 752 abort (); 753 754 *bucket_head = bucket; 755 756 /* Test for empty bucket. */ 757 if (bucket->data == NULL) 758 return NULL; 759 760 /* See if the entry is the first in the bucket. */ 761 if ((*table->comparator) (entry, bucket->data)) 762 { 763 void *data = bucket->data; 764 765 if (delete) 766 { 767 if (bucket->next) 768 { 769 struct hash_entry *next = bucket->next; 770 771 /* Bump the first overflow entry into the bucket head, then save 772 the previous first overflow entry for later recycling. */ 773 *bucket = *next; 774 free_entry (table, next); 775 } 776 else 777 { 778 bucket->data = NULL; 779 } 780 } 781 782 return data; 783 } 784 785 /* Scan the bucket overflow. */ 786 for (cursor = bucket; cursor->next; cursor = cursor->next) 787 { 788 if ((*table->comparator) (entry, cursor->next->data)) 789 { 790 void *data = cursor->next->data; 791 792 if (delete) 793 { 794 struct hash_entry *next = cursor->next; 795 796 /* Unlink the entry to delete, then save the freed entry for later 797 recycling. */ 798 cursor->next = next->next; 799 free_entry (table, next); 800 } 801 802 return data; 803 } 804 } 805 806 /* No entry found. */ 807 return NULL; 808 } 809 810 /* For an already existing hash table, change the number of buckets through 811 specifying CANDIDATE. The contents of the hash table are preserved. The 812 new number of buckets is automatically selected so as to _guarantee_ that 813 the table may receive at least CANDIDATE different user entries, including 814 those already in the table, before any other growth of the hash table size 815 occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the 816 exact number of buckets desired. */ 817 818 bool 819 hash_rehash (Hash_table *table, size_t candidate) 820 { 821 Hash_table *new_table; 822 struct hash_entry *bucket; 823 struct hash_entry *cursor; 824 struct hash_entry *next; 825 826 new_table = hash_initialize (candidate, table->tuning, table->hasher, 827 table->comparator, table->data_freer); 828 if (new_table == NULL) 829 return false; 830 831 /* Merely reuse the extra old space into the new table. */ 832 #if USE_OBSTACK 833 obstack_free (&new_table->entry_stack, NULL); 834 new_table->entry_stack = table->entry_stack; 835 #endif 836 new_table->free_entry_list = table->free_entry_list; 837 838 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 839 if (bucket->data) 840 for (cursor = bucket; cursor; cursor = next) 841 { 842 void *data = cursor->data; 843 struct hash_entry *new_bucket 844 = (new_table->bucket 845 + new_table->hasher (data, new_table->n_buckets)); 846 847 if (! (new_bucket < new_table->bucket_limit)) 848 abort (); 849 850 next = cursor->next; 851 852 if (new_bucket->data) 853 { 854 if (cursor == bucket) 855 { 856 /* Allocate or recycle an entry, when moving from a bucket 857 header into a bucket overflow. */ 858 struct hash_entry *new_entry = allocate_entry (new_table); 859 860 if (new_entry == NULL) 861 return false; 862 863 new_entry->data = data; 864 new_entry->next = new_bucket->next; 865 new_bucket->next = new_entry; 866 } 867 else 868 { 869 /* Merely relink an existing entry, when moving from a 870 bucket overflow into a bucket overflow. */ 871 cursor->next = new_bucket->next; 872 new_bucket->next = cursor; 873 } 874 } 875 else 876 { 877 /* Free an existing entry, when moving from a bucket 878 overflow into a bucket header. Also take care of the 879 simple case of moving from a bucket header into a bucket 880 header. */ 881 new_bucket->data = data; 882 new_table->n_buckets_used++; 883 if (cursor != bucket) 884 free_entry (new_table, cursor); 885 } 886 } 887 888 free (table->bucket); 889 table->bucket = new_table->bucket; 890 table->bucket_limit = new_table->bucket_limit; 891 table->n_buckets = new_table->n_buckets; 892 table->n_buckets_used = new_table->n_buckets_used; 893 table->free_entry_list = new_table->free_entry_list; 894 /* table->n_entries already holds its value. */ 895 #if USE_OBSTACK 896 table->entry_stack = new_table->entry_stack; 897 #endif 898 free (new_table); 899 900 return true; 901 } 902 903 /* If ENTRY matches an entry already in the hash table, return the pointer 904 to the entry from the table. Otherwise, insert ENTRY and return ENTRY. 905 Return NULL if the storage required for insertion cannot be allocated. */ 906 907 void * 908 hash_insert (Hash_table *table, const void *entry) 909 { 910 void *data; 911 struct hash_entry *bucket; 912 913 /* The caller cannot insert a NULL entry. */ 914 if (! entry) 915 abort (); 916 917 /* If there's a matching entry already in the table, return that. */ 918 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL) 919 return data; 920 921 /* ENTRY is not matched, it should be inserted. */ 922 923 if (bucket->data) 924 { 925 struct hash_entry *new_entry = allocate_entry (table); 926 927 if (new_entry == NULL) 928 return NULL; 929 930 /* Add ENTRY in the overflow of the bucket. */ 931 932 new_entry->data = (void *) entry; 933 new_entry->next = bucket->next; 934 bucket->next = new_entry; 935 table->n_entries++; 936 return (void *) entry; 937 } 938 939 /* Add ENTRY right in the bucket head. */ 940 941 bucket->data = (void *) entry; 942 table->n_entries++; 943 table->n_buckets_used++; 944 945 /* If the growth threshold of the buckets in use has been reached, increase 946 the table size and rehash. There's no point in checking the number of 947 entries: if the hashing function is ill-conditioned, rehashing is not 948 likely to improve it. */ 949 950 if (table->n_buckets_used 951 > table->tuning->growth_threshold * table->n_buckets) 952 { 953 /* Check more fully, before starting real work. If tuning arguments 954 became invalid, the second check will rely on proper defaults. */ 955 check_tuning (table); 956 if (table->n_buckets_used 957 > table->tuning->growth_threshold * table->n_buckets) 958 { 959 const Hash_tuning *tuning = table->tuning; 960 float candidate = 961 (tuning->is_n_buckets 962 ? (table->n_buckets * tuning->growth_factor) 963 : (table->n_buckets * tuning->growth_factor 964 * tuning->growth_threshold)); 965 966 if (SIZE_MAX <= candidate) 967 return NULL; 968 969 /* If the rehash fails, arrange to return NULL. */ 970 if (!hash_rehash (table, candidate)) 971 entry = NULL; 972 } 973 } 974 975 return (void *) entry; 976 } 977 978 /* If ENTRY is already in the table, remove it and return the just-deleted 979 data (the user may want to deallocate its storage). If ENTRY is not in the 980 table, don't modify the table and return NULL. */ 981 982 void * 983 hash_delete (Hash_table *table, const void *entry) 984 { 985 void *data; 986 struct hash_entry *bucket; 987 988 data = hash_find_entry (table, entry, &bucket, true); 989 if (!data) 990 return NULL; 991 992 table->n_entries--; 993 if (!bucket->data) 994 { 995 table->n_buckets_used--; 996 997 /* If the shrink threshold of the buckets in use has been reached, 998 rehash into a smaller table. */ 999 1000 if (table->n_buckets_used 1001 < table->tuning->shrink_threshold * table->n_buckets) 1002 { 1003 /* Check more fully, before starting real work. If tuning arguments 1004 became invalid, the second check will rely on proper defaults. */ 1005 check_tuning (table); 1006 if (table->n_buckets_used 1007 < table->tuning->shrink_threshold * table->n_buckets) 1008 { 1009 const Hash_tuning *tuning = table->tuning; 1010 size_t candidate = 1011 (tuning->is_n_buckets 1012 ? table->n_buckets * tuning->shrink_factor 1013 : (table->n_buckets * tuning->shrink_factor 1014 * tuning->growth_threshold)); 1015 1016 hash_rehash (table, candidate); 1017 } 1018 } 1019 } 1020 1021 return data; 1022 } 1023 1024 /* Testing. */ 1025 1026 #if TESTING 1027 1028 void 1029 hash_print (const Hash_table *table) 1030 { 1031 struct hash_entry const *bucket; 1032 1033 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++) 1034 { 1035 struct hash_entry *cursor; 1036 1037 if (bucket) 1038 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket)); 1039 1040 for (cursor = bucket; cursor; cursor = cursor->next) 1041 { 1042 char const *s = cursor->data; 1043 /* FIXME */ 1044 if (s) 1045 printf (" %s\n", s); 1046 } 1047 } 1048 } 1049 1050 #endif /* TESTING */ 1051
