src/cpphash.c

   1 /*
   2 ** LCLint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2000 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://lclint.cs.virginia.edu
  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 "cpp.h"
  58 # include "cpplib.h"
  59 # include "cpphash.h"
  60
  61 typedef /*@only@*/ HASHNODE *o_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 *
  77    HashNode_copy (/*@null@*/ HASHNODE *,
  78                   /*@dependent@*/ HASHNODE **p_hdr,
  79                   /*@dependent@*/ /*@null@*/ /*@special@*/ HASHNODE *p_prev)
  80      /*@*/ ;
  81
  82 void cppReader_saveHashtab ()
  83 {
  84   int i;
  85
  86   for (i = 0; i < CPP_HASHSIZE; i++)
  87     {
  88       ohashtab[i] = HashNode_copy (hashtab[i], &ohashtab[i], NULL);
  89     }
  90 }
  91
  92 void cppReader_restoreHashtab ()
  93 {
  94   int i;
  95
  96   for (i = 0; i < CPP_HASHSIZE; i++) {
  97     /* HashNode_delete (hashtab[i]); */
  98     hashtab[i] = HashNode_copy (ohashtab[i], &hashtab[i], NULL);
  99   }
 100 }
 101
 102 static void HashNode_delete (/*@only@*/ /*@null@*/ HASHNODE *node)
 103 {
 104   if (node == NULL)
 105     {
 106       ;
 107     }
 108   else
 109     {
 110       HashNode_delete (node->next);
 111
 112       if (node->type == T_MACRO)
 113         {
 114           DEFINITION *d = node->value.defn;
 115           struct reflist *ap, *nextap;
 116
 117           for (ap = d->pattern; ap != NULL; ap = nextap)
 118             {
 119               nextap = ap->next;
 120               sfree (ap);
 121             }
 122
 123           if (d->nargs >= 0)
 124             {
 125               sfree (d->args.argnames);
 126             }
 127
 128           sfree (d);
 129         }
 130
 131       cstring_free (node->name);
 132       sfree (node);
 133     }
 134 }
 135
 136 /*@null@*/ HASHNODE *HashNode_copy (HASHNODE *node, HASHNODE **hdr,
 137                                     /*@dependent@*/ HASHNODE *prev)
 138 {
 139   if (node == NULL)
 140     {
 141       return NULL;
 142     }
 143   else
 144     {
 145       HASHNODE *res = dmalloc (sizeof (*res));
 146
 147       res->next = HashNode_copy (node->next, hdr, res);
 148       res->prev = prev;
 149
 150       res->bucket_hdr = hdr;
 151       res->type = node->type;
 152       res->length = node->length;
 153       res->name = cstring_copy (node->name);
 154
 155       if (node->type == T_MACRO)
 156         {
 157           DEFINITION *d = node->value.defn;
 158           DEFINITION *nd = dmalloc (sizeof (*nd));
 159
 160           res->value.defn = nd;
 161           nd->nargs = d->nargs;
 162
 163           nd->length = d->length;
 164           nd->predefined = d->predefined;
 165           nd->expansion = d->expansion;
 166           nd->line = d->line;
 167           nd->file = d->file;
 168
 169           if (d->pattern != NULL)
 170             {
 171               struct reflist *ap, *nextap;
 172               struct reflist **last = &nd->pattern;
 173
 174               for (ap = d->pattern; ap != NULL; ap = nextap)
 175                 {
 176                   struct reflist *npattern = dmalloc (sizeof (*(nd->pattern)));
 177
 178                   nextap = ap->next;
 179
 180                   if (ap == d->pattern)
 181                     {
 182                       *last = npattern;
 183                       /*@-branchstate@*/
 184                     } /*@=branchstate@*/ /* npattern is propagated through loop */
 185
 186                   last = &(npattern->next);
 187                   npattern->next = NULL; /* will get filled in */
 188                   npattern->stringify = d->pattern->stringify;
 189                   npattern->raw_before = d->pattern->raw_before;
 190                   npattern->raw_after = d->pattern->raw_after;
 191                   npattern->rest_args = d->pattern->rest_args;
 192                   npattern->argno = d->pattern->argno;
 193                   /*@-mustfree@*/
 194                 }
 195               /*@=mustfree@*/
 196             }
 197           else
 198             {
 199               nd->pattern = NULL;
 200             }
 201
 202           if (d->nargs >= 0)
 203             {
 204               llassert (d->args.argnames != NULL);
 205
 206               nd->args.argnames = mstring_copy (d->args.argnames);
 207             }
 208           else
 209             {
 210               /*
 211               ** This fix found by:
 212               **
 213               **    Date: Mon, 31 May 1999 15:10:50 +0900 (JST)
 214               **    From: "N.Komazaki" <koma@focs.sei.co.jp>
 215               */
 216
 217               /*! why doesn't lclint report an error for this? */
 218               nd->args.argnames = mstring_createEmpty ();
 219             }
 220         }
 221       else
 222         {
 223           if (node->type == T_CONST)
 224             {
 225               res->value.ival = node->value.ival;
 226             }
 227           else if (node->type == T_PCSTRING)
 228             {
 229               res->value.cpval = mstring_copy (node->value.cpval);
 230                   llassert (res->value.cpval != NULL);
 231             }
 232           else
 233             {
 234               res->value = node->value;
 235             }
 236         }
 237
 238       /*@-uniondef@*/ /*@-compdef@*/ /* res->prev is not defined */
 239       return res;
 240       /*@=uniondef@*/ /*@=compdef@*/
 241     }
 242 }
 243
 244 /* Return hash function on name.  must be compatible with the one
 245    computed a step at a time, elsewhere  */
 246
 247 int
 248 hashf (const char *name, int len, int hashsize)
 249 {
 250   unsigned int r = 0;
 251
 252   while (len-- != 0)
 253     {
 254       r = hashStep (r, *name++);
 255     }
 256
 257   return (int) (makePositive (r) % hashsize);
 258 }
 259
 260 /*
 261 ** Find the most recent hash node for name name (ending with first
 262 ** non-identifier char) cppReader_installed by install
 263 **
 264 ** If LEN is >= 0, it is the length of the name.
 265 ** Otherwise, compute the length by scanning the entire name.
 266 **
 267 ** If HASH is >= 0, it is the precomputed hash code.
 268 ** Otherwise, compute the hash code.
 269 */
 270
 271 /*@null@*/ HASHNODE *cppReader_lookup (char *name, int len, int hash)
 272 {
 273   const char *bp;
 274   HASHNODE *bucket;
 275
 276   if (len < 0)
 277     {
 278       for (bp = name; isIdentifierChar (*bp); bp++)
 279         {
 280           ;
 281         }
 282
 283       len = bp - name;
 284     }
 285
 286   if (hash < 0)
 287     {
 288       hash = hashf (name, len, CPP_HASHSIZE);
 289     }
 290
 291   bucket = hashtab[hash];
 292
 293   while (bucket != NULL)
 294     {
 295       if (bucket->length == len &&
 296           cstring_equalLen (bucket->name, cstring_fromChars (name), len))
 297         {
 298           return bucket;
 299         }
 300
 301       bucket = bucket->next;
 302     }
 303
 304   return NULL;
 305 }
 306
 307 /*@null@*/ HASHNODE *cppReader_lookupExpand (char *name, int len, int hash)
 308 {
 309   HASHNODE *node = cppReader_lookup (name, len, hash);
 310
 311   DPRINTF (("Lookup expand: %s", name));
 312
 313   if (node != NULL)
 314     {
 315       if (node->type == T_MACRO)
 316         {
 317           DEFINITION *defn = (DEFINITION *) node->value.defn;
 318
 319           DPRINTF (("Check macro..."));
 320
 321           if (defn->noExpand) {
 322             DPRINTF (("No expand!"));
 323             return NULL;
 324           }
 325         }
 326     }
 327
 328   return node;
 329 }
 330
 331 /*
 332  * Delete a hash node.  Some weirdness to free junk from macros.
 333  * More such weirdness will have to be added if you define more hash
 334  * types that need it.
 335  */
 336
 337 /* Note that the DEFINITION of a macro is removed from the hash table
 338    but its storage is not freed.  This would be a storage leak
 339    except that it is not reasonable to keep undefining and redefining
 340    large numbers of macros many times.
 341    In any case, this is necessary, because a macro can be #undef'd
 342    in the middle of reading the arguments to a call to it.
 343    If #undef freed the DEFINITION, that would crash.  */
 344
 345 void
 346 cppReader_deleteMacro (HASHNODE *hp)
 347 {
 348   if (hp->prev != NULL)
 349     {
 350       /*@-mustfree@*/
 351       hp->prev->next = hp->next;
 352       /*@=mustfree@*/
 353       /*@-branchstate@*/
 354     } /*@=branchstate@*/
 355
 356   if (hp->next != NULL)
 357     {
 358       hp->next->prev = hp->prev;
 359     }
 360
 361   /* make sure that the bucket chain header that
 362      the deleted guy was on points to the right thing afterwards.  */
 363   if (hp == *hp->bucket_hdr) {
 364     *hp->bucket_hdr = hp->next;
 365   }
 366
 367   if (hp->type == T_MACRO)
 368     {
 369       DEFINITION *d = hp->value.defn;
 370       struct reflist *ap, *nextap;
 371
 372       for (ap = d->pattern; ap != NULL; ap = nextap)
 373         {
 374           nextap = ap->next;
 375           sfree (ap);
 376         }
 377
 378       if (d->nargs >= 0)
 379         {
 380           sfree (d->args.argnames);
 381         }
 382     }
 383
 384   /*@-dependenttrans@*/ /*@-exposetrans@*/ /*@-compdestroy@*/
 385   sfree (hp);
 386   /*@=dependenttrans@*/ /*@=exposetrans@*/ /*@=compdestroy@*/
 387 }
 388
 389 /* Install a name in the main hash table, even if it is already there.
 390      name stops with first non alphanumeric, except leading '#'.
 391    caller must check against redefinition if that is desired.
 392    cppReader_deleteMacro () removes things installed by install () in fifo order.
 393    this is important because of the `defined' special symbol used
 394    in #if, and also if pushdef/popdef directives are ever implemented.
 395
 396    If LEN is >= 0, it is the length of the name.
 397    Otherwise, compute the length by scanning the entire name.
 398
 399    If HASH is >= 0, it is the precomputed hash code.
 400    Otherwise, compute the hash code.  */
 401
 402 HASHNODE *cppReader_install (char *name, int len, enum node_type type,
 403                              int ivalue, char *value, int hash)
 404 {
 405   HASHNODE *hp;
 406   int i, bucket;
 407   char *p, *q;
 408
 409   if (len < 0) {
 410     p = name;
 411
 412     while (isIdentifierChar (*p))
 413       {
 414         p++;
 415       }
 416
 417     len = p - name;
 418   }
 419
 420   if (hash < 0)
 421     {
 422       hash = hashf (name, len, CPP_HASHSIZE);
 423     }
 424
 425   i = sizeof (*hp) + len + 1;
 426
 427
 428   hp = (HASHNODE *) dmalloc (size_fromInt (i));
 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   hashtab[bucket] = hp;
 441
 442   hp->type = type;
 443   hp->length = len;
 444
 445   if (hp->type == T_CONST)
 446     {
 447       hp->value.ival = ivalue;
 448       llassert (value == NULL);
 449     }
 450   else
 451     {
 452       hp->value.cpval = value;
 453     }
 454
 455   {
 456     char *tmp = ((char *) hp) + sizeof (*hp);
 457     p = tmp;
 458     q = name;
 459
 460     for (i = 0; i < len; i++)
 461       {
 462         *p++ = *q++;
 463       }
 464
 465     tmp[len] = '\0';
 466     hp->name = cstring_fromChars (tmp);
 467   }
 468
 469   /*@-mustfree@*/ /*@-uniondef@*/ /*@-compdef@*/
 470   return hp;
 471   /*@=mustfree@*/ /*@=uniondef@*/ /*@=compdef@*/
 472 }
 473
 474 HASHNODE *cppReader_installMacro (char *name, int len,
 475                                   struct definition *defn, int hash)
 476 {
 477   return cppReader_install (name, len, T_MACRO, 0, (char  *) defn, hash);
 478 }
 479
 480 void
 481 cppReader_hashCleanup (void)
 482 {
 483   int i;
 484
 485   for (i = CPP_HASHSIZE; --i >= 0; )
 486     {
 487       while (hashtab[i] != NULL)
 488         {
 489           cppReader_deleteMacro (hashtab[i]);
 490         }
 491     }
 492 }