libcpp/symtab.c

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