src/cpphash.c

   1 /*
   2 ** Splint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2001 University of Virginia,
   4 **         Massachusetts Institute of Technology
   5 **
   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.
  10 **
  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.
  15 **
  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.
  19 **
  20 ** For information on lclint: lclint-request@cs.virginia.edu
  21 ** To report a bug: lclint-bug@cs.virginia.edu
  22 ** For more information: http://www.splint.org
  23 */
  24 /*
  25 ** cpphash.c
  26 **
  27 ** Pre-processor hash table.  Derived from gnu cpp.
  28 */
  29
  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
  35
  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
  39 later version.
  40
  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.
  45
  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.
  49
  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!  */
  53
  54 # include "lclintMacros.nf"
  55 # include "llbasic.h"
  56 # include <string.h>
  57 # include "cpplib.h"
  58 # include "cpphash.h"
  59
  60 typedef /*@null@*/ /*@only@*/ hashNode o_hashNode;
  61 typedef /*@null@*/ /*@only@*/ hashNode n_hashNode;
  62
  63 static o_hashNode hashtab[CPP_HASHSIZE];
  64 static o_hashNode ohashtab[CPP_HASHSIZE];
  65
  66 static void hashNode_delete (/*@null@*/ /*@only@*/ hashNode);
  67
  68 /* p_prev need not be defined, but isn't defined by hashNode_copy */
  69
  70 /*@function static unsigned int hashStep (unsigned, char) modifies nothing ; @*/
  71 # define hashStep(old, c) (((old) << 2) + (unsigned int) (c))
  72
  73 /*@function static unsigned int makePositive (unsigned int) modifies nothing ; @*/
  74 # define makePositive(v) ((v) & 0x7fffffff) /* make number positive */
  75
  76 static /*@null@*/ hashNode hashNode_copy (/*@null@*/ hashNode,
  77                                           /*@null@*/ /*@dependent@*/ n_hashNode *p_hdr,
  78                                           /*@dependent@*/ /*@null@*/ /*@special@*/ hashNode p_prev)
  79      /*@*/ ;
  80
  81 void cppReader_saveHashtab ()
  82 {
  83   int i;
  84
  85   for (i = 0; i < CPP_HASHSIZE; i++)
  86     {
  87       ohashtab[i] = hashNode_copy (hashtab[i], &ohashtab[i], NULL);
  88     }
  89 }
  90
  91 void cppReader_restoreHashtab ()
  92 {
  93   int i;
  94
  95   for (i = 0; i < CPP_HASHSIZE; i++) {
  96     /* hashNode_delete (hashtab[i]); */
  97     hashtab[i] = hashNode_copy (ohashtab[i], &hashtab[i], NULL);
  98   }
  99 }
 100
 101 static void hashNode_delete (/*@only@*/ /*@null@*/ hashNode node)
 102 {
 103   if (node == NULL)
 104     {
 105       ;
 106     }
 107   else
 108     {
 109       hashNode_delete (node->next);
 110
 111       if (node->type == T_MACRO)
 112         {
 113           DEFINITION *d = node->value.defn;
 114           struct reflist *ap, *nextap;
 115
 116           for (ap = d->pattern; ap != NULL; ap = nextap)
 117             {
 118               nextap = ap->next;
 119               sfree (ap);
 120             }
 121
 122           if (d->nargs >= 0)
 123             {
 124               sfree (d->args.argnames);
 125             }
 126
 127           sfree (d);
 128         }
 129
 130       cstring_free (node->name);
 131       sfree (node);
 132     }
 133 }
 134
 135 /*@null@*/ hashNode hashNode_copy (hashNode node, hashNode *hdr,
 136                                    /*@dependent@*/ hashNode prev)
 137 {
 138   if (node == NULL)
 139     {
 140       return NULL;
 141     }
 142   else
 143     {
 144       hashNode res = dmalloc (sizeof (*res));
 145
 146       res->next = hashNode_copy (node->next, hdr, res);
 147       res->prev = prev;
 148
 149       res->bucket_hdr = hdr;
 150       res->type = node->type;
 151       res->length = node->length;
 152       res->name = cstring_copy (node->name);
 153
 154       if (node->type == T_MACRO)
 155         {
 156           DEFINITION *d = node->value.defn;
 157           DEFINITION *nd = dmalloc (sizeof (*nd));
 158
 159           res->value.defn = nd;
 160           nd->nargs = d->nargs;
 161
 162           nd->length = d->length;
 163           nd->predefined = d->predefined;
 164           nd->expansion = d->expansion;
 165           nd->line = d->line;
 166           nd->file = d->file;
 167
 168           if (d->pattern != NULL)
 169             {
 170               struct reflist *ap, *nextap;
 171               struct reflist **last = &nd->pattern;
 172
 173               for (ap = d->pattern; ap != NULL; ap = nextap)
 174                 {
 175                   struct reflist *npattern = dmalloc (sizeof (*(nd->pattern)));
 176
 177                   nextap = ap->next;
 178
 179                   if (ap == d->pattern)
 180                     {
 181                       *last = npattern;
 182                       /*@-branchstate@*/
 183                     } /*@=branchstate@*/ /* npattern is propagated through loop */
 184
 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;
 192                   /*@-mustfree@*/
 193                 }
 194               /*@=mustfree@*/
 195             }
 196           else
 197             {
 198               nd->pattern = NULL;
 199             }
 200
 201           if (d->nargs >= 0)
 202             {
 203               llassert (d->args.argnames != NULL);
 204
 205               nd->args.argnames = mstring_copy (d->args.argnames);
 206             }
 207           else
 208             {
 209               /*
 210               ** This fix found by:
 211               **
 212               **    Date: Mon, 31 May 1999 15:10:50 +0900 (JST)
 213               **    From: "N.Komazaki" <koma@focs.sei.co.jp>
 214               */
 215
 216               /*! why doesn't lclint report an error for this? */
 217               nd->args.argnames = mstring_createEmpty ();
 218             }
 219         }
 220       else
 221         {
 222           if (node->type == T_CONST)
 223             {
 224               res->value.ival = node->value.ival;
 225             }
 226           else if (node->type == T_PCSTRING)
 227             {
 228               res->value.cpval = mstring_copy (node->value.cpval);
 229               llassert (res->value.cpval != NULL);
 230             }
 231           else
 232             {
 233               res->value = node->value;
 234             }
 235         }
 236
 237       /*@-uniondef@*/ /*@-compdef@*/ /* res->prev is not defined */
 238       return res;
 239       /*@=uniondef@*/ /*@=compdef@*/
 240     }
 241 }
 242
 243 /* Return hash function on name.  must be compatible with the one
 244    computed a step at a time, elsewhere  */
 245
 246 int
 247 hashf (const char *name, int len, int hashsize)
 248 {
 249   unsigned int r = 0;
 250
 251   while (len-- != 0)
 252     {
 253       r = hashStep (r, *name++);
 254     }
 255
 256   return (int) (makePositive (r) % hashsize);
 257 }
 258
 259 /*
 260 ** Find the most recent hash node for name name (ending with first
 261 ** non-identifier char) cppReader_installed by install
 262 **
 263 ** If LEN is >= 0, it is the length of the name.
 264 ** Otherwise, compute the length by scanning the entire name.
 265 **
 266 ** If HASH is >= 0, it is the precomputed hash code.
 267 ** Otherwise, compute the hash code.
 268 */
 269
 270 /*@null@*/ hashNode cppReader_lookup (char *name, int len, int hash)
 271 {
 272   const char *bp;
 273   hashNode bucket;
 274
 275   if (len < 0)
 276     {
 277       for (bp = name; isIdentifierChar (*bp); bp++)
 278         {
 279           ;
 280         }
 281
 282       len = bp - name;
 283     }
 284
 285   if (hash < 0)
 286     {
 287       hash = hashf (name, len, CPP_HASHSIZE);
 288     }
 289
 290   bucket = hashtab[hash];
 291
 292   while (bucket != NULL)
 293     {
 294       if (bucket->length == len &&
 295           cstring_equalLen (bucket->name, cstring_fromChars (name), len))
 296         {
 297           return bucket;
 298         }
 299
 300       bucket = bucket->next;
 301     }
 302
 303   return NULL;
 304 }
 305
 306 /*@null@*/ hashNode cppReader_lookupExpand (char *name, int len, int hash)
 307 {
 308   hashNode node = cppReader_lookup (name, len, hash);
 309
 310   DPRINTF (("Lookup expand: %s", name));
 311
 312   if (node != NULL)
 313     {
 314       if (node->type == T_MACRO)
 315         {
 316           DEFINITION *defn = (DEFINITION *) node->value.defn;
 317
 318           DPRINTF (("Check macro..."));
 319
 320           if (defn->noExpand) {
 321             DPRINTF (("No expand!"));
 322             return NULL;
 323           }
 324         }
 325     }
 326
 327   return node;
 328 }
 329
 330 /*
 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.
 334  */
 335
 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.  */
 343
 344 void
 345 cppReader_deleteMacro (hashNode hp)
 346 {
 347   if (hp->prev != NULL)
 348     {
 349       /*@-mustfree@*/
 350       hp->prev->next = hp->next;
 351       /*@=mustfree@*/
 352       /*@-branchstate@*/
 353     } /*@=branchstate@*/
 354
 355   if (hp->next != NULL)
 356     {
 357       hp->next->prev = hp->prev;
 358     }
 359
 360   /* make sure that the bucket chain header that
 361      the deleted guy was on points to the right thing afterwards.  */
 362   if (hp == *hp->bucket_hdr) {
 363     *hp->bucket_hdr = hp->next;
 364   }
 365
 366   if (hp->type == T_MACRO)
 367     {
 368       DEFINITION *d = hp->value.defn;
 369       struct reflist *ap, *nextap;
 370
 371       for (ap = d->pattern; ap != NULL; ap = nextap)
 372         {
 373           nextap = ap->next;
 374           sfree (ap);
 375         }
 376
 377       if (d->nargs >= 0)
 378         {
 379           sfree (d->args.argnames);
 380         }
 381     }
 382
 383   /*@-dependenttrans@*/ /*@-exposetrans@*/ /*@-compdestroy@*/
 384   sfree (hp);
 385   /*@=dependenttrans@*/ /*@=exposetrans@*/ /*@=compdestroy@*/
 386 }
 387
 388 /* Install a name in the main hash table, even if it is already there.
 389      name stops with first non alphanumeric, except leading '#'.
 390    caller must check against redefinition if that is desired.
 391    cppReader_deleteMacro () removes things installed by install () in fifo order.
 392    this is important because of the `defined' special symbol used
 393    in #if, and also if pushdef/popdef directives are ever implemented.
 394
 395    If LEN is >= 0, it is the length of the name.
 396    Otherwise, compute the length by scanning the entire name.
 397
 398    If HASH is >= 0, it is the precomputed hash code.
 399    Otherwise, compute the hash code.  */
 400
 401 hashNode cppReader_install (char *name, int len, enum node_type type,
 402                              int ivalue, char *value, int hash)
 403 {
 404   hashNode hp;
 405   int i, bucket;
 406   char *p;
 407
 408   DPRINTF (("Install: %s", name));
 409
 410   if (len < 0) {
 411     p = name;
 412
 413     while (isIdentifierChar (*p))
 414       {
 415         p++;
 416       }
 417
 418     len = p - name;
 419   }
 420
 421   if (hash < 0)
 422     {
 423       hash = hashf (name, len, CPP_HASHSIZE);
 424     }
 425
 426   i = sizeof (*hp) + len + 1;
 427
 428   hp = (hashNode) dmalloc (sizeof (*hp));
 429   bucket = hash;
 430   hp->bucket_hdr = &hashtab[bucket];
 431
 432   hp->next = hashtab[bucket];
 433   hp->prev = NULL;
 434
 435   if (hp->next != NULL)
 436     {
 437       hp->next->prev = hp;
 438     }
 439
 440
 441   hashtab[bucket] = hp;
 442
 443   hp->type = type;
 444   hp->length = len;
 445
 446   if (hp->type == T_CONST)
 447     {
 448       hp->value.ival = ivalue;
 449       llassert (value == NULL);
 450     }
 451   else
 452     {
 453       hp->value.cpval = value;
 454     }
 455
 456   hp->name = cstring_clip (cstring_fromCharsNew (name), len);
 457
 458   DPRINTF (("Name: *%s*", hp->name));
 459   /*@-mustfree@*/ /*@-uniondef@*/ /*@-compdef@*/ /*@-compmempass@*/
 460   return hp;
 461   /*@=mustfree@*/ /*@=uniondef@*/ /*@=compdef@*/ /*@=compmempass@*/
 462 }
 463
 464 hashNode cppReader_installMacro (char *name, int len,
 465                                  struct definition *defn, int hash)
 466 {
 467   return cppReader_install (name, len, T_MACRO, 0, (char  *) defn, hash);
 468 }
 469
 470 void
 471 cppReader_hashCleanup (void)
 472 {
 473   int i;
 474
 475   for (i = CPP_HASHSIZE; --i >= 0; )
 476     {
 477       while (hashtab[i] != NULL)
 478         {
 479           cppReader_deleteMacro (hashtab[i]);
 480         }
 481     }
 482 }