]>
Commit | Line | Data |
---|---|---|
2a967f3d | 1 | /* Hash tables. |
b453c95f | 2 | Copyright (C) 2000, 2001, 2003, 2004 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 | |
30 | existing entry with a potential new one. Also, the ability to | |
31 | delete members from the table has been removed. */ | |
32 | ||
7bb3fbbb | 33 | static unsigned int calc_hash (const unsigned char *, size_t); |
1d088dee | 34 | static void ht_expand (hash_table *); |
a2f7be91 | 35 | static double approx_sqrt (double); |
2a967f3d | 36 | |
2a967f3d NB |
37 | /* Calculate the hash of the string STR of length LEN. */ |
38 | ||
39 | static unsigned int | |
7bb3fbbb | 40 | calc_hash (const unsigned char *str, size_t len) |
2a967f3d | 41 | { |
7bb3fbbb | 42 | size_t n = len; |
2a967f3d | 43 | unsigned int r = 0; |
2a967f3d NB |
44 | |
45 | while (n--) | |
c6e83800 | 46 | r = HT_HASHSTEP (r, *str++); |
2a967f3d | 47 | |
c6e83800 | 48 | return HT_HASHFINISH (r, len); |
2a967f3d NB |
49 | } |
50 | ||
51 | /* Initialize an identifier hashtable. */ | |
52 | ||
53 | hash_table * | |
1d088dee | 54 | ht_create (unsigned int order) |
2a967f3d NB |
55 | { |
56 | unsigned int nslots = 1 << order; | |
57 | hash_table *table; | |
58 | ||
c3f829c1 | 59 | table = XCNEW (hash_table); |
2a967f3d NB |
60 | |
61 | /* Strings need no alignment. */ | |
43839642 ZW |
62 | _obstack_begin (&table->stack, 0, 0, |
63 | (void *(*) (long)) xmalloc, | |
64 | (void (*) (void *)) free); | |
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 | |
1d088dee | 77 | ht_destroy (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 NB |
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, and, if | |
87 | INSERT is CPP_ALLOCED, frees the last obstack object. If the | |
88 | identifier hasn't been seen before, and INSERT is CPP_NO_INSERT, | |
89 | returns NULL. Otherwise insert and returns a new entry. A new | |
90 | string is alloced if INSERT is CPP_ALLOC, otherwise INSERT is | |
91 | CPP_ALLOCED and the item is assumed to be at the top of the | |
92 | obstack. */ | |
93 | hashnode | |
7bb3fbbb | 94 | ht_lookup (hash_table *table, const unsigned char *str, size_t len, |
1d088dee | 95 | enum ht_lookup_option insert) |
2a967f3d | 96 | { |
c6e83800 ZW |
97 | return ht_lookup_with_hash (table, str, len, calc_hash (str, len), |
98 | insert); | |
99 | } | |
100 | ||
101 | hashnode | |
102 | ht_lookup_with_hash (hash_table *table, const unsigned char *str, | |
103 | size_t len, unsigned int hash, | |
104 | enum ht_lookup_option insert) | |
105 | { | |
2a967f3d NB |
106 | unsigned int hash2; |
107 | unsigned int index; | |
108 | size_t sizemask; | |
109 | hashnode node; | |
110 | ||
111 | sizemask = table->nslots - 1; | |
112 | index = hash & sizemask; | |
2a967f3d NB |
113 | table->searches++; |
114 | ||
7bb3fbbb RS |
115 | node = table->entries[index]; |
116 | ||
117 | if (node != NULL) | |
2a967f3d | 118 | { |
7bb3fbbb RS |
119 | if (node->hash_value == hash |
120 | && HT_LEN (node) == (unsigned int) len | |
121 | && !memcmp (HT_STR (node), str, len)) | |
2a967f3d NB |
122 | { |
123 | if (insert == HT_ALLOCED) | |
124 | /* The string we search for was placed at the end of the | |
125 | obstack. Release it. */ | |
fad205ff | 126 | obstack_free (&table->stack, (void *) str); |
2a967f3d NB |
127 | return node; |
128 | } | |
129 | ||
7bb3fbbb RS |
130 | /* hash2 must be odd, so we're guaranteed to visit every possible |
131 | location in the table during rehashing. */ | |
132 | hash2 = ((hash * 17) & sizemask) | 1; | |
133 | ||
134 | for (;;) | |
135 | { | |
136 | table->collisions++; | |
137 | index = (index + hash2) & sizemask; | |
138 | node = table->entries[index]; | |
139 | if (node == NULL) | |
140 | break; | |
141 | ||
142 | if (node->hash_value == hash | |
143 | && HT_LEN (node) == (unsigned int) len | |
144 | && !memcmp (HT_STR (node), str, len)) | |
145 | { | |
146 | if (insert == HT_ALLOCED) | |
147 | /* The string we search for was placed at the end of the | |
148 | obstack. Release it. */ | |
149 | obstack_free (&table->stack, (void *) str); | |
150 | return node; | |
151 | } | |
152 | } | |
2a967f3d NB |
153 | } |
154 | ||
155 | if (insert == HT_NO_INSERT) | |
156 | return NULL; | |
157 | ||
158 | node = (*table->alloc_node) (table); | |
159 | table->entries[index] = node; | |
160 | ||
7bb3fbbb | 161 | HT_LEN (node) = (unsigned int) len; |
5e0c54e5 | 162 | node->hash_value = hash; |
2a967f3d | 163 | if (insert == HT_ALLOC) |
c3f829c1 GDR |
164 | HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack, |
165 | str, len); | |
2a967f3d NB |
166 | else |
167 | HT_STR (node) = str; | |
168 | ||
169 | if (++table->nelements * 4 >= table->nslots * 3) | |
170 | /* Must expand the string table. */ | |
171 | ht_expand (table); | |
172 | ||
173 | return node; | |
174 | } | |
175 | ||
176 | /* Double the size of a hash table, re-hashing existing entries. */ | |
177 | ||
178 | static void | |
1d088dee | 179 | ht_expand (hash_table *table) |
2a967f3d NB |
180 | { |
181 | hashnode *nentries, *p, *limit; | |
182 | unsigned int size, sizemask; | |
183 | ||
184 | size = table->nslots * 2; | |
c3f829c1 | 185 | nentries = XCNEWVEC (hashnode, size); |
2a967f3d NB |
186 | sizemask = size - 1; |
187 | ||
188 | p = table->entries; | |
189 | limit = p + table->nslots; | |
190 | do | |
191 | if (*p) | |
192 | { | |
193 | unsigned int index, hash, hash2; | |
194 | ||
5e0c54e5 | 195 | hash = (*p)->hash_value; |
2a967f3d NB |
196 | index = hash & sizemask; |
197 | ||
4ae2e3e9 | 198 | if (nentries[index]) |
2a967f3d | 199 | { |
4ae2e3e9 RS |
200 | hash2 = ((hash * 17) & sizemask) | 1; |
201 | do | |
2a967f3d | 202 | { |
4ae2e3e9 | 203 | index = (index + hash2) & sizemask; |
2a967f3d | 204 | } |
4ae2e3e9 | 205 | while (nentries[index]); |
2a967f3d | 206 | } |
4ae2e3e9 | 207 | nentries[index] = *p; |
2a967f3d NB |
208 | } |
209 | while (++p < limit); | |
210 | ||
b453c95f GK |
211 | if (table->entries_owned) |
212 | free (table->entries); | |
213 | table->entries_owned = true; | |
2a967f3d NB |
214 | table->entries = nentries; |
215 | table->nslots = size; | |
216 | } | |
217 | ||
218 | /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE, | |
219 | the node, and V. */ | |
220 | void | |
1d088dee | 221 | ht_forall (hash_table *table, ht_cb cb, const void *v) |
2a967f3d NB |
222 | { |
223 | hashnode *p, *limit; | |
224 | ||
225 | p = table->entries; | |
226 | limit = p + table->nslots; | |
227 | do | |
228 | if (*p) | |
229 | { | |
230 | if ((*cb) (table->pfile, *p, v) == 0) | |
231 | break; | |
232 | } | |
233 | while (++p < limit); | |
234 | } | |
235 | ||
b453c95f GK |
236 | /* Restore the hash table. */ |
237 | void | |
238 | ht_load (hash_table *ht, hashnode *entries, | |
239 | unsigned int nslots, unsigned int nelements, | |
240 | bool own) | |
241 | { | |
242 | if (ht->entries_owned) | |
243 | free (ht->entries); | |
244 | ht->entries = entries; | |
245 | ht->nslots = nslots; | |
246 | ht->nelements = nelements; | |
247 | ht->entries_owned = own; | |
248 | } | |
249 | ||
2a967f3d NB |
250 | /* Dump allocation statistics to stderr. */ |
251 | ||
252 | void | |
1d088dee | 253 | ht_dump_statistics (hash_table *table) |
2a967f3d NB |
254 | { |
255 | size_t nelts, nids, overhead, headers; | |
0fd9e8dd SB |
256 | size_t total_bytes, longest; |
257 | double sum_of_squares, exp_len, exp_len2, exp2_len; | |
2a967f3d NB |
258 | hashnode *p, *limit; |
259 | ||
260 | #define SCALE(x) ((unsigned long) ((x) < 1024*10 \ | |
261 | ? (x) \ | |
262 | : ((x) < 1024*1024*10 \ | |
263 | ? (x) / 1024 \ | |
264 | : (x) / (1024*1024)))) | |
265 | #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M')) | |
266 | ||
267 | total_bytes = longest = sum_of_squares = nids = 0; | |
268 | p = table->entries; | |
269 | limit = p + table->nslots; | |
270 | do | |
271 | if (*p) | |
272 | { | |
273 | size_t n = HT_LEN (*p); | |
274 | ||
275 | total_bytes += n; | |
0fd9e8dd | 276 | sum_of_squares += (double) n * n; |
2a967f3d NB |
277 | if (n > longest) |
278 | longest = n; | |
279 | nids++; | |
280 | } | |
281 | while (++p < limit); | |
1d088dee | 282 | |
2a967f3d NB |
283 | nelts = table->nelements; |
284 | overhead = obstack_memory_used (&table->stack) - total_bytes; | |
285 | headers = table->nslots * sizeof (hashnode); | |
286 | ||
287 | fprintf (stderr, "\nString pool\nentries\t\t%lu\n", | |
288 | (unsigned long) nelts); | |
289 | fprintf (stderr, "identifiers\t%lu (%.2f%%)\n", | |
290 | (unsigned long) nids, nids * 100.0 / nelts); | |
291 | fprintf (stderr, "slots\t\t%lu\n", | |
292 | (unsigned long) table->nslots); | |
293 | fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n", | |
294 | SCALE (total_bytes), LABEL (total_bytes), | |
295 | SCALE (overhead), LABEL (overhead)); | |
296 | fprintf (stderr, "table size\t%lu%c\n", | |
297 | SCALE (headers), LABEL (headers)); | |
298 | ||
299 | exp_len = (double)total_bytes / (double)nelts; | |
300 | exp2_len = exp_len * exp_len; | |
301 | exp_len2 = (double) sum_of_squares / (double) nelts; | |
302 | ||
303 | fprintf (stderr, "coll/search\t%.4f\n", | |
304 | (double) table->collisions / (double) table->searches); | |
305 | fprintf (stderr, "ins/search\t%.4f\n", | |
306 | (double) nelts / (double) table->searches); | |
307 | fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n", | |
308 | exp_len, approx_sqrt (exp_len2 - exp2_len)); | |
309 | fprintf (stderr, "longest entry\t%lu\n", | |
310 | (unsigned long) longest); | |
311 | #undef SCALE | |
312 | #undef LABEL | |
313 | } | |
314 | ||
315 | /* Return the approximate positive square root of a number N. This is for | |
316 | statistical reports, not code generation. */ | |
a2f7be91 | 317 | static double |
1d088dee | 318 | approx_sqrt (double x) |
2a967f3d NB |
319 | { |
320 | double s, d; | |
321 | ||
322 | if (x < 0) | |
323 | abort (); | |
324 | if (x == 0) | |
325 | return 0; | |
326 | ||
327 | s = x; | |
328 | do | |
329 | { | |
330 | d = (s * s - x) / (2 * s); | |
331 | s -= d; | |
332 | } | |
333 | while (d > .0001); | |
334 | return s; | |
335 | } |