gas/hash.c

   1 /* hash.c -- gas hash table code
   2    Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
   3    2000, 2001, 2002
   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 "safe-ctype.h"
  34 #include "obstack.h"
  35
  36 /* The default number of entries to use when creating a hash table.  */
  37
  38 #define DEFAULT_SIZE (4051)
  39
  40 /* An entry in a hash table.  */
  41
  42 struct hash_entry {
  43   /* Next entry for this hash code.  */
  44   struct hash_entry *next;
  45   /* String being hashed.  */
  46   const char *string;
  47   /* Hash code.  This is the full hash code, not the index into the
  48      table.  */
  49   unsigned long hash;
  50   /* Pointer being stored in the hash table.  */
  51   PTR data;
  52 };
  53
  54 /* A hash table.  */
  55
  56 struct hash_control {
  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 = (struct hash_entry *) 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 = (struct hash_entry *) 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 /* Number of hash tables to maintain (at once) in any testing.  */
 419 #define TABLES (6)
 420
 421 /* We can have 12 statistics.  */
 422 #define STATBUFSIZE (12)
 423
 424 /* Display statistics here.  */
 425 int statbuf[STATBUFSIZE];
 426
 427 /* Human farts here.  */
 428 char answer[100];
 429
 430 /* We test many hash tables at once.  */
 431 char *hashtable[TABLES];
 432
 433 /* Points to curent hash_control.  */
 434 char *h;
 435 char **pp;
 436 char *p;
 437 char *name;
 438 char *value;
 439 int size;
 440 int used;
 441 char command;
 442
 443 /* Number 0:TABLES-1 of current hashed symbol table.  */
 444 int number;
 445
 446 int
 447 main ()
 448 {
 449   void applicatee ();
 450   void destroy ();
 451   char *what ();
 452   int *ip;
 453
 454   number = 0;
 455   h = 0;
 456   printf ("type h <RETURN> for help\n");
 457   for (;;)
 458     {
 459       printf ("hash_test command: ");
 460       gets (answer);
 461       command = answer[0];
 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   printf ("   %s : ", description);
 550   gets (answer);
 551   return xstrdup (answer);
 552 }
 553
 554 void
 555 destroy (string, value)
 556      char *string;
 557      char *value;
 558 {
 559   free (string);
 560   free (value);
 561 }
 562
 563 void
 564 applicatee (string, value)
 565      char *string;
 566      char *value;
 567 {
 568   printf ("%.20s-%.20s\n", string, value);
 569 }
 570
 571 /* Determine number: what hash table to use.
 572    Also determine h: points to hash_control.  */
 573
 574 void
 575 whattable ()
 576 {
 577   for (;;)
 578     {
 579       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 580       gets (answer);
 581       sscanf (answer, "%d", &number);
 582       if (number >= 0 && number < TABLES)
 583         {
 584           h = hashtable[number];
 585           if (!h)
 586             {
 587               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 588             }
 589           return;
 590         }
 591       else
 592         {
 593           printf ("invalid hash table number: %d\n", number);
 594         }
 595     }
 596 }
 597
 598 #endif /* TEST */