OSDN Git Service

* ifcvt.c (cond_exec_find_if_block): Return FALSE if no
[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, 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.  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 = XCNEW (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 = XCNEWVEC (hashnode, nslots);
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) = (const unsigned char *) obstack_copy0 (&table->stack,
165                                                            str, len);
166   else
167     HT_STR (node) = str;
168
169   if (++table->nelements * 4 >= table->nslots * 3)
170     /* Must expand the string table.  */
171     ht_expand (table);
172
173   return node;
174 }
175
176 /* Double the size of a hash table, re-hashing existing entries.  */
177
178 static void
179 ht_expand (hash_table *table)
180 {
181   hashnode *nentries, *p, *limit;
182   unsigned int size, sizemask;
183
184   size = table->nslots * 2;
185   nentries = XCNEWVEC (hashnode, size);
186   sizemask = size - 1;
187
188   p = table->entries;
189   limit = p + table->nslots;
190   do
191     if (*p)
192       {
193         unsigned int index, hash, hash2;
194
195         hash = (*p)->hash_value;
196         index = hash & sizemask;
197
198         if (nentries[index])
199           {
200             hash2 = ((hash * 17) & sizemask) | 1;
201             do
202               {
203                 index = (index + hash2) & sizemask;
204               }
205             while (nentries[index]);
206           }
207         nentries[index] = *p;
208       }
209   while (++p < limit);
210
211   if (table->entries_owned)
212     free (table->entries);
213   table->entries_owned = true;
214   table->entries = nentries;
215   table->nslots = size;
216 }
217
218 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
219    the node, and V.  */
220 void
221 ht_forall (hash_table *table, ht_cb cb, const void *v)
222 {
223   hashnode *p, *limit;
224
225   p = table->entries;
226   limit = p + table->nslots;
227   do
228     if (*p)
229       {
230         if ((*cb) (table->pfile, *p, v) == 0)
231           break;
232       }
233   while (++p < limit);
234 }
235
236 /* Restore the hash table.  */
237 void
238 ht_load (hash_table *ht, hashnode *entries,
239          unsigned int nslots, unsigned int nelements,
240          bool own)
241 {
242   if (ht->entries_owned)
243     free (ht->entries);
244   ht->entries = entries;
245   ht->nslots = nslots;
246   ht->nelements = nelements;
247   ht->entries_owned = own;
248 }
249
250 /* Dump allocation statistics to stderr.  */
251
252 void
253 ht_dump_statistics (hash_table *table)
254 {
255   size_t nelts, nids, overhead, headers;
256   size_t total_bytes, longest;
257   double sum_of_squares, exp_len, exp_len2, exp2_len;
258   hashnode *p, *limit;
259
260 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
261                   ? (x) \
262                   : ((x) < 1024*1024*10 \
263                      ? (x) / 1024 \
264                      : (x) / (1024*1024))))
265 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
266
267   total_bytes = longest = sum_of_squares = nids = 0;
268   p = table->entries;
269   limit = p + table->nslots;
270   do
271     if (*p)
272       {
273         size_t n = HT_LEN (*p);
274
275         total_bytes += n;
276         sum_of_squares += (double) n * n;
277         if (n > longest)
278           longest = n;
279         nids++;
280       }
281   while (++p < limit);
282
283   nelts = table->nelements;
284   overhead = obstack_memory_used (&table->stack) - total_bytes;
285   headers = table->nslots * sizeof (hashnode);
286
287   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
288            (unsigned long) nelts);
289   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
290            (unsigned long) nids, nids * 100.0 / nelts);
291   fprintf (stderr, "slots\t\t%lu\n",
292            (unsigned long) table->nslots);
293   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
294            SCALE (total_bytes), LABEL (total_bytes),
295            SCALE (overhead), LABEL (overhead));
296   fprintf (stderr, "table size\t%lu%c\n",
297            SCALE (headers), LABEL (headers));
298
299   exp_len = (double)total_bytes / (double)nelts;
300   exp2_len = exp_len * exp_len;
301   exp_len2 = (double) sum_of_squares / (double) nelts;
302
303   fprintf (stderr, "coll/search\t%.4f\n",
304            (double) table->collisions / (double) table->searches);
305   fprintf (stderr, "ins/search\t%.4f\n",
306            (double) nelts / (double) table->searches);
307   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
308            exp_len, approx_sqrt (exp_len2 - exp2_len));
309   fprintf (stderr, "longest entry\t%lu\n",
310            (unsigned long) longest);
311 #undef SCALE
312 #undef LABEL
313 }
314
315 /* Return the approximate positive square root of a number N.  This is for
316    statistical reports, not code generation.  */
317 static double
318 approx_sqrt (double x)
319 {
320   double s, d;
321
322   if (x < 0)
323     abort ();
324   if (x == 0)
325     return 0;
326
327   s = x;
328   do
329     {
330       d = (s * s - x) / (2 * s);
331       s -= d;
332     }
333   while (d > .0001);
334   return s;
335 }