]>
Commit | Line | Data |
---|---|---|
2a967f3d | 1 | /* Hash tables. |
83ffe9cd | 2 | Copyright (C) 2000-2023 Free Software Foundation, Inc. |
2a967f3d NB |
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 | |
748086b7 | 6 | Free Software Foundation; either version 3, or (at your option) any |
2a967f3d NB |
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 | |
748086b7 JJ |
15 | along with this program; see the file COPYING3. If not see |
16 | <http://www.gnu.org/licenses/>. | |
2a967f3d NB |
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" | |
4f4e53dd | 24 | #include "symtab.h" |
2a967f3d NB |
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 | |
dae4174e | 30 | existing entry with a potential new one. */ |
2a967f3d | 31 | |
7bb3fbbb | 32 | static unsigned int calc_hash (const unsigned char *, size_t); |
0823efed | 33 | static void ht_expand (cpp_hash_table *); |
a2f7be91 | 34 | static double approx_sqrt (double); |
2a967f3d | 35 | |
dae4174e TT |
36 | /* A deleted entry. */ |
37 | #define DELETED ((hashnode) -1) | |
38 | ||
2a967f3d NB |
39 | /* Calculate the hash of the string STR of length LEN. */ |
40 | ||
41 | static unsigned int | |
7bb3fbbb | 42 | calc_hash (const unsigned char *str, size_t len) |
2a967f3d | 43 | { |
7bb3fbbb | 44 | size_t n = len; |
2a967f3d | 45 | unsigned int r = 0; |
2a967f3d NB |
46 | |
47 | while (n--) | |
c6e83800 | 48 | r = HT_HASHSTEP (r, *str++); |
2a967f3d | 49 | |
c6e83800 | 50 | return HT_HASHFINISH (r, len); |
2a967f3d NB |
51 | } |
52 | ||
53 | /* Initialize an identifier hashtable. */ | |
54 | ||
0823efed | 55 | cpp_hash_table * |
1d088dee | 56 | ht_create (unsigned int order) |
2a967f3d NB |
57 | { |
58 | unsigned int nslots = 1 << order; | |
0823efed | 59 | cpp_hash_table *table; |
2a967f3d | 60 | |
0823efed | 61 | table = XCNEW (cpp_hash_table); |
2a967f3d NB |
62 | |
63 | /* Strings need no alignment. */ | |
19a9ba64 | 64 | obstack_specify_allocation (&table->stack, 0, 0, xmalloc, free); |
43839642 | 65 | |
2a967f3d NB |
66 | obstack_alignment_mask (&table->stack) = 0; |
67 | ||
c3f829c1 | 68 | table->entries = XCNEWVEC (hashnode, nslots); |
b453c95f | 69 | table->entries_owned = true; |
2a967f3d NB |
70 | table->nslots = nslots; |
71 | return table; | |
72 | } | |
73 | ||
bef985f3 NB |
74 | /* Frees all memory associated with a hash table. */ |
75 | ||
76 | void | |
0823efed | 77 | ht_destroy (cpp_hash_table *table) |
bef985f3 NB |
78 | { |
79 | obstack_free (&table->stack, NULL); | |
b453c95f GK |
80 | if (table->entries_owned) |
81 | free (table->entries); | |
bef985f3 NB |
82 | free (table); |
83 | } | |
84 | ||
2a967f3d | 85 | /* Returns the hash entry for the a STR of length LEN. If that string |
dae4174e | 86 | already exists in the table, returns the existing entry. If the |
2a967f3d NB |
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 | |
dae4174e | 89 | string is allocated. */ |
2a967f3d | 90 | hashnode |
0823efed | 91 | ht_lookup (cpp_hash_table *table, const unsigned char *str, size_t len, |
1d088dee | 92 | enum ht_lookup_option insert) |
2a967f3d | 93 | { |
c6e83800 ZW |
94 | return ht_lookup_with_hash (table, str, len, calc_hash (str, len), |
95 | insert); | |
96 | } | |
97 | ||
98 | hashnode | |
0823efed | 99 | ht_lookup_with_hash (cpp_hash_table *table, const unsigned char *str, |
c6e83800 ZW |
100 | size_t len, unsigned int hash, |
101 | enum ht_lookup_option insert) | |
102 | { | |
2a967f3d NB |
103 | unsigned int hash2; |
104 | unsigned int index; | |
dae4174e | 105 | unsigned int deleted_index = table->nslots; |
2a967f3d NB |
106 | size_t sizemask; |
107 | hashnode node; | |
108 | ||
109 | sizemask = table->nslots - 1; | |
110 | index = hash & sizemask; | |
2a967f3d NB |
111 | table->searches++; |
112 | ||
7bb3fbbb | 113 | node = table->entries[index]; |
dae4174e | 114 | |
7bb3fbbb | 115 | if (node != NULL) |
2a967f3d | 116 | { |
dae4174e TT |
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; | |
2a967f3d | 123 | |
7bb3fbbb RS |
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 | ||
dae4174e | 136 | if (node == DELETED) |
7bb3fbbb | 137 | { |
dae4174e TT |
138 | if (deleted_index != table->nslots) |
139 | deleted_index = index; | |
7bb3fbbb | 140 | } |
dae4174e TT |
141 | else if (node->hash_value == hash |
142 | && HT_LEN (node) == (unsigned int) len | |
143 | && !memcmp (HT_STR (node), str, len)) | |
144 | return node; | |
7bb3fbbb | 145 | } |
2a967f3d NB |
146 | } |
147 | ||
148 | if (insert == HT_NO_INSERT) | |
149 | return NULL; | |
150 | ||
dae4174e TT |
151 | /* We prefer to overwrite the first deleted slot we saw. */ |
152 | if (deleted_index != table->nslots) | |
153 | index = deleted_index; | |
154 | ||
2a967f3d NB |
155 | node = (*table->alloc_node) (table); |
156 | table->entries[index] = node; | |
157 | ||
7bb3fbbb | 158 | HT_LEN (node) = (unsigned int) len; |
5e0c54e5 | 159 | node->hash_value = hash; |
dae4174e TT |
160 | |
161 | if (table->alloc_subobject) | |
162 | { | |
f1bf410c | 163 | char *chars = (char *) table->alloc_subobject (len + 1); |
dae4174e TT |
164 | memcpy (chars, str, len); |
165 | chars[len] = '\0'; | |
166 | HT_STR (node) = (const unsigned char *) chars; | |
167 | } | |
2a967f3d | 168 | else |
dae4174e TT |
169 | HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack, |
170 | str, len); | |
2a967f3d NB |
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 | |
0823efed | 182 | ht_expand (cpp_hash_table *table) |
2a967f3d NB |
183 | { |
184 | hashnode *nentries, *p, *limit; | |
185 | unsigned int size, sizemask; | |
186 | ||
187 | size = table->nslots * 2; | |
c3f829c1 | 188 | nentries = XCNEWVEC (hashnode, size); |
2a967f3d NB |
189 | sizemask = size - 1; |
190 | ||
191 | p = table->entries; | |
192 | limit = p + table->nslots; | |
193 | do | |
dae4174e | 194 | if (*p && *p != DELETED) |
2a967f3d NB |
195 | { |
196 | unsigned int index, hash, hash2; | |
197 | ||
5e0c54e5 | 198 | hash = (*p)->hash_value; |
2a967f3d NB |
199 | index = hash & sizemask; |
200 | ||
4ae2e3e9 | 201 | if (nentries[index]) |
2a967f3d | 202 | { |
4ae2e3e9 RS |
203 | hash2 = ((hash * 17) & sizemask) | 1; |
204 | do | |
2a967f3d | 205 | { |
4ae2e3e9 | 206 | index = (index + hash2) & sizemask; |
2a967f3d | 207 | } |
4ae2e3e9 | 208 | while (nentries[index]); |
2a967f3d | 209 | } |
4ae2e3e9 | 210 | nentries[index] = *p; |
2a967f3d NB |
211 | } |
212 | while (++p < limit); | |
213 | ||
b453c95f GK |
214 | if (table->entries_owned) |
215 | free (table->entries); | |
216 | table->entries_owned = true; | |
2a967f3d NB |
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 | |
0823efed | 224 | ht_forall (cpp_hash_table *table, ht_cb cb, const void *v) |
2a967f3d NB |
225 | { |
226 | hashnode *p, *limit; | |
227 | ||
228 | p = table->entries; | |
229 | limit = p + table->nslots; | |
230 | do | |
dae4174e | 231 | if (*p && *p != DELETED) |
2a967f3d NB |
232 | { |
233 | if ((*cb) (table->pfile, *p, v) == 0) | |
234 | break; | |
235 | } | |
236 | while (++p < limit); | |
237 | } | |
238 | ||
dae4174e TT |
239 | /* Like ht_forall, but a nonzero return from the callback means that |
240 | the entry should be removed from the table. */ | |
241 | void | |
0823efed | 242 | ht_purge (cpp_hash_table *table, ht_cb cb, const void *v) |
dae4174e TT |
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 | ||
b453c95f GK |
257 | /* Restore the hash table. */ |
258 | void | |
0823efed | 259 | ht_load (cpp_hash_table *ht, hashnode *entries, |
b453c95f GK |
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 | ||
2a967f3d NB |
271 | /* Dump allocation statistics to stderr. */ |
272 | ||
273 | void | |
0823efed | 274 | ht_dump_statistics (cpp_hash_table *table) |
2a967f3d NB |
275 | { |
276 | size_t nelts, nids, overhead, headers; | |
dae4174e | 277 | size_t total_bytes, longest, deleted = 0; |
0fd9e8dd | 278 | double sum_of_squares, exp_len, exp_len2, exp2_len; |
2a967f3d NB |
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 | |
dae4174e TT |
292 | if (*p == DELETED) |
293 | ++deleted; | |
294 | else if (*p) | |
2a967f3d NB |
295 | { |
296 | size_t n = HT_LEN (*p); | |
297 | ||
298 | total_bytes += n; | |
0fd9e8dd | 299 | sum_of_squares += (double) n * n; |
2a967f3d NB |
300 | if (n > longest) |
301 | longest = n; | |
302 | nids++; | |
303 | } | |
304 | while (++p < limit); | |
1d088dee | 305 | |
2a967f3d | 306 | nelts = table->nelements; |
2a967f3d NB |
307 | headers = table->nslots * sizeof (hashnode); |
308 | ||
60448173 | 309 | fprintf (stderr, "\nString pool\n%-32s%lu\n", "entries:", |
2a967f3d | 310 | (unsigned long) nelts); |
60448173 | 311 | fprintf (stderr, "%-32s%lu (%.2f%%)\n", "identifiers:", |
2a967f3d | 312 | (unsigned long) nids, nids * 100.0 / nelts); |
60448173 | 313 | fprintf (stderr, "%-32s%lu\n", "slots:", |
2a967f3d | 314 | (unsigned long) table->nslots); |
60448173 | 315 | fprintf (stderr, "%-32s%lu\n", "deleted:", |
dae4174e | 316 | (unsigned long) deleted); |
46aeb07f ML |
317 | |
318 | if (table->alloc_subobject) | |
60448173 | 319 | fprintf (stderr, "%-32s%lu%c\n", "GGC bytes:", |
46aeb07f ML |
320 | SCALE (total_bytes), LABEL (total_bytes)); |
321 | else | |
322 | { | |
323 | overhead = obstack_memory_used (&table->stack) - total_bytes; | |
60448173 ML |
324 | fprintf (stderr, "%-32s%lu%c (%lu%c overhead)\n", |
325 | "obstack bytes:", | |
037903cb ML |
326 | SCALE (total_bytes), LABEL (total_bytes), |
327 | SCALE (overhead), LABEL (overhead)); | |
46aeb07f | 328 | } |
60448173 | 329 | fprintf (stderr, "%-32s%lu%c\n", "table size:", |
2a967f3d NB |
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 | ||
60448173 | 336 | fprintf (stderr, "%-32s%.4f\n", "coll/search:", |
2a967f3d | 337 | (double) table->collisions / (double) table->searches); |
60448173 | 338 | fprintf (stderr, "%-32s%.4f\n", "ins/search:", |
2a967f3d | 339 | (double) nelts / (double) table->searches); |
60448173 ML |
340 | fprintf (stderr, "%-32s%.2f bytes (+/- %.2f)\n", |
341 | "avg. entry:", | |
2a967f3d | 342 | exp_len, approx_sqrt (exp_len2 - exp2_len)); |
60448173 | 343 | fprintf (stderr, "%-32s%lu\n", "longest entry:", |
2a967f3d NB |
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. */ | |
a2f7be91 | 351 | static double |
1d088dee | 352 | approx_sqrt (double x) |
2a967f3d NB |
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 | } |