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 /* Let particular systems override the size of a chunk.  */
  39 #ifndef OBSTACK_CHUNK_SIZE
  40 #define OBSTACK_CHUNK_SIZE 0
  41 #endif
  42   /* Let them override the alloc and free routines too.  */
  43 #ifndef OBSTACK_CHUNK_ALLOC
  44 #define OBSTACK_CHUNK_ALLOC xmalloc
  45 #endif
  46 #ifndef OBSTACK_CHUNK_FREE
  47 #define OBSTACK_CHUNK_FREE free
  48 #endif
  49
  50 /* Initialize an obstack.  */
  51 void
  52 gcc_obstack_init (obstack)
  53      struct obstack *obstack;
  54 {
  55   _obstack_begin (obstack, OBSTACK_CHUNK_SIZE, 0,
  56                   (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC,
  57                   (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE);
  58 }
  59
  60 /* Calculate the hash of the string STR of length LEN.  */
  61
  62 static unsigned int
  63 calc_hash (str, len)
  64      const unsigned char *str;
  65      unsigned int len;
  66 {
  67   unsigned int n = len;
  68   unsigned int r = 0;
  69 #define HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
  70
  71   while (n--)
  72     r = HASHSTEP (r, *str++);
  73
  74   return r + len;
  75 #undef HASHSTEP
  76 }
  77
  78 /* Initialize an identifier hashtable.  */
  79
  80 hash_table *
  81 ht_create (order)
  82      unsigned int order;
  83 {
  84   unsigned int nslots = 1 << order;
  85   hash_table *table;
  86
  87   table = (hash_table *) xmalloc (sizeof (hash_table));
  88   memset (table, 0, sizeof (hash_table));
  89
  90   /* Strings need no alignment.  */
  91   gcc_obstack_init (&table->stack);
  92   obstack_alignment_mask (&table->stack) = 0;
  93
  94   table->entries = (hashnode *) xcalloc (nslots, sizeof (hashnode));
  95   table->nslots = nslots;
  96   return table;
  97 }
  98
  99 /* Frees all memory associated with a hash table.  */
 100
 101 void
 102 ht_destroy (table)
 103      hash_table *table;
 104 {
 105   obstack_free (&table->stack, NULL);
 106   free (table->entries);
 107   free (table);
 108 }
 109
 110 /* Returns the hash entry for the a STR of length LEN.  If that string
 111    already exists in the table, returns the existing entry, and, if
 112    INSERT is CPP_ALLOCED, frees the last obstack object.  If the
 113    identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
 114    returns NULL.  Otherwise insert and returns a new entry.  A new
 115    string is alloced if INSERT is CPP_ALLOC, otherwise INSERT is
 116    CPP_ALLOCED and the item is assumed to be at the top of the
 117    obstack.  */
 118 hashnode
 119 ht_lookup (table, str, len, insert)
 120      hash_table *table;
 121      const unsigned char *str;
 122      unsigned int len;
 123      enum ht_lookup_option insert;
 124 {
 125   unsigned int hash = calc_hash (str, len);
 126   unsigned int hash2;
 127   unsigned int index;
 128   size_t sizemask;
 129   hashnode node;
 130
 131   sizemask = table->nslots - 1;
 132   index = hash & sizemask;
 133
 134   /* hash2 must be odd, so we're guaranteed to visit every possible
 135      location in the table during rehashing.  */
 136   hash2 = ((hash * 17) & sizemask) | 1;
 137   table->searches++;
 138
 139   for (;;)
 140     {
 141       node = table->entries[index];
 142
 143       if (node == NULL)
 144         break;
 145
 146       if (HT_LEN (node) == len && !memcmp (HT_STR (node), str, len))
 147         {
 148           if (insert == HT_ALLOCED)
 149             /* The string we search for was placed at the end of the
 150                obstack.  Release it.  */
 151             obstack_free (&table->stack, (PTR) str);
 152           return node;
 153         }
 154
 155       index = (index + hash2) & sizemask;
 156       table->collisions++;
 157     }
 158
 159   if (insert == HT_NO_INSERT)
 160     return NULL;
 161
 162   node = (*table->alloc_node) (table);
 163   table->entries[index] = node;
 164
 165   HT_LEN (node) = len;
 166   if (insert == HT_ALLOC)
 167     HT_STR (node) = obstack_copy0 (&table->stack, str, len);
 168   else
 169     HT_STR (node) = str;
 170
 171   if (++table->nelements * 4 >= table->nslots * 3)
 172     /* Must expand the string table.  */
 173     ht_expand (table);
 174
 175   return node;
 176 }
 177
 178 /* Double the size of a hash table, re-hashing existing entries.  */
 179
 180 static void
 181 ht_expand (table)
 182      hash_table *table;
 183 {
 184   hashnode *nentries, *p, *limit;
 185   unsigned int size, sizemask;
 186
 187   size = table->nslots * 2;
 188   nentries = (hashnode *) xcalloc (size, sizeof (hashnode));
 189   sizemask = size - 1;
 190
 191   p = table->entries;
 192   limit = p + table->nslots;
 193   do
 194     if (*p)
 195       {
 196         unsigned int index, hash, hash2;
 197
 198         hash = calc_hash (HT_STR (*p), HT_LEN (*p));
 199         hash2 = ((hash * 17) & sizemask) | 1;
 200         index = hash & sizemask;
 201
 202         for (;;)
 203           {
 204             if (! nentries[index])
 205               {
 206                 nentries[index] = *p;
 207                 break;
 208               }
 209
 210             index = (index + hash2) & sizemask;
 211           }
 212       }
 213   while (++p < limit);
 214
 215   free (table->entries);
 216   table->entries = nentries;
 217   table->nslots = size;
 218 }
 219
 220 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
 221    the node, and V.  */
 222 void
 223 ht_forall (table, cb, v)
 224      hash_table *table;
 225      ht_cb cb;
 226      const PTR v;
 227 {
 228   hashnode *p, *limit;
 229
 230   p = table->entries;
 231   limit = p + table->nslots;
 232   do
 233     if (*p)
 234       {
 235         if ((*cb) (table->pfile, *p, v) == 0)
 236           break;
 237       }
 238   while (++p < limit);
 239 }
 240
 241 /* Dump allocation statistics to stderr.  */
 242
 243 void
 244 ht_dump_statistics (table)
 245      hash_table *table;
 246 {
 247   size_t nelts, nids, overhead, headers;
 248   size_t total_bytes, longest, sum_of_squares;
 249   double exp_len, exp_len2, exp2_len;
 250   hashnode *p, *limit;
 251
 252 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 253                   ? (x) \
 254                   : ((x) < 1024*1024*10 \
 255                      ? (x) / 1024 \
 256                      : (x) / (1024*1024))))
 257 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 258
 259   total_bytes = longest = sum_of_squares = nids = 0;
 260   p = table->entries;
 261   limit = p + table->nslots;
 262   do
 263     if (*p)
 264       {
 265         size_t n = HT_LEN (*p);
 266
 267         total_bytes += n;
 268         sum_of_squares += n * n;
 269         if (n > longest)
 270           longest = n;
 271         nids++;
 272       }
 273   while (++p < limit);
 274
 275   nelts = table->nelements;
 276   overhead = obstack_memory_used (&table->stack) - total_bytes;
 277   headers = table->nslots * sizeof (hashnode);
 278
 279   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
 280            (unsigned long) nelts);
 281   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
 282            (unsigned long) nids, nids * 100.0 / nelts);
 283   fprintf (stderr, "slots\t\t%lu\n",
 284            (unsigned long) table->nslots);
 285   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
 286            SCALE (total_bytes), LABEL (total_bytes),
 287            SCALE (overhead), LABEL (overhead));
 288   fprintf (stderr, "table size\t%lu%c\n",
 289            SCALE (headers), LABEL (headers));
 290
 291   exp_len = (double)total_bytes / (double)nelts;
 292   exp2_len = exp_len * exp_len;
 293   exp_len2 = (double) sum_of_squares / (double) nelts;
 294
 295   fprintf (stderr, "coll/search\t%.4f\n",
 296            (double) table->collisions / (double) table->searches);
 297   fprintf (stderr, "ins/search\t%.4f\n",
 298            (double) nelts / (double) table->searches);
 299   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
 300            exp_len, approx_sqrt (exp_len2 - exp2_len));
 301   fprintf (stderr, "longest entry\t%lu\n",
 302            (unsigned long) longest);
 303 #undef SCALE
 304 #undef LABEL
 305 }
 306
 307 /* Return the approximate positive square root of a number N.  This is for
 308    statistical reports, not code generation.  */
 309 double
 310 approx_sqrt (x)
 311      double x;
 312 {
 313   double s, d;
 314
 315   if (x < 0)
 316     abort ();
 317   if (x == 0)
 318     return 0;
 319
 320   s = x;
 321   do
 322     {
 323       d = (s * s - x) / (2 * s);
 324       s -= d;
 325     }
 326   while (d > .0001);
 327   return s;
 328 }