OSDN Git Service

libcpp:
[pf3gnuchains/gcc-fork.git] / libcpp / symtab.c
1 /* Hash tables.
2    Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
3
4 This program is free software; you can redistribute it and/or modify it
5 under the terms of the GNU General Public License as published by the
6 Free Software Foundation; either version 2, or (at your option) any
7 later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
17
18  In other words, you are welcome to use, share and improve this program.
19  You are forbidden to forbid anyone else to use, share and improve
20  what you give them.   Help stamp out software-hoarding!  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "symtab.h"
25
26 /* The code below is a specialization of Vladimir Makarov's expandable
27    hash tables (see libiberty/hashtab.c).  The abstraction penalty was
28    too high to continue using the generic form.  This code knows
29    intrinsically how to calculate a hash value, and how to compare an
30    existing entry with a potential new one.  Also, the ability to
31    delete members from the table has been removed.  */
32
33 static unsigned int calc_hash (const unsigned char *, size_t);
34 static void ht_expand (hash_table *);
35 static double approx_sqrt (double);
36
37 /* Calculate the hash of the string STR of length LEN.  */
38
39 static unsigned int
40 calc_hash (const unsigned char *str, size_t len)
41 {
42   size_t n = len;
43   unsigned int r = 0;
44
45   while (n--)
46     r = HT_HASHSTEP (r, *str++);
47
48   return HT_HASHFINISH (r, len);
49 }
50
51 /* Initialize an identifier hashtable.  */
52
53 hash_table *
54 ht_create (unsigned int order)
55 {
56   unsigned int nslots = 1 << order;
57   hash_table *table;
58
59   table = xcalloc (1, sizeof (hash_table));
60
61   /* Strings need no alignment.  */
62   _obstack_begin (&table->stack, 0, 0,
63                   (void *(*) (long)) xmalloc,
64                   (void (*) (void *)) free);
65
66   obstack_alignment_mask (&table->stack) = 0;
67
68   table->entries = xcalloc (nslots, sizeof (hashnode));
69   table->entries_owned = true;
70   table->nslots = nslots;
71   return table;
72 }
73
74 /* Frees all memory associated with a hash table.  */
75
76 void
77 ht_destroy (hash_table *table)
78 {
79   obstack_free (&table->stack, NULL);
80   if (table->entries_owned)
81     free (table->entries);
82   free (table);
83 }
84
85 /* Returns the hash entry for the a STR of length LEN.  If that string
86    already exists in the table, returns the existing entry, and, if
87    INSERT is CPP_ALLOCED, frees the last obstack object.  If the
88    identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
89    returns NULL.  Otherwise insert and returns a new entry.  A new
90    string is alloced if INSERT is CPP_ALLOC, otherwise INSERT is
91    CPP_ALLOCED and the item is assumed to be at the top of the
92    obstack.  */
93 hashnode
94 ht_lookup (hash_table *table, const unsigned char *str, size_t len,
95            enum ht_lookup_option insert)
96 {
97   return ht_lookup_with_hash (table, str, len, calc_hash (str, len),
98                               insert);
99 }
100
101 hashnode
102 ht_lookup_with_hash (hash_table *table, const unsigned char *str,
103                      size_t len, unsigned int hash,
104                      enum ht_lookup_option insert)
105 {
106   unsigned int hash2;
107   unsigned int index;
108   size_t sizemask;
109   hashnode node;
110
111   sizemask = table->nslots - 1;
112   index = hash & sizemask;
113   table->searches++;
114
115   node = table->entries[index];
116  
117   if (node != NULL)
118     {
119       if (node->hash_value == hash
120           && HT_LEN (node) == (unsigned int) len
121           && !memcmp (HT_STR (node), str, len))
122         {
123           if (insert == HT_ALLOCED)
124             /* The string we search for was placed at the end of the
125                obstack.  Release it.  */
126             obstack_free (&table->stack, (void *) str);
127           return node;
128         }
129
130       /* hash2 must be odd, so we're guaranteed to visit every possible
131          location in the table during rehashing.  */
132       hash2 = ((hash * 17) & sizemask) | 1;
133
134       for (;;)
135         {
136           table->collisions++;
137           index = (index + hash2) & sizemask;
138           node = table->entries[index];
139           if (node == NULL)
140             break;
141
142           if (node->hash_value == hash
143               && HT_LEN (node) == (unsigned int) len
144               && !memcmp (HT_STR (node), str, len))
145             {
146               if (insert == HT_ALLOCED)
147               /* The string we search for was placed at the end of the
148                  obstack.  Release it.  */
149                 obstack_free (&table->stack, (void *) str);
150               return node;
151             }
152         }
153     }
154
155   if (insert == HT_NO_INSERT)
156     return NULL;
157
158   node = (*table->alloc_node) (table);
159   table->entries[index] = node;
160
161   HT_LEN (node) = (unsigned int) len;
162   node->hash_value = hash;
163   if (insert == HT_ALLOC)
164     HT_STR (node) = obstack_copy0 (&table->stack, str, len);
165   else
166     HT_STR (node) = str;
167
168   if (++table->nelements * 4 >= table->nslots * 3)
169     /* Must expand the string table.  */
170     ht_expand (table);
171
172   return node;
173 }
174
175 /* Double the size of a hash table, re-hashing existing entries.  */
176
177 static void
178 ht_expand (hash_table *table)
179 {
180   hashnode *nentries, *p, *limit;
181   unsigned int size, sizemask;
182
183   size = table->nslots * 2;
184   nentries = xcalloc (size, sizeof (hashnode));
185   sizemask = size - 1;
186
187   p = table->entries;
188   limit = p + table->nslots;
189   do
190     if (*p)
191       {
192         unsigned int index, hash, hash2;
193
194         hash = (*p)->hash_value;
195         index = hash & sizemask;
196
197         if (nentries[index])
198           {
199             hash2 = ((hash * 17) & sizemask) | 1;
200             do
201               {
202                 index = (index + hash2) & sizemask;
203               }
204             while (nentries[index]);
205           }
206         nentries[index] = *p;
207       }
208   while (++p < limit);
209
210   if (table->entries_owned)
211     free (table->entries);
212   table->entries_owned = true;
213   table->entries = nentries;
214   table->nslots = size;
215 }
216
217 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
218    the node, and V.  */
219 void
220 ht_forall (hash_table *table, ht_cb cb, const void *v)
221 {
222   hashnode *p, *limit;
223
224   p = table->entries;
225   limit = p + table->nslots;
226   do
227     if (*p)
228       {
229         if ((*cb) (table->pfile, *p, v) == 0)
230           break;
231       }
232   while (++p < limit);
233 }
234
235 /* Restore the hash table.  */
236 void
237 ht_load (hash_table *ht, hashnode *entries,
238          unsigned int nslots, unsigned int nelements,
239          bool own)
240 {
241   if (ht->entries_owned)
242     free (ht->entries);
243   ht->entries = entries;
244   ht->nslots = nslots;
245   ht->nelements = nelements;
246   ht->entries_owned = own;
247 }
248
249 /* Dump allocation statistics to stderr.  */
250
251 void
252 ht_dump_statistics (hash_table *table)
253 {
254   size_t nelts, nids, overhead, headers;
255   size_t total_bytes, longest, sum_of_squares;
256   double exp_len, exp_len2, exp2_len;
257   hashnode *p, *limit;
258
259 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
260                   ? (x) \
261                   : ((x) < 1024*1024*10 \
262                      ? (x) / 1024 \
263                      : (x) / (1024*1024))))
264 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
265
266   total_bytes = longest = sum_of_squares = nids = 0;
267   p = table->entries;
268   limit = p + table->nslots;
269   do
270     if (*p)
271       {
272         size_t n = HT_LEN (*p);
273
274         total_bytes += n;
275         sum_of_squares += n * n;
276         if (n > longest)
277           longest = n;
278         nids++;
279       }
280   while (++p < limit);
281
282   nelts = table->nelements;
283   overhead = obstack_memory_used (&table->stack) - total_bytes;
284   headers = table->nslots * sizeof (hashnode);
285
286   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
287            (unsigned long) nelts);
288   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
289            (unsigned long) nids, nids * 100.0 / nelts);
290   fprintf (stderr, "slots\t\t%lu\n",
291            (unsigned long) table->nslots);
292   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
293            SCALE (total_bytes), LABEL (total_bytes),
294            SCALE (overhead), LABEL (overhead));
295   fprintf (stderr, "table size\t%lu%c\n",
296            SCALE (headers), LABEL (headers));
297
298   exp_len = (double)total_bytes / (double)nelts;
299   exp2_len = exp_len * exp_len;
300   exp_len2 = (double) sum_of_squares / (double) nelts;
301
302   fprintf (stderr, "coll/search\t%.4f\n",
303            (double) table->collisions / (double) table->searches);
304   fprintf (stderr, "ins/search\t%.4f\n",
305            (double) nelts / (double) table->searches);
306   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
307            exp_len, approx_sqrt (exp_len2 - exp2_len));
308   fprintf (stderr, "longest entry\t%lu\n",
309            (unsigned long) longest);
310 #undef SCALE
311 #undef LABEL
312 }
313
314 /* Return the approximate positive square root of a number N.  This is for
315    statistical reports, not code generation.  */
316 static double
317 approx_sqrt (double x)
318 {
319   double s, d;
320
321   if (x < 0)
322     abort ();
323   if (x == 0)
324     return 0;
325
326   s = x;
327   do
328     {
329       d = (s * s - x) / (2 * s);
330       s -= d;
331     }
332   while (d > .0001);
333   return s;
334 }