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, 2003
   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    assembler.  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 (void)
  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 (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 (struct hash_control *,
 124                                        const char *,
 125                                        struct hash_entry ***,
 126                                        unsigned long *);
 127
 128 static struct hash_entry *
 129 hash_lookup (struct hash_control *table, const char *key,
 130              struct hash_entry ***plist, unsigned long *phash)
 131 {
 132   register unsigned long hash;
 133   unsigned int len;
 134   register const unsigned char *s;
 135   register unsigned int c;
 136   unsigned int index;
 137   struct hash_entry **list;
 138   struct hash_entry *p;
 139   struct hash_entry *prev;
 140
 141 #ifdef HASH_STATISTICS
 142   ++table->lookups;
 143 #endif
 144
 145   hash = 0;
 146   len = 0;
 147   s = (const unsigned char *) key;
 148   while ((c = *s++) != '\0')
 149     {
 150       hash += c + (c << 17);
 151       hash ^= hash >> 2;
 152       ++len;
 153     }
 154   hash += len + (len << 17);
 155   hash ^= hash >> 2;
 156
 157   if (phash != NULL)
 158     *phash = hash;
 159
 160   index = hash % table->size;
 161   list = table->table + index;
 162
 163   if (plist != NULL)
 164     *plist = list;
 165
 166   prev = NULL;
 167   for (p = *list; p != NULL; p = p->next)
 168     {
 169 #ifdef HASH_STATISTICS
 170       ++table->hash_compares;
 171 #endif
 172
 173       if (p->hash == hash)
 174         {
 175 #ifdef HASH_STATISTICS
 176           ++table->string_compares;
 177 #endif
 178
 179           if (strcmp (p->string, key) == 0)
 180             {
 181               if (prev != NULL)
 182                 {
 183                   prev->next = p->next;
 184                   p->next = *list;
 185                   *list = p;
 186                 }
 187
 188               return p;
 189             }
 190         }
 191
 192       prev = p;
 193     }
 194
 195   return NULL;
 196 }
 197
 198 /* Insert an entry into a hash table.  This returns NULL on success.
 199    On error, it returns a printable string indicating the error.  It
 200    is considered to be an error if the entry already exists in the
 201    hash table.  */
 202
 203 const char *
 204 hash_insert (struct hash_control *table, const char *key, PTR value)
 205 {
 206   struct hash_entry *p;
 207   struct hash_entry **list;
 208   unsigned long hash;
 209
 210   p = hash_lookup (table, key, &list, &hash);
 211   if (p != NULL)
 212     return "exists";
 213
 214 #ifdef HASH_STATISTICS
 215   ++table->insertions;
 216 #endif
 217
 218   p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 219   p->string = key;
 220   p->hash = hash;
 221   p->data = value;
 222
 223   p->next = *list;
 224   *list = p;
 225
 226   return NULL;
 227 }
 228
 229 /* Insert or replace an entry in a hash table.  This returns NULL on
 230    success.  On error, it returns a printable string indicating the
 231    error.  If an entry already exists, its value is replaced.  */
 232
 233 const char *
 234 hash_jam (struct hash_control *table, const char *key, PTR value)
 235 {
 236   struct hash_entry *p;
 237   struct hash_entry **list;
 238   unsigned long hash;
 239
 240   p = hash_lookup (table, key, &list, &hash);
 241   if (p != NULL)
 242     {
 243 #ifdef HASH_STATISTICS
 244       ++table->replacements;
 245 #endif
 246
 247       p->data = value;
 248     }
 249   else
 250     {
 251 #ifdef HASH_STATISTICS
 252       ++table->insertions;
 253 #endif
 254
 255       p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
 256       p->string = key;
 257       p->hash = hash;
 258       p->data = value;
 259
 260       p->next = *list;
 261       *list = p;
 262     }
 263
 264   return NULL;
 265 }
 266
 267 /* Replace an existing entry in a hash table.  This returns the old
 268    value stored for the entry.  If the entry is not found in the hash
 269    table, this does nothing and returns NULL.  */
 270
 271 PTR
 272 hash_replace (struct hash_control *table, const char *key, PTR value)
 273 {
 274   struct hash_entry *p;
 275   PTR ret;
 276
 277   p = hash_lookup (table, key, NULL, NULL);
 278   if (p == NULL)
 279     return NULL;
 280
 281 #ifdef HASH_STATISTICS
 282   ++table->replacements;
 283 #endif
 284
 285   ret = p->data;
 286
 287   p->data = value;
 288
 289   return ret;
 290 }
 291
 292 /* Find an entry in a hash table, returning its value.  Returns NULL
 293    if the entry is not found.  */
 294
 295 PTR
 296 hash_find (struct hash_control *table, const char *key)
 297 {
 298   struct hash_entry *p;
 299
 300   p = hash_lookup (table, key, NULL, NULL);
 301   if (p == NULL)
 302     return NULL;
 303
 304   return p->data;
 305 }
 306
 307 /* Delete an entry from a hash table.  This returns the value stored
 308    for that entry, or NULL if there is no such entry.  */
 309
 310 PTR
 311 hash_delete (struct hash_control *table, const char *key)
 312 {
 313   struct hash_entry *p;
 314   struct hash_entry **list;
 315
 316   p = hash_lookup (table, key, &list, NULL);
 317   if (p == NULL)
 318     return NULL;
 319
 320   if (p != *list)
 321     abort ();
 322
 323 #ifdef HASH_STATISTICS
 324   ++table->deletions;
 325 #endif
 326
 327   *list = p->next;
 328
 329   /* Note that we never reclaim the memory for this entry.  If gas
 330      ever starts deleting hash table entries in a big way, this will
 331      have to change.  */
 332
 333   return p->data;
 334 }
 335
 336 /* Traverse a hash table.  Call the function on every entry in the
 337    hash table.  */
 338
 339 void
 340 hash_traverse (struct hash_control *table,
 341                void (*pfn) (const char *key, PTR value))
 342 {
 343   unsigned int i;
 344
 345   for (i = 0; i < table->size; ++i)
 346     {
 347       struct hash_entry *p;
 348
 349       for (p = table->table[i]; p != NULL; p = p->next)
 350         (*pfn) (p->string, p->data);
 351     }
 352 }
 353
 354 /* Print hash table statistics on the specified file.  NAME is the
 355    name of the hash table, used for printing a header.  */
 356
 357 void
 358 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
 359                        const char *name ATTRIBUTE_UNUSED,
 360                        struct hash_control *table ATTRIBUTE_UNUSED)
 361 {
 362 #ifdef HASH_STATISTICS
 363   unsigned int i;
 364   unsigned long total;
 365   unsigned long empty;
 366
 367   fprintf (f, "%s hash statistics:\n", name);
 368   fprintf (f, "\t%lu lookups\n", table->lookups);
 369   fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
 370   fprintf (f, "\t%lu string comparisons\n", table->string_compares);
 371   fprintf (f, "\t%lu insertions\n", table->insertions);
 372   fprintf (f, "\t%lu replacements\n", table->replacements);
 373   fprintf (f, "\t%lu deletions\n", table->deletions);
 374
 375   total = 0;
 376   empty = 0;
 377   for (i = 0; i < table->size; ++i)
 378     {
 379       struct hash_entry *p;
 380
 381       if (table->table[i] == NULL)
 382         ++empty;
 383       else
 384         {
 385           for (p = table->table[i]; p != NULL; p = p->next)
 386             ++total;
 387         }
 388     }
 389
 390   fprintf (f, "\t%g average chain length\n", (double) total / table->size);
 391   fprintf (f, "\t%lu empty slots\n", empty);
 392 #endif
 393 }
 394 \f
 395 #ifdef TEST
 396
 397 /* This test program is left over from the old hash table code.  */
 398
 399 /* Number of hash tables to maintain (at once) in any testing.  */
 400 #define TABLES (6)
 401
 402 /* We can have 12 statistics.  */
 403 #define STATBUFSIZE (12)
 404
 405 /* Display statistics here.  */
 406 int statbuf[STATBUFSIZE];
 407
 408 /* Human farts here.  */
 409 char answer[100];
 410
 411 /* We test many hash tables at once.  */
 412 char *hashtable[TABLES];
 413
 414 /* Points to current hash_control.  */
 415 char *h;
 416 char **pp;
 417 char *p;
 418 char *name;
 419 char *value;
 420 int size;
 421 int used;
 422 char command;
 423
 424 /* Number 0:TABLES-1 of current hashed symbol table.  */
 425 int number;
 426
 427 int
 428 main ()
 429 {
 430   void applicatee ();
 431   void destroy ();
 432   char *what ();
 433   int *ip;
 434
 435   number = 0;
 436   h = 0;
 437   printf ("type h <RETURN> for help\n");
 438   for (;;)
 439     {
 440       printf ("hash_test command: ");
 441       gets (answer);
 442       command = answer[0];
 443       command = TOLOWER (command);      /* Ecch!  */
 444       switch (command)
 445         {
 446         case '#':
 447           printf ("old hash table #=%d.\n", number);
 448           whattable ();
 449           break;
 450         case '?':
 451           for (pp = hashtable; pp < hashtable + TABLES; pp++)
 452             {
 453               printf ("address of hash table #%d control block is %xx\n",
 454                       pp - hashtable, *pp);
 455             }
 456           break;
 457         case 'a':
 458           hash_traverse (h, applicatee);
 459           break;
 460         case 'd':
 461           hash_traverse (h, destroy);
 462           hash_die (h);
 463           break;
 464         case 'f':
 465           p = hash_find (h, name = what ("symbol"));
 466           printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
 467           break;
 468         case 'h':
 469           printf ("# show old, select new default hash table number\n");
 470           printf ("? display all hashtable control block addresses\n");
 471           printf ("a apply a simple display-er to each symbol in table\n");
 472           printf ("d die: destroy hashtable\n");
 473           printf ("f find value of nominated symbol\n");
 474           printf ("h this help\n");
 475           printf ("i insert value into symbol\n");
 476           printf ("j jam value into symbol\n");
 477           printf ("n new hashtable\n");
 478           printf ("r replace a value with another\n");
 479           printf ("s say what %% of table is used\n");
 480           printf ("q exit this program\n");
 481           printf ("x delete a symbol from table, report its value\n");
 482           break;
 483         case 'i':
 484           p = hash_insert (h, name = what ("symbol"), value = what ("value"));
 485           if (p)
 486             {
 487               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
 488                       p);
 489             }
 490           break;
 491         case 'j':
 492           p = hash_jam (h, name = what ("symbol"), value = what ("value"));
 493           if (p)
 494             {
 495               printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
 496             }
 497           break;
 498         case 'n':
 499           h = hashtable[number] = (char *) hash_new ();
 500           break;
 501         case 'q':
 502           exit (EXIT_SUCCESS);
 503         case 'r':
 504           p = hash_replace (h, name = what ("symbol"), value = what ("value"));
 505           printf ("old value was \"%s\"\n", p ? p : "{}");
 506           break;
 507         case 's':
 508           hash_say (h, statbuf, STATBUFSIZE);
 509           for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
 510             {
 511               printf ("%d ", *ip);
 512             }
 513           printf ("\n");
 514           break;
 515         case 'x':
 516           p = hash_delete (h, name = what ("symbol"));
 517           printf ("old value was \"%s\"\n", p ? p : "{}");
 518           break;
 519         default:
 520           printf ("I can't understand command \"%c\"\n", command);
 521           break;
 522         }
 523     }
 524 }
 525
 526 char *
 527 what (description)
 528      char *description;
 529 {
 530   printf ("   %s : ", description);
 531   gets (answer);
 532   return xstrdup (answer);
 533 }
 534
 535 void
 536 destroy (string, value)
 537      char *string;
 538      char *value;
 539 {
 540   free (string);
 541   free (value);
 542 }
 543
 544 void
 545 applicatee (string, value)
 546      char *string;
 547      char *value;
 548 {
 549   printf ("%.20s-%.20s\n", string, value);
 550 }
 551
 552 /* Determine number: what hash table to use.
 553    Also determine h: points to hash_control.  */
 554
 555 void
 556 whattable ()
 557 {
 558   for (;;)
 559     {
 560       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
 561       gets (answer);
 562       sscanf (answer, "%d", &number);
 563       if (number >= 0 && number < TABLES)
 564         {
 565           h = hashtable[number];
 566           if (!h)
 567             {
 568               printf ("warning: current hash-table-#%d. has no hash-control\n", number);
 569             }
 570           return;
 571         }
 572       else
 573         {
 574           printf ("invalid hash table number: %d\n", number);
 575         }
 576     }
 577 }
 578
 579 #endif /* TEST */