gcc/hashtable.c

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