1 /***********************************************************************
2 * symbol.c - a symbol is an object with a name, a value and a
3 * reference count
4 ***********************************************************************
5 *
6 * Copyright (c) 1995-2002 Silicon Graphics, Inc. All Rights Reserved.
7 *
8 * This program is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2 of the License, or (at your
11 * option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 * for more details.
17 *
18 * You should have received a copy of the GNU General Public License along
19 * with this program; if not, write to the Free Software Foundation, Inc.,
20 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 */
22
23 #include <stdlib.h>
24 #include <string.h>
25 #include "symbol.h"
26 #include "dstruct.h"
27 #include "pmapi.h"
28
29
30 /***********************************************************************
31 * constants
32 ***********************************************************************/
33
34 /* bucket memory alignment, address mask and size */
35 #undef ALIGN
36 #define ALIGN 1024
37 #undef MASK
38 #define MASK (ALIGN - 1)
39 #undef BSIZE
40 #define BSIZE (ALIGN / sizeof(SymUnion))
41
42
43
44 /***********************************************************************
45 * types
46 ***********************************************************************/
47
48 typedef SymUnion Bucket[BSIZE];
49
50
51
52 /***********************************************************************
53 * local functions
54 ***********************************************************************/
55
56 static void
57 addBucket(SymUnion *st)
58 {
59 SymUnion *bckt = (SymUnion *) aalloc(ALIGN, sizeof(Bucket));
60 SymUnion *scoop = bckt + 1;
61
62 bckt->hdr.prev = st;
63 bckt->hdr.next = st->hdr.next;
64 bckt->hdr.free = scoop;
65 st->hdr.next->hdr.prev = bckt;
66 st->hdr.next = bckt;
67 scoop->entry.refs = 0;
68 scoop->entry.stat.free.ptr = NULL;
69 scoop->entry.stat.free.count = BSIZE - 1;
70 }
71
72 static void
73 remBucket(SymUnion *bckt)
74 {
75 SymUnion *prev = bckt->hdr.prev;
76 SymUnion *next = bckt->hdr.next;
77 SymUnion *scan;
78 int i = 1;
79
80 prev->hdr.next = next;
81 next->hdr.prev = prev;
82 while (i < BSIZE) {
83 scan = bckt + i;
84 if (scan->entry.refs == 0)
85 i += scan->entry.stat.free.count;
86 else {
87 free(scan->entry.stat.used.name);
88 i++;
89 }
90 }
91 free(bckt);
92 }
93
94
95
96 /***********************************************************************
97 * exported functions
98 ***********************************************************************/
99
100 /* initialize symbol table */
101 void
102 symSetTable(SymbolTable *st)
103 {
104 /* start with one clean bucket */
105 st->hdr.next = st;
106 st->hdr.prev = st;
107 addBucket(st);
108 }
109
110
111 /* reset symbol table */
112 void
113 symClearTable(SymbolTable *st)
114 {
115 /* unchain all buckets and free storage */
116 while (st->hdr.next != st)
117 remBucket(st->hdr.next);
118 /* start with one clean bucket */
119 addBucket(st);
120 }
121
122
123 /* Convert string to symbol. A copy of the name string is made
124 on the heap for use by the symbol. */
125 Symbol
126 symIntern(SymbolTable *st, char *name)
127 {
128 SymUnion *bckt;
129 SymUnion *scoop = NULL;
130 char *copy;
131 int i;
132
133 /* pick up existing symbol */
134 bckt = st->hdr.next;
135 while (bckt != st) {
136 i = 1;
137 while (i < BSIZE) {
138 scoop = bckt + i;
139 if (scoop->entry.refs) {
140 if (strcmp(name, scoop->entry.stat.used.name) == 0) {
141 scoop->entry.refs++;
142 return scoop;
143 }
144 i++;
145 }
146 else
147 i += scoop->entry.stat.free.count;
148 }
149 bckt = bckt->hdr.next;
150 }
151
152 /* pick up free entry */
153 bckt = st->hdr.next;
154 while (bckt != st) {
155 if ((scoop = bckt->hdr.free)) {
156 if (scoop->entry.stat.free.count > 1)
157 scoop += --scoop->entry.stat.free.count;
158 else
159 bckt->hdr.free = scoop->entry.stat.free.ptr;
160 break;
161 }
162 bckt = bckt->hdr.next;
163 }
164
165 /* no free entry - allocate new bucket */
166 if (scoop == NULL) {
167 addBucket(st);
168 scoop = st->hdr.next + 1;
169 scoop += --scoop->entry.stat.free.count;
170 }
171
172 /* initialize symbol */
173 scoop->entry.refs = 1;
174 copy = (char *) alloc(strlen(name) + 1);
175 strcpy(copy, name);
176 scoop->entry.stat.used.name = copy;
177 scoop->entry.stat.used.value = NULL;
178 return scoop;
179 }
180
181
182 /* lookup symbol by name */
183 Symbol
184 symLookup(SymbolTable *st, char *name)
185 {
186 SymUnion *bckt;
187 SymUnion *scoop;
188 int i;
189
190 bckt = st->hdr.next;
191 while (bckt != st) {
192 i = 1;
193 while (i < BSIZE) {
194 scoop = bckt + i;
195 if (scoop->entry.refs) {
196 if (strcmp(name, scoop->entry.stat.used.name) == 0) {
197 scoop->entry.refs++;
198 return scoop;
199 }
200 i++;
201 }
202 else
203 i += scoop->entry.stat.free.count;
204 }
205 bckt = bckt->hdr.next;
206 }
207 return NULL;
208 }
209
210
211 /* copy symbol */
212 Symbol
213 symCopy(Symbol sym)
214 {
215 sym->entry.refs++;
216 return sym;
217 }
218
219
220 /* remove reference to symbol */
221 void
222 symFree(Symbol sym)
223 {
224 SymUnion *bckt;
225 SymUnion *lead, *lag;
226
227 if ((sym != SYM_NULL) && (--sym->entry.refs <= 0)) {
228
229 /* free up name string BUT NOT value */
230 free(sym->entry.stat.used.name);
231
232 /* find correct place in ordered free list */
233 bckt = (SymUnion *) ((char *) sym - ((long) sym & MASK));
234 lead = bckt->hdr.free;
235 lag = NULL;
236 while ((lead != NULL) && (lead < sym)) {
237 lag = lead;
238 lead = lead->entry.stat.free.ptr;
239 }
240
241 /* coalesce with preceding free block */
|
Event deref_ptr: |
Directly dereferencing pointer "lag". |
| Also see events: |
[check_after_deref] |
242 if (lag + lag->entry.stat.free.count == sym) {
243 lag->entry.stat.free.count++;
244 sym = lag;
245 }
246
247 /* link up as single free entry */
248 else {
|
Event check_after_deref: |
Dereferencing "lag" before a null check. |
| Also see events: |
[deref_ptr] |
249 if (lag)
250 lag->entry.stat.free.ptr = sym;
251 else
252 bckt->hdr.free = sym;
253 sym->entry.stat.free.count = 1;
254 sym->entry.stat.free.ptr = lead;
255 }
256
257 /* coalesce with following free block */
258 if (sym + sym->entry.stat.free.count == lead) {
259 sym->entry.stat.free.count += lead->entry.stat.free.count;
260 sym->entry.stat.free.ptr = lead->entry.stat.free.ptr;
261 }
262 }
263 }
264
265