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. */
115 struct _mesa_symbol_table_iterator
{
117 * Name space of symbols returned by this iterator.
123 * Currently iterated symbol
125 * The next call to \c _mesa_symbol_table_iterator_get will return this
126 * value. It will also update this value to the value that should be
127 * returned by the next call.
134 check_symbol_table(struct _mesa_symbol_table
*table
)
137 struct scope_level
*scope
;
139 for (scope
= table
->current_scope
; scope
!= NULL
; scope
= scope
->next
) {
142 for (sym
= scope
->symbols
144 ; sym
= sym
->next_with_same_name
) {
145 const struct symbol_header
*const hdr
= sym
->hdr
;
148 for (sym2
= hdr
->symbols
150 ; sym2
= sym2
->next_with_same_name
) {
151 assert(sym2
->hdr
== hdr
);
159 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table
*table
)
161 struct scope_level
*const scope
= table
->current_scope
;
162 struct symbol
*sym
= scope
->symbols
;
164 table
->current_scope
= scope
->next
;
169 while (sym
!= NULL
) {
170 struct symbol
*const next
= sym
->next_with_same_scope
;
171 struct symbol_header
*const hdr
= sym
->hdr
;
173 assert(hdr
->symbols
== sym
);
175 hdr
->symbols
= sym
->next_with_same_name
;
182 check_symbol_table(table
);
187 _mesa_symbol_table_push_scope(struct _mesa_symbol_table
*table
)
189 struct scope_level
*const scope
= calloc(1, sizeof(*scope
));
191 scope
->next
= table
->current_scope
;
192 table
->current_scope
= scope
;
197 static struct symbol_header
*
198 find_symbol(struct _mesa_symbol_table
*table
, const char *name
)
200 return (struct symbol_header
*) hash_table_find(table
->ht
, name
);
204 struct _mesa_symbol_table_iterator
*
205 _mesa_symbol_table_iterator_ctor(struct _mesa_symbol_table
*table
,
206 int name_space
, const char *name
)
208 struct _mesa_symbol_table_iterator
*iter
= calloc(1, sizeof(*iter
));
209 struct symbol_header
*const hdr
= find_symbol(table
, name
);
211 iter
->name_space
= name_space
;
216 for (sym
= hdr
->symbols
; sym
!= NULL
; sym
= sym
->next_with_same_name
) {
217 assert(sym
->hdr
== hdr
);
219 if ((name_space
== -1) || (sym
->name_space
== name_space
)) {
231 _mesa_symbol_table_iterator_dtor(struct _mesa_symbol_table_iterator
*iter
)
238 _mesa_symbol_table_iterator_get(struct _mesa_symbol_table_iterator
*iter
)
240 return (iter
->curr
== NULL
) ? NULL
: iter
->curr
->data
;
245 _mesa_symbol_table_iterator_next(struct _mesa_symbol_table_iterator
*iter
)
247 struct symbol_header
*hdr
;
249 if (iter
->curr
== NULL
) {
253 hdr
= iter
->curr
->hdr
;
254 iter
->curr
= iter
->curr
->next_with_same_name
;
256 while (iter
->curr
!= NULL
) {
257 assert(iter
->curr
->hdr
== hdr
);
260 if ((iter
->name_space
== -1)
261 || (iter
->curr
->name_space
== iter
->name_space
)) {
265 iter
->curr
= iter
->curr
->next_with_same_name
;
273 * Determine the scope "distance" of a symbol from the current scope
276 * A non-negative number for the number of scopes between the current scope
277 * and the scope where a symbol was defined. A value of zero means the current
278 * scope. A negative number if the symbol does not exist.
281 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table
*table
,
282 int name_space
, const char *name
)
284 struct symbol_header
*const hdr
= find_symbol(table
, name
);
288 for (sym
= hdr
->symbols
; sym
!= NULL
; sym
= sym
->next_with_same_name
) {
289 assert(sym
->hdr
== hdr
);
291 if ((name_space
== -1) || (sym
->name_space
== name_space
)) {
292 assert(sym
->depth
<= table
->depth
);
293 return sym
->depth
- table
->depth
;
303 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table
*table
,
304 int name_space
, const char *name
)
306 struct symbol_header
*const hdr
= find_symbol(table
, name
);
312 for (sym
= hdr
->symbols
; sym
!= NULL
; sym
= sym
->next_with_same_name
) {
313 assert(sym
->hdr
== hdr
);
315 if ((name_space
== -1) || (sym
->name_space
== name_space
)) {
326 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table
*table
,
327 int name_space
, const char *name
,
330 struct symbol_header
*hdr
;
333 check_symbol_table(table
);
335 hdr
= find_symbol(table
, name
);
337 check_symbol_table(table
);
340 hdr
= calloc(1, sizeof(*hdr
));
341 hdr
->name
= strdup(name
);
343 hash_table_insert(table
->ht
, hdr
, hdr
->name
);
344 hdr
->next
= table
->hdr
;
348 check_symbol_table(table
);
350 /* If the symbol already exists in this namespace at this scope, it cannot
351 * be added to the table.
353 for (sym
= hdr
->symbols
354 ; (sym
!= NULL
) && (sym
->name_space
!= name_space
)
355 ; sym
= sym
->next_with_same_name
) {
359 if (sym
&& (sym
->depth
== table
->depth
))
362 sym
= calloc(1, sizeof(*sym
));
363 sym
->next_with_same_name
= hdr
->symbols
;
364 sym
->next_with_same_scope
= table
->current_scope
->symbols
;
366 sym
->name_space
= name_space
;
367 sym
->data
= declaration
;
368 sym
->depth
= table
->depth
;
370 assert(sym
->hdr
== hdr
);
373 table
->current_scope
->symbols
= sym
;
375 check_symbol_table(table
);
381 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table
*table
,
382 int name_space
, const char *name
,
385 struct symbol_header
*hdr
;
388 struct scope_level
*top_scope
;
390 check_symbol_table(table
);
392 hdr
= find_symbol(table
, name
);
394 check_symbol_table(table
);
397 hdr
= calloc(1, sizeof(*hdr
));
398 hdr
->name
= strdup(name
);
400 hash_table_insert(table
->ht
, hdr
, hdr
->name
);
401 hdr
->next
= table
->hdr
;
405 check_symbol_table(table
);
407 /* If the symbol already exists in this namespace at this scope, it cannot
408 * be added to the table.
410 for (sym
= hdr
->symbols
411 ; (sym
!= NULL
) && (sym
->name_space
!= name_space
)
412 ; sym
= sym
->next_with_same_name
) {
416 if (sym
&& sym
->depth
== 0)
419 /* Find the top-level scope */
420 for (top_scope
= table
->current_scope
421 ; top_scope
->next
!= NULL
422 ; top_scope
= top_scope
->next
) {
426 sym
= calloc(1, sizeof(*sym
));
427 sym
->next_with_same_scope
= top_scope
->symbols
;
429 sym
->name_space
= name_space
;
430 sym
->data
= declaration
;
432 assert(sym
->hdr
== hdr
);
434 /* Since next_with_same_name is ordered by scope, we need to append the
435 * new symbol to the _end_ of the list.
437 if (hdr
->symbols
== NULL
) {
440 for (curr
= hdr
->symbols
441 ; curr
->next_with_same_name
!= NULL
442 ; curr
= curr
->next_with_same_name
) {
445 curr
->next_with_same_name
= sym
;
447 top_scope
->symbols
= sym
;
449 check_symbol_table(table
);
455 struct _mesa_symbol_table
*
456 _mesa_symbol_table_ctor(void)
458 struct _mesa_symbol_table
*table
= calloc(1, sizeof(*table
));
461 table
->ht
= hash_table_ctor(32, hash_table_string_hash
,
462 hash_table_string_compare
);
464 _mesa_symbol_table_push_scope(table
);
472 _mesa_symbol_table_dtor(struct _mesa_symbol_table
*table
)
474 struct symbol_header
*hdr
;
475 struct symbol_header
*next
;
477 while (table
->current_scope
!= NULL
) {
478 _mesa_symbol_table_pop_scope(table
);
481 for (hdr
= table
->hdr
; hdr
!= NULL
; hdr
= next
) {
487 hash_table_dtor(table
->ht
);