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.
25 #include "main/errors.h"
26 #include "symbol_table.h"
27 #include "util/hash_table.h"
28 #include "util/u_string.h"
35 * Link to the next symbol in the table with the same name
37 * The linked list of symbols with the same name is ordered by scope
38 * from inner-most to outer-most.
40 struct symbol
*next_with_same_name
;
43 * Link to the next symbol in the table with the same scope
45 * The linked list of symbols with the same scope is unordered. Symbols
46 * in this list my have unique names.
48 struct symbol
*next_with_same_scope
;
50 /** Scope depth where this symbol was defined. */
54 * Arbitrary user supplied data.
61 * Element of the scope stack.
64 /** Link to next (inner) scope level. */
65 struct scope_level
*next
;
67 /** Linked list of symbols with the same scope. */
68 struct symbol
*symbols
;
75 struct _mesa_symbol_table
{
76 /** Hash table containing all symbols in the symbol table. */
77 struct hash_table
*ht
;
79 /** Top of scope stack. */
80 struct scope_level
*current_scope
;
82 /** Current scope depth. */
87 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table
*table
)
89 struct scope_level
*const scope
= table
->current_scope
;
90 struct symbol
*sym
= scope
->symbols
;
92 table
->current_scope
= scope
->next
;
98 struct symbol
*const next
= sym
->next_with_same_scope
;
99 struct hash_entry
*hte
= _mesa_hash_table_search(table
->ht
,
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.
105 hte
->key
= sym
->next_with_same_name
->name
;
106 hte
->data
= sym
->next_with_same_name
;
108 _mesa_hash_table_remove(table
->ht
, hte
);
119 _mesa_symbol_table_push_scope(struct _mesa_symbol_table
*table
)
121 struct scope_level
*const scope
= calloc(1, sizeof(*scope
));
123 _mesa_error_no_memory(__func__
);
127 scope
->next
= table
->current_scope
;
128 table
->current_scope
= scope
;
133 static struct symbol
*
134 find_symbol(struct _mesa_symbol_table
*table
, const char *name
)
136 struct hash_entry
*entry
= _mesa_hash_table_search(table
->ht
, name
);
137 return entry
? (struct symbol
*) entry
->data
: NULL
;
142 * Determine the scope "distance" of a symbol from the current scope
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.
150 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table
*table
,
153 struct symbol
*const sym
= find_symbol(table
, name
);
156 assert(sym
->depth
<= table
->depth
);
157 return sym
->depth
- table
->depth
;
165 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table
*table
,
168 struct symbol
*const sym
= find_symbol(table
, name
);
177 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table
*table
,
178 const char *name
, void *declaration
)
180 struct symbol
*new_sym
;
181 struct symbol
*sym
= find_symbol(table
, name
);
183 if (sym
&& sym
->depth
== table
->depth
)
186 new_sym
= calloc(1, sizeof(*sym
));
187 if (new_sym
== NULL
) {
188 _mesa_error_no_memory(__func__
);
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
;
197 new_sym
->name
= strdup(name
);
198 if (new_sym
->name
== NULL
) {
200 _mesa_error_no_memory(__func__
);
205 new_sym
->next_with_same_scope
= table
->current_scope
->symbols
;
206 new_sym
->data
= declaration
;
207 new_sym
->depth
= table
->depth
;
209 table
->current_scope
->symbols
= new_sym
;
211 _mesa_hash_table_insert(table
->ht
, new_sym
->name
, new_sym
);
217 _mesa_symbol_table_replace_symbol(struct _mesa_symbol_table
*table
,
221 struct symbol
*sym
= find_symbol(table
, name
);
223 /* If the symbol doesn't exist, it cannot be replaced. */
227 sym
->data
= declaration
;
232 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table
*table
,
233 const char *name
, void *declaration
)
235 struct scope_level
*top_scope
;
236 struct symbol
*inner_sym
= NULL
;
237 struct symbol
*sym
= find_symbol(table
, name
);
245 /* Get symbol from the outer scope with the same name */
246 sym
= sym
->next_with_same_name
;
249 /* Find the top-level scope */
250 for (top_scope
= table
->current_scope
; top_scope
->next
!= NULL
;
251 top_scope
= top_scope
->next
) {
255 sym
= calloc(1, sizeof(*sym
));
257 _mesa_error_no_memory(__func__
);
262 /* In case we add the global out of order store a link to the global
265 inner_sym
->next_with_same_name
= sym
;
267 sym
->name
= inner_sym
->name
;
269 sym
->name
= strdup(name
);
270 if (sym
->name
== NULL
) {
272 _mesa_error_no_memory(__func__
);
277 sym
->next_with_same_scope
= top_scope
->symbols
;
278 sym
->data
= declaration
;
280 top_scope
->symbols
= sym
;
282 _mesa_hash_table_insert(table
->ht
, sym
->name
, sym
);
289 struct _mesa_symbol_table
*
290 _mesa_symbol_table_ctor(void)
292 struct _mesa_symbol_table
*table
= calloc(1, sizeof(*table
));
295 table
->ht
= _mesa_hash_table_create(NULL
, _mesa_hash_string
,
296 _mesa_key_string_equal
);
298 _mesa_symbol_table_push_scope(table
);
306 _mesa_symbol_table_dtor(struct _mesa_symbol_table
*table
)
308 while (table
->current_scope
!= NULL
) {
309 _mesa_symbol_table_pop_scope(table
);
312 _mesa_hash_table_destroy(table
->ht
, NULL
);