gas/hash.c

   1 /* hash.c -- gas hash table code
   2    Copyright (C) 1987-2020 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
 411 /* Insert ELEMENT into HTAB.  If the element exists, it is overwritten.  */
 412
 413 void
 414 htab_insert (htab_t htab, PTR element)
 415 {
 416   void **slot = htab_find_slot (htab, element, INSERT);
 417   if (slot != NULL && htab->del_f)
 418     (*htab->del_f) (*slot);
 419
 420   *slot = element;
 421 }
 422
 423 /* Print statistics about a hash table.  */
 424
 425 void
 426 htab_print_statistics (FILE *f, const char *name, htab_t table)
 427 {
 428   fprintf (f, "%s hash statistics:\n", name);
 429   fprintf (f, "\t%u searches\n", table->searches);
 430   fprintf (f, "\t%u collisions\n", table->collisions);
 431   fprintf (f, "\t%lu elements\n", (unsigned long) htab_elements (table));
 432   fprintf (f, "\t%lu table size\n", (unsigned long) htab_size (table));
 433 }
 434 \f
 435 #ifdef TEST
 436
 437 /* This test program is left over from the old hash table code.  */
 438
 439 /* Number of hash tables to maintain (at once) in any testing.  */
 440 #define TABLES (6)
 441
 442 /* We can have 12 statistics.  */
 443 #define STATBUFSIZE (12)
 444
 445 /* Display statistics here.  */
 446 int statbuf[STATBUFSIZE];
 447
 448 /* Human farts here.  */
 449 char answer[100];
 450
 451 /* We test many hash tables at once.  */
 452 char *hashtable[TABLES];
 453
 454 /* Points to current hash_control.  */
 455 char *h;
 456 char **pp;
 457 char *p;
 458 char *name;
 459 char *value;
 460 int size;
 461 int used;
 462 char command;
 463
 464 /* Number 0:TABLES-1 of current hashed symbol table.  */
 465 int number;
 466
 467 int
 468 main ()
 469 {
 470   void applicatee ();
 471   void destroy ();
 472   char *what ();
 473   int *ip;
 474
 475   number = 0;
 476   h = 0;
 477   printf ("type h <RETURN> for help\n");
 478   for (;;)
 479     {
 480       printf ("hash_test command: ");
 481       gets (answer);
 482       command = answer[0];
 483       command = TOLOWER (command);      /* Ecch!  */
 484       switch (command)
 485         {
 486         case '#':
 487           printf ("old hash table #=%d.\n", number);
 488           whattable ();
 489           break;
 490         case '?':
 491           for (pp = hashtable; pp < hashtable + TABLES; pp++)
 492             {
 493               printf ("address of hash table #%d control block is %xx\n",
 494                       pp - hashtable, *pp);
 495             }
 496           break;
 497         case 'a':
 498           hash_traverse (h, applicatee);
 499           break;
 500         case 'd':
 501           hash_traverse (h, destroy);
 502           hash_die (h);
 503           break;
 504         case 'f':
 505           p = hash_find (h, name = what ("symbol"));
 506           printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
 507           break;
 508         case 'h':
 509           printf ("# show old, select new default hash table number\n");
 510           printf ("? display all hashtable control block addresses\n");
 511           printf ("a apply a simple display-er to each symbol in table\n");
 512           printf ("d die: destroy hashtable\n");
 513           printf ("f find value of nominated symbol\n");
 514           printf ("h this help\n");
 515           printf ("i insert value into symbol\n");
 516           printf ("j jam value into symbol\n");
 517           printf ("n new hashtable\n");
 518           printf ("r replace a value with another\n");
 519           printf ("s say what %% of table is used\n");
 520           printf ("q exit this program\n");
 521           printf ("x delete a symbol from table, report its value\n");
 522           break;
 523         case 'i':
 524           p = hash_insert (h, name = what ("symbol"), value = what ("value"));
 525           if (p)
 526             {
 527               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
 528                       p);
 529             }
 530           break;
 531         case 'j':
 532           p = hash_jam (h, name = what ("symbol"), value = what ("value"));
 533           if (p)
 534             {
 535               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
 536             }
 537           break;
 538         case 'n':
 539           h = hashtable[number] = (char *) hash_new ();
 540           break;
 541         case 'q':
 542           exit (EXIT_SUCCESS);
 543         case 'r':
 544           p = hash_replace (h, name = what ("symbol"), value = what ("value"));
 545           printf ("old value was \"%s\"\n", p ? p : "{}");
 546           break;
 547         case 's':
 548           hash_say (h, statbuf, STATBUFSIZE);
 549           for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
 550             {
 551               printf ("%d ", *ip);
 552             }
 553           printf ("\n");
 554           break;
 555         case 'x':
 556           p = hash_delete (h, name = what ("symbol"));
 557           printf ("old value was \"%s\"\n", p ? p : "{}");
 558           break;
 559         default:
 560           printf ("I can't understand command \"%c\"\n", command);
 561           break;
 562         }
 563     }
 564 }
 565
 566 char *
 567 what (description)
 568      char *description;
 569 {
 570   printf ("   %s : ", description);
 571   gets (answer);
 572   return xstrdup (answer);
 573 }
 574
 575 void
 576 destroy (string, value)
 577      char *string;
 578      char *value;
 579 {
 580   free (string);
 581   free (value);
 582 }
 583
 584 void
 585 applicatee (string, value)
 586      char *string;
 587      char *value;
 588 {
 589   printf ("%.20s-%.20s\n", string, value);
 590 }
 591
 592 /* Determine number: what hash table to use.
 593    Also determine h: points to hash_control.  */
 594
 595 void
 596 whattable ()
 597 {
 598   for (;;)
 599     {
 600       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 601       gets (answer);
 602       sscanf (answer, "%d", &number);
 603       if (number >= 0 && number < TABLES)
 604         {
 605           h = hashtable[number];
 606           if (!h)
 607             {
 608               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 609             }
 610           return;
 611         }
 612       else
 613         {
 614           printf ("invalid hash table number: %d\n", number);
 615         }
 616     }
 617 }
 618
 619 #endif /* TEST */