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