gas/hash.c

   1 /* hash.c -- gas hash table code
   2    Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 1999
   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 {
  42   /* Next entry for this hash code.  */
  43   struct hash_entry *next;
  44   /* String being hashed.  */
  45   const char *string;
  46   /* Hash code.  This is the full hash code, not the index into the
  47      table.  */
  48   unsigned long hash;
  49   /* Pointer being stored in the hash table.  */
  50   PTR data;
  51 };
  52
  53 /* A hash table.  */
  54
  55 struct hash_control
  56 {
  57   /* The hash array.  */
  58   struct hash_entry **table;
  59   /* The number of slots in the hash table.  */
  60   unsigned int size;
  61   /* An obstack for this hash table.  */
  62   struct obstack memory;
  63
  64 #ifdef HASH_STATISTICS
  65   /* Statistics.  */
  66   unsigned long lookups;
  67   unsigned long hash_compares;
  68   unsigned long string_compares;
  69   unsigned long insertions;
  70   unsigned long replacements;
  71   unsigned long deletions;
  72 #endif /* HASH_STATISTICS */
  73 };
  74
  75 /* Create a hash table.  This return a control block.  */
  76
  77 struct hash_control *
  78 hash_new ()
  79 {
  80   unsigned int size;
  81   struct hash_control *ret;
  82   unsigned int alloc;
  83
  84   size = DEFAULT_SIZE;
  85
  86   ret = (struct hash_control *) xmalloc (sizeof *ret);
  87   obstack_begin (&ret->memory, chunksize);
  88   alloc = size * sizeof (struct hash_entry *);
  89   ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
  90   memset (ret->table, 0, alloc);
  91   ret->size = size;
  92
  93 #ifdef HASH_STATISTICS
  94   ret->lookups = 0;
  95   ret->hash_compares = 0;
  96   ret->string_compares = 0;
  97   ret->insertions = 0;
  98   ret->replacements = 0;
  99   ret->deletions = 0;
 100 #endif
 101
 102   return ret;
 103 }
 104
 105 /* Delete a hash table, freeing all allocated memory.  */
 106
 107 void
 108 hash_die (table)
 109      struct hash_control *table;
 110 {
 111   obstack_free (&table->memory, 0);
 112   free (table);
 113 }
 114
 115 /* Look up a string in a hash table.  This returns a pointer to the
 116    hash_entry, or NULL if the string is not in the table.  If PLIST is
 117    not NULL, this sets *PLIST to point to the start of the list which
 118    would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
 119    to the hash code for KEY.
 120
 121    Each time we look up a string, we move it to the start of the list
 122    for its hash code, to take advantage of referential locality.  */
 123
 124 static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
 125                                                const char *,
 126                                                struct hash_entry ***,
 127                                                unsigned long *));
 128
 129 static struct hash_entry *
 130 hash_lookup (table, key, plist, phash)
 131      struct hash_control *table;
 132      const char *key;
 133      struct hash_entry ***plist;
 134      unsigned long *phash;
 135 {
 136   register unsigned long hash;
 137   unsigned int len;
 138   register const unsigned char *s;
 139   register unsigned int c;
 140   unsigned int index;
 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   len = 0;
 151   s = (const unsigned char *) key;
 152   while ((c = *s++) != '\0')
 153     {
 154       hash += c + (c << 17);
 155       hash ^= hash >> 2;
 156       ++len;
 157     }
 158   hash += len + (len << 17);
 159   hash ^= hash >> 2;
 160
 161   if (phash != NULL)
 162     *phash = hash;
 163
 164   index = hash % table->size;
 165   list = table->table + index;
 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 (strcmp (p->string, key) == 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 (table, key, value)
 209      struct hash_control *table;
 210      const char *key;
 211      PTR value;
 212 {
 213   struct hash_entry *p;
 214   struct hash_entry **list;
 215   unsigned long hash;
 216
 217   p = hash_lookup (table, key, &list, &hash);
 218   if (p != NULL)
 219     return "exists";
 220
 221 #ifdef HASH_STATISTICS
 222   ++table->insertions;
 223 #endif
 224
 225   p = obstack_alloc (&table->memory, sizeof *p);
 226   p->string = key;
 227   p->hash = hash;
 228   p->data = value;
 229
 230   p->next = *list;
 231   *list = p;
 232
 233   return NULL;
 234 }
 235
 236 /* Insert or replace an entry in a hash table.  This returns NULL on
 237    success.  On error, it returns a printable string indicating the
 238    error.  If an entry already exists, its value is replaced.  */
 239
 240 const char *
 241 hash_jam (table, key, value)
 242      struct hash_control *table;
 243      const char *key;
 244      PTR value;
 245 {
 246   struct hash_entry *p;
 247   struct hash_entry **list;
 248   unsigned long hash;
 249
 250   p = hash_lookup (table, key, &list, &hash);
 251   if (p != NULL)
 252     {
 253 #ifdef HASH_STATISTICS
 254       ++table->replacements;
 255 #endif
 256
 257       p->data = value;
 258     }
 259   else
 260     {
 261 #ifdef HASH_STATISTICS
 262       ++table->insertions;
 263 #endif
 264
 265       p = obstack_alloc (&table->memory, sizeof *p);
 266       p->string = key;
 267       p->hash = hash;
 268       p->data = value;
 269
 270       p->next = *list;
 271       *list = p;
 272     }
 273
 274   return NULL;
 275 }
 276
 277 /* Replace an existing entry in a hash table.  This returns the old
 278    value stored for the entry.  If the entry is not found in the hash
 279    table, this does nothing and returns NULL.  */
 280
 281 PTR
 282 hash_replace (table, key, value)
 283      struct hash_control *table;
 284      const char *key;
 285      PTR value;
 286 {
 287   struct hash_entry *p;
 288   PTR ret;
 289
 290   p = hash_lookup (table, key, NULL, NULL);
 291   if (p == NULL)
 292     return NULL;
 293
 294 #ifdef HASH_STATISTICS
 295   ++table->replacements;
 296 #endif
 297
 298   ret = p->data;
 299
 300   p->data = value;
 301
 302   return ret;
 303 }
 304
 305 /* Find an entry in a hash table, returning its value.  Returns NULL
 306    if the entry is not found.  */
 307
 308 PTR
 309 hash_find (table, key)
 310      struct hash_control *table;
 311      const char *key;
 312 {
 313   struct hash_entry *p;
 314
 315   p = hash_lookup (table, key, NULL, NULL);
 316   if (p == NULL)
 317     return NULL;
 318
 319   return p->data;
 320 }
 321
 322 /* Delete an entry from a hash table.  This returns the value stored
 323    for that entry, or NULL if there is no such entry.  */
 324
 325 PTR
 326 hash_delete (table, key)
 327      struct hash_control *table;
 328      const char *key;
 329 {
 330   struct hash_entry *p;
 331   struct hash_entry **list;
 332
 333   p = hash_lookup (table, 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   /* Note that we never reclaim the memory for this entry.  If gas
 347      ever starts deleting hash table entries in a big way, this will
 348      have to change.  */
 349
 350   return p->data;
 351 }
 352
 353 /* Traverse a hash table.  Call the function on every entry in the
 354    hash table.  */
 355
 356 void
 357 hash_traverse (table, pfn)
 358      struct hash_control *table;
 359      void (*pfn) PARAMS ((const char *key, PTR 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 (f, name, table)
 377      FILE *f ATTRIBUTE_UNUSED;
 378      const char *name ATTRIBUTE_UNUSED;
 379      struct hash_control *table ATTRIBUTE_UNUSED;
 380 {
 381 #ifdef HASH_STATISTICS
 382   unsigned int i;
 383   unsigned long total;
 384   unsigned long empty;
 385
 386   fprintf (f, "%s hash statistics:\n", name);
 387   fprintf (f, "\t%lu lookups\n", table->lookups);
 388   fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
 389   fprintf (f, "\t%lu string comparisons\n", table->string_compares);
 390   fprintf (f, "\t%lu insertions\n", table->insertions);
 391   fprintf (f, "\t%lu replacements\n", table->replacements);
 392   fprintf (f, "\t%lu deletions\n", table->deletions);
 393
 394   total = 0;
 395   empty = 0;
 396   for (i = 0; i < table->size; ++i)
 397     {
 398       struct hash_entry *p;
 399
 400       if (table->table[i] == NULL)
 401         ++empty;
 402       else
 403         {
 404           for (p = table->table[i]; p != NULL; p = p->next)
 405             ++total;
 406         }
 407     }
 408
 409   fprintf (f, "\t%g average chain length\n", (double) total / table->size);
 410   fprintf (f, "\t%lu empty slots\n", empty);
 411 #endif
 412 }
 413 \f
 414 #ifdef TEST
 415
 416 /* This test program is left over from the old hash table code.  */
 417
 418 #define TABLES (6)              /* number of hash tables to maintain */
 419                                 /* (at once) in any testing */
 420 #define STATBUFSIZE (12)        /* we can have 12 statistics */
 421
 422 int statbuf[STATBUFSIZE];       /* display statistics here */
 423 char answer[100];               /* human farts here */
 424 char *hashtable[TABLES];        /* we test many hash tables at once */
 425 char *h;                        /* points to curent hash_control */
 426 char **pp;
 427 char *p;
 428 char *name;
 429 char *value;
 430 int size;
 431 int used;
 432 char command;
 433 int number;                     /* number 0:TABLES-1 of current hashed */
 434                                 /* symbol table */
 435
 436 int
 437 main ()
 438 {
 439   void applicatee ();
 440   void destroy ();
 441   char *what ();
 442   int *ip;
 443
 444   number = 0;
 445   h = 0;
 446   printf ("type h <RETURN> for help\n");
 447   for (;;)
 448     {
 449       printf ("hash_test command: ");
 450       gets (answer);
 451       command = answer[0];
 452       if (isupper (command))
 453         command = tolower (command);    /* ecch! */
 454       switch (command)
 455         {
 456         case '#':
 457           printf ("old hash table #=%d.\n", number);
 458           whattable ();
 459           break;
 460         case '?':
 461           for (pp = hashtable; pp < hashtable + TABLES; pp++)
 462             {
 463               printf ("address of hash table #%d control block is %xx\n"
 464                       ,pp - hashtable, *pp);
 465             }
 466           break;
 467         case 'a':
 468           hash_traverse (h, applicatee);
 469           break;
 470         case 'd':
 471           hash_traverse (h, destroy);
 472           hash_die (h);
 473           break;
 474         case 'f':
 475           p = hash_find (h, name = what ("symbol"));
 476           printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
 477           break;
 478         case 'h':
 479           printf ("# show old, select new default hash table number\n");
 480           printf ("? display all hashtable control block addresses\n");
 481           printf ("a apply a simple display-er to each symbol in table\n");
 482           printf ("d die: destroy hashtable\n");
 483           printf ("f find value of nominated symbol\n");
 484           printf ("h this help\n");
 485           printf ("i insert value into symbol\n");
 486           printf ("j jam value into symbol\n");
 487           printf ("n new hashtable\n");
 488           printf ("r replace a value with another\n");
 489           printf ("s say what %% of table is used\n");
 490           printf ("q exit this program\n");
 491           printf ("x delete a symbol from table, report its value\n");
 492           break;
 493         case 'i':
 494           p = hash_insert (h, name = what ("symbol"), value = what ("value"));
 495           if (p)
 496             {
 497               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
 498                       p);
 499             }
 500           break;
 501         case 'j':
 502           p = hash_jam (h, name = what ("symbol"), value = what ("value"));
 503           if (p)
 504             {
 505               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
 506             }
 507           break;
 508         case 'n':
 509           h = hashtable[number] = (char *) hash_new ();
 510           break;
 511         case 'q':
 512           exit (EXIT_SUCCESS);
 513         case 'r':
 514           p = hash_replace (h, name = what ("symbol"), value = what ("value"));
 515           printf ("old value was \"%s\"\n", p ? p : "{}");
 516           break;
 517         case 's':
 518           hash_say (h, statbuf, STATBUFSIZE);
 519           for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
 520             {
 521               printf ("%d ", *ip);
 522             }
 523           printf ("\n");
 524           break;
 525         case 'x':
 526           p = hash_delete (h, name = what ("symbol"));
 527           printf ("old value was \"%s\"\n", p ? p : "{}");
 528           break;
 529         default:
 530           printf ("I can't understand command \"%c\"\n", command);
 531           break;
 532         }
 533     }
 534 }
 535
 536 char *
 537 what (description)
 538      char *description;
 539 {
 540   char *retval;
 541   char *malloc ();
 542
 543   printf ("   %s : ", description);
 544   gets (answer);
 545   /* will one day clean up answer here */
 546   retval = malloc (strlen (answer) + 1);
 547   if (!retval)
 548     {
 549       error ("room");
 550     }
 551   (void) strcpy (retval, answer);
 552   return (retval);
 553 }
 554
 555 void
 556 destroy (string, value)
 557      char *string;
 558      char *value;
 559 {
 560   free (string);
 561   free (value);
 562 }
 563
 564
 565 void
 566 applicatee (string, value)
 567      char *string;
 568      char *value;
 569 {
 570   printf ("%.20s-%.20s\n", string, value);
 571 }
 572
 573 void
 574 whattable ()                    /* determine number: what hash table to use */
 575                                 /* also determine h: points to hash_control */
 576 {
 577
 578   for (;;)
 579     {
 580       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 581       gets (answer);
 582       sscanf (answer, "%d", &number);
 583       if (number >= 0 && number < TABLES)
 584         {
 585           h = hashtable[number];
 586           if (!h)
 587             {
 588               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 589             }
 590           return;
 591         }
 592       else
 593         {
 594           printf ("invalid hash table number: %d\n", number);
 595         }
 596     }
 597 }
 598
 599 #endif /* #ifdef TEST */
 600
 601 /* end of hash.c */