gas/hash.c

   1 /* hash.c -- gas hash table code
   2    Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 99, 2000
   3    Free Software Foundation, Inc.
   4
   5    This file is part of GAS, the GNU Assembler.
   6
   7    GAS is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2, or (at your option)
  10    any later version.
  11
  12    GAS is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GAS; see the file COPYING.  If not, write to the Free
  19    Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20    02111-1307, USA.  */
  21
  22 /* This version of the hash table code is a wholescale replacement of
  23    the old hash table code, which was fairly bad.  This is based on
  24    the hash table code in BFD, but optimized slightly for the
  25    asssembler.  The assembler does not need to derive structures that
  26    are stored in the hash table.  Instead, it always stores a pointer.
  27    The assembler uses the hash table mostly to store symbols, and we
  28    don't need to confuse the symbol structure with a hash table
  29    structure.  */
  30
  31 #include "as.h"
  32 #include "obstack.h"
  33
  34 /* The default number of entries to use when creating a hash table.  */
  35
  36 #define DEFAULT_SIZE (4051)
  37
  38 /* An entry in a hash table.  */
  39
  40 struct hash_entry {
  41   /* Next entry for this hash code.  */
  42   struct hash_entry *next;
  43   /* String being hashed.  */
  44   const char *string;
  45   /* Hash code.  This is the full hash code, not the index into the
  46      table.  */
  47   unsigned long hash;
  48   /* Pointer being stored in the hash table.  */
  49   PTR data;
  50 };
  51
  52 /* A hash table.  */
  53
  54 struct hash_control {
  55   /* The hash array.  */
  56   struct hash_entry **table;
  57   /* The number of slots in the hash table.  */
  58   unsigned int size;
  59   /* An obstack for this hash table.  */
  60   struct obstack memory;
  61
  62 #ifdef HASH_STATISTICS
  63   /* Statistics.  */
  64   unsigned long lookups;
  65   unsigned long hash_compares;
  66   unsigned long string_compares;
  67   unsigned long insertions;
  68   unsigned long replacements;
  69   unsigned long deletions;
  70 #endif /* HASH_STATISTICS */
  71 };
  72
  73 /* Create a hash table.  This return a control block.  */
  74
  75 struct hash_control *
  76 hash_new ()
  77 {
  78   unsigned int size;
  79   struct hash_control *ret;
  80   unsigned int alloc;
  81
  82   size = DEFAULT_SIZE;
  83
  84   ret = (struct hash_control *) xmalloc (sizeof *ret);
  85   obstack_begin (&ret->memory, chunksize);
  86   alloc = size * sizeof (struct hash_entry *);
  87   ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
  88   memset (ret->table, 0, alloc);
  89   ret->size = size;
  90
  91 #ifdef HASH_STATISTICS
  92   ret->lookups = 0;
  93   ret->hash_compares = 0;
  94   ret->string_compares = 0;
  95   ret->insertions = 0;
  96   ret->replacements = 0;
  97   ret->deletions = 0;
  98 #endif
  99
 100   return ret;
 101 }
 102
 103 /* Delete a hash table, freeing all allocated memory.  */
 104
 105 void
 106 hash_die (table)
 107      struct hash_control *table;
 108 {
 109   obstack_free (&table->memory, 0);
 110   free (table);
 111 }
 112
 113 /* Look up a string in a hash table.  This returns a pointer to the
 114    hash_entry, or NULL if the string is not in the table.  If PLIST is
 115    not NULL, this sets *PLIST to point to the start of the list which
 116    would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
 117    to the hash code for KEY.
 118
 119    Each time we look up a string, we move it to the start of the list
 120    for its hash code, to take advantage of referential locality.  */
 121
 122 static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
 123                                                const char *,
 124                                                struct hash_entry ***,
 125                                                unsigned long *));
 126
 127 static struct hash_entry *
 128 hash_lookup (table, key, plist, phash)
 129      struct hash_control *table;
 130      const char *key;
 131      struct hash_entry ***plist;
 132      unsigned long *phash;
 133 {
 134   register unsigned long hash;
 135   unsigned int len;
 136   register const unsigned char *s;
 137   register unsigned int c;
 138   unsigned int index;
 139   struct hash_entry **list;
 140   struct hash_entry *p;
 141   struct hash_entry *prev;
 142
 143 #ifdef HASH_STATISTICS
 144   ++table->lookups;
 145 #endif
 146
 147   hash = 0;
 148   len = 0;
 149   s = (const unsigned char *) key;
 150   while ((c = *s++) != '\0')
 151     {
 152       hash += c + (c << 17);
 153       hash ^= hash >> 2;
 154       ++len;
 155     }
 156   hash += len + (len << 17);
 157   hash ^= hash >> 2;
 158
 159   if (phash != NULL)
 160     *phash = hash;
 161
 162   index = hash % table->size;
 163   list = table->table + index;
 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 (strcmp (p->string, key) == 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 (table, key, value)
 207      struct hash_control *table;
 208      const char *key;
 209      PTR value;
 210 {
 211   struct hash_entry *p;
 212   struct hash_entry **list;
 213   unsigned long hash;
 214
 215   p = hash_lookup (table, key, &list, &hash);
 216   if (p != NULL)
 217     return "exists";
 218
 219 #ifdef HASH_STATISTICS
 220   ++table->insertions;
 221 #endif
 222
 223   p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 224   p->string = key;
 225   p->hash = hash;
 226   p->data = value;
 227
 228   p->next = *list;
 229   *list = p;
 230
 231   return NULL;
 232 }
 233
 234 /* Insert or replace an entry in a hash table.  This returns NULL on
 235    success.  On error, it returns a printable string indicating the
 236    error.  If an entry already exists, its value is replaced.  */
 237
 238 const char *
 239 hash_jam (table, key, value)
 240      struct hash_control *table;
 241      const char *key;
 242      PTR value;
 243 {
 244   struct hash_entry *p;
 245   struct hash_entry **list;
 246   unsigned long hash;
 247
 248   p = hash_lookup (table, key, &list, &hash);
 249   if (p != NULL)
 250     {
 251 #ifdef HASH_STATISTICS
 252       ++table->replacements;
 253 #endif
 254
 255       p->data = value;
 256     }
 257   else
 258     {
 259 #ifdef HASH_STATISTICS
 260       ++table->insertions;
 261 #endif
 262
 263       p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 264       p->string = key;
 265       p->hash = hash;
 266       p->data = value;
 267
 268       p->next = *list;
 269       *list = p;
 270     }
 271
 272   return NULL;
 273 }
 274
 275 /* Replace an existing entry in a hash table.  This returns the old
 276    value stored for the entry.  If the entry is not found in the hash
 277    table, this does nothing and returns NULL.  */
 278
 279 PTR
 280 hash_replace (table, key, value)
 281      struct hash_control *table;
 282      const char *key;
 283      PTR value;
 284 {
 285   struct hash_entry *p;
 286   PTR ret;
 287
 288   p = hash_lookup (table, key, NULL, NULL);
 289   if (p == NULL)
 290     return NULL;
 291
 292 #ifdef HASH_STATISTICS
 293   ++table->replacements;
 294 #endif
 295
 296   ret = p->data;
 297
 298   p->data = value;
 299
 300   return ret;
 301 }
 302
 303 /* Find an entry in a hash table, returning its value.  Returns NULL
 304    if the entry is not found.  */
 305
 306 PTR
 307 hash_find (table, key)
 308      struct hash_control *table;
 309      const char *key;
 310 {
 311   struct hash_entry *p;
 312
 313   p = hash_lookup (table, key, NULL, NULL);
 314   if (p == NULL)
 315     return NULL;
 316
 317   return p->data;
 318 }
 319
 320 /* Delete an entry from a hash table.  This returns the value stored
 321    for that entry, or NULL if there is no such entry.  */
 322
 323 PTR
 324 hash_delete (table, key)
 325      struct hash_control *table;
 326      const char *key;
 327 {
 328   struct hash_entry *p;
 329   struct hash_entry **list;
 330
 331   p = hash_lookup (table, key, &list, NULL);
 332   if (p == NULL)
 333     return NULL;
 334
 335   if (p != *list)
 336     abort ();
 337
 338 #ifdef HASH_STATISTICS
 339   ++table->deletions;
 340 #endif
 341
 342   *list = p->next;
 343
 344   /* Note that we never reclaim the memory for this entry.  If gas
 345      ever starts deleting hash table entries in a big way, this will
 346      have to change.  */
 347
 348   return p->data;
 349 }
 350
 351 /* Traverse a hash table.  Call the function on every entry in the
 352    hash table.  */
 353
 354 void
 355 hash_traverse (table, pfn)
 356      struct hash_control *table;
 357      void (*pfn) PARAMS ((const char *key, PTR 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 (f, name, table)
 375      FILE *f ATTRIBUTE_UNUSED;
 376      const char *name ATTRIBUTE_UNUSED;
 377      struct hash_control *table ATTRIBUTE_UNUSED;
 378 {
 379 #ifdef HASH_STATISTICS
 380   unsigned int i;
 381   unsigned long total;
 382   unsigned long empty;
 383
 384   fprintf (f, "%s hash statistics:\n", name);
 385   fprintf (f, "\t%lu lookups\n", table->lookups);
 386   fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
 387   fprintf (f, "\t%lu string comparisons\n", table->string_compares);
 388   fprintf (f, "\t%lu insertions\n", table->insertions);
 389   fprintf (f, "\t%lu replacements\n", table->replacements);
 390   fprintf (f, "\t%lu deletions\n", table->deletions);
 391
 392   total = 0;
 393   empty = 0;
 394   for (i = 0; i < table->size; ++i)
 395     {
 396       struct hash_entry *p;
 397
 398       if (table->table[i] == NULL)
 399         ++empty;
 400       else
 401         {
 402           for (p = table->table[i]; p != NULL; p = p->next)
 403             ++total;
 404         }
 405     }
 406
 407   fprintf (f, "\t%g average chain length\n", (double) total / table->size);
 408   fprintf (f, "\t%lu empty slots\n", empty);
 409 #endif
 410 }
 411 \f
 412 #ifdef TEST
 413
 414 /* This test program is left over from the old hash table code.  */
 415
 416 /* Number of hash tables to maintain (at once) in any testing.  */
 417 #define TABLES (6)
 418
 419 /* We can have 12 statistics.  */
 420 #define STATBUFSIZE (12)
 421
 422 /* Display statistics here.  */
 423 int statbuf[STATBUFSIZE];
 424
 425 /* Human farts here.  */
 426 char answer[100];
 427
 428 /* We test many hash tables at once.  */
 429 char *hashtable[TABLES];
 430
 431 /* Points to curent hash_control.  */
 432 char *h;
 433 char **pp;
 434 char *p;
 435 char *name;
 436 char *value;
 437 int size;
 438 int used;
 439 char command;
 440
 441 /* Number 0:TABLES-1 of current hashed symbol table.  */
 442 int number;
 443
 444 int
 445 main ()
 446 {
 447   void applicatee ();
 448   void destroy ();
 449   char *what ();
 450   int *ip;
 451
 452   number = 0;
 453   h = 0;
 454   printf ("type h <RETURN> for help\n");
 455   for (;;)
 456     {
 457       printf ("hash_test command: ");
 458       gets (answer);
 459       command = answer[0];
 460       if (isupper (command))
 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   char *retval;
 549   char *malloc ();
 550
 551   printf ("   %s : ", description);
 552   gets (answer);
 553   /* Will one day clean up answer here.  */
 554   retval = malloc (strlen (answer) + 1);
 555   if (!retval)
 556     {
 557       error ("room");
 558     }
 559   (void) strcpy (retval, answer);
 560   return (retval);
 561 }
 562
 563 void
 564 destroy (string, value)
 565      char *string;
 566      char *value;
 567 {
 568   free (string);
 569   free (value);
 570 }
 571
 572 void
 573 applicatee (string, value)
 574      char *string;
 575      char *value;
 576 {
 577   printf ("%.20s-%.20s\n", string, value);
 578 }
 579
 580 /* Determine number: what hash table to use.
 581    Also determine h: points to hash_control.  */
 582
 583 void
 584 whattable ()
 585 {
 586   for (;;)
 587     {
 588       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 589       gets (answer);
 590       sscanf (answer, "%d", &number);
 591       if (number >= 0 && number < TABLES)
 592         {
 593           h = hashtable[number];
 594           if (!h)
 595             {
 596               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 597             }
 598           return;
 599         }
 600       else
 601         {
 602           printf ("invalid hash table number: %d\n", number);
 603         }
 604     }
 605 }
 606
 607 #endif /* TEST */