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
));
176 _mesa_error_no_memory(__func__
);
180 scope
->next
= table
->current_scope
;
181 table
->current_scope
= scope
;
186 static struct symbol_header
*
187 find_symbol(struct _mesa_symbol_table
*table
, const char *name
)
189 return (struct symbol_header
*) hash_table_find(table
->ht
, name
);
194 * Determine the scope "distance" of a symbol from the current scope
197 * A non-negative number for the number of scopes between the current scope
198 * and the scope where a symbol was defined. A value of zero means the current
199 * scope. A negative number if the symbol does not exist.
202 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table
*table
,
203 int name_space
, const char *name
)
205 struct symbol_header
*const hdr
= find_symbol(table
, name
);
209 for (sym
= hdr
->symbols
; sym
!= NULL
; sym
= sym
->next_with_same_name
) {
210 assert(sym
->hdr
== hdr
);
212 if ((name_space
== -1) || (sym
->name_space
== name_space
)) {
213 assert(sym
->depth
<= table
->depth
);
214 return sym
->depth
- table
->depth
;
224 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table
*table
,
225 int name_space
, const char *name
)
227 struct symbol_header
*const hdr
= find_symbol(table
, name
);
233 for (sym
= hdr
->symbols
; sym
!= NULL
; sym
= sym
->next_with_same_name
) {
234 assert(sym
->hdr
== hdr
);
236 if ((name_space
== -1) || (sym
->name_space
== name_space
)) {
247 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table
*table
,
248 int name_space
, const char *name
,
251 struct symbol_header
*hdr
;
254 check_symbol_table(table
);
256 hdr
= find_symbol(table
, name
);
258 check_symbol_table(table
);
261 hdr
= calloc(1, sizeof(*hdr
));
263 _mesa_error_no_memory(__func__
);
267 hdr
->name
= strdup(name
);
268 if (hdr
->name
== NULL
) {
270 _mesa_error_no_memory(__func__
);
274 hash_table_insert(table
->ht
, hdr
, hdr
->name
);
275 hdr
->next
= table
->hdr
;
279 check_symbol_table(table
);
281 /* If the symbol already exists in this namespace at this scope, it cannot
282 * be added to the table.
284 for (sym
= hdr
->symbols
285 ; (sym
!= NULL
) && (sym
->name_space
!= name_space
)
286 ; sym
= sym
->next_with_same_name
) {
290 if (sym
&& (sym
->depth
== table
->depth
))
293 sym
= calloc(1, sizeof(*sym
));
295 _mesa_error_no_memory(__func__
);
299 sym
->next_with_same_name
= hdr
->symbols
;
300 sym
->next_with_same_scope
= table
->current_scope
->symbols
;
302 sym
->name_space
= name_space
;
303 sym
->data
= declaration
;
304 sym
->depth
= table
->depth
;
306 assert(sym
->hdr
== hdr
);
309 table
->current_scope
->symbols
= sym
;
311 check_symbol_table(table
);
317 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table
*table
,
318 int name_space
, const char *name
,
321 struct symbol_header
*hdr
;
324 struct scope_level
*top_scope
;
326 check_symbol_table(table
);
328 hdr
= find_symbol(table
, name
);
330 check_symbol_table(table
);
333 hdr
= calloc(1, sizeof(*hdr
));
335 _mesa_error_no_memory(__func__
);
339 hdr
->name
= strdup(name
);
341 hash_table_insert(table
->ht
, hdr
, hdr
->name
);
342 hdr
->next
= table
->hdr
;
346 check_symbol_table(table
);
348 /* If the symbol already exists in this namespace at this scope, it cannot
349 * be added to the table.
351 for (sym
= hdr
->symbols
352 ; (sym
!= NULL
) && (sym
->name_space
!= name_space
)
353 ; sym
= sym
->next_with_same_name
) {
357 if (sym
&& sym
->depth
== 0)
360 /* Find the top-level scope */
361 for (top_scope
= table
->current_scope
362 ; top_scope
->next
!= NULL
363 ; top_scope
= top_scope
->next
) {
367 sym
= calloc(1, sizeof(*sym
));
369 _mesa_error_no_memory(__func__
);
373 sym
->next_with_same_scope
= top_scope
->symbols
;
375 sym
->name_space
= name_space
;
376 sym
->data
= declaration
;
378 assert(sym
->hdr
== hdr
);
380 /* Since next_with_same_name is ordered by scope, we need to append the
381 * new symbol to the _end_ of the list.
383 if (hdr
->symbols
== NULL
) {
386 for (curr
= hdr
->symbols
387 ; curr
->next_with_same_name
!= NULL
388 ; curr
= curr
->next_with_same_name
) {
391 curr
->next_with_same_name
= sym
;
393 top_scope
->symbols
= sym
;
395 check_symbol_table(table
);
401 struct _mesa_symbol_table
*
402 _mesa_symbol_table_ctor(void)
404 struct _mesa_symbol_table
*table
= calloc(1, sizeof(*table
));
407 table
->ht
= hash_table_ctor(32, hash_table_string_hash
,
408 hash_table_string_compare
);
410 _mesa_symbol_table_push_scope(table
);
418 _mesa_symbol_table_dtor(struct _mesa_symbol_table
*table
)
420 struct symbol_header
*hdr
;
421 struct symbol_header
*next
;
423 while (table
->current_scope
!= NULL
) {
424 _mesa_symbol_table_pop_scope(table
);
427 for (hdr
= table
->hdr
; hdr
!= NULL
; hdr
= next
) {
433 hash_table_dtor(table
->ht
);