OSDN Git Service

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