merge from gcc
[binutils.git] / gas / hash.c
bloba7b82987b20fab32b90b277581d451c433452a8a
1 /* hash.c -- gas hash table code
2 Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
3 2000, 2001, 2002
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)
11 any later version.
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
21 02111-1307, USA. */
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. */
32 #include "as.h"
33 #include "safe-ctype.h"
34 #include "obstack.h"
36 /* The default number of entries to use when creating a hash table. */
38 #define DEFAULT_SIZE (4051)
40 /* An entry in a hash table. */
42 struct hash_entry {
43 /* Next entry for this hash code. */
44 struct hash_entry *next;
45 /* String being hashed. */
46 const char *string;
47 /* Hash code. This is the full hash code, not the index into the
48 table. */
49 unsigned long hash;
50 /* Pointer being stored in the hash table. */
51 PTR data;
54 /* A hash table. */
56 struct hash_control {
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;
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 */
75 /* Create a hash table. This return a control block. */
77 struct hash_control *
78 hash_new (void)
80 unsigned int size;
81 struct hash_control *ret;
82 unsigned int alloc;
84 size = DEFAULT_SIZE;
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;
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
102 return ret;
105 /* Delete a hash table, freeing all allocated memory. */
107 void
108 hash_die (struct hash_control *table)
110 obstack_free (&table->memory, 0);
111 free (table);
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.
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. */
123 static struct hash_entry *hash_lookup (struct hash_control *,
124 const char *,
125 struct hash_entry ***,
126 unsigned long *);
128 static struct hash_entry *
129 hash_lookup (struct hash_control *table, const char *key,
130 struct hash_entry ***plist, unsigned long *phash)
132 register unsigned long hash;
133 unsigned int len;
134 register const unsigned char *s;
135 register unsigned int c;
136 unsigned int index;
137 struct hash_entry **list;
138 struct hash_entry *p;
139 struct hash_entry *prev;
141 #ifdef HASH_STATISTICS
142 ++table->lookups;
143 #endif
145 hash = 0;
146 len = 0;
147 s = (const unsigned char *) key;
148 while ((c = *s++) != '\0')
150 hash += c + (c << 17);
151 hash ^= hash >> 2;
152 ++len;
154 hash += len + (len << 17);
155 hash ^= hash >> 2;
157 if (phash != NULL)
158 *phash = hash;
160 index = hash % table->size;
161 list = table->table + index;
163 if (plist != NULL)
164 *plist = list;
166 prev = NULL;
167 for (p = *list; p != NULL; p = p->next)
169 #ifdef HASH_STATISTICS
170 ++table->hash_compares;
171 #endif
173 if (p->hash == hash)
175 #ifdef HASH_STATISTICS
176 ++table->string_compares;
177 #endif
179 if (strcmp (p->string, key) == 0)
181 if (prev != NULL)
183 prev->next = p->next;
184 p->next = *list;
185 *list = p;
188 return p;
192 prev = p;
195 return NULL;
198 /* Insert an entry into a hash table. This returns NULL on success.
199 On error, it returns a printable string indicating the error. It
200 is considered to be an error if the entry already exists in the
201 hash table. */
203 const char *
204 hash_insert (struct hash_control *table, const char *key, PTR value)
206 struct hash_entry *p;
207 struct hash_entry **list;
208 unsigned long hash;
210 p = hash_lookup (table, key, &list, &hash);
211 if (p != NULL)
212 return "exists";
214 #ifdef HASH_STATISTICS
215 ++table->insertions;
216 #endif
218 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
219 p->string = key;
220 p->hash = hash;
221 p->data = value;
223 p->next = *list;
224 *list = p;
226 return NULL;
229 /* Insert or replace an entry in a hash table. This returns NULL on
230 success. On error, it returns a printable string indicating the
231 error. If an entry already exists, its value is replaced. */
233 const char *
234 hash_jam (struct hash_control *table, const char *key, PTR value)
236 struct hash_entry *p;
237 struct hash_entry **list;
238 unsigned long hash;
240 p = hash_lookup (table, key, &list, &hash);
241 if (p != NULL)
243 #ifdef HASH_STATISTICS
244 ++table->replacements;
245 #endif
247 p->data = value;
249 else
251 #ifdef HASH_STATISTICS
252 ++table->insertions;
253 #endif
255 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
256 p->string = key;
257 p->hash = hash;
258 p->data = value;
260 p->next = *list;
261 *list = p;
264 return NULL;
267 /* Replace an existing entry in a hash table. This returns the old
268 value stored for the entry. If the entry is not found in the hash
269 table, this does nothing and returns NULL. */
272 hash_replace (struct hash_control *table, const char *key, PTR value)
274 struct hash_entry *p;
275 PTR ret;
277 p = hash_lookup (table, key, NULL, NULL);
278 if (p == NULL)
279 return NULL;
281 #ifdef HASH_STATISTICS
282 ++table->replacements;
283 #endif
285 ret = p->data;
287 p->data = value;
289 return ret;
292 /* Find an entry in a hash table, returning its value. Returns NULL
293 if the entry is not found. */
296 hash_find (struct hash_control *table, const char *key)
298 struct hash_entry *p;
300 p = hash_lookup (table, key, NULL, NULL);
301 if (p == NULL)
302 return NULL;
304 return p->data;
307 /* Delete an entry from a hash table. This returns the value stored
308 for that entry, or NULL if there is no such entry. */
311 hash_delete (struct hash_control *table, const char *key)
313 struct hash_entry *p;
314 struct hash_entry **list;
316 p = hash_lookup (table, key, &list, NULL);
317 if (p == NULL)
318 return NULL;
320 if (p != *list)
321 abort ();
323 #ifdef HASH_STATISTICS
324 ++table->deletions;
325 #endif
327 *list = p->next;
329 /* Note that we never reclaim the memory for this entry. If gas
330 ever starts deleting hash table entries in a big way, this will
331 have to change. */
333 return p->data;
336 /* Traverse a hash table. Call the function on every entry in the
337 hash table. */
339 void
340 hash_traverse (struct hash_control *table,
341 void (*pfn) (const char *key, PTR value))
343 unsigned int i;
345 for (i = 0; i < table->size; ++i)
347 struct hash_entry *p;
349 for (p = table->table[i]; p != NULL; p = p->next)
350 (*pfn) (p->string, p->data);
354 /* Print hash table statistics on the specified file. NAME is the
355 name of the hash table, used for printing a header. */
357 void
358 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
359 const char *name ATTRIBUTE_UNUSED,
360 struct hash_control *table ATTRIBUTE_UNUSED)
362 #ifdef HASH_STATISTICS
363 unsigned int i;
364 unsigned long total;
365 unsigned long empty;
367 fprintf (f, "%s hash statistics:\n", name);
368 fprintf (f, "\t%lu lookups\n", table->lookups);
369 fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
370 fprintf (f, "\t%lu string comparisons\n", table->string_compares);
371 fprintf (f, "\t%lu insertions\n", table->insertions);
372 fprintf (f, "\t%lu replacements\n", table->replacements);
373 fprintf (f, "\t%lu deletions\n", table->deletions);
375 total = 0;
376 empty = 0;
377 for (i = 0; i < table->size; ++i)
379 struct hash_entry *p;
381 if (table->table[i] == NULL)
382 ++empty;
383 else
385 for (p = table->table[i]; p != NULL; p = p->next)
386 ++total;
390 fprintf (f, "\t%g average chain length\n", (double) total / table->size);
391 fprintf (f, "\t%lu empty slots\n", empty);
392 #endif
395 #ifdef TEST
397 /* This test program is left over from the old hash table code. */
399 /* Number of hash tables to maintain (at once) in any testing. */
400 #define TABLES (6)
402 /* We can have 12 statistics. */
403 #define STATBUFSIZE (12)
405 /* Display statistics here. */
406 int statbuf[STATBUFSIZE];
408 /* Human farts here. */
409 char answer[100];
411 /* We test many hash tables at once. */
412 char *hashtable[TABLES];
414 /* Points to current hash_control. */
415 char *h;
416 char **pp;
417 char *p;
418 char *name;
419 char *value;
420 int size;
421 int used;
422 char command;
424 /* Number 0:TABLES-1 of current hashed symbol table. */
425 int number;
428 main ()
430 void applicatee ();
431 void destroy ();
432 char *what ();
433 int *ip;
435 number = 0;
436 h = 0;
437 printf ("type h <RETURN> for help\n");
438 for (;;)
440 printf ("hash_test command: ");
441 gets (answer);
442 command = answer[0];
443 command = TOLOWER (command); /* Ecch! */
444 switch (command)
446 case '#':
447 printf ("old hash table #=%d.\n", number);
448 whattable ();
449 break;
450 case '?':
451 for (pp = hashtable; pp < hashtable + TABLES; pp++)
453 printf ("address of hash table #%d control block is %xx\n",
454 pp - hashtable, *pp);
456 break;
457 case 'a':
458 hash_traverse (h, applicatee);
459 break;
460 case 'd':
461 hash_traverse (h, destroy);
462 hash_die (h);
463 break;
464 case 'f':
465 p = hash_find (h, name = what ("symbol"));
466 printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
467 break;
468 case 'h':
469 printf ("# show old, select new default hash table number\n");
470 printf ("? display all hashtable control block addresses\n");
471 printf ("a apply a simple display-er to each symbol in table\n");
472 printf ("d die: destroy hashtable\n");
473 printf ("f find value of nominated symbol\n");
474 printf ("h this help\n");
475 printf ("i insert value into symbol\n");
476 printf ("j jam value into symbol\n");
477 printf ("n new hashtable\n");
478 printf ("r replace a value with another\n");
479 printf ("s say what %% of table is used\n");
480 printf ("q exit this program\n");
481 printf ("x delete a symbol from table, report its value\n");
482 break;
483 case 'i':
484 p = hash_insert (h, name = what ("symbol"), value = what ("value"));
485 if (p)
487 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value,
490 break;
491 case 'j':
492 p = hash_jam (h, name = what ("symbol"), value = what ("value"));
493 if (p)
495 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p);
497 break;
498 case 'n':
499 h = hashtable[number] = (char *) hash_new ();
500 break;
501 case 'q':
502 exit (EXIT_SUCCESS);
503 case 'r':
504 p = hash_replace (h, name = what ("symbol"), value = what ("value"));
505 printf ("old value was \"%s\"\n", p ? p : "{}");
506 break;
507 case 's':
508 hash_say (h, statbuf, STATBUFSIZE);
509 for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
511 printf ("%d ", *ip);
513 printf ("\n");
514 break;
515 case 'x':
516 p = hash_delete (h, name = what ("symbol"));
517 printf ("old value was \"%s\"\n", p ? p : "{}");
518 break;
519 default:
520 printf ("I can't understand command \"%c\"\n", command);
521 break;
526 char *
527 what (description)
528 char *description;
530 printf (" %s : ", description);
531 gets (answer);
532 return xstrdup (answer);
535 void
536 destroy (string, value)
537 char *string;
538 char *value;
540 free (string);
541 free (value);
544 void
545 applicatee (string, value)
546 char *string;
547 char *value;
549 printf ("%.20s-%.20s\n", string, value);
552 /* Determine number: what hash table to use.
553 Also determine h: points to hash_control. */
555 void
556 whattable ()
558 for (;;)
560 printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
561 gets (answer);
562 sscanf (answer, "%d", &number);
563 if (number >= 0 && number < TABLES)
565 h = hashtable[number];
566 if (!h)
568 printf ("warning: current hash-table-#%d. has no hash-control\n", number);
570 return;
572 else
574 printf ("invalid hash table number: %d\n", number);
579 #endif /* TEST */