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