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