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