2 ** Splint - annotation-assisted static program checker
3 ** Copyright (C) 1994-2003 University of Virginia,
4 ** Massachusetts Institute of Technology
6 ** This program is free software; you can redistribute it and/or modify it
7 ** under the terms of the GNU General Public License as published by the
8 ** Free Software Foundation; either version 2 of the License, or (at your
9 ** option) any later version.
11 ** This program is distributed in the hope that it will be useful, but
12 ** WITHOUT ANY WARRANTY; without even the implied warranty of
13 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 ** General Public License for more details.
16 ** The GNU General Public License is available from http://www.gnu.org/ or
17 ** the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
18 ** MA 02111-1307, USA.
20 ** For information on splint: info@splint.org
21 ** To report a bug: splint-bug@splint.org
22 ** For more information: http://www.splint.org
27 ** Pre-processor hash table. Derived from gnu cpp.
30 /* Part of CPP library. (Macro hash table support.)
31 Copyright (C) 1986, 87, 89, 92-95, 1996 Free Software Foundation, Inc.
32 Written by Per Bothner, 1994.
33 Based on CCCP program by by Paul Rubin, June 1986
34 Adapted to ANSI C, Richard Stallman, Jan 1987
36 This program is free software; you can redistribute it and/or modify it
37 under the terms of the GNU General Public License as published by the
38 Free Software Foundation; either version 2, or (at your option) any
41 This program is distributed in the hope that it will be useful,
42 but WITHOUT ANY WARRANTY; without even the implied warranty of
43 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
44 GNU General Public License for more details.
46 You should have received a copy of the GNU General Public License
47 along with this program; if not, write to the Free Software
48 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
50 In other words, you are welcome to use, share and improve this program.
51 You are forbidden to forbid anyone else to use, share and improve
52 what you give them. Help stamp out software-hoarding! */
54 # include "splintMacros.nf"
60 typedef /*@null@*/ /*@only@*/ hashNode o_hashNode;
61 typedef /*@null@*/ /*@only@*/ hashNode n_hashNode;
63 static o_hashNode hashtab[CPP_HASHSIZE];
64 static o_hashNode ohashtab[CPP_HASHSIZE];
66 static void hashNode_delete (/*@null@*/ /*@only@*/ hashNode);
68 /* p_prev need not be defined, but isn't defined by hashNode_copy */
70 /*@function static unsigned int hashStep (unsigned, char) modifies nothing ; @*/
71 # define hashStep(old, c) (((old) << 2) + (unsigned int) (c))
73 /*@function static unsigned int makePositive (unsigned int) modifies nothing ; @*/
74 # define makePositive(v) ((v) & 0x7fffffff) /* make number positive */
76 static /*@null@*/ hashNode hashNode_copy (/*@null@*/ hashNode,
77 /*@null@*/ /*@dependent@*/ n_hashNode *p_hdr,
78 /*@dependent@*/ /*@null@*/ /*@special@*/ hashNode p_prev)
81 void cppReader_saveHashtab ()
85 for (i = 0; i < CPP_HASHSIZE; i++)
87 ohashtab[i] = hashNode_copy (hashtab[i], &ohashtab[i], NULL);
91 void cppReader_restoreHashtab ()
95 for (i = 0; i < CPP_HASHSIZE; i++) {
96 /* hashNode_delete (hashtab[i]); */
97 hashtab[i] = hashNode_copy (ohashtab[i], &hashtab[i], NULL);
101 static void hashNode_delete (/*@only@*/ /*@null@*/ hashNode node)
109 hashNode_delete (node->next);
111 if (node->type == T_MACRO)
113 DEFINITION *d = node->value.defn;
114 struct reflist *ap, *nextap;
116 for (ap = d->pattern; ap != NULL; ap = nextap)
124 sfree (d->args.argnames);
130 cstring_free (node->name);
135 /*@null@*/ hashNode hashNode_copy (hashNode node, hashNode *hdr,
136 /*@dependent@*/ hashNode prev)
144 hashNode res = dmalloc (sizeof (*res));
146 res->next = hashNode_copy (node->next, hdr, res);
149 res->bucket_hdr = hdr;
150 res->type = node->type;
151 res->length = node->length;
152 res->name = cstring_copy (node->name);
154 if (node->type == T_MACRO)
156 DEFINITION *d = node->value.defn;
157 DEFINITION *nd = dmalloc (sizeof (*nd));
159 res->value.defn = nd;
160 nd->nargs = d->nargs;
162 nd->length = d->length;
163 nd->predefined = d->predefined;
164 nd->expansion = d->expansion;
168 if (d->pattern != NULL)
170 struct reflist *ap, *nextap;
171 struct reflist **last = &nd->pattern;
173 for (ap = d->pattern; ap != NULL; ap = nextap)
175 struct reflist *npattern = dmalloc (sizeof (* (nd->pattern)));
179 if (ap == d->pattern)
183 } /*@=branchstate@*/ /* npattern is propagated through loop */
185 last = & (npattern->next);
186 npattern->next = NULL; /* will get filled in */
187 npattern->stringify = d->pattern->stringify;
188 npattern->raw_before = d->pattern->raw_before;
189 npattern->raw_after = d->pattern->raw_after;
190 npattern->rest_args = d->pattern->rest_args;
191 npattern->argno = d->pattern->argno;
203 llassert (d->args.argnames != NULL);
205 nd->args.argnames = mstring_copy (d->args.argnames);
210 ** This fix found by:
212 ** Date: Mon, 31 May 1999 15:10:50 +0900 (JST)
213 ** From: "N.Komazaki" <koma@focs.sei.co.jp>
216 /*! why doesn't splint report an error for this? */
217 nd->args.argnames = mstring_createEmpty ();
222 if (node->type == T_CONST)
224 res->value.ival = node->value.ival;
226 else if (node->type == T_PCSTRING)
228 res->value.cpval = mstring_copy (node->value.cpval);
229 llassert (res->value.cpval != NULL);
233 res->value = node->value;
237 /*@-uniondef@*/ /*@-compdef@*/ /* res->prev is not defined */
239 /*@=uniondef@*/ /*@=compdef@*/
243 /* Return hash function on name. must be compatible with the one
244 computed a step at a time, elsewhere */
247 cpphash_hashCode (const char *name, size_t len, int hashsize)
253 r = hashStep (r, *name++);
256 return (int) (makePositive (r) % hashsize);
260 ** Find the most recent hash node for name name (ending with first
261 ** non-identifier char) cpphash_installed by install
263 ** If len is >= 0, it is the length of the name.
264 ** Otherwise, compute the length by scanning the entire name.
266 ** If hash is >= 0, it is the precomputed hash code.
267 ** Otherwise, compute the hash code.
270 /*@null@*/ hashNode cpphash_lookup (char *name, int len, int hash)
277 for (bp = name; isIdentifierChar (*bp); bp++)
287 hash = cpphash_hashCode (name, size_fromInt (len), CPP_HASHSIZE);
290 bucket = hashtab[hash];
292 while (bucket != NULL)
294 if (bucket->length == size_fromInt (len) &&
295 cstring_equalLen (bucket->name, cstring_fromChars (name), size_fromInt (len)))
300 bucket = bucket->next;
306 /*@null@*/ hashNode cpphash_lookupExpand (char *name, int len, int hash, bool forceExpand)
308 hashNode node = cpphash_lookup (name, len, hash);
310 DPRINTF (("Lookup expand: %s", name));
314 if (node->type == T_MACRO)
316 DEFINITION *defn = (DEFINITION *) node->value.defn;
318 DPRINTF (("Check macro..."));
320 if (defn->noExpand && !forceExpand) {
321 DPRINTF (("No expand!"));
331 * Delete a hash node. Some weirdness to free junk from macros.
332 * More such weirdness will have to be added if you define more hash
333 * types that need it.
336 /* Note that the DEFINITION of a macro is removed from the hash table
337 but its storage is not freed. This would be a storage leak
338 except that it is not reasonable to keep undefining and redefining
339 large numbers of macros many times.
340 In any case, this is necessary, because a macro can be #undef'd
341 in the middle of reading the arguments to a call to it.
342 If #undef freed the DEFINITION, that would crash. */
345 cppReader_deleteMacro (hashNode hp)
347 if (hp->prev != NULL)
350 hp->prev->next = hp->next;
355 if (hp->next != NULL)
357 hp->next->prev = hp->prev;
360 /* make sure that the bucket chain header that
361 the deleted guy was on points to the right thing afterwards. */
363 llassert (hp != NULL);
364 llassert (hp->bucket_hdr != NULL);
366 if (hp == *hp->bucket_hdr) {
367 *hp->bucket_hdr = hp->next;
370 if (hp->type == T_MACRO)
372 DEFINITION *d = hp->value.defn;
373 struct reflist *ap, *nextap;
375 for (ap = d->pattern; ap != NULL; ap = nextap)
383 sfree (d->args.argnames);
387 /*@-dependenttrans@*/ /*@-exposetrans@*/ /*@-compdestroy@*/
389 /*@=dependenttrans@*/ /*@=exposetrans@*/ /*@=compdestroy@*/
392 /* Install a name in the main hash table, even if it is already there.
393 name stops with first non alphanumeric, except leading '#'.
394 caller must check against redefinition if that is desired.
395 cppReader_deleteMacro () removes things installed by install () in fifo order.
396 this is important because of the `defined' special symbol used
397 in #if, and also if pushdef/popdef directives are ever implemented.
399 If LEN is >= 0, it is the length of the name.
400 Otherwise, compute the length by scanning the entire name.
402 If HASH is >= 0, it is the precomputed hash code.
403 Otherwise, compute the hash code. */
405 hashNode cpphash_install (char *name, int len, enum node_type type,
406 int ivalue, char *value, int hash)
412 DPRINTF (("Install: %s / %d", name, len));
417 while (isIdentifierChar (*p))
427 hash = cpphash_hashCode (name, size_fromInt (len), CPP_HASHSIZE);
430 hp = (hashNode) dmalloc (sizeof (*hp));
432 hp->bucket_hdr = &hashtab[bucket];
434 hp->next = hashtab[bucket];
437 if (hp->next != NULL)
442 hashtab[bucket] = hp;
445 hp->length = size_fromInt (len);
447 if (hp->type == T_CONST)
449 hp->value.ival = ivalue;
450 llassert (value == NULL);
454 hp->value.cpval = value;
457 hp->name = cstring_clip (cstring_fromCharsNew (name), size_fromInt (len));
459 DPRINTF (("Name: *%s*", hp->name));
460 /*@-mustfree@*/ /*@-uniondef@*/ /*@-compdef@*/ /*@-compmempass@*/
462 /*@=mustfree@*/ /*@=uniondef@*/ /*@=compdef@*/ /*@=compmempass@*/
465 hashNode cpphash_installMacro (char *name, size_t len,
466 struct definition *defn, int hash)
468 DPRINTF (("install macro: %s", name));
469 return cpphash_install (name, size_toInt (len), T_MACRO, 0, (char *) defn, hash);
473 cppReader_hashCleanup (void)
477 for (i = CPP_HASHSIZE; --i >= 0; )
479 while (hashtab[i] != NULL)
481 cppReader_deleteMacro (hashtab[i]);