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