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.
6 This file is part of GAS, the GNU Assembler.
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)
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.
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, 59 Temple Place - Suite 330, Boston, MA
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
33 #include "safe-ctype.h"
36 /* An entry in a hash table. */
39 /* Next entry for this hash code. */
40 struct hash_entry *next;
41 /* String being hashed. */
43 /* Hash code. This is the full hash code, not the index into the
46 /* Pointer being stored in the hash table. */
54 struct hash_entry **table;
55 /* The number of slots in the hash table. */
57 /* An obstack for this hash table. */
58 struct obstack memory;
60 #ifdef HASH_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 */
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. */
76 static unsigned long gas_hash_table_size = 65537;
79 set_gas_hash_table_size (unsigned long size)
81 gas_hash_table_size = size;
84 /* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size(). */
86 get_gas_hash_table_size (void)
88 /* Extend this prime list if you want more granularity of hash table size. */
89 static const unsigned long hash_size_primes[] =
91 1021, 4051, 8599, 16699, 65537
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])
102 return hash_size_primes[index];
105 /* Create a hash table. This return a control block. */
107 struct hash_control *
112 struct hash_control *ret;
114 size = get_gas_hash_table_size ();
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);
123 #ifdef HASH_STATISTICS
125 ret->hash_compares = 0;
126 ret->string_compares = 0;
128 ret->replacements = 0;
135 /* Delete a hash table, freeing all allocated memory. */
138 hash_die (struct hash_control *table)
140 obstack_free (&table->memory, 0);
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.
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. */
153 static struct hash_entry *hash_lookup (struct hash_control *,
155 struct hash_entry ***,
158 static struct hash_entry *
159 hash_lookup (struct hash_control *table, const char *key,
160 struct hash_entry ***plist, unsigned long *phash)
162 register unsigned long hash;
164 register const unsigned char *s;
165 register unsigned int c;
167 struct hash_entry **list;
168 struct hash_entry *p;
169 struct hash_entry *prev;
171 #ifdef HASH_STATISTICS
177 s = (const unsigned char *) key;
178 while ((c = *s++) != '\0')
180 hash += c + (c << 17);
184 hash += len + (len << 17);
190 index = hash % table->size;
191 list = table->table + index;
197 for (p = *list; p != NULL; p = p->next)
199 #ifdef HASH_STATISTICS
200 ++table->hash_compares;
205 #ifdef HASH_STATISTICS
206 ++table->string_compares;
209 if (strcmp (p->string, key) == 0)
213 prev->next = p->next;
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
234 hash_insert (struct hash_control *table, const char *key, PTR value)
236 struct hash_entry *p;
237 struct hash_entry **list;
240 p = hash_lookup (table, key, &list, &hash);
244 #ifdef HASH_STATISTICS
248 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
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. */
264 hash_jam (struct hash_control *table, const char *key, PTR value)
266 struct hash_entry *p;
267 struct hash_entry **list;
270 p = hash_lookup (table, key, &list, &hash);
273 #ifdef HASH_STATISTICS
274 ++table->replacements;
281 #ifdef HASH_STATISTICS
285 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
297 /* Find an entry in a hash table, returning its value. Returns NULL
298 if the entry is not found. */
301 hash_find (struct hash_control *table, const char *key)
303 struct hash_entry *p;
305 p = hash_lookup (table, key, NULL, NULL);
312 /* Traverse a hash table. Call the function on every entry in the
316 hash_traverse (struct hash_control *table,
317 void (*pfn) (const char *key, PTR value))
321 for (i = 0; i < table->size; ++i)
323 struct hash_entry *p;
325 for (p = table->table[i]; p != NULL; p = p->next)
326 (*pfn) (p->string, p->data);
330 /* Print hash table statistics on the specified file. NAME is the
331 name of the hash table, used for printing a header. */
334 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
335 const char *name ATTRIBUTE_UNUSED,
336 struct hash_control *table ATTRIBUTE_UNUSED)
338 #ifdef HASH_STATISTICS
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);
353 for (i = 0; i < table->size; ++i)
355 struct hash_entry *p;
357 if (table->table[i] == NULL)
361 for (p = table->table[i]; p != NULL; p = p->next)
366 fprintf (f, "\t%g average chain length\n", (double) total / table->size);
367 fprintf (f, "\t%lu empty slots\n", empty);
373 /* This test program is left over from the old hash table code. */
375 /* Number of hash tables to maintain (at once) in any testing. */
378 /* We can have 12 statistics. */
379 #define STATBUFSIZE (12)
381 /* Display statistics here. */
382 int statbuf[STATBUFSIZE];
384 /* Human farts here. */
387 /* We test many hash tables at once. */
388 char *hashtable[TABLES];
390 /* Points to current hash_control. */
400 /* Number 0:TABLES-1 of current hashed symbol table. */
413 printf ("type h <RETURN> for help\n");
416 printf ("hash_test command: ");
419 command = TOLOWER (command); /* Ecch! */
423 printf ("old hash table #=%d.\n", number);
427 for (pp = hashtable; pp < hashtable + TABLES; pp++)
429 printf ("address of hash table #%d control block is %xx\n",
430 pp - hashtable, *pp);
434 hash_traverse (h, applicatee);
437 hash_traverse (h, destroy);
441 p = hash_find (h, name = what ("symbol"));
442 printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
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");
460 p = hash_insert (h, name = what ("symbol"), value = what ("value"));
463 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value,
468 p = hash_jam (h, name = what ("symbol"), value = what ("value"));
471 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p);
475 h = hashtable[number] = (char *) hash_new ();
480 p = hash_replace (h, name = what ("symbol"), value = what ("value"));
481 printf ("old value was \"%s\"\n", p ? p : "{}");
484 hash_say (h, statbuf, STATBUFSIZE);
485 for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
492 p = hash_delete (h, name = what ("symbol"));
493 printf ("old value was \"%s\"\n", p ? p : "{}");
496 printf ("I can't understand command \"%c\"\n", command);
506 printf (" %s : ", description);
508 return xstrdup (answer);
512 destroy (string, value)
521 applicatee (string, value)
525 printf ("%.20s-%.20s\n", string, value);
528 /* Determine number: what hash table to use.
529 Also determine h: points to hash_control. */
536 printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
538 sscanf (answer, "%d", &number);
539 if (number >= 0 && number < TABLES)
541 h = hashtable[number];
544 printf ("warning: current hash-table-#%d. has no hash-control\n", number);
550 printf ("invalid hash table number: %d\n", number);