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