gcc/hashtable.c

   1 /* Hash tables.
   2    Copyright (C) 2000, 2001, 2003 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 (const unsigned char *, unsigned int);
  34 static void ht_expand (hash_table *);
  35
  36 /* Calculate the hash of the string STR of length LEN.  */
  37
  38 static unsigned int
  39 calc_hash (const unsigned char *str, unsigned int len)
  40 {
  41   unsigned int n = len;
  42   unsigned int r = 0;
  43 #define HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
  44
  45   while (n--)
  46     r = HASHSTEP (r, *str++);
  47
  48   return r + len;
  49 #undef HASHSTEP
  50 }
  51
  52 /* Initialize an identifier hashtable.  */
  53
  54 hash_table *
  55 ht_create (unsigned int order)
  56 {
  57   unsigned int nslots = 1 << order;
  58   hash_table *table;
  59
  60   table = (hash_table *) xmalloc (sizeof (hash_table));
  61   memset (table, 0, sizeof (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 = (hashnode *) xcalloc (nslots, sizeof (hashnode));
  71   table->nslots = nslots;
  72   return table;
  73 }
  74
  75 /* Frees all memory associated with a hash table.  */
  76
  77 void
  78 ht_destroy (hash_table *table)
  79 {
  80   obstack_free (&table->stack, NULL);
  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, unsigned int len,
  95            enum ht_lookup_option insert)
  96 {
  97   unsigned int hash = calc_hash (str, len);
  98   unsigned int hash2;
  99   unsigned int index;
 100   size_t sizemask;
 101   hashnode node;
 102
 103   sizemask = table->nslots - 1;
 104   index = hash & sizemask;
 105
 106   /* hash2 must be odd, so we're guaranteed to visit every possible
 107      location in the table during rehashing.  */
 108   hash2 = ((hash * 17) & sizemask) | 1;
 109   table->searches++;
 110
 111   for (;;)
 112     {
 113       node = table->entries[index];
 114
 115       if (node == NULL)
 116         break;
 117
 118       if (node->hash_value == hash && HT_LEN (node) == len
 119           && !memcmp (HT_STR (node), str, len))
 120         {
 121           if (insert == HT_ALLOCED)
 122             /* The string we search for was placed at the end of the
 123                obstack.  Release it.  */
 124             obstack_free (&table->stack, (void *) str);
 125           return node;
 126         }
 127
 128       index = (index + hash2) & sizemask;
 129       table->collisions++;
 130     }
 131
 132   if (insert == HT_NO_INSERT)
 133     return NULL;
 134
 135   node = (*table->alloc_node) (table);
 136   table->entries[index] = node;
 137
 138   HT_LEN (node) = len;
 139   node->hash_value = hash;
 140   if (insert == HT_ALLOC)
 141     HT_STR (node) = obstack_copy0 (&table->stack, str, len);
 142   else
 143     HT_STR (node) = str;
 144
 145   if (++table->nelements * 4 >= table->nslots * 3)
 146     /* Must expand the string table.  */
 147     ht_expand (table);
 148
 149   return node;
 150 }
 151
 152 /* Double the size of a hash table, re-hashing existing entries.  */
 153
 154 static void
 155 ht_expand (hash_table *table)
 156 {
 157   hashnode *nentries, *p, *limit;
 158   unsigned int size, sizemask;
 159
 160   size = table->nslots * 2;
 161   nentries = (hashnode *) xcalloc (size, sizeof (hashnode));
 162   sizemask = size - 1;
 163
 164   p = table->entries;
 165   limit = p + table->nslots;
 166   do
 167     if (*p)
 168       {
 169         unsigned int index, hash, hash2;
 170
 171         hash = (*p)->hash_value;
 172         hash2 = ((hash * 17) & sizemask) | 1;
 173         index = hash & sizemask;
 174
 175         for (;;)
 176           {
 177             if (! nentries[index])
 178               {
 179                 nentries[index] = *p;
 180                 break;
 181               }
 182
 183             index = (index + hash2) & sizemask;
 184           }
 185       }
 186   while (++p < limit);
 187
 188   free (table->entries);
 189   table->entries = nentries;
 190   table->nslots = size;
 191 }
 192
 193 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
 194    the node, and V.  */
 195 void
 196 ht_forall (hash_table *table, ht_cb cb, const void *v)
 197 {
 198   hashnode *p, *limit;
 199
 200   p = table->entries;
 201   limit = p + table->nslots;
 202   do
 203     if (*p)
 204       {
 205         if ((*cb) (table->pfile, *p, v) == 0)
 206           break;
 207       }
 208   while (++p < limit);
 209 }
 210
 211 /* Dump allocation statistics to stderr.  */
 212
 213 void
 214 ht_dump_statistics (hash_table *table)
 215 {
 216   size_t nelts, nids, overhead, headers;
 217   size_t total_bytes, longest, sum_of_squares;
 218   double exp_len, exp_len2, exp2_len;
 219   hashnode *p, *limit;
 220
 221 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
 222                   ? (x) \
 223                   : ((x) < 1024*1024*10 \
 224                      ? (x) / 1024 \
 225                      : (x) / (1024*1024))))
 226 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
 227
 228   total_bytes = longest = sum_of_squares = nids = 0;
 229   p = table->entries;
 230   limit = p + table->nslots;
 231   do
 232     if (*p)
 233       {
 234         size_t n = HT_LEN (*p);
 235
 236         total_bytes += n;
 237         sum_of_squares += n * n;
 238         if (n > longest)
 239           longest = n;
 240         nids++;
 241       }
 242   while (++p < limit);
 243
 244   nelts = table->nelements;
 245   overhead = obstack_memory_used (&table->stack) - total_bytes;
 246   headers = table->nslots * sizeof (hashnode);
 247
 248   fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
 249            (unsigned long) nelts);
 250   fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
 251            (unsigned long) nids, nids * 100.0 / nelts);
 252   fprintf (stderr, "slots\t\t%lu\n",
 253            (unsigned long) table->nslots);
 254   fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
 255            SCALE (total_bytes), LABEL (total_bytes),
 256            SCALE (overhead), LABEL (overhead));
 257   fprintf (stderr, "table size\t%lu%c\n",
 258            SCALE (headers), LABEL (headers));
 259
 260   exp_len = (double)total_bytes / (double)nelts;
 261   exp2_len = exp_len * exp_len;
 262   exp_len2 = (double) sum_of_squares / (double) nelts;
 263
 264   fprintf (stderr, "coll/search\t%.4f\n",
 265            (double) table->collisions / (double) table->searches);
 266   fprintf (stderr, "ins/search\t%.4f\n",
 267            (double) nelts / (double) table->searches);
 268   fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
 269            exp_len, approx_sqrt (exp_len2 - exp2_len));
 270   fprintf (stderr, "longest entry\t%lu\n",
 271            (unsigned long) longest);
 272 #undef SCALE
 273 #undef LABEL
 274 }
 275
 276 /* Return the approximate positive square root of a number N.  This is for
 277    statistical reports, not code generation.  */
 278 double
 279 approx_sqrt (double x)
 280 {
 281   double s, d;
 282
 283   if (x < 0)
 284     abort ();
 285   if (x == 0)
 286     return 0;
 287
 288   s = x;
 289   do
 290     {
 291       d = (s * s - x) / (2 * s);
 292       s -= d;
 293     }
 294   while (d > .0001);
 295   return s;
 296 }