1 /*
2 * Copyright © 2008 Intel Corporation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
22 */
23
24
25 #include "main/errors.h"
26 #include "symbol_table.h"
27 #include "util/hash_table.h"
28 #include "util/u_string.h"
29
30 struct symbol {
31 /** Symbol name. */
32 char *name;
33
34 /**
35 * Link to the next symbol in the table with the same name
36 *
37 * The linked list of symbols with the same name is ordered by scope
38 * from inner-most to outer-most.
39 */
40 struct symbol *next_with_same_name;
41
42 /**
43 * Link to the next symbol in the table with the same scope
44 *
45 * The linked list of symbols with the same scope is unordered. Symbols
46 * in this list my have unique names.
47 */
48 struct symbol *next_with_same_scope;
49
50 /** Scope depth where this symbol was defined. */
51 unsigned depth;
52
53 /**
54 * Arbitrary user supplied data.
55 */
56 void *data;
57 };
58
59
60 /**
61 * Element of the scope stack.
62 */
63 struct scope_level {
64 /** Link to next (inner) scope level. */
65 struct scope_level *next;
66
67 /** Linked list of symbols with the same scope. */
68 struct symbol *symbols;
69 };
70
71
72 /**
73 *
74 */
75 struct _mesa_symbol_table {
76 /** Hash table containing all symbols in the symbol table. */
77 struct hash_table *ht;
78
79 /** Top of scope stack. */
80 struct scope_level *current_scope;
81
82 /** Current scope depth. */
83 unsigned depth;
84 };
85
86 void
_mesa_symbol_table_pop_scope(struct _mesa_symbol_table * table)87 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
88 {
89 struct scope_level *const scope = table->current_scope;
90 struct symbol *sym = scope->symbols;
91
92 table->current_scope = scope->next;
93 table->depth--;
94
95 free(scope);
96
97 while (sym != NULL) {
98 struct symbol *const next = sym->next_with_same_scope;
99 struct hash_entry *hte = _mesa_hash_table_search(table->ht,
100 sym->name);
101 if (sym->next_with_same_name) {
102 /* If there is a symbol with this name in an outer scope update
103 * the hash table to point to it.
104 */
105 hte->key = sym->next_with_same_name->name;
106 hte->data = sym->next_with_same_name;
107 } else {
108 _mesa_hash_table_remove(table->ht, hte);
109 free(sym->name);
110 }
111
112 free(sym);
113 sym = next;
114 }
115 }
116
117
118 void
_mesa_symbol_table_push_scope(struct _mesa_symbol_table * table)119 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
120 {
121 struct scope_level *const scope = calloc(1, sizeof(*scope));
122 if (scope == NULL) {
123 _mesa_error_no_memory(__func__);
124 return;
125 }
126
127 scope->next = table->current_scope;
128 table->current_scope = scope;
129 table->depth++;
130 }
131
132
133 static struct symbol *
find_symbol(struct _mesa_symbol_table * table,const char * name)134 find_symbol(struct _mesa_symbol_table *table, const char *name)
135 {
136 struct hash_entry *entry = _mesa_hash_table_search(table->ht, name);
137 return entry ? (struct symbol *) entry->data : NULL;
138 }
139
140
141 /**
142 * Determine the scope "distance" of a symbol from the current scope
143 *
144 * \return
145 * A non-negative number for the number of scopes between the current scope
146 * and the scope where a symbol was defined. A value of zero means the current
147 * scope. A negative number if the symbol does not exist.
148 */
149 int
_mesa_symbol_table_symbol_scope(struct _mesa_symbol_table * table,const char * name)150 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
151 const char *name)
152 {
153 struct symbol *const sym = find_symbol(table, name);
154
155 if (sym) {
156 assert(sym->depth <= table->depth);
157 return table->depth - sym->depth;
158 }
159
160 return -1;
161 }
162
163
164 void *
_mesa_symbol_table_find_symbol(struct _mesa_symbol_table * table,const char * name)165 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
166 const char *name)
167 {
168 struct symbol *const sym = find_symbol(table, name);
169 if (sym)
170 return sym->data;
171
172 return NULL;
173 }
174
175
176 int
_mesa_symbol_table_add_symbol(struct _mesa_symbol_table * table,const char * name,void * declaration)177 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
178 const char *name, void *declaration)
179 {
180 struct symbol *new_sym;
181 struct symbol *sym = find_symbol(table, name);
182
183 if (sym && sym->depth == table->depth)
184 return -1;
185
186 new_sym = calloc(1, sizeof(*sym));
187 if (new_sym == NULL) {
188 _mesa_error_no_memory(__func__);
189 return -1;
190 }
191
192 if (sym) {
193 /* Store link to symbol in outer scope with the same name */
194 new_sym->next_with_same_name = sym;
195 new_sym->name = sym->name;
196 } else {
197 new_sym->name = strdup(name);
198 if (new_sym->name == NULL) {
199 free(new_sym);
200 _mesa_error_no_memory(__func__);
201 return -1;
202 }
203 }
204
205 new_sym->next_with_same_scope = table->current_scope->symbols;
206 new_sym->data = declaration;
207 new_sym->depth = table->depth;
208
209 table->current_scope->symbols = new_sym;
210
211 _mesa_hash_table_insert(table->ht, new_sym->name, new_sym);
212
213 return 0;
214 }
215
216 int
_mesa_symbol_table_replace_symbol(struct _mesa_symbol_table * table,const char * name,void * declaration)217 _mesa_symbol_table_replace_symbol(struct _mesa_symbol_table *table,
218 const char *name,
219 void *declaration)
220 {
221 struct symbol *sym = find_symbol(table, name);
222
223 /* If the symbol doesn't exist, it cannot be replaced. */
224 if (sym == NULL)
225 return -1;
226
227 sym->data = declaration;
228 return 0;
229 }
230
231 int
_mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table * table,const char * name,void * declaration)232 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
233 const char *name, void *declaration)
234 {
235 struct scope_level *top_scope;
236 struct symbol *inner_sym = NULL;
237 struct symbol *sym = find_symbol(table, name);
238
239 while (sym) {
240 if (sym->depth == 0)
241 return -1;
242
243 inner_sym = sym;
244
245 /* Get symbol from the outer scope with the same name */
246 sym = sym->next_with_same_name;
247 }
248
249 /* Find the top-level scope */
250 for (top_scope = table->current_scope; top_scope->next != NULL;
251 top_scope = top_scope->next) {
252 /* empty */
253 }
254
255 sym = calloc(1, sizeof(*sym));
256 if (sym == NULL) {
257 _mesa_error_no_memory(__func__);
258 return -1;
259 }
260
261 if (inner_sym) {
262 /* In case we add the global out of order store a link to the global
263 * symbol in global.
264 */
265 inner_sym->next_with_same_name = sym;
266
267 sym->name = inner_sym->name;
268 } else {
269 sym->name = strdup(name);
270 if (sym->name == NULL) {
271 free(sym);
272 _mesa_error_no_memory(__func__);
273 return -1;
274 }
275 }
276
277 sym->next_with_same_scope = top_scope->symbols;
278 sym->data = declaration;
279
280 top_scope->symbols = sym;
281
282 _mesa_hash_table_insert(table->ht, sym->name, sym);
283
284 return 0;
285 }
286
287
288
289 struct _mesa_symbol_table *
_mesa_symbol_table_ctor(void)290 _mesa_symbol_table_ctor(void)
291 {
292 struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
293
294 if (table != NULL) {
295 table->ht = _mesa_hash_table_create(NULL, _mesa_hash_string,
296 _mesa_key_string_equal);
297
298 _mesa_symbol_table_push_scope(table);
299 }
300
301 return table;
302 }
303
304
305 void
_mesa_symbol_table_dtor(struct _mesa_symbol_table * table)306 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
307 {
308 while (table->current_scope != NULL) {
309 _mesa_symbol_table_pop_scope(table);
310 }
311
312 _mesa_hash_table_destroy(table->ht, NULL);
313 free(table);
314 }
315