Implement SD-6: SG10 Feature Test Recommendations
[gcc.git] / libcpp / symtab.c
1 /* Hash tables.
2 Copyright (C) 2000-2014 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 3, 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; see the file COPYING3. If not see
16 <http://www.gnu.org/licenses/>.
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 (cpp_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 cpp_hash_table *
56 ht_create (unsigned int order)
57 {
58 unsigned int nslots = 1 << order;
59 cpp_hash_table *table;
60
61 table = XCNEW (cpp_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 (cpp_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 (cpp_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 (cpp_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 = (char *) 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 (cpp_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 (cpp_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 (cpp_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 (cpp_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 (cpp_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 }