Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / binutils-2.22 / libiberty / hashtab.c
1 /* An expandable hash tables datatype.  
2    Copyright (C) 1999, 2000, 2001, 2002, 2003, 2004, 2009, 2010
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   return htab_create_typed_alloc (size, hash_f, eq_f, del_f, alloc_f, alloc_f,
295                                   free_f);
296 }
297
298 /* As above, but uses the variants of ALLOC_F and FREE_F which accept
299    an extra argument.  */
300
301 htab_t
302 htab_create_alloc_ex (size_t size, htab_hash hash_f, htab_eq eq_f,
303                       htab_del del_f, void *alloc_arg,
304                       htab_alloc_with_arg alloc_f,
305                       htab_free_with_arg free_f)
306 {
307   htab_t result;
308   unsigned int size_prime_index;
309
310   size_prime_index = higher_prime_index (size);
311   size = prime_tab[size_prime_index].prime;
312
313   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
314   if (result == NULL)
315     return NULL;
316   result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
317   if (result->entries == NULL)
318     {
319       if (free_f != NULL)
320         (*free_f) (alloc_arg, result);
321       return NULL;
322     }
323   result->size = size;
324   result->size_prime_index = size_prime_index;
325   result->hash_f = hash_f;
326   result->eq_f = eq_f;
327   result->del_f = del_f;
328   result->alloc_arg = alloc_arg;
329   result->alloc_with_arg_f = alloc_f;
330   result->free_with_arg_f = free_f;
331   return result;
332 }
333
334 /*
335
336 @deftypefn Supplemental htab_t htab_create_typed_alloc (size_t @var{size}, @
337 htab_hash @var{hash_f}, htab_eq @var{eq_f}, htab_del @var{del_f}, @
338 htab_alloc @var{alloc_tab_f}, htab_alloc @var{alloc_f}, @
339 htab_free @var{free_f})
340
341 This function creates a hash table that uses two different allocators
342 @var{alloc_tab_f} and @var{alloc_f} to use for allocating the table itself
343 and its entries respectively.  This is useful when variables of different
344 types need to be allocated with different allocators.
345
346 The created hash table is slightly larger than @var{size} and it is
347 initially empty (all the hash table entries are @code{HTAB_EMPTY_ENTRY}).
348 The function returns the created hash table, or @code{NULL} if memory
349 allocation fails.
350
351 @end deftypefn
352
353 */
354
355 htab_t
356 htab_create_typed_alloc (size_t size, htab_hash hash_f, htab_eq eq_f,
357                          htab_del del_f, htab_alloc alloc_tab_f,
358                          htab_alloc alloc_f, htab_free free_f)
359 {
360   htab_t result;
361   unsigned int size_prime_index;
362
363   size_prime_index = higher_prime_index (size);
364   size = prime_tab[size_prime_index].prime;
365
366   result = (htab_t) (*alloc_tab_f) (1, sizeof (struct htab));
367   if (result == NULL)
368     return NULL;
369   result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
370   if (result->entries == NULL)
371     {
372       if (free_f != NULL)
373         (*free_f) (result);
374       return NULL;
375     }
376   result->size = size;
377   result->size_prime_index = size_prime_index;
378   result->hash_f = hash_f;
379   result->eq_f = eq_f;
380   result->del_f = del_f;
381   result->alloc_f = alloc_f;
382   result->free_f = free_f;
383   return result;
384 }
385
386
387 /* Update the function pointers and allocation parameter in the htab_t.  */
388
389 void
390 htab_set_functions_ex (htab_t htab, htab_hash hash_f, htab_eq eq_f,
391                        htab_del del_f, PTR alloc_arg,
392                        htab_alloc_with_arg alloc_f, htab_free_with_arg free_f)
393 {
394   htab->hash_f = hash_f;
395   htab->eq_f = eq_f;
396   htab->del_f = del_f;
397   htab->alloc_arg = alloc_arg;
398   htab->alloc_with_arg_f = alloc_f;
399   htab->free_with_arg_f = free_f;
400 }
401
402 /* These functions exist solely for backward compatibility.  */
403
404 #undef htab_create
405 htab_t
406 htab_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
407 {
408   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
409 }
410
411 htab_t
412 htab_try_create (size_t size, htab_hash hash_f, htab_eq eq_f, htab_del del_f)
413 {
414   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
415 }
416
417 /* This function frees all memory allocated for given hash table.
418    Naturally the hash table must already exist. */
419
420 void
421 htab_delete (htab_t htab)
422 {
423   size_t size = htab_size (htab);
424   PTR *entries = htab->entries;
425   int i;
426
427   if (htab->del_f)
428     for (i = size - 1; i >= 0; i--)
429       if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
430         (*htab->del_f) (entries[i]);
431
432   if (htab->free_f != NULL)
433     {
434       (*htab->free_f) (entries);
435       (*htab->free_f) (htab);
436     }
437   else if (htab->free_with_arg_f != NULL)
438     {
439       (*htab->free_with_arg_f) (htab->alloc_arg, entries);
440       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
441     }
442 }
443
444 /* This function clears all entries in the given hash table.  */
445
446 void
447 htab_empty (htab_t htab)
448 {
449   size_t size = htab_size (htab);
450   PTR *entries = htab->entries;
451   int i;
452
453   if (htab->del_f)
454     for (i = size - 1; i >= 0; i--)
455       if (entries[i] != HTAB_EMPTY_ENTRY && entries[i] != HTAB_DELETED_ENTRY)
456         (*htab->del_f) (entries[i]);
457
458   /* Instead of clearing megabyte, downsize the table.  */
459   if (size > 1024*1024 / sizeof (PTR))
460     {
461       int nindex = higher_prime_index (1024 / sizeof (PTR));
462       int nsize = prime_tab[nindex].prime;
463
464       if (htab->free_f != NULL)
465         (*htab->free_f) (htab->entries);
466       else if (htab->free_with_arg_f != NULL)
467         (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
468       if (htab->alloc_with_arg_f != NULL)
469         htab->entries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
470                                                            sizeof (PTR *));
471       else
472         htab->entries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
473      htab->size = nsize;
474      htab->size_prime_index = nindex;
475     }
476   else
477     memset (entries, 0, size * sizeof (PTR));
478   htab->n_deleted = 0;
479   htab->n_elements = 0;
480 }
481
482 /* Similar to htab_find_slot, but without several unwanted side effects:
483     - Does not call htab->eq_f when it finds an existing entry.
484     - Does not change the count of elements/searches/collisions in the
485       hash table.
486    This function also assumes there are no deleted entries in the table.
487    HASH is the hash value for the element to be inserted.  */
488
489 static PTR *
490 find_empty_slot_for_expand (htab_t htab, hashval_t hash)
491 {
492   hashval_t index = htab_mod (hash, htab);
493   size_t size = htab_size (htab);
494   PTR *slot = htab->entries + index;
495   hashval_t hash2;
496
497   if (*slot == HTAB_EMPTY_ENTRY)
498     return slot;
499   else if (*slot == HTAB_DELETED_ENTRY)
500     abort ();
501
502   hash2 = htab_mod_m2 (hash, htab);
503   for (;;)
504     {
505       index += hash2;
506       if (index >= size)
507         index -= size;
508
509       slot = htab->entries + index;
510       if (*slot == HTAB_EMPTY_ENTRY)
511         return slot;
512       else if (*slot == HTAB_DELETED_ENTRY)
513         abort ();
514     }
515 }
516
517 /* The following function changes size of memory allocated for the
518    entries and repeatedly inserts the table elements.  The occupancy
519    of the table after the call will be about 50%.  Naturally the hash
520    table must already exist.  Remember also that the place of the
521    table entries is changed.  If memory allocation failures are allowed,
522    this function will return zero, indicating that the table could not be
523    expanded.  If all goes well, it will return a non-zero value.  */
524
525 static int
526 htab_expand (htab_t htab)
527 {
528   PTR *oentries;
529   PTR *olimit;
530   PTR *p;
531   PTR *nentries;
532   size_t nsize, osize, elts;
533   unsigned int oindex, nindex;
534
535   oentries = htab->entries;
536   oindex = htab->size_prime_index;
537   osize = htab->size;
538   olimit = oentries + osize;
539   elts = htab_elements (htab);
540
541   /* Resize only when table after removal of unused elements is either
542      too full or too empty.  */
543   if (elts * 2 > osize || (elts * 8 < osize && osize > 32))
544     {
545       nindex = higher_prime_index (elts * 2);
546       nsize = prime_tab[nindex].prime;
547     }
548   else
549     {
550       nindex = oindex;
551       nsize = osize;
552     }
553
554   if (htab->alloc_with_arg_f != NULL)
555     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
556                                                   sizeof (PTR *));
557   else
558     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
559   if (nentries == NULL)
560     return 0;
561   htab->entries = nentries;
562   htab->size = nsize;
563   htab->size_prime_index = nindex;
564   htab->n_elements -= htab->n_deleted;
565   htab->n_deleted = 0;
566
567   p = oentries;
568   do
569     {
570       PTR x = *p;
571
572       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
573         {
574           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
575
576           *q = x;
577         }
578
579       p++;
580     }
581   while (p < olimit);
582
583   if (htab->free_f != NULL)
584     (*htab->free_f) (oentries);
585   else if (htab->free_with_arg_f != NULL)
586     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
587   return 1;
588 }
589
590 /* This function searches for a hash table entry equal to the given
591    element.  It cannot be used to insert or delete an element.  */
592
593 PTR
594 htab_find_with_hash (htab_t htab, const PTR element, hashval_t hash)
595 {
596   hashval_t index, hash2;
597   size_t size;
598   PTR entry;
599
600   htab->searches++;
601   size = htab_size (htab);
602   index = htab_mod (hash, htab);
603
604   entry = htab->entries[index];
605   if (entry == HTAB_EMPTY_ENTRY
606       || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
607     return entry;
608
609   hash2 = htab_mod_m2 (hash, htab);
610   for (;;)
611     {
612       htab->collisions++;
613       index += hash2;
614       if (index >= size)
615         index -= size;
616
617       entry = htab->entries[index];
618       if (entry == HTAB_EMPTY_ENTRY
619           || (entry != HTAB_DELETED_ENTRY && (*htab->eq_f) (entry, element)))
620         return entry;
621     }
622 }
623
624 /* Like htab_find_slot_with_hash, but compute the hash value from the
625    element.  */
626
627 PTR
628 htab_find (htab_t htab, const PTR element)
629 {
630   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
631 }
632
633 /* This function searches for a hash table slot containing an entry
634    equal to the given element.  To delete an entry, call this with
635    insert=NO_INSERT, then call htab_clear_slot on the slot returned
636    (possibly after doing some checks).  To insert an entry, call this
637    with insert=INSERT, then write the value you want into the returned
638    slot.  When inserting an entry, NULL may be returned if memory
639    allocation fails.  */
640
641 PTR *
642 htab_find_slot_with_hash (htab_t htab, const PTR element,
643                           hashval_t hash, enum insert_option insert)
644 {
645   PTR *first_deleted_slot;
646   hashval_t index, hash2;
647   size_t size;
648   PTR entry;
649
650   size = htab_size (htab);
651   if (insert == INSERT && size * 3 <= htab->n_elements * 4)
652     {
653       if (htab_expand (htab) == 0)
654         return NULL;
655       size = htab_size (htab);
656     }
657
658   index = htab_mod (hash, htab);
659
660   htab->searches++;
661   first_deleted_slot = NULL;
662
663   entry = htab->entries[index];
664   if (entry == HTAB_EMPTY_ENTRY)
665     goto empty_entry;
666   else if (entry == HTAB_DELETED_ENTRY)
667     first_deleted_slot = &htab->entries[index];
668   else if ((*htab->eq_f) (entry, element))
669     return &htab->entries[index];
670       
671   hash2 = htab_mod_m2 (hash, htab);
672   for (;;)
673     {
674       htab->collisions++;
675       index += hash2;
676       if (index >= size)
677         index -= size;
678       
679       entry = htab->entries[index];
680       if (entry == HTAB_EMPTY_ENTRY)
681         goto empty_entry;
682       else if (entry == HTAB_DELETED_ENTRY)
683         {
684           if (!first_deleted_slot)
685             first_deleted_slot = &htab->entries[index];
686         }
687       else if ((*htab->eq_f) (entry, element))
688         return &htab->entries[index];
689     }
690
691  empty_entry:
692   if (insert == NO_INSERT)
693     return NULL;
694
695   if (first_deleted_slot)
696     {
697       htab->n_deleted--;
698       *first_deleted_slot = HTAB_EMPTY_ENTRY;
699       return first_deleted_slot;
700     }
701
702   htab->n_elements++;
703   return &htab->entries[index];
704 }
705
706 /* Like htab_find_slot_with_hash, but compute the hash value from the
707    element.  */
708
709 PTR *
710 htab_find_slot (htab_t htab, const PTR element, enum insert_option insert)
711 {
712   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
713                                    insert);
714 }
715
716 /* This function deletes an element with the given value from hash
717    table (the hash is computed from the element).  If there is no matching
718    element in the hash table, this function does nothing.  */
719
720 void
721 htab_remove_elt (htab_t htab, PTR element)
722 {
723   htab_remove_elt_with_hash (htab, element, (*htab->hash_f) (element));
724 }
725
726
727 /* This function deletes an element with the given value from hash
728    table.  If there is no matching element in the hash table, this
729    function does nothing.  */
730
731 void
732 htab_remove_elt_with_hash (htab_t htab, PTR element, hashval_t hash)
733 {
734   PTR *slot;
735
736   slot = htab_find_slot_with_hash (htab, element, hash, NO_INSERT);
737   if (*slot == HTAB_EMPTY_ENTRY)
738     return;
739
740   if (htab->del_f)
741     (*htab->del_f) (*slot);
742
743   *slot = HTAB_DELETED_ENTRY;
744   htab->n_deleted++;
745 }
746
747 /* This function clears a specified slot in a hash table.  It is
748    useful when you've already done the lookup and don't want to do it
749    again.  */
750
751 void
752 htab_clear_slot (htab_t htab, PTR *slot)
753 {
754   if (slot < htab->entries || slot >= htab->entries + htab_size (htab)
755       || *slot == HTAB_EMPTY_ENTRY || *slot == HTAB_DELETED_ENTRY)
756     abort ();
757
758   if (htab->del_f)
759     (*htab->del_f) (*slot);
760
761   *slot = HTAB_DELETED_ENTRY;
762   htab->n_deleted++;
763 }
764
765 /* This function scans over the entire hash table calling
766    CALLBACK for each live entry.  If CALLBACK returns false,
767    the iteration stops.  INFO is passed as CALLBACK's second
768    argument.  */
769
770 void
771 htab_traverse_noresize (htab_t htab, htab_trav callback, PTR info)
772 {
773   PTR *slot;
774   PTR *limit;
775   
776   slot = htab->entries;
777   limit = slot + htab_size (htab);
778
779   do
780     {
781       PTR x = *slot;
782
783       if (x != HTAB_EMPTY_ENTRY && x != HTAB_DELETED_ENTRY)
784         if (!(*callback) (slot, info))
785           break;
786     }
787   while (++slot < limit);
788 }
789
790 /* Like htab_traverse_noresize, but does resize the table when it is
791    too empty to improve effectivity of subsequent calls.  */
792
793 void
794 htab_traverse (htab_t htab, htab_trav callback, PTR info)
795 {
796   size_t size = htab_size (htab);
797   if (htab_elements (htab) * 8 < size && size > 32)
798     htab_expand (htab);
799
800   htab_traverse_noresize (htab, callback, info);
801 }
802
803 /* Return the fraction of fixed collisions during all work with given
804    hash table. */
805
806 double
807 htab_collisions (htab_t htab)
808 {
809   if (htab->searches == 0)
810     return 0.0;
811
812   return (double) htab->collisions / (double) htab->searches;
813 }
814
815 /* Hash P as a null-terminated string.
816
817    Copied from gcc/hashtable.c.  Zack had the following to say with respect
818    to applicability, though note that unlike hashtable.c, this hash table
819    implementation re-hashes rather than chain buckets.
820
821    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
822    From: Zack Weinberg <zackw@panix.com>
823    Date: Fri, 17 Aug 2001 02:15:56 -0400
824
825    I got it by extracting all the identifiers from all the source code
826    I had lying around in mid-1999, and testing many recurrences of
827    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
828    prime numbers or the appropriate identity.  This was the best one.
829    I don't remember exactly what constituted "best", except I was
830    looking at bucket-length distributions mostly.
831    
832    So it should be very good at hashing identifiers, but might not be
833    as good at arbitrary strings.
834    
835    I'll add that it thoroughly trounces the hash functions recommended
836    for this use at http://burtleburtle.net/bob/hash/index.html, both
837    on speed and bucket distribution.  I haven't tried it against the
838    function they just started using for Perl's hashes.  */
839
840 hashval_t
841 htab_hash_string (const PTR p)
842 {
843   const unsigned char *str = (const unsigned char *) p;
844   hashval_t r = 0;
845   unsigned char c;
846
847   while ((c = *str++) != 0)
848     r = r * 67 + c - 113;
849
850   return r;
851 }
852
853 /* DERIVED FROM:
854 --------------------------------------------------------------------
855 lookup2.c, by Bob Jenkins, December 1996, Public Domain.
856 hash(), hash2(), hash3, and mix() are externally useful functions.
857 Routines to test the hash are included if SELF_TEST is defined.
858 You can use this free for any purpose.  It has no warranty.
859 --------------------------------------------------------------------
860 */
861
862 /*
863 --------------------------------------------------------------------
864 mix -- mix 3 32-bit values reversibly.
865 For every delta with one or two bit set, and the deltas of all three
866   high bits or all three low bits, whether the original value of a,b,c
867   is almost all zero or is uniformly distributed,
868 * If mix() is run forward or backward, at least 32 bits in a,b,c
869   have at least 1/4 probability of changing.
870 * If mix() is run forward, every bit of c will change between 1/3 and
871   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
872 mix() was built out of 36 single-cycle latency instructions in a 
873   structure that could supported 2x parallelism, like so:
874       a -= b; 
875       a -= c; x = (c>>13);
876       b -= c; a ^= x;
877       b -= a; x = (a<<8);
878       c -= a; b ^= x;
879       c -= b; x = (b>>13);
880       ...
881   Unfortunately, superscalar Pentiums and Sparcs can't take advantage 
882   of that parallelism.  They've also turned some of those single-cycle
883   latency instructions into multi-cycle latency instructions.  Still,
884   this is the fastest good hash I could find.  There were about 2^^68
885   to choose from.  I only looked at a billion or so.
886 --------------------------------------------------------------------
887 */
888 /* same, but slower, works on systems that might have 8 byte hashval_t's */
889 #define mix(a,b,c) \
890 { \
891   a -= b; a -= c; a ^= (c>>13); \
892   b -= c; b -= a; b ^= (a<< 8); \
893   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
894   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
895   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
896   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
897   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
898   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
899   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
900 }
901
902 /*
903 --------------------------------------------------------------------
904 hash() -- hash a variable-length key into a 32-bit value
905   k     : the key (the unaligned variable-length array of bytes)
906   len   : the length of the key, counting by bytes
907   level : can be any 4-byte value
908 Returns a 32-bit value.  Every bit of the key affects every bit of
909 the return value.  Every 1-bit and 2-bit delta achieves avalanche.
910 About 36+6len instructions.
911
912 The best hash table sizes are powers of 2.  There is no need to do
913 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
914 use a bitmask.  For example, if you need only 10 bits, do
915   h = (h & hashmask(10));
916 In which case, the hash table should have hashsize(10) elements.
917
918 If you are hashing n strings (ub1 **)k, do it like this:
919   for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
920
921 By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
922 code any way you wish, private, educational, or commercial.  It's free.
923
924 See http://burtleburtle.net/bob/hash/evahash.html
925 Use for hash table lookup, or anything where one collision in 2^32 is
926 acceptable.  Do NOT use for cryptographic purposes.
927 --------------------------------------------------------------------
928 */
929
930 hashval_t
931 iterative_hash (const PTR k_in /* the key */,
932                 register size_t  length /* the length of the key */,
933                 register hashval_t initval /* the previous hash, or
934                                               an arbitrary value */)
935 {
936   register const unsigned char *k = (const unsigned char *)k_in;
937   register hashval_t a,b,c,len;
938
939   /* Set up the internal state */
940   len = length;
941   a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
942   c = initval;           /* the previous hash value */
943
944   /*---------------------------------------- handle most of the key */
945 #ifndef WORDS_BIGENDIAN
946   /* On a little-endian machine, if the data is 4-byte aligned we can hash
947      by word for better speed.  This gives nondeterministic results on
948      big-endian machines.  */
949   if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0)
950     while (len >= 12)    /* aligned */
951       {
952         a += *(hashval_t *)(k+0);
953         b += *(hashval_t *)(k+4);
954         c += *(hashval_t *)(k+8);
955         mix(a,b,c);
956         k += 12; len -= 12;
957       }
958   else /* unaligned */
959 #endif
960     while (len >= 12)
961       {
962         a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24));
963         b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24));
964         c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)k[11]<<24));
965         mix(a,b,c);
966         k += 12; len -= 12;
967       }
968
969   /*------------------------------------- handle the last 11 bytes */
970   c += length;
971   switch(len)              /* all the case statements fall through */
972     {
973     case 11: c+=((hashval_t)k[10]<<24);
974     case 10: c+=((hashval_t)k[9]<<16);
975     case 9 : c+=((hashval_t)k[8]<<8);
976       /* the first byte of c is reserved for the length */
977     case 8 : b+=((hashval_t)k[7]<<24);
978     case 7 : b+=((hashval_t)k[6]<<16);
979     case 6 : b+=((hashval_t)k[5]<<8);
980     case 5 : b+=k[4];
981     case 4 : a+=((hashval_t)k[3]<<24);
982     case 3 : a+=((hashval_t)k[2]<<16);
983     case 2 : a+=((hashval_t)k[1]<<8);
984     case 1 : a+=k[0];
985       /* case 0: nothing left to add */
986     }
987   mix(a,b,c);
988   /*-------------------------------------------- report the result */
989   return c;
990 }