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 #include "main/imports.h"
25 #include "symbol_table.h"
26 #include "../../util/hash_table.h"
27 #include "util/u_string.h"
28
29 struct symbol {
30 /** Symbol name. */
31 char *name;
32
33 /**
34 * Link to the next symbol in the table with the same name
35 *
36 * The linked list of symbols with the same name is ordered by scope
37 * from inner-most to outer-most.
38 */
39 struct symbol *next_with_same_name;
40
41 /**
42 * Link to the next symbol in the table with the same scope
43 *
44 * The linked list of symbols with the same scope is unordered. Symbols
45 * in this list my have unique names.
46 */
47 struct symbol *next_with_same_scope;
48
49 /** Scope depth where this symbol was defined. */
50 unsigned depth;
51
52 /**
53 * Arbitrary user supplied data.
54 */
55 void *data;
56 };
57
58
59 /**
60 * Element of the scope stack.
61 */
62 struct scope_level {
63 /** Link to next (inner) scope level. */
64 struct scope_level *next;
65
66 /** Linked list of symbols with the same scope. */
67 struct symbol *symbols;
68 };
69
70
71 /**
72 *
73 */
74 struct _mesa_symbol_table {
75 /** Hash table containing all symbols in the symbol table. */
76 struct hash_table *ht;
77
78 /** Top of scope stack. */
79 struct scope_level *current_scope;
80
81 /** Current scope depth. */
82 unsigned depth;
83 };
84
85 void
_mesa_symbol_table_pop_scope(struct _mesa_symbol_table * table)86 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
87 {
88 struct scope_level *const scope = table->current_scope;
89 struct symbol *sym = scope->symbols;
90
91 table->current_scope = scope->next;
92 table->depth--;
93
94 free(scope);
95
96 while (sym != NULL) {
97 struct symbol *const next = sym->next_with_same_scope;
98 struct hash_entry *hte = _mesa_hash_table_search(table->ht,
99 sym->name);
100 if (sym->next_with_same_name) {
101 /* If there is a symbol with this name in an outer scope update
102 * the hash table to point to it.
103 */
104 hte->key = sym->next_with_same_name->name;
105 hte->data = sym->next_with_same_name;
106 } else {
107 _mesa_hash_table_remove(table->ht, hte);
108 free(sym->name);
109 }
110
111 free(sym);
112 sym = next;
113 }
114 }
115
116
117 void
_mesa_symbol_table_push_scope(struct _mesa_symbol_table * table)118 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
119 {
120 struct scope_level *const scope = calloc(1, sizeof(*scope));
121 if (scope == NULL) {
122 _mesa_error_no_memory(__func__);
123 return;
124 }
125
126 scope->next = table->current_scope;
127 table->current_scope = scope;
128 table->depth++;
129 }
130
131
132 static struct symbol *
find_symbol(struct _mesa_symbol_table * table,const char * name)133 find_symbol(struct _mesa_symbol_table *table, const char *name)
134 {
135 struct hash_entry *entry = _mesa_hash_table_search(table->ht, name);
136 return entry ? (struct symbol *) entry->data : NULL;
137 }
138
139
140 /**
141 * Determine the scope "distance" of a symbol from the current scope
142 *
143 * \return
144 * A non-negative number for the number of scopes between the current scope
145 * and the scope where a symbol was defined. A value of zero means the current
146 * scope. A negative number if the symbol does not exist.
147 */
148 int
_mesa_symbol_table_symbol_scope(struct _mesa_symbol_table * table,const char * name)149 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
150 const char *name)
151 {
152 struct symbol *const sym = find_symbol(table, name);
153
154 if (sym) {
155 assert(sym->depth <= table->depth);
156 return sym->depth - table->depth;
157 }
158
159 return -1;
160 }
161
162
163 void *
_mesa_symbol_table_find_symbol(struct _mesa_symbol_table * table,const char * name)164 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
165 const char *name)
166 {
167 struct symbol *const sym = find_symbol(table, name);
168 if (sym)
169 return sym->data;
170
171 return NULL;
172 }
173
174
175 int
_mesa_symbol_table_add_symbol(struct _mesa_symbol_table * table,const char * name,void * declaration)176 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
177 const char *name, void *declaration)
178 {
179 struct symbol *new_sym;
180 struct symbol *sym = find_symbol(table, name);
181
182 if (sym && sym->depth == table->depth)
183 return -1;
184
185 new_sym = calloc(1, sizeof(*sym));
186 if (new_sym == NULL) {
187 _mesa_error_no_memory(__func__);
188 return -1;
189 }
190
191 if (sym) {
192 /* Store link to symbol in outer scope with the same name */
193 new_sym->next_with_same_name = sym;
194 new_sym->name = sym->name;
195 } else {
196 new_sym->name = util_strdup(name);
197 if (new_sym->name == NULL) {
198 free(new_sym);
199 _mesa_error_no_memory(__func__);
200 return -1;
201 }
202 }
203
204 new_sym->next_with_same_scope = table->current_scope->symbols;
205 new_sym->data = declaration;
206 new_sym->depth = table->depth;
207
208 table->current_scope->symbols = new_sym;
209
210 _mesa_hash_table_insert(table->ht, new_sym->name, new_sym);
211
212 return 0;
213 }
214
215 int
_mesa_symbol_table_replace_symbol(struct _mesa_symbol_table * table,const char * name,void * declaration)216 _mesa_symbol_table_replace_symbol(struct _mesa_symbol_table *table,
217 const char *name,
218 void *declaration)
219 {
220 struct symbol *sym = find_symbol(table, name);
221
222 /* If the symbol doesn't exist, it cannot be replaced. */
223 if (sym == NULL)
224 return -1;
225
226 sym->data = declaration;
227 return 0;
228 }
229
230 int
_mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table * table,const char * name,void * declaration)231 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
232 const char *name, void *declaration)
233 {
234 struct scope_level *top_scope;
235 struct symbol *inner_sym = NULL;
236 struct symbol *sym = find_symbol(table, name);
237
238 while (sym) {
239 if (sym->depth == 0)
240 return -1;
241
242 inner_sym = sym;
243
244 /* Get symbol from the outer scope with the same name */
245 sym = sym->next_with_same_name;
246 }
247
248 /* Find the top-level scope */
249 for (top_scope = table->current_scope; top_scope->next != NULL;
250 top_scope = top_scope->next) {
251 /* empty */
252 }
253
254 sym = calloc(1, sizeof(*sym));
255 if (sym == NULL) {
256 _mesa_error_no_memory(__func__);
257 return -1;
258 }
259
260 if (inner_sym) {
261 /* In case we add the global out of order store a link to the global
262 * symbol in global.
263 */
264 inner_sym->next_with_same_name = sym;
265
266 sym->name = inner_sym->name;
267 } else {
268 sym->name = util_strdup(name);
269 if (sym->name == NULL) {
270 free(sym);
271 _mesa_error_no_memory(__func__);
272 return -1;
273 }
274 }
275
276 sym->next_with_same_scope = top_scope->symbols;
277 sym->data = declaration;
278
279 top_scope->symbols = sym;
280
281 _mesa_hash_table_insert(table->ht, sym->name, sym);
282
283 return 0;
284 }
285
286
287
288 struct _mesa_symbol_table *
_mesa_symbol_table_ctor(void)289 _mesa_symbol_table_ctor(void)
290 {
291 struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
292
293 if (table != NULL) {
294 table->ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string,
295 _mesa_key_string_equal);
296
297 _mesa_symbol_table_push_scope(table);
298 }
299
300 return table;
301 }
302
303
304 void
_mesa_symbol_table_dtor(struct _mesa_symbol_table * table)305 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
306 {
307 while (table->current_scope != NULL) {
308 _mesa_symbol_table_pop_scope(table);
309 }
310
311 _mesa_hash_table_destroy(table->ht, NULL);
312 free(table);
313 }
314