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
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
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.
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.
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! */
32 #define obstack_chunk_alloc xmalloc
33 #define obstack_chunk_free free
35 /* Initial hash table size. (It can grow if necessary.) This is the
36 largest prime number smaller than 2**12. */
39 /* This is the structure used for the hash table. */
42 struct cpp_hashnode **entries;
47 static void expand_hash PARAMS ((struct htab *));
48 static unsigned long higher_prime_number PARAMS ((unsigned long));
50 /* Set up and tear down internal structures for macro expansion. */
52 _cpp_init_macros (pfile)
55 pfile->hash_ob = xnew (struct obstack);
56 obstack_init (pfile->hash_ob);
58 pfile->hashtab = xobnew (pfile->hash_ob, struct htab);
60 pfile->hashtab->nelts = 0;
61 pfile->hashtab->size = HASHSIZE;
62 pfile->hashtab->entries = xcnewvec (cpp_hashnode *, HASHSIZE);
66 _cpp_cleanup_macros (pfile)
69 cpp_hashnode **p, **limit;
71 p = pfile->hashtab->entries;
72 limit = p + pfile->hashtab->size;
77 _cpp_free_definition (*p);
78 (*p)->fe_value = 0; /* expose the node to GC */
83 free (pfile->hashtab->entries);
84 obstack_free (pfile->hash_ob, 0);
85 free (pfile->hash_ob);
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. */
96 cpp_lookup (pfile, name, len)
103 const U_CHAR *str = name;
107 r = HASHSTEP (r, str);
112 return _cpp_lookup_with_hash (pfile, name, len, r);
116 _cpp_lookup_with_hash (pfile, name, len, hash)
126 cpp_hashnode **entries;
128 entries = pfile->hashtab->entries;
129 size = pfile->hashtab->size;
134 entry = entries[index];
137 if (entry->hash == hash && entry->length == len
138 && !memcmp (entry->name, name, len))
141 hash2 = 1 + hash % (size - 2);
148 entry = entries[index];
152 if (entry->hash == hash && entry->length == len
153 && !memcmp (entry->name, name, len))
158 pfile->hashtab->nelts++;
160 /* Create a new hash node. */
162 U_CHAR *p = obstack_alloc (pfile->hash_ob, sizeof (cpp_hashnode) + len);
163 entry = (cpp_hashnode *)p;
164 p += offsetof (cpp_hashnode, name);
166 entry->type = T_VOID;
170 entry->value.expansion = NULL;
171 memcpy (p, name, len);
174 entries[index] = entry;
177 if (size * 3 <= pfile->hashtab->nelts * 4)
178 expand_hash (pfile->hashtab);
187 cpp_hashnode **oentries;
188 cpp_hashnode **olimit;
192 oentries = htab->entries;
193 olimit = oentries + htab->size;
195 htab->size = size = higher_prime_number (htab->size * 2);
196 htab->entries = xcnewvec (cpp_hashnode *, size);
198 for (p = oentries; p < olimit; p++)
203 unsigned int hash, hash2;
204 cpp_hashnode *entry = *p;
209 if (htab->entries[index] == NULL)
212 htab->entries[index] = entry;
216 hash2 = 1 + hash % (size - 2);
223 if (htab->entries[index] == NULL)
232 /* The following function returns the nearest prime number which is
233 greater than a given source number, N. */
236 higher_prime_number (n)
241 /* Ensure we have a larger number and then force to odd. */
245 /* All odd numbers < 9 are prime. */
249 /* Otherwise find the next prime using a sieve. */
252 for (i = 3; i * i <= n; i += 2)
263 cpp_forall_identifiers (pfile, cb)
265 int (*cb) PARAMS ((cpp_reader *, cpp_hashnode *));
267 cpp_hashnode **p, **limit;
269 p = pfile->hashtab->entries;
270 limit = p + pfile->hashtab->size;
274 if ((*cb) (pfile, *p) == 0)