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
38struct 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
52struct 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
76static unsigned long gas_hash_table_size = 65537;
77
78void
79set_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().  */
85static unsigned long
86get_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
107struct hash_control *
108hash_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
137void
138hash_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
153static struct hash_entry *
154hash_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
225const char *
226hash_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
255const char *
256hash_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
293PTR
294hash_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
317PTR
318hash_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
332PTR
333hash_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
347PTR
348hash_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
376void
377hash_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
394void
395hash_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.  */
443int statbuf[STATBUFSIZE];
444
445/* Human farts here.  */
446char answer[100];
447
448/* We test many hash tables at once.  */
449char *hashtable[TABLES];
450
451/* Points to current hash_control.  */
452char *h;
453char **pp;
454char *p;
455char *name;
456char *value;
457int size;
458int used;
459char command;
460
461/* Number 0:TABLES-1 of current hashed symbol table.  */
462int number;
463
464int
465main ()
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
563char *
564what (description)
565     char *description;
566{
567  printf ("   %s : ", description);
568  gets (answer);
569  return xstrdup (answer);
570}
571
572void
573destroy (string, value)
574     char *string;
575     char *value;
576{
577  free (string);
578  free (value);
579}
580
581void
582applicatee (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
592void
593whattable ()
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