gcc/cpphash.c

   1 /* Part of CPP library.  (Identifier and string tables.)
   2    Copyright (C) 1986, 1987, 1989, 1992, 1993, 1994, 1995, 1996, 1998,
   3    1999, 2000 Free Software Foundation, Inc.
   4    Written by Per Bothner, 1994.
   5    Based on CCCP program by Paul Rubin, June 1986
   6    Adapted to ANSI C, Richard Stallman, Jan 1987
   7
   8 This program is free software; you can redistribute it and/or modify it
   9 under the terms of the GNU General Public License as published by the
  10 Free Software Foundation; either version 2, or (at your option) any
  11 later version.
  12
  13 This program is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with this program; if not, write to the Free Software
  20 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  21
  22  In other words, you are welcome to use, share and improve this program.
  23  You are forbidden to forbid anyone else to use, share and improve
  24  what you give them.   Help stamp out software-hoarding!  */
  25
  26 #include "config.h"
  27 #include "system.h"
  28 #include "cpplib.h"
  29 #include "cpphash.h"
  30 #include "obstack.h"
  31
  32 #define obstack_chunk_alloc xmalloc
  33 #define obstack_chunk_free free
  34
  35 /* Initial hash table size.  (It can grow if necessary.)  This is the
  36    largest prime number smaller than 2**12. */
  37 #define HASHSIZE 4093
  38
  39 /* This is the structure used for the hash table.  */
  40 struct htab
  41 {
  42   struct cpp_hashnode **entries;
  43   size_t size;
  44   size_t nelts;
  45 };
  46
  47 static void expand_hash PARAMS ((struct htab *));
  48 static unsigned long higher_prime_number PARAMS ((unsigned long));
  49
  50 /* Set up and tear down internal structures for macro expansion.  */
  51 void
  52 _cpp_init_hashtable (pfile)
  53      cpp_reader *pfile;
  54 {
  55   pfile->hash_ob = xnew (struct obstack);
  56   obstack_init (pfile->hash_ob);
  57
  58   pfile->hashtab = xobnew (pfile->hash_ob, struct htab);
  59
  60   pfile->hashtab->nelts = 0;
  61   pfile->hashtab->size = HASHSIZE;
  62   pfile->hashtab->entries = xcnewvec (cpp_hashnode *, HASHSIZE);
  63 }
  64
  65 void
  66 _cpp_cleanup_hashtable (pfile)
  67      cpp_reader *pfile;
  68 {
  69   cpp_hashnode **p, **limit;
  70
  71   p = pfile->hashtab->entries;
  72   limit = p + pfile->hashtab->size;
  73   do
  74     {
  75       if (*p)
  76         {
  77           _cpp_free_definition (*p);
  78           (*p)->fe_value = 0;  /* expose the node to GC */
  79         }
  80     }
  81   while (++p < limit);
  82
  83   free (pfile->hashtab->entries);
  84   obstack_free (pfile->hash_ob, 0);
  85   free (pfile->hash_ob);
  86 }
  87
  88 /* The code below is a specialization of Vladimir Makarov's expandable
  89    hash tables (see libiberty/hashtab.c).  The abstraction penalty was
  90    too high to continue using the generic form.  This code knows
  91    intrinsically how to calculate a hash value, and how to compare an
  92    existing entry with a potential new one.  Also, the ability to
  93    delete members from the table has been removed.  */
  94
  95 cpp_hashnode *
  96 cpp_lookup (pfile, name, len)
  97      cpp_reader *pfile;
  98      const U_CHAR *name;
  99      size_t len;
 100 {
 101   size_t n = len;
 102   unsigned int r = 0;
 103   const U_CHAR *str = name;
 104   U_CHAR *dest = _cpp_pool_reserve (&pfile->ident_pool, len + 1);
 105
 106   do
 107     {
 108       r = HASHSTEP (r, *str);
 109       *dest++ = *str++;
 110     }
 111   while (--n);
 112   *dest = '\0';
 113
 114   return _cpp_lookup_with_hash (pfile, len, r);
 115 }
 116
 117 /* NAME is a null-terminated identifier of length len.  It is assumed
 118    to have been placed at the front of the identifier pool.  */
 119 cpp_hashnode *
 120 _cpp_lookup_with_hash (pfile, len, hash)
 121      cpp_reader *pfile;
 122      size_t len;
 123      unsigned int hash;
 124 {
 125   unsigned int index;
 126   size_t size;
 127   cpp_hashnode *entry;
 128   cpp_hashnode **entries;
 129   unsigned char *name = POOL_FRONT (&pfile->ident_pool);
 130
 131   entries = pfile->hashtab->entries;
 132   size = pfile->hashtab->size;
 133
 134   hash += len;
 135   index = hash % size;
 136
 137   entry = entries[index];
 138   if (entry)
 139     {
 140       unsigned int hash2;
 141
 142       if (entry->hash == hash && entry->length == len
 143           && !memcmp (entry->name, name, len))
 144         return entry;
 145
 146       hash2 = 1 + hash % (size - 2);
 147
 148       for (;;)
 149         {
 150           index += hash2;
 151           if (index >= size)
 152             index -= size;
 153           entry = entries[index];
 154
 155           if (entry == NULL)
 156             break;
 157           if (entry->hash == hash && entry->length == len
 158               && !memcmp (entry->name, name, len))
 159             return entry;
 160         }
 161     }
 162
 163   /* Commit the memory for the identifier.  */
 164   POOL_COMMIT (&pfile->ident_pool, len + 1);
 165
 166   /* Create a new hash node and insert it in the table.  */
 167   entries[index] = obstack_alloc (pfile->hash_ob, sizeof (cpp_hashnode));
 168
 169   entry = entries[index];
 170   entry->type = NT_VOID;
 171   entry->flags = 0;
 172   entry->fe_value = 0;
 173   entry->directive_index = 0;
 174   entry->arg_index = 0;
 175   entry->length = len;
 176   entry->hash = hash;
 177   entry->name = name;
 178   entry->value.macro = 0;
 179
 180   pfile->hashtab->nelts++;
 181   if (size * 3 <= pfile->hashtab->nelts * 4)
 182     expand_hash (pfile->hashtab);
 183
 184   return entry;
 185 }
 186
 187 static void
 188 expand_hash (htab)
 189      struct htab *htab;
 190 {
 191   cpp_hashnode **oentries;
 192   cpp_hashnode **olimit;
 193   cpp_hashnode **p;
 194   size_t size;
 195
 196   oentries = htab->entries;
 197   olimit = oentries + htab->size;
 198
 199   htab->size = size = higher_prime_number (htab->size * 2);
 200   htab->entries = xcnewvec (cpp_hashnode *, size);
 201
 202   for (p = oentries; p < olimit; p++)
 203     {
 204       if (*p != NULL)
 205         {
 206           unsigned int index;
 207           unsigned int hash, hash2;
 208           cpp_hashnode *entry = *p;
 209
 210           hash = entry->hash;
 211           index = hash % size;
 212
 213           if (htab->entries[index] == NULL)
 214             {
 215             insert:
 216               htab->entries[index] = entry;
 217               continue;
 218             }
 219
 220           hash2 = 1 + hash % (size - 2);
 221           for (;;)
 222             {
 223               index += hash2;
 224               if (index >= size)
 225                 index -= size;
 226
 227               if (htab->entries[index] == NULL)
 228                 goto insert;
 229             }
 230         }
 231     }
 232
 233   free (oentries);
 234 }
 235
 236 /* The following function returns the nearest prime number which is
 237    greater than a given source number, N. */
 238
 239 static unsigned long
 240 higher_prime_number (n)
 241      unsigned long n;
 242 {
 243   unsigned long i;
 244
 245   /* Ensure we have a larger number and then force to odd.  */
 246   n++;
 247   n |= 0x01;
 248
 249   /* All odd numbers < 9 are prime.  */
 250   if (n < 9)
 251     return n;
 252
 253   /* Otherwise find the next prime using a sieve.  */
 254
 255  next:
 256   for (i = 3; i * i <= n; i += 2)
 257     if (n % i == 0)
 258       {
 259          n += 2;
 260          goto next;
 261        }
 262
 263   return n;
 264 }
 265
 266 void
 267 cpp_forall_identifiers (pfile, cb, v)
 268      cpp_reader *pfile;
 269      int (*cb) PARAMS ((cpp_reader *, cpp_hashnode *, void *));
 270      void *v;
 271 {
 272     cpp_hashnode **p, **limit;
 273
 274   p = pfile->hashtab->entries;
 275   limit = p + pfile->hashtab->size;
 276   do
 277     {
 278       if (*p)
 279         if ((*cb) (pfile, *p, v) == 0)
 280           break;
 281     }
 282   while (++p < limit);
 283 }
 284
 285 /* Determine whether the identifier ID, of length LEN, is a defined macro.  */
 286 int
 287 cpp_defined (pfile, id, len)
 288      cpp_reader *pfile;
 289      const U_CHAR *id;
 290      int len;
 291 {
 292   cpp_hashnode *hp = cpp_lookup (pfile, id, len);
 293
 294   /* If it's of type NT_MACRO, it cannot be poisoned.  */
 295   return hp->type == NT_MACRO;
 296 }