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