Back to index

cell-binutils  2.17cvs20070401
hash.c
Go to the documentation of this file.
00001 /* hash.c -- gas hash table code
00002    Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
00003    2000, 2001, 2002, 2003, 2005
00004    Free Software Foundation, Inc.
00005 
00006    This file is part of GAS, the GNU Assembler.
00007 
00008    GAS is free software; you can redistribute it and/or modify
00009    it under the terms of the GNU General Public License as published by
00010    the Free Software Foundation; either version 2, or (at your option)
00011    any later version.
00012 
00013    GAS is distributed in the hope that it will be useful,
00014    but WITHOUT ANY WARRANTY; without even the implied warranty of
00015    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016    GNU General Public License for more details.
00017 
00018    You should have received a copy of the GNU General Public License
00019    along with GAS; see the file COPYING.  If not, write to the Free
00020    Software Foundation, 51 Franklin Street - Fifth Floor, Boston, MA
00021    02110-1301, USA.  */
00022 
00023 /* This version of the hash table code is a wholescale replacement of
00024    the old hash table code, which was fairly bad.  This is based on
00025    the hash table code in BFD, but optimized slightly for the
00026    assembler.  The assembler does not need to derive structures that
00027    are stored in the hash table.  Instead, it always stores a pointer.
00028    The assembler uses the hash table mostly to store symbols, and we
00029    don't need to confuse the symbol structure with a hash table
00030    structure.  */
00031 
00032 #include "as.h"
00033 #include "safe-ctype.h"
00034 #include "obstack.h"
00035 
00036 /* An entry in a hash table.  */
00037 
00038 struct hash_entry {
00039   /* Next entry for this hash code.  */
00040   struct hash_entry *next;
00041   /* String being hashed.  */
00042   const char *string;
00043   /* Hash code.  This is the full hash code, not the index into the
00044      table.  */
00045   unsigned long hash;
00046   /* Pointer being stored in the hash table.  */
00047   PTR data;
00048 };
00049 
00050 /* A hash table.  */
00051 
00052 struct hash_control {
00053   /* The hash array.  */
00054   struct hash_entry **table;
00055   /* The number of slots in the hash table.  */
00056   unsigned int size;
00057   /* An obstack for this hash table.  */
00058   struct obstack memory;
00059 
00060 #ifdef HASH_STATISTICS
00061   /* Statistics.  */
00062   unsigned long lookups;
00063   unsigned long hash_compares;
00064   unsigned long string_compares;
00065   unsigned long insertions;
00066   unsigned long replacements;
00067   unsigned long deletions;
00068 #endif /* HASH_STATISTICS */
00069 };
00070 
00071 /* The default number of entries to use when creating a hash table.
00072    Note this value can be reduced to 4051 by using the command line
00073    switch --reduce-memory-overheads, or set to other values by using
00074    the --hash-size=<NUMBER> switch.  */
00075 
00076 static unsigned long gas_hash_table_size = 65537;
00077 
00078 void
00079 set_gas_hash_table_size (unsigned long size)
00080 {
00081   gas_hash_table_size = size;
00082 }
00083 
00084 /* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size().  */
00085 static unsigned long
00086 get_gas_hash_table_size (void)
00087 {
00088   /* Extend this prime list if you want more granularity of hash table size.  */
00089   static const unsigned long hash_size_primes[] =
00090     {
00091       1021, 4051, 8599, 16699, 65537
00092     };
00093   unsigned int index;
00094 
00095   /* Work out the best prime number near the hash_size.
00096      FIXME: This could be a more sophisticated algorithm,
00097      but is it really worth implementing it ?   */
00098   for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index)
00099     if (gas_hash_table_size <= hash_size_primes[index])
00100       break;
00101 
00102   return hash_size_primes[index];
00103 }
00104 
00105 /* Create a hash table.  This return a control block.  */
00106 
00107 struct hash_control *
00108 hash_new (void)
00109 {
00110   unsigned long size;
00111   unsigned long alloc;
00112   struct hash_control *ret;
00113 
00114   size = get_gas_hash_table_size ();
00115 
00116   ret = xmalloc (sizeof *ret);
00117   obstack_begin (&ret->memory, chunksize);
00118   alloc = size * sizeof (struct hash_entry *);
00119   ret->table = obstack_alloc (&ret->memory, alloc);
00120   memset (ret->table, 0, alloc);
00121   ret->size = size;
00122 
00123 #ifdef HASH_STATISTICS
00124   ret->lookups = 0;
00125   ret->hash_compares = 0;
00126   ret->string_compares = 0;
00127   ret->insertions = 0;
00128   ret->replacements = 0;
00129   ret->deletions = 0;
00130 #endif
00131 
00132   return ret;
00133 }
00134 
00135 /* Delete a hash table, freeing all allocated memory.  */
00136 
00137 void
00138 hash_die (struct hash_control *table)
00139 {
00140   obstack_free (&table->memory, 0);
00141   free (table);
00142 }
00143 
00144 /* Look up a string in a hash table.  This returns a pointer to the
00145    hash_entry, or NULL if the string is not in the table.  If PLIST is
00146    not NULL, this sets *PLIST to point to the start of the list which
00147    would hold this hash entry.  If PHASH is not NULL, this sets *PHASH
00148    to the hash code for KEY.
00149 
00150    Each time we look up a string, we move it to the start of the list
00151    for its hash code, to take advantage of referential locality.  */
00152 
00153 static struct hash_entry *
00154 hash_lookup (struct hash_control *table, const char *key, size_t len,
00155             struct hash_entry ***plist, unsigned long *phash)
00156 {
00157   unsigned long hash;
00158   size_t n;
00159   unsigned int c;
00160   unsigned int index;
00161   struct hash_entry **list;
00162   struct hash_entry *p;
00163   struct hash_entry *prev;
00164 
00165 #ifdef HASH_STATISTICS
00166   ++table->lookups;
00167 #endif
00168 
00169   hash = 0;
00170   for (n = 0; n < len; n++)
00171     {
00172       c = key[n];
00173       hash += c + (c << 17);
00174       hash ^= hash >> 2;
00175     }
00176   hash += len + (len << 17);
00177   hash ^= hash >> 2;
00178 
00179   if (phash != NULL)
00180     *phash = hash;
00181 
00182   index = hash % table->size;
00183   list = table->table + index;
00184 
00185   if (plist != NULL)
00186     *plist = list;
00187 
00188   prev = NULL;
00189   for (p = *list; p != NULL; p = p->next)
00190     {
00191 #ifdef HASH_STATISTICS
00192       ++table->hash_compares;
00193 #endif
00194 
00195       if (p->hash == hash)
00196        {
00197 #ifdef HASH_STATISTICS
00198          ++table->string_compares;
00199 #endif
00200 
00201          if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
00202            {
00203              if (prev != NULL)
00204               {
00205                 prev->next = p->next;
00206                 p->next = *list;
00207                 *list = p;
00208               }
00209 
00210              return p;
00211            }
00212        }
00213 
00214       prev = p;
00215     }
00216 
00217   return NULL;
00218 }
00219 
00220 /* Insert an entry into a hash table.  This returns NULL on success.
00221    On error, it returns a printable string indicating the error.  It
00222    is considered to be an error if the entry already exists in the
00223    hash table.  */
00224 
00225 const char *
00226 hash_insert (struct hash_control *table, const char *key, PTR value)
00227 {
00228   struct hash_entry *p;
00229   struct hash_entry **list;
00230   unsigned long hash;
00231 
00232   p = hash_lookup (table, key, strlen (key), &list, &hash);
00233   if (p != NULL)
00234     return "exists";
00235 
00236 #ifdef HASH_STATISTICS
00237   ++table->insertions;
00238 #endif
00239 
00240   p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
00241   p->string = key;
00242   p->hash = hash;
00243   p->data = value;
00244 
00245   p->next = *list;
00246   *list = p;
00247 
00248   return NULL;
00249 }
00250 
00251 /* Insert or replace an entry in a hash table.  This returns NULL on
00252    success.  On error, it returns a printable string indicating the
00253    error.  If an entry already exists, its value is replaced.  */
00254 
00255 const char *
00256 hash_jam (struct hash_control *table, const char *key, PTR value)
00257 {
00258   struct hash_entry *p;
00259   struct hash_entry **list;
00260   unsigned long hash;
00261 
00262   p = hash_lookup (table, key, strlen (key), &list, &hash);
00263   if (p != NULL)
00264     {
00265 #ifdef HASH_STATISTICS
00266       ++table->replacements;
00267 #endif
00268 
00269       p->data = value;
00270     }
00271   else
00272     {
00273 #ifdef HASH_STATISTICS
00274       ++table->insertions;
00275 #endif
00276 
00277       p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
00278       p->string = key;
00279       p->hash = hash;
00280       p->data = value;
00281 
00282       p->next = *list;
00283       *list = p;
00284     }
00285 
00286   return NULL;
00287 }
00288 
00289 /* Replace an existing entry in a hash table.  This returns the old
00290    value stored for the entry.  If the entry is not found in the hash
00291    table, this does nothing and returns NULL.  */
00292 
00293 PTR
00294 hash_replace (struct hash_control *table, const char *key, PTR value)
00295 {
00296   struct hash_entry *p;
00297   PTR ret;
00298 
00299   p = hash_lookup (table, key, strlen (key), NULL, NULL);
00300   if (p == NULL)
00301     return NULL;
00302 
00303 #ifdef HASH_STATISTICS
00304   ++table->replacements;
00305 #endif
00306 
00307   ret = p->data;
00308 
00309   p->data = value;
00310 
00311   return ret;
00312 }
00313 
00314 /* Find an entry in a hash table, returning its value.  Returns NULL
00315    if the entry is not found.  */
00316 
00317 PTR
00318 hash_find (struct hash_control *table, const char *key)
00319 {
00320   struct hash_entry *p;
00321 
00322   p = hash_lookup (table, key, strlen (key), NULL, NULL);
00323   if (p == NULL)
00324     return NULL;
00325 
00326   return p->data;
00327 }
00328 
00329 /* As hash_find, but KEY is of length LEN and is not guaranteed to be
00330    NUL-terminated.  */
00331 
00332 PTR
00333 hash_find_n (struct hash_control *table, const char *key, size_t len)
00334 {
00335   struct hash_entry *p;
00336 
00337   p = hash_lookup (table, key, len, NULL, NULL);
00338   if (p == NULL)
00339     return NULL;
00340 
00341   return p->data;
00342 }
00343 
00344 /* Delete an entry from a hash table.  This returns the value stored
00345    for that entry, or NULL if there is no such entry.  */
00346 
00347 PTR
00348 hash_delete (struct hash_control *table, const char *key)
00349 {
00350   struct hash_entry *p;
00351   struct hash_entry **list;
00352 
00353   p = hash_lookup (table, key, strlen (key), &list, NULL);
00354   if (p == NULL)
00355     return NULL;
00356 
00357   if (p != *list)
00358     abort ();
00359 
00360 #ifdef HASH_STATISTICS
00361   ++table->deletions;
00362 #endif
00363 
00364   *list = p->next;
00365 
00366   /* Note that we never reclaim the memory for this entry.  If gas
00367      ever starts deleting hash table entries in a big way, this will
00368      have to change.  */
00369 
00370   return p->data;
00371 }
00372 
00373 /* Traverse a hash table.  Call the function on every entry in the
00374    hash table.  */
00375 
00376 void
00377 hash_traverse (struct hash_control *table,
00378               void (*pfn) (const char *key, PTR value))
00379 {
00380   unsigned int i;
00381 
00382   for (i = 0; i < table->size; ++i)
00383     {
00384       struct hash_entry *p;
00385 
00386       for (p = table->table[i]; p != NULL; p = p->next)
00387        (*pfn) (p->string, p->data);
00388     }
00389 }
00390 
00391 /* Print hash table statistics on the specified file.  NAME is the
00392    name of the hash table, used for printing a header.  */
00393 
00394 void
00395 hash_print_statistics (FILE *f ATTRIBUTE_UNUSED,
00396                      const char *name ATTRIBUTE_UNUSED,
00397                      struct hash_control *table ATTRIBUTE_UNUSED)
00398 {
00399 #ifdef HASH_STATISTICS
00400   unsigned int i;
00401   unsigned long total;
00402   unsigned long empty;
00403 
00404   fprintf (f, "%s hash statistics:\n", name);
00405   fprintf (f, "\t%lu lookups\n", table->lookups);
00406   fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
00407   fprintf (f, "\t%lu string comparisons\n", table->string_compares);
00408   fprintf (f, "\t%lu insertions\n", table->insertions);
00409   fprintf (f, "\t%lu replacements\n", table->replacements);
00410   fprintf (f, "\t%lu deletions\n", table->deletions);
00411 
00412   total = 0;
00413   empty = 0;
00414   for (i = 0; i < table->size; ++i)
00415     {
00416       struct hash_entry *p;
00417 
00418       if (table->table[i] == NULL)
00419        ++empty;
00420       else
00421        {
00422          for (p = table->table[i]; p != NULL; p = p->next)
00423            ++total;
00424        }
00425     }
00426 
00427   fprintf (f, "\t%g average chain length\n", (double) total / table->size);
00428   fprintf (f, "\t%lu empty slots\n", empty);
00429 #endif
00430 }
00431 
00432 #ifdef TEST
00433 
00434 /* This test program is left over from the old hash table code.  */
00435 
00436 /* Number of hash tables to maintain (at once) in any testing.  */
00437 #define TABLES (6)
00438 
00439 /* We can have 12 statistics.  */
00440 #define STATBUFSIZE (12)
00441 
00442 /* Display statistics here.  */
00443 int statbuf[STATBUFSIZE];
00444 
00445 /* Human farts here.  */
00446 char answer[100];
00447 
00448 /* We test many hash tables at once.  */
00449 char *hashtable[TABLES];
00450 
00451 /* Points to current hash_control.  */
00452 char *h;
00453 char **pp;
00454 char *p;
00455 char *name;
00456 char *value;
00457 int size;
00458 int used;
00459 char command;
00460 
00461 /* Number 0:TABLES-1 of current hashed symbol table.  */
00462 int number;
00463 
00464 int
00465 main ()
00466 {
00467   void applicatee ();
00468   void destroy ();
00469   char *what ();
00470   int *ip;
00471 
00472   number = 0;
00473   h = 0;
00474   printf ("type h <RETURN> for help\n");
00475   for (;;)
00476     {
00477       printf ("hash_test command: ");
00478       gets (answer);
00479       command = answer[0];
00480       command = TOLOWER (command); /* Ecch!  */
00481       switch (command)
00482        {
00483        case '#':
00484          printf ("old hash table #=%d.\n", number);
00485          whattable ();
00486          break;
00487        case '?':
00488          for (pp = hashtable; pp < hashtable + TABLES; pp++)
00489            {
00490              printf ("address of hash table #%d control block is %xx\n",
00491                     pp - hashtable, *pp);
00492            }
00493          break;
00494        case 'a':
00495          hash_traverse (h, applicatee);
00496          break;
00497        case 'd':
00498          hash_traverse (h, destroy);
00499          hash_die (h);
00500          break;
00501        case 'f':
00502          p = hash_find (h, name = what ("symbol"));
00503          printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
00504          break;
00505        case 'h':
00506          printf ("# show old, select new default hash table number\n");
00507          printf ("? display all hashtable control block addresses\n");
00508          printf ("a apply a simple display-er to each symbol in table\n");
00509          printf ("d die: destroy hashtable\n");
00510          printf ("f find value of nominated symbol\n");
00511          printf ("h this help\n");
00512          printf ("i insert value into symbol\n");
00513          printf ("j jam value into symbol\n");
00514          printf ("n new hashtable\n");
00515          printf ("r replace a value with another\n");
00516          printf ("s say what %% of table is used\n");
00517          printf ("q exit this program\n");
00518          printf ("x delete a symbol from table, report its value\n");
00519          break;
00520        case 'i':
00521          p = hash_insert (h, name = what ("symbol"), value = what ("value"));
00522          if (p)
00523            {
00524              printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value,
00525                     p);
00526            }
00527          break;
00528        case 'j':
00529          p = hash_jam (h, name = what ("symbol"), value = what ("value"));
00530          if (p)
00531            {
00532              printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
00533            }
00534          break;
00535        case 'n':
00536          h = hashtable[number] = (char *) hash_new ();
00537          break;
00538        case 'q':
00539          exit (EXIT_SUCCESS);
00540        case 'r':
00541          p = hash_replace (h, name = what ("symbol"), value = what ("value"));
00542          printf ("old value was \"%s\"\n", p ? p : "{}");
00543          break;
00544        case 's':
00545          hash_say (h, statbuf, STATBUFSIZE);
00546          for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
00547            {
00548              printf ("%d ", *ip);
00549            }
00550          printf ("\n");
00551          break;
00552        case 'x':
00553          p = hash_delete (h, name = what ("symbol"));
00554          printf ("old value was \"%s\"\n", p ? p : "{}");
00555          break;
00556        default:
00557          printf ("I can't understand command \"%c\"\n", command);
00558          break;
00559        }
00560     }
00561 }
00562 
00563 char *
00564 what (description)
00565      char *description;
00566 {
00567   printf ("   %s : ", description);
00568   gets (answer);
00569   return xstrdup (answer);
00570 }
00571 
00572 void
00573 destroy (string, value)
00574      char *string;
00575      char *value;
00576 {
00577   free (string);
00578   free (value);
00579 }
00580 
00581 void
00582 applicatee (string, value)
00583      char *string;
00584      char *value;
00585 {
00586   printf ("%.20s-%.20s\n", string, value);
00587 }
00588 
00589 /* Determine number: what hash table to use.
00590    Also determine h: points to hash_control.  */
00591 
00592 void
00593 whattable ()
00594 {
00595   for (;;)
00596     {
00597       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
00598       gets (answer);
00599       sscanf (answer, "%d", &number);
00600       if (number >= 0 && number < TABLES)
00601        {
00602          h = hashtable[number];
00603          if (!h)
00604            {
00605              printf ("warning: current hash-table-#%d. has no hash-control\n", number);
00606            }
00607          return;
00608        }
00609       else
00610        {
00611          printf ("invalid hash table number: %d\n", number);
00612        }
00613     }
00614 }
00615 
00616 #endif /* TEST */