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_macros (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_macros (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
 105   do
 106     {
 107       r = HASHSTEP (r, *str);
 108       str++;
 109     }
 110   while (--n);
 111
 112   return _cpp_lookup_with_hash (pfile, name, len, r);
 113 }
 114
 115 cpp_hashnode *
 116 _cpp_lookup_with_hash (pfile, name, len, hash)
 117      cpp_reader *pfile;
 118      const U_CHAR *name;
 119      size_t len;
 120      unsigned int hash;
 121 {
 122   unsigned int index;
 123   unsigned int hash2;
 124   size_t size;
 125   cpp_hashnode *entry;
 126   cpp_hashnode **entries;
 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 == NULL)
 136     goto insert;
 137   if (entry->hash == hash && entry->length == len
 138       && !memcmp (entry->name, name, len))
 139     return entry;
 140
 141   hash2 = 1 + hash % (size - 2);
 142
 143   for (;;)
 144     {
 145       index += hash2;
 146       if (index >= size)
 147         index -= size;
 148       entry = entries[index];
 149
 150       if (entry == NULL)
 151         goto insert;
 152       if (entry->hash == hash && entry->length == len
 153           && !memcmp (entry->name, name, len))
 154         return entry;
 155     }
 156
 157  insert:
 158   pfile->hashtab->nelts++;
 159
 160   /* Create a new hash node.  */
 161   {
 162     U_CHAR *p = obstack_alloc (pfile->hash_ob, sizeof (cpp_hashnode) + len);
 163     entry = (cpp_hashnode *)p;
 164     p += offsetof (cpp_hashnode, name);
 165
 166     entry->type = T_VOID;
 167     entry->fe_value = 0;
 168     entry->length = len;
 169     entry->hash = hash;
 170     entry->value.expansion = NULL;
 171     memcpy (p, name, len);
 172     p[len] = 0;
 173
 174     entries[index] = entry;
 175   }
 176
 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)
 264      cpp_reader *pfile;
 265      int (*cb) PARAMS ((cpp_reader *, cpp_hashnode *));
 266 {
 267     cpp_hashnode **p, **limit;
 268
 269   p = pfile->hashtab->entries;
 270   limit = p + pfile->hashtab->size;
 271   do
 272     {
 273       if (*p)
 274         if ((*cb) (pfile, *p) == 0)
 275           break;
 276     }
 277   while (++p < limit);
 278 }