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 {
  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 = (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       if (isupper (command))
 463         command = tolower (command);    /* Ecch!  */
 464       switch (command)
 465         {
 466         case '#':
 467           printf ("old hash table #=%d.\n", number);
 468           whattable ();
 469           break;
 470         case '?':
 471           for (pp = hashtable; pp < hashtable + TABLES; pp++)
 472             {
 473               printf ("address of hash table #%d control block is %xx\n",
 474                       pp - hashtable, *pp);
 475             }
 476           break;
 477         case 'a':
 478           hash_traverse (h, applicatee);
 479           break;
 480         case 'd':
 481           hash_traverse (h, destroy);
 482           hash_die (h);
 483           break;
 484         case 'f':
 485           p = hash_find (h, name = what ("symbol"));
 486           printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
 487           break;
 488         case 'h':
 489           printf ("# show old, select new default hash table number\n");
 490           printf ("? display all hashtable control block addresses\n");
 491           printf ("a apply a simple display-er to each symbol in table\n");
 492           printf ("d die: destroy hashtable\n");
 493           printf ("f find value of nominated symbol\n");
 494           printf ("h this help\n");
 495           printf ("i insert value into symbol\n");
 496           printf ("j jam value into symbol\n");
 497           printf ("n new hashtable\n");
 498           printf ("r replace a value with another\n");
 499           printf ("s say what %% of table is used\n");
 500           printf ("q exit this program\n");
 501           printf ("x delete a symbol from table, report its value\n");
 502           break;
 503         case 'i':
 504           p = hash_insert (h, name = what ("symbol"), value = what ("value"));
 505           if (p)
 506             {
 507               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
 508                       p);
 509             }
 510           break;
 511         case 'j':
 512           p = hash_jam (h, name = what ("symbol"), value = what ("value"));
 513           if (p)
 514             {
 515               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
 516             }
 517           break;
 518         case 'n':
 519           h = hashtable[number] = (char *) hash_new ();
 520           break;
 521         case 'q':
 522           exit (EXIT_SUCCESS);
 523         case 'r':
 524           p = hash_replace (h, name = what ("symbol"), value = what ("value"));
 525           printf ("old value was \"%s\"\n", p ? p : "{}");
 526           break;
 527         case 's':
 528           hash_say (h, statbuf, STATBUFSIZE);
 529           for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
 530             {
 531               printf ("%d ", *ip);
 532             }
 533           printf ("\n");
 534           break;
 535         case 'x':
 536           p = hash_delete (h, name = what ("symbol"));
 537           printf ("old value was \"%s\"\n", p ? p : "{}");
 538           break;
 539         default:
 540           printf ("I can't understand command \"%c\"\n", command);
 541           break;
 542         }
 543     }
 544 }
 545
 546 char *
 547 what (description)
 548      char *description;
 549 {
 550   char *retval;
 551   char *malloc ();
 552
 553   printf ("   %s : ", description);
 554   gets (answer);
 555   /* Will one day clean up answer here.  */
 556   retval = malloc (strlen (answer) + 1);
 557   if (!retval)
 558     {
 559       error ("room");
 560     }
 561   (void) strcpy (retval, answer);
 562   return (retval);
 563 }
 564
 565 void
 566 destroy (string, value)
 567      char *string;
 568      char *value;
 569 {
 570   free (string);
 571   free (value);
 572 }
 573
 574 void
 575 applicatee (string, value)
 576      char *string;
 577      char *value;
 578 {
 579   printf ("%.20s-%.20s\n", string, value);
 580 }
 581
 582 /* Determine number: what hash table to use.
 583    Also determine h: points to hash_control.  */
 584
 585 void
 586 whattable ()
 587 {
 588   for (;;)
 589     {
 590       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 591       gets (answer);
 592       sscanf (answer, "%d", &number);
 593       if (number >= 0 && number < TABLES)
 594         {
 595           h = hashtable[number];
 596           if (!h)
 597             {
 598               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 599             }
 600           return;
 601         }
 602       else
 603         {
 604           printf ("invalid hash table number: %d\n", number);
 605         }
 606     }
 607 }
 608
 609 #endif /* TEST */