gas/hash.c

   1 /* hash.c -- gas hash table code
   2    Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
   3    2000
   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 2, 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, 59 Temple Place - Suite 330, Boston, MA
  21    02111-1307, 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    asssembler.  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 "obstack.h"
  34
  35 /* The default number of entries to use when creating a hash table.  */
  36
  37 #define DEFAULT_SIZE (4051)
  38
  39 /* An entry in a hash table.  */
  40
  41 struct hash_entry {
  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   /* The hash array.  */
  57   struct hash_entry **table;
  58   /* The number of slots in the hash table.  */
  59   unsigned int size;
  60   /* An obstack for this hash table.  */
  61   struct obstack memory;
  62
  63 #ifdef HASH_STATISTICS
  64   /* Statistics.  */
  65   unsigned long lookups;
  66   unsigned long hash_compares;
  67   unsigned long string_compares;
  68   unsigned long insertions;
  69   unsigned long replacements;
  70   unsigned long deletions;
  71 #endif /* HASH_STATISTICS */
  72 };
  73
  74 /* Create a hash table.  This return a control block.  */
  75
  76 struct hash_control *
  77 hash_new ()
  78 {
  79   unsigned int size;
  80   struct hash_control *ret;
  81   unsigned int alloc;
  82
  83   size = DEFAULT_SIZE;
  84
  85   ret = (struct hash_control *) xmalloc (sizeof *ret);
  86   obstack_begin (&ret->memory, chunksize);
  87   alloc = size * sizeof (struct hash_entry *);
  88   ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
  89   memset (ret->table, 0, alloc);
  90   ret->size = size;
  91
  92 #ifdef HASH_STATISTICS
  93   ret->lookups = 0;
  94   ret->hash_compares = 0;
  95   ret->string_compares = 0;
  96   ret->insertions = 0;
  97   ret->replacements = 0;
  98   ret->deletions = 0;
  99 #endif
 100
 101   return ret;
 102 }
 103
 104 /* Delete a hash table, freeing all allocated memory.  */
 105
 106 void
 107 hash_die (table)
 108      struct hash_control *table;
 109 {
 110   obstack_free (&table->memory, 0);
 111   free (table);
 112 }
 113
 114 /* Look up a string in a hash table.  This returns a pointer to the
 115    hash_entry, or NULL if the string is not in the table.  If PLIST is
 116    not NULL, this sets *PLIST to point to the start of the list which
 117    would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
 118    to the hash code for KEY.
 119
 120    Each time we look up a string, we move it to the start of the list
 121    for its hash code, to take advantage of referential locality.  */
 122
 123 static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
 124                                                const char *,
 125                                                struct hash_entry ***,
 126                                                unsigned long *));
 127
 128 static struct hash_entry *
 129 hash_lookup (table, key, plist, phash)
 130      struct hash_control *table;
 131      const char *key;
 132      struct hash_entry ***plist;
 133      unsigned long *phash;
 134 {
 135   register unsigned long hash;
 136   unsigned int len;
 137   register const unsigned char *s;
 138   register unsigned int c;
 139   unsigned int index;
 140   struct hash_entry **list;
 141   struct hash_entry *p;
 142   struct hash_entry *prev;
 143
 144 #ifdef HASH_STATISTICS
 145   ++table->lookups;
 146 #endif
 147
 148   hash = 0;
 149   len = 0;
 150   s = (const unsigned char *) key;
 151   while ((c = *s++) != '\0')
 152     {
 153       hash += c + (c << 17);
 154       hash ^= hash >> 2;
 155       ++len;
 156     }
 157   hash += len + (len << 17);
 158   hash ^= hash >> 2;
 159
 160   if (phash != NULL)
 161     *phash = hash;
 162
 163   index = hash % table->size;
 164   list = table->table + index;
 165
 166   if (plist != NULL)
 167     *plist = list;
 168
 169   prev = NULL;
 170   for (p = *list; p != NULL; p = p->next)
 171     {
 172 #ifdef HASH_STATISTICS
 173       ++table->hash_compares;
 174 #endif
 175
 176       if (p->hash == hash)
 177         {
 178 #ifdef HASH_STATISTICS
 179           ++table->string_compares;
 180 #endif
 181
 182           if (strcmp (p->string, key) == 0)
 183             {
 184               if (prev != NULL)
 185                 {
 186                   prev->next = p->next;
 187                   p->next = *list;
 188                   *list = p;
 189                 }
 190
 191               return p;
 192             }
 193         }
 194
 195       prev = p;
 196     }
 197
 198   return NULL;
 199 }
 200
 201 /* Insert an entry into a hash table.  This returns NULL on success.
 202    On error, it returns a printable string indicating the error.  It
 203    is considered to be an error if the entry already exists in the
 204    hash table.  */
 205
 206 const char *
 207 hash_insert (table, key, value)
 208      struct hash_control *table;
 209      const char *key;
 210      PTR value;
 211 {
 212   struct hash_entry *p;
 213   struct hash_entry **list;
 214   unsigned long hash;
 215
 216   p = hash_lookup (table, key, &list, &hash);
 217   if (p != NULL)
 218     return "exists";
 219
 220 #ifdef HASH_STATISTICS
 221   ++table->insertions;
 222 #endif
 223
 224   p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 225   p->string = key;
 226   p->hash = hash;
 227   p->data = value;
 228
 229   p->next = *list;
 230   *list = p;
 231
 232   return NULL;
 233 }
 234
 235 /* Insert or replace an entry in a hash table.  This returns NULL on
 236    success.  On error, it returns a printable string indicating the
 237    error.  If an entry already exists, its value is replaced.  */
 238
 239 const char *
 240 hash_jam (table, key, value)
 241      struct hash_control *table;
 242      const char *key;
 243      PTR value;
 244 {
 245   struct hash_entry *p;
 246   struct hash_entry **list;
 247   unsigned long hash;
 248
 249   p = hash_lookup (table, key, &list, &hash);
 250   if (p != NULL)
 251     {
 252 #ifdef HASH_STATISTICS
 253       ++table->replacements;
 254 #endif
 255
 256       p->data = value;
 257     }
 258   else
 259     {
 260 #ifdef HASH_STATISTICS
 261       ++table->insertions;
 262 #endif
 263
 264       p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 265       p->string = key;
 266       p->hash = hash;
 267       p->data = value;
 268
 269       p->next = *list;
 270       *list = p;
 271     }
 272
 273   return NULL;
 274 }
 275
 276 /* Replace an existing entry in a hash table.  This returns the old
 277    value stored for the entry.  If the entry is not found in the hash
 278    table, this does nothing and returns NULL.  */
 279
 280 PTR
 281 hash_replace (table, key, value)
 282      struct hash_control *table;
 283      const char *key;
 284      PTR value;
 285 {
 286   struct hash_entry *p;
 287   PTR ret;
 288
 289   p = hash_lookup (table, key, NULL, NULL);
 290   if (p == NULL)
 291     return NULL;
 292
 293 #ifdef HASH_STATISTICS
 294   ++table->replacements;
 295 #endif
 296
 297   ret = p->data;
 298
 299   p->data = value;
 300
 301   return ret;
 302 }
 303
 304 /* Find an entry in a hash table, returning its value.  Returns NULL
 305    if the entry is not found.  */
 306
 307 PTR
 308 hash_find (table, key)
 309      struct hash_control *table;
 310      const char *key;
 311 {
 312   struct hash_entry *p;
 313
 314   p = hash_lookup (table, key, NULL, NULL);
 315   if (p == NULL)
 316     return NULL;
 317
 318   return p->data;
 319 }
 320
 321 /* Delete an entry from a hash table.  This returns the value stored
 322    for that entry, or NULL if there is no such entry.  */
 323
 324 PTR
 325 hash_delete (table, key)
 326      struct hash_control *table;
 327      const char *key;
 328 {
 329   struct hash_entry *p;
 330   struct hash_entry **list;
 331
 332   p = hash_lookup (table, key, &list, NULL);
 333   if (p == NULL)
 334     return NULL;
 335
 336   if (p != *list)
 337     abort ();
 338
 339 #ifdef HASH_STATISTICS
 340   ++table->deletions;
 341 #endif
 342
 343   *list = p->next;
 344
 345   /* Note that we never reclaim the memory for this entry.  If gas
 346      ever starts deleting hash table entries in a big way, this will
 347      have to change.  */
 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 (table, pfn)
 357      struct hash_control *table;
 358      void (*pfn) PARAMS ((const char *key, PTR value));
 359 {
 360   unsigned int i;
 361
 362   for (i = 0; i < table->size; ++i)
 363     {
 364       struct hash_entry *p;
 365
 366       for (p = table->table[i]; p != NULL; p = p->next)
 367         (*pfn) (p->string, p->data);
 368     }
 369 }
 370
 371 /* Print hash table statistics on the specified file.  NAME is the
 372    name of the hash table, used for printing a header.  */
 373
 374 void
 375 hash_print_statistics (f, name, table)
 376      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 curent 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       if (isupper (command))
 462         command = tolower (command);    /* Ecch!  */
 463       switch (command)
 464         {
 465         case '#':
 466           printf ("old hash table #=%d.\n", number);
 467           whattable ();
 468           break;
 469         case '?':
 470           for (pp = hashtable; pp < hashtable + TABLES; pp++)
 471             {
 472               printf ("address of hash table #%d control block is %xx\n",
 473                       pp - hashtable, *pp);
 474             }
 475           break;
 476         case 'a':
 477           hash_traverse (h, applicatee);
 478           break;
 479         case 'd':
 480           hash_traverse (h, destroy);
 481           hash_die (h);
 482           break;
 483         case 'f':
 484           p = hash_find (h, name = what ("symbol"));
 485           printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
 486           break;
 487         case 'h':
 488           printf ("# show old, select new default hash table number\n");
 489           printf ("? display all hashtable control block addresses\n");
 490           printf ("a apply a simple display-er to each symbol in table\n");
 491           printf ("d die: destroy hashtable\n");
 492           printf ("f find value of nominated symbol\n");
 493           printf ("h this help\n");
 494           printf ("i insert value into symbol\n");
 495           printf ("j jam value into symbol\n");
 496           printf ("n new hashtable\n");
 497           printf ("r replace a value with another\n");
 498           printf ("s say what %% of table is used\n");
 499           printf ("q exit this program\n");
 500           printf ("x delete a symbol from table, report its value\n");
 501           break;
 502         case 'i':
 503           p = hash_insert (h, name = what ("symbol"), value = what ("value"));
 504           if (p)
 505             {
 506               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
 507                       p);
 508             }
 509           break;
 510         case 'j':
 511           p = hash_jam (h, name = what ("symbol"), value = what ("value"));
 512           if (p)
 513             {
 514               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
 515             }
 516           break;
 517         case 'n':
 518           h = hashtable[number] = (char *) hash_new ();
 519           break;
 520         case 'q':
 521           exit (EXIT_SUCCESS);
 522         case 'r':
 523           p = hash_replace (h, name = what ("symbol"), value = what ("value"));
 524           printf ("old value was \"%s\"\n", p ? p : "{}");
 525           break;
 526         case 's':
 527           hash_say (h, statbuf, STATBUFSIZE);
 528           for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
 529             {
 530               printf ("%d ", *ip);
 531             }
 532           printf ("\n");
 533           break;
 534         case 'x':
 535           p = hash_delete (h, name = what ("symbol"));
 536           printf ("old value was \"%s\"\n", p ? p : "{}");
 537           break;
 538         default:
 539           printf ("I can't understand command \"%c\"\n", command);
 540           break;
 541         }
 542     }
 543 }
 544
 545 char *
 546 what (description)
 547      char *description;
 548 {
 549   char *retval;
 550   char *malloc ();
 551
 552   printf ("   %s : ", description);
 553   gets (answer);
 554   /* Will one day clean up answer here.  */
 555   retval = malloc (strlen (answer) + 1);
 556   if (!retval)
 557     {
 558       error ("room");
 559     }
 560   (void) strcpy (retval, answer);
 561   return (retval);
 562 }
 563
 564 void
 565 destroy (string, value)
 566      char *string;
 567      char *value;
 568 {
 569   free (string);
 570   free (value);
 571 }
 572
 573 void
 574 applicatee (string, value)
 575      char *string;
 576      char *value;
 577 {
 578   printf ("%.20s-%.20s\n", string, value);
 579 }
 580
 581 /* Determine number: what hash table to use.
 582    Also determine h: points to hash_control.  */
 583
 584 void
 585 whattable ()
 586 {
 587   for (;;)
 588     {
 589       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 590       gets (answer);
 591       sscanf (answer, "%d", &number);
 592       if (number >= 0 && number < TABLES)
 593         {
 594           h = hashtable[number];
 595           if (!h)
 596             {
 597               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 598             }
 599           return;
 600         }
 601       else
 602         {
 603           printf ("invalid hash table number: %d\n", number);
 604         }
 605     }
 606 }
 607
 608 #endif /* TEST */