]>
Commit | Line | Data |
---|---|---|
2a967f3d | 1 | /* Hash tables. |
dae4174e | 2 | Copyright (C) 2000, 2001, 2003, 2004, 2008 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 | |
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 | |
200031d1 | 16 | Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
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); |
1d088dee | 33 | static void ht_expand (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 | ||
55 | hash_table * | |
1d088dee | 56 | ht_create (unsigned int order) |
2a967f3d NB |
57 | { |
58 | unsigned int nslots = 1 << order; | |
59 | hash_table *table; | |
60 | ||
c3f829c1 | 61 | table = XCNEW (hash_table); |
2a967f3d NB |
62 | |
63 | /* Strings need no alignment. */ | |
43839642 ZW |
64 | _obstack_begin (&table->stack, 0, 0, |
65 | (void *(*) (long)) xmalloc, | |
66 | (void (*) (void *)) free); | |
67 | ||
2a967f3d NB |
68 | obstack_alignment_mask (&table->stack) = 0; |
69 | ||
c3f829c1 | 70 | table->entries = XCNEWVEC (hashnode, nslots); |
b453c95f | 71 | table->entries_owned = true; |
2a967f3d NB |
72 | table->nslots = nslots; |
73 | return table; | |
74 | } | |
75 | ||
bef985f3 NB |
76 | /* Frees all memory associated with a hash table. */ |
77 | ||
78 | void | |
1d088dee | 79 | ht_destroy (hash_table *table) |
bef985f3 NB |
80 | { |
81 | obstack_free (&table->stack, NULL); | |
b453c95f GK |
82 | if (table->entries_owned) |
83 | free (table->entries); | |
bef985f3 NB |
84 | free (table); |
85 | } | |
86 | ||
2a967f3d | 87 | /* Returns the hash entry for the a STR of length LEN. If that string |
dae4174e | 88 | already exists in the table, returns the existing entry. If the |
2a967f3d NB |
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 | |
dae4174e | 91 | string is allocated. */ |
2a967f3d | 92 | hashnode |
7bb3fbbb | 93 | ht_lookup (hash_table *table, const unsigned char *str, size_t len, |
1d088dee | 94 | enum ht_lookup_option insert) |
2a967f3d | 95 | { |
c6e83800 ZW |
96 | return ht_lookup_with_hash (table, str, len, calc_hash (str, len), |
97 | insert); | |
98 | } | |
99 | ||
100 | hashnode | |
101 | ht_lookup_with_hash (hash_table *table, const unsigned char *str, | |
102 | size_t len, unsigned int hash, | |
103 | enum ht_lookup_option insert) | |
104 | { | |
2a967f3d NB |
105 | unsigned int hash2; |
106 | unsigned int index; | |
dae4174e | 107 | unsigned int deleted_index = table->nslots; |
2a967f3d NB |
108 | size_t sizemask; |
109 | hashnode node; | |
110 | ||
111 | sizemask = table->nslots - 1; | |
112 | index = hash & sizemask; | |
2a967f3d NB |
113 | table->searches++; |
114 | ||
7bb3fbbb | 115 | node = table->entries[index]; |
dae4174e | 116 | |
7bb3fbbb | 117 | if (node != NULL) |
2a967f3d | 118 | { |
dae4174e TT |
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; | |
2a967f3d | 125 | |
7bb3fbbb RS |
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 | ||
dae4174e | 138 | if (node == DELETED) |
7bb3fbbb | 139 | { |
dae4174e TT |
140 | if (deleted_index != table->nslots) |
141 | deleted_index = index; | |
7bb3fbbb | 142 | } |
dae4174e TT |
143 | else if (node->hash_value == hash |
144 | && HT_LEN (node) == (unsigned int) len | |
145 | && !memcmp (HT_STR (node), str, len)) | |
146 | return node; | |
7bb3fbbb | 147 | } |
2a967f3d NB |
148 | } |
149 | ||
150 | if (insert == HT_NO_INSERT) | |
151 | return NULL; | |
152 | ||
dae4174e TT |
153 | /* We prefer to overwrite the first deleted slot we saw. */ |
154 | if (deleted_index != table->nslots) | |
155 | index = deleted_index; | |
156 | ||
2a967f3d NB |
157 | node = (*table->alloc_node) (table); |
158 | table->entries[index] = node; | |
159 | ||
7bb3fbbb | 160 | HT_LEN (node) = (unsigned int) len; |
5e0c54e5 | 161 | node->hash_value = hash; |
dae4174e TT |
162 | |
163 | if (table->alloc_subobject) | |
164 | { | |
165 | char *chars = table->alloc_subobject (len + 1); | |
166 | memcpy (chars, str, len); | |
167 | chars[len] = '\0'; | |
168 | HT_STR (node) = (const unsigned char *) chars; | |
169 | } | |
2a967f3d | 170 | else |
dae4174e TT |
171 | HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack, |
172 | str, len); | |
2a967f3d NB |
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 | |
1d088dee | 184 | ht_expand (hash_table *table) |
2a967f3d NB |
185 | { |
186 | hashnode *nentries, *p, *limit; | |
187 | unsigned int size, sizemask; | |
188 | ||
189 | size = table->nslots * 2; | |
c3f829c1 | 190 | nentries = XCNEWVEC (hashnode, size); |
2a967f3d NB |
191 | sizemask = size - 1; |
192 | ||
193 | p = table->entries; | |
194 | limit = p + table->nslots; | |
195 | do | |
dae4174e | 196 | if (*p && *p != DELETED) |
2a967f3d NB |
197 | { |
198 | unsigned int index, hash, hash2; | |
199 | ||
5e0c54e5 | 200 | hash = (*p)->hash_value; |
2a967f3d NB |
201 | index = hash & sizemask; |
202 | ||
4ae2e3e9 | 203 | if (nentries[index]) |
2a967f3d | 204 | { |
4ae2e3e9 RS |
205 | hash2 = ((hash * 17) & sizemask) | 1; |
206 | do | |
2a967f3d | 207 | { |
4ae2e3e9 | 208 | index = (index + hash2) & sizemask; |
2a967f3d | 209 | } |
4ae2e3e9 | 210 | while (nentries[index]); |
2a967f3d | 211 | } |
4ae2e3e9 | 212 | nentries[index] = *p; |
2a967f3d NB |
213 | } |
214 | while (++p < limit); | |
215 | ||
b453c95f GK |
216 | if (table->entries_owned) |
217 | free (table->entries); | |
218 | table->entries_owned = true; | |
2a967f3d NB |
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 | |
1d088dee | 226 | ht_forall (hash_table *table, ht_cb cb, const void *v) |
2a967f3d NB |
227 | { |
228 | hashnode *p, *limit; | |
229 | ||
230 | p = table->entries; | |
231 | limit = p + table->nslots; | |
232 | do | |
dae4174e | 233 | if (*p && *p != DELETED) |
2a967f3d NB |
234 | { |
235 | if ((*cb) (table->pfile, *p, v) == 0) | |
236 | break; | |
237 | } | |
238 | while (++p < limit); | |
239 | } | |
240 | ||
dae4174e TT |
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 (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 | ||
b453c95f GK |
259 | /* Restore the hash table. */ |
260 | void | |
261 | ht_load (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 | ||
2a967f3d NB |
273 | /* Dump allocation statistics to stderr. */ |
274 | ||
275 | void | |
1d088dee | 276 | ht_dump_statistics (hash_table *table) |
2a967f3d NB |
277 | { |
278 | size_t nelts, nids, overhead, headers; | |
dae4174e | 279 | size_t total_bytes, longest, deleted = 0; |
0fd9e8dd | 280 | double sum_of_squares, exp_len, exp_len2, exp2_len; |
2a967f3d NB |
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 | |
dae4174e TT |
294 | if (*p == DELETED) |
295 | ++deleted; | |
296 | else if (*p) | |
2a967f3d NB |
297 | { |
298 | size_t n = HT_LEN (*p); | |
299 | ||
300 | total_bytes += n; | |
0fd9e8dd | 301 | sum_of_squares += (double) n * n; |
2a967f3d NB |
302 | if (n > longest) |
303 | longest = n; | |
304 | nids++; | |
305 | } | |
306 | while (++p < limit); | |
1d088dee | 307 | |
2a967f3d NB |
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); | |
dae4174e TT |
318 | fprintf (stderr, "deleted\t\t%lu\n", |
319 | (unsigned long) deleted); | |
2a967f3d NB |
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. */ | |
a2f7be91 | 344 | static double |
1d088dee | 345 | approx_sqrt (double x) |
2a967f3d NB |
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 | } |