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