Merge branch 'vendor/GCC50'
[dragonfly.git] / contrib / binutils-2.25 / gas / hash.c
1 /* hash.c -- gas hash table code
2    Copyright (C) 1987-2014 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
36 struct 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
50 struct 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
74 static unsigned long gas_hash_table_size = 65537;
75
76 void
77 set_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
84 struct hash_control *
85 hash_new_sized (unsigned long size)
86 {
87   unsigned long alloc;
88   struct hash_control *ret;
89
90   ret = (struct hash_control *) xmalloc (sizeof *ret);
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
109 struct hash_control *
110 hash_new (void)
111 {
112   return hash_new_sized (gas_hash_table_size);
113 }
114
115 /* Delete a hash table, freeing all allocated memory.  */
116
117 void
118 hash_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
133 static struct hash_entry *
134 hash_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
205 const char *
206 hash_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
235 const char *
236 hash_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
273 void *
274 hash_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
297 void *
298 hash_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
312 void *
313 hash_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
327 void *
328 hash_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
355 void
356 hash_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
373 void
374 hash_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 \f
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.  */
422 int statbuf[STATBUFSIZE];
423
424 /* Human farts here.  */
425 char answer[100];
426
427 /* We test many hash tables at once.  */
428 char *hashtable[TABLES];
429
430 /* Points to current hash_control.  */
431 char *h;
432 char **pp;
433 char *p;
434 char *name;
435 char *value;
436 int size;
437 int used;
438 char command;
439
440 /* Number 0:TABLES-1 of current hashed symbol table.  */
441 int number;
442
443 int
444 main ()
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
542 char *
543 what (description)
544      char *description;
545 {
546   printf ("   %s : ", description);
547   gets (answer);
548   return xstrdup (answer);
549 }
550
551 void
552 destroy (string, value)
553      char *string;
554      char *value;
555 {
556   free (string);
557   free (value);
558 }
559
560 void
561 applicatee (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
571 void
572 whattable ()
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 */