OSDN Git Service

ChangeLog:
[pf3gnuchains/gcc-fork.git] / libcpp / symtab.c
1 /* Hash tables.
2    Copyright (C) 2000, 2001, 2003 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 #define HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
45
46   while (n--)
47     r = HASHSTEP (r, *str++);
48
49   return r + len;
50 #undef HASHSTEP
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 = xcalloc (1, sizeof (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 = xcalloc (nslots, sizeof (hashnode));
71   table->nslots = nslots;
72   return table;
73 }
74
75 /* Frees all memory associated with a hash table.  */
76
77 void
78 ht_destroy (hash_table *table)
79 {
80   obstack_free (&table->stack, NULL);
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   unsigned int hash = calc_hash (str, len);
98   unsigned int hash2;
99   unsigned int index;
100   size_t sizemask;
101   hashnode node;
102
103   sizemask = table->nslots - 1;
104   index = hash & sizemask;
105   table->searches++;
106
107   node = table->entries[index];
108  
109   if (node != NULL)
110     {
111       if (node->hash_value == hash
112           && HT_LEN (node) == (unsigned int) len
113           && !memcmp (HT_STR (node), str, len))
114         {
115           if (insert == HT_ALLOCED)
116             /* The string we search for was placed at the end of the
117                obstack.  Release it.  */
118             obstack_free (&table->stack, (void *) str);
119           return node;
120         }
121
122       /* hash2 must be odd, so we're guaranteed to visit every possible
123          location in the table during rehashing.  */
124       hash2 = ((hash * 17) & sizemask) | 1;
125
126       for (;;)
127         {
128           table->collisions++;
129           index = (index + hash2) & sizemask;
130           node = table->entries[index];
131           if (node == NULL)
132             break;
133
134           if (node->hash_value == hash
135               && HT_LEN (node) == (unsigned int) len
136               && !memcmp (HT_STR (node), str, len))
137             {
138               if (insert == HT_ALLOCED)
139               /* The string we search for was placed at the end of the
140                  obstack.  Release it.  */
141                 obstack_free (&table->stack, (void *) str);
142               return node;
143             }
144         }
145     }
146
147   if (insert == HT_NO_INSERT)
148     return NULL;
149
150   node = (*table->alloc_node) (table);
151   table->entries[index] = node;
152
153   HT_LEN (node) = (unsigned int) len;
154   node->hash_value = hash;
155   if (insert == HT_ALLOC)
156     HT_STR (node) = obstack_copy0 (&table->stack, str, len);
157   else
158     HT_STR (node) = str;
159
160   if (++table->nelements * 4 >= table->nslots * 3)
161     /* Must expand the string table.  */
162     ht_expand (table);
163
164   return node;
165 }
166
167 /* Double the size of a hash table, re-hashing existing entries.  */
168
169 static void
170 ht_expand (hash_table *table)
171 {
172   hashnode *nentries, *p, *limit;
173   unsigned int size, sizemask;
174
175   size = table->nslots * 2;
176   nentries = xcalloc (size, sizeof (hashnode));
177   sizemask = size - 1;
178
179   p = table->entries;
180   limit = p + table->nslots;
181   do
182     if (*p)
183       {
184         unsigned int index, hash, hash2;
185
186         hash = (*p)->hash_value;
187         index = hash & sizemask;
188
189         if (nentries[index])
190           {
191             hash2 = ((hash * 17) & sizemask) | 1;
192             do
193               {
194                 index = (index + hash2) & sizemask;
195               }
196             while (nentries[index]);
197           }
198         nentries[index] = *p;
199       }
200   while (++p < limit);
201
202   free (table->entries);
203   table->entries = nentries;
204   table->nslots = size;
205 }
206
207 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
208    the node, and V.  */
209 void
210 ht_forall (hash_table *table, ht_cb cb, const void *v)
211 {
212   hashnode *p, *limit;
213
214   p = table->entries;
215   limit = p + table->nslots;
216   do
217     if (*p)
218       {
219         if ((*cb) (table->pfile, *p, v) == 0)
220           break;
221       }
222   while (++p < limit);
223 }
224
225 /* Dump allocation statistics to stderr.  */
226
227 void
228 ht_dump_statistics (hash_table *table)
229 {
230   size_t nelts, nids, overhead, headers;
231   size_t total_bytes, longest, sum_of_squares;
232   double exp_len, exp_len2, exp2_len;
233   hashnode *p, *limit;
234
235 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
236                   ? (x) \
237                   : ((x) < 1024*1024*10 \
238                      ? (x) / 1024 \
239                      : (x) / (1024*1024))))
240 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
241
242   total_bytes = longest = sum_of_squares = nids = 0;
243   p = table->entries;
244   limit = p + table->nslots;
245   do
246     if (*p)
247       {
248         size_t n = HT_LEN (*p);
249
250         total_bytes += n;
251         sum_of_squares += n * n;
252         if (n > longest)
253           longest = n;
254         nids++;
255       }
256   while (++p < limit);
257
258   nelts = table->nelements;
259   overhead = obstack_memory_used (&table->stack) - total_bytes;
260   headers = table->nslots * sizeof (hashnode);
261
262   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
263            (unsigned long) nelts);
264   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
265            (unsigned long) nids, nids * 100.0 / nelts);
266   fprintf (stderr, "slots\t\t%lu\n",
267            (unsigned long) table->nslots);
268   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
269            SCALE (total_bytes), LABEL (total_bytes),
270            SCALE (overhead), LABEL (overhead));
271   fprintf (stderr, "table size\t%lu%c\n",
272            SCALE (headers), LABEL (headers));
273
274   exp_len = (double)total_bytes / (double)nelts;
275   exp2_len = exp_len * exp_len;
276   exp_len2 = (double) sum_of_squares / (double) nelts;
277
278   fprintf (stderr, "coll/search\t%.4f\n",
279            (double) table->collisions / (double) table->searches);
280   fprintf (stderr, "ins/search\t%.4f\n",
281            (double) nelts / (double) table->searches);
282   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
283            exp_len, approx_sqrt (exp_len2 - exp2_len));
284   fprintf (stderr, "longest entry\t%lu\n",
285            (unsigned long) longest);
286 #undef SCALE
287 #undef LABEL
288 }
289
290 /* Return the approximate positive square root of a number N.  This is for
291    statistical reports, not code generation.  */
292 static double
293 approx_sqrt (double x)
294 {
295   double s, d;
296
297   if (x < 0)
298     abort ();
299   if (x == 0)
300     return 0;
301
302   s = x;
303   do
304     {
305       d = (s * s - x) / (2 * s);
306       s -= d;
307     }
308   while (d > .0001);
309   return s;
310 }