1 /* Hash tables.
2 Copyright (C) 2000-2019 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
calc_hash(const unsigned char * str,size_t len)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 *
ht_create(unsigned int order)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_specify_allocation (&table->stack, 0, 0, xmalloc, 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
ht_destroy(cpp_hash_table * table)77 ht_destroy (cpp_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. If the
87 identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
88 returns NULL. Otherwise insert and returns a new entry. A new
89 string is allocated. */
90 hashnode
ht_lookup(cpp_hash_table * table,const unsigned char * str,size_t len,enum ht_lookup_option insert)91 ht_lookup (cpp_hash_table *table, const unsigned char *str, size_t len,
92 enum ht_lookup_option insert)
93 {
94 return ht_lookup_with_hash (table, str, len, calc_hash (str, len),
95 insert);
96 }
97
98 hashnode
ht_lookup_with_hash(cpp_hash_table * table,const unsigned char * str,size_t len,unsigned int hash,enum ht_lookup_option insert)99 ht_lookup_with_hash (cpp_hash_table *table, const unsigned char *str,
100 size_t len, unsigned int hash,
101 enum ht_lookup_option insert)
102 {
103 unsigned int hash2;
104 unsigned int index;
105 unsigned int deleted_index = table->nslots;
106 size_t sizemask;
107 hashnode node;
108
109 sizemask = table->nslots - 1;
110 index = hash & sizemask;
111 table->searches++;
112
113 node = table->entries[index];
114
115 if (node != NULL)
116 {
117 if (node == DELETED)
118 deleted_index = index;
119 else if (node->hash_value == hash
120 && HT_LEN (node) == (unsigned int) len
121 && !memcmp (HT_STR (node), str, len))
122 return node;
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 == DELETED)
137 {
138 if (deleted_index != table->nslots)
139 deleted_index = index;
140 }
141 else if (node->hash_value == hash
142 && HT_LEN (node) == (unsigned int) len
143 && !memcmp (HT_STR (node), str, len))
144 return node;
145 }
146 }
147
148 if (insert == HT_NO_INSERT)
149 return NULL;
150
151 /* We prefer to overwrite the first deleted slot we saw. */
152 if (deleted_index != table->nslots)
153 index = deleted_index;
154
155 node = (*table->alloc_node) (table);
156 table->entries[index] = node;
157
158 HT_LEN (node) = (unsigned int) len;
159 node->hash_value = hash;
160
161 if (table->alloc_subobject)
162 {
163 char *chars = (char *) table->alloc_subobject (len + 1);
164 memcpy (chars, str, len);
165 chars[len] = '\0';
166 HT_STR (node) = (const unsigned char *) chars;
167 }
168 else
169 HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack,
170 str, len);
171
172 if (++table->nelements * 4 >= table->nslots * 3)
173 /* Must expand the string table. */
174 ht_expand (table);
175
176 return node;
177 }
178
179 /* Double the size of a hash table, re-hashing existing entries. */
180
181 static void
ht_expand(cpp_hash_table * table)182 ht_expand (cpp_hash_table *table)
183 {
184 hashnode *nentries, *p, *limit;
185 unsigned int size, sizemask;
186
187 size = table->nslots * 2;
188 nentries = XCNEWVEC (hashnode, size);
189 sizemask = size - 1;
190
191 p = table->entries;
192 limit = p + table->nslots;
193 do
194 if (*p && *p != DELETED)
195 {
196 unsigned int index, hash, hash2;
197
198 hash = (*p)->hash_value;
199 index = hash & sizemask;
200
201 if (nentries[index])
202 {
203 hash2 = ((hash * 17) & sizemask) | 1;
204 do
205 {
206 index = (index + hash2) & sizemask;
207 }
208 while (nentries[index]);
209 }
210 nentries[index] = *p;
211 }
212 while (++p < limit);
213
214 if (table->entries_owned)
215 free (table->entries);
216 table->entries_owned = true;
217 table->entries = nentries;
218 table->nslots = size;
219 }
220
221 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
222 the node, and V. */
223 void
ht_forall(cpp_hash_table * table,ht_cb cb,const void * v)224 ht_forall (cpp_hash_table *table, ht_cb cb, const void *v)
225 {
226 hashnode *p, *limit;
227
228 p = table->entries;
229 limit = p + table->nslots;
230 do
231 if (*p && *p != DELETED)
232 {
233 if ((*cb) (table->pfile, *p, v) == 0)
234 break;
235 }
236 while (++p < limit);
237 }
238
239 /* Like ht_forall, but a nonzero return from the callback means that
240 the entry should be removed from the table. */
241 void
ht_purge(cpp_hash_table * table,ht_cb cb,const void * v)242 ht_purge (cpp_hash_table *table, ht_cb cb, const void *v)
243 {
244 hashnode *p, *limit;
245
246 p = table->entries;
247 limit = p + table->nslots;
248 do
249 if (*p && *p != DELETED)
250 {
251 if ((*cb) (table->pfile, *p, v))
252 *p = DELETED;
253 }
254 while (++p < limit);
255 }
256
257 /* Restore the hash table. */
258 void
ht_load(cpp_hash_table * ht,hashnode * entries,unsigned int nslots,unsigned int nelements,bool own)259 ht_load (cpp_hash_table *ht, hashnode *entries,
260 unsigned int nslots, unsigned int nelements,
261 bool own)
262 {
263 if (ht->entries_owned)
264 free (ht->entries);
265 ht->entries = entries;
266 ht->nslots = nslots;
267 ht->nelements = nelements;
268 ht->entries_owned = own;
269 }
270
271 /* Dump allocation statistics to stderr. */
272
273 void
ht_dump_statistics(cpp_hash_table * table)274 ht_dump_statistics (cpp_hash_table *table)
275 {
276 size_t nelts, nids, overhead, headers;
277 size_t total_bytes, longest, deleted = 0;
278 double sum_of_squares, exp_len, exp_len2, exp2_len;
279 hashnode *p, *limit;
280
281 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
282 ? (x) \
283 : ((x) < 1024*1024*10 \
284 ? (x) / 1024 \
285 : (x) / (1024*1024))))
286 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
287
288 total_bytes = longest = sum_of_squares = nids = 0;
289 p = table->entries;
290 limit = p + table->nslots;
291 do
292 if (*p == DELETED)
293 ++deleted;
294 else if (*p)
295 {
296 size_t n = HT_LEN (*p);
297
298 total_bytes += n;
299 sum_of_squares += (double) n * n;
300 if (n > longest)
301 longest = n;
302 nids++;
303 }
304 while (++p < limit);
305
306 nelts = table->nelements;
307 headers = table->nslots * sizeof (hashnode);
308
309 fprintf (stderr, "\nString pool\n%-32s%lu\n", "entries:",
310 (unsigned long) nelts);
311 fprintf (stderr, "%-32s%lu (%.2f%%)\n", "identifiers:",
312 (unsigned long) nids, nids * 100.0 / nelts);
313 fprintf (stderr, "%-32s%lu\n", "slots:",
314 (unsigned long) table->nslots);
315 fprintf (stderr, "%-32s%lu\n", "deleted:",
316 (unsigned long) deleted);
317
318 if (table->alloc_subobject)
319 fprintf (stderr, "%-32s%lu%c\n", "GGC bytes:",
320 SCALE (total_bytes), LABEL (total_bytes));
321 else
322 {
323 overhead = obstack_memory_used (&table->stack) - total_bytes;
324 fprintf (stderr, "%-32s%lu%c (%lu%c overhead)\n",
325 "obstack bytes:",
326 SCALE (total_bytes), LABEL (total_bytes),
327 SCALE (overhead), LABEL (overhead));
328 }
329 fprintf (stderr, "%-32s%lu%c\n", "table size:",
330 SCALE (headers), LABEL (headers));
331
332 exp_len = (double)total_bytes / (double)nelts;
333 exp2_len = exp_len * exp_len;
334 exp_len2 = (double) sum_of_squares / (double) nelts;
335
336 fprintf (stderr, "%-32s%.4f\n", "coll/search:",
337 (double) table->collisions / (double) table->searches);
338 fprintf (stderr, "%-32s%.4f\n", "ins/search:",
339 (double) nelts / (double) table->searches);
340 fprintf (stderr, "%-32s%.2f bytes (+/- %.2f)\n",
341 "avg. entry:",
342 exp_len, approx_sqrt (exp_len2 - exp2_len));
343 fprintf (stderr, "%-32s%lu\n", "longest entry:",
344 (unsigned long) longest);
345 #undef SCALE
346 #undef LABEL
347 }
348
349 /* Return the approximate positive square root of a number N. This is for
350 statistical reports, not code generation. */
351 static double
approx_sqrt(double x)352 approx_sqrt (double x)
353 {
354 double s, d;
355
356 if (x < 0)
357 abort ();
358 if (x == 0)
359 return 0;
360
361 s = x;
362 do
363 {
364 d = (s * s - x) / (2 * s);
365 s -= d;
366 }
367 while (d > .0001);
368 return s;
369 }
370