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, 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 "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 = xcalloc (1, sizeof (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 = xcalloc (nslots, sizeof (hashnode));
  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) = obstack_copy0 (&table->stack, str, len);
 165   else
 166     HT_STR (node) = str;
 167
 168   if (++table->nelements * 4 >= table->nslots * 3)
 169     /* Must expand the string table.  */
 170     ht_expand (table);
 171
 172   return node;
 173 }
 174
 175 /* Double the size of a hash table, re-hashing existing entries.  */
 176
 177 static void
 178 ht_expand (hash_table *table)
 179 {
 180   hashnode *nentries, *p, *limit;
 181   unsigned int size, sizemask;
 182
 183   size = table->nslots * 2;
 184   nentries = xcalloc (size, sizeof (hashnode));
 185   sizemask = size - 1;
 186
 187   p = table->entries;
 188   limit = p + table->nslots;
 189   do
 190     if (*p)
 191       {
 192         unsigned int index, hash, hash2;
 193
 194         hash = (*p)->hash_value;
 195         index = hash & sizemask;
 196
 197         if (nentries[index])
 198           {
 199             hash2 = ((hash * 17) & sizemask) | 1;
 200             do
 201               {
 202                 index = (index + hash2) & sizemask;
 203               }
 204             while (nentries[index]);
 205           }
 206         nentries[index] = *p;
 207       }
 208   while (++p < limit);
 209
 210   if (table->entries_owned)
 211     free (table->entries);
 212   table->entries_owned = true;
 213   table->entries = nentries;
 214   table->nslots = size;
 215 }
 216
 217 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
 218    the node, and V.  */
 219 void
 220 ht_forall (hash_table *table, ht_cb cb, const void *v)
 221 {
 222   hashnode *p, *limit;
 223
 224   p = table->entries;
 225   limit = p + table->nslots;
 226   do
 227     if (*p)
 228       {
 229         if ((*cb) (table->pfile, *p, v) == 0)
 230           break;
 231       }
 232   while (++p < limit);
 233 }
 234
 235 /* Restore the hash table.  */
 236 void
 237 ht_load (hash_table *ht, hashnode *entries,
 238          unsigned int nslots, unsigned int nelements,
 239          bool own)
 240 {
 241   if (ht->entries_owned)
 242     free (ht->entries);
 243   ht->entries = entries;
 244   ht->nslots = nslots;
 245   ht->nelements = nelements;
 246   ht->entries_owned = own;
 247 }
 248
 249 /* Dump allocation statistics to stderr.  */
 250
 251 void
 252 ht_dump_statistics (hash_table *table)
 253 {
 254   size_t nelts, nids, overhead, headers;
 255   size_t total_bytes, longest;
 256   double sum_of_squares, exp_len, exp_len2, exp2_len;
 257   hashnode *p, *limit;
 258
 259 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 260                   ? (x) \
 261                   : ((x) < 1024*1024*10 \
 262                      ? (x) / 1024 \
 263                      : (x) / (1024*1024))))
 264 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 265
 266   total_bytes = longest = sum_of_squares = nids = 0;
 267   p = table->entries;
 268   limit = p + table->nslots;
 269   do
 270     if (*p)
 271       {
 272         size_t n = HT_LEN (*p);
 273
 274         total_bytes += n;
 275         sum_of_squares += (double) n * n;
 276         if (n > longest)
 277           longest = n;
 278         nids++;
 279       }
 280   while (++p < limit);
 281
 282   nelts = table->nelements;
 283   overhead = obstack_memory_used (&table->stack) - total_bytes;
 284   headers = table->nslots * sizeof (hashnode);
 285
 286   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
 287            (unsigned long) nelts);
 288   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
 289            (unsigned long) nids, nids * 100.0 / nelts);
 290   fprintf (stderr, "slots\t\t%lu\n",
 291            (unsigned long) table->nslots);
 292   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
 293            SCALE (total_bytes), LABEL (total_bytes),
 294            SCALE (overhead), LABEL (overhead));
 295   fprintf (stderr, "table size\t%lu%c\n",
 296            SCALE (headers), LABEL (headers));
 297
 298   exp_len = (double)total_bytes / (double)nelts;
 299   exp2_len = exp_len * exp_len;
 300   exp_len2 = (double) sum_of_squares / (double) nelts;
 301
 302   fprintf (stderr, "coll/search\t%.4f\n",
 303            (double) table->collisions / (double) table->searches);
 304   fprintf (stderr, "ins/search\t%.4f\n",
 305            (double) nelts / (double) table->searches);
 306   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
 307            exp_len, approx_sqrt (exp_len2 - exp2_len));
 308   fprintf (stderr, "longest entry\t%lu\n",
 309            (unsigned long) longest);
 310 #undef SCALE
 311 #undef LABEL
 312 }
 313
 314 /* Return the approximate positive square root of a number N.  This is for
 315    statistical reports, not code generation.  */
 316 static double
 317 approx_sqrt (double x)
 318 {
 319   double s, d;
 320
 321   if (x < 0)
 322     abort ();
 323   if (x == 0)
 324     return 0;
 325
 326   s = x;
 327   do
 328     {
 329       d = (s * s - x) / (2 * s);
 330       s -= d;
 331     }
 332   while (d > .0001);
 333   return s;
 334 }