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