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 */