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