gcclibs/libiberty/hashtab.c

1 /* An expandable hash tables datatype.
22 /* This package implements basic hash table functionality.  It is possible
28    grows too high the hash table will be expanded.
32    expanded by creation of new hash table and transferring elements from
77    hash-table routines to handle NULL specially; that would avoid
194 /* Returns a hash code for P.  */
216 /* Return the current size of given hash table.  */
226 /* Return the current number of elements in given hash table. */
264 /* Compute the primary hash for HASH given HTAB's current size.  */
267 htab_mod (hashval_t hash, htab_t htab)
270   return htab_mod_1 (hash, p->prime, p->inv, p->shift);
273 /* Compute the secondary hash for HASH given HTAB's current size.  */
276 htab_mod_m2 (hashval_t hash, htab_t htab)
279   return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
283    source length.  Created hash table is initiated as empty (all the
284    hash table entries are HTAB_EMPTY_ENTRY).  The function returns the
285    created hash table, or NULL if memory allocation fails.  */
383 /* This function frees all memory allocated for given hash table.
384    Naturally the hash table must already exist. */
410 /* This function clears all entries in the given hash table.  */
451       hash table.
453    HASH is the hash value for the element to be inserted.  */
456 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
458   hashval_t index = htab_mod (hash, htab);
468   hash2 = htab_mod_m2 (hash, htab);
485    of the table after the call will be about 50%.  Naturally the hash
556 /* This function searches for a hash table entry equal to the given
560 htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
568   index = htab_mod (hash, htab);
575   hash2 = htab_mod_m2 (hash, htab);
590 /* Like htab_find_slot_with_hash, but compute the hash value from the
599 /* This function searches for a hash table slot containing an entry
609                           hashval_t hash, enum insert_option insert)
624   index = htab_mod (hash, htab);
637   hash2 = htab_mod_m2 (hash, htab);
672 /* Like htab_find_slot_with_hash, but compute the hash value from the
682 /* This function deletes an element with the given value from hash
683    table (the hash is computed from the element).  If there is no matching
684    element in the hash table, this function does nothing.  */
693 /* This function deletes an element with the given value from hash
694    table.  If there is no matching element in the hash table, this
698 htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
702   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
713 /* This function clears a specified slot in a hash table.  It is
731 /* This function scans over the entire hash table calling
769    hash table. */
783    to applicability, though note that unlike hashtable.c, this hash table
800    I'll add that it thoroughly trounces the hash functions recommended
801    for this use at http://burtleburtle.net/bob/hash/index.html, both
821 hash(), hash2(), hash3, and mix() are externally useful functions.
822 Routines to test the hash are included if SELF_TEST is defined.
849   this is the fastest good hash I could find.  There were about 2^^68
869 hash() -- hash a variable-length key into a 32-bit value
877 The best hash table sizes are powers of 2.  There is no need to do
881 In which case, the hash table should have hashsize(10) elements.
884   for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
889 See http://burtleburtle.net/bob/hash/evahash.html
890 Use for hash table lookup, or anything where one collision in 2^32 is
898                 register hashval_t initval /* the previous hash, or
907   c = initval;           /* the previous hash value */
911   /* On a little-endian machine, if the data is 4-byte aligned we can hash