]>
Commit | Line | Data |
---|---|---|
2a967f3d | 1 | /* Hash tables. |
1d088dee | 2 | Copyright (C) 2000, 2001, 2003 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 | |
16 | Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. | |
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 "hashtable.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. 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; |
a078edf8 | 44 | #define HASHSTEP(r, c) ((r) * 67 + ((c) - 113)); |
2a967f3d NB |
45 | |
46 | while (n--) | |
47 | r = HASHSTEP (r, *str++); | |
48 | ||
49 | return r + len; | |
50 | #undef HASHSTEP | |
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 | ||
29da5c92 | 61 | table = xcalloc (1, sizeof (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 | ||
703ad42b | 70 | table->entries = xcalloc (nslots, sizeof (hashnode)); |
2a967f3d NB |
71 | table->nslots = nslots; |
72 | return table; | |
73 | } | |
74 | ||
bef985f3 NB |
75 | /* Frees all memory associated with a hash table. */ |
76 | ||
77 | void | |
1d088dee | 78 | ht_destroy (hash_table *table) |
bef985f3 NB |
79 | { |
80 | obstack_free (&table->stack, NULL); | |
81 | free (table->entries); | |
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 NB |
96 | { |
97 | unsigned int hash = calc_hash (str, len); | |
98 | unsigned int hash2; | |
99 | unsigned int index; | |
100 | size_t sizemask; | |
101 | hashnode node; | |
102 | ||
103 | sizemask = table->nslots - 1; | |
104 | index = hash & sizemask; | |
2a967f3d NB |
105 | table->searches++; |
106 | ||
7bb3fbbb RS |
107 | node = table->entries[index]; |
108 | ||
109 | if (node != NULL) | |
2a967f3d | 110 | { |
7bb3fbbb RS |
111 | if (node->hash_value == hash |
112 | && HT_LEN (node) == (unsigned int) len | |
113 | && !memcmp (HT_STR (node), str, len)) | |
2a967f3d NB |
114 | { |
115 | if (insert == HT_ALLOCED) | |
116 | /* The string we search for was placed at the end of the | |
117 | obstack. Release it. */ | |
fad205ff | 118 | obstack_free (&table->stack, (void *) str); |
2a967f3d NB |
119 | return node; |
120 | } | |
121 | ||
7bb3fbbb RS |
122 | /* hash2 must be odd, so we're guaranteed to visit every possible |
123 | location in the table during rehashing. */ | |
124 | hash2 = ((hash * 17) & sizemask) | 1; | |
125 | ||
126 | for (;;) | |
127 | { | |
128 | table->collisions++; | |
129 | index = (index + hash2) & sizemask; | |
130 | node = table->entries[index]; | |
131 | if (node == NULL) | |
132 | break; | |
133 | ||
134 | if (node->hash_value == hash | |
135 | && HT_LEN (node) == (unsigned int) len | |
136 | && !memcmp (HT_STR (node), str, len)) | |
137 | { | |
138 | if (insert == HT_ALLOCED) | |
139 | /* The string we search for was placed at the end of the | |
140 | obstack. Release it. */ | |
141 | obstack_free (&table->stack, (void *) str); | |
142 | return node; | |
143 | } | |
144 | } | |
2a967f3d NB |
145 | } |
146 | ||
147 | if (insert == HT_NO_INSERT) | |
148 | return NULL; | |
149 | ||
150 | node = (*table->alloc_node) (table); | |
151 | table->entries[index] = node; | |
152 | ||
7bb3fbbb | 153 | HT_LEN (node) = (unsigned int) len; |
5e0c54e5 | 154 | node->hash_value = hash; |
2a967f3d | 155 | if (insert == HT_ALLOC) |
2c3fcba6 | 156 | HT_STR (node) = obstack_copy0 (&table->stack, str, len); |
2a967f3d NB |
157 | else |
158 | HT_STR (node) = str; | |
159 | ||
160 | if (++table->nelements * 4 >= table->nslots * 3) | |
161 | /* Must expand the string table. */ | |
162 | ht_expand (table); | |
163 | ||
164 | return node; | |
165 | } | |
166 | ||
167 | /* Double the size of a hash table, re-hashing existing entries. */ | |
168 | ||
169 | static void | |
1d088dee | 170 | ht_expand (hash_table *table) |
2a967f3d NB |
171 | { |
172 | hashnode *nentries, *p, *limit; | |
173 | unsigned int size, sizemask; | |
174 | ||
175 | size = table->nslots * 2; | |
703ad42b | 176 | nentries = xcalloc (size, sizeof (hashnode)); |
2a967f3d NB |
177 | sizemask = size - 1; |
178 | ||
179 | p = table->entries; | |
180 | limit = p + table->nslots; | |
181 | do | |
182 | if (*p) | |
183 | { | |
184 | unsigned int index, hash, hash2; | |
185 | ||
5e0c54e5 | 186 | hash = (*p)->hash_value; |
2a967f3d NB |
187 | index = hash & sizemask; |
188 | ||
4ae2e3e9 | 189 | if (nentries[index]) |
2a967f3d | 190 | { |
4ae2e3e9 RS |
191 | hash2 = ((hash * 17) & sizemask) | 1; |
192 | do | |
2a967f3d | 193 | { |
4ae2e3e9 | 194 | index = (index + hash2) & sizemask; |
2a967f3d | 195 | } |
4ae2e3e9 | 196 | while (nentries[index]); |
2a967f3d | 197 | } |
4ae2e3e9 | 198 | nentries[index] = *p; |
2a967f3d NB |
199 | } |
200 | while (++p < limit); | |
201 | ||
202 | free (table->entries); | |
203 | table->entries = nentries; | |
204 | table->nslots = size; | |
205 | } | |
206 | ||
207 | /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE, | |
208 | the node, and V. */ | |
209 | void | |
1d088dee | 210 | ht_forall (hash_table *table, ht_cb cb, const void *v) |
2a967f3d NB |
211 | { |
212 | hashnode *p, *limit; | |
213 | ||
214 | p = table->entries; | |
215 | limit = p + table->nslots; | |
216 | do | |
217 | if (*p) | |
218 | { | |
219 | if ((*cb) (table->pfile, *p, v) == 0) | |
220 | break; | |
221 | } | |
222 | while (++p < limit); | |
223 | } | |
224 | ||
225 | /* Dump allocation statistics to stderr. */ | |
226 | ||
227 | void | |
1d088dee | 228 | ht_dump_statistics (hash_table *table) |
2a967f3d NB |
229 | { |
230 | size_t nelts, nids, overhead, headers; | |
231 | size_t total_bytes, longest, sum_of_squares; | |
232 | double exp_len, exp_len2, exp2_len; | |
233 | hashnode *p, *limit; | |
234 | ||
235 | #define SCALE(x) ((unsigned long) ((x) < 1024*10 \ | |
236 | ? (x) \ | |
237 | : ((x) < 1024*1024*10 \ | |
238 | ? (x) / 1024 \ | |
239 | : (x) / (1024*1024)))) | |
240 | #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M')) | |
241 | ||
242 | total_bytes = longest = sum_of_squares = nids = 0; | |
243 | p = table->entries; | |
244 | limit = p + table->nslots; | |
245 | do | |
246 | if (*p) | |
247 | { | |
248 | size_t n = HT_LEN (*p); | |
249 | ||
250 | total_bytes += n; | |
251 | sum_of_squares += n * n; | |
252 | if (n > longest) | |
253 | longest = n; | |
254 | nids++; | |
255 | } | |
256 | while (++p < limit); | |
1d088dee | 257 | |
2a967f3d NB |
258 | nelts = table->nelements; |
259 | overhead = obstack_memory_used (&table->stack) - total_bytes; | |
260 | headers = table->nslots * sizeof (hashnode); | |
261 | ||
262 | fprintf (stderr, "\nString pool\nentries\t\t%lu\n", | |
263 | (unsigned long) nelts); | |
264 | fprintf (stderr, "identifiers\t%lu (%.2f%%)\n", | |
265 | (unsigned long) nids, nids * 100.0 / nelts); | |
266 | fprintf (stderr, "slots\t\t%lu\n", | |
267 | (unsigned long) table->nslots); | |
268 | fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n", | |
269 | SCALE (total_bytes), LABEL (total_bytes), | |
270 | SCALE (overhead), LABEL (overhead)); | |
271 | fprintf (stderr, "table size\t%lu%c\n", | |
272 | SCALE (headers), LABEL (headers)); | |
273 | ||
274 | exp_len = (double)total_bytes / (double)nelts; | |
275 | exp2_len = exp_len * exp_len; | |
276 | exp_len2 = (double) sum_of_squares / (double) nelts; | |
277 | ||
278 | fprintf (stderr, "coll/search\t%.4f\n", | |
279 | (double) table->collisions / (double) table->searches); | |
280 | fprintf (stderr, "ins/search\t%.4f\n", | |
281 | (double) nelts / (double) table->searches); | |
282 | fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n", | |
283 | exp_len, approx_sqrt (exp_len2 - exp2_len)); | |
284 | fprintf (stderr, "longest entry\t%lu\n", | |
285 | (unsigned long) longest); | |
286 | #undef SCALE | |
287 | #undef LABEL | |
288 | } | |
289 | ||
290 | /* Return the approximate positive square root of a number N. This is for | |
291 | statistical reports, not code generation. */ | |
a2f7be91 | 292 | static double |
1d088dee | 293 | approx_sqrt (double x) |
2a967f3d NB |
294 | { |
295 | double s, d; | |
296 | ||
297 | if (x < 0) | |
298 | abort (); | |
299 | if (x == 0) | |
300 | return 0; | |
301 | ||
302 | s = x; | |
303 | do | |
304 | { | |
305 | d = (s * s - x) / (2 * s); | |
306 | s -= d; | |
307 | } | |
308 | while (d > .0001); | |
309 | return s; | |
310 | } |