OSDN Git Service

27741ef6247fc9219b93a3af177877291dd46485
[pf3gnuchains/gcc-fork.git] / libiberty / hashtab.c
1 /* An expandable hash tables datatype.  
2    Copyright (C) 1999, 2000, 2001, 2002 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 /* These functions exist solely for backward compatibility.  */
195
196 #undef htab_create
197 htab_t
198 htab_create (size, hash_f, eq_f, del_f)
199      size_t size;
200      htab_hash hash_f;
201      htab_eq eq_f;
202      htab_del del_f;
203 {
204   return htab_create_alloc (size, hash_f, eq_f, del_f, xcalloc, free);
205 }
206
207 htab_t
208 htab_try_create (size, hash_f, eq_f, del_f)
209      size_t size;
210      htab_hash hash_f;
211      htab_eq eq_f;
212      htab_del del_f;
213 {
214   return htab_create_alloc (size, hash_f, eq_f, del_f, calloc, free);
215 }
216
217 /* This function frees all memory allocated for given hash table.
218    Naturally the hash table must already exist. */
219
220 void
221 htab_delete (htab)
222      htab_t htab;
223 {
224   int i;
225
226   if (htab->del_f)
227     for (i = htab->size - 1; i >= 0; i--)
228       if (htab->entries[i] != EMPTY_ENTRY
229           && htab->entries[i] != DELETED_ENTRY)
230         (*htab->del_f) (htab->entries[i]);
231
232   if (htab->free_f != NULL)
233     {
234       (*htab->free_f) (htab->entries);
235       (*htab->free_f) (htab);
236     }
237 }
238
239 /* This function clears all entries in the given hash table.  */
240
241 void
242 htab_empty (htab)
243      htab_t htab;
244 {
245   int i;
246
247   if (htab->del_f)
248     for (i = htab->size - 1; i >= 0; i--)
249       if (htab->entries[i] != EMPTY_ENTRY
250           && htab->entries[i] != DELETED_ENTRY)
251         (*htab->del_f) (htab->entries[i]);
252
253   memset (htab->entries, 0, htab->size * sizeof (PTR));
254 }
255
256 /* Similar to htab_find_slot, but without several unwanted side effects:
257     - Does not call htab->eq_f when it finds an existing entry.
258     - Does not change the count of elements/searches/collisions in the
259       hash table.
260    This function also assumes there are no deleted entries in the table.
261    HASH is the hash value for the element to be inserted.  */
262
263 static PTR *
264 find_empty_slot_for_expand (htab, hash)
265      htab_t htab;
266      hashval_t hash;
267 {
268   size_t size = htab->size;
269   unsigned int index = hash % size;
270   PTR *slot = htab->entries + index;
271   hashval_t hash2;
272
273   if (*slot == EMPTY_ENTRY)
274     return slot;
275   else if (*slot == DELETED_ENTRY)
276     abort ();
277
278   hash2 = 1 + hash % (size - 2);
279   for (;;)
280     {
281       index += hash2;
282       if (index >= size)
283         index -= size;
284
285       slot = htab->entries + index;
286       if (*slot == EMPTY_ENTRY)
287         return slot;
288       else if (*slot == DELETED_ENTRY)
289         abort ();
290     }
291 }
292
293 /* The following function changes size of memory allocated for the
294    entries and repeatedly inserts the table elements.  The occupancy
295    of the table after the call will be about 50%.  Naturally the hash
296    table must already exist.  Remember also that the place of the
297    table entries is changed.  If memory allocation failures are allowed,
298    this function will return zero, indicating that the table could not be
299    expanded.  If all goes well, it will return a non-zero value.  */
300
301 static int
302 htab_expand (htab)
303      htab_t htab;
304 {
305   PTR *oentries;
306   PTR *olimit;
307   PTR *p;
308   PTR *nentries;
309   size_t nsize;
310
311   oentries = htab->entries;
312   olimit = oentries + htab->size;
313
314   nsize = higher_prime_number (htab->size * 2);
315
316   nentries = (PTR *) (*htab->alloc_f) (nsize, sizeof (PTR));
317   if (nentries == NULL)
318     return 0;
319   htab->entries = nentries;
320   htab->size = nsize;
321
322   htab->n_elements -= htab->n_deleted;
323   htab->n_deleted = 0;
324
325   p = oentries;
326   do
327     {
328       PTR x = *p;
329
330       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
331         {
332           PTR *q = find_empty_slot_for_expand (htab, (*htab->hash_f) (x));
333
334           *q = x;
335         }
336
337       p++;
338     }
339   while (p < olimit);
340
341   if (htab->free_f != NULL)
342     (*htab->free_f) (oentries);
343   return 1;
344 }
345
346 /* This function searches for a hash table entry equal to the given
347    element.  It cannot be used to insert or delete an element.  */
348
349 PTR
350 htab_find_with_hash (htab, element, hash)
351      htab_t htab;
352      const PTR element;
353      hashval_t hash;
354 {
355   unsigned int index;
356   hashval_t hash2;
357   size_t size;
358   PTR entry;
359
360   htab->searches++;
361   size = htab->size;
362   index = hash % size;
363
364   entry = htab->entries[index];
365   if (entry == EMPTY_ENTRY
366       || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
367     return entry;
368
369   hash2 = 1 + hash % (size - 2);
370
371   for (;;)
372     {
373       htab->collisions++;
374       index += hash2;
375       if (index >= size)
376         index -= size;
377
378       entry = htab->entries[index];
379       if (entry == EMPTY_ENTRY
380           || (entry != DELETED_ENTRY && (*htab->eq_f) (entry, element)))
381         return entry;
382     }
383 }
384
385 /* Like htab_find_slot_with_hash, but compute the hash value from the
386    element.  */
387
388 PTR
389 htab_find (htab, element)
390      htab_t htab;
391      const PTR element;
392 {
393   return htab_find_with_hash (htab, element, (*htab->hash_f) (element));
394 }
395
396 /* This function searches for a hash table slot containing an entry
397    equal to the given element.  To delete an entry, call this with
398    INSERT = 0, then call htab_clear_slot on the slot returned (possibly
399    after doing some checks).  To insert an entry, call this with
400    INSERT = 1, then write the value you want into the returned slot.
401    When inserting an entry, NULL may be returned if memory allocation
402    fails.  */
403
404 PTR *
405 htab_find_slot_with_hash (htab, element, hash, insert)
406      htab_t htab;
407      const PTR element;
408      hashval_t hash;
409      enum insert_option insert;
410 {
411   PTR *first_deleted_slot;
412   unsigned int index;
413   hashval_t hash2;
414   size_t size;
415   PTR entry;
416
417   if (insert == INSERT && htab->size * 3 <= htab->n_elements * 4
418       && htab_expand (htab) == 0)
419     return NULL;
420
421   size = htab->size;
422   index = hash % size;
423
424   htab->searches++;
425   first_deleted_slot = NULL;
426
427   entry = htab->entries[index];
428   if (entry == EMPTY_ENTRY)
429     goto empty_entry;
430   else if (entry == DELETED_ENTRY)
431     first_deleted_slot = &htab->entries[index];
432   else if ((*htab->eq_f) (entry, element))
433     return &htab->entries[index];
434       
435   hash2 = 1 + hash % (size - 2);
436   for (;;)
437     {
438       htab->collisions++;
439       index += hash2;
440       if (index >= size)
441         index -= size;
442       
443       entry = htab->entries[index];
444       if (entry == EMPTY_ENTRY)
445         goto empty_entry;
446       else if (entry == DELETED_ENTRY)
447         {
448           if (!first_deleted_slot)
449             first_deleted_slot = &htab->entries[index];
450         }
451       else if ((*htab->eq_f) (entry, element))
452         return &htab->entries[index];
453     }
454
455  empty_entry:
456   if (insert == NO_INSERT)
457     return NULL;
458
459   htab->n_elements++;
460
461   if (first_deleted_slot)
462     {
463       *first_deleted_slot = EMPTY_ENTRY;
464       return first_deleted_slot;
465     }
466
467   return &htab->entries[index];
468 }
469
470 /* Like htab_find_slot_with_hash, but compute the hash value from the
471    element.  */
472
473 PTR *
474 htab_find_slot (htab, element, insert)
475      htab_t htab;
476      const PTR element;
477      enum insert_option insert;
478 {
479   return htab_find_slot_with_hash (htab, element, (*htab->hash_f) (element),
480                                    insert);
481 }
482
483 /* This function deletes an element with the given value from hash
484    table.  If there is no matching element in the hash table, this
485    function does nothing.  */
486
487 void
488 htab_remove_elt (htab, element)
489      htab_t htab;
490      PTR element;
491 {
492   PTR *slot;
493
494   slot = htab_find_slot (htab, element, NO_INSERT);
495   if (*slot == EMPTY_ENTRY)
496     return;
497
498   if (htab->del_f)
499     (*htab->del_f) (*slot);
500
501   *slot = DELETED_ENTRY;
502   htab->n_deleted++;
503 }
504
505 /* This function clears a specified slot in a hash table.  It is
506    useful when you've already done the lookup and don't want to do it
507    again.  */
508
509 void
510 htab_clear_slot (htab, slot)
511      htab_t htab;
512      PTR *slot;
513 {
514   if (slot < htab->entries || slot >= htab->entries + htab->size
515       || *slot == EMPTY_ENTRY || *slot == DELETED_ENTRY)
516     abort ();
517
518   if (htab->del_f)
519     (*htab->del_f) (*slot);
520
521   *slot = DELETED_ENTRY;
522   htab->n_deleted++;
523 }
524
525 /* This function scans over the entire hash table calling
526    CALLBACK for each live entry.  If CALLBACK returns false,
527    the iteration stops.  INFO is passed as CALLBACK's second
528    argument.  */
529
530 void
531 htab_traverse (htab, callback, info)
532      htab_t htab;
533      htab_trav callback;
534      PTR info;
535 {
536   PTR *slot = htab->entries;
537   PTR *limit = slot + htab->size;
538
539   do
540     {
541       PTR x = *slot;
542
543       if (x != EMPTY_ENTRY && x != DELETED_ENTRY)
544         if (!(*callback) (slot, info))
545           break;
546     }
547   while (++slot < limit);
548 }
549
550 /* Return the current size of given hash table. */
551
552 size_t
553 htab_size (htab)
554      htab_t htab;
555 {
556   return htab->size;
557 }
558
559 /* Return the current number of elements in given hash table. */
560
561 size_t
562 htab_elements (htab)
563      htab_t htab;
564 {
565   return htab->n_elements - htab->n_deleted;
566 }
567
568 /* Return the fraction of fixed collisions during all work with given
569    hash table. */
570
571 double
572 htab_collisions (htab)
573      htab_t htab;
574 {
575   if (htab->searches == 0)
576     return 0.0;
577
578   return (double) htab->collisions / (double) htab->searches;
579 }
580
581 /* Hash P as a null-terminated string.
582
583    Copied from gcc/hashtable.c.  Zack had the following to say with respect
584    to applicability, though note that unlike hashtable.c, this hash table
585    implementation re-hashes rather than chain buckets.
586
587    http://gcc.gnu.org/ml/gcc-patches/2001-08/msg01021.html
588    From: Zack Weinberg <zackw@panix.com>
589    Date: Fri, 17 Aug 2001 02:15:56 -0400
590
591    I got it by extracting all the identifiers from all the source code
592    I had lying around in mid-1999, and testing many recurrences of
593    the form "H_n = H_{n-1} * K + c_n * L + M" where K, L, M were either
594    prime numbers or the appropriate identity.  This was the best one.
595    I don't remember exactly what constituted "best", except I was
596    looking at bucket-length distributions mostly.
597    
598    So it should be very good at hashing identifiers, but might not be
599    as good at arbitrary strings.
600    
601    I'll add that it thoroughly trounces the hash functions recommended
602    for this use at http://burtleburtle.net/bob/hash/index.html, both
603    on speed and bucket distribution.  I haven't tried it against the
604    function they just started using for Perl's hashes.  */
605
606 hashval_t
607 htab_hash_string (p)
608      const PTR p;
609 {
610   const unsigned char *str = (const unsigned char *) p;
611   hashval_t r = 0;
612   unsigned char c;
613
614   while ((c = *str++) != 0)
615     r = r * 67 + c - 113;
616
617   return r;
618 }