gas/hash.c

   1 /* hash.c -- gas hash table code
   2    Copyright (C) 1987-2017 Free Software Foundation, Inc.
   3
   4    This file is part of GAS, the GNU Assembler.
   5
   6    GAS is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 3, or (at your option)
   9    any later version.
  10
  11    GAS is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with GAS; see the file COPYING.  If not, write to the Free
  18    Software Foundation, 51 Franklin Street - Fifth Floor, Boston, MA
  19    02110-1301, USA.  */
  20
  21 /* This version of the hash table code is a wholescale replacement of
  22    the old hash table code, which was fairly bad.  This is based on
  23    the hash table code in BFD, but optimized slightly for the
  24    assembler.  The assembler does not need to derive structures that
  25    are stored in the hash table.  Instead, it always stores a pointer.
  26    The assembler uses the hash table mostly to store symbols, and we
  27    don't need to confuse the symbol structure with a hash table
  28    structure.  */
  29
  30 #include "as.h"
  31 #include "safe-ctype.h"
  32 #include "obstack.h"
  33
  34 /* An entry in a hash table.  */
  35
  36 struct hash_entry {
  37   /* Next entry for this hash code.  */
  38   struct hash_entry *next;
  39   /* String being hashed.  */
  40   const char *string;
  41   /* Hash code.  This is the full hash code, not the index into the
  42      table.  */
  43   unsigned long hash;
  44   /* Pointer being stored in the hash table.  */
  45   void *data;
  46 };
  47
  48 /* A hash table.  */
  49
  50 struct hash_control {
  51   /* The hash array.  */
  52   struct hash_entry **table;
  53   /* The number of slots in the hash table.  */
  54   unsigned int size;
  55   /* An obstack for this hash table.  */
  56   struct obstack memory;
  57
  58 #ifdef HASH_STATISTICS
  59   /* Statistics.  */
  60   unsigned long lookups;
  61   unsigned long hash_compares;
  62   unsigned long string_compares;
  63   unsigned long insertions;
  64   unsigned long replacements;
  65   unsigned long deletions;
  66 #endif /* HASH_STATISTICS */
  67 };
  68
  69 /* The default number of entries to use when creating a hash table.
  70    Note this value can be reduced to 4051 by using the command line
  71    switch --reduce-memory-overheads, or set to other values by using
  72    the --hash-size=<NUMBER> switch.  */
  73
  74 static unsigned long gas_hash_table_size = 65537;
  75
  76 void
  77 set_gas_hash_table_size (unsigned long size)
  78 {
  79   gas_hash_table_size = bfd_hash_set_default_size (size);
  80 }
  81
  82 /* Create a hash table.  This return a control block.  */
  83
  84 struct hash_control *
  85 hash_new_sized (unsigned long size)
  86 {
  87   unsigned long alloc;
  88   struct hash_control *ret;
  89
  90   ret = XNEW (struct hash_control);
  91   obstack_begin (&ret->memory, chunksize);
  92   alloc = size * sizeof (struct hash_entry *);
  93   ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
  94   memset (ret->table, 0, alloc);
  95   ret->size = size;
  96
  97 #ifdef HASH_STATISTICS
  98   ret->lookups = 0;
  99   ret->hash_compares = 0;
 100   ret->string_compares = 0;
 101   ret->insertions = 0;
 102   ret->replacements = 0;
 103   ret->deletions = 0;
 104 #endif
 105
 106   return ret;
 107 }
 108
 109 struct hash_control *
 110 hash_new (void)
 111 {
 112   return hash_new_sized (gas_hash_table_size);
 113 }
 114
 115 /* Delete a hash table, freeing all allocated memory.  */
 116
 117 void
 118 hash_die (struct hash_control *table)
 119 {
 120   obstack_free (&table->memory, 0);
 121   free (table);
 122 }
 123
 124 /* Look up a string in a hash table.  This returns a pointer to the
 125    hash_entry, or NULL if the string is not in the table.  If PLIST is
 126    not NULL, this sets *PLIST to point to the start of the list which
 127    would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
 128    to the hash code for KEY.
 129
 130    Each time we look up a string, we move it to the start of the list
 131    for its hash code, to take advantage of referential locality.  */
 132
 133 static struct hash_entry *
 134 hash_lookup (struct hash_control *table, const char *key, size_t len,
 135              struct hash_entry ***plist, unsigned long *phash)
 136 {
 137   unsigned long hash;
 138   size_t n;
 139   unsigned int c;
 140   unsigned int hindex;
 141   struct hash_entry **list;
 142   struct hash_entry *p;
 143   struct hash_entry *prev;
 144
 145 #ifdef HASH_STATISTICS
 146   ++table->lookups;
 147 #endif
 148
 149   hash = 0;
 150   for (n = 0; n < len; n++)
 151     {
 152       c = key[n];
 153       hash += c + (c << 17);
 154       hash ^= hash >> 2;
 155     }
 156   hash += len + (len << 17);
 157   hash ^= hash >> 2;
 158
 159   if (phash != NULL)
 160     *phash = hash;
 161
 162   hindex = hash % table->size;
 163   list = table->table + hindex;
 164
 165   if (plist != NULL)
 166     *plist = list;
 167
 168   prev = NULL;
 169   for (p = *list; p != NULL; p = p->next)
 170     {
 171 #ifdef HASH_STATISTICS
 172       ++table->hash_compares;
 173 #endif
 174
 175       if (p->hash == hash)
 176         {
 177 #ifdef HASH_STATISTICS
 178           ++table->string_compares;
 179 #endif
 180
 181           if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
 182             {
 183               if (prev != NULL)
 184                 {
 185                   prev->next = p->next;
 186                   p->next = *list;
 187                   *list = p;
 188                 }
 189
 190               return p;
 191             }
 192         }
 193
 194       prev = p;
 195     }
 196
 197   return NULL;
 198 }
 199
 200 /* Insert an entry into a hash table.  This returns NULL on success.
 201    On error, it returns a printable string indicating the error.  It
 202    is considered to be an error if the entry already exists in the
 203    hash table.  */
 204
 205 const char *
 206 hash_insert (struct hash_control *table, const char *key, void *val)
 207 {
 208   struct hash_entry *p;
 209   struct hash_entry **list;
 210   unsigned long hash;
 211
 212   p = hash_lookup (table, key, strlen (key), &list, &hash);
 213   if (p != NULL)
 214     return "exists";
 215
 216 #ifdef HASH_STATISTICS
 217   ++table->insertions;
 218 #endif
 219
 220   p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 221   p->string = key;
 222   p->hash = hash;
 223   p->data = val;
 224
 225   p->next = *list;
 226   *list = p;
 227
 228   return NULL;
 229 }
 230
 231 /* Insert or replace an entry in a hash table.  This returns NULL on
 232    success.  On error, it returns a printable string indicating the
 233    error.  If an entry already exists, its value is replaced.  */
 234
 235 const char *
 236 hash_jam (struct hash_control *table, const char *key, void *val)
 237 {
 238   struct hash_entry *p;
 239   struct hash_entry **list;
 240   unsigned long hash;
 241
 242   p = hash_lookup (table, key, strlen (key), &list, &hash);
 243   if (p != NULL)
 244     {
 245 #ifdef HASH_STATISTICS
 246       ++table->replacements;
 247 #endif
 248
 249       p->data = val;
 250     }
 251   else
 252     {
 253 #ifdef HASH_STATISTICS
 254       ++table->insertions;
 255 #endif
 256
 257       p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 258       p->string = key;
 259       p->hash = hash;
 260       p->data = val;
 261
 262       p->next = *list;
 263       *list = p;
 264     }
 265
 266   return NULL;
 267 }
 268
 269 /* Replace an existing entry in a hash table.  This returns the old
 270    value stored for the entry.  If the entry is not found in the hash
 271    table, this does nothing and returns NULL.  */
 272
 273 void *
 274 hash_replace (struct hash_control *table, const char *key, void *value)
 275 {
 276   struct hash_entry *p;
 277   void *ret;
 278
 279   p = hash_lookup (table, key, strlen (key), NULL, NULL);
 280   if (p == NULL)
 281     return NULL;
 282
 283 #ifdef HASH_STATISTICS
 284   ++table->replacements;
 285 #endif
 286
 287   ret = p->data;
 288
 289   p->data = value;
 290
 291   return ret;
 292 }
 293
 294 /* Find an entry in a hash table, returning its value.  Returns NULL
 295    if the entry is not found.  */
 296
 297 void *
 298 hash_find (struct hash_control *table, const char *key)
 299 {
 300   struct hash_entry *p;
 301
 302   p = hash_lookup (table, key, strlen (key), NULL, NULL);
 303   if (p == NULL)
 304     return NULL;
 305
 306   return p->data;
 307 }
 308
 309 /* As hash_find, but KEY is of length LEN and is not guaranteed to be
 310    NUL-terminated.  */
 311
 312 void *
 313 hash_find_n (struct hash_control *table, const char *key, size_t len)
 314 {
 315   struct hash_entry *p;
 316
 317   p = hash_lookup (table, key, len, NULL, NULL);
 318   if (p == NULL)
 319     return NULL;
 320
 321   return p->data;
 322 }
 323
 324 /* Delete an entry from a hash table.  This returns the value stored
 325    for that entry, or NULL if there is no such entry.  */
 326
 327 void *
 328 hash_delete (struct hash_control *table, const char *key, int freeme)
 329 {
 330   struct hash_entry *p;
 331   struct hash_entry **list;
 332
 333   p = hash_lookup (table, key, strlen (key), &list, NULL);
 334   if (p == NULL)
 335     return NULL;
 336
 337   if (p != *list)
 338     abort ();
 339
 340 #ifdef HASH_STATISTICS
 341   ++table->deletions;
 342 #endif
 343
 344   *list = p->next;
 345
 346   if (freeme)
 347     obstack_free (&table->memory, p);
 348
 349   return p->data;
 350 }
 351
 352 /* Traverse a hash table.  Call the function on every entry in the
 353    hash table.  */
 354
 355 void
 356 hash_traverse (struct hash_control *table,
 357                void (*pfn) (const char *key, void *value))
 358 {
 359   unsigned int i;
 360
 361   for (i = 0; i < table->size; ++i)
 362     {
 363       struct hash_entry *p;
 364
 365       for (p = table->table[i]; p != NULL; p = p->next)
 366         (*pfn) (p->string, p->data);
 367     }
 368 }
 369
 370 /* Print hash table statistics on the specified file.  NAME is the
 371    name of the hash table, used for printing a header.  */
 372
 373 void
 374 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
 375                        const char *name ATTRIBUTE_UNUSED,
 376                        struct hash_control *table ATTRIBUTE_UNUSED)
 377 {
 378 #ifdef HASH_STATISTICS
 379   unsigned int i;
 380   unsigned long total;
 381   unsigned long empty;
 382
 383   fprintf (f, "%s hash statistics:\n", name);
 384   fprintf (f, "\t%lu lookups\n", table->lookups);
 385   fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
 386   fprintf (f, "\t%lu string comparisons\n", table->string_compares);
 387   fprintf (f, "\t%lu insertions\n", table->insertions);
 388   fprintf (f, "\t%lu replacements\n", table->replacements);
 389   fprintf (f, "\t%lu deletions\n", table->deletions);
 390
 391   total = 0;
 392   empty = 0;
 393   for (i = 0; i < table->size; ++i)
 394     {
 395       struct hash_entry *p;
 396
 397       if (table->table[i] == NULL)
 398         ++empty;
 399       else
 400         {
 401           for (p = table->table[i]; p != NULL; p = p->next)
 402             ++total;
 403         }
 404     }
 405
 406   fprintf (f, "\t%g average chain length\n", (double) total / table->size);
 407   fprintf (f, "\t%lu empty slots\n", empty);
 408 #endif
 409 }
 410 \f
 411 #ifdef TEST
 412
 413 /* This test program is left over from the old hash table code.  */
 414
 415 /* Number of hash tables to maintain (at once) in any testing.  */
 416 #define TABLES (6)
 417
 418 /* We can have 12 statistics.  */
 419 #define STATBUFSIZE (12)
 420
 421 /* Display statistics here.  */
 422 int statbuf[STATBUFSIZE];
 423
 424 /* Human farts here.  */
 425 char answer[100];
 426
 427 /* We test many hash tables at once.  */
 428 char *hashtable[TABLES];
 429
 430 /* Points to current hash_control.  */
 431 char *h;
 432 char **pp;
 433 char *p;
 434 char *name;
 435 char *value;
 436 int size;
 437 int used;
 438 char command;
 439
 440 /* Number 0:TABLES-1 of current hashed symbol table.  */
 441 int number;
 442
 443 int
 444 main ()
 445 {
 446   void applicatee ();
 447   void destroy ();
 448   char *what ();
 449   int *ip;
 450
 451   number = 0;
 452   h = 0;
 453   printf ("type h <RETURN> for help\n");
 454   for (;;)
 455     {
 456       printf ("hash_test command: ");
 457       gets (answer);
 458       command = answer[0];
 459       command = TOLOWER (command);      /* Ecch!  */
 460       switch (command)
 461         {
 462         case '#':
 463           printf ("old hash table #=%d.\n", number);
 464           whattable ();
 465           break;
 466         case '?':
 467           for (pp = hashtable; pp < hashtable + TABLES; pp++)
 468             {
 469               printf ("address of hash table #%d control block is %xx\n",
 470                       pp - hashtable, *pp);
 471             }
 472           break;
 473         case 'a':
 474           hash_traverse (h, applicatee);
 475           break;
 476         case 'd':
 477           hash_traverse (h, destroy);
 478           hash_die (h);
 479           break;
 480         case 'f':
 481           p = hash_find (h, name = what ("symbol"));
 482           printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
 483           break;
 484         case 'h':
 485           printf ("# show old, select new default hash table number\n");
 486           printf ("? display all hashtable control block addresses\n");
 487           printf ("a apply a simple display-er to each symbol in table\n");
 488           printf ("d die: destroy hashtable\n");
 489           printf ("f find value of nominated symbol\n");
 490           printf ("h this help\n");
 491           printf ("i insert value into symbol\n");
 492           printf ("j jam value into symbol\n");
 493           printf ("n new hashtable\n");
 494           printf ("r replace a value with another\n");
 495           printf ("s say what %% of table is used\n");
 496           printf ("q exit this program\n");
 497           printf ("x delete a symbol from table, report its value\n");
 498           break;
 499         case 'i':
 500           p = hash_insert (h, name = what ("symbol"), value = what ("value"));
 501           if (p)
 502             {
 503               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
 504                       p);
 505             }
 506           break;
 507         case 'j':
 508           p = hash_jam (h, name = what ("symbol"), value = what ("value"));
 509           if (p)
 510             {
 511               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
 512             }
 513           break;
 514         case 'n':
 515           h = hashtable[number] = (char *) hash_new ();
 516           break;
 517         case 'q':
 518           exit (EXIT_SUCCESS);
 519         case 'r':
 520           p = hash_replace (h, name = what ("symbol"), value = what ("value"));
 521           printf ("old value was \"%s\"\n", p ? p : "{}");
 522           break;
 523         case 's':
 524           hash_say (h, statbuf, STATBUFSIZE);
 525           for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
 526             {
 527               printf ("%d ", *ip);
 528             }
 529           printf ("\n");
 530           break;
 531         case 'x':
 532           p = hash_delete (h, name = what ("symbol"));
 533           printf ("old value was \"%s\"\n", p ? p : "{}");
 534           break;
 535         default:
 536           printf ("I can't understand command \"%c\"\n", command);
 537           break;
 538         }
 539     }
 540 }
 541
 542 char *
 543 what (description)
 544      char *description;
 545 {
 546   printf ("   %s : ", description);
 547   gets (answer);
 548   return xstrdup (answer);
 549 }
 550
 551 void
 552 destroy (string, value)
 553      char *string;
 554      char *value;
 555 {
 556   free (string);
 557   free (value);
 558 }
 559
 560 void
 561 applicatee (string, value)
 562      char *string;
 563      char *value;
 564 {
 565   printf ("%.20s-%.20s\n", string, value);
 566 }
 567
 568 /* Determine number: what hash table to use.
 569    Also determine h: points to hash_control.  */
 570
 571 void
 572 whattable ()
 573 {
 574   for (;;)
 575     {
 576       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 577       gets (answer);
 578       sscanf (answer, "%d", &number);
 579       if (number >= 0 && number < TABLES)
 580         {
 581           h = hashtable[number];
 582           if (!h)
 583             {
 584               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 585             }
 586           return;
 587         }
 588       else
 589         {
 590           printf ("invalid hash table number: %d\n", number);
 591         }
 592     }
 593 }
 594
 595 #endif /* TEST */