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