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