libcpp/symtab.c

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