src/lsymbol.c

   1 /*
   2 ** Splint - annotation-assisted static program checker
   3 ** Copyright (C) 1994-2003 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 splint: info@splint.org
  21 ** To report a bug: splint-bug@splint.org
  22 ** For more information: http://www.splint.org
  23 */
  24 /*
  25 ** lsymbol.c
  26 **
  27 ** String manager
  28 **
  29 **      This module implements an abstraction for efficiently managing
  30 **      string comparisons.  It alloctes and manages a string context,
  31 **      which consists of three major data structures:
  32 **       - a StringEntry table
  33 **       - a character-string table
  34 **       - a hash table
  35 **
  36 **      A StringEntry table is made of of StringEntries. StringEntries
  37 **      are linked in hash-chains to support fast lookup. Every
  38 **      allocated StringEntry corresponds to a unique character-string
  39 **      in the character-string table. StringEntries can be referenced
  40 **      via Symbol values.
  41 **
  42 **      A character-string table is composed of character-strings. A
  43 **      character-string is a variable length byte array that is always
  44 **      null-terminated ('\0').
  45 **
  46 **      A hash table manages the start of each hash-list of StringEntries.
  47 **      StringEntries are entered into the hash-list by hashing on its
  48 **      character-string representation.
  49 **
  50 **      This module provides routines for retrieving a unique Symbol for a
  51 **      given character-string, and returning the character-string given its
  52 **      corresponding Symbol. An item is allocated in both tables whenever a
  53 **      new character-string is encountered, otherwise the Symbol for the
  54 **      character-string is found and returned.
  55 **
  56 **  AUTHORS:
  57 **
  58 **      Shota Aki
  59 **
  60 **  MODIFICATION HISTORY:
  61 **
  62 **      {0} Aki      at Digital -- 89.08.07 -- original
  63 **      {1} Aki      at Digital -- 89.11.13 -- context switchable
  64 **      {2} Aki      at Digital -- 89.11.28 -- removed use of TABLES interface
  65 **      {3} Aki      at Digital -- 89.11.29 -- moved to RC
  66 **      {4} Aki      at Digital -- 90.04.10 -- support primary-context
  67 **      {5} McKeeman at Digital -- 90.05.08 -- C to Larch SL
  68 **      {6} Wild     at Digital -- 91.06.26 -- Update copyright notice.
  69 **      {n} Who      at Where   -- yy.mm.dd -- what
  70 */
  71
  72 # include "splintMacros.nf"
  73 # include "basic.h"
  74
  75 /*@+ignorequals@*/
  76
  77 /*@constant int NULLFACTOR; @*/
  78 # define NULLFACTOR 1
  79
  80 typedef Handle CharIndex;
  81
  82 typedef struct
  83 {
  84   lsymbol HashNext;
  85   CharIndex i;
  86 } StringEntry;
  87
  88 static void AllocCharSpace (unsigned p_newSize) /*@modifies internalState@*/ ;
  89 static CharIndex AllocChar (/*@unique@*/ const char *p_name) /*@modifies internalState@*/ ;
  90 static void AllocEntrySpace (unsigned p_newSize) /*@modifies internalState@*/ ;
  91 static lsymbol AllocEntry (const char *p_name, long unsigned p_hashValue)
  92    /*@modifies internalState@*/ ;
  93
  94 static /*@only@*/ /*@null@*/ lsymbol *hashArray = NULL;
  95
  96 static long unsigned MaxChar;
  97 static CharIndex FreeChar;
  98 static /*@only@*/ /*@null@*/ char *CharString;
  99
 100 static long unsigned MaxEntry;
 101 static lsymbol FreeEntry;
 102 static /*@only@*/ /*@null@*/ StringEntry *Entry;
 103
 104 lsymbol
 105 lsymbol_fromString (cstring s)
 106 {
 107   if (cstring_isUndefined (s))
 108     {
 109       return lsymbol_undefined;
 110     }
 111   else
 112     {
 113       return (lsymbol_fromChars (cstring_toCharsSafe (s)));
 114     }
 115 }
 116
 117 lsymbol
 118 lsymbol_fromChars (/*@temp@*/ const char *name)
 119 {
 120   lsymbol ss;
 121   long unsigned hashValue;
 122   unsigned h = 0;
 123   const char *p = name;
 124
 125   while (*p != '\0')
 126     {
 127       h = (h << 1) + (unsigned) (*p);
 128       p++;
 129     }
 130
 131   hashValue = h & HASHMASK;
 132
 133   if (hashArray == NULL) /* evs - was MaxIndex == 0 */
 134     {
 135       /* nothing initialized */
 136       ss = AllocEntry (name, hashValue);
 137     }
 138   else
 139     {
 140       ss = hashArray[hashValue]; /* start of hash chain */
 141
 142       if (ss == lsymbol_undefined)
 143         {
 144           /* hash not initialized */
 145           ss = AllocEntry (name, hashValue);
 146         }
 147       else
 148         {
 149          /*
 150           * Traverse hash-chain. Loop terminates when
 151           * a match is found or end of chain is encountered.
 152           */
 153
 154           llassert (Entry != NULL);
 155           llassert (CharString != NULL);
 156
 157           while (strcmp (&CharString[Entry[ss].i], name) != 0)
 158             {
 159               if (lsymbol_undefined == (ss = Entry[ss].HashNext))
 160                 {
 161                   ss = AllocEntry (name, hashValue);
 162                   break;
 163                 }
 164             }
 165         }
 166     }
 167
 168   return ss;
 169 }
 170
 171 cstring lsymbol_toString (lsymbol ss)
 172 {
 173   return (cstring_fromChars (lsymbol_toChars (ss)));
 174 }
 175
 176 char *
 177 lsymbol_toCharsSafe (lsymbol ss)
 178 {
 179   char *ret = lsymbol_toChars (ss);
 180
 181   if (ret == NULL)
 182     {
 183       ret = mstring_create (0);
 184     }
 185
 186   return ret;
 187 }
 188
 189 char *lsymbol_toChars (lsymbol ss)
 190 {
 191   if (lsymbol_isDefined (ss))
 192     {
 193       if (ss >= FreeEntry)
 194         {
 195           llcontbug (message ("lsymbol_toChars: invalid lsymbol: %d", ss));
 196           return NULL;
 197         }
 198
 199       llassert (Entry != NULL);
 200       llassert (CharString != NULL);
 201
 202       return &CharString[Entry[ss].i];
 203     }
 204   else
 205     {
 206       return NULL;
 207     }
 208 }
 209
 210 static void
 211 AllocCharSpace (unsigned newSize)
 212 {
 213   llassert (newSize > MaxChar);
 214
 215   CharString = (char *) drealloc ((void *) CharString, newSize * sizeof (*CharString));
 216   MaxChar = newSize;
 217 /*@-compdef@*/
 218 } /*@=compdef@*/
 219
 220 static CharIndex
 221 AllocChar (/*@unique@*/ const char *name)
 222 {
 223   int namelength;
 224   CharIndex retVal;
 225   long unsigned size;
 226   CharIndex unused;
 227
 228   namelength = size_toInt (strlen (name));
 229   unused = FreeChar;
 230   size = MaxChar;
 231
 232   if ((unused + namelength + NULLFACTOR) > size)
 233     {
 234       if (size == 0)
 235         size = INITCHARSTRING;
 236       else
 237         size = (unsigned) (DELTACHARSTRING * size);
 238
 239       AllocCharSpace (size);
 240     }
 241
 242   llassert (CharString != NULL);
 243
 244   retVal = unused;
 245   strcpy (&CharString[unused], name);
 246   unused += namelength;
 247   CharString[unused] = '\0';
 248   unused += 1;
 249
 250   FreeChar = unused;
 251   return retVal;
 252 }
 253
 254 static void
 255 AllocEntrySpace (unsigned newSize)
 256 {
 257   llassert (newSize > MaxEntry);
 258
 259   /* Casts mess up checking here. */
 260   /*@-mustfree@*/
 261   Entry = (StringEntry *) drealloc ((void *) Entry, newSize * sizeof (*Entry));
 262   /*@=mustfree@*/
 263
 264   if (MaxEntry == 0) MaxEntry = 1;
 265
 266   FreeEntry = MaxEntry;
 267   MaxEntry = newSize;
 268 /*@-compdef@*/
 269 } /*@=compdef@*/
 270
 271 static lsymbol AllocEntry (const char *name, long unsigned hashValue)
 272 {
 273   lsymbol retVal;
 274   long unsigned size;
 275
 276   size = MaxEntry;
 277
 278   if ((retVal = FreeEntry) == size)
 279     {
 280       if (size == 0)
 281         {
 282           size = INITSTRINGENTRY;
 283         }
 284       else
 285         {
 286           size = (unsigned) (DELTASTRINGENTRY * size);
 287         }
 288
 289       AllocEntrySpace (size);
 290       retVal = FreeEntry;
 291     }
 292
 293   FreeEntry = retVal + 1;
 294
 295   llassert (hashArray != NULL);
 296   llassert (Entry != NULL);
 297
 298   Entry[retVal].HashNext = hashArray[hashValue];
 299   hashArray[hashValue] = retVal;
 300   Entry[retVal].i = AllocChar (name);
 301
 302   return retVal;
 303 }
 304
 305 void
 306 lsymbol_initMod (void)
 307    /*@globals undef CharString, undef Entry; @*/
 308 {
 309   int i;
 310
 311   if (hashArray != NULL)
 312     {
 313       sfree (hashArray);
 314     }
 315
 316   hashArray = (lsymbol *) dmalloc (HASHSIZE * sizeof (*hashArray));
 317
 318   for (i = 0; i < HASHSIZE; i++)
 319     {
 320       hashArray[i] = lsymbol_undefined;
 321     }
 322
 323   MaxChar = 0;
 324   MaxEntry = 0;
 325
 326   FreeChar = 0;
 327   FreeEntry = 0;
 328
 329   CharString = (char *) 0;
 330   Entry = (StringEntry *) 0;
 331 /*@-compdef@*/
 332 }
 333 /*@=compdef@*/
 334
 335 void
 336 lsymbol_destroyMod (void)
 337    /*@globals killed Entry, killed CharString, killed hashArray@*/
 338 {
 339    sfree (Entry);
 340    sfree (CharString);
 341    sfree (hashArray);
 342 }
 343
 344 # ifdef DEADCODE
 345 void
 346 lsymbol_printStats (void)
 347 {
 348   /* only for debugging */
 349   printf ("Number of lsymbols generated = %d\n", (int) FreeEntry);
 350 }
 351 # endif /* DEADCODE */
 352
 353 /*
 354 ** note lsymbol_setbool, etc. defined in abstract.c
 355 */
 356