1/* hash.c -- gas hash table code
2   Copyright (C) 1987-2017 Free Software Foundation, Inc.
3
4   This file is part of GAS, the GNU Assembler.
5
6   GAS is free software; you can redistribute it and/or modify
7   it under the terms of the GNU General Public License as published by
8   the Free Software Foundation; either version 3, or (at your option)
9   any later version.
10
11   GAS is distributed in the hope that it will be useful,
12   but WITHOUT ANY WARRANTY; without even the implied warranty of
13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14   GNU General Public License for more details.
15
16   You should have received a copy of the GNU General Public License
17   along with GAS; see the file COPYING.  If not, write to the Free
18   Software Foundation, 51 Franklin Street - Fifth Floor, Boston, MA
19   02110-1301, USA.  */
20
21/* This version of the hash table code is a wholescale replacement of
22   the old hash table code, which was fairly bad.  This is based on
23   the hash table code in BFD, but optimized slightly for the
24   assembler.  The assembler does not need to derive structures that
25   are stored in the hash table.  Instead, it always stores a pointer.
26   The assembler uses the hash table mostly to store symbols, and we
27   don't need to confuse the symbol structure with a hash table
28   structure.  */
29
30#include "as.h"
31#include "safe-ctype.h"
32#include "obstack.h"
33
34/* An entry in a hash table.  */
35
36struct hash_entry {
37  /* Next entry for this hash code.  */
38  struct hash_entry *next;
39  /* String being hashed.  */
40  const char *string;
41  /* Hash code.  This is the full hash code, not the index into the
42     table.  */
43  unsigned long hash;
44  /* Pointer being stored in the hash table.  */
45  void *data;
46};
47
48/* A hash table.  */
49
50struct hash_control {
51  /* The hash array.  */
52  struct hash_entry **table;
53  /* The number of slots in the hash table.  */
54  unsigned int size;
55  /* An obstack for this hash table.  */
56  struct obstack memory;
57
58#ifdef HASH_STATISTICS
59  /* Statistics.  */
60  unsigned long lookups;
61  unsigned long hash_compares;
62  unsigned long string_compares;
63  unsigned long insertions;
64  unsigned long replacements;
65  unsigned long deletions;
66#endif /* HASH_STATISTICS */
67};
68
69/* The default number of entries to use when creating a hash table.
70   Note this value can be reduced to 4051 by using the command line
71   switch --reduce-memory-overheads, or set to other values by using
72   the --hash-size=<NUMBER> switch.  */
73
74static unsigned long gas_hash_table_size = 65537;
75
76void
77set_gas_hash_table_size (unsigned long size)
78{
79  gas_hash_table_size = bfd_hash_set_default_size (size);
80}
81
82/* Create a hash table.  This return a control block.  */
83
84struct hash_control *
85hash_new_sized (unsigned long size)
86{
87  unsigned long alloc;
88  struct hash_control *ret;
89
90  ret = XNEW (struct hash_control);
91  obstack_begin (&ret->memory, chunksize);
92  alloc = size * sizeof (struct hash_entry *);
93  ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
94  memset (ret->table, 0, alloc);
95  ret->size = size;
96
97#ifdef HASH_STATISTICS
98  ret->lookups = 0;
99  ret->hash_compares = 0;
100  ret->string_compares = 0;
101  ret->insertions = 0;
102  ret->replacements = 0;
103  ret->deletions = 0;
104#endif
105
106  return ret;
107}
108
109struct hash_control *
110hash_new (void)
111{
112  return hash_new_sized (gas_hash_table_size);
113}
114
115/* Delete a hash table, freeing all allocated memory.  */
116
117void
118hash_die (struct hash_control *table)
119{
120  obstack_free (&table->memory, 0);
121  free (table);
122}
123
124/* Look up a string in a hash table.  This returns a pointer to the
125   hash_entry, or NULL if the string is not in the table.  If PLIST is
126   not NULL, this sets *PLIST to point to the start of the list which
127   would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
128   to the hash code for KEY.
129
130   Each time we look up a string, we move it to the start of the list
131   for its hash code, to take advantage of referential locality.  */
132
133static struct hash_entry *
134hash_lookup (struct hash_control *table, const char *key, size_t len,
135	     struct hash_entry ***plist, unsigned long *phash)
136{
137  unsigned long hash;
138  size_t n;
139  unsigned int c;
140  unsigned int hindex;
141  struct hash_entry **list;
142  struct hash_entry *p;
143  struct hash_entry *prev;
144
145#ifdef HASH_STATISTICS
146  ++table->lookups;
147#endif
148
149  hash = 0;
150  for (n = 0; n < len; n++)
151    {
152      c = key[n];
153      hash += c + (c << 17);
154      hash ^= hash >> 2;
155    }
156  hash += len + (len << 17);
157  hash ^= hash >> 2;
158
159  if (phash != NULL)
160    *phash = hash;
161
162  hindex = hash % table->size;
163  list = table->table + hindex;
164
165  if (plist != NULL)
166    *plist = list;
167
168  prev = NULL;
169  for (p = *list; p != NULL; p = p->next)
170    {
171#ifdef HASH_STATISTICS
172      ++table->hash_compares;
173#endif
174
175      if (p->hash == hash)
176	{
177#ifdef HASH_STATISTICS
178	  ++table->string_compares;
179#endif
180
181	  if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
182	    {
183	      if (prev != NULL)
184		{
185		  prev->next = p->next;
186		  p->next = *list;
187		  *list = p;
188		}
189
190	      return p;
191	    }
192	}
193
194      prev = p;
195    }
196
197  return NULL;
198}
199
200/* Insert an entry into a hash table.  This returns NULL on success.
201   On error, it returns a printable string indicating the error.  It
202   is considered to be an error if the entry already exists in the
203   hash table.  */
204
205const char *
206hash_insert (struct hash_control *table, const char *key, void *val)
207{
208  struct hash_entry *p;
209  struct hash_entry **list;
210  unsigned long hash;
211
212  p = hash_lookup (table, key, strlen (key), &list, &hash);
213  if (p != NULL)
214    return "exists";
215
216#ifdef HASH_STATISTICS
217  ++table->insertions;
218#endif
219
220  p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
221  p->string = key;
222  p->hash = hash;
223  p->data = val;
224
225  p->next = *list;
226  *list = p;
227
228  return NULL;
229}
230
231/* Insert or replace an entry in a hash table.  This returns NULL on
232   success.  On error, it returns a printable string indicating the
233   error.  If an entry already exists, its value is replaced.  */
234
235const char *
236hash_jam (struct hash_control *table, const char *key, void *val)
237{
238  struct hash_entry *p;
239  struct hash_entry **list;
240  unsigned long hash;
241
242  p = hash_lookup (table, key, strlen (key), &list, &hash);
243  if (p != NULL)
244    {
245#ifdef HASH_STATISTICS
246      ++table->replacements;
247#endif
248
249      p->data = val;
250    }
251  else
252    {
253#ifdef HASH_STATISTICS
254      ++table->insertions;
255#endif
256
257      p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
258      p->string = key;
259      p->hash = hash;
260      p->data = val;
261
262      p->next = *list;
263      *list = p;
264    }
265
266  return NULL;
267}
268
269/* Replace an existing entry in a hash table.  This returns the old
270   value stored for the entry.  If the entry is not found in the hash
271   table, this does nothing and returns NULL.  */
272
273void *
274hash_replace (struct hash_control *table, const char *key, void *value)
275{
276  struct hash_entry *p;
277  void *ret;
278
279  p = hash_lookup (table, key, strlen (key), NULL, NULL);
280  if (p == NULL)
281    return NULL;
282
283#ifdef HASH_STATISTICS
284  ++table->replacements;
285#endif
286
287  ret = p->data;
288
289  p->data = value;
290
291  return ret;
292}
293
294/* Find an entry in a hash table, returning its value.  Returns NULL
295   if the entry is not found.  */
296
297void *
298hash_find (struct hash_control *table, const char *key)
299{
300  struct hash_entry *p;
301
302  p = hash_lookup (table, key, strlen (key), NULL, NULL);
303  if (p == NULL)
304    return NULL;
305
306  return p->data;
307}
308
309/* As hash_find, but KEY is of length LEN and is not guaranteed to be
310   NUL-terminated.  */
311
312void *
313hash_find_n (struct hash_control *table, const char *key, size_t len)
314{
315  struct hash_entry *p;
316
317  p = hash_lookup (table, key, len, NULL, NULL);
318  if (p == NULL)
319    return NULL;
320
321  return p->data;
322}
323
324/* Delete an entry from a hash table.  This returns the value stored
325   for that entry, or NULL if there is no such entry.  */
326
327void *
328hash_delete (struct hash_control *table, const char *key, int freeme)
329{
330  struct hash_entry *p;
331  struct hash_entry **list;
332
333  p = hash_lookup (table, key, strlen (key), &list, NULL);
334  if (p == NULL)
335    return NULL;
336
337  if (p != *list)
338    abort ();
339
340#ifdef HASH_STATISTICS
341  ++table->deletions;
342#endif
343
344  *list = p->next;
345
346  if (freeme)
347    obstack_free (&table->memory, p);
348
349  return p->data;
350}
351
352/* Traverse a hash table.  Call the function on every entry in the
353   hash table.  */
354
355void
356hash_traverse (struct hash_control *table,
357	       void (*pfn) (const char *key, void *value))
358{
359  unsigned int i;
360
361  for (i = 0; i < table->size; ++i)
362    {
363      struct hash_entry *p;
364
365      for (p = table->table[i]; p != NULL; p = p->next)
366	(*pfn) (p->string, p->data);
367    }
368}
369
370/* Print hash table statistics on the specified file.  NAME is the
371   name of the hash table, used for printing a header.  */
372
373void
374hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
375		       const char *name ATTRIBUTE_UNUSED,
376		       struct hash_control *table ATTRIBUTE_UNUSED)
377{
378#ifdef HASH_STATISTICS
379  unsigned int i;
380  unsigned long total;
381  unsigned long empty;
382
383  fprintf (f, "%s hash statistics:\n", name);
384  fprintf (f, "\t%lu lookups\n", table->lookups);
385  fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
386  fprintf (f, "\t%lu string comparisons\n", table->string_compares);
387  fprintf (f, "\t%lu insertions\n", table->insertions);
388  fprintf (f, "\t%lu replacements\n", table->replacements);
389  fprintf (f, "\t%lu deletions\n", table->deletions);
390
391  total = 0;
392  empty = 0;
393  for (i = 0; i < table->size; ++i)
394    {
395      struct hash_entry *p;
396
397      if (table->table[i] == NULL)
398	++empty;
399      else
400	{
401	  for (p = table->table[i]; p != NULL; p = p->next)
402	    ++total;
403	}
404    }
405
406  fprintf (f, "\t%g average chain length\n", (double) total / table->size);
407  fprintf (f, "\t%lu empty slots\n", empty);
408#endif
409}
410
411#ifdef TEST
412
413/* This test program is left over from the old hash table code.  */
414
415/* Number of hash tables to maintain (at once) in any testing.  */
416#define TABLES (6)
417
418/* We can have 12 statistics.  */
419#define STATBUFSIZE (12)
420
421/* Display statistics here.  */
422int statbuf[STATBUFSIZE];
423
424/* Human farts here.  */
425char answer[100];
426
427/* We test many hash tables at once.  */
428char *hashtable[TABLES];
429
430/* Points to current hash_control.  */
431char *h;
432char **pp;
433char *p;
434char *name;
435char *value;
436int size;
437int used;
438char command;
439
440/* Number 0:TABLES-1 of current hashed symbol table.  */
441int number;
442
443int
444main ()
445{
446  void applicatee ();
447  void destroy ();
448  char *what ();
449  int *ip;
450
451  number = 0;
452  h = 0;
453  printf ("type h <RETURN> for help\n");
454  for (;;)
455    {
456      printf ("hash_test command: ");
457      gets (answer);
458      command = answer[0];
459      command = TOLOWER (command);	/* Ecch!  */
460      switch (command)
461	{
462	case '#':
463	  printf ("old hash table #=%d.\n", number);
464	  whattable ();
465	  break;
466	case '?':
467	  for (pp = hashtable; pp < hashtable + TABLES; pp++)
468	    {
469	      printf ("address of hash table #%d control block is %xx\n",
470		      pp - hashtable, *pp);
471	    }
472	  break;
473	case 'a':
474	  hash_traverse (h, applicatee);
475	  break;
476	case 'd':
477	  hash_traverse (h, destroy);
478	  hash_die (h);
479	  break;
480	case 'f':
481	  p = hash_find (h, name = what ("symbol"));
482	  printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
483	  break;
484	case 'h':
485	  printf ("# show old, select new default hash table number\n");
486	  printf ("? display all hashtable control block addresses\n");
487	  printf ("a apply a simple display-er to each symbol in table\n");
488	  printf ("d die: destroy hashtable\n");
489	  printf ("f find value of nominated symbol\n");
490	  printf ("h this help\n");
491	  printf ("i insert value into symbol\n");
492	  printf ("j jam value into symbol\n");
493	  printf ("n new hashtable\n");
494	  printf ("r replace a value with another\n");
495	  printf ("s say what %% of table is used\n");
496	  printf ("q exit this program\n");
497	  printf ("x delete a symbol from table, report its value\n");
498	  break;
499	case 'i':
500	  p = hash_insert (h, name = what ("symbol"), value = what ("value"));
501	  if (p)
502	    {
503	      printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
504		      p);
505	    }
506	  break;
507	case 'j':
508	  p = hash_jam (h, name = what ("symbol"), value = what ("value"));
509	  if (p)
510	    {
511	      printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
512	    }
513	  break;
514	case 'n':
515	  h = hashtable[number] = (char *) hash_new ();
516	  break;
517	case 'q':
518	  exit (EXIT_SUCCESS);
519	case 'r':
520	  p = hash_replace (h, name = what ("symbol"), value = what ("value"));
521	  printf ("old value was \"%s\"\n", p ? p : "{}");
522	  break;
523	case 's':
524	  hash_say (h, statbuf, STATBUFSIZE);
525	  for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
526	    {
527	      printf ("%d ", *ip);
528	    }
529	  printf ("\n");
530	  break;
531	case 'x':
532	  p = hash_delete (h, name = what ("symbol"));
533	  printf ("old value was \"%s\"\n", p ? p : "{}");
534	  break;
535	default:
536	  printf ("I can't understand command \"%c\"\n", command);
537	  break;
538	}
539    }
540}
541
542char *
543what (description)
544     char *description;
545{
546  printf ("   %s : ", description);
547  gets (answer);
548  return xstrdup (answer);
549}
550
551void
552destroy (string, value)
553     char *string;
554     char *value;
555{
556  free (string);
557  free (value);
558}
559
560void
561applicatee (string, value)
562     char *string;
563     char *value;
564{
565  printf ("%.20s-%.20s\n", string, value);
566}
567
568/* Determine number: what hash table to use.
569   Also determine h: points to hash_control.  */
570
571void
572whattable ()
573{
574  for (;;)
575    {
576      printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
577      gets (answer);
578      sscanf (answer, "%d", &number);
579      if (number >= 0 && number < TABLES)
580	{
581	  h = hashtable[number];
582	  if (!h)
583	    {
584	      printf ("warning: current hash-table-#%d. has no hash-control\n", number);
585	    }
586	  return;
587	}
588      else
589	{
590	  printf ("invalid hash table number: %d\n", number);
591	}
592    }
593}
594
595#endif /* TEST */
596