OSDN Git Service

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