1/* An expandable hash tables datatype. 2 Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004 3 Free Software Foundation, Inc. 4 Contributed by Vladimir Makarov (vmakarov@cygnus.com). 5 6This file is part of the libiberty library. 7Libiberty is free software; you can redistribute it and/or 8modify it under the terms of the GNU Library General Public 9License as published by the Free Software Foundation; either 10version 2 of the License, or (at your option) any later version. 11 12Libiberty is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15Library General Public License for more details. 16 17You should have received a copy of the GNU Library General Public 18License along with libiberty; see the file COPYING.LIB. If 19not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, 20Boston, MA 02111-1307, USA. */ 21 22/* This package implements basic hash table functionality. It is possible 23 to search for an entry, create an entry and destroy an entry. 24 25 Elements in the table are generic pointers. 26 27 The size of the table is not fixed; if the occupancy of the table 28 grows too high the hash table will be expanded. 29 30 The abstract data implementation is based on generalized Algorithm D 31 from Knuth's book "The art of computer programming". Hash table is 32 expanded by creation of new hash table and transferring elements from 33 the old table to the new table. */ 34 35#ifdef HAVE_CONFIG_H 36#include "config.h" 37#endif 38 39#include <sys/types.h> 40 41#ifdef HAVE_STDLIB_H 42#include <stdlib.h> 43#endif 44#ifdef HAVE_STRING_H 45#include <string.h> 46#endif 47#ifdef HAVE_MALLOC_H 48#include <malloc.h> 49#endif 50#ifdef HAVE_LIMITS_H 51#include <limits.h> 52#endif 53#ifdef HAVE_STDINT_H 54#include <stdint.h> 55#endif 56 57#include <stdio.h> 58 59#include "libiberty.h" 60#include "ansidecl.h" 61#include "hashtab.h" 62 63#ifndef CHAR_BIT 64#define CHAR_BIT 8 65#endif 66 67/* This macro defines reserved value for empty table entry. */ 68 69#define EMPTY_ENTRY ((PTR) 0) 70 71/* This macro defines reserved value for table entry which contained 72 a deleted element. */ 73 74#define DELETED_ENTRY ((PTR) 1) 75 76static unsigned int higher_prime_index PARAMS ((unsigned long)); 77static hashval_t htab_mod_1 PARAMS ((hashval_t, hashval_t, hashval_t, int)); 78static hashval_t htab_mod PARAMS ((hashval_t, htab_t)); 79static hashval_t htab_mod_m2 PARAMS ((hashval_t, htab_t)); 80static hashval_t hash_pointer PARAMS ((const void *)); 81static int eq_pointer PARAMS ((const void *, const void *)); 82static int htab_expand PARAMS ((htab_t)); 83static PTR *find_empty_slot_for_expand PARAMS ((htab_t, hashval_t)); 84 85/* At some point, we could make these be NULL, and modify the 86 hash-table routines to handle NULL specially; that would avoid 87 function-call overhead for the common case of hashing pointers. */ 88htab_hash htab_hash_pointer = hash_pointer; 89htab_eq htab_eq_pointer = eq_pointer; 90 91/* Table of primes and multiplicative inverses. 92 93 Note that these are not minimally reduced inverses. Unlike when generating 94 code to divide by a constant, we want to be able to use the same algorithm 95 all the time. All of these inverses (are implied to) have bit 32 set. 96 97 For the record, here's the function that computed the table; it's a 98 vastly simplified version of the function of the same name from gcc. */ 99 100#if 0 101unsigned int 102ceil_log2 (unsigned int x) 103{ 104 int i; 105 for (i = 31; i >= 0 ; --i) 106 if (x > (1u << i)) 107 return i+1; 108 abort (); 109} 110 111unsigned int 112choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp) 113{ 114 unsigned long long mhigh; 115 double nx; 116 int lgup, post_shift; 117 int pow, pow2; 118 int n = 32, precision = 32; 119 120 lgup = ceil_log2 (d); 121 pow = n + lgup; 122 pow2 = n + lgup - precision; 123 124 nx = ldexp (1.0, pow) + ldexp (1.0, pow2); 125 mhigh = nx / d; 126 127 *shiftp = lgup - 1; 128 *mlp = mhigh; 129 return mhigh >> 32; 130} 131#endif 132 133struct prime_ent 134{ 135 hashval_t prime; 136 hashval_t inv; 137 hashval_t inv_m2; /* inverse of prime-2 */ 138 hashval_t shift; 139}; 140 141static struct prime_ent const prime_tab[] = { 142 { 7, 0x24924925, 0x9999999b, 2 }, 143 { 13, 0x3b13b13c, 0x745d1747, 3 }, 144 { 31, 0x08421085, 0x1a7b9612, 4 }, 145 { 61, 0x0c9714fc, 0x15b1e5f8, 5 }, 146 { 127, 0x02040811, 0x0624dd30, 6 }, 147 { 251, 0x05197f7e, 0x073260a5, 7 }, 148 { 509, 0x01824366, 0x02864fc8, 8 }, 149 { 1021, 0x00c0906d, 0x014191f7, 9 }, 150 { 2039, 0x0121456f, 0x0161e69e, 10 }, 151 { 4093, 0x00300902, 0x00501908, 11 }, 152 { 8191, 0x00080041, 0x00180241, 12 }, 153 { 16381, 0x000c0091, 0x00140191, 13 }, 154 { 32749, 0x002605a5, 0x002a06e6, 14 }, 155 { 65521, 0x000f00e2, 0x00110122, 15 }, 156 { 131071, 0x00008001, 0x00018003, 16 }, 157 { 262139, 0x00014002, 0x0001c004, 17 }, 158 { 524287, 0x00002001, 0x00006001, 18 }, 159 { 1048573, 0x00003001, 0x00005001, 19 }, 160 { 2097143, 0x00004801, 0x00005801, 20 }, 161 { 4194301, 0x00000c01, 0x00001401, 21 }, 162 { 8388593, 0x00001e01, 0x00002201, 22 }, 163 { 16777213, 0x00000301, 0x00000501, 23 }, 164 { 33554393, 0x00001381, 0x00001481, 24 }, 165 { 67108859, 0x00000141, 0x000001c1, 25 }, 166 { 134217689, 0x000004e1, 0x00000521, 26 }, 167 { 268435399, 0x00000391, 0x000003b1, 27 }, 168 { 536870909, 0x00000019, 0x00000029, 28 }, 169 { 1073741789, 0x0000008d, 0x00000095, 29 }, 170 { 2147483647, 0x00000003, 0x00000007, 30 }, 171 /* Avoid "decimal constant so large it is unsigned" for 4294967291. */ 172 { 0xfffffffb, 0x00000006, 0x00000008, 31 } 173}; 174 175/* The following function returns an index into the above table of the 176 nearest prime number which is greater than N, and near a power of two. */ 177 178static unsigned int 179higher_prime_index (n) 180 unsigned long n; 181{ 182 unsigned int low = 0; 183 unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]); 184 185 while (low != high) 186 { 187 unsigned int mid = low + (high - low) / 2; 188 if (n > prime_tab[mid].prime) 189 low = mid + 1; 190 else 191 high = mid; 192 } 193 194 /* If we've run out of primes, abort. */ 195 if (n > prime_tab[low].prime) 196 { 197 fprintf (stderr, "Cannot find prime bigger than %lu\n", n); 198 abort (); 199 } 200 201 return low; 202} 203 204/* Returns a hash code for P. */ 205 206static hashval_t 207hash_pointer (p) 208 const PTR p; 209{ 210 return (hashval_t) ((long)p >> 3); 211} 212 213/* Returns non-zero if P1 and P2 are equal. */ 214 215static int 216eq_pointer (p1, p2) 217 const PTR p1; 218 const PTR p2; 219{ 220 return p1 == p2; 221} 222 223/* Return the current size of given hash table. */ 224 225inline size_t 226htab_size (htab) 227 htab_t htab; 228{ 229 return htab->size; 230} 231 232/* Return the current number of elements in given hash table. */ 233 234inline size_t 235htab_elements (htab) 236 htab_t htab; 237{ 238 return htab->n_elements - htab->n_deleted; 239} 240 241/* Return X % Y. */ 242 243static inline hashval_t 244htab_mod_1 (x, y, inv, shift) 245 hashval_t x, y, inv; 246 int shift; 247{ 248 /* The multiplicative inverses computed above are for 32-bit types, and 249 requires that we be able to compute a highpart multiply. */ 250#ifdef UNSIGNED_64BIT_TYPE 251 __extension__ typedef UNSIGNED_64BIT_TYPE ull; 252 if (sizeof (hashval_t) * CHAR_BIT <= 32) 253 { 254 hashval_t t1, t2, t3, t4, q, r; 255 256 t1 = ((ull)x * inv) >> 32; 257 t2 = x - t1; 258 t3 = t2 >> 1; 259 t4 = t1 + t3; 260 q = t4 >> shift; 261 r = x - (q * y); 262 263 return r; 264 } 265#endif 266 267 /* Otherwise just use the native division routines. */ 268 return x % y; 269} 270 271/* Compute the primary hash for HASH given HTAB's current size. */ 272 273static inline hashval_t 274htab_mod (hash, htab) 275 hashval_t hash; 276 htab_t htab; 277{ 278 const struct prime_ent *p = &prime_tab[htab->size_prime_index]; 279 return htab_mod_1 (hash, p->prime, p->inv, p->shift); 280} 281 282/* Compute the secondary hash for HASH given HTAB's current size. */ 283 284static inline hashval_t 285htab_mod_m2 (hash, htab) 286 hashval_t hash; 287 htab_t htab; 288{ 289 const struct prime_ent *p = &prime_tab[htab->size_prime_index]; 290 return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift); 291} 292 293/* This function creates table with length slightly longer than given 294 source length. Created hash table is initiated as empty (all the 295 hash table entries are EMPTY_ENTRY). The function returns the 296 created hash table, or NULL if memory allocation fails. */ 297 298htab_t 299htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f) 300 size_t size; 301 htab_hash hash_f; 302 htab_eq eq_f; 303 htab_del del_f; 304 htab_alloc alloc_f; 305 htab_free free_f; 306{ 307 htab_t result; 308 unsigned int size_prime_index; 309 310 size_prime_index = higher_prime_index (size); 311 size = prime_tab[size_prime_index].prime; 312 313 result = (htab_t) (*alloc_f) (1, sizeof (struct htab)); 314 if (result == NULL) 315 return NULL; 316 result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR)); 317 if (result->entries == NULL) 318 { 319 if (free_f != NULL) 320 (*free_f) (result); 321 return NULL; 322 } 323 result->size = size; 324 result->size_prime_index = size_prime_index; 325 result->hash_f = hash_f; 326 result->eq_f = eq_f; 327 result->del_f = del_f; 328 result->alloc_f = alloc_f; 329 result->free_f = free_f; 330 return result; 331} 332 333/* As above, but use the variants of alloc_f and free_f which accept 334 an extra argument. */ 335 336htab_t 337htab_create_alloc_ex (size, hash_f, eq_f, del_f, alloc_arg, alloc_f, 338 free_f) 339 size_t size; 340 htab_hash hash_f; 341 htab_eq eq_f; 342 htab_del del_f; 343 PTR alloc_arg; 344 htab_alloc_with_arg alloc_f; 345 htab_free_with_arg free_f; 346{ 347 htab_t result; 348 unsigned int size_prime_index; 349 350 size_prime_index = higher_prime_index (size); 351 size = prime_tab[size_prime_index].prime; 352 353 result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab)); 354 if (result == NULL) 355 return NULL; 356 result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR)); 357 if (result->entries == NULL) 358 { 359 if (free_f != NULL) 360 (*free_f) (alloc_arg, result); 361 return NULL; 362 } 363 result->size = size; 364 result->size_prime_index = size_prime_index; 365 result->hash_f = hash_f; 366 result->eq_f = eq_f; 367 result->del_f = del_f; 368 result->alloc_arg = alloc_arg; 369 result->alloc_with_arg_f = alloc_f; 370 result->free_with_arg_f = free_f; 371 return result; 372} 373 374/* Update the function pointers and allocation parameter in the htab_t. */ 375 376void 377htab_set_functions_ex (htab, hash_f, eq_f, del_f, alloc_arg, alloc_f, free_f) 378 htab_t htab; 379 htab_hash hash_f; 380 htab_eq eq_f; 381 htab_del del_f; 382 PTR alloc_arg; 383 htab_alloc_with_arg alloc_f; 384 htab_free_with_arg free_f; 385{ 386 htab->hash_f = hash_f; 387 htab->eq_f = eq_f; 388 htab->del_f = del_f; 389 htab->alloc_arg = alloc_arg; 390 htab->alloc_with_arg_f = alloc_f; 391 htab->free_with_arg_f = free_f; 392} 393 394/* These functions exist solely for backward compatibility. */ 395 396#undef htab_create 397htab_t 398htab_create (size, hash_f, eq_f, del_f) 399 size_t size; 400 htab_hash hash_f; 401 htab_eq eq_f; 402 htab_del del_f; 403{ 404 return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free); 405} 406 407htab_t 408htab_try_create (size, hash_f, eq_f, del_f) 409 size_t size; 410 htab_hash hash_f; 411 htab_eq eq_f; 412 htab_del del_f; 413{ 414 return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free); 415} 416 417/* This function frees all memory allocated for given hash table. 418 Naturally the hash table must already exist. */ 419 420void 421htab_delete (htab) 422 htab_t htab; 423{ 424 size_t size = htab_size (htab); 425 PTR *entries = htab->entries; 426 int i; 427 428 if (htab->del_f) 429 for (i = size - 1; i >= 0; i--) 430 if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY) 431 (*htab->del_f) (entries[i]); 432 433 if (htab->free_f != NULL) 434 { 435 (*htab->free_f) (entries); 436 (*htab->free_f) (htab); 437 } 438 else if (htab->free_with_arg_f != NULL) 439 { 440 (*htab->free_with_arg_f) (htab->alloc_arg, entries); 441 (*htab->free_with_arg_f) (htab->alloc_arg, htab); 442 } 443} 444 445/* This function clears all entries in the given hash table. */ 446 447void 448htab_empty (htab) 449 htab_t htab; 450{ 451 size_t size = htab_size (htab); 452 PTR *entries = htab->entries; 453 int i; 454 455 if (htab->del_f) 456 for (i = size - 1; i >= 0; i--) 457 if (entries[i] != EMPTY_ENTRY && entries[i] != DELETED_ENTRY) 458 (*htab->del_f) (entries[i]); 459 460 memset (entries, 0, size * sizeof (PTR)); 461} 462 463/* Similar to htab_find_slot, but without several unwanted side effects: 464 - Does not call htab->eq_f when it finds an existing entry. 465 - Does not change the count of elements/searches/collisions in the 466 hash table. 467 This function also assumes there are no deleted entries in the table. 468 HASH is the hash value for the element to be inserted. */ 469 470static PTR * 471find_empty_slot_for_expand (htab, hash) 472 htab_t htab; 473 hashval_t hash; 474{ 475 hashval_t index = htab_mod (hash, htab); 476 size_t size = htab_size (htab); 477 PTR *slot = htab->entries + index; 478 hashval_t hash2; 479 480 if (*slot == EMPTY_ENTRY) 481 return slot; 482 else if (*slot == DELETED_ENTRY) 483 abort (); 484 485 hash2 = htab_mod_m2 (hash, htab); 486 for (;;) 487 { 488 index += hash2; 489 if (index >= size) 490 index -= size; 491 492 slot = htab->entries + index; 493 if (*slot == EMPTY_ENTRY) 494 return slot; 495 else if (*slot == DELETED_ENTRY) 496 abort (); 497 } 498} 499 500/* The following function changes size of memory allocated for the 501 entries and repeatedly inserts the table elements. The occupancy 502 of the table after the call will be about 50%. Naturally the hash 503 table must already exist. Remember also that the place of the 504 table entries is changed. If memory allocation failures are allowed, 505 this function will return zero, indicating that the table could not be 506 expanded. If all goes well, it will return a non-zero value. */ 507 508static int 509htab_expand (htab) 510 htab_t htab; 511{ 512 PTR *oentries; 513 PTR *olimit; 514 PTR *p; 515 PTR *nentries; 516 size_t nsize, osize, elts; 517 unsigned int oindex, nindex; 518 519 oentries = htab->entries; 520 oindex = htab->size_prime_index; 521 osize = htab->size; 522 olimit = oentries + osize; 523 elts = htab_elements (htab); 524 525 /* Resize only when table after removal of unused elements is either 526 too full or too empty. */ 527 if (elts * 2 > osize || (elts * 8 < osize && osize > 32)) 528 { 529 nindex = higher_prime_index (elts * 2); 530 nsize = prime_tab[nindex].prime; 531 } 532 else 533 { 534 nindex = oindex; 535 nsize = osize; 536 } 537 538 if (htab->alloc_with_arg_f != NULL) 539 nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize, 540 sizeof (PTR *)); 541 else 542 nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *)); 543 if (nentries == NULL) 544 return 0; 545 htab->entries = nentries; 546 htab->size = nsize; 547 htab->size_prime_index = nindex; 548 htab->n_elements -= htab->n_deleted; 549 htab->n_deleted = 0; 550 551 p = oentries; 552 do 553 { 554 PTR x = *p; 555 556 if (x != EMPTY_ENTRY && x != DELETED_ENTRY) 557 { 558 PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x)); 559 560 *q = x; 561 } 562 563 p++; 564 } 565 while (p < olimit); 566 567 if (htab->free_f != NULL) 568 (*htab->free_f) (oentries); 569 else if (htab->free_with_arg_f != NULL) 570 (*htab->free_with_arg_f) (htab->alloc_arg, oentries); 571 return 1; 572} 573 574/* This function searches for a hash table entry equal to the given 575 element. It cannot be used to insert or delete an element. */ 576 577PTR 578htab_find_with_hash (htab, element, hash) 579 htab_t htab; 580 const PTR element; 581 hashval_t hash; 582{ 583 hashval_t index, hash2; 584 size_t size; 585 PTR entry; 586 587 htab->searches++; 588 size = htab_size (htab); 589 index = htab_mod (hash, htab); 590 591 entry = htab->entries[index]; 592 if (entry == EMPTY_ENTRY 593 || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))) 594 return entry; 595 596 hash2 = htab_mod_m2 (hash, htab); 597 for (;;) 598 { 599 htab->collisions++; 600 index += hash2; 601 if (index >= size) 602 index -= size; 603 604 entry = htab->entries[index]; 605 if (entry == EMPTY_ENTRY 606 || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element))) 607 return entry; 608 } 609} 610 611/* Like htab_find_slot_with_hash, but compute the hash value from the 612 element. */ 613 614PTR 615htab_find (htab, element) 616 htab_t htab; 617 const PTR element; 618{ 619 return htab_find_with_hash (htab, element, (*htab->hash_f) (element)); 620} 621 622/* This function searches for a hash table slot containing an entry 623 equal to the given element. To delete an entry, call this with 624 INSERT = 0, then call htab_clear_slot on the slot returned (possibly 625 after doing some checks). To insert an entry, call this with 626 INSERT = 1, then write the value you want into the returned slot. 627 When inserting an entry, NULL may be returned if memory allocation 628 fails. */ 629 630PTR * 631htab_find_slot_with_hash (htab, element, hash, insert) 632 htab_t htab; 633 const PTR element; 634 hashval_t hash; 635 enum insert_option insert; 636{ 637 PTR *first_deleted_slot; 638 hashval_t index, hash2; 639 size_t size; 640 PTR entry; 641 642 size = htab_size (htab); 643 if (insert == INSERT && size * 3 <= htab->n_elements * 4) 644 { 645 if (htab_expand (htab) == 0) 646 return NULL; 647 size = htab_size (htab); 648 } 649 650 index = htab_mod (hash, htab); 651 652 htab->searches++; 653 first_deleted_slot = NULL; 654 655 entry = htab->entries[index]; 656 if (entry == EMPTY_ENTRY) 657 goto empty_entry; 658 else if (entry == DELETED_ENTRY) 659 first_deleted_slot = &htab->entries[index]; 660 else if ((*htab->eq_f) (entry, element)) 661 return &htab->entries[index]; 662 663 hash2 = htab_mod_m2 (hash, htab); 664 for (;;) 665 { 666 htab->collisions++; 667 index += hash2; 668 if (index >= size) 669 index -= size; 670 671 entry = htab->entries[index]; 672 if (entry == EMPTY_ENTRY) 673 goto empty_entry; 674 else if (entry == DELETED_ENTRY) 675 { 676 if (!first_deleted_slot) 677 first_deleted_slot = &htab->entries[index]; 678 } 679 else if ((*htab->eq_f) (entry, element)) 680 return &htab->entries[index]; 681 } 682 683 empty_entry: 684 if (insert == NO_INSERT) 685 return NULL; 686 687 if (first_deleted_slot) 688 { 689 htab->n_deleted--; 690 *first_deleted_slot = EMPTY_ENTRY; 691 return first_deleted_slot; 692 } 693 694 htab->n_elements++; 695 return &htab->entries[index]; 696} 697 698/* Like htab_find_slot_with_hash, but compute the hash value from the 699 element. */ 700 701PTR * 702htab_find_slot (htab, element, insert) 703 htab_t htab; 704 const PTR element; 705 enum insert_option insert; 706{ 707 return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element), 708 insert); 709} 710 711/* This function deletes an element with the given value from hash 712 table (the hash is computed from the element). If there is no matching 713 element in the hash table, this function does nothing. */ 714 715void 716htab_remove_elt (htab, element) 717 htab_t htab; 718 PTR element; 719{ 720 htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element)); 721} 722 723 724/* This function deletes an element with the given value from hash 725 table. If there is no matching element in the hash table, this 726 function does nothing. */ 727 728void 729htab_remove_elt_with_hash (htab, element, hash) 730 htab_t htab; 731 PTR element; 732 hashval_t hash; 733{ 734 PTR *slot; 735 736 slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT); 737 if (*slot == EMPTY_ENTRY) 738 return; 739 740 if (htab->del_f) 741 (*htab->del_f) (*slot); 742 743 *slot = DELETED_ENTRY; 744 htab->n_deleted++; 745} 746 747/* This function clears a specified slot in a hash table. It is 748 useful when you've already done the lookup and don't want to do it 749 again. */ 750 751void 752htab_clear_slot (htab, slot) 753 htab_t htab; 754 PTR *slot; 755{ 756 if (slot < htab->entries || slot >= htab->entries + htab_size (htab) 757 || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY) 758 abort (); 759 760 if (htab->del_f) 761 (*htab->del_f) (*slot); 762 763 *slot = DELETED_ENTRY; 764 htab->n_deleted++; 765} 766 767/* This function scans over the entire hash table calling 768 CALLBACK for each live entry. If CALLBACK returns false, 769 the iteration stops. INFO is passed as CALLBACK's second 770 argument. */ 771 772void 773htab_traverse_noresize (htab, callback, info) 774 htab_t htab; 775 htab_trav callback; 776 PTR info; 777{ 778 PTR *slot; 779 PTR *limit; 780 781 slot = htab->entries; 782 limit = slot + htab_size (htab); 783 784 do 785 { 786 PTR x = *slot; 787 788 if (x != EMPTY_ENTRY && x != DELETED_ENTRY) 789 if (!(*callback) (slot, info)) 790 break; 791 } 792 while (++slot < limit); 793} 794 795/* Like htab_traverse_noresize, but does resize the table when it is 796 too empty to improve effectivity of subsequent calls. */ 797 798void 799htab_traverse (htab, callback, info) 800 htab_t htab; 801 htab_trav callback; 802 PTR info; 803{ 804 if (htab_elements (htab) * 8 < htab_size (htab)) 805 htab_expand (htab); 806 807 htab_traverse_noresize (htab, callback, info); 808} 809 810/* Return the fraction of fixed collisions during all work with given 811 hash table. */ 812 813double 814htab_collisions (htab) 815 htab_t htab; 816{ 817 if (htab->searches == 0) 818 return 0.0; 819 820 return (double) htab->collisions / (double) htab->searches; 821} 822 823/* Hash P as a null-terminated string. 824 825 Copied from gcc/hashtable.c. Zack had the following to say with respect 826 to applicability, though note that unlike hashtable.c, this hash table 827 implementation re-hashes rather than chain buckets. 828 829 http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html 830 From: Zack Weinberg <zackw@panix.com> 831 Date: Fri, 17 Aug 2001 02:15:56 -0400 832 833 I got it by extracting all the identifiers from all the source code 834 I had lying around in mid-1999, and testing many recurrences of 835 the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either 836 prime numbers or the appropriate identity. This was the best one. 837 I don't remember exactly what constituted "best", except I was 838 looking at bucket-length distributions mostly. 839 840 So it should be very good at hashing identifiers, but might not be 841 as good at arbitrary strings. 842 843 I'll add that it thoroughly trounces the hash functions recommended 844 for this use at http://burtleburtle.net/bob/hash/index.html, both 845 on speed and bucket distribution. I haven't tried it against the 846 function they just started using for Perl's hashes. */ 847 848hashval_t 849htab_hash_string (p) 850 const PTR p; 851{ 852 const unsigned char *str = (const unsigned char *) p; 853 hashval_t r = 0; 854 unsigned char c; 855 856 while ((c = *str++) != 0) 857 r = r * 67 + c - 113; 858 859 return r; 860} 861 862/* DERIVED FROM: 863-------------------------------------------------------------------- 864lookup2.c, by Bob Jenkins, December 1996, Public Domain. 865hash(), hash2(), hash3, and mix() are externally useful functions. 866Routines to test the hash are included if SELF_TEST is defined. 867You can use this free for any purpose. It has no warranty. 868-------------------------------------------------------------------- 869*/ 870 871/* 872-------------------------------------------------------------------- 873mix -- mix 3 32-bit values reversibly. 874For every delta with one or two bit set, and the deltas of all three 875 high bits or all three low bits, whether the original value of a,b,c 876 is almost all zero or is uniformly distributed, 877* If mix() is run forward or backward, at least 32 bits in a,b,c 878 have at least 1/4 probability of changing. 879* If mix() is run forward, every bit of c will change between 1/3 and 880 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.) 881mix() was built out of 36 single-cycle latency instructions in a 882 structure that could supported 2x parallelism, like so: 883 a -= b; 884 a -= c; x = (c>>13); 885 b -= c; a ^= x; 886 b -= a; x = (a<<8); 887 c -= a; b ^= x; 888 c -= b; x = (b>>13); 889 ... 890 Unfortunately, superscalar Pentiums and Sparcs can't take advantage 891 of that parallelism. They've also turned some of those single-cycle 892 latency instructions into multi-cycle latency instructions. Still, 893 this is the fastest good hash I could find. There were about 2^^68 894 to choose from. I only looked at a billion or so. 895-------------------------------------------------------------------- 896*/ 897/* same, but slower, works on systems that might have 8 byte hashval_t's */ 898#define mix(a,b,c) \ 899{ \ 900 a -= b; a -= c; a ^= (c>>13); \ 901 b -= c; b -= a; b ^= (a<< 8); \ 902 c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \ 903 a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \ 904 b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \ 905 c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \ 906 a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \ 907 b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \ 908 c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \ 909} 910 911/* 912-------------------------------------------------------------------- 913hash() -- hash a variable-length key into a 32-bit value 914 k : the key (the unaligned variable-length array of bytes) 915 len : the length of the key, counting by bytes 916 level : can be any 4-byte value 917Returns a 32-bit value. Every bit of the key affects every bit of 918the return value. Every 1-bit and 2-bit delta achieves avalanche. 919About 36+6len instructions. 920 921The best hash table sizes are powers of 2. There is no need to do 922mod a prime (mod is sooo slow!). If you need less than 32 bits, 923use a bitmask. For example, if you need only 10 bits, do 924 h = (h & hashmask(10)); 925In which case, the hash table should have hashsize(10) elements. 926 927If you are hashing n strings (ub1 **)k, do it like this: 928 for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h); 929 930By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this 931code any way you wish, private, educational, or commercial. It's free. 932 933See http://burtleburtle.net/bob/hash/evahash.html 934Use for hash table lookup, or anything where one collision in 2^32 is 935acceptable. Do NOT use for cryptographic purposes. 936-------------------------------------------------------------------- 937*/ 938 939hashval_t iterative_hash (k_in, length, initval) 940 const PTR k_in; /* the key */ 941 register size_t length; /* the length of the key */ 942 register hashval_t initval; /* the previous hash, or an arbitrary value */ 943{ 944 register const unsigned char *k = (const unsigned char *)k_in; 945 register hashval_t a,b,c,len; 946 947 /* Set up the internal state */ 948 len = length; 949 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ 950 c = initval; /* the previous hash value */ 951 952 /*---------------------------------------- handle most of the key */ 953#ifndef WORDS_BIGENDIAN 954 /* On a little-endian machine, if the data is 4-byte aligned we can hash 955 by word for better speed. This gives nondeterministic results on 956 big-endian machines. */ 957 if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0) 958 while (len >= 12) /* aligned */ 959 { 960 a += *(hashval_t *)(k+0); 961 b += *(hashval_t *)(k+4); 962 c += *(hashval_t *)(k+8); 963 mix(a,b,c); 964 k += 12; len -= 12; 965 } 966 else /* unaligned */ 967#endif 968 while (len >= 12) 969 { 970 a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24)); 971 b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24)); 972 c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24)); 973 mix(a,b,c); 974 k += 12; len -= 12; 975 } 976 977 /*------------------------------------- handle the last 11 bytes */ 978 c += length; 979 switch(len) /* all the case statements fall through */ 980 { 981 case 11: c+=((hashval_t)k[10]<<24); 982 case 10: c+=((hashval_t)k[9]<<16); 983 case 9 : c+=((hashval_t)k[8]<<8); 984 /* the first byte of c is reserved for the length */ 985 case 8 : b+=((hashval_t)k[7]<<24); 986 case 7 : b+=((hashval_t)k[6]<<16); 987 case 6 : b+=((hashval_t)k[5]<<8); 988 case 5 : b+=k[4]; 989 case 4 : a+=((hashval_t)k[3]<<24); 990 case 3 : a+=((hashval_t)k[2]<<16); 991 case 2 : a+=((hashval_t)k[1]<<8); 992 case 1 : a+=k[0]; 993 /* case 0: nothing left to add */ 994 } 995 mix(a,b,c); 996 /*-------------------------------------------- report the result */ 997 return c; 998} 999