merge from gcc
[external/binutils.git] / libiberty / hashtab.c
1 /* An expandable hash tables datatype.  
2    Copyright (C) 1999, 2000, 2001, 2002, 2003 Free Software Foundation, Inc.
3    Contributed by Vladimir Makarov (vmakarov@cygnus.com).
4
5 This file is part of the libiberty library.
6 Libiberty is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Library General Public
8 License as published by the Free Software Foundation; either
9 version 2 of the License, or (at your option) any later version.
10
11 Libiberty is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 Library General Public License for more details.
15
16 You should have received a copy of the GNU Library General Public
17 License along with libiberty; see the file COPYING.LIB.  If
18 not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.  */
20
21 /* This package implements basic hash table functionality.  It is possible
22    to search for an entry, create an entry and destroy an entry.
23
24    Elements in the table are generic pointers.
25
26    The size of the table is not fixed; if the occupancy of the table
27    grows too high the hash table will be expanded.
28
29    The abstract data implementation is based on generalized Algorithm D
30    from Knuth's book "The art of computer programming".  Hash table is
31    expanded by creation of new hash table and transferring elements from
32    the old table to the new table. */
33
34 #ifdef HAVE_CONFIG_H
35 #include "config.h"
36 #endif
37
38 #include <sys/types.h>
39
40 #ifdef HAVE_STDLIB_H
41 #include <stdlib.h>
42 #endif
43
44 #ifdef HAVE_STRING_H
45 #include <string.h>
46 #endif
47
48 #include <stdio.h>
49
50 #include "libiberty.h"
51 #include "hashtab.h"
52
53 /* This macro defines reserved value for empty table entry. */
54
55 #define EMPTY_ENTRY    ((PTR) 0)
56
57 /* This macro defines reserved value for table entry which contained
58    a deleted element. */
59
60 #define DELETED_ENTRY  ((PTR) 1)
61
62 static unsigned long higher_prime_number PARAMS ((unsigned long));
63 static hashval_t hash_pointer PARAMS ((const void *));
64 static int eq_pointer PARAMS ((const void *, const void *));
65 static int htab_expand PARAMS ((htab_t));
66 static PTR *find_empty_slot_for_expand  PARAMS ((htab_t, hashval_t));
67
68 /* At some point, we could make these be NULL, and modify the
69    hash-table routines to handle NULL specially; that would avoid
70    function-call overhead for the common case of hashing pointers.  */
71 htab_hash htab_hash_pointer = hash_pointer;
72 htab_eq htab_eq_pointer = eq_pointer;
73
74 /* The following function returns a nearest prime number which is
75    greater than N, and near a power of two. */
76
77 static unsigned long
78 higher_prime_number (n)
79      unsigned long n;
80 {
81   /* These are primes that are near, but slightly smaller than, a
82      power of two.  */
83   static const unsigned long primes[] = {
84     (unsigned long) 7,
85     (unsigned long) 13,
86     (unsigned long) 31,
87     (unsigned long) 61,
88     (unsigned long) 127,
89     (unsigned long) 251,
90     (unsigned long) 509,
91     (unsigned long) 1021,
92     (unsigned long) 2039,
93     (unsigned long) 4093,
94     (unsigned long) 8191,
95     (unsigned long) 16381,
96     (unsigned long) 32749,
97     (unsigned long) 65521,
98     (unsigned long) 131071,
99     (unsigned long) 262139,
100     (unsigned long) 524287,
101     (unsigned long) 1048573,
102     (unsigned long) 2097143,
103     (unsigned long) 4194301,
104     (unsigned long) 8388593,
105     (unsigned long) 16777213,
106     (unsigned long) 33554393,
107     (unsigned long) 67108859,
108     (unsigned long) 134217689,
109     (unsigned long) 268435399,
110     (unsigned long) 536870909,
111     (unsigned long) 1073741789,
112     (unsigned long) 2147483647,
113                                         /* 4294967291L */
114     ((unsigned long) 2147483647) + ((unsigned long) 2147483644),
115   };
116
117   const unsigned long *low = &primes[0];
118   const unsigned long *high = &primes[sizeof(primes) / sizeof(primes[0])];
119
120   while (low != high)
121     {
122       const unsigned long *mid = low + (high - low) / 2;
123       if (n > *mid)
124         low = mid + 1;
125       else
126         high = mid;
127     }
128
129   /* If we've run out of primes, abort.  */
130   if (n > *low)
131     {
132       fprintf (stderr, "Cannot find prime bigger than %lu\n", n);
133       abort ();
134     }
135
136   return *low;
137 }
138
139 /* Returns a hash code for P.  */
140
141 static hashval_t
142 hash_pointer (p)
143      const PTR p;
144 {
145   return (hashval_t) ((long)p >> 3);
146 }
147
148 /* Returns non-zero if P1 and P2 are equal.  */
149
150 static int
151 eq_pointer (p1, p2)
152      const PTR p1;
153      const PTR p2;
154 {
155   return p1 == p2;
156 }
157
158 /* This function creates table with length slightly longer than given
159    source length.  Created hash table is initiated as empty (all the
160    hash table entries are EMPTY_ENTRY).  The function returns the
161    created hash table, or NULL if memory allocation fails.  */
162
163 htab_t
164 htab_create_alloc (size, hash_f, eq_f, del_f, alloc_f, free_f)
165      size_t size;
166      htab_hash hash_f;
167      htab_eq eq_f;
168      htab_del del_f;
169      htab_alloc alloc_f;
170      htab_free free_f;
171 {
172   htab_t result;
173
174   size = higher_prime_number (size);
175   result = (htab_t) (*alloc_f) (1, sizeof (struct htab));
176   if (result == NULL)
177     return NULL;
178   result->entries = (PTR *) (*alloc_f) (size, sizeof (PTR));
179   if (result->entries == NULL)
180     {
181       if (free_f != NULL)
182         (*free_f) (result);
183       return NULL;
184     }
185   result->size = size;
186   result->hash_f = hash_f;
187   result->eq_f = eq_f;
188   result->del_f = del_f;
189   result->alloc_f = alloc_f;
190   result->free_f = free_f;
191   return result;
192 }
193
194 /* As above, but use the variants of alloc_f and free_f which accept
195    an extra argument.  */
196
197 htab_t
198 htab_create_alloc_ex (size, hash_f, eq_f, del_f, alloc_arg, alloc_f,
199                       free_f)
200      size_t size;
201      htab_hash hash_f;
202      htab_eq eq_f;
203      htab_del del_f;
204      PTR alloc_arg;
205      htab_alloc_with_arg alloc_f;
206      htab_free_with_arg free_f;
207 {
208   htab_t result;
209
210   size = higher_prime_number (size);
211   result = (htab_t) (*alloc_f) (alloc_arg, 1, sizeof (struct htab));
212   if (result == NULL)
213     return NULL;
214   result->entries = (PTR *) (*alloc_f) (alloc_arg, size, sizeof (PTR));
215   if (result->entries == NULL)
216     {
217       if (free_f != NULL)
218         (*free_f) (alloc_arg, result);
219       return NULL;
220     }
221   result->size = size;
222   result->hash_f = hash_f;
223   result->eq_f = eq_f;
224   result->del_f = del_f;
225   result->alloc_arg = alloc_arg;
226   result->alloc_with_arg_f = alloc_f;
227   result->free_with_arg_f = free_f;
228   return result;
229 }
230
231 /* Update the function pointers and allocation parameter in the htab_t.  */
232
233 void
234 htab_set_functions_ex (htab, hash_f, eq_f, del_f, alloc_arg, alloc_f, free_f)
235      htab_t htab;
236      htab_hash hash_f;
237      htab_eq eq_f;
238      htab_del del_f;
239      PTR alloc_arg;
240      htab_alloc_with_arg alloc_f;
241      htab_free_with_arg free_f;
242 {
243   htab->hash_f = hash_f;
244   htab->eq_f = eq_f;
245   htab->del_f = del_f;
246   htab->alloc_arg = alloc_arg;
247   htab->alloc_with_arg_f = alloc_f;
248   htab->free_with_arg_f = free_f;
249 }
250
251 /* These functions exist solely for backward compatibility.  */
252
253 #undef htab_create
254 htab_t
255 htab_create (size, hash_f, eq_f, del_f)
256      size_t size;
257      htab_hash hash_f;
258      htab_eq eq_f;
259      htab_del del_f;
260 {
261   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
262 }
263
264 htab_t
265 htab_try_create (size, hash_f, eq_f, del_f)
266      size_t size;
267      htab_hash hash_f;
268      htab_eq eq_f;
269      htab_del del_f;
270 {
271   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
272 }
273
274 /* This function frees all memory allocated for given hash table.
275    Naturally the hash table must already exist. */
276
277 void
278 htab_delete (htab)
279      htab_t htab;
280 {
281   int i;
282
283   if (htab->del_f)
284     for (i = htab->size - 1; i >= 0; i--)
285       if (htab->entries[i] != EMPTY_ENTRY
286           && htab->entries[i] != DELETED_ENTRY)
287         (*htab->del_f) (htab->entries[i]);
288
289   if (htab->free_f != NULL)
290     {
291       (*htab->free_f) (htab->entries);
292       (*htab->free_f) (htab);
293     }
294   else if (htab->free_with_arg_f != NULL)
295     {
296       (*htab->free_with_arg_f) (htab->alloc_arg, htab->entries);
297       (*htab->free_with_arg_f) (htab->alloc_arg, htab);
298     }
299 }
300
301 /* This function clears all entries in the given hash table.  */
302
303 void
304 htab_empty (htab)
305      htab_t htab;
306 {
307   int i;
308
309   if (htab->del_f)
310     for (i = htab->size - 1; i >= 0; i--)
311       if (htab->entries[i] != EMPTY_ENTRY
312           && htab->entries[i] != DELETED_ENTRY)
313         (*htab->del_f) (htab->entries[i]);
314
315   memset (htab->entries, 0, htab->size * sizeof (PTR));
316 }
317
318 /* Similar to htab_find_slot, but without several unwanted side effects:
319     - Does not call htab->eq_f when it finds an existing entry.
320     - Does not change the count of elements/searches/collisions in the
321       hash table.
322    This function also assumes there are no deleted entries in the table.
323    HASH is the hash value for the element to be inserted.  */
324
325 static PTR *
326 find_empty_slot_for_expand (htab, hash)
327      htab_t htab;
328      hashval_t hash;
329 {
330   size_t size = htab->size;
331   unsigned int index = hash % size;
332   PTR *slot = htab->entries + index;
333   hashval_t hash2;
334
335   if (*slot == EMPTY_ENTRY)
336     return slot;
337   else if (*slot == DELETED_ENTRY)
338     abort ();
339
340   hash2 = 1 + hash % (size - 2);
341   for (;;)
342     {
343       index += hash2;
344       if (index >= size)
345         index -= size;
346
347       slot = htab->entries + index;
348       if (*slot == EMPTY_ENTRY)
349         return slot;
350       else if (*slot == DELETED_ENTRY)
351         abort ();
352     }
353 }
354
355 /* The following function changes size of memory allocated for the
356    entries and repeatedly inserts the table elements.  The occupancy
357    of the table after the call will be about 50%.  Naturally the hash
358    table must already exist.  Remember also that the place of the
359    table entries is changed.  If memory allocation failures are allowed,
360    this function will return zero, indicating that the table could not be
361    expanded.  If all goes well, it will return a non-zero value.  */
362
363 static int
364 htab_expand (htab)
365      htab_t htab;
366 {
367   PTR *oentries;
368   PTR *olimit;
369   PTR *p;
370   PTR *nentries;
371   size_t nsize;
372
373   oentries = htab->entries;
374   olimit = oentries + htab->size;
375
376   /* Resize only when table after removal of unused elements is either
377      too full or too empty.  */
378   if ((htab->n_elements - htab->n_deleted) * 2 > htab->size
379       || ((htab->n_elements - htab->n_deleted) * 8 < htab->size
380           && htab->size > 32))
381     nsize = higher_prime_number ((htab->n_elements - htab->n_deleted) * 2);
382   else
383     nsize = htab->size;
384
385   if (htab->alloc_with_arg_f != NULL)
386     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
387                                                   sizeof (PTR *));
388   else
389     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
390   if (nentries == NULL)
391     return 0;
392   htab->entries = nentries;
393   htab->size = nsize;
394
395   htab->n_elements -= htab->n_deleted;
396   htab->n_deleted = 0;
397
398   p = oentries;
399   do
400     {
401       PTR x = *p;
402
403       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
404         {
405           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
406
407           *q = x;
408         }
409
410       p++;
411     }
412   while (p < olimit);
413
414   if (htab->free_f != NULL)
415     (*htab->free_f) (oentries);
416   else if (htab->free_with_arg_f != NULL)
417     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
418   return 1;
419 }
420
421 /* This function searches for a hash table entry equal to the given
422    element.  It cannot be used to insert or delete an element.  */
423
424 PTR
425 htab_find_with_hash (htab, element, hash)
426      htab_t htab;
427      const PTR element;
428      hashval_t hash;
429 {
430   unsigned int index;
431   hashval_t hash2;
432   size_t size;
433   PTR entry;
434
435   htab->searches++;
436   size = htab->size;
437   index = hash % size;
438
439   entry = htab->entries[index];
440   if (entry == EMPTY_ENTRY
441       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
442     return entry;
443
444   hash2 = 1 + hash % (size - 2);
445
446   for (;;)
447     {
448       htab->collisions++;
449       index += hash2;
450       if (index >= size)
451         index -= size;
452
453       entry = htab->entries[index];
454       if (entry == EMPTY_ENTRY
455           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
456         return entry;
457     }
458 }
459
460 /* Like htab_find_slot_with_hash, but compute the hash value from the
461    element.  */
462
463 PTR
464 htab_find (htab, element)
465      htab_t htab;
466      const PTR element;
467 {
468   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
469 }
470
471 /* This function searches for a hash table slot containing an entry
472    equal to the given element.  To delete an entry, call this with
473    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
474    after doing some checks).  To insert an entry, call this with
475    INSERT = 1, then write the value you want into the returned slot.
476    When inserting an entry, NULL may be returned if memory allocation
477    fails.  */
478
479 PTR *
480 htab_find_slot_with_hash (htab, element, hash, insert)
481      htab_t htab;
482      const PTR element;
483      hashval_t hash;
484      enum insert_option insert;
485 {
486   PTR *first_deleted_slot;
487   unsigned int index;
488   hashval_t hash2;
489   size_t size;
490   PTR entry;
491
492   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
493       && htab_expand (htab) == 0)
494     return NULL;
495
496   size = htab->size;
497   index = hash % size;
498
499   htab->searches++;
500   first_deleted_slot = NULL;
501
502   entry = htab->entries[index];
503   if (entry == EMPTY_ENTRY)
504     goto empty_entry;
505   else if (entry == DELETED_ENTRY)
506     first_deleted_slot = &htab->entries[index];
507   else if ((*htab->eq_f) (entry, element))
508     return &htab->entries[index];
509       
510   hash2 = 1 + hash % (size - 2);
511   for (;;)
512     {
513       htab->collisions++;
514       index += hash2;
515       if (index >= size)
516         index -= size;
517       
518       entry = htab->entries[index];
519       if (entry == EMPTY_ENTRY)
520         goto empty_entry;
521       else if (entry == DELETED_ENTRY)
522         {
523           if (!first_deleted_slot)
524             first_deleted_slot = &htab->entries[index];
525         }
526       else if ((*htab->eq_f) (entry, element))
527         return &htab->entries[index];
528     }
529
530  empty_entry:
531   if (insert == NO_INSERT)
532     return NULL;
533
534   htab->n_elements++;
535
536   if (first_deleted_slot)
537     {
538       *first_deleted_slot = EMPTY_ENTRY;
539       return first_deleted_slot;
540     }
541
542   return &htab->entries[index];
543 }
544
545 /* Like htab_find_slot_with_hash, but compute the hash value from the
546    element.  */
547
548 PTR *
549 htab_find_slot (htab, element, insert)
550      htab_t htab;
551      const PTR element;
552      enum insert_option insert;
553 {
554   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
555                                    insert);
556 }
557
558 /* This function deletes an element with the given value from hash
559    table.  If there is no matching element in the hash table, this
560    function does nothing.  */
561
562 void
563 htab_remove_elt (htab, element)
564      htab_t htab;
565      PTR element;
566 {
567   PTR *slot;
568
569   slot = htab_find_slot (htab, element, NO_INSERT);
570   if (*slot == EMPTY_ENTRY)
571     return;
572
573   if (htab->del_f)
574     (*htab->del_f) (*slot);
575
576   *slot = DELETED_ENTRY;
577   htab->n_deleted++;
578 }
579
580 /* This function clears a specified slot in a hash table.  It is
581    useful when you've already done the lookup and don't want to do it
582    again.  */
583
584 void
585 htab_clear_slot (htab, slot)
586      htab_t htab;
587      PTR *slot;
588 {
589   if (slot < htab->entries || slot >= htab->entries + htab->size
590       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
591     abort ();
592
593   if (htab->del_f)
594     (*htab->del_f) (*slot);
595
596   *slot = DELETED_ENTRY;
597   htab->n_deleted++;
598 }
599
600 /* This function scans over the entire hash table calling
601    CALLBACK for each live entry.  If CALLBACK returns false,
602    the iteration stops.  INFO is passed as CALLBACK's second
603    argument.  */
604
605 void
606 htab_traverse_noresize (htab, callback, info)
607      htab_t htab;
608      htab_trav callback;
609      PTR info;
610 {
611   PTR *slot;
612   PTR *limit;
613
614   slot = htab->entries;
615   limit = slot + htab->size;
616
617   do
618     {
619       PTR x = *slot;
620
621       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
622         if (!(*callback) (slot, info))
623           break;
624     }
625   while (++slot < limit);
626 }
627
628 /* Like htab_traverse_noresize, but does resize the table when it is
629    too empty to improve effectivity of subsequent calls.  */
630
631 void
632 htab_traverse (htab, callback, info)
633      htab_t htab;
634      htab_trav callback;
635      PTR info;
636 {
637   if ((htab->n_elements - htab->n_deleted) * 8 < htab->size)
638     htab_expand (htab);
639
640   htab_traverse_noresize (htab, callback, info);
641 }
642
643 /* Return the current size of given hash table. */
644
645 size_t
646 htab_size (htab)
647      htab_t htab;
648 {
649   return htab->size;
650 }
651
652 /* Return the current number of elements in given hash table. */
653
654 size_t
655 htab_elements (htab)
656      htab_t htab;
657 {
658   return htab->n_elements - htab->n_deleted;
659 }
660
661 /* Return the fraction of fixed collisions during all work with given
662    hash table. */
663
664 double
665 htab_collisions (htab)
666      htab_t htab;
667 {
668   if (htab->searches == 0)
669     return 0.0;
670
671   return (double) htab->collisions / (double) htab->searches;
672 }
673
674 /* Hash P as a null-terminated string.
675
676    Copied from gcc/hashtable.c.  Zack had the following to say with respect
677    to applicability, though note that unlike hashtable.c, this hash table
678    implementation re-hashes rather than chain buckets.
679
680    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
681    From: Zack Weinberg <zackw@panix.com>
682    Date: Fri, 17 Aug 2001 02:15:56 -0400
683
684    I got it by extracting all the identifiers from all the source code
685    I had lying around in mid-1999, and testing many recurrences of
686    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
687    prime numbers or the appropriate identity.  This was the best one.
688    I don't remember exactly what constituted "best", except I was
689    looking at bucket-length distributions mostly.
690    
691    So it should be very good at hashing identifiers, but might not be
692    as good at arbitrary strings.
693    
694    I'll add that it thoroughly trounces the hash functions recommended
695    for this use at http://burtleburtle.net/bob/hash/index.html, both
696    on speed and bucket distribution.  I haven't tried it against the
697    function they just started using for Perl's hashes.  */
698
699 hashval_t
700 htab_hash_string (p)
701      const PTR p;
702 {
703   const unsigned char *str = (const unsigned char *) p;
704   hashval_t r = 0;
705   unsigned char c;
706
707   while ((c = *str++) != 0)
708     r = r * 67 + c - 113;
709
710   return r;
711 }