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@*/ char *p_name) /*@modifies internalState@*/ ;
90 static void AllocEntrySpace (unsigned p_newSize) /*@modifies internalState@*/ ;
91 static lsymbol AllocEntry (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
lsymbol_fromString(cstring s)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
lsymbol_fromChars(char * name)118 lsymbol_fromChars (/*@temp@*/ char *name)
119 {
120 lsymbol ss;
121 long unsigned hashValue;
122 unsigned h = 0;
123 char *p = name;
124
125 while (*p != '\0')
126 {
127 h = (h << 1) + (unsigned) (*p++);
128 }
129
130 hashValue = h & HASHMASK;
131
132 if (hashArray == NULL) /* evs - was MaxIndex == 0 */
133 {
134 /* nothing initialized */
135 ss = AllocEntry (name, hashValue);
136 }
137 else
138 {
139 ss = hashArray[hashValue]; /* start of hash chain */
140
141 if (ss == lsymbol_undefined)
142 {
143 /* hash not initialized */
144 ss = AllocEntry (name, hashValue);
145 }
146 else
147 {
148 /*
149 * Traverse hash-chain. Loop terminates when
150 * a match is found or end of chain is encountered.
151 */
152
153 llassert (Entry != NULL);
154 llassert (CharString != NULL);
155
156 while (strcmp (&CharString[Entry[ss].i], name) != 0)
157 {
158 if (lsymbol_undefined == (ss = Entry[ss].HashNext))
159 {
160 ss = AllocEntry (name, hashValue);
161 break;
162 }
163 }
164 }
165 }
166
167 return ss;
168 }
169
lsymbol_toString(lsymbol ss)170 cstring lsymbol_toString (lsymbol ss)
171 {
172 return (cstring_fromChars (lsymbol_toChars (ss)));
173 }
174
175 char *
lsymbol_toCharsSafe(lsymbol ss)176 lsymbol_toCharsSafe (lsymbol ss)
177 {
178 char *ret = lsymbol_toChars (ss);
179
180 if (ret == NULL)
181 {
182 ret = mstring_create (0);
183 }
184
185 return ret;
186 }
187
lsymbol_toChars(lsymbol ss)188 char *lsymbol_toChars (lsymbol ss)
189 {
190 if (lsymbol_isDefined (ss))
191 {
192 if (ss >= FreeEntry)
193 {
194 llcontbug (message ("lsymbol_toChars: invalid lsymbol: %d", ss));
195 return NULL;
196 }
197
198 llassert (Entry != NULL);
199 llassert (CharString != NULL);
200
201 return &CharString[Entry[ss].i];
202 }
203 else
204 {
205 return NULL;
206 }
207 }
208
209 static void
AllocCharSpace(unsigned newSize)210 AllocCharSpace (unsigned newSize)
211 {
212 llassert (newSize > MaxChar);
213
214 CharString = (char *) drealloc ((void *) CharString, newSize * sizeof (*CharString));
215 MaxChar = newSize;
216 /*@-compdef@*/
217 } /*@=compdef@*/
218
219 static CharIndex
AllocChar(char * name)220 AllocChar (/*@unique@*/ char *name)
221 {
222 int namelength;
223 CharIndex retVal;
224 long unsigned size;
225 CharIndex unused;
226
227 namelength = size_toInt (strlen (name));
228 unused = FreeChar;
229 size = MaxChar;
230
231 if ((unused + namelength + NULLFACTOR) > size)
232 {
233 if (size == 0)
234 size = INITCHARSTRING;
235 else
236 size = (unsigned) (DELTACHARSTRING * size);
237
238 AllocCharSpace (size);
239 }
240
241 llassert (CharString != NULL);
242
243 retVal = unused;
244 strcpy (&CharString[unused], name);
245 unused += namelength;
246 CharString[unused] = '\0';
247 unused += 1;
248
249 FreeChar = unused;
250 return retVal;
251 }
252
253 static void
AllocEntrySpace(unsigned newSize)254 AllocEntrySpace (unsigned newSize)
255 {
256 llassert (newSize > MaxEntry);
257
258 /* Casts mess up checking here. */
259 /*@-mustfree@*/
260 Entry = (StringEntry *) drealloc ((void *) Entry, newSize * sizeof (*Entry));
261 /*@=mustfree@*/
262
263 if (MaxEntry == 0) MaxEntry = 1;
264
265 FreeEntry = MaxEntry;
266 MaxEntry = newSize;
267 /*@-compdef@*/
268 } /*@=compdef@*/
269
AllocEntry(char * name,long unsigned hashValue)270 static lsymbol AllocEntry (char *name, long unsigned hashValue)
271 {
272 lsymbol retVal;
273 long unsigned size;
274
275 size = MaxEntry;
276
277 if ((retVal = FreeEntry) == size)
278 {
279 if (size == 0)
280 {
281 size = INITSTRINGENTRY;
282 }
283 else
284 {
285 size = (unsigned) (DELTASTRINGENTRY * size);
286 }
287
288 AllocEntrySpace (size);
289 retVal = FreeEntry;
290 }
291
292 FreeEntry = retVal + 1;
293
294 llassert (hashArray != NULL);
295 llassert (Entry != NULL);
296
297 Entry[retVal].HashNext = hashArray[hashValue];
298 hashArray[hashValue] = retVal;
299 Entry[retVal].i = AllocChar (name);
300
301 return retVal;
302 }
303
304 void
lsymbol_initMod(void)305 lsymbol_initMod (void)
306 /*@globals undef CharString, undef Entry; @*/
307 {
308 int i;
309
310 if (hashArray != NULL)
311 {
312 sfree (hashArray);
313 }
314
315 hashArray = (lsymbol *) dmalloc (HASHSIZE * sizeof (*hashArray));
316
317 for (i = 0; i < HASHSIZE; i++)
318 {
319 hashArray[i] = lsymbol_undefined;
320 }
321
322 MaxChar = 0;
323 MaxEntry = 0;
324
325 FreeChar = 0;
326 FreeEntry = 0;
327
328 CharString = (char *) 0;
329 Entry = (StringEntry *) 0;
330 /*@-compdef@*/
331 }
332 /*@=compdef@*/
333
334 void
lsymbol_destroyMod(void)335 lsymbol_destroyMod (void)
336 /*@globals killed Entry, killed CharString, killed hashArray@*/
337 {
338 sfree (Entry);
339 sfree (CharString);
340 sfree (hashArray);
341 }
342
343 void
lsymbol_printStats(void)344 lsymbol_printStats (void)
345 {
346 /* only for debugging */
347 printf ("Number of lsymbols generated = %d\n", (int) FreeEntry);
348 }
349
350 /*
351 ** note lsymbol_setbool, etc. defined in abstract.c
352 */
353
354
355
356
357
358
359
360
361