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