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         _cpp_free_definition (*p);
  77     }
  78   while (++p < limit);
  79
  80   free (pfile->hashtab->entries);
  81   obstack_free (pfile->hash_ob, 0);
  82   free (pfile->hash_ob);
  83 }
  84
  85 /* The code below is a specialization of Vladimir Makarov's expandable
  86    hash tables (see libiberty/hashtab.c).  The abstraction penalty was
  87    too high to continue using the generic form.  This code knows
  88    intrinsically how to calculate a hash value, and how to compare an
  89    existing entry with a potential new one.  Also, the ability to
  90    delete members from the table has been removed.  */
  91
  92 cpp_hashnode *
  93 cpp_lookup (pfile, name, len)
  94      cpp_reader *pfile;
  95      const U_CHAR *name;
  96      size_t len;
  97 {
  98   size_t n = len;
  99   unsigned int r = 0;
 100   const U_CHAR *str = name;
 101   U_CHAR *dest = _cpp_pool_reserve (&pfile->ident_pool, len + 1);
 102
 103   do
 104     {
 105       r = HASHSTEP (r, *str);
 106       *dest++ = *str++;
 107     }
 108   while (--n);
 109   *dest = '\0';
 110
 111   return _cpp_lookup_with_hash (pfile, len, r);
 112 }
 113
 114 /* NAME is a null-terminated identifier of length len.  It is assumed
 115    to have been placed at the front of the identifier pool.  */
 116 cpp_hashnode *
 117 _cpp_lookup_with_hash (pfile, len, hash)
 118      cpp_reader *pfile;
 119      size_t len;
 120      unsigned int hash;
 121 {
 122   unsigned int index;
 123   size_t size;
 124   cpp_hashnode *entry;
 125   cpp_hashnode **entries;
 126   unsigned char *name = POOL_FRONT (&pfile->ident_pool);
 127
 128   entries = pfile->hashtab->entries;
 129   size = pfile->hashtab->size;
 130
 131   hash += len;
 132   index = hash % size;
 133
 134   entry = entries[index];
 135   if (entry)
 136     {
 137       unsigned int hash2;
 138
 139       if (entry->hash == hash && entry->length == len
 140           && !memcmp (entry->name, name, len))
 141         return entry;
 142
 143       hash2 = 1 + hash % (size - 2);
 144
 145       for (;;)
 146         {
 147           index += hash2;
 148           if (index >= size)
 149             index -= size;
 150           entry = entries[index];
 151
 152           if (entry == NULL)
 153             break;
 154           if (entry->hash == hash && entry->length == len
 155               && !memcmp (entry->name, name, len))
 156             return entry;
 157         }
 158     }
 159
 160   /* Commit the memory for the identifier.  */
 161   POOL_COMMIT (&pfile->ident_pool, len + 1);
 162
 163   /* Create a new hash node and insert it in the table.  */
 164   entries[index] = obstack_alloc (pfile->hash_ob, sizeof (cpp_hashnode));
 165
 166   entry = entries[index];
 167   entry->type = NT_VOID;
 168   entry->flags = 0;
 169   entry->directive_index = 0;
 170   entry->arg_index = 0;
 171   entry->length = len;
 172   entry->hash = hash;
 173   entry->name = name;
 174   entry->value.macro = 0;
 175
 176   pfile->hashtab->nelts++;
 177   if (size * 3 <= pfile->hashtab->nelts * 4)
 178     expand_hash (pfile->hashtab);
 179
 180   return entry;
 181 }
 182
 183 static void
 184 expand_hash (htab)
 185      struct htab *htab;
 186 {
 187   cpp_hashnode **oentries;
 188   cpp_hashnode **olimit;
 189   cpp_hashnode **p;
 190   size_t size;
 191
 192   oentries = htab->entries;
 193   olimit = oentries + htab->size;
 194
 195   htab->size = size = higher_prime_number (htab->size * 2);
 196   htab->entries = xcnewvec (cpp_hashnode *, size);
 197
 198   for (p = oentries; p < olimit; p++)
 199     {
 200       if (*p != NULL)
 201         {
 202           unsigned int index;
 203           unsigned int hash, hash2;
 204           cpp_hashnode *entry = *p;
 205
 206           hash = entry->hash;
 207           index = hash % size;
 208
 209           if (htab->entries[index] == NULL)
 210             {
 211             insert:
 212               htab->entries[index] = entry;
 213               continue;
 214             }
 215
 216           hash2 = 1 + hash % (size - 2);
 217           for (;;)
 218             {
 219               index += hash2;
 220               if (index >= size)
 221                 index -= size;
 222
 223               if (htab->entries[index] == NULL)
 224                 goto insert;
 225             }
 226         }
 227     }
 228
 229   free (oentries);
 230 }
 231
 232 /* The following function returns the nearest prime number which is
 233    greater than a given source number, N. */
 234
 235 static unsigned long
 236 higher_prime_number (n)
 237      unsigned long n;
 238 {
 239   unsigned long i;
 240
 241   /* Ensure we have a larger number and then force to odd.  */
 242   n++;
 243   n |= 0x01;
 244
 245   /* All odd numbers < 9 are prime.  */
 246   if (n < 9)
 247     return n;
 248
 249   /* Otherwise find the next prime using a sieve.  */
 250
 251  next:
 252   for (i = 3; i * i <= n; i += 2)
 253     if (n % i == 0)
 254       {
 255          n += 2;
 256          goto next;
 257        }
 258
 259   return n;
 260 }
 261
 262 void
 263 cpp_forall_identifiers (pfile, cb, v)
 264      cpp_reader *pfile;
 265      int (*cb) PARAMS ((cpp_reader *, cpp_hashnode *, void *));
 266      void *v;
 267 {
 268     cpp_hashnode **p, **limit;
 269
 270   p = pfile->hashtab->entries;
 271   limit = p + pfile->hashtab->size;
 272   do
 273     {
 274       if (*p)
 275         if ((*cb) (pfile, *p, v) == 0)
 276           break;
 277     }
 278   while (++p < limit);
 279 }
 280
 281 /* Determine whether the identifier ID, of length LEN, is a defined macro.  */
 282 int
 283 cpp_defined (pfile, id, len)
 284      cpp_reader *pfile;
 285      const U_CHAR *id;
 286      int len;
 287 {
 288   cpp_hashnode *hp = cpp_lookup (pfile, id, len);
 289
 290   /* If it's of type NT_MACRO, it cannot be poisoned.  */
 291   return hp->type == NT_MACRO;
 292 }