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.
29 #include "symbol_table.h"
30 #include "hash_table.h"
34 * Link to the next symbol in the table with the same name
36 * The linked list of symbols with the same name is ordered by scope
37 * from inner-most to outer-most.
39 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
;
52 * Header information for the list of symbols with the same name.
54 struct symbol_header
*hdr
;
58 * Name space of the symbol
60 * Name space are arbitrary user assigned integers. No two symbols can
61 * exist in the same name space at the same scope level.
67 * Arbitrary user supplied data.
75 struct symbol_header
{
79 /** Linked list of symbols with the same name. */
80 struct symbol
*symbols
;
85 * Element of the scope stack.
88 /** Link to next (inner) scope level. */
89 struct scope_level
*next
;
91 /** Linked list of symbols with the same scope. */
92 struct symbol
*symbols
;
99 struct _mesa_symbol_table
{
100 /** Hash table containing all symbols in the symbol table. */
101 struct hash_table
*ht
;
103 /** Top of scope stack. */
104 struct scope_level
*current_scope
;
108 struct _mesa_symbol_table_iterator
{
110 * Name space of symbols returned by this iterator.
116 * Currently iterated symbol
118 * The next call to \c _mesa_symbol_table_iterator_get will return this
119 * value. It will also update this value to the value that should be
120 * returned by the next call.
127 check_symbol_table(struct _mesa_symbol_table
*table
)
130 struct scope_level
*scope
;
132 for (scope
= table
->current_scope
; scope
!= NULL
; scope
= scope
->next
) {
135 for (sym
= scope
->symbols
137 ; sym
= sym
->next_with_same_name
) {
138 const struct symbol_header
*const hdr
= sym
->hdr
;
141 for (sym2
= hdr
->symbols
143 ; sym2
= sym2
->next_with_same_name
) {
144 assert(sym2
->hdr
== hdr
);
152 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table
*table
)
154 struct scope_level
*const scope
= table
->current_scope
;
155 struct symbol
*sym
= scope
->symbols
;
157 table
->current_scope
= scope
->next
;
161 while (sym
!= NULL
) {
162 struct symbol
*const next
= sym
->next_with_same_scope
;
163 struct symbol_header
*const hdr
= sym
->hdr
;
165 assert(hdr
->symbols
== sym
);
167 hdr
->symbols
= sym
->next_with_same_name
;
174 check_symbol_table(table
);
179 _mesa_symbol_table_push_scope(struct _mesa_symbol_table
*table
)
181 struct scope_level
*const scope
= calloc(1, sizeof(*scope
));
183 scope
->next
= table
->current_scope
;
184 table
->current_scope
= scope
;
188 static struct symbol_header
*
189 find_symbol(struct _mesa_symbol_table
*table
, const char *name
)
191 return (struct symbol_header
*) hash_table_find(table
->ht
, name
);
195 struct _mesa_symbol_table_iterator
*
196 _mesa_symbol_table_iterator_ctor(struct _mesa_symbol_table
*table
,
197 int name_space
, const char *name
)
199 struct _mesa_symbol_table_iterator
*iter
= calloc(1, sizeof(*iter
));
200 struct symbol_header
*const hdr
= find_symbol(table
, name
);
202 iter
->name_space
= name_space
;
207 for (sym
= hdr
->symbols
; sym
!= NULL
; sym
= sym
->next_with_same_name
) {
208 assert(sym
->hdr
== hdr
);
210 if ((name_space
== -1) || (sym
->name_space
== name_space
)) {
222 _mesa_symbol_table_iterator_dtor(struct _mesa_symbol_table_iterator
*iter
)
229 _mesa_symbol_table_iterator_get(struct _mesa_symbol_table_iterator
*iter
)
231 return (iter
->curr
== NULL
) ? NULL
: iter
->curr
->data
;
236 _mesa_symbol_table_iterator_next(struct _mesa_symbol_table_iterator
*iter
)
238 struct symbol_header
*hdr
;
240 if (iter
->curr
== NULL
) {
244 hdr
= iter
->curr
->hdr
;
245 iter
->curr
= iter
->curr
->next_with_same_name
;
247 while (iter
->curr
!= NULL
) {
248 assert(iter
->curr
->hdr
== hdr
);
250 if ((iter
->name_space
== -1)
251 || (iter
->curr
->name_space
== iter
->name_space
)) {
255 iter
->curr
= iter
->curr
->next_with_same_name
;
263 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table
*table
,
264 int name_space
, const char *name
)
266 struct symbol_header
*const hdr
= find_symbol(table
, name
);
272 for (sym
= hdr
->symbols
; sym
!= NULL
; sym
= sym
->next_with_same_name
) {
273 assert(sym
->hdr
== hdr
);
275 if ((name_space
== -1) || (sym
->name_space
== name_space
)) {
286 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table
*table
,
287 int name_space
, const char *name
,
290 struct symbol_header
*hdr
;
293 check_symbol_table(table
);
295 hdr
= find_symbol(table
, name
);
297 check_symbol_table(table
);
300 hdr
= calloc(1, sizeof(*hdr
));
303 hash_table_insert(table
->ht
, hdr
, name
);
306 check_symbol_table(table
);
308 sym
= calloc(1, sizeof(*sym
));
309 sym
->next_with_same_name
= hdr
->symbols
;
310 sym
->next_with_same_scope
= table
->current_scope
->symbols
;
312 sym
->name_space
= name_space
;
313 sym
->data
= declaration
;
315 assert(sym
->hdr
== hdr
);
318 table
->current_scope
->symbols
= sym
;
320 check_symbol_table(table
);
325 struct _mesa_symbol_table
*
326 _mesa_symbol_table_ctor(void)
328 struct _mesa_symbol_table
*table
= calloc(1, sizeof(*table
));
331 table
->ht
= hash_table_ctor(32, hash_table_string_hash
,
332 hash_table_string_compare
);
334 _mesa_symbol_table_push_scope(table
);
342 _mesa_symbol_table_dtor(struct _mesa_symbol_table
*table
)
344 while (table
->current_scope
!= NULL
) {
345 _mesa_symbol_table_pop_scope(table
);
348 hash_table_dtor(table
->ht
);