Commit | Line | Data |
---|---|---|
54d22525 | 1 | /* hash.c -- gas hash table code |
f7e42eb4 NC |
2 | Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999, |
3 | 2000 | |
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 | |
26 | asssembler. The assembler does not need to derive structures that | |
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" | |
54d22525 | 33 | #include "obstack.h" |
252b5132 | 34 | |
54d22525 | 35 | /* The default number of entries to use when creating a hash table. */ |
252b5132 | 36 | |
54d22525 | 37 | #define DEFAULT_SIZE (4051) |
252b5132 | 38 | |
54d22525 | 39 | /* An entry in a hash table. */ |
252b5132 | 40 | |
b041f888 | 41 | struct hash_entry { |
54d22525 ILT |
42 | /* Next entry for this hash code. */ |
43 | struct hash_entry *next; | |
44 | /* String being hashed. */ | |
45 | const char *string; | |
46 | /* Hash code. This is the full hash code, not the index into the | |
47 | table. */ | |
48 | unsigned long hash; | |
49 | /* Pointer being stored in the hash table. */ | |
50 | PTR data; | |
252b5132 RH |
51 | }; |
52 | ||
54d22525 ILT |
53 | /* A hash table. */ |
54 | ||
b041f888 | 55 | struct hash_control { |
54d22525 ILT |
56 | /* The hash array. */ |
57 | struct hash_entry **table; | |
58 | /* The number of slots in the hash table. */ | |
59 | unsigned int size; | |
60 | /* An obstack for this hash table. */ | |
61 | struct obstack memory; | |
62 | ||
63 | #ifdef HASH_STATISTICS | |
64 | /* Statistics. */ | |
65 | unsigned long lookups; | |
66 | unsigned long hash_compares; | |
67 | unsigned long string_compares; | |
68 | unsigned long insertions; | |
69 | unsigned long replacements; | |
70 | unsigned long deletions; | |
71 | #endif /* HASH_STATISTICS */ | |
252b5132 | 72 | }; |
54d22525 ILT |
73 | |
74 | /* Create a hash table. This return a control block. */ | |
75 | ||
252b5132 RH |
76 | struct hash_control * |
77 | hash_new () | |
78 | { | |
54d22525 ILT |
79 | unsigned int size; |
80 | struct hash_control *ret; | |
81 | unsigned int alloc; | |
82 | ||
83 | size = DEFAULT_SIZE; | |
84 | ||
85 | ret = (struct hash_control *) xmalloc (sizeof *ret); | |
86 | obstack_begin (&ret->memory, chunksize); | |
87 | alloc = size * sizeof (struct hash_entry *); | |
88 | ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc); | |
89 | memset (ret->table, 0, alloc); | |
90 | ret->size = size; | |
91 | ||
92 | #ifdef HASH_STATISTICS | |
93 | ret->lookups = 0; | |
94 | ret->hash_compares = 0; | |
95 | ret->string_compares = 0; | |
96 | ret->insertions = 0; | |
97 | ret->replacements = 0; | |
98 | ret->deletions = 0; | |
99 | #endif | |
100 | ||
8fc2faa7 | 101 | return ret; |
252b5132 RH |
102 | } |
103 | ||
54d22525 ILT |
104 | /* Delete a hash table, freeing all allocated memory. */ |
105 | ||
252b5132 | 106 | void |
54d22525 ILT |
107 | hash_die (table) |
108 | struct hash_control *table; | |
252b5132 | 109 | { |
54d22525 ILT |
110 | obstack_free (&table->memory, 0); |
111 | free (table); | |
252b5132 | 112 | } |
54d22525 ILT |
113 | |
114 | /* Look up a string in a hash table. This returns a pointer to the | |
115 | hash_entry, or NULL if the string is not in the table. If PLIST is | |
116 | not NULL, this sets *PLIST to point to the start of the list which | |
117 | would hold this hash entry. If PHASH is not NULL, this sets *PHASH | |
118 | to the hash code for KEY. | |
119 | ||
120 | Each time we look up a string, we move it to the start of the list | |
121 | for its hash code, to take advantage of referential locality. */ | |
122 | ||
123 | static struct hash_entry *hash_lookup PARAMS ((struct hash_control *, | |
124 | const char *, | |
125 | struct hash_entry ***, | |
126 | unsigned long *)); | |
127 | ||
128 | static struct hash_entry * | |
129 | hash_lookup (table, key, plist, phash) | |
130 | struct hash_control *table; | |
131 | const char *key; | |
132 | struct hash_entry ***plist; | |
133 | unsigned long *phash; | |
252b5132 | 134 | { |
54d22525 ILT |
135 | register unsigned long hash; |
136 | unsigned int len; | |
137 | register const unsigned char *s; | |
138 | register unsigned int c; | |
139 | unsigned int index; | |
140 | struct hash_entry **list; | |
141 | struct hash_entry *p; | |
142 | struct hash_entry *prev; | |
143 | ||
144 | #ifdef HASH_STATISTICS | |
145 | ++table->lookups; | |
146 | #endif | |
252b5132 | 147 | |
54d22525 ILT |
148 | hash = 0; |
149 | len = 0; | |
150 | s = (const unsigned char *) key; | |
151 | while ((c = *s++) != '\0') | |
252b5132 | 152 | { |
54d22525 ILT |
153 | hash += c + (c << 17); |
154 | hash ^= hash >> 2; | |
155 | ++len; | |
252b5132 | 156 | } |
54d22525 ILT |
157 | hash += len + (len << 17); |
158 | hash ^= hash >> 2; | |
159 | ||
160 | if (phash != NULL) | |
161 | *phash = hash; | |
162 | ||
163 | index = hash % table->size; | |
164 | list = table->table + index; | |
252b5132 | 165 | |
54d22525 ILT |
166 | if (plist != NULL) |
167 | *plist = list; | |
168 | ||
169 | prev = NULL; | |
170 | for (p = *list; p != NULL; p = p->next) | |
252b5132 | 171 | { |
54d22525 ILT |
172 | #ifdef HASH_STATISTICS |
173 | ++table->hash_compares; | |
174 | #endif | |
175 | ||
176 | if (p->hash == hash) | |
252b5132 | 177 | { |
54d22525 ILT |
178 | #ifdef HASH_STATISTICS |
179 | ++table->string_compares; | |
180 | #endif | |
181 | ||
182 | if (strcmp (p->string, key) == 0) | |
183 | { | |
184 | if (prev != NULL) | |
185 | { | |
186 | prev->next = p->next; | |
187 | p->next = *list; | |
188 | *list = p; | |
189 | } | |
190 | ||
191 | return p; | |
192 | } | |
252b5132 | 193 | } |
252b5132 | 194 | |
54d22525 | 195 | prev = p; |
252b5132 | 196 | } |
54d22525 ILT |
197 | |
198 | return NULL; | |
252b5132 | 199 | } |
54d22525 ILT |
200 | |
201 | /* Insert an entry into a hash table. This returns NULL on success. | |
202 | On error, it returns a printable string indicating the error. It | |
203 | is considered to be an error if the entry already exists in the | |
204 | hash table. */ | |
205 | ||
206 | const char * | |
207 | hash_insert (table, key, value) | |
208 | struct hash_control *table; | |
209 | const char *key; | |
252b5132 RH |
210 | PTR value; |
211 | { | |
54d22525 ILT |
212 | struct hash_entry *p; |
213 | struct hash_entry **list; | |
214 | unsigned long hash; | |
252b5132 | 215 | |
54d22525 ILT |
216 | p = hash_lookup (table, key, &list, &hash); |
217 | if (p != NULL) | |
218 | return "exists"; | |
219 | ||
220 | #ifdef HASH_STATISTICS | |
221 | ++table->insertions; | |
222 | #endif | |
223 | ||
8fc2faa7 | 224 | p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); |
54d22525 ILT |
225 | p->string = key; |
226 | p->hash = hash; | |
227 | p->data = value; | |
228 | ||
229 | p->next = *list; | |
230 | *list = p; | |
231 | ||
232 | return NULL; | |
252b5132 | 233 | } |
54d22525 ILT |
234 | |
235 | /* Insert or replace an entry in a hash table. This returns NULL on | |
236 | success. On error, it returns a printable string indicating the | |
237 | error. If an entry already exists, its value is replaced. */ | |
238 | ||
252b5132 | 239 | const char * |
54d22525 ILT |
240 | hash_jam (table, key, value) |
241 | struct hash_control *table; | |
242 | const char *key; | |
252b5132 RH |
243 | PTR value; |
244 | { | |
54d22525 ILT |
245 | struct hash_entry *p; |
246 | struct hash_entry **list; | |
247 | unsigned long hash; | |
252b5132 | 248 | |
54d22525 ILT |
249 | p = hash_lookup (table, key, &list, &hash); |
250 | if (p != NULL) | |
252b5132 | 251 | { |
54d22525 ILT |
252 | #ifdef HASH_STATISTICS |
253 | ++table->replacements; | |
254 | #endif | |
255 | ||
256 | p->data = value; | |
252b5132 | 257 | } |
54d22525 | 258 | else |
252b5132 | 259 | { |
54d22525 ILT |
260 | #ifdef HASH_STATISTICS |
261 | ++table->insertions; | |
262 | #endif | |
263 | ||
8fc2faa7 | 264 | p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); |
54d22525 ILT |
265 | p->string = key; |
266 | p->hash = hash; | |
267 | p->data = value; | |
268 | ||
269 | p->next = *list; | |
270 | *list = p; | |
252b5132 | 271 | } |
54d22525 ILT |
272 | |
273 | return NULL; | |
252b5132 RH |
274 | } |
275 | ||
54d22525 ILT |
276 | /* Replace an existing entry in a hash table. This returns the old |
277 | value stored for the entry. If the entry is not found in the hash | |
278 | table, this does nothing and returns NULL. */ | |
279 | ||
280 | PTR | |
281 | hash_replace (table, key, value) | |
282 | struct hash_control *table; | |
283 | const char *key; | |
284 | PTR value; | |
252b5132 | 285 | { |
54d22525 ILT |
286 | struct hash_entry *p; |
287 | PTR ret; | |
252b5132 | 288 | |
54d22525 ILT |
289 | p = hash_lookup (table, key, NULL, NULL); |
290 | if (p == NULL) | |
291 | return NULL; | |
292 | ||
293 | #ifdef HASH_STATISTICS | |
294 | ++table->replacements; | |
252b5132 RH |
295 | #endif |
296 | ||
54d22525 | 297 | ret = p->data; |
252b5132 | 298 | |
54d22525 | 299 | p->data = value; |
252b5132 | 300 | |
54d22525 | 301 | return ret; |
252b5132 | 302 | } |
54d22525 ILT |
303 | |
304 | /* Find an entry in a hash table, returning its value. Returns NULL | |
305 | if the entry is not found. */ | |
306 | ||
252b5132 | 307 | PTR |
54d22525 ILT |
308 | hash_find (table, key) |
309 | struct hash_control *table; | |
310 | const char *key; | |
252b5132 | 311 | { |
54d22525 | 312 | struct hash_entry *p; |
252b5132 | 313 | |
54d22525 ILT |
314 | p = hash_lookup (table, key, NULL, NULL); |
315 | if (p == NULL) | |
252b5132 | 316 | return NULL; |
54d22525 ILT |
317 | |
318 | return p->data; | |
252b5132 | 319 | } |
54d22525 ILT |
320 | |
321 | /* Delete an entry from a hash table. This returns the value stored | |
322 | for that entry, or NULL if there is no such entry. */ | |
323 | ||
324 | PTR | |
325 | hash_delete (table, key) | |
326 | struct hash_control *table; | |
327 | const char *key; | |
252b5132 | 328 | { |
54d22525 ILT |
329 | struct hash_entry *p; |
330 | struct hash_entry **list; | |
331 | ||
332 | p = hash_lookup (table, key, &list, NULL); | |
333 | if (p == NULL) | |
334 | return NULL; | |
335 | ||
336 | if (p != *list) | |
337 | abort (); | |
338 | ||
339 | #ifdef HASH_STATISTICS | |
340 | ++table->deletions; | |
252b5132 | 341 | #endif |
54d22525 ILT |
342 | |
343 | *list = p->next; | |
344 | ||
345 | /* Note that we never reclaim the memory for this entry. If gas | |
346 | ever starts deleting hash table entries in a big way, this will | |
347 | have to change. */ | |
348 | ||
349 | return p->data; | |
252b5132 | 350 | } |
54d22525 ILT |
351 | |
352 | /* Traverse a hash table. Call the function on every entry in the | |
353 | hash table. */ | |
354 | ||
252b5132 | 355 | void |
54d22525 ILT |
356 | hash_traverse (table, pfn) |
357 | struct hash_control *table; | |
358 | void (*pfn) PARAMS ((const char *key, PTR value)); | |
252b5132 | 359 | { |
54d22525 | 360 | unsigned int i; |
252b5132 | 361 | |
54d22525 ILT |
362 | for (i = 0; i < table->size; ++i) |
363 | { | |
364 | struct hash_entry *p; | |
252b5132 | 365 | |
54d22525 ILT |
366 | for (p = table->table[i]; p != NULL; p = p->next) |
367 | (*pfn) (p->string, p->data); | |
368 | } | |
369 | } | |
252b5132 | 370 | |
54d22525 ILT |
371 | /* Print hash table statistics on the specified file. NAME is the |
372 | name of the hash table, used for printing a header. */ | |
252b5132 | 373 | |
54d22525 ILT |
374 | void |
375 | hash_print_statistics (f, name, table) | |
ab9da554 ILT |
376 | FILE *f ATTRIBUTE_UNUSED; |
377 | const char *name ATTRIBUTE_UNUSED; | |
378 | struct hash_control *table ATTRIBUTE_UNUSED; | |
54d22525 ILT |
379 | { |
380 | #ifdef HASH_STATISTICS | |
381 | unsigned int i; | |
382 | unsigned long total; | |
383 | unsigned long empty; | |
384 | ||
385 | fprintf (f, "%s hash statistics:\n", name); | |
386 | fprintf (f, "\t%lu lookups\n", table->lookups); | |
387 | fprintf (f, "\t%lu hash comparisons\n", table->hash_compares); | |
388 | fprintf (f, "\t%lu string comparisons\n", table->string_compares); | |
389 | fprintf (f, "\t%lu insertions\n", table->insertions); | |
390 | fprintf (f, "\t%lu replacements\n", table->replacements); | |
391 | fprintf (f, "\t%lu deletions\n", table->deletions); | |
392 | ||
393 | total = 0; | |
394 | empty = 0; | |
395 | for (i = 0; i < table->size; ++i) | |
396 | { | |
397 | struct hash_entry *p; | |
252b5132 | 398 | |
54d22525 ILT |
399 | if (table->table[i] == NULL) |
400 | ++empty; | |
401 | else | |
402 | { | |
403 | for (p = table->table[i]; p != NULL; p = p->next) | |
404 | ++total; | |
405 | } | |
406 | } | |
252b5132 | 407 | |
54d22525 ILT |
408 | fprintf (f, "\t%g average chain length\n", (double) total / table->size); |
409 | fprintf (f, "\t%lu empty slots\n", empty); | |
410 | #endif | |
252b5132 RH |
411 | } |
412 | \f | |
252b5132 RH |
413 | #ifdef TEST |
414 | ||
54d22525 ILT |
415 | /* This test program is left over from the old hash table code. */ |
416 | ||
8fc2faa7 KH |
417 | /* Number of hash tables to maintain (at once) in any testing. */ |
418 | #define TABLES (6) | |
419 | ||
420 | /* We can have 12 statistics. */ | |
421 | #define STATBUFSIZE (12) | |
422 | ||
423 | /* Display statistics here. */ | |
424 | int statbuf[STATBUFSIZE]; | |
425 | ||
426 | /* Human farts here. */ | |
427 | char answer[100]; | |
428 | ||
429 | /* We test many hash tables at once. */ | |
430 | char *hashtable[TABLES]; | |
252b5132 | 431 | |
8fc2faa7 KH |
432 | /* Points to curent hash_control. */ |
433 | char *h; | |
252b5132 RH |
434 | char **pp; |
435 | char *p; | |
436 | char *name; | |
437 | char *value; | |
438 | int size; | |
439 | int used; | |
440 | char command; | |
8fc2faa7 KH |
441 | |
442 | /* Number 0:TABLES-1 of current hashed symbol table. */ | |
443 | int number; | |
252b5132 | 444 | |
54d22525 | 445 | int |
252b5132 RH |
446 | main () |
447 | { | |
448 | void applicatee (); | |
449 | void destroy (); | |
450 | char *what (); | |
451 | int *ip; | |
452 | ||
453 | number = 0; | |
454 | h = 0; | |
455 | printf ("type h <RETURN> for help\n"); | |
456 | for (;;) | |
457 | { | |
458 | printf ("hash_test command: "); | |
459 | gets (answer); | |
460 | command = answer[0]; | |
461 | if (isupper (command)) | |
8fc2faa7 | 462 | command = tolower (command); /* Ecch! */ |
252b5132 RH |
463 | switch (command) |
464 | { | |
465 | case '#': | |
466 | printf ("old hash table #=%d.\n", number); | |
467 | whattable (); | |
468 | break; | |
469 | case '?': | |
470 | for (pp = hashtable; pp < hashtable + TABLES; pp++) | |
471 | { | |
8fc2faa7 KH |
472 | printf ("address of hash table #%d control block is %xx\n", |
473 | pp - hashtable, *pp); | |
252b5132 RH |
474 | } |
475 | break; | |
476 | case 'a': | |
54d22525 | 477 | hash_traverse (h, applicatee); |
252b5132 RH |
478 | break; |
479 | case 'd': | |
54d22525 | 480 | hash_traverse (h, destroy); |
252b5132 RH |
481 | hash_die (h); |
482 | break; | |
483 | case 'f': | |
484 | p = hash_find (h, name = what ("symbol")); | |
485 | printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT"); | |
486 | break; | |
487 | case 'h': | |
488 | printf ("# show old, select new default hash table number\n"); | |
489 | printf ("? display all hashtable control block addresses\n"); | |
490 | printf ("a apply a simple display-er to each symbol in table\n"); | |
491 | printf ("d die: destroy hashtable\n"); | |
492 | printf ("f find value of nominated symbol\n"); | |
493 | printf ("h this help\n"); | |
494 | printf ("i insert value into symbol\n"); | |
495 | printf ("j jam value into symbol\n"); | |
496 | printf ("n new hashtable\n"); | |
497 | printf ("r replace a value with another\n"); | |
498 | printf ("s say what %% of table is used\n"); | |
499 | printf ("q exit this program\n"); | |
500 | printf ("x delete a symbol from table, report its value\n"); | |
501 | break; | |
502 | case 'i': | |
503 | p = hash_insert (h, name = what ("symbol"), value = what ("value")); | |
504 | if (p) | |
505 | { | |
506 | printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, | |
507 | p); | |
508 | } | |
509 | break; | |
510 | case 'j': | |
511 | p = hash_jam (h, name = what ("symbol"), value = what ("value")); | |
512 | if (p) | |
513 | { | |
514 | printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p); | |
515 | } | |
516 | break; | |
517 | case 'n': | |
518 | h = hashtable[number] = (char *) hash_new (); | |
519 | break; | |
520 | case 'q': | |
521 | exit (EXIT_SUCCESS); | |
522 | case 'r': | |
523 | p = hash_replace (h, name = what ("symbol"), value = what ("value")); | |
524 | printf ("old value was \"%s\"\n", p ? p : "{}"); | |
525 | break; | |
526 | case 's': | |
527 | hash_say (h, statbuf, STATBUFSIZE); | |
528 | for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++) | |
529 | { | |
530 | printf ("%d ", *ip); | |
531 | } | |
532 | printf ("\n"); | |
533 | break; | |
534 | case 'x': | |
535 | p = hash_delete (h, name = what ("symbol")); | |
536 | printf ("old value was \"%s\"\n", p ? p : "{}"); | |
537 | break; | |
538 | default: | |
539 | printf ("I can't understand command \"%c\"\n", command); | |
540 | break; | |
541 | } | |
542 | } | |
543 | } | |
544 | ||
545 | char * | |
546 | what (description) | |
547 | char *description; | |
548 | { | |
549 | char *retval; | |
550 | char *malloc (); | |
551 | ||
552 | printf (" %s : ", description); | |
553 | gets (answer); | |
8fc2faa7 | 554 | /* Will one day clean up answer here. */ |
252b5132 RH |
555 | retval = malloc (strlen (answer) + 1); |
556 | if (!retval) | |
557 | { | |
558 | error ("room"); | |
559 | } | |
560 | (void) strcpy (retval, answer); | |
561 | return (retval); | |
562 | } | |
563 | ||
564 | void | |
565 | destroy (string, value) | |
566 | char *string; | |
567 | char *value; | |
568 | { | |
569 | free (string); | |
570 | free (value); | |
571 | } | |
572 | ||
252b5132 RH |
573 | void |
574 | applicatee (string, value) | |
575 | char *string; | |
576 | char *value; | |
577 | { | |
578 | printf ("%.20s-%.20s\n", string, value); | |
579 | } | |
580 | ||
8fc2faa7 KH |
581 | /* Determine number: what hash table to use. |
582 | Also determine h: points to hash_control. */ | |
583 | ||
54d22525 | 584 | void |
8fc2faa7 | 585 | whattable () |
252b5132 | 586 | { |
252b5132 RH |
587 | for (;;) |
588 | { | |
589 | printf (" what hash table (%d:%d) ? ", 0, TABLES - 1); | |
590 | gets (answer); | |
591 | sscanf (answer, "%d", &number); | |
592 | if (number >= 0 && number < TABLES) | |
593 | { | |
594 | h = hashtable[number]; | |
595 | if (!h) | |
596 | { | |
597 | printf ("warning: current hash-table-#%d. has no hash-control\n", number); | |
598 | } | |
599 | return; | |
600 | } | |
601 | else | |
602 | { | |
603 | printf ("invalid hash table number: %d\n", number); | |
604 | } | |
605 | } | |
606 | } | |
607 | ||
8fc2faa7 | 608 | #endif /* TEST */ |