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