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.
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, 59 Temple Place - Suite 330, Boston, MA
21   02111-1307, 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/* The default number of entries to use when creating a hash table.  */
37
38#define DEFAULT_SIZE (4051)
39
40/* An entry in a hash table.  */
41
42struct 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;
52};
53
54/* A hash table.  */
55
56struct 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;
63
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 */
73};
74
75/* Create a hash table.  This return a control block.  */
76
77struct hash_control *
78hash_new (void)
79{
80  unsigned int size;
81  struct hash_control *ret;
82  unsigned int alloc;
83
84  size = DEFAULT_SIZE;
85
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;
92
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
101
102  return ret;
103}
104
105/* Delete a hash table, freeing all allocated memory.  */
106
107void
108hash_die (struct hash_control *table)
109{
110  obstack_free (&table->memory, 0);
111  free (table);
112}
113
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.
119
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.  */
122
123static struct hash_entry *hash_lookup (struct hash_control *,
124				       const char *,
125				       struct hash_entry ***,
126				       unsigned long *);
127
128static struct hash_entry *
129hash_lookup (struct hash_control *table, const char *key,
130	     struct hash_entry ***plist, unsigned long *phash)
131{
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;
140
141#ifdef HASH_STATISTICS
142  ++table->lookups;
143#endif
144
145  hash = 0;
146  len = 0;
147  s = (const unsigned char *) key;
148  while ((c = *s++) != '\0')
149    {
150      hash += c + (c << 17);
151      hash ^= hash >> 2;
152      ++len;
153    }
154  hash += len + (len << 17);
155  hash ^= hash >> 2;
156
157  if (phash != NULL)
158    *phash = hash;
159
160  index = hash % table->size;
161  list = table->table + index;
162
163  if (plist != NULL)
164    *plist = list;
165
166  prev = NULL;
167  for (p = *list; p != NULL; p = p->next)
168    {
169#ifdef HASH_STATISTICS
170      ++table->hash_compares;
171#endif
172
173      if (p->hash == hash)
174	{
175#ifdef HASH_STATISTICS
176	  ++table->string_compares;
177#endif
178
179	  if (strcmp (p->string, key) == 0)
180	    {
181	      if (prev != NULL)
182		{
183		  prev->next = p->next;
184		  p->next = *list;
185		  *list = p;
186		}
187
188	      return p;
189	    }
190	}
191
192      prev = p;
193    }
194
195  return NULL;
196}
197
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.  */
202
203const char *
204hash_insert (struct hash_control *table, const char *key, PTR value)
205{
206  struct hash_entry *p;
207  struct hash_entry **list;
208  unsigned long hash;
209
210  p = hash_lookup (table, key, &list, &hash);
211  if (p != NULL)
212    return "exists";
213
214#ifdef HASH_STATISTICS
215  ++table->insertions;
216#endif
217
218  p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
219  p->string = key;
220  p->hash = hash;
221  p->data = value;
222
223  p->next = *list;
224  *list = p;
225
226  return NULL;
227}
228
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.  */
232
233const char *
234hash_jam (struct hash_control *table, const char *key, PTR value)
235{
236  struct hash_entry *p;
237  struct hash_entry **list;
238  unsigned long hash;
239
240  p = hash_lookup (table, key, &list, &hash);
241  if (p != NULL)
242    {
243#ifdef HASH_STATISTICS
244      ++table->replacements;
245#endif
246
247      p->data = value;
248    }
249  else
250    {
251#ifdef HASH_STATISTICS
252      ++table->insertions;
253#endif
254
255      p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
256      p->string = key;
257      p->hash = hash;
258      p->data = value;
259
260      p->next = *list;
261      *list = p;
262    }
263
264  return NULL;
265}
266
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.  */
270
271PTR
272hash_replace (struct hash_control *table, const char *key, PTR value)
273{
274  struct hash_entry *p;
275  PTR ret;
276
277  p = hash_lookup (table, key, NULL, NULL);
278  if (p == NULL)
279    return NULL;
280
281#ifdef HASH_STATISTICS
282  ++table->replacements;
283#endif
284
285  ret = p->data;
286
287  p->data = value;
288
289  return ret;
290}
291
292/* Find an entry in a hash table, returning its value.  Returns NULL
293   if the entry is not found.  */
294
295PTR
296hash_find (struct hash_control *table, const char *key)
297{
298  struct hash_entry *p;
299
300  p = hash_lookup (table, key, NULL, NULL);
301  if (p == NULL)
302    return NULL;
303
304  return p->data;
305}
306
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.  */
309
310PTR
311hash_delete (struct hash_control *table, const char *key)
312{
313  struct hash_entry *p;
314  struct hash_entry **list;
315
316  p = hash_lookup (table, key, &list, NULL);
317  if (p == NULL)
318    return NULL;
319
320  if (p != *list)
321    abort ();
322
323#ifdef HASH_STATISTICS
324  ++table->deletions;
325#endif
326
327  *list = p->next;
328
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.  */
332
333  return p->data;
334}
335
336/* Traverse a hash table.  Call the function on every entry in the
337   hash table.  */
338
339void
340hash_traverse (struct hash_control *table,
341	       void (*pfn) (const char *key, PTR value))
342{
343  unsigned int i;
344
345  for (i = 0; i < table->size; ++i)
346    {
347      struct hash_entry *p;
348
349      for (p = table->table[i]; p != NULL; p = p->next)
350	(*pfn) (p->string, p->data);
351    }
352}
353
354/* Print hash table statistics on the specified file.  NAME is the
355   name of the hash table, used for printing a header.  */
356
357void
358hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
359		       const char *name ATTRIBUTE_UNUSED,
360		       struct hash_control *table ATTRIBUTE_UNUSED)
361{
362#ifdef HASH_STATISTICS
363  unsigned int i;
364  unsigned long total;
365  unsigned long empty;
366
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);
374
375  total = 0;
376  empty = 0;
377  for (i = 0; i < table->size; ++i)
378    {
379      struct hash_entry *p;
380
381      if (table->table[i] == NULL)
382	++empty;
383      else
384	{
385	  for (p = table->table[i]; p != NULL; p = p->next)
386	    ++total;
387	}
388    }
389
390  fprintf (f, "\t%g average chain length\n", (double) total / table->size);
391  fprintf (f, "\t%lu empty slots\n", empty);
392#endif
393}
394
395#ifdef TEST
396
397/* This test program is left over from the old hash table code.  */
398
399/* Number of hash tables to maintain (at once) in any testing.  */
400#define TABLES (6)
401
402/* We can have 12 statistics.  */
403#define STATBUFSIZE (12)
404
405/* Display statistics here.  */
406int statbuf[STATBUFSIZE];
407
408/* Human farts here.  */
409char answer[100];
410
411/* We test many hash tables at once.  */
412char *hashtable[TABLES];
413
414/* Points to current hash_control.  */
415char *h;
416char **pp;
417char *p;
418char *name;
419char *value;
420int size;
421int used;
422char command;
423
424/* Number 0:TABLES-1 of current hashed symbol table.  */
425int number;
426
427int
428main ()
429{
430  void applicatee ();
431  void destroy ();
432  char *what ();
433  int *ip;
434
435  number = 0;
436  h = 0;
437  printf ("type h <RETURN> for help\n");
438  for (;;)
439    {
440      printf ("hash_test command: ");
441      gets (answer);
442      command = answer[0];
443      command = TOLOWER (command);	/* Ecch!  */
444      switch (command)
445	{
446	case '#':
447	  printf ("old hash table #=%d.\n", number);
448	  whattable ();
449	  break;
450	case '?':
451	  for (pp = hashtable; pp < hashtable + TABLES; pp++)
452	    {
453	      printf ("address of hash table #%d control block is %xx\n",
454		      pp - hashtable, *pp);
455	    }
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)
486	    {
487	      printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
488		      p);
489	    }
490	  break;
491	case 'j':
492	  p = hash_jam (h, name = what ("symbol"), value = what ("value"));
493	  if (p)
494	    {
495	      printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
496	    }
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++)
510	    {
511	      printf ("%d ", *ip);
512	    }
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;
522	}
523    }
524}
525
526char *
527what (description)
528     char *description;
529{
530  printf ("   %s : ", description);
531  gets (answer);
532  return xstrdup (answer);
533}
534
535void
536destroy (string, value)
537     char *string;
538     char *value;
539{
540  free (string);
541  free (value);
542}
543
544void
545applicatee (string, value)
546     char *string;
547     char *value;
548{
549  printf ("%.20s-%.20s\n", string, value);
550}
551
552/* Determine number: what hash table to use.
553   Also determine h: points to hash_control.  */
554
555void
556whattable ()
557{
558  for (;;)
559    {
560      printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
561      gets (answer);
562      sscanf (answer, "%d", &number);
563      if (number >= 0 && number < TABLES)
564	{
565	  h = hashtable[number];
566	  if (!h)
567	    {
568	      printf ("warning: current hash-table-#%d. has no hash-control\n", number);
569	    }
570	  return;
571	}
572      else
573	{
574	  printf ("invalid hash table number: %d\n", number);
575	}
576    }
577}
578
579#endif /* TEST */
580