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 "hash_table.h"
30 * Link to the next symbol in the table with the same name
32 * The linked list of symbols with the same name is ordered by scope
33 * from inner-most to outer-most.
35 struct symbol
*next_with_same_name
;
39 * Link to the next symbol in the table with the same scope
41 * The linked list of symbols with the same scope is unordered. Symbols
42 * in this list my have unique names.
44 struct symbol
*next_with_same_scope
;
48 * Header information for the list of symbols with the same name.
50 struct symbol_header
*hdr
;
54 * Name space of the symbol
56 * Name space are arbitrary user assigned integers. No two symbols can
57 * exist in the same name space at the same scope level.
61 /** Scope depth where this symbol was defined. */
65 * Arbitrary user supplied data.
73 struct symbol_header
{
74 /** Linkage in list of all headers in a given symbol table. */
75 struct symbol_header
*next
;
80 /** Linked list of symbols with the same name. */
81 struct symbol
*symbols
;
86 * Element of the scope stack.
89 /** Link to next (inner) scope level. */
90 struct scope_level
*next
;
92 /** Linked list of symbols with the same scope. */
93 struct symbol
*symbols
;
100 struct _mesa_symbol_table
{
101 /** Hash table containing all symbols in the symbol table. */
102 struct hash_table
*ht
;
104 /** Top of scope stack. */
105 struct scope_level
*current_scope
;
107 /** List of all symbol headers in the table. */
108 struct symbol_header
*hdr
;
110 /** Current scope depth. */
116 check_symbol_table(struct _mesa_symbol_table
*table
)
119 struct scope_level
*scope
;
121 for (scope
= table
->current_scope
; scope
!= NULL
; scope
= scope
->next
) {
124 for (sym
= scope
->symbols
126 ; sym
= sym
->next_with_same_name
) {
127 const struct symbol_header
*const hdr
= sym
->hdr
;
130 for (sym2
= hdr
->symbols
132 ; sym2
= sym2
->next_with_same_name
) {
133 assert(sym2
->hdr
== hdr
);
139 #endif /* !defined(NDEBUG) */
143 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table
*table
)
145 struct scope_level
*const scope
= table
->current_scope
;
146 struct symbol
*sym
= scope
->symbols
;
148 table
->current_scope
= scope
->next
;
153 while (sym
!= NULL
) {
154 struct symbol
*const next
= sym
->next_with_same_scope
;
155 struct symbol_header
*const hdr
= sym
->hdr
;
157 assert(hdr
->symbols
== sym
);
159 hdr
->symbols
= sym
->next_with_same_name
;
166 check_symbol_table(table
);
171 _mesa_symbol_table_push_scope(struct _mesa_symbol_table
*table
)
173 struct scope_level
*const scope
= calloc(1, sizeof(*scope
));
175 scope
->next
= table
->current_scope
;
176 table
->current_scope
= scope
;
181 static struct symbol_header
*
182 find_symbol(struct _mesa_symbol_table
*table
, const char *name
)
184 return (struct symbol_header
*) hash_table_find(table
->ht
, name
);
189 * Determine the scope "distance" of a symbol from the current scope
192 * A non-negative number for the number of scopes between the current scope
193 * and the scope where a symbol was defined. A value of zero means the current
194 * scope. A negative number if the symbol does not exist.
197 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table
*table
,
198 int name_space
, const char *name
)
200 struct symbol_header
*const hdr
= find_symbol(table
, name
);
204 for (sym
= hdr
->symbols
; sym
!= NULL
; sym
= sym
->next_with_same_name
) {
205 assert(sym
->hdr
== hdr
);
207 if ((name_space
== -1) || (sym
->name_space
== name_space
)) {
208 assert(sym
->depth
<= table
->depth
);
209 return sym
->depth
- table
->depth
;
219 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table
*table
,
220 int name_space
, const char *name
)
222 struct symbol_header
*const hdr
= find_symbol(table
, name
);
228 for (sym
= hdr
->symbols
; sym
!= NULL
; sym
= sym
->next_with_same_name
) {
229 assert(sym
->hdr
== hdr
);
231 if ((name_space
== -1) || (sym
->name_space
== name_space
)) {
242 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table
*table
,
243 int name_space
, const char *name
,
246 struct symbol_header
*hdr
;
249 check_symbol_table(table
);
251 hdr
= find_symbol(table
, name
);
253 check_symbol_table(table
);
256 hdr
= calloc(1, sizeof(*hdr
));
257 hdr
->name
= strdup(name
);
259 hash_table_insert(table
->ht
, hdr
, hdr
->name
);
260 hdr
->next
= table
->hdr
;
264 check_symbol_table(table
);
266 /* If the symbol already exists in this namespace at this scope, it cannot
267 * be added to the table.
269 for (sym
= hdr
->symbols
270 ; (sym
!= NULL
) && (sym
->name_space
!= name_space
)
271 ; sym
= sym
->next_with_same_name
) {
275 if (sym
&& (sym
->depth
== table
->depth
))
278 sym
= calloc(1, sizeof(*sym
));
279 sym
->next_with_same_name
= hdr
->symbols
;
280 sym
->next_with_same_scope
= table
->current_scope
->symbols
;
282 sym
->name_space
= name_space
;
283 sym
->data
= declaration
;
284 sym
->depth
= table
->depth
;
286 assert(sym
->hdr
== hdr
);
289 table
->current_scope
->symbols
= sym
;
291 check_symbol_table(table
);
297 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table
*table
,
298 int name_space
, const char *name
,
301 struct symbol_header
*hdr
;
304 struct scope_level
*top_scope
;
306 check_symbol_table(table
);
308 hdr
= find_symbol(table
, name
);
310 check_symbol_table(table
);
313 hdr
= calloc(1, sizeof(*hdr
));
314 hdr
->name
= strdup(name
);
316 hash_table_insert(table
->ht
, hdr
, hdr
->name
);
317 hdr
->next
= table
->hdr
;
321 check_symbol_table(table
);
323 /* If the symbol already exists in this namespace at this scope, it cannot
324 * be added to the table.
326 for (sym
= hdr
->symbols
327 ; (sym
!= NULL
) && (sym
->name_space
!= name_space
)
328 ; sym
= sym
->next_with_same_name
) {
332 if (sym
&& sym
->depth
== 0)
335 /* Find the top-level scope */
336 for (top_scope
= table
->current_scope
337 ; top_scope
->next
!= NULL
338 ; top_scope
= top_scope
->next
) {
342 sym
= calloc(1, sizeof(*sym
));
343 sym
->next_with_same_scope
= top_scope
->symbols
;
345 sym
->name_space
= name_space
;
346 sym
->data
= declaration
;
348 assert(sym
->hdr
== hdr
);
350 /* Since next_with_same_name is ordered by scope, we need to append the
351 * new symbol to the _end_ of the list.
353 if (hdr
->symbols
== NULL
) {
356 for (curr
= hdr
->symbols
357 ; curr
->next_with_same_name
!= NULL
358 ; curr
= curr
->next_with_same_name
) {
361 curr
->next_with_same_name
= sym
;
363 top_scope
->symbols
= sym
;
365 check_symbol_table(table
);
371 struct _mesa_symbol_table
*
372 _mesa_symbol_table_ctor(void)
374 struct _mesa_symbol_table
*table
= calloc(1, sizeof(*table
));
377 table
->ht
= hash_table_ctor(32, hash_table_string_hash
,
378 hash_table_string_compare
);
380 _mesa_symbol_table_push_scope(table
);
388 _mesa_symbol_table_dtor(struct _mesa_symbol_table
*table
)
390 struct symbol_header
*hdr
;
391 struct symbol_header
*next
;
393 while (table
->current_scope
!= NULL
) {
394 _mesa_symbol_table_pop_scope(table
);
397 for (hdr
= table
->hdr
; hdr
!= NULL
; hdr
= next
) {
403 hash_table_dtor(table
->ht
);