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
   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 /* 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   PTR 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 = size;
  82 }
  83
  84 /* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size().  */
  85 static unsigned long
  86 get_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
 107 struct hash_control *
 108 hash_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
 137 void
 138 hash_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
 153 static struct hash_entry *hash_lookup (struct hash_control *,
 154                                        const char *,
 155                                        struct hash_entry ***,
 156                                        unsigned long *);
 157
 158 static struct hash_entry *
 159 hash_lookup (struct hash_control *table, const char *key,
 160              struct hash_entry ***plist, unsigned long *phash)
 161 {
 162   register unsigned long hash;
 163   unsigned int len;
 164   register const unsigned char *s;
 165   register unsigned int c;
 166   unsigned int index;
 167   struct hash_entry **list;
 168   struct hash_entry *p;
 169   struct hash_entry *prev;
 170
 171 #ifdef HASH_STATISTICS
 172   ++table->lookups;
 173 #endif
 174
 175   hash = 0;
 176   len = 0;
 177   s = (const unsigned char *) key;
 178   while ((c = *s++) != '\0')
 179     {
 180       hash += c + (c << 17);
 181       hash ^= hash >> 2;
 182       ++len;
 183     }
 184   hash += len + (len << 17);
 185   hash ^= hash >> 2;
 186
 187   if (phash != NULL)
 188     *phash = hash;
 189
 190   index = hash % table->size;
 191   list = table->table + index;
 192
 193   if (plist != NULL)
 194     *plist = list;
 195
 196   prev = NULL;
 197   for (p = *list; p != NULL; p = p->next)
 198     {
 199 #ifdef HASH_STATISTICS
 200       ++table->hash_compares;
 201 #endif
 202
 203       if (p->hash == hash)
 204         {
 205 #ifdef HASH_STATISTICS
 206           ++table->string_compares;
 207 #endif
 208
 209           if (strcmp (p->string, key) == 0)
 210             {
 211               if (prev != NULL)
 212                 {
 213                   prev->next = p->next;
 214                   p->next = *list;
 215                   *list = p;
 216                 }
 217
 218               return p;
 219             }
 220         }
 221
 222       prev = p;
 223     }
 224
 225   return NULL;
 226 }
 227
 228 /* Insert an entry into a hash table.  This returns NULL on success.
 229    On error, it returns a printable string indicating the error.  It
 230    is considered to be an error if the entry already exists in the
 231    hash table.  */
 232
 233 const char *
 234 hash_insert (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     return "exists";
 243
 244 #ifdef HASH_STATISTICS
 245   ++table->insertions;
 246 #endif
 247
 248   p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 249   p->string = key;
 250   p->hash = hash;
 251   p->data = value;
 252
 253   p->next = *list;
 254   *list = p;
 255
 256   return NULL;
 257 }
 258
 259 /* Insert or replace an entry in a hash table.  This returns NULL on
 260    success.  On error, it returns a printable string indicating the
 261    error.  If an entry already exists, its value is replaced.  */
 262
 263 const char *
 264 hash_jam (struct hash_control *table, const char *key, PTR value)
 265 {
 266   struct hash_entry *p;
 267   struct hash_entry **list;
 268   unsigned long hash;
 269
 270   p = hash_lookup (table, key, &list, &hash);
 271   if (p != NULL)
 272     {
 273 #ifdef HASH_STATISTICS
 274       ++table->replacements;
 275 #endif
 276
 277       p->data = value;
 278     }
 279   else
 280     {
 281 #ifdef HASH_STATISTICS
 282       ++table->insertions;
 283 #endif
 284
 285       p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 286       p->string = key;
 287       p->hash = hash;
 288       p->data = value;
 289
 290       p->next = *list;
 291       *list = p;
 292     }
 293
 294   return NULL;
 295 }
 296
 297 /* Find an entry in a hash table, returning its value.  Returns NULL
 298    if the entry is not found.  */
 299
 300 PTR
 301 hash_find (struct hash_control *table, const char *key)
 302 {
 303   struct hash_entry *p;
 304
 305   p = hash_lookup (table, key, NULL, NULL);
 306   if (p == NULL)
 307     return NULL;
 308
 309   return p->data;
 310 }
 311
 312 /* Traverse a hash table.  Call the function on every entry in the
 313    hash table.  */
 314
 315 void
 316 hash_traverse (struct hash_control *table,
 317                void (*pfn) (const char *key, PTR value))
 318 {
 319   unsigned int i;
 320
 321   for (i = 0; i < table->size; ++i)
 322     {
 323       struct hash_entry *p;
 324
 325       for (p = table->table[i]; p != NULL; p = p->next)
 326         (*pfn) (p->string, p->data);
 327     }
 328 }
 329
 330 /* Print hash table statistics on the specified file.  NAME is the
 331    name of the hash table, used for printing a header.  */
 332
 333 void
 334 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
 335                        const char *name ATTRIBUTE_UNUSED,
 336                        struct hash_control *table ATTRIBUTE_UNUSED)
 337 {
 338 #ifdef HASH_STATISTICS
 339   unsigned int i;
 340   unsigned long total;
 341   unsigned long empty;
 342
 343   fprintf (f, "%s hash statistics:\n", name);
 344   fprintf (f, "\t%lu lookups\n", table->lookups);
 345   fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
 346   fprintf (f, "\t%lu string comparisons\n", table->string_compares);
 347   fprintf (f, "\t%lu insertions\n", table->insertions);
 348   fprintf (f, "\t%lu replacements\n", table->replacements);
 349   fprintf (f, "\t%lu deletions\n", table->deletions);
 350
 351   total = 0;
 352   empty = 0;
 353   for (i = 0; i < table->size; ++i)
 354     {
 355       struct hash_entry *p;
 356
 357       if (table->table[i] == NULL)
 358         ++empty;
 359       else
 360         {
 361           for (p = table->table[i]; p != NULL; p = p->next)
 362             ++total;
 363         }
 364     }
 365
 366   fprintf (f, "\t%g average chain length\n", (double) total / table->size);
 367   fprintf (f, "\t%lu empty slots\n", empty);
 368 #endif
 369 }
 370 \f
 371 #ifdef TEST
 372
 373 /* This test program is left over from the old hash table code.  */
 374
 375 /* Number of hash tables to maintain (at once) in any testing.  */
 376 #define TABLES (6)
 377
 378 /* We can have 12 statistics.  */
 379 #define STATBUFSIZE (12)
 380
 381 /* Display statistics here.  */
 382 int statbuf[STATBUFSIZE];
 383
 384 /* Human farts here.  */
 385 char answer[100];
 386
 387 /* We test many hash tables at once.  */
 388 char *hashtable[TABLES];
 389
 390 /* Points to current hash_control.  */
 391 char *h;
 392 char **pp;
 393 char *p;
 394 char *name;
 395 char *value;
 396 int size;
 397 int used;
 398 char command;
 399
 400 /* Number 0:TABLES-1 of current hashed symbol table.  */
 401 int number;
 402
 403 int
 404 main ()
 405 {
 406   void applicatee ();
 407   void destroy ();
 408   char *what ();
 409   int *ip;
 410
 411   number = 0;
 412   h = 0;
 413   printf ("type h <RETURN> for help\n");
 414   for (;;)
 415     {
 416       printf ("hash_test command: ");
 417       gets (answer);
 418       command = answer[0];
 419       command = TOLOWER (command);      /* Ecch!  */
 420       switch (command)
 421         {
 422         case '#':
 423           printf ("old hash table #=%d.\n", number);
 424           whattable ();
 425           break;
 426         case '?':
 427           for (pp = hashtable; pp < hashtable + TABLES; pp++)
 428             {
 429               printf ("address of hash table #%d control block is %xx\n",
 430                       pp - hashtable, *pp);
 431             }
 432           break;
 433         case 'a':
 434           hash_traverse (h, applicatee);
 435           break;
 436         case 'd':
 437           hash_traverse (h, destroy);
 438           hash_die (h);
 439           break;
 440         case 'f':
 441           p = hash_find (h, name = what ("symbol"));
 442           printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
 443           break;
 444         case 'h':
 445           printf ("# show old, select new default hash table number\n");
 446           printf ("? display all hashtable control block addresses\n");
 447           printf ("a apply a simple display-er to each symbol in table\n");
 448           printf ("d die: destroy hashtable\n");
 449           printf ("f find value of nominated symbol\n");
 450           printf ("h this help\n");
 451           printf ("i insert value into symbol\n");
 452           printf ("j jam value into symbol\n");
 453           printf ("n new hashtable\n");
 454           printf ("r replace a value with another\n");
 455           printf ("s say what %% of table is used\n");
 456           printf ("q exit this program\n");
 457           printf ("x delete a symbol from table, report its value\n");
 458           break;
 459         case 'i':
 460           p = hash_insert (h, name = what ("symbol"), value = what ("value"));
 461           if (p)
 462             {
 463               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
 464                       p);
 465             }
 466           break;
 467         case 'j':
 468           p = hash_jam (h, name = what ("symbol"), value = what ("value"));
 469           if (p)
 470             {
 471               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
 472             }
 473           break;
 474         case 'n':
 475           h = hashtable[number] = (char *) hash_new ();
 476           break;
 477         case 'q':
 478           exit (EXIT_SUCCESS);
 479         case 'r':
 480           p = hash_replace (h, name = what ("symbol"), value = what ("value"));
 481           printf ("old value was \"%s\"\n", p ? p : "{}");
 482           break;
 483         case 's':
 484           hash_say (h, statbuf, STATBUFSIZE);
 485           for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
 486             {
 487               printf ("%d ", *ip);
 488             }
 489           printf ("\n");
 490           break;
 491         case 'x':
 492           p = hash_delete (h, name = what ("symbol"));
 493           printf ("old value was \"%s\"\n", p ? p : "{}");
 494           break;
 495         default:
 496           printf ("I can't understand command \"%c\"\n", command);
 497           break;
 498         }
 499     }
 500 }
 501
 502 char *
 503 what (description)
 504      char *description;
 505 {
 506   printf ("   %s : ", description);
 507   gets (answer);
 508   return xstrdup (answer);
 509 }
 510
 511 void
 512 destroy (string, value)
 513      char *string;
 514      char *value;
 515 {
 516   free (string);
 517   free (value);
 518 }
 519
 520 void
 521 applicatee (string, value)
 522      char *string;
 523      char *value;
 524 {
 525   printf ("%.20s-%.20s\n", string, value);
 526 }
 527
 528 /* Determine number: what hash table to use.
 529    Also determine h: points to hash_control.  */
 530
 531 void
 532 whattable ()
 533 {
 534   for (;;)
 535     {
 536       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 537       gets (answer);
 538       sscanf (answer, "%d", &number);
 539       if (number >= 0 && number < TABLES)
 540         {
 541           h = hashtable[number];
 542           if (!h)
 543             {
 544               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 545             }
 546           return;
 547         }
 548       else
 549         {
 550           printf ("invalid hash table number: %d\n", number);
 551         }
 552     }
 553 }
 554
 555 #endif /* TEST */