libcpp/symtab.c

   1 /* Hash tables.
   2    Copyright (C) 2000, 2001, 2003, 2004, 2008, 2009
   3    Free Software Foundation, Inc.
   4
   5 This program is free software; you can redistribute it and/or modify it
   6 under the terms of the GNU General Public License as published by the
   7 Free Software Foundation; either version 3, or (at your option) any
   8 later version.
   9
  10 This program is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with this program; see the file COPYING3.  If not see
  17 <http://www.gnu.org/licenses/>.
  18
  19  In other words, you are welcome to use, share and improve this program.
  20  You are forbidden to forbid anyone else to use, share and improve
  21  what you give them.   Help stamp out software-hoarding!  */
  22
  23 #include "config.h"
  24 #include "system.h"
  25 #include "symtab.h"
  26
  27 /* The code below is a specialization of Vladimir Makarov's expandable
  28    hash tables (see libiberty/hashtab.c).  The abstraction penalty was
  29    too high to continue using the generic form.  This code knows
  30    intrinsically how to calculate a hash value, and how to compare an
  31    existing entry with a potential new one.  */
  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 /* A deleted entry.  */
  38 #define DELETED ((hashnode) -1)
  39
  40 /* Calculate the hash of the string STR of length LEN.  */
  41
  42 static unsigned int
  43 calc_hash (const unsigned char *str, size_t len)
  44 {
  45   size_t n = len;
  46   unsigned int r = 0;
  47
  48   while (n--)
  49     r = HT_HASHSTEP (r, *str++);
  50
  51   return HT_HASHFINISH (r, len);
  52 }
  53
  54 /* Initialize an identifier hashtable.  */
  55
  56 hash_table *
  57 ht_create (unsigned int order)
  58 {
  59   unsigned int nslots = 1 << order;
  60   hash_table *table;
  61
  62   table = XCNEW (hash_table);
  63
  64   /* Strings need no alignment.  */
  65   _obstack_begin (&table->stack, 0, 0,
  66                   (void *(*) (long)) xmalloc,
  67                   (void (*) (void *)) free);
  68
  69   obstack_alignment_mask (&table->stack) = 0;
  70
  71   table->entries = XCNEWVEC (hashnode, nslots);
  72   table->entries_owned = true;
  73   table->nslots = nslots;
  74   return table;
  75 }
  76
  77 /* Frees all memory associated with a hash table.  */
  78
  79 void
  80 ht_destroy (hash_table *table)
  81 {
  82   obstack_free (&table->stack, NULL);
  83   if (table->entries_owned)
  84     free (table->entries);
  85   free (table);
  86 }
  87
  88 /* Returns the hash entry for the a STR of length LEN.  If that string
  89    already exists in the table, returns the existing entry.  If the
  90    identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
  91    returns NULL.  Otherwise insert and returns a new entry.  A new
  92    string is allocated.  */
  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   unsigned int deleted_index = table->nslots;
 109   size_t sizemask;
 110   hashnode node;
 111
 112   sizemask = table->nslots - 1;
 113   index = hash & sizemask;
 114   table->searches++;
 115
 116   node = table->entries[index];
 117
 118   if (node != NULL)
 119     {
 120       if (node == DELETED)
 121         deleted_index = index;
 122       else if (node->hash_value == hash
 123                && HT_LEN (node) == (unsigned int) len
 124                && !memcmp (HT_STR (node), str, len))
 125         return node;
 126
 127       /* hash2 must be odd, so we're guaranteed to visit every possible
 128          location in the table during rehashing.  */
 129       hash2 = ((hash * 17) & sizemask) | 1;
 130
 131       for (;;)
 132         {
 133           table->collisions++;
 134           index = (index + hash2) & sizemask;
 135           node = table->entries[index];
 136           if (node == NULL)
 137             break;
 138
 139           if (node == DELETED)
 140             {
 141               if (deleted_index != table->nslots)
 142                 deleted_index = index;
 143             }
 144           else if (node->hash_value == hash
 145                    && HT_LEN (node) == (unsigned int) len
 146                    && !memcmp (HT_STR (node), str, len))
 147             return node;
 148         }
 149     }
 150
 151   if (insert == HT_NO_INSERT)
 152     return NULL;
 153
 154   /* We prefer to overwrite the first deleted slot we saw.  */
 155   if (deleted_index != table->nslots)
 156     index = deleted_index;
 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
 164   if (table->alloc_subobject)
 165     {
 166       char *chars = table->alloc_subobject (len + 1);
 167       memcpy (chars, str, len);
 168       chars[len] = '\0';
 169       HT_STR (node) = (const unsigned char *) chars;
 170     }
 171   else
 172     HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack,
 173                                                            str, len);
 174
 175   if (++table->nelements * 4 >= table->nslots * 3)
 176     /* Must expand the string table.  */
 177     ht_expand (table);
 178
 179   return node;
 180 }
 181
 182 /* Double the size of a hash table, re-hashing existing entries.  */
 183
 184 static void
 185 ht_expand (hash_table *table)
 186 {
 187   hashnode *nentries, *p, *limit;
 188   unsigned int size, sizemask;
 189
 190   size = table->nslots * 2;
 191   nentries = XCNEWVEC (hashnode, size);
 192   sizemask = size - 1;
 193
 194   p = table->entries;
 195   limit = p + table->nslots;
 196   do
 197     if (*p && *p != DELETED)
 198       {
 199         unsigned int index, hash, hash2;
 200
 201         hash = (*p)->hash_value;
 202         index = hash & sizemask;
 203
 204         if (nentries[index])
 205           {
 206             hash2 = ((hash * 17) & sizemask) | 1;
 207             do
 208               {
 209                 index = (index + hash2) & sizemask;
 210               }
 211             while (nentries[index]);
 212           }
 213         nentries[index] = *p;
 214       }
 215   while (++p < limit);
 216
 217   if (table->entries_owned)
 218     free (table->entries);
 219   table->entries_owned = true;
 220   table->entries = nentries;
 221   table->nslots = size;
 222 }
 223
 224 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
 225    the node, and V.  */
 226 void
 227 ht_forall (hash_table *table, ht_cb cb, const void *v)
 228 {
 229   hashnode *p, *limit;
 230
 231   p = table->entries;
 232   limit = p + table->nslots;
 233   do
 234     if (*p && *p != DELETED)
 235       {
 236         if ((*cb) (table->pfile, *p, v) == 0)
 237           break;
 238       }
 239   while (++p < limit);
 240 }
 241
 242 /* Like ht_forall, but a nonzero return from the callback means that
 243    the entry should be removed from the table.  */
 244 void
 245 ht_purge (hash_table *table, ht_cb cb, const void *v)
 246 {
 247   hashnode *p, *limit;
 248
 249   p = table->entries;
 250   limit = p + table->nslots;
 251   do
 252     if (*p && *p != DELETED)
 253       {
 254         if ((*cb) (table->pfile, *p, v))
 255           *p = DELETED;
 256       }
 257   while (++p < limit);
 258 }
 259
 260 /* Restore the hash table.  */
 261 void
 262 ht_load (hash_table *ht, hashnode *entries,
 263          unsigned int nslots, unsigned int nelements,
 264          bool own)
 265 {
 266   if (ht->entries_owned)
 267     free (ht->entries);
 268   ht->entries = entries;
 269   ht->nslots = nslots;
 270   ht->nelements = nelements;
 271   ht->entries_owned = own;
 272 }
 273
 274 /* Dump allocation statistics to stderr.  */
 275
 276 void
 277 ht_dump_statistics (hash_table *table)
 278 {
 279   size_t nelts, nids, overhead, headers;
 280   size_t total_bytes, longest, deleted = 0;
 281   double sum_of_squares, exp_len, exp_len2, exp2_len;
 282   hashnode *p, *limit;
 283
 284 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 285                   ? (x) \
 286                   : ((x) < 1024*1024*10 \
 287                      ? (x) / 1024 \
 288                      : (x) / (1024*1024))))
 289 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 290
 291   total_bytes = longest = sum_of_squares = nids = 0;
 292   p = table->entries;
 293   limit = p + table->nslots;
 294   do
 295     if (*p == DELETED)
 296       ++deleted;
 297     else if (*p)
 298       {
 299         size_t n = HT_LEN (*p);
 300
 301         total_bytes += n;
 302         sum_of_squares += (double) n * n;
 303         if (n > longest)
 304           longest = n;
 305         nids++;
 306       }
 307   while (++p < limit);
 308
 309   nelts = table->nelements;
 310   overhead = obstack_memory_used (&table->stack) - total_bytes;
 311   headers = table->nslots * sizeof (hashnode);
 312
 313   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
 314            (unsigned long) nelts);
 315   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
 316            (unsigned long) nids, nids * 100.0 / nelts);
 317   fprintf (stderr, "slots\t\t%lu\n",
 318            (unsigned long) table->nslots);
 319   fprintf (stderr, "deleted\t\t%lu\n",
 320            (unsigned long) deleted);
 321   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
 322            SCALE (total_bytes), LABEL (total_bytes),
 323            SCALE (overhead), LABEL (overhead));
 324   fprintf (stderr, "table size\t%lu%c\n",
 325            SCALE (headers), LABEL (headers));
 326
 327   exp_len = (double)total_bytes / (double)nelts;
 328   exp2_len = exp_len * exp_len;
 329   exp_len2 = (double) sum_of_squares / (double) nelts;
 330
 331   fprintf (stderr, "coll/search\t%.4f\n",
 332            (double) table->collisions / (double) table->searches);
 333   fprintf (stderr, "ins/search\t%.4f\n",
 334            (double) nelts / (double) table->searches);
 335   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
 336            exp_len, approx_sqrt (exp_len2 - exp2_len));
 337   fprintf (stderr, "longest entry\t%lu\n",
 338            (unsigned long) longest);
 339 #undef SCALE
 340 #undef LABEL
 341 }
 342
 343 /* Return the approximate positive square root of a number N.  This is for
 344    statistical reports, not code generation.  */
 345 static double
 346 approx_sqrt (double x)
 347 {
 348   double s, d;
 349
 350   if (x < 0)
 351     abort ();
 352   if (x == 0)
 353     return 0;
 354
 355   s = x;
 356   do
 357     {
 358       d = (s * s - x) / (2 * s);
 359       s -= d;
 360     }
 361   while (d > .0001);
 362   return s;
 363 }