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, 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   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 /* Replace an existing entry in a hash table.  This returns the old
 298    value stored for the entry.  If the entry is not found in the hash
 299    table, this does nothing and returns NULL.  */
 300
 301 PTR
 302 hash_replace (struct hash_control *table, const char *key, PTR value)
 303 {
 304   struct hash_entry *p;
 305   PTR ret;
 306
 307   p = hash_lookup (table, key, NULL, NULL);
 308   if (p == NULL)
 309     return NULL;
 310
 311 #ifdef HASH_STATISTICS
 312   ++table->replacements;
 313 #endif
 314
 315   ret = p->data;
 316
 317   p->data = value;
 318
 319   return ret;
 320 }
 321
 322 /* Find an entry in a hash table, returning its value.  Returns NULL
 323    if the entry is not found.  */
 324
 325 PTR
 326 hash_find (struct hash_control *table, const char *key)
 327 {
 328   struct hash_entry *p;
 329
 330   p = hash_lookup (table, key, NULL, NULL);
 331   if (p == NULL)
 332     return NULL;
 333
 334   return p->data;
 335 }
 336
 337 /* Delete an entry from a hash table.  This returns the value stored
 338    for that entry, or NULL if there is no such entry.  */
 339
 340 PTR
 341 hash_delete (struct hash_control *table, const char *key)
 342 {
 343   struct hash_entry *p;
 344   struct hash_entry **list;
 345
 346   p = hash_lookup (table, key, &list, NULL);
 347   if (p == NULL)
 348     return NULL;
 349
 350   if (p != *list)
 351     abort ();
 352
 353 #ifdef HASH_STATISTICS
 354   ++table->deletions;
 355 #endif
 356
 357   *list = p->next;
 358
 359   /* Note that we never reclaim the memory for this entry.  If gas
 360      ever starts deleting hash table entries in a big way, this will
 361      have to change.  */
 362
 363   return p->data;
 364 }
 365
 366 /* Traverse a hash table.  Call the function on every entry in the
 367    hash table.  */
 368
 369 void
 370 hash_traverse (struct hash_control *table,
 371                void (*pfn) (const char *key, PTR value))
 372 {
 373   unsigned int i;
 374
 375   for (i = 0; i < table->size; ++i)
 376     {
 377       struct hash_entry *p;
 378
 379       for (p = table->table[i]; p != NULL; p = p->next)
 380         (*pfn) (p->string, p->data);
 381     }
 382 }
 383
 384 /* Print hash table statistics on the specified file.  NAME is the
 385    name of the hash table, used for printing a header.  */
 386
 387 void
 388 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
 389                        const char *name ATTRIBUTE_UNUSED,
 390                        struct hash_control *table ATTRIBUTE_UNUSED)
 391 {
 392 #ifdef HASH_STATISTICS
 393   unsigned int i;
 394   unsigned long total;
 395   unsigned long empty;
 396
 397   fprintf (f, "%s hash statistics:\n", name);
 398   fprintf (f, "\t%lu lookups\n", table->lookups);
 399   fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
 400   fprintf (f, "\t%lu string comparisons\n", table->string_compares);
 401   fprintf (f, "\t%lu insertions\n", table->insertions);
 402   fprintf (f, "\t%lu replacements\n", table->replacements);
 403   fprintf (f, "\t%lu deletions\n", table->deletions);
 404
 405   total = 0;
 406   empty = 0;
 407   for (i = 0; i < table->size; ++i)
 408     {
 409       struct hash_entry *p;
 410
 411       if (table->table[i] == NULL)
 412         ++empty;
 413       else
 414         {
 415           for (p = table->table[i]; p != NULL; p = p->next)
 416             ++total;
 417         }
 418     }
 419
 420   fprintf (f, "\t%g average chain length\n", (double) total / table->size);
 421   fprintf (f, "\t%lu empty slots\n", empty);
 422 #endif
 423 }
 424 \f
 425 #ifdef TEST
 426
 427 /* This test program is left over from the old hash table code.  */
 428
 429 /* Number of hash tables to maintain (at once) in any testing.  */
 430 #define TABLES (6)
 431
 432 /* We can have 12 statistics.  */
 433 #define STATBUFSIZE (12)
 434
 435 /* Display statistics here.  */
 436 int statbuf[STATBUFSIZE];
 437
 438 /* Human farts here.  */
 439 char answer[100];
 440
 441 /* We test many hash tables at once.  */
 442 char *hashtable[TABLES];
 443
 444 /* Points to current hash_control.  */
 445 char *h;
 446 char **pp;
 447 char *p;
 448 char *name;
 449 char *value;
 450 int size;
 451 int used;
 452 char command;
 453
 454 /* Number 0:TABLES-1 of current hashed symbol table.  */
 455 int number;
 456
 457 int
 458 main ()
 459 {
 460   void applicatee ();
 461   void destroy ();
 462   char *what ();
 463   int *ip;
 464
 465   number = 0;
 466   h = 0;
 467   printf ("type h <RETURN> for help\n");
 468   for (;;)
 469     {
 470       printf ("hash_test command: ");
 471       gets (answer);
 472       command = answer[0];
 473       command = TOLOWER (command);      /* Ecch!  */
 474       switch (command)
 475         {
 476         case '#':
 477           printf ("old hash table #=%d.\n", number);
 478           whattable ();
 479           break;
 480         case '?':
 481           for (pp = hashtable; pp < hashtable + TABLES; pp++)
 482             {
 483               printf ("address of hash table #%d control block is %xx\n",
 484                       pp - hashtable, *pp);
 485             }
 486           break;
 487         case 'a':
 488           hash_traverse (h, applicatee);
 489           break;
 490         case 'd':
 491           hash_traverse (h, destroy);
 492           hash_die (h);
 493           break;
 494         case 'f':
 495           p = hash_find (h, name = what ("symbol"));
 496           printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
 497           break;
 498         case 'h':
 499           printf ("# show old, select new default hash table number\n");
 500           printf ("? display all hashtable control block addresses\n");
 501           printf ("a apply a simple display-er to each symbol in table\n");
 502           printf ("d die: destroy hashtable\n");
 503           printf ("f find value of nominated symbol\n");
 504           printf ("h this help\n");
 505           printf ("i insert value into symbol\n");
 506           printf ("j jam value into symbol\n");
 507           printf ("n new hashtable\n");
 508           printf ("r replace a value with another\n");
 509           printf ("s say what %% of table is used\n");
 510           printf ("q exit this program\n");
 511           printf ("x delete a symbol from table, report its value\n");
 512           break;
 513         case 'i':
 514           p = hash_insert (h, name = what ("symbol"), value = what ("value"));
 515           if (p)
 516             {
 517               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
 518                       p);
 519             }
 520           break;
 521         case 'j':
 522           p = hash_jam (h, name = what ("symbol"), value = what ("value"));
 523           if (p)
 524             {
 525               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
 526             }
 527           break;
 528         case 'n':
 529           h = hashtable[number] = (char *) hash_new ();
 530           break;
 531         case 'q':
 532           exit (EXIT_SUCCESS);
 533         case 'r':
 534           p = hash_replace (h, name = what ("symbol"), value = what ("value"));
 535           printf ("old value was \"%s\"\n", p ? p : "{}");
 536           break;
 537         case 's':
 538           hash_say (h, statbuf, STATBUFSIZE);
 539           for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
 540             {
 541               printf ("%d ", *ip);
 542             }
 543           printf ("\n");
 544           break;
 545         case 'x':
 546           p = hash_delete (h, name = what ("symbol"));
 547           printf ("old value was \"%s\"\n", p ? p : "{}");
 548           break;
 549         default:
 550           printf ("I can't understand command \"%c\"\n", command);
 551           break;
 552         }
 553     }
 554 }
 555
 556 char *
 557 what (description)
 558      char *description;
 559 {
 560   printf ("   %s : ", description);
 561   gets (answer);
 562   return xstrdup (answer);
 563 }
 564
 565 void
 566 destroy (string, value)
 567      char *string;
 568      char *value;
 569 {
 570   free (string);
 571   free (value);
 572 }
 573
 574 void
 575 applicatee (string, value)
 576      char *string;
 577      char *value;
 578 {
 579   printf ("%.20s-%.20s\n", string, value);
 580 }
 581
 582 /* Determine number: what hash table to use.
 583    Also determine h: points to hash_control.  */
 584
 585 void
 586 whattable ()
 587 {
 588   for (;;)
 589     {
 590       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 591       gets (answer);
 592       sscanf (answer, "%d", &number);
 593       if (number >= 0 && number < TABLES)
 594         {
 595           h = hashtable[number];
 596           if (!h)
 597             {
 598               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 599             }
 600           return;
 601         }
 602       else
 603         {
 604           printf ("invalid hash table number: %d\n", number);
 605         }
 606     }
 607 }
 608
 609 #endif /* TEST */