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 (HT_LEN (node) == len && !memcmp (HT_STR (node), str, len))
 125         {
 126           if (insert == HT_ALLOCED)
 127             /* The string we search for was placed at the end of the
 128                obstack.  Release it.  */
 129             obstack_free (&table->stack, (PTR) str);
 130           return node;
 131         }
 132
 133       index = (index + hash2) & sizemask;
 134       table->collisions++;
 135     }
 136
 137   if (insert == HT_NO_INSERT)
 138     return NULL;
 139
 140   node = (*table->alloc_node) (table);
 141   table->entries[index] = node;
 142
 143   HT_LEN (node) = len;
 144   if (insert == HT_ALLOC)
 145     HT_STR (node) = obstack_copy0 (&table->stack, str, len);
 146   else
 147     HT_STR (node) = str;
 148
 149   if (++table->nelements * 4 >= table->nslots * 3)
 150     /* Must expand the string table.  */
 151     ht_expand (table);
 152
 153   return node;
 154 }
 155
 156 /* Double the size of a hash table, re-hashing existing entries.  */
 157
 158 static void
 159 ht_expand (table)
 160      hash_table *table;
 161 {
 162   hashnode *nentries, *p, *limit;
 163   unsigned int size, sizemask;
 164
 165   size = table->nslots * 2;
 166   nentries = (hashnode *) xcalloc (size, sizeof (hashnode));
 167   sizemask = size - 1;
 168
 169   p = table->entries;
 170   limit = p + table->nslots;
 171   do
 172     if (*p)
 173       {
 174         unsigned int index, hash, hash2;
 175
 176         hash = calc_hash (HT_STR (*p), HT_LEN (*p));
 177         hash2 = ((hash * 17) & sizemask) | 1;
 178         index = hash & sizemask;
 179
 180         for (;;)
 181           {
 182             if (! nentries[index])
 183               {
 184                 nentries[index] = *p;
 185                 break;
 186               }
 187
 188             index = (index + hash2) & sizemask;
 189           }
 190       }
 191   while (++p < limit);
 192
 193   free (table->entries);
 194   table->entries = nentries;
 195   table->nslots = size;
 196 }
 197
 198 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
 199    the node, and V.  */
 200 void
 201 ht_forall (table, cb, v)
 202      hash_table *table;
 203      ht_cb cb;
 204      const PTR v;
 205 {
 206   hashnode *p, *limit;
 207
 208   p = table->entries;
 209   limit = p + table->nslots;
 210   do
 211     if (*p)
 212       {
 213         if ((*cb) (table->pfile, *p, v) == 0)
 214           break;
 215       }
 216   while (++p < limit);
 217 }
 218
 219 /* Dump allocation statistics to stderr.  */
 220
 221 void
 222 ht_dump_statistics (table)
 223      hash_table *table;
 224 {
 225   size_t nelts, nids, overhead, headers;
 226   size_t total_bytes, longest, sum_of_squares;
 227   double exp_len, exp_len2, exp2_len;
 228   hashnode *p, *limit;
 229
 230 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 231                   ? (x) \
 232                   : ((x) < 1024*1024*10 \
 233                      ? (x) / 1024 \
 234                      : (x) / (1024*1024))))
 235 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 236
 237   total_bytes = longest = sum_of_squares = nids = 0;
 238   p = table->entries;
 239   limit = p + table->nslots;
 240   do
 241     if (*p)
 242       {
 243         size_t n = HT_LEN (*p);
 244
 245         total_bytes += n;
 246         sum_of_squares += n * n;
 247         if (n > longest)
 248           longest = n;
 249         nids++;
 250       }
 251   while (++p < limit);
 252
 253   nelts = table->nelements;
 254   overhead = obstack_memory_used (&table->stack) - total_bytes;
 255   headers = table->nslots * sizeof (hashnode);
 256
 257   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
 258            (unsigned long) nelts);
 259   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
 260            (unsigned long) nids, nids * 100.0 / nelts);
 261   fprintf (stderr, "slots\t\t%lu\n",
 262            (unsigned long) table->nslots);
 263   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
 264            SCALE (total_bytes), LABEL (total_bytes),
 265            SCALE (overhead), LABEL (overhead));
 266   fprintf (stderr, "table size\t%lu%c\n",
 267            SCALE (headers), LABEL (headers));
 268
 269   exp_len = (double)total_bytes / (double)nelts;
 270   exp2_len = exp_len * exp_len;
 271   exp_len2 = (double) sum_of_squares / (double) nelts;
 272
 273   fprintf (stderr, "coll/search\t%.4f\n",
 274            (double) table->collisions / (double) table->searches);
 275   fprintf (stderr, "ins/search\t%.4f\n",
 276            (double) nelts / (double) table->searches);
 277   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
 278            exp_len, approx_sqrt (exp_len2 - exp2_len));
 279   fprintf (stderr, "longest entry\t%lu\n",
 280            (unsigned long) longest);
 281 #undef SCALE
 282 #undef LABEL
 283 }
 284
 285 /* Return the approximate positive square root of a number N.  This is for
 286    statistical reports, not code generation.  */
 287 double
 288 approx_sqrt (x)
 289      double x;
 290 {
 291   double s, d;
 292
 293   if (x < 0)
 294     abort ();
 295   if (x == 0)
 296     return 0;
 297
 298   s = x;
 299   do
 300     {
 301       d = (s * s - x) / (2 * s);
 302       s -= d;
 303     }
 304   while (d > .0001);
 305   return s;
 306 }