Back to index

cell-binutils  2.17cvs20070401
hashtab.c
Go to the documentation of this file.
00001 /* An expandable hash tables datatype.  
00002    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004
00003    Free Software Foundation, Inc.
00004    Contributed by Vladimir Makarov (vmakarov@cygnus.com).
00005 
00006 This file is part of the libiberty library.
00007 Libiberty is free software; you can redistribute it and/or
00008 modify it under the terms of the GNU Library General Public
00009 License as published by the Free Software Foundation; either
00010 version 2 of the License, or (at your option) any later version.
00011 
00012 Libiberty is distributed in the hope that it will be useful,
00013 but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 Library General Public License for more details.
00016 
00017 You should have received a copy of the GNU Library General Public
00018 License along with libiberty; see the file COPYING.LIB.  If
00019 not, write to the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
00020 Boston, MA 02110-1301, USA.  */
00021 
00022 /* This package implements basic hash table functionality.  It is possible
00023    to search for an entry, create an entry and destroy an entry.
00024 
00025    Elements in the table are generic pointers.
00026 
00027    The size of the table is not fixed; if the occupancy of the table
00028    grows too high the hash table will be expanded.
00029 
00030    The abstract data implementation is based on generalized Algorithm D
00031    from Knuth's book "The art of computer programming".  Hash table is
00032    expanded by creation of new hash table and transferring elements from
00033    the old table to the new table. */
00034 
00035 #ifdef HAVE_CONFIG_H
00036 #include "config.h"
00037 #endif
00038 
00039 #include <sys/types.h>
00040 
00041 #ifdef HAVE_STDLIB_H
00042 #include <stdlib.h>
00043 #endif
00044 #ifdef HAVE_STRING_H
00045 #include <string.h>
00046 #endif
00047 #ifdef HAVE_MALLOC_H
00048 #include <malloc.h>
00049 #endif
00050 #ifdef HAVE_LIMITS_H
00051 #include <limits.h>
00052 #endif
00053 #ifdef HAVE_STDINT_H
00054 #include <stdint.h>
00055 #endif
00056 
00057 #include <stdio.h>
00058 
00059 #include "libiberty.h"
00060 #include "ansidecl.h"
00061 #include "hashtab.h"
00062 
00063 #ifndef CHAR_BIT
00064 #define CHAR_BIT 8
00065 #endif
00066 
00067 static unsigned int higher_prime_index (unsigned long);
00068 static hashval_t htab_mod_1 (hashval_t, hashval_t, hashval_t, int);
00069 static hashval_t htab_mod (hashval_t, htab_t);
00070 static hashval_t htab_mod_m2 (hashval_t, htab_t);
00071 static hashval_t hash_pointer (const void *);
00072 static int eq_pointer (const void *, const void *);
00073 static int htab_expand (htab_t);
00074 static PTR *find_empty_slot_for_expand (htab_t, hashval_t);
00075 
00076 /* At some point, we could make these be NULL, and modify the
00077    hash-table routines to handle NULL specially; that would avoid
00078    function-call overhead for the common case of hashing pointers.  */
00079 htab_hash htab_hash_pointer = hash_pointer;
00080 htab_eq htab_eq_pointer = eq_pointer;
00081 
00082 /* Table of primes and multiplicative inverses.
00083 
00084    Note that these are not minimally reduced inverses.  Unlike when generating
00085    code to divide by a constant, we want to be able to use the same algorithm
00086    all the time.  All of these inverses (are implied to) have bit 32 set.
00087 
00088    For the record, here's the function that computed the table; it's a 
00089    vastly simplified version of the function of the same name from gcc.  */
00090 
00091 #if 0
00092 unsigned int
00093 ceil_log2 (unsigned int x)
00094 {
00095   int i;
00096   for (i = 31; i >= 0 ; --i)
00097     if (x > (1u << i))
00098       return i+1;
00099   abort ();
00100 }
00101 
00102 unsigned int
00103 choose_multiplier (unsigned int d, unsigned int *mlp, unsigned char *shiftp)
00104 {
00105   unsigned long long mhigh;
00106   double nx;
00107   int lgup, post_shift;
00108   int pow, pow2;
00109   int n = 32, precision = 32;
00110 
00111   lgup = ceil_log2 (d);
00112   pow = n + lgup;
00113   pow2 = n + lgup - precision;
00114 
00115   nx = ldexp (1.0, pow) + ldexp (1.0, pow2);
00116   mhigh = nx / d;
00117 
00118   *shiftp = lgup - 1;
00119   *mlp = mhigh;
00120   return mhigh >> 32;
00121 }
00122 #endif
00123 
00124 struct prime_ent
00125 {
00126   hashval_t prime;
00127   hashval_t inv;
00128   hashval_t inv_m2;  /* inverse of prime-2 */
00129   hashval_t shift;
00130 };
00131 
00132 static struct prime_ent const prime_tab[] = {
00133   {          7, 0x24924925, 0x9999999b, 2 },
00134   {         13, 0x3b13b13c, 0x745d1747, 3 },
00135   {         31, 0x08421085, 0x1a7b9612, 4 },
00136   {         61, 0x0c9714fc, 0x15b1e5f8, 5 },
00137   {        127, 0x02040811, 0x0624dd30, 6 },
00138   {        251, 0x05197f7e, 0x073260a5, 7 },
00139   {        509, 0x01824366, 0x02864fc8, 8 },
00140   {       1021, 0x00c0906d, 0x014191f7, 9 },
00141   {       2039, 0x0121456f, 0x0161e69e, 10 },
00142   {       4093, 0x00300902, 0x00501908, 11 },
00143   {       8191, 0x00080041, 0x00180241, 12 },
00144   {      16381, 0x000c0091, 0x00140191, 13 },
00145   {      32749, 0x002605a5, 0x002a06e6, 14 },
00146   {      65521, 0x000f00e2, 0x00110122, 15 },
00147   {     131071, 0x00008001, 0x00018003, 16 },
00148   {     262139, 0x00014002, 0x0001c004, 17 },
00149   {     524287, 0x00002001, 0x00006001, 18 },
00150   {    1048573, 0x00003001, 0x00005001, 19 },
00151   {    2097143, 0x00004801, 0x00005801, 20 },
00152   {    4194301, 0x00000c01, 0x00001401, 21 },
00153   {    8388593, 0x00001e01, 0x00002201, 22 },
00154   {   16777213, 0x00000301, 0x00000501, 23 },
00155   {   33554393, 0x00001381, 0x00001481, 24 },
00156   {   67108859, 0x00000141, 0x000001c1, 25 },
00157   {  134217689, 0x000004e1, 0x00000521, 26 },
00158   {  268435399, 0x00000391, 0x000003b1, 27 },
00159   {  536870909, 0x00000019, 0x00000029, 28 },
00160   { 1073741789, 0x0000008d, 0x00000095, 29 },
00161   { 2147483647, 0x00000003, 0x00000007, 30 },
00162   /* Avoid "decimal constant so large it is unsigned" for 4294967291.  */
00163   { 0xfffffffb, 0x00000006, 0x00000008, 31 }
00164 };
00165 
00166 /* The following function returns an index into the above table of the
00167    nearest prime number which is greater than N, and near a power of two. */
00168 
00169 static unsigned int
00170 higher_prime_index (unsigned long n)
00171 {
00172   unsigned int low = 0;
00173   unsigned int high = sizeof(prime_tab) / sizeof(prime_tab[0]);
00174 
00175   while (low != high)
00176     {
00177       unsigned int mid = low + (high - low) / 2;
00178       if (n > prime_tab[mid].prime)
00179        low = mid + 1;
00180       else
00181        high = mid;
00182     }
00183 
00184   /* If we've run out of primes, abort.  */
00185   if (n > prime_tab[low].prime)
00186     {
00187       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
00188       abort ();
00189     }
00190 
00191   return low;
00192 }
00193 
00194 /* Returns a hash code for P.  */
00195 
00196 static hashval_t
00197 hash_pointer (const PTR p)
00198 {
00199   return (hashval_t) ((long)p >> 3);
00200 }
00201 
00202 /* Returns non-zero if P1 and P2 are equal.  */
00203 
00204 static int
00205 eq_pointer (const PTR p1, const PTR p2)
00206 {
00207   return p1 == p2;
00208 }
00209 
00210 
00211 /* The parens around the function names in the next two definitions
00212    are essential in order to prevent macro expansions of the name.
00213    The bodies, however, are expanded as expected, so they are not
00214    recursive definitions.  */
00215 
00216 /* Return the current size of given hash table.  */
00217 
00218 #define htab_size(htab)  ((htab)->size)
00219 
00220 size_t
00221 (htab_size) (htab_t htab)
00222 {
00223   return htab_size (htab);
00224 }
00225 
00226 /* Return the current number of elements in given hash table. */
00227 
00228 #define htab_elements(htab)  ((htab)->n_elements - (htab)->n_deleted)
00229 
00230 size_t
00231 (htab_elements) (htab_t htab)
00232 {
00233   return htab_elements (htab);
00234 }
00235 
00236 /* Return X % Y.  */
00237 
00238 static inline hashval_t
00239 htab_mod_1 (hashval_t x, hashval_t y, hashval_t inv, int shift)
00240 {
00241   /* The multiplicative inverses computed above are for 32-bit types, and
00242      requires that we be able to compute a highpart multiply.  */
00243 #ifdef UNSIGNED_64BIT_TYPE
00244   __extension__ typedef UNSIGNED_64BIT_TYPE ull;
00245   if (sizeof (hashval_t) * CHAR_BIT <= 32)
00246     {
00247       hashval_t t1, t2, t3, t4, q, r;
00248 
00249       t1 = ((ull)x * inv) >> 32;
00250       t2 = x - t1;
00251       t3 = t2 >> 1;
00252       t4 = t1 + t3;
00253       q  = t4 >> shift;
00254       r  = x - (q * y);
00255 
00256       return r;
00257     }
00258 #endif
00259 
00260   /* Otherwise just use the native division routines.  */
00261   return x % y;
00262 }
00263 
00264 /* Compute the primary hash for HASH given HTAB's current size.  */
00265 
00266 static inline hashval_t
00267 htab_mod (hashval_t hash, htab_t htab)
00268 {
00269   const struct prime_ent *p = &prime_tab[htab->size_prime_index];
00270   return htab_mod_1 (hash, p->prime, p->inv, p->shift);
00271 }
00272 
00273 /* Compute the secondary hash for HASH given HTAB's current size.  */
00274 
00275 static inline hashval_t
00276 htab_mod_m2 (hashval_t hash, htab_t htab)
00277 {
00278   const struct prime_ent *p = &prime_tab[htab->size_prime_index];
00279   return 1 + htab_mod_1 (hash, p->prime - 2, p->inv_m2, p->shift);
00280 }
00281 
00282 /* This function creates table with length slightly longer than given
00283    source length.  Created hash table is initiated as empty (all the
00284    hash table entries are HTAB_EMPTY_ENTRY).  The function returns the
00285    created hash table, or NULL if memory allocation fails.  */
00286 
00287 htab_t
00288 htab_create_alloc (size_t size, htab_hash hash_f, htab_eq eq_f,
00289                    htab_del del_f, htab_alloc alloc_f, htab_free free_f)
00290 {
00291   htab_t result;
00292   unsigned int size_prime_index;
00293 
00294   size_prime_index = higher_prime_index (size);
00295   size = prime_tab[size_prime_index].prime;
00296 
00297   result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
00298   if (result == NULL)
00299     return NULL;
00300   result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
00301   if (result->entries == NULL)
00302     {
00303       if (free_f != NULL)
00304        (*free_f) (result);
00305       return NULL;
00306     }
00307   result->size = size;
00308   result->size_prime_index = size_prime_index;
00309   result->hash_f = hash_f;
00310   result->eq_f = eq_f;
00311   result->del_f = del_f;
00312   result->alloc_f = alloc_f;
00313   result->free_f = free_f;
00314   return result;
00315 }
00316 
00317 /* As above, but use the variants of alloc_f and free_f which accept
00318    an extra argument.  */
00319 
00320 htab_t
00321 htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f,
00322                       htab_del del_f, void *alloc_arg,
00323                       htab_alloc_with_arg alloc_f,
00324                     htab_free_with_arg free_f)
00325 {
00326   htab_t result;
00327   unsigned int size_prime_index;
00328 
00329   size_prime_index = higher_prime_index (size);
00330   size = prime_tab[size_prime_index].prime;
00331 
00332   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
00333   if (result == NULL)
00334     return NULL;
00335   result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
00336   if (result->entries == NULL)
00337     {
00338       if (free_f != NULL)
00339        (*free_f) (alloc_arg, result);
00340       return NULL;
00341     }
00342   result->size = size;
00343   result->size_prime_index = size_prime_index;
00344   result->hash_f = hash_f;
00345   result->eq_f = eq_f;
00346   result->del_f = del_f;
00347   result->alloc_arg = alloc_arg;
00348   result->alloc_with_arg_f = alloc_f;
00349   result->free_with_arg_f = free_f;
00350   return result;
00351 }
00352 
00353 /* Update the function pointers and allocation parameter in the htab_t.  */
00354 
00355 void
00356 htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f,
00357                        htab_del del_f, PTR alloc_arg,
00358                        htab_alloc_with_arg alloc_f, htab_free_with_arg free_f)
00359 {
00360   htab->hash_f = hash_f;
00361   htab->eq_f = eq_f;
00362   htab->del_f = del_f;
00363   htab->alloc_arg = alloc_arg;
00364   htab->alloc_with_arg_f = alloc_f;
00365   htab->free_with_arg_f = free_f;
00366 }
00367 
00368 /* These functions exist solely for backward compatibility.  */
00369 
00370 #undef htab_create
00371 htab_t
00372 htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
00373 {
00374   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
00375 }
00376 
00377 htab_t
00378 htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
00379 {
00380   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
00381 }
00382 
00383 /* This function frees all memory allocated for given hash table.
00384    Naturally the hash table must already exist. */
00385 
00386 void
00387 htab_delete (htab_t htab)
00388 {
00389   size_t size = htab_size (htab);
00390   PTR *entries = htab->entries;
00391   int i;
00392 
00393   if (htab->del_f)
00394     for (i = size - 1; i >= 0; i--)
00395       if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
00396        (*htab->del_f) (entries[i]);
00397 
00398   if (htab->free_f != NULL)
00399     {
00400       (*htab->free_f) (entries);
00401       (*htab->free_f) (htab);
00402     }
00403   else if (htab->free_with_arg_f != NULL)
00404     {
00405       (*htab->free_with_arg_f) (htab->alloc_arg, entries);
00406       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
00407     }
00408 }
00409 
00410 /* This function clears all entries in the given hash table.  */
00411 
00412 void
00413 htab_empty (htab_t htab)
00414 {
00415   size_t size = htab_size (htab);
00416   PTR *entries = htab->entries;
00417   int i;
00418 
00419   if (htab->del_f)
00420     for (i = size - 1; i >= 0; i--)
00421       if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
00422        (*htab->del_f) (entries[i]);
00423 
00424   /* Instead of clearing megabyte, downsize the table.  */
00425   if (size > 1024*1024 / sizeof (PTR))
00426     {
00427       int nindex = higher_prime_index (1024 / sizeof (PTR));
00428       int nsize = prime_tab[nindex].prime;
00429 
00430       if (htab->free_f != NULL)
00431        (*htab->free_f) (htab->entries);
00432       else if (htab->free_with_arg_f != NULL)
00433        (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
00434       if (htab->alloc_with_arg_f != NULL)
00435        htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
00436                                                      sizeof (PTR *));
00437       else
00438        htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
00439      htab->size = nsize;
00440      htab->size_prime_index = nindex;
00441     }
00442   else
00443     memset (entries, 0, size * sizeof (PTR));
00444   htab->n_deleted = 0;
00445   htab->n_elements = 0;
00446 }
00447 
00448 /* Similar to htab_find_slot, but without several unwanted side effects:
00449     - Does not call htab->eq_f when it finds an existing entry.
00450     - Does not change the count of elements/searches/collisions in the
00451       hash table.
00452    This function also assumes there are no deleted entries in the table.
00453    HASH is the hash value for the element to be inserted.  */
00454 
00455 static PTR *
00456 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
00457 {
00458   hashval_t index = htab_mod (hash, htab);
00459   size_t size = htab_size (htab);
00460   PTR *slot = htab->entries + index;
00461   hashval_t hash2;
00462 
00463   if (*slot == HTAB_EMPTY_ENTRY)
00464     return slot;
00465   else if (*slot == HTAB_DELETED_ENTRY)
00466     abort ();
00467 
00468   hash2 = htab_mod_m2 (hash, htab);
00469   for (;;)
00470     {
00471       index += hash2;
00472       if (index >= size)
00473        index -= size;
00474 
00475       slot = htab->entries + index;
00476       if (*slot == HTAB_EMPTY_ENTRY)
00477        return slot;
00478       else if (*slot == HTAB_DELETED_ENTRY)
00479        abort ();
00480     }
00481 }
00482 
00483 /* The following function changes size of memory allocated for the
00484    entries and repeatedly inserts the table elements.  The occupancy
00485    of the table after the call will be about 50%.  Naturally the hash
00486    table must already exist.  Remember also that the place of the
00487    table entries is changed.  If memory allocation failures are allowed,
00488    this function will return zero, indicating that the table could not be
00489    expanded.  If all goes well, it will return a non-zero value.  */
00490 
00491 static int
00492 htab_expand (htab_t htab)
00493 {
00494   PTR *oentries;
00495   PTR *olimit;
00496   PTR *p;
00497   PTR *nentries;
00498   size_t nsize, osize, elts;
00499   unsigned int oindex, nindex;
00500 
00501   oentries = htab->entries;
00502   oindex = htab->size_prime_index;
00503   osize = htab->size;
00504   olimit = oentries + osize;
00505   elts = htab_elements (htab);
00506 
00507   /* Resize only when table after removal of unused elements is either
00508      too full or too empty.  */
00509   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
00510     {
00511       nindex = higher_prime_index (elts * 2);
00512       nsize = prime_tab[nindex].prime;
00513     }
00514   else
00515     {
00516       nindex = oindex;
00517       nsize = osize;
00518     }
00519 
00520   if (htab->alloc_with_arg_f != NULL)
00521     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
00522                                             sizeof (PTR *));
00523   else
00524     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
00525   if (nentries == NULL)
00526     return 0;
00527   htab->entries = nentries;
00528   htab->size = nsize;
00529   htab->size_prime_index = nindex;
00530   htab->n_elements -= htab->n_deleted;
00531   htab->n_deleted = 0;
00532 
00533   p = oentries;
00534   do
00535     {
00536       PTR x = *p;
00537 
00538       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
00539        {
00540          PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
00541 
00542          *q = x;
00543        }
00544 
00545       p++;
00546     }
00547   while (p < olimit);
00548 
00549   if (htab->free_f != NULL)
00550     (*htab->free_f) (oentries);
00551   else if (htab->free_with_arg_f != NULL)
00552     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
00553   return 1;
00554 }
00555 
00556 /* This function searches for a hash table entry equal to the given
00557    element.  It cannot be used to insert or delete an element.  */
00558 
00559 PTR
00560 htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
00561 {
00562   hashval_t index, hash2;
00563   size_t size;
00564   PTR entry;
00565 
00566   htab->searches++;
00567   size = htab_size (htab);
00568   index = htab_mod (hash, htab);
00569 
00570   entry = htab->entries[index];
00571   if (entry == HTAB_EMPTY_ENTRY
00572       || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
00573     return entry;
00574 
00575   hash2 = htab_mod_m2 (hash, htab);
00576   for (;;)
00577     {
00578       htab->collisions++;
00579       index += hash2;
00580       if (index >= size)
00581        index -= size;
00582 
00583       entry = htab->entries[index];
00584       if (entry == HTAB_EMPTY_ENTRY
00585          || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
00586        return entry;
00587     }
00588 }
00589 
00590 /* Like htab_find_slot_with_hash, but compute the hash value from the
00591    element.  */
00592 
00593 PTR
00594 htab_find (htab_t htab, const PTR element)
00595 {
00596   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
00597 }
00598 
00599 /* This function searches for a hash table slot containing an entry
00600    equal to the given element.  To delete an entry, call this with
00601    insert=NO_INSERT, then call htab_clear_slot on the slot returned
00602    (possibly after doing some checks).  To insert an entry, call this
00603    with insert=INSERT, then write the value you want into the returned
00604    slot.  When inserting an entry, NULL may be returned if memory
00605    allocation fails.  */
00606 
00607 PTR *
00608 htab_find_slot_with_hash (htab_t htab, const PTR element,
00609                           hashval_t hash, enum insert_option insert)
00610 {
00611   PTR *first_deleted_slot;
00612   hashval_t index, hash2;
00613   size_t size;
00614   PTR entry;
00615 
00616   size = htab_size (htab);
00617   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
00618     {
00619       if (htab_expand (htab) == 0)
00620        return NULL;
00621       size = htab_size (htab);
00622     }
00623 
00624   index = htab_mod (hash, htab);
00625 
00626   htab->searches++;
00627   first_deleted_slot = NULL;
00628 
00629   entry = htab->entries[index];
00630   if (entry == HTAB_EMPTY_ENTRY)
00631     goto empty_entry;
00632   else if (entry == HTAB_DELETED_ENTRY)
00633     first_deleted_slot = &htab->entries[index];
00634   else if ((*htab->eq_f) (entry, element))
00635     return &htab->entries[index];
00636       
00637   hash2 = htab_mod_m2 (hash, htab);
00638   for (;;)
00639     {
00640       htab->collisions++;
00641       index += hash2;
00642       if (index >= size)
00643        index -= size;
00644       
00645       entry = htab->entries[index];
00646       if (entry == HTAB_EMPTY_ENTRY)
00647        goto empty_entry;
00648       else if (entry == HTAB_DELETED_ENTRY)
00649        {
00650          if (!first_deleted_slot)
00651            first_deleted_slot = &htab->entries[index];
00652        }
00653       else if ((*htab->eq_f) (entry, element))
00654        return &htab->entries[index];
00655     }
00656 
00657  empty_entry:
00658   if (insert == NO_INSERT)
00659     return NULL;
00660 
00661   if (first_deleted_slot)
00662     {
00663       htab->n_deleted--;
00664       *first_deleted_slot = HTAB_EMPTY_ENTRY;
00665       return first_deleted_slot;
00666     }
00667 
00668   htab->n_elements++;
00669   return &htab->entries[index];
00670 }
00671 
00672 /* Like htab_find_slot_with_hash, but compute the hash value from the
00673    element.  */
00674 
00675 PTR *
00676 htab_find_slot (htab_t htab, const PTR element, enum insert_option insert)
00677 {
00678   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
00679                                insert);
00680 }
00681 
00682 /* This function deletes an element with the given value from hash
00683    table (the hash is computed from the element).  If there is no matching
00684    element in the hash table, this function does nothing.  */
00685 
00686 void
00687 htab_remove_elt (htab_t htab, PTR element)
00688 {
00689   htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
00690 }
00691 
00692 
00693 /* This function deletes an element with the given value from hash
00694    table.  If there is no matching element in the hash table, this
00695    function does nothing.  */
00696 
00697 void
00698 htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
00699 {
00700   PTR *slot;
00701 
00702   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
00703   if (*slot == HTAB_EMPTY_ENTRY)
00704     return;
00705 
00706   if (htab->del_f)
00707     (*htab->del_f) (*slot);
00708 
00709   *slot = HTAB_DELETED_ENTRY;
00710   htab->n_deleted++;
00711 }
00712 
00713 /* This function clears a specified slot in a hash table.  It is
00714    useful when you've already done the lookup and don't want to do it
00715    again.  */
00716 
00717 void
00718 htab_clear_slot (htab_t htab, PTR *slot)
00719 {
00720   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
00721       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
00722     abort ();
00723 
00724   if (htab->del_f)
00725     (*htab->del_f) (*slot);
00726 
00727   *slot = HTAB_DELETED_ENTRY;
00728   htab->n_deleted++;
00729 }
00730 
00731 /* This function scans over the entire hash table calling
00732    CALLBACK for each live entry.  If CALLBACK returns false,
00733    the iteration stops.  INFO is passed as CALLBACK's second
00734    argument.  */
00735 
00736 void
00737 htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
00738 {
00739   PTR *slot;
00740   PTR *limit;
00741   
00742   slot = htab->entries;
00743   limit = slot + htab_size (htab);
00744 
00745   do
00746     {
00747       PTR x = *slot;
00748 
00749       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
00750        if (!(*callback) (slot, info))
00751          break;
00752     }
00753   while (++slot < limit);
00754 }
00755 
00756 /* Like htab_traverse_noresize, but does resize the table when it is
00757    too empty to improve effectivity of subsequent calls.  */
00758 
00759 void
00760 htab_traverse (htab_t htab, htab_trav callback, PTR info)
00761 {
00762   if (htab_elements (htab) * 8 < htab_size (htab))
00763     htab_expand (htab);
00764 
00765   htab_traverse_noresize (htab, callback, info);
00766 }
00767 
00768 /* Return the fraction of fixed collisions during all work with given
00769    hash table. */
00770 
00771 double
00772 htab_collisions (htab_t htab)
00773 {
00774   if (htab->searches == 0)
00775     return 0.0;
00776 
00777   return (double) htab->collisions / (double) htab->searches;
00778 }
00779 
00780 /* Hash P as a null-terminated string.
00781 
00782    Copied from gcc/hashtable.c.  Zack had the following to say with respect
00783    to applicability, though note that unlike hashtable.c, this hash table
00784    implementation re-hashes rather than chain buckets.
00785 
00786    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
00787    From: Zack Weinberg <zackw@panix.com>
00788    Date: Fri, 17 Aug 2001 02:15:56 -0400
00789 
00790    I got it by extracting all the identifiers from all the source code
00791    I had lying around in mid-1999, and testing many recurrences of
00792    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
00793    prime numbers or the appropriate identity.  This was the best one.
00794    I don't remember exactly what constituted "best", except I was
00795    looking at bucket-length distributions mostly.
00796    
00797    So it should be very good at hashing identifiers, but might not be
00798    as good at arbitrary strings.
00799    
00800    I'll add that it thoroughly trounces the hash functions recommended
00801    for this use at http://burtleburtle.net/bob/hash/index.html, both
00802    on speed and bucket distribution.  I haven't tried it against the
00803    function they just started using for Perl's hashes.  */
00804 
00805 hashval_t
00806 htab_hash_string (const PTR p)
00807 {
00808   const unsigned char *str = (const unsigned char *) p;
00809   hashval_t r = 0;
00810   unsigned char c;
00811 
00812   while ((c = *str++) != 0)
00813     r = r * 67 + c - 113;
00814 
00815   return r;
00816 }
00817 
00818 /* DERIVED FROM:
00819 --------------------------------------------------------------------
00820 lookup2.c, by Bob Jenkins, December 1996, Public Domain.
00821 hash(), hash2(), hash3, and mix() are externally useful functions.
00822 Routines to test the hash are included if SELF_TEST is defined.
00823 You can use this free for any purpose.  It has no warranty.
00824 --------------------------------------------------------------------
00825 */
00826 
00827 /*
00828 --------------------------------------------------------------------
00829 mix -- mix 3 32-bit values reversibly.
00830 For every delta with one or two bit set, and the deltas of all three
00831   high bits or all three low bits, whether the original value of a,b,c
00832   is almost all zero or is uniformly distributed,
00833 * If mix() is run forward or backward, at least 32 bits in a,b,c
00834   have at least 1/4 probability of changing.
00835 * If mix() is run forward, every bit of c will change between 1/3 and
00836   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
00837 mix() was built out of 36 single-cycle latency instructions in a 
00838   structure that could supported 2x parallelism, like so:
00839       a -= b; 
00840       a -= c; x = (c>>13);
00841       b -= c; a ^= x;
00842       b -= a; x = (a<<8);
00843       c -= a; b ^= x;
00844       c -= b; x = (b>>13);
00845       ...
00846   Unfortunately, superscalar Pentiums and Sparcs can't take advantage 
00847   of that parallelism.  They've also turned some of those single-cycle
00848   latency instructions into multi-cycle latency instructions.  Still,
00849   this is the fastest good hash I could find.  There were about 2^^68
00850   to choose from.  I only looked at a billion or so.
00851 --------------------------------------------------------------------
00852 */
00853 /* same, but slower, works on systems that might have 8 byte hashval_t's */
00854 #define mix(a,b,c) \
00855 { \
00856   a -= b; a -= c; a ^= (c>>13); \
00857   b -= c; b -= a; b ^= (a<< 8); \
00858   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
00859   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
00860   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
00861   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
00862   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
00863   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
00864   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
00865 }
00866 
00867 /*
00868 --------------------------------------------------------------------
00869 hash() -- hash a variable-length key into a 32-bit value
00870   k     : the key (the unaligned variable-length array of bytes)
00871   len   : the length of the key, counting by bytes
00872   level : can be any 4-byte value
00873 Returns a 32-bit value.  Every bit of the key affects every bit of
00874 the return value.  Every 1-bit and 2-bit delta achieves avalanche.
00875 About 36+6len instructions.
00876 
00877 The best hash table sizes are powers of 2.  There is no need to do
00878 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
00879 use a bitmask.  For example, if you need only 10 bits, do
00880   h = (h & hashmask(10));
00881 In which case, the hash table should have hashsize(10) elements.
00882 
00883 If you are hashing n strings (ub1 **)k, do it like this:
00884   for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
00885 
00886 By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
00887 code any way you wish, private, educational, or commercial.  It's free.
00888 
00889 See http://burtleburtle.net/bob/hash/evahash.html
00890 Use for hash table lookup, or anything where one collision in 2^32 is
00891 acceptable.  Do NOT use for cryptographic purposes.
00892 --------------------------------------------------------------------
00893 */
00894 
00895 hashval_t
00896 iterative_hash (const PTR k_in /* the key */,
00897                 register size_t  length /* the length of the key */,
00898                 register hashval_t initval /* the previous hash, or
00899                                               an arbitrary value */)
00900 {
00901   register const unsigned char *k = (const unsigned char *)k_in;
00902   register hashval_t a,b,c,len;
00903 
00904   /* Set up the internal state */
00905   len = length;
00906   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
00907   c = initval;           /* the previous hash value */
00908 
00909   /*---------------------------------------- handle most of the key */
00910 #ifndef WORDS_BIGENDIAN
00911   /* On a little-endian machine, if the data is 4-byte aligned we can hash
00912      by word for better speed.  This gives nondeterministic results on
00913      big-endian machines.  */
00914   if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0)
00915     while (len >= 12)    /* aligned */
00916       {
00917        a += *(hashval_t *)(k+0);
00918        b += *(hashval_t *)(k+4);
00919        c += *(hashval_t *)(k+8);
00920        mix(a,b,c);
00921        k += 12; len -= 12;
00922       }
00923   else /* unaligned */
00924 #endif
00925     while (len >= 12)
00926       {
00927        a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
00928        b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
00929        c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
00930        mix(a,b,c);
00931        k += 12; len -= 12;
00932       }
00933 
00934   /*------------------------------------- handle the last 11 bytes */
00935   c += length;
00936   switch(len)              /* all the case statements fall through */
00937     {
00938     case 11: c+=((hashval_t)k[10]<<24);
00939     case 10: c+=((hashval_t)k[9]<<16);
00940     case 9 : c+=((hashval_t)k[8]<<8);
00941       /* the first byte of c is reserved for the length */
00942     case 8 : b+=((hashval_t)k[7]<<24);
00943     case 7 : b+=((hashval_t)k[6]<<16);
00944     case 6 : b+=((hashval_t)k[5]<<8);
00945     case 5 : b+=k[4];
00946     case 4 : a+=((hashval_t)k[3]<<24);
00947     case 3 : a+=((hashval_t)k[2]<<16);
00948     case 2 : a+=((hashval_t)k[1]<<8);
00949     case 1 : a+=k[0];
00950       /* case 0: nothing left to add */
00951     }
00952   mix(a,b,c);
00953   /*-------------------------------------------- report the result */
00954   return c;
00955 }