OSDN Git Service

include/
[pf3gnuchains/gcc-fork.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   nsize = higher_prime_number (htab->size * 2);
377
378   if (htab->alloc_with_arg_f != NULL)
379     nentries = (PTR *) (*htab->alloc_with_arg_f) (htab->alloc_arg, nsize,
380                                                   sizeof (PTR *));
381   else
382     nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR *));
383   if (nentries == NULL)
384     return 0;
385   htab->entries = nentries;
386   htab->size = nsize;
387
388   htab->n_elements -= htab->n_deleted;
389   htab->n_deleted = 0;
390
391   p = oentries;
392   do
393     {
394       PTR x = *p;
395
396       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
397         {
398           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
399
400           *q = x;
401         }
402
403       p++;
404     }
405   while (p < olimit);
406
407   if (htab->free_f != NULL)
408     (*htab->free_f) (oentries);
409   else if (htab->free_with_arg_f != NULL)
410     (*htab->free_with_arg_f) (htab->alloc_arg, oentries);
411   return 1;
412 }
413
414 /* This function searches for a hash table entry equal to the given
415    element.  It cannot be used to insert or delete an element.  */
416
417 PTR
418 htab_find_with_hash (htab, element, hash)
419      htab_t htab;
420      const PTR element;
421      hashval_t hash;
422 {
423   unsigned int index;
424   hashval_t hash2;
425   size_t size;
426   PTR entry;
427
428   htab->searches++;
429   size = htab->size;
430   index = hash % size;
431
432   entry = htab->entries[index];
433   if (entry == EMPTY_ENTRY
434       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
435     return entry;
436
437   hash2 = 1 + hash % (size - 2);
438
439   for (;;)
440     {
441       htab->collisions++;
442       index += hash2;
443       if (index >= size)
444         index -= size;
445
446       entry = htab->entries[index];
447       if (entry == EMPTY_ENTRY
448           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
449         return entry;
450     }
451 }
452
453 /* Like htab_find_slot_with_hash, but compute the hash value from the
454    element.  */
455
456 PTR
457 htab_find (htab, element)
458      htab_t htab;
459      const PTR element;
460 {
461   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
462 }
463
464 /* This function searches for a hash table slot containing an entry
465    equal to the given element.  To delete an entry, call this with
466    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
467    after doing some checks).  To insert an entry, call this with
468    INSERT = 1, then write the value you want into the returned slot.
469    When inserting an entry, NULL may be returned if memory allocation
470    fails.  */
471
472 PTR *
473 htab_find_slot_with_hash (htab, element, hash, insert)
474      htab_t htab;
475      const PTR element;
476      hashval_t hash;
477      enum insert_option insert;
478 {
479   PTR *first_deleted_slot;
480   unsigned int index;
481   hashval_t hash2;
482   size_t size;
483   PTR entry;
484
485   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
486       && htab_expand (htab) == 0)
487     return NULL;
488
489   size = htab->size;
490   index = hash % size;
491
492   htab->searches++;
493   first_deleted_slot = NULL;
494
495   entry = htab->entries[index];
496   if (entry == EMPTY_ENTRY)
497     goto empty_entry;
498   else if (entry == DELETED_ENTRY)
499     first_deleted_slot = &htab->entries[index];
500   else if ((*htab->eq_f) (entry, element))
501     return &htab->entries[index];
502       
503   hash2 = 1 + hash % (size - 2);
504   for (;;)
505     {
506       htab->collisions++;
507       index += hash2;
508       if (index >= size)
509         index -= size;
510       
511       entry = htab->entries[index];
512       if (entry == EMPTY_ENTRY)
513         goto empty_entry;
514       else if (entry == DELETED_ENTRY)
515         {
516           if (!first_deleted_slot)
517             first_deleted_slot = &htab->entries[index];
518         }
519       else if ((*htab->eq_f) (entry, element))
520         return &htab->entries[index];
521     }
522
523  empty_entry:
524   if (insert == NO_INSERT)
525     return NULL;
526
527   htab->n_elements++;
528
529   if (first_deleted_slot)
530     {
531       *first_deleted_slot = EMPTY_ENTRY;
532       return first_deleted_slot;
533     }
534
535   return &htab->entries[index];
536 }
537
538 /* Like htab_find_slot_with_hash, but compute the hash value from the
539    element.  */
540
541 PTR *
542 htab_find_slot (htab, element, insert)
543      htab_t htab;
544      const PTR element;
545      enum insert_option insert;
546 {
547   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
548                                    insert);
549 }
550
551 /* This function deletes an element with the given value from hash
552    table.  If there is no matching element in the hash table, this
553    function does nothing.  */
554
555 void
556 htab_remove_elt (htab, element)
557      htab_t htab;
558      PTR element;
559 {
560   PTR *slot;
561
562   slot = htab_find_slot (htab, element, NO_INSERT);
563   if (*slot == EMPTY_ENTRY)
564     return;
565
566   if (htab->del_f)
567     (*htab->del_f) (*slot);
568
569   *slot = DELETED_ENTRY;
570   htab->n_deleted++;
571 }
572
573 /* This function clears a specified slot in a hash table.  It is
574    useful when you've already done the lookup and don't want to do it
575    again.  */
576
577 void
578 htab_clear_slot (htab, slot)
579      htab_t htab;
580      PTR *slot;
581 {
582   if (slot < htab->entries || slot >= htab->entries + htab->size
583       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
584     abort ();
585
586   if (htab->del_f)
587     (*htab->del_f) (*slot);
588
589   *slot = DELETED_ENTRY;
590   htab->n_deleted++;
591 }
592
593 /* This function scans over the entire hash table calling
594    CALLBACK for each live entry.  If CALLBACK returns false,
595    the iteration stops.  INFO is passed as CALLBACK's second
596    argument.  */
597
598 void
599 htab_traverse (htab, callback, info)
600      htab_t htab;
601      htab_trav callback;
602      PTR info;
603 {
604   PTR *slot = htab->entries;
605   PTR *limit = slot + htab->size;
606
607   do
608     {
609       PTR x = *slot;
610
611       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
612         if (!(*callback) (slot, info))
613           break;
614     }
615   while (++slot < limit);
616 }
617
618 /* Return the current size of given hash table. */
619
620 size_t
621 htab_size (htab)
622      htab_t htab;
623 {
624   return htab->size;
625 }
626
627 /* Return the current number of elements in given hash table. */
628
629 size_t
630 htab_elements (htab)
631      htab_t htab;
632 {
633   return htab->n_elements - htab->n_deleted;
634 }
635
636 /* Return the fraction of fixed collisions during all work with given
637    hash table. */
638
639 double
640 htab_collisions (htab)
641      htab_t htab;
642 {
643   if (htab->searches == 0)
644     return 0.0;
645
646   return (double) htab->collisions / (double) htab->searches;
647 }
648
649 /* Hash P as a null-terminated string.
650
651    Copied from gcc/hashtable.c.  Zack had the following to say with respect
652    to applicability, though note that unlike hashtable.c, this hash table
653    implementation re-hashes rather than chain buckets.
654
655    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
656    From: Zack Weinberg <zackw@panix.com>
657    Date: Fri, 17 Aug 2001 02:15:56 -0400
658
659    I got it by extracting all the identifiers from all the source code
660    I had lying around in mid-1999, and testing many recurrences of
661    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
662    prime numbers or the appropriate identity.  This was the best one.
663    I don't remember exactly what constituted "best", except I was
664    looking at bucket-length distributions mostly.
665    
666    So it should be very good at hashing identifiers, but might not be
667    as good at arbitrary strings.
668    
669    I'll add that it thoroughly trounces the hash functions recommended
670    for this use at http://burtleburtle.net/bob/hash/index.html, both
671    on speed and bucket distribution.  I haven't tried it against the
672    function they just started using for Perl's hashes.  */
673
674 hashval_t
675 htab_hash_string (p)
676      const PTR p;
677 {
678   const unsigned char *str = (const unsigned char *) p;
679   hashval_t r = 0;
680   unsigned char c;
681
682   while ((c = *str++) != 0)
683     r = r * 67 + c - 113;
684
685   return r;
686 }