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 "hashtable.h"
  25
  26 /* The code below is a specialization of Vladimir Makarov's expandable
  27    hash tables (see libiberty/hashtab.c).  The abstraction penalty was
  28    too high to continue using the generic form.  This code knows
  29    intrinsically how to calculate a hash value, and how to compare an
  30    existing entry with a potential new one.  Also, the ability to
  31    delete members from the table has been removed.  */
  32
  33 static unsigned int calc_hash PARAMS ((const unsigned char *, unsigned int));
  34 static void ht_expand PARAMS ((hash_table *));
  35
  36 /* Let particular systems override the size of a chunk.  */
  37 #ifndef OBSTACK_CHUNK_SIZE
  38 #define OBSTACK_CHUNK_SIZE 0
  39 #endif
  40   /* Let them override the alloc and free routines too.  */
  41 #ifndef OBSTACK_CHUNK_ALLOC
  42 #define OBSTACK_CHUNK_ALLOC xmalloc
  43 #endif
  44 #ifndef OBSTACK_CHUNK_FREE
  45 #define OBSTACK_CHUNK_FREE free
  46 #endif
  47
  48 /* Initialize an obstack.  */
  49 void
  50 gcc_obstack_init (obstack)
  51      struct obstack *obstack;
  52 {
  53   _obstack_begin (obstack, OBSTACK_CHUNK_SIZE, 0,
  54                   (void *(*) PARAMS ((long))) OBSTACK_CHUNK_ALLOC,
  55                   (void (*) PARAMS ((void *))) OBSTACK_CHUNK_FREE);
  56 }
  57
  58 /* Calculate the hash of the string STR of length LEN.  */
  59
  60 static unsigned int
  61 calc_hash (str, len)
  62      const unsigned char *str;
  63      unsigned int len;
  64 {
  65   unsigned int n = len;
  66   unsigned int r = 0;
  67 #define HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
  68
  69   while (n--)
  70     r = HASHSTEP (r, *str++);
  71
  72   return r + len;
  73 #undef HASHSTEP
  74 }
  75
  76 /* Initialize an identifier hashtable.  */
  77
  78 hash_table *
  79 ht_create (order)
  80      unsigned int order;
  81 {
  82   unsigned int nslots = 1 << order;
  83   hash_table *table;
  84
  85   table = (hash_table *) xmalloc (sizeof (hash_table));
  86   memset (table, 0, sizeof (hash_table));
  87
  88   /* Strings need no alignment.  */
  89   gcc_obstack_init (&table->stack);
  90   obstack_alignment_mask (&table->stack) = 0;
  91
  92   table->entries = (hashnode *) xcalloc (nslots, sizeof (hashnode));
  93   table->nslots = nslots;
  94   return table;
  95 }
  96
  97 /* Frees all memory associated with a hash table.  */
  98
  99 void
 100 ht_destroy (table)
 101      hash_table *table;
 102 {
 103   obstack_free (&table->stack, NULL);
 104   free (table->entries);
 105   free (table);
 106 }
 107
 108 /* Returns the hash entry for the a STR of length LEN.  If that string
 109    already exists in the table, returns the existing entry, and, if
 110    INSERT is CPP_ALLOCED, frees the last obstack object.  If the
 111    identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
 112    returns NULL.  Otherwise insert and returns a new entry.  A new
 113    string is alloced if INSERT is CPP_ALLOC, otherwise INSERT is
 114    CPP_ALLOCED and the item is assumed to be at the top of the
 115    obstack.  */
 116 hashnode
 117 ht_lookup (table, str, len, insert)
 118      hash_table *table;
 119      const unsigned char *str;
 120      unsigned int len;
 121      enum ht_lookup_option insert;
 122 {
 123   unsigned int hash = calc_hash (str, len);
 124   unsigned int hash2;
 125   unsigned int index;
 126   size_t sizemask;
 127   hashnode node;
 128
 129   sizemask = table->nslots - 1;
 130   index = hash & sizemask;
 131
 132   /* hash2 must be odd, so we're guaranteed to visit every possible
 133      location in the table during rehashing.  */
 134   hash2 = ((hash * 17) & sizemask) | 1;
 135   table->searches++;
 136
 137   for (;;)
 138     {
 139       node = table->entries[index];
 140
 141       if (node == NULL)
 142         break;
 143
 144       if (node->hash_value == hash && HT_LEN (node) == len
 145           && !memcmp (HT_STR (node), str, len))
 146         {
 147           if (insert == HT_ALLOCED)
 148             /* The string we search for was placed at the end of the
 149                obstack.  Release it.  */
 150             obstack_free (&table->stack, (PTR) str);
 151           return node;
 152         }
 153
 154       index = (index + hash2) & sizemask;
 155       table->collisions++;
 156     }
 157
 158   if (insert == HT_NO_INSERT)
 159     return NULL;
 160
 161   node = (*table->alloc_node) (table);
 162   table->entries[index] = node;
 163
 164   HT_LEN (node) = len;
 165   node->hash_value = hash;
 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 = (*p)->hash_value;
 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 }