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