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