2 * Copyright © 2008 Intel Corporation
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:
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
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.
24 #include "main/imports.h"
25 #include "symbol_table.h"
26 #include "../../util/hash_table.h"
33 * Link to the next symbol in the table with the same name
35 * The linked list of symbols with the same name is ordered by scope
36 * from inner-most to outer-most.
38 struct symbol
*next_with_same_name
;
41 * Link to the next symbol in the table with the same scope
43 * The linked list of symbols with the same scope is unordered. Symbols
44 * in this list my have unique names.
46 struct symbol
*next_with_same_scope
;
48 /** Scope depth where this symbol was defined. */
52 * Arbitrary user supplied data.
59 * Element of the scope stack.
62 /** Link to next (inner) scope level. */
63 struct scope_level
*next
;
65 /** Linked list of symbols with the same scope. */
66 struct symbol
*symbols
;
73 struct _mesa_symbol_table
{
74 /** Hash table containing all symbols in the symbol table. */
75 struct hash_table
*ht
;
77 /** Top of scope stack. */
78 struct scope_level
*current_scope
;
80 /** Current scope depth. */
85 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table
*table
)
87 struct scope_level
*const scope
= table
->current_scope
;
88 struct symbol
*sym
= scope
->symbols
;
90 table
->current_scope
= scope
->next
;
96 struct symbol
*const next
= sym
->next_with_same_scope
;
97 struct hash_entry
*hte
= _mesa_hash_table_search(table
->ht
,
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.
103 hte
->key
= sym
->next_with_same_name
->name
;
104 hte
->data
= sym
->next_with_same_name
;
106 _mesa_hash_table_remove(table
->ht
, hte
);
117 _mesa_symbol_table_push_scope(struct _mesa_symbol_table
*table
)
119 struct scope_level
*const scope
= calloc(1, sizeof(*scope
));
121 _mesa_error_no_memory(__func__
);
125 scope
->next
= table
->current_scope
;
126 table
->current_scope
= scope
;
131 static struct symbol
*
132 find_symbol(struct _mesa_symbol_table
*table
, const char *name
)
134 struct hash_entry
*entry
= _mesa_hash_table_search(table
->ht
, name
);
135 return entry
? (struct symbol
*) entry
->data
: NULL
;
140 * Determine the scope "distance" of a symbol from the current scope
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.
148 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table
*table
,
151 struct symbol
*const sym
= find_symbol(table
, name
);
154 assert(sym
->depth
<= table
->depth
);
155 return sym
->depth
- table
->depth
;
163 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table
*table
,
166 struct symbol
*const sym
= find_symbol(table
, name
);
175 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table
*table
,
176 const char *name
, void *declaration
)
178 struct symbol
*new_sym
;
179 struct symbol
*sym
= find_symbol(table
, name
);
181 if (sym
&& sym
->depth
== table
->depth
)
184 new_sym
= calloc(1, sizeof(*sym
));
185 if (new_sym
== NULL
) {
186 _mesa_error_no_memory(__func__
);
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
;
195 new_sym
->name
= strdup(name
);
196 if (new_sym
->name
== NULL
) {
198 _mesa_error_no_memory(__func__
);
203 new_sym
->next_with_same_scope
= table
->current_scope
->symbols
;
204 new_sym
->data
= declaration
;
205 new_sym
->depth
= table
->depth
;
207 table
->current_scope
->symbols
= new_sym
;
209 _mesa_hash_table_insert(table
->ht
, new_sym
->name
, new_sym
);
215 _mesa_symbol_table_replace_symbol(struct _mesa_symbol_table
*table
,
219 struct symbol
*sym
= find_symbol(table
, name
);
221 /* If the symbol doesn't exist, it cannot be replaced. */
225 sym
->data
= declaration
;
230 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table
*table
,
231 const char *name
, void *declaration
)
233 struct scope_level
*top_scope
;
234 struct symbol
*inner_sym
= NULL
;
235 struct symbol
*sym
= find_symbol(table
, name
);
243 /* Get symbol from the outer scope with the same name */
244 sym
= sym
->next_with_same_name
;
247 /* Find the top-level scope */
248 for (top_scope
= table
->current_scope
; top_scope
->next
!= NULL
;
249 top_scope
= top_scope
->next
) {
253 sym
= calloc(1, sizeof(*sym
));
255 _mesa_error_no_memory(__func__
);
260 /* In case we add the global out of order store a link to the global
263 inner_sym
->next_with_same_name
= sym
;
265 sym
->name
= inner_sym
->name
;
267 sym
->name
= strdup(name
);
268 if (sym
->name
== NULL
) {
270 _mesa_error_no_memory(__func__
);
275 sym
->next_with_same_scope
= top_scope
->symbols
;
276 sym
->data
= declaration
;
278 top_scope
->symbols
= sym
;
280 _mesa_hash_table_insert(table
->ht
, sym
->name
, sym
);
287 struct _mesa_symbol_table
*
288 _mesa_symbol_table_ctor(void)
290 struct _mesa_symbol_table
*table
= calloc(1, sizeof(*table
));
293 table
->ht
= _mesa_hash_table_create(NULL
, _mesa_key_hash_string
,
294 _mesa_key_string_equal
);
296 _mesa_symbol_table_push_scope(table
);
304 _mesa_symbol_table_dtor(struct _mesa_symbol_table
*table
)
306 while (table
->current_scope
!= NULL
) {
307 _mesa_symbol_table_pop_scope(table
);
310 _mesa_hash_table_destroy(table
->ht
, NULL
);