gcc/hashtable.c

   1 /* Hash tables.
   2    Copyright (C) 2000, 2001 Free Software Foundation, Inc.
   3
   4 This program is free software; you can redistribute it and/or modify it
   5 under the terms of the GNU General Public License as published by the
   6 Free Software Foundation; either version 2, or (at your option) any
   7 later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  17
  18  In other words, you are welcome to use, share and improve this program.
  19  You are forbidden to forbid anyone else to use, share and improve
  20  what you give them.   Help stamp out software-hoarding!  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "hashtable.h"
  27
  28 /* The code below is a specialization of Vladimir Makarov's expandable
  29    hash tables (see libiberty/hashtab.c).  The abstraction penalty was
  30    too high to continue using the generic form.  This code knows
  31    intrinsically how to calculate a hash value, and how to compare an
  32    existing entry with a potential new one.  Also, the ability to
  33    delete members from the table has been removed.  */
  34
  35 static unsigned int calc_hash PARAMS ((const unsigned char *, unsigned int));
  36 static void ht_expand PARAMS ((hash_table *));
  37
  38 /* Calculate the hash of the string STR of length LEN.  */
  39
  40 static unsigned int
  41 calc_hash (str, len)
  42      const unsigned char *str;
  43      unsigned int len;
  44 {
  45   unsigned int n = len;
  46   unsigned int r = 0;
  47 #define HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
  48
  49   while (n--)
  50     r = HASHSTEP (r, *str++);
  51
  52   return r + len;
  53 #undef HASHSTEP
  54 }
  55
  56 /* Initialize an identifier hashtable.  */
  57
  58 hash_table *
  59 ht_create (order)
  60      unsigned int order;
  61 {
  62   unsigned int nslots = 1 << order;
  63   hash_table *table;
  64
  65   table = (hash_table *) xmalloc (sizeof (hash_table));
  66   memset (table, 0, sizeof (hash_table));
  67
  68   /* Strings need no alignment.  */
  69   gcc_obstack_init (&table->stack);
  70   obstack_alignment_mask (&table->stack) = 0;
  71
  72   table->entries = (hashnode *) xcalloc (nslots, sizeof (hashnode));
  73   table->nslots = nslots;
  74   return table;
  75 }
  76
  77 /* Frees all memory associated with a hash table.  */
  78
  79 void
  80 ht_destroy (table)
  81      hash_table *table;
  82 {
  83   obstack_free (&table->stack, NULL);
  84   free (table->entries);
  85   free (table);
  86 }
  87
  88 /* Returns the hash entry for the a STR of length LEN.  If that string
  89    already exists in the table, returns the existing entry, and, if
  90    INSERT is CPP_ALLOCED, frees the last obstack object.  If the
  91    identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
  92    returns NULL.  Otherwise insert and returns a new entry.  A new
  93    string is alloced if INSERT is CPP_ALLOC, otherwise INSERT is
  94    CPP_ALLOCED and the item is assumed to be at the top of the
  95    obstack.  */
  96 hashnode
  97 ht_lookup (table, str, len, insert)
  98      hash_table *table;
  99      const unsigned char *str;
 100      unsigned int len;
 101      enum ht_lookup_option insert;
 102 {
 103   unsigned int hash = calc_hash (str, len);
 104   unsigned int hash2;
 105   unsigned int index;
 106   size_t sizemask;
 107   hashnode node;
 108
 109   sizemask = table->nslots - 1;
 110   index = hash & sizemask;
 111
 112   /* hash2 must be odd, so we're guaranteed to visit every possible
 113      location in the table during rehashing.  */
 114   hash2 = ((hash * 17) & sizemask) | 1;
 115   table->searches++;
 116
 117   for (;;)
 118     {
 119       node = table->entries[index];
 120
 121       if (node == NULL)
 122         break;
 123
 124       if (node->hash_value == hash && HT_LEN (node) == len
 125           && !memcmp (HT_STR (node), str, len))
 126         {
 127           if (insert == HT_ALLOCED)
 128             /* The string we search for was placed at the end of the
 129                obstack.  Release it.  */
 130             obstack_free (&table->stack, (PTR) str);
 131           return node;
 132         }
 133
 134       index = (index + hash2) & sizemask;
 135       table->collisions++;
 136     }
 137
 138   if (insert == HT_NO_INSERT)
 139     return NULL;
 140
 141   node = (*table->alloc_node) (table);
 142   table->entries[index] = node;
 143
 144   HT_LEN (node) = len;
 145   node->hash_value = hash;
 146   if (insert == HT_ALLOC)
 147     HT_STR (node) = obstack_copy0 (&table->stack, str, len);
 148   else
 149     HT_STR (node) = str;
 150
 151   if (++table->nelements * 4 >= table->nslots * 3)
 152     /* Must expand the string table.  */
 153     ht_expand (table);
 154
 155   return node;
 156 }
 157
 158 /* Double the size of a hash table, re-hashing existing entries.  */
 159
 160 static void
 161 ht_expand (table)
 162      hash_table *table;
 163 {
 164   hashnode *nentries, *p, *limit;
 165   unsigned int size, sizemask;
 166
 167   size = table->nslots * 2;
 168   nentries = (hashnode *) xcalloc (size, sizeof (hashnode));
 169   sizemask = size - 1;
 170
 171   p = table->entries;
 172   limit = p + table->nslots;
 173   do
 174     if (*p)
 175       {
 176         unsigned int index, hash, hash2;
 177
 178         hash = (*p)->hash_value;
 179         hash2 = ((hash * 17) & sizemask) | 1;
 180         index = hash & sizemask;
 181
 182         for (;;)
 183           {
 184             if (! nentries[index])
 185               {
 186                 nentries[index] = *p;
 187                 break;
 188               }
 189
 190             index = (index + hash2) & sizemask;
 191           }
 192       }
 193   while (++p < limit);
 194
 195   free (table->entries);
 196   table->entries = nentries;
 197   table->nslots = size;
 198 }
 199
 200 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
 201    the node, and V.  */
 202 void
 203 ht_forall (table, cb, v)
 204      hash_table *table;
 205      ht_cb cb;
 206      const PTR v;
 207 {
 208   hashnode *p, *limit;
 209
 210   p = table->entries;
 211   limit = p + table->nslots;
 212   do
 213     if (*p)
 214       {
 215         if ((*cb) (table->pfile, *p, v) == 0)
 216           break;
 217       }
 218   while (++p < limit);
 219 }
 220
 221 /* Dump allocation statistics to stderr.  */
 222
 223 void
 224 ht_dump_statistics (table)
 225      hash_table *table;
 226 {
 227   size_t nelts, nids, overhead, headers;
 228   size_t total_bytes, longest, sum_of_squares;
 229   double exp_len, exp_len2, exp2_len;
 230   hashnode *p, *limit;
 231
 232 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 233                   ? (x) \
 234                   : ((x) < 1024*1024*10 \
 235                      ? (x) / 1024 \
 236                      : (x) / (1024*1024))))
 237 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 238
 239   total_bytes = longest = sum_of_squares = nids = 0;
 240   p = table->entries;
 241   limit = p + table->nslots;
 242   do
 243     if (*p)
 244       {
 245         size_t n = HT_LEN (*p);
 246
 247         total_bytes += n;
 248         sum_of_squares += n * n;
 249         if (n > longest)
 250           longest = n;
 251         nids++;
 252       }
 253   while (++p < limit);
 254
 255   nelts = table->nelements;
 256   overhead = obstack_memory_used (&table->stack) - total_bytes;
 257   headers = table->nslots * sizeof (hashnode);
 258
 259   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
 260            (unsigned long) nelts);
 261   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
 262            (unsigned long) nids, nids * 100.0 / nelts);
 263   fprintf (stderr, "slots\t\t%lu\n",
 264            (unsigned long) table->nslots);
 265   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
 266            SCALE (total_bytes), LABEL (total_bytes),
 267            SCALE (overhead), LABEL (overhead));
 268   fprintf (stderr, "table size\t%lu%c\n",
 269            SCALE (headers), LABEL (headers));
 270
 271   exp_len = (double)total_bytes / (double)nelts;
 272   exp2_len = exp_len * exp_len;
 273   exp_len2 = (double) sum_of_squares / (double) nelts;
 274
 275   fprintf (stderr, "coll/search\t%.4f\n",
 276            (double) table->collisions / (double) table->searches);
 277   fprintf (stderr, "ins/search\t%.4f\n",
 278            (double) nelts / (double) table->searches);
 279   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
 280            exp_len, approx_sqrt (exp_len2 - exp2_len));
 281   fprintf (stderr, "longest entry\t%lu\n",
 282            (unsigned long) longest);
 283 #undef SCALE
 284 #undef LABEL
 285 }
 286
 287 /* Return the approximate positive square root of a number N.  This is for
 288    statistical reports, not code generation.  */
 289 double
 290 approx_sqrt (x)
 291      double x;
 292 {
 293   double s, d;
 294
 295   if (x < 0)
 296     abort ();
 297   if (x == 0)
 298     return 0;
 299
 300   s = x;
 301   do
 302     {
 303       d = (s * s - x) / (2 * s);
 304       s -= d;
 305     }
 306   while (d > .0001);
 307   return s;
 308 }