Commit | Line | Data |
---|---|---|
54d22525 | 1 | /* hash.c -- gas hash table code |
f7e42eb4 | 2 | Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999, |
4bdd3565 | 3 | 2000, 2001, 2002, 2003, 2005 |
252b5132 RH |
4 | Free Software Foundation, Inc. |
5 | ||
6 | This file is part of GAS, the GNU Assembler. | |
7 | ||
8 | GAS is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 2, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GAS is distributed in the hope that it will be useful, | |
14 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
16 | GNU General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
54d22525 ILT |
19 | along with GAS; see the file COPYING. If not, write to the Free |
20 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
21 | 02111-1307, USA. */ | |
22 | ||
23 | /* This version of the hash table code is a wholescale replacement of | |
24 | the old hash table code, which was fairly bad. This is based on | |
25 | the hash table code in BFD, but optimized slightly for the | |
436d9e46 | 26 | assembler. The assembler does not need to derive structures that |
54d22525 ILT |
27 | are stored in the hash table. Instead, it always stores a pointer. |
28 | The assembler uses the hash table mostly to store symbols, and we | |
29 | don't need to confuse the symbol structure with a hash table | |
30 | structure. */ | |
252b5132 RH |
31 | |
32 | #include "as.h" | |
3882b010 | 33 | #include "safe-ctype.h" |
54d22525 | 34 | #include "obstack.h" |
252b5132 | 35 | |
54d22525 | 36 | /* An entry in a hash table. */ |
252b5132 | 37 | |
b041f888 | 38 | struct hash_entry { |
54d22525 ILT |
39 | /* Next entry for this hash code. */ |
40 | struct hash_entry *next; | |
41 | /* String being hashed. */ | |
42 | const char *string; | |
43 | /* Hash code. This is the full hash code, not the index into the | |
44 | table. */ | |
45 | unsigned long hash; | |
46 | /* Pointer being stored in the hash table. */ | |
47 | PTR data; | |
252b5132 RH |
48 | }; |
49 | ||
54d22525 ILT |
50 | /* A hash table. */ |
51 | ||
b041f888 | 52 | struct hash_control { |
54d22525 ILT |
53 | /* The hash array. */ |
54 | struct hash_entry **table; | |
55 | /* The number of slots in the hash table. */ | |
56 | unsigned int size; | |
57 | /* An obstack for this hash table. */ | |
58 | struct obstack memory; | |
59 | ||
60 | #ifdef HASH_STATISTICS | |
61 | /* Statistics. */ | |
62 | unsigned long lookups; | |
63 | unsigned long hash_compares; | |
64 | unsigned long string_compares; | |
65 | unsigned long insertions; | |
66 | unsigned long replacements; | |
67 | unsigned long deletions; | |
68 | #endif /* HASH_STATISTICS */ | |
252b5132 | 69 | }; |
54d22525 | 70 | |
4bdd3565 NC |
71 | /* The default number of entries to use when creating a hash table. |
72 | Note this value can be reduced to 4051 by using the command line | |
73 | switch --reduce-memory-overheads, or set to other values by using | |
74 | the --hash-size=<NUMBER> switch. */ | |
75 | ||
f7a568ea | 76 | static unsigned long gas_hash_table_size = 65537; |
4bdd3565 NC |
77 | |
78 | void | |
f7a568ea | 79 | set_gas_hash_table_size (unsigned long size) |
4bdd3565 NC |
80 | { |
81 | gas_hash_table_size = size; | |
82 | } | |
83 | ||
84 | /* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size(). */ | |
f7a568ea | 85 | static unsigned long |
4bdd3565 NC |
86 | get_gas_hash_table_size (void) |
87 | { | |
88 | /* Extend this prime list if you want more granularity of hash table size. */ | |
f7a568ea | 89 | static const unsigned long hash_size_primes[] = |
4bdd3565 NC |
90 | { |
91 | 1021, 4051, 8599, 16699, 65537 | |
92 | }; | |
93 | unsigned int index; | |
94 | ||
95 | /* Work out the best prime number near the hash_size. | |
96 | FIXME: This could be a more sophisticated algorithm, | |
97 | but is it really worth implementing it ? */ | |
98 | for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index) | |
99 | if (gas_hash_table_size <= hash_size_primes[index]) | |
100 | break; | |
101 | ||
102 | return hash_size_primes[index]; | |
103 | } | |
104 | ||
54d22525 ILT |
105 | /* Create a hash table. This return a control block. */ |
106 | ||
252b5132 | 107 | struct hash_control * |
b1f1fa96 | 108 | hash_new (void) |
252b5132 | 109 | { |
f7a568ea NC |
110 | unsigned long size; |
111 | unsigned long alloc; | |
54d22525 | 112 | struct hash_control *ret; |
54d22525 | 113 | |
4bdd3565 | 114 | size = get_gas_hash_table_size (); |
54d22525 | 115 | |
4bdd3565 | 116 | ret = xmalloc (sizeof *ret); |
54d22525 ILT |
117 | obstack_begin (&ret->memory, chunksize); |
118 | alloc = size * sizeof (struct hash_entry *); | |
4bdd3565 | 119 | ret->table = obstack_alloc (&ret->memory, alloc); |
54d22525 ILT |
120 | memset (ret->table, 0, alloc); |
121 | ret->size = size; | |
122 | ||
123 | #ifdef HASH_STATISTICS | |
124 | ret->lookups = 0; | |
125 | ret->hash_compares = 0; | |
126 | ret->string_compares = 0; | |
127 | ret->insertions = 0; | |
128 | ret->replacements = 0; | |
129 | ret->deletions = 0; | |
130 | #endif | |
131 | ||
8fc2faa7 | 132 | return ret; |
252b5132 RH |
133 | } |
134 | ||
54d22525 ILT |
135 | /* Delete a hash table, freeing all allocated memory. */ |
136 | ||
252b5132 | 137 | void |
b1f1fa96 | 138 | hash_die (struct hash_control *table) |
252b5132 | 139 | { |
54d22525 ILT |
140 | obstack_free (&table->memory, 0); |
141 | free (table); | |
252b5132 | 142 | } |
54d22525 ILT |
143 | |
144 | /* Look up a string in a hash table. This returns a pointer to the | |
145 | hash_entry, or NULL if the string is not in the table. If PLIST is | |
146 | not NULL, this sets *PLIST to point to the start of the list which | |
147 | would hold this hash entry. If PHASH is not NULL, this sets *PHASH | |
148 | to the hash code for KEY. | |
149 | ||
150 | Each time we look up a string, we move it to the start of the list | |
151 | for its hash code, to take advantage of referential locality. */ | |
152 | ||
b1f1fa96 KH |
153 | static struct hash_entry *hash_lookup (struct hash_control *, |
154 | const char *, | |
155 | struct hash_entry ***, | |
156 | unsigned long *); | |
54d22525 ILT |
157 | |
158 | static struct hash_entry * | |
b1f1fa96 KH |
159 | hash_lookup (struct hash_control *table, const char *key, |
160 | struct hash_entry ***plist, unsigned long *phash) | |
252b5132 | 161 | { |
54d22525 ILT |
162 | register unsigned long hash; |
163 | unsigned int len; | |
164 | register const unsigned char *s; | |
165 | register unsigned int c; | |
166 | unsigned int index; | |
167 | struct hash_entry **list; | |
168 | struct hash_entry *p; | |
169 | struct hash_entry *prev; | |
170 | ||
171 | #ifdef HASH_STATISTICS | |
172 | ++table->lookups; | |
173 | #endif | |
252b5132 | 174 | |
54d22525 ILT |
175 | hash = 0; |
176 | len = 0; | |
177 | s = (const unsigned char *) key; | |
178 | while ((c = *s++) != '\0') | |
252b5132 | 179 | { |
54d22525 ILT |
180 | hash += c + (c << 17); |
181 | hash ^= hash >> 2; | |
182 | ++len; | |
252b5132 | 183 | } |
54d22525 ILT |
184 | hash += len + (len << 17); |
185 | hash ^= hash >> 2; | |
186 | ||
187 | if (phash != NULL) | |
188 | *phash = hash; | |
189 | ||
190 | index = hash % table->size; | |
191 | list = table->table + index; | |
252b5132 | 192 | |
54d22525 ILT |
193 | if (plist != NULL) |
194 | *plist = list; | |
195 | ||
196 | prev = NULL; | |
197 | for (p = *list; p != NULL; p = p->next) | |
252b5132 | 198 | { |
54d22525 ILT |
199 | #ifdef HASH_STATISTICS |
200 | ++table->hash_compares; | |
201 | #endif | |
202 | ||
203 | if (p->hash == hash) | |
252b5132 | 204 | { |
54d22525 ILT |
205 | #ifdef HASH_STATISTICS |
206 | ++table->string_compares; | |
207 | #endif | |
208 | ||
209 | if (strcmp (p->string, key) == 0) | |
210 | { | |
211 | if (prev != NULL) | |
212 | { | |
213 | prev->next = p->next; | |
214 | p->next = *list; | |
215 | *list = p; | |
216 | } | |
217 | ||
218 | return p; | |
219 | } | |
252b5132 | 220 | } |
252b5132 | 221 | |
54d22525 | 222 | prev = p; |
252b5132 | 223 | } |
54d22525 ILT |
224 | |
225 | return NULL; | |
252b5132 | 226 | } |
54d22525 ILT |
227 | |
228 | /* Insert an entry into a hash table. This returns NULL on success. | |
229 | On error, it returns a printable string indicating the error. It | |
230 | is considered to be an error if the entry already exists in the | |
231 | hash table. */ | |
232 | ||
233 | const char * | |
b1f1fa96 | 234 | hash_insert (struct hash_control *table, const char *key, PTR value) |
252b5132 | 235 | { |
54d22525 ILT |
236 | struct hash_entry *p; |
237 | struct hash_entry **list; | |
238 | unsigned long hash; | |
252b5132 | 239 | |
54d22525 ILT |
240 | p = hash_lookup (table, key, &list, &hash); |
241 | if (p != NULL) | |
242 | return "exists"; | |
243 | ||
244 | #ifdef HASH_STATISTICS | |
245 | ++table->insertions; | |
246 | #endif | |
247 | ||
8fc2faa7 | 248 | p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); |
54d22525 ILT |
249 | p->string = key; |
250 | p->hash = hash; | |
251 | p->data = value; | |
252 | ||
253 | p->next = *list; | |
254 | *list = p; | |
255 | ||
256 | return NULL; | |
252b5132 | 257 | } |
54d22525 ILT |
258 | |
259 | /* Insert or replace an entry in a hash table. This returns NULL on | |
260 | success. On error, it returns a printable string indicating the | |
261 | error. If an entry already exists, its value is replaced. */ | |
262 | ||
252b5132 | 263 | const char * |
b1f1fa96 | 264 | hash_jam (struct hash_control *table, const char *key, PTR value) |
252b5132 | 265 | { |
54d22525 ILT |
266 | struct hash_entry *p; |
267 | struct hash_entry **list; | |
268 | unsigned long hash; | |
252b5132 | 269 | |
54d22525 ILT |
270 | p = hash_lookup (table, key, &list, &hash); |
271 | if (p != NULL) | |
252b5132 | 272 | { |
54d22525 ILT |
273 | #ifdef HASH_STATISTICS |
274 | ++table->replacements; | |
275 | #endif | |
276 | ||
277 | p->data = value; | |
252b5132 | 278 | } |
54d22525 | 279 | else |
252b5132 | 280 | { |
54d22525 ILT |
281 | #ifdef HASH_STATISTICS |
282 | ++table->insertions; | |
283 | #endif | |
284 | ||
8fc2faa7 | 285 | p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); |
54d22525 ILT |
286 | p->string = key; |
287 | p->hash = hash; | |
288 | p->data = value; | |
289 | ||
290 | p->next = *list; | |
291 | *list = p; | |
252b5132 | 292 | } |
54d22525 ILT |
293 | |
294 | return NULL; | |
252b5132 RH |
295 | } |
296 | ||
54d22525 ILT |
297 | /* Find an entry in a hash table, returning its value. Returns NULL |
298 | if the entry is not found. */ | |
299 | ||
252b5132 | 300 | PTR |
b1f1fa96 | 301 | hash_find (struct hash_control *table, const char *key) |
252b5132 | 302 | { |
54d22525 | 303 | struct hash_entry *p; |
252b5132 | 304 | |
54d22525 ILT |
305 | p = hash_lookup (table, key, NULL, NULL); |
306 | if (p == NULL) | |
252b5132 | 307 | return NULL; |
54d22525 ILT |
308 | |
309 | return p->data; | |
252b5132 | 310 | } |
54d22525 | 311 | |
54d22525 ILT |
312 | /* Traverse a hash table. Call the function on every entry in the |
313 | hash table. */ | |
314 | ||
252b5132 | 315 | void |
b1f1fa96 KH |
316 | hash_traverse (struct hash_control *table, |
317 | void (*pfn) (const char *key, PTR value)) | |
252b5132 | 318 | { |
54d22525 | 319 | unsigned int i; |
252b5132 | 320 | |
54d22525 ILT |
321 | for (i = 0; i < table->size; ++i) |
322 | { | |
323 | struct hash_entry *p; | |
252b5132 | 324 | |
54d22525 ILT |
325 | for (p = table->table[i]; p != NULL; p = p->next) |
326 | (*pfn) (p->string, p->data); | |
327 | } | |
328 | } | |
252b5132 | 329 | |
54d22525 ILT |
330 | /* Print hash table statistics on the specified file. NAME is the |
331 | name of the hash table, used for printing a header. */ | |
252b5132 | 332 | |
54d22525 | 333 | void |
b1f1fa96 KH |
334 | hash_print_statistics (FILE *f ATTRIBUTE_UNUSED, |
335 | const char *name ATTRIBUTE_UNUSED, | |
336 | struct hash_control *table ATTRIBUTE_UNUSED) | |
54d22525 ILT |
337 | { |
338 | #ifdef HASH_STATISTICS | |
339 | unsigned int i; | |
340 | unsigned long total; | |
341 | unsigned long empty; | |
342 | ||
343 | fprintf (f, "%s hash statistics:\n", name); | |
344 | fprintf (f, "\t%lu lookups\n", table->lookups); | |
345 | fprintf (f, "\t%lu hash comparisons\n", table->hash_compares); | |
346 | fprintf (f, "\t%lu string comparisons\n", table->string_compares); | |
347 | fprintf (f, "\t%lu insertions\n", table->insertions); | |
348 | fprintf (f, "\t%lu replacements\n", table->replacements); | |
349 | fprintf (f, "\t%lu deletions\n", table->deletions); | |
350 | ||
351 | total = 0; | |
352 | empty = 0; | |
353 | for (i = 0; i < table->size; ++i) | |
354 | { | |
355 | struct hash_entry *p; | |
252b5132 | 356 | |
54d22525 ILT |
357 | if (table->table[i] == NULL) |
358 | ++empty; | |
359 | else | |
360 | { | |
361 | for (p = table->table[i]; p != NULL; p = p->next) | |
362 | ++total; | |
363 | } | |
364 | } | |
252b5132 | 365 | |
54d22525 ILT |
366 | fprintf (f, "\t%g average chain length\n", (double) total / table->size); |
367 | fprintf (f, "\t%lu empty slots\n", empty); | |
368 | #endif | |
252b5132 RH |
369 | } |
370 | \f | |
252b5132 RH |
371 | #ifdef TEST |
372 | ||
54d22525 ILT |
373 | /* This test program is left over from the old hash table code. */ |
374 | ||
8fc2faa7 KH |
375 | /* Number of hash tables to maintain (at once) in any testing. */ |
376 | #define TABLES (6) | |
377 | ||
378 | /* We can have 12 statistics. */ | |
379 | #define STATBUFSIZE (12) | |
380 | ||
381 | /* Display statistics here. */ | |
382 | int statbuf[STATBUFSIZE]; | |
383 | ||
384 | /* Human farts here. */ | |
385 | char answer[100]; | |
386 | ||
387 | /* We test many hash tables at once. */ | |
388 | char *hashtable[TABLES]; | |
252b5132 | 389 | |
47eebc20 | 390 | /* Points to current hash_control. */ |
8fc2faa7 | 391 | char *h; |
252b5132 RH |
392 | char **pp; |
393 | char *p; | |
394 | char *name; | |
395 | char *value; | |
396 | int size; | |
397 | int used; | |
398 | char command; | |
8fc2faa7 KH |
399 | |
400 | /* Number 0:TABLES-1 of current hashed symbol table. */ | |
401 | int number; | |
252b5132 | 402 | |
54d22525 | 403 | int |
252b5132 RH |
404 | main () |
405 | { | |
406 | void applicatee (); | |
407 | void destroy (); | |
408 | char *what (); | |
409 | int *ip; | |
410 | ||
411 | number = 0; | |
412 | h = 0; | |
413 | printf ("type h <RETURN> for help\n"); | |
414 | for (;;) | |
415 | { | |
416 | printf ("hash_test command: "); | |
417 | gets (answer); | |
418 | command = answer[0]; | |
3882b010 | 419 | command = TOLOWER (command); /* Ecch! */ |
252b5132 RH |
420 | switch (command) |
421 | { | |
422 | case '#': | |
423 | printf ("old hash table #=%d.\n", number); | |
424 | whattable (); | |
425 | break; | |
426 | case '?': | |
427 | for (pp = hashtable; pp < hashtable + TABLES; pp++) | |
428 | { | |
8fc2faa7 KH |
429 | printf ("address of hash table #%d control block is %xx\n", |
430 | pp - hashtable, *pp); | |
252b5132 RH |
431 | } |
432 | break; | |
433 | case 'a': | |
54d22525 | 434 | hash_traverse (h, applicatee); |
252b5132 RH |
435 | break; |
436 | case 'd': | |
54d22525 | 437 | hash_traverse (h, destroy); |
252b5132 RH |
438 | hash_die (h); |
439 | break; | |
440 | case 'f': | |
441 | p = hash_find (h, name = what ("symbol")); | |
442 | printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT"); | |
443 | break; | |
444 | case 'h': | |
445 | printf ("# show old, select new default hash table number\n"); | |
446 | printf ("? display all hashtable control block addresses\n"); | |
447 | printf ("a apply a simple display-er to each symbol in table\n"); | |
448 | printf ("d die: destroy hashtable\n"); | |
449 | printf ("f find value of nominated symbol\n"); | |
450 | printf ("h this help\n"); | |
451 | printf ("i insert value into symbol\n"); | |
452 | printf ("j jam value into symbol\n"); | |
453 | printf ("n new hashtable\n"); | |
454 | printf ("r replace a value with another\n"); | |
455 | printf ("s say what %% of table is used\n"); | |
456 | printf ("q exit this program\n"); | |
457 | printf ("x delete a symbol from table, report its value\n"); | |
458 | break; | |
459 | case 'i': | |
460 | p = hash_insert (h, name = what ("symbol"), value = what ("value")); | |
461 | if (p) | |
462 | { | |
463 | printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, | |
464 | p); | |
465 | } | |
466 | break; | |
467 | case 'j': | |
468 | p = hash_jam (h, name = what ("symbol"), value = what ("value")); | |
469 | if (p) | |
470 | { | |
471 | printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p); | |
472 | } | |
473 | break; | |
474 | case 'n': | |
475 | h = hashtable[number] = (char *) hash_new (); | |
476 | break; | |
477 | case 'q': | |
478 | exit (EXIT_SUCCESS); | |
479 | case 'r': | |
480 | p = hash_replace (h, name = what ("symbol"), value = what ("value")); | |
481 | printf ("old value was \"%s\"\n", p ? p : "{}"); | |
482 | break; | |
483 | case 's': | |
484 | hash_say (h, statbuf, STATBUFSIZE); | |
485 | for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++) | |
486 | { | |
487 | printf ("%d ", *ip); | |
488 | } | |
489 | printf ("\n"); | |
490 | break; | |
491 | case 'x': | |
492 | p = hash_delete (h, name = what ("symbol")); | |
493 | printf ("old value was \"%s\"\n", p ? p : "{}"); | |
494 | break; | |
495 | default: | |
496 | printf ("I can't understand command \"%c\"\n", command); | |
497 | break; | |
498 | } | |
499 | } | |
500 | } | |
501 | ||
502 | char * | |
503 | what (description) | |
504 | char *description; | |
505 | { | |
252b5132 RH |
506 | printf (" %s : ", description); |
507 | gets (answer); | |
a2c36061 | 508 | return xstrdup (answer); |
252b5132 RH |
509 | } |
510 | ||
511 | void | |
512 | destroy (string, value) | |
513 | char *string; | |
514 | char *value; | |
515 | { | |
516 | free (string); | |
517 | free (value); | |
518 | } | |
519 | ||
252b5132 RH |
520 | void |
521 | applicatee (string, value) | |
522 | char *string; | |
523 | char *value; | |
524 | { | |
525 | printf ("%.20s-%.20s\n", string, value); | |
526 | } | |
527 | ||
8fc2faa7 KH |
528 | /* Determine number: what hash table to use. |
529 | Also determine h: points to hash_control. */ | |
530 | ||
54d22525 | 531 | void |
8fc2faa7 | 532 | whattable () |
252b5132 | 533 | { |
252b5132 RH |
534 | for (;;) |
535 | { | |
536 | printf (" what hash table (%d:%d) ? ", 0, TABLES - 1); | |
537 | gets (answer); | |
538 | sscanf (answer, "%d", &number); | |
539 | if (number >= 0 && number < TABLES) | |
540 | { | |
541 | h = hashtable[number]; | |
542 | if (!h) | |
543 | { | |
544 | printf ("warning: current hash-table-#%d. has no hash-control\n", number); | |
545 | } | |
546 | return; | |
547 | } | |
548 | else | |
549 | { | |
550 | printf ("invalid hash table number: %d\n", number); | |
551 | } | |
552 | } | |
553 | } | |
554 | ||
8fc2faa7 | 555 | #endif /* TEST */ |