OSDN Git Service

5414ff05fc9dc3a5143b2818830a57b6565b6981
[pf3gnuchains/gcc-fork.git] / libcpp / symtab.c
1 /* Hash tables.
2    Copyright (C) 2000, 2001, 2003, 2004, 2008 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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.  */
31
32 static unsigned int calc_hash (const unsigned char *, size_t);
33 static void ht_expand (hash_table *);
34 static double approx_sqrt (double);
35
36 /* A deleted entry.  */
37 #define DELETED ((hashnode) -1)
38
39 /* Calculate the hash of the string STR of length LEN.  */
40
41 static unsigned int
42 calc_hash (const unsigned char *str, size_t len)
43 {
44   size_t n = len;
45   unsigned int r = 0;
46
47   while (n--)
48     r = HT_HASHSTEP (r, *str++);
49
50   return HT_HASHFINISH (r, len);
51 }
52
53 /* Initialize an identifier hashtable.  */
54
55 hash_table *
56 ht_create (unsigned int order)
57 {
58   unsigned int nslots = 1 << order;
59   hash_table *table;
60
61   table = XCNEW (hash_table);
62
63   /* Strings need no alignment.  */
64   _obstack_begin (&table->stack, 0, 0,
65                   (void *(*) (long)) xmalloc,
66                   (void (*) (void *)) free);
67
68   obstack_alignment_mask (&table->stack) = 0;
69
70   table->entries = XCNEWVEC (hashnode, nslots);
71   table->entries_owned = true;
72   table->nslots = nslots;
73   return table;
74 }
75
76 /* Frees all memory associated with a hash table.  */
77
78 void
79 ht_destroy (hash_table *table)
80 {
81   obstack_free (&table->stack, NULL);
82   if (table->entries_owned)
83     free (table->entries);
84   free (table);
85 }
86
87 /* Returns the hash entry for the a STR of length LEN.  If that string
88    already exists in the table, returns the existing entry.  If the
89    identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
90    returns NULL.  Otherwise insert and returns a new entry.  A new
91    string is allocated.  */
92 hashnode
93 ht_lookup (hash_table *table, const unsigned char *str, size_t len,
94            enum ht_lookup_option insert)
95 {
96   return ht_lookup_with_hash (table, str, len, calc_hash (str, len),
97                               insert);
98 }
99
100 hashnode
101 ht_lookup_with_hash (hash_table *table, const unsigned char *str,
102                      size_t len, unsigned int hash,
103                      enum ht_lookup_option insert)
104 {
105   unsigned int hash2;
106   unsigned int index;
107   unsigned int deleted_index = table->nslots;
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 == DELETED)
120         deleted_index = index;
121       else if (node->hash_value == hash
122                && HT_LEN (node) == (unsigned int) len
123                && !memcmp (HT_STR (node), str, len))
124         return node;
125
126       /* hash2 must be odd, so we're guaranteed to visit every possible
127          location in the table during rehashing.  */
128       hash2 = ((hash * 17) & sizemask) | 1;
129
130       for (;;)
131         {
132           table->collisions++;
133           index = (index + hash2) & sizemask;
134           node = table->entries[index];
135           if (node == NULL)
136             break;
137
138           if (node == DELETED)
139             {
140               if (deleted_index != table->nslots)
141                 deleted_index = index;
142             }
143           else if (node->hash_value == hash
144                    && HT_LEN (node) == (unsigned int) len
145                    && !memcmp (HT_STR (node), str, len))
146             return node;
147         }
148     }
149
150   if (insert == HT_NO_INSERT)
151     return NULL;
152
153   /* We prefer to overwrite the first deleted slot we saw.  */
154   if (deleted_index != table->nslots)
155     index = deleted_index;
156
157   node = (*table->alloc_node) (table);
158   table->entries[index] = node;
159
160   HT_LEN (node) = (unsigned int) len;
161   node->hash_value = hash;
162
163   if (table->alloc_subobject)
164     {
165       char *chars = table->alloc_subobject (len + 1);
166       memcpy (chars, str, len);
167       chars[len] = '\0';
168       HT_STR (node) = (const unsigned char *) chars;
169     }
170   else
171     HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack,
172                                                            str, len);
173
174   if (++table->nelements * 4 >= table->nslots * 3)
175     /* Must expand the string table.  */
176     ht_expand (table);
177
178   return node;
179 }
180
181 /* Double the size of a hash table, re-hashing existing entries.  */
182
183 static void
184 ht_expand (hash_table *table)
185 {
186   hashnode *nentries, *p, *limit;
187   unsigned int size, sizemask;
188
189   size = table->nslots * 2;
190   nentries = XCNEWVEC (hashnode, size);
191   sizemask = size - 1;
192
193   p = table->entries;
194   limit = p + table->nslots;
195   do
196     if (*p && *p != DELETED)
197       {
198         unsigned int index, hash, hash2;
199
200         hash = (*p)->hash_value;
201         index = hash & sizemask;
202
203         if (nentries[index])
204           {
205             hash2 = ((hash * 17) & sizemask) | 1;
206             do
207               {
208                 index = (index + hash2) & sizemask;
209               }
210             while (nentries[index]);
211           }
212         nentries[index] = *p;
213       }
214   while (++p < limit);
215
216   if (table->entries_owned)
217     free (table->entries);
218   table->entries_owned = true;
219   table->entries = nentries;
220   table->nslots = size;
221 }
222
223 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
224    the node, and V.  */
225 void
226 ht_forall (hash_table *table, ht_cb cb, const void *v)
227 {
228   hashnode *p, *limit;
229
230   p = table->entries;
231   limit = p + table->nslots;
232   do
233     if (*p && *p != DELETED)
234       {
235         if ((*cb) (table->pfile, *p, v) == 0)
236           break;
237       }
238   while (++p < limit);
239 }
240
241 /* Like ht_forall, but a nonzero return from the callback means that
242    the entry should be removed from the table.  */
243 void
244 ht_purge (hash_table *table, ht_cb cb, const void *v)
245 {
246   hashnode *p, *limit;
247
248   p = table->entries;
249   limit = p + table->nslots;
250   do
251     if (*p && *p != DELETED)
252       {
253         if ((*cb) (table->pfile, *p, v))
254           *p = DELETED;
255       }
256   while (++p < limit);
257 }
258
259 /* Restore the hash table.  */
260 void
261 ht_load (hash_table *ht, hashnode *entries,
262          unsigned int nslots, unsigned int nelements,
263          bool own)
264 {
265   if (ht->entries_owned)
266     free (ht->entries);
267   ht->entries = entries;
268   ht->nslots = nslots;
269   ht->nelements = nelements;
270   ht->entries_owned = own;
271 }
272
273 /* Dump allocation statistics to stderr.  */
274
275 void
276 ht_dump_statistics (hash_table *table)
277 {
278   size_t nelts, nids, overhead, headers;
279   size_t total_bytes, longest, deleted = 0;
280   double sum_of_squares, exp_len, exp_len2, exp2_len;
281   hashnode *p, *limit;
282
283 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
284                   ? (x) \
285                   : ((x) < 1024*1024*10 \
286                      ? (x) / 1024 \
287                      : (x) / (1024*1024))))
288 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
289
290   total_bytes = longest = sum_of_squares = nids = 0;
291   p = table->entries;
292   limit = p + table->nslots;
293   do
294     if (*p == DELETED)
295       ++deleted;
296     else if (*p)
297       {
298         size_t n = HT_LEN (*p);
299
300         total_bytes += n;
301         sum_of_squares += (double) n * n;
302         if (n > longest)
303           longest = n;
304         nids++;
305       }
306   while (++p < limit);
307
308   nelts = table->nelements;
309   overhead = obstack_memory_used (&table->stack) - total_bytes;
310   headers = table->nslots * sizeof (hashnode);
311
312   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
313            (unsigned long) nelts);
314   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
315            (unsigned long) nids, nids * 100.0 / nelts);
316   fprintf (stderr, "slots\t\t%lu\n",
317            (unsigned long) table->nslots);
318   fprintf (stderr, "deleted\t\t%lu\n",
319            (unsigned long) deleted);
320   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
321            SCALE (total_bytes), LABEL (total_bytes),
322            SCALE (overhead), LABEL (overhead));
323   fprintf (stderr, "table size\t%lu%c\n",
324            SCALE (headers), LABEL (headers));
325
326   exp_len = (double)total_bytes / (double)nelts;
327   exp2_len = exp_len * exp_len;
328   exp_len2 = (double) sum_of_squares / (double) nelts;
329
330   fprintf (stderr, "coll/search\t%.4f\n",
331            (double) table->collisions / (double) table->searches);
332   fprintf (stderr, "ins/search\t%.4f\n",
333            (double) nelts / (double) table->searches);
334   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
335            exp_len, approx_sqrt (exp_len2 - exp2_len));
336   fprintf (stderr, "longest entry\t%lu\n",
337            (unsigned long) longest);
338 #undef SCALE
339 #undef LABEL
340 }
341
342 /* Return the approximate positive square root of a number N.  This is for
343    statistical reports, not code generation.  */
344 static double
345 approx_sqrt (double x)
346 {
347   double s, d;
348
349   if (x < 0)
350     abort ();
351   if (x == 0)
352     return 0;
353
354   s = x;
355   do
356     {
357       d = (s * s - x) / (2 * s);
358       s -= d;
359     }
360   while (d > .0001);
361   return s;
362 }