2000-08-29 Michael Snyder <msnyder@seadog.cygnus.com>
[binutils.git] / gas / hash.c
blob094340873fce07b80cfa746232865868ba1f52ee
1 /* hash.c -- gas hash table code
2 Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 99, 2000
3 Free Software Foundation, Inc.
5 This file is part of GAS, the GNU Assembler.
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.
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.
17 You should have received a copy of the GNU General Public License
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. */
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. */
31 #include "as.h"
32 #include "obstack.h"
34 /* The default number of entries to use when creating a hash table. */
36 #define DEFAULT_SIZE (4051)
38 /* An entry in a hash table. */
40 struct hash_entry
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;
53 /* A hash table. */
55 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 ()
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 (table)
109 struct hash_control *table;
111 obstack_free (&table->memory, 0);
112 free (table);
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.
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. */
124 static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
125 const char *,
126 struct hash_entry ***,
127 unsigned long *));
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;
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;
145 #ifdef HASH_STATISTICS
146 ++table->lookups;
147 #endif
149 hash = 0;
150 len = 0;
151 s = (const unsigned char *) key;
152 while ((c = *s++) != '\0')
154 hash += c + (c << 17);
155 hash ^= hash >> 2;
156 ++len;
158 hash += len + (len << 17);
159 hash ^= hash >> 2;
161 if (phash != NULL)
162 *phash = hash;
164 index = hash % table->size;
165 list = table->table + index;
167 if (plist != NULL)
168 *plist = list;
170 prev = NULL;
171 for (p = *list; p != NULL; p = p->next)
173 #ifdef HASH_STATISTICS
174 ++table->hash_compares;
175 #endif
177 if (p->hash == hash)
179 #ifdef HASH_STATISTICS
180 ++table->string_compares;
181 #endif
183 if (strcmp (p->string, key) == 0)
185 if (prev != NULL)
187 prev->next = p->next;
188 p->next = *list;
189 *list = p;
192 return p;
196 prev = p;
199 return NULL;
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. */
207 const char *
208 hash_insert (table, key, value)
209 struct hash_control *table;
210 const char *key;
211 PTR value;
213 struct hash_entry *p;
214 struct hash_entry **list;
215 unsigned long hash;
217 p = hash_lookup (table, key, &list, &hash);
218 if (p != NULL)
219 return "exists";
221 #ifdef HASH_STATISTICS
222 ++table->insertions;
223 #endif
225 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
226 p->string = key;
227 p->hash = hash;
228 p->data = value;
230 p->next = *list;
231 *list = p;
233 return NULL;
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. */
240 const char *
241 hash_jam (table, key, value)
242 struct hash_control *table;
243 const char *key;
244 PTR value;
246 struct hash_entry *p;
247 struct hash_entry **list;
248 unsigned long hash;
250 p = hash_lookup (table, key, &list, &hash);
251 if (p != NULL)
253 #ifdef HASH_STATISTICS
254 ++table->replacements;
255 #endif
257 p->data = value;
259 else
261 #ifdef HASH_STATISTICS
262 ++table->insertions;
263 #endif
265 p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
266 p->string = key;
267 p->hash = hash;
268 p->data = value;
270 p->next = *list;
271 *list = p;
274 return NULL;
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. */
282 hash_replace (table, key, value)
283 struct hash_control *table;
284 const char *key;
285 PTR value;
287 struct hash_entry *p;
288 PTR ret;
290 p = hash_lookup (table, key, NULL, NULL);
291 if (p == NULL)
292 return NULL;
294 #ifdef HASH_STATISTICS
295 ++table->replacements;
296 #endif
298 ret = p->data;
300 p->data = value;
302 return ret;
305 /* Find an entry in a hash table, returning its value. Returns NULL
306 if the entry is not found. */
309 hash_find (table, key)
310 struct hash_control *table;
311 const char *key;
313 struct hash_entry *p;
315 p = hash_lookup (table, key, NULL, NULL);
316 if (p == NULL)
317 return NULL;
319 return p->data;
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. */
326 hash_delete (table, key)
327 struct hash_control *table;
328 const char *key;
330 struct hash_entry *p;
331 struct hash_entry **list;
333 p = hash_lookup (table, key, &list, NULL);
334 if (p == NULL)
335 return NULL;
337 if (p != *list)
338 abort ();
340 #ifdef HASH_STATISTICS
341 ++table->deletions;
342 #endif
344 *list = p->next;
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. */
350 return p->data;
353 /* Traverse a hash table. Call the function on every entry in the
354 hash table. */
356 void
357 hash_traverse (table, pfn)
358 struct hash_control *table;
359 void (*pfn) PARAMS ((const char *key, PTR value));
361 unsigned int i;
363 for (i = 0; i < table->size; ++i)
365 struct hash_entry *p;
367 for (p = table->table[i]; p != NULL; p = p->next)
368 (*pfn) (p->string, p->data);
372 /* Print hash table statistics on the specified file. NAME is the
373 name of the hash table, used for printing a header. */
375 void
376 hash_print_statistics (f, name, table)
377 FILE *f ATTRIBUTE_UNUSED;
378 const char *name ATTRIBUTE_UNUSED;
379 struct hash_control *table ATTRIBUTE_UNUSED;
381 #ifdef HASH_STATISTICS
382 unsigned int i;
383 unsigned long total;
384 unsigned long empty;
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);
394 total = 0;
395 empty = 0;
396 for (i = 0; i < table->size; ++i)
398 struct hash_entry *p;
400 if (table->table[i] == NULL)
401 ++empty;
402 else
404 for (p = table->table[i]; p != NULL; p = p->next)
405 ++total;
409 fprintf (f, "\t%g average chain length\n", (double) total / table->size);
410 fprintf (f, "\t%lu empty slots\n", empty);
411 #endif
414 #ifdef TEST
416 /* This test program is left over from the old hash table code. */
418 /* Number of hash tables to maintain (at once) in any testing. */
419 #define TABLES (6)
421 /* We can have 12 statistics. */
422 #define STATBUFSIZE (12)
424 /* Display statistics here. */
425 int statbuf[STATBUFSIZE];
427 /* Human farts here. */
428 char answer[100];
430 /* We test many hash tables at once. */
431 char *hashtable[TABLES];
433 /* Points to curent hash_control. */
434 char *h;
435 char **pp;
436 char *p;
437 char *name;
438 char *value;
439 int size;
440 int used;
441 char command;
443 /* Number 0:TABLES-1 of current hashed symbol table. */
444 int number;
447 main ()
449 void applicatee ();
450 void destroy ();
451 char *what ();
452 int *ip;
454 number = 0;
455 h = 0;
456 printf ("type h <RETURN> for help\n");
457 for (;;)
459 printf ("hash_test command: ");
460 gets (answer);
461 command = answer[0];
462 if (isupper (command))
463 command = tolower (command); /* Ecch! */
464 switch (command)
466 case '#':
467 printf ("old hash table #=%d.\n", number);
468 whattable ();
469 break;
470 case '?':
471 for (pp = hashtable; pp < hashtable + TABLES; pp++)
473 printf ("address of hash table #%d control block is %xx\n",
474 pp - hashtable, *pp);
476 break;
477 case 'a':
478 hash_traverse (h, applicatee);
479 break;
480 case 'd':
481 hash_traverse (h, destroy);
482 hash_die (h);
483 break;
484 case 'f':
485 p = hash_find (h, name = what ("symbol"));
486 printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
487 break;
488 case 'h':
489 printf ("# show old, select new default hash table number\n");
490 printf ("? display all hashtable control block addresses\n");
491 printf ("a apply a simple display-er to each symbol in table\n");
492 printf ("d die: destroy hashtable\n");
493 printf ("f find value of nominated symbol\n");
494 printf ("h this help\n");
495 printf ("i insert value into symbol\n");
496 printf ("j jam value into symbol\n");
497 printf ("n new hashtable\n");
498 printf ("r replace a value with another\n");
499 printf ("s say what %% of table is used\n");
500 printf ("q exit this program\n");
501 printf ("x delete a symbol from table, report its value\n");
502 break;
503 case 'i':
504 p = hash_insert (h, name = what ("symbol"), value = what ("value"));
505 if (p)
507 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value,
510 break;
511 case 'j':
512 p = hash_jam (h, name = what ("symbol"), value = what ("value"));
513 if (p)
515 printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p);
517 break;
518 case 'n':
519 h = hashtable[number] = (char *) hash_new ();
520 break;
521 case 'q':
522 exit (EXIT_SUCCESS);
523 case 'r':
524 p = hash_replace (h, name = what ("symbol"), value = what ("value"));
525 printf ("old value was \"%s\"\n", p ? p : "{}");
526 break;
527 case 's':
528 hash_say (h, statbuf, STATBUFSIZE);
529 for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
531 printf ("%d ", *ip);
533 printf ("\n");
534 break;
535 case 'x':
536 p = hash_delete (h, name = what ("symbol"));
537 printf ("old value was \"%s\"\n", p ? p : "{}");
538 break;
539 default:
540 printf ("I can't understand command \"%c\"\n", command);
541 break;
546 char *
547 what (description)
548 char *description;
550 char *retval;
551 char *malloc ();
553 printf (" %s : ", description);
554 gets (answer);
555 /* Will one day clean up answer here. */
556 retval = malloc (strlen (answer) + 1);
557 if (!retval)
559 error ("room");
561 (void) strcpy (retval, answer);
562 return (retval);
565 void
566 destroy (string, value)
567 char *string;
568 char *value;
570 free (string);
571 free (value);
574 void
575 applicatee (string, value)
576 char *string;
577 char *value;
579 printf ("%.20s-%.20s\n", string, value);
582 /* Determine number: what hash table to use.
583 Also determine h: points to hash_control. */
585 void
586 whattable ()
588 for (;;)
590 printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
591 gets (answer);
592 sscanf (answer, "%d", &number);
593 if (number >= 0 && number < TABLES)
595 h = hashtable[number];
596 if (!h)
598 printf ("warning: current hash-table-#%d. has no hash-control\n", number);
600 return;
602 else
604 printf ("invalid hash table number: %d\n", number);
609 #endif /* TEST */