]>
Commit | Line | Data |
---|---|---|
1 | /* | |
2 | ** LCLint - 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://lclint.cs.virginia.edu | |
23 | */ | |
24 | /* | |
25 | ** usymIdSet.c | |
26 | ** | |
27 | ** based on set_template.c | |
28 | ** | |
29 | ** where T has T_equal (or change this) and T_unparse | |
30 | */ | |
31 | ||
32 | # include "lclintMacros.nf" | |
33 | # include "basic.h" | |
34 | ||
35 | usymIdSet | |
36 | usymIdSet_new () | |
37 | { | |
38 | return usymIdSet_undefined; | |
39 | } | |
40 | ||
41 | static /*@notnull@*/ /*@only@*/ usymIdSet | |
42 | usymIdSet_newEmpty (void) | |
43 | { | |
44 | usymIdSet s = (usymIdSet) dmalloc (sizeof (*s)); | |
45 | ||
46 | s->entries = 0; | |
47 | s->nspace = usymIdSetBASESIZE; | |
48 | s->elements = (usymId *) dmalloc (sizeof (*s->elements) * usymIdSetBASESIZE); | |
49 | ||
50 | return (s); | |
51 | } | |
52 | ||
53 | static void | |
54 | usymIdSet_grow (/*@notnull@*/ usymIdSet s) | |
55 | { | |
56 | int i; | |
57 | usymId *newelements; | |
58 | ||
59 | s->nspace = usymIdSetBASESIZE; | |
60 | newelements = (usymId *) dmalloc (sizeof (*newelements) * (s->entries + s->nspace)); | |
61 | ||
62 | for (i = 0; i < s->entries; i++) | |
63 | { | |
64 | newelements[i] = s->elements[i]; | |
65 | } | |
66 | ||
67 | sfree (s->elements); | |
68 | s->elements = newelements; | |
69 | } | |
70 | ||
71 | /*@only@*/ usymIdSet | |
72 | usymIdSet_single (usymId t) | |
73 | { | |
74 | usymIdSet s = (usymIdSet) dmalloc (sizeof (*s)); | |
75 | ||
76 | s->entries = 1; | |
77 | s->nspace = usymIdSetBASESIZE - 1; | |
78 | s->elements = (usymId *) dmalloc (sizeof (*s->elements) * usymIdSetBASESIZE); | |
79 | s->elements[0] = t; | |
80 | ||
81 | return (s); | |
82 | } | |
83 | ||
84 | static usymIdSet | |
85 | usymIdSet_insert (/*@returned@*/ usymIdSet s, usymId el) | |
86 | { | |
87 | if (usymIdSet_isUndefined (s)) | |
88 | { | |
89 | s = usymIdSet_newEmpty (); | |
90 | } | |
91 | ||
92 | if (usymIdSet_member (s, el)) | |
93 | { | |
94 | return s; | |
95 | } | |
96 | else | |
97 | { | |
98 | if (s->nspace <= 0) | |
99 | usymIdSet_grow (s); | |
100 | s->nspace--; | |
101 | s->elements[s->entries] = el; | |
102 | s->entries++; | |
103 | return s; | |
104 | } | |
105 | } | |
106 | ||
107 | static usymIdSet | |
108 | usymIdSet_copy (/*@notnull@*/ usymIdSet s) | |
109 | { | |
110 | int size = s->entries + 1; | |
111 | usymIdSet t = (usymIdSet) dmalloc (sizeof (*t)); | |
112 | int i; | |
113 | ||
114 | t->entries = s->entries; | |
115 | t->nspace = 1; | |
116 | t->elements = (usymId *) dmalloc (sizeof (*t->elements) * size); | |
117 | ||
118 | for (i = 0; i < s->entries; i++) | |
119 | { | |
120 | t->elements[i] = s->elements[i]; | |
121 | } | |
122 | ||
123 | return t; | |
124 | } | |
125 | ||
126 | usymIdSet | |
127 | usymIdSet_add (usymIdSet s, usymId el) | |
128 | { | |
129 | if (usymIdSet_isDefined (s)) | |
130 | { | |
131 | llassert (!usymIdSet_member (s, el)); | |
132 | ||
133 | return (usymIdSet_insert (usymIdSet_copy (s), el)); | |
134 | } | |
135 | else | |
136 | { | |
137 | return (usymIdSet_single (el)); | |
138 | } | |
139 | } | |
140 | ||
141 | usymIdSet | |
142 | usymIdSet_removeFresh (/*@temp@*/ usymIdSet s, usymId el) | |
143 | { | |
144 | if (usymIdSet_isDefined (s)) | |
145 | { | |
146 | usymIdSet t = usymIdSet_newEmpty (); | |
147 | int i; | |
148 | ||
149 | for (i = 0; i < s->entries; i++) | |
150 | { | |
151 | if (!usymId_equal (el, s->elements[i])) | |
152 | { | |
153 | t = usymIdSet_insert (t, s->elements[i]); | |
154 | } | |
155 | } | |
156 | ||
157 | return t; | |
158 | } | |
159 | else | |
160 | { | |
161 | return usymIdSet_undefined; | |
162 | } | |
163 | } | |
164 | ||
165 | usymIdSet | |
166 | usymIdSet_newUnion (usymIdSet s1, usymIdSet s2) | |
167 | { | |
168 | usymIdSet t = usymIdSet_new (); | |
169 | ||
170 | usymIdSet_elements (s1, current) | |
171 | { | |
172 | t = usymIdSet_insert (t, current); | |
173 | } end_usymIdSet_elements; | |
174 | ||
175 | usymIdSet_elements (s2, current) | |
176 | { | |
177 | t = usymIdSet_insert (t, current); | |
178 | } end_usymIdSet_elements; | |
179 | ||
180 | return t; | |
181 | } | |
182 | ||
183 | /* | |
184 | ** returns a new usymIdSet comprised of all elements | |
185 | ** in s which are not in t. | |
186 | */ | |
187 | ||
188 | usymIdSet | |
189 | usymIdSet_subtract (usymIdSet s, usymIdSet t) | |
190 | { | |
191 | usymIdSet r = usymIdSet_new (); | |
192 | ||
193 | usymIdSet_elements (s, current) | |
194 | { | |
195 | if (!usymIdSet_member (t, current)) | |
196 | { | |
197 | r = usymIdSet_insert (r, current); | |
198 | } | |
199 | } end_usymIdSet_elements; | |
200 | ||
201 | return r; | |
202 | } | |
203 | ||
204 | bool | |
205 | usymIdSet_member (usymIdSet s, usymId el) | |
206 | { | |
207 | if (usymIdSet_isUndefined (s)) | |
208 | { | |
209 | return FALSE; | |
210 | } | |
211 | else | |
212 | { | |
213 | int i; | |
214 | ||
215 | for (i = 0; i < s->entries; i++) | |
216 | { | |
217 | if (usymId_equal (el, s->elements[i])) | |
218 | return TRUE; | |
219 | } | |
220 | return FALSE; | |
221 | } | |
222 | } | |
223 | ||
224 | void | |
225 | usymIdSet_free (/*@only@*/ usymIdSet s) | |
226 | { | |
227 | if (!usymIdSet_isUndefined (s)) | |
228 | { | |
229 | int i; | |
230 | for (i = 0; i < s->entries; i++) | |
231 | { | |
232 | /* usymId_free (s->elements[i]); */ | |
233 | } | |
234 | ||
235 | sfree (s->elements); | |
236 | sfree (s); | |
237 | } | |
238 | } | |
239 | ||
240 | cstring usymIdSet_dump (usymIdSet lset) | |
241 | { | |
242 | cstring st = cstring_undefined; | |
243 | ||
244 | if (!usymIdSet_isUndefined (lset)) | |
245 | { | |
246 | bool first = TRUE; | |
247 | int i; | |
248 | ||
249 | for (i = 0; i < lset->entries; i++) | |
250 | { | |
251 | usymId current = lset->elements[i]; | |
252 | ||
253 | if (!usymId_isInvalid (current)) | |
254 | { | |
255 | current = usymtab_convertId (current); | |
256 | ||
257 | if (first) | |
258 | { | |
259 | st = message ("%d", current); | |
260 | first = FALSE; | |
261 | } | |
262 | else | |
263 | { | |
264 | st = message ("%q,%d", st, current); | |
265 | } | |
266 | } | |
267 | } | |
268 | } | |
269 | return (st); | |
270 | } | |
271 | ||
272 | /* | |
273 | ** end of list is '@' or '\0' | |
274 | */ | |
275 | ||
276 | usymIdSet | |
277 | usymIdSet_undump (char **s) | |
278 | { | |
279 | usymIdSet t = usymIdSet_new (); | |
280 | char *olds = *s; | |
281 | char c; | |
282 | ||
283 | ||
284 | while ((c = **s) != '\0' && c != '@' && c != '#' && c != '\n') | |
285 | { | |
286 | int tid = 0; | |
287 | ||
288 | while (c != '@' && c != '#' && c != ',' && c != '\0' && c != '\n') | |
289 | { | |
290 | while (c >= '0' && c <= '9') | |
291 | { | |
292 | tid *= 10; | |
293 | tid += (int) (c - '0'); | |
294 | (*s)++; | |
295 | c = **s; | |
296 | } | |
297 | ||
298 | if (*s == olds) | |
299 | { | |
300 | llcontbug (message ("usymIdSet_undump: loop: %s", | |
301 | cstring_fromChars (*s))); | |
302 | ||
303 | while (**s != '\0') | |
304 | { | |
305 | (*s)++; | |
306 | } | |
307 | ||
308 | /*@innerbreak@*/ break; | |
309 | } | |
310 | ||
311 | olds = *s; | |
312 | ||
313 | t = usymIdSet_insert (t, usymId_fromInt (tid)); | |
314 | } | |
315 | ||
316 | if (c == ',') | |
317 | { | |
318 | (*s)++; | |
319 | } | |
320 | } | |
321 | ||
322 | return t; | |
323 | } | |
324 | ||
325 | /*@only@*/ cstring | |
326 | usymIdSet_unparse (usymIdSet ll) | |
327 | { | |
328 | cstring s = cstring_undefined; | |
329 | ||
330 | if (!usymIdSet_isUndefined (ll)) | |
331 | { | |
332 | int i; | |
333 | ||
334 | for (i = 0; i < ll->entries; i++) | |
335 | { | |
336 | usymId current = ll->elements[i]; | |
337 | ||
338 | if (i == 0) | |
339 | s = uentry_getName (usymtab_getGlobalEntry (current)); | |
340 | else | |
341 | s = message ("%q, %q", s, uentry_getName (usymtab_getGlobalEntry (current))); | |
342 | } | |
343 | } | |
344 | ||
345 | return s; | |
346 | } | |
347 | ||
348 | int | |
349 | usymIdSet_compare (usymIdSet l1, usymIdSet l2) | |
350 | { | |
351 | if (usymIdSet_isUndefined (l1)) | |
352 | { | |
353 | return (usymIdSet_size (l2) == 0 ? 0 : 1); | |
354 | } | |
355 | ||
356 | if (usymIdSet_isUndefined (l2)) | |
357 | { | |
358 | return (usymIdSet_size (l1) == 0 ? 0 : 1); | |
359 | } | |
360 | ||
361 | { | |
362 | int li1 = l1->entries; | |
363 | int li2 = l2->entries; | |
364 | int leastelements = (li1 < li2) ? li1 : li2; | |
365 | int i = 0; | |
366 | ||
367 | while (i < leastelements) | |
368 | { | |
369 | if (usymId_equal (l1->elements[i], l2->elements[i])) | |
370 | { | |
371 | i++; | |
372 | } | |
373 | else | |
374 | { | |
375 | if (l1->elements[i] > l2->elements[i]) | |
376 | { | |
377 | return 1; | |
378 | } | |
379 | else | |
380 | { | |
381 | return -1; | |
382 | } | |
383 | } | |
384 | } | |
385 | ||
386 | return (int_compare (li1, li2)); | |
387 | } | |
388 | } |