1 /*
2  * Copyright © 2008 Intel Corporation
3  *
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:
10  *
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
13  * Software.
14  *
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.
22  */
23 
24 
25 #include "main/errors.h"
26 #include "symbol_table.h"
27 #include "util/hash_table.h"
28 #include "util/u_string.h"
29 
30 struct symbol {
31    /** Symbol name. */
32    char *name;
33 
34     /**
35      * Link to the next symbol in the table with the same name
36      *
37      * The linked list of symbols with the same name is ordered by scope
38      * from inner-most to outer-most.
39      */
40     struct symbol *next_with_same_name;
41 
42     /**
43      * Link to the next symbol in the table with the same scope
44      *
45      * The linked list of symbols with the same scope is unordered.  Symbols
46      * in this list my have unique names.
47      */
48     struct symbol *next_with_same_scope;
49 
50     /** Scope depth where this symbol was defined. */
51     unsigned depth;
52 
53     /**
54      * Arbitrary user supplied data.
55      */
56     void *data;
57 };
58 
59 
60 /**
61  * Element of the scope stack.
62  */
63 struct scope_level {
64     /** Link to next (inner) scope level. */
65     struct scope_level *next;
66 
67     /** Linked list of symbols with the same scope. */
68     struct symbol *symbols;
69 };
70 
71 
72 /**
73  *
74  */
75 struct _mesa_symbol_table {
76     /** Hash table containing all symbols in the symbol table. */
77     struct hash_table *ht;
78 
79     /** Top of scope stack. */
80     struct scope_level *current_scope;
81 
82     /** Current scope depth. */
83     unsigned depth;
84 };
85 
86 void
_mesa_symbol_table_pop_scope(struct _mesa_symbol_table * table)87 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
88 {
89     struct scope_level *const scope = table->current_scope;
90     struct symbol *sym = scope->symbols;
91 
92     table->current_scope = scope->next;
93     table->depth--;
94 
95     free(scope);
96 
97     while (sym != NULL) {
98         struct symbol *const next = sym->next_with_same_scope;
99         struct hash_entry *hte = _mesa_hash_table_search(table->ht,
100                                                          sym->name);
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.
104             */
105            hte->key = sym->next_with_same_name->name;
106            hte->data = sym->next_with_same_name;
107         } else {
108            _mesa_hash_table_remove(table->ht, hte);
109            free(sym->name);
110         }
111 
112         free(sym);
113         sym = next;
114     }
115 }
116 
117 
118 void
_mesa_symbol_table_push_scope(struct _mesa_symbol_table * table)119 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
120 {
121     struct scope_level *const scope = calloc(1, sizeof(*scope));
122     if (scope == NULL) {
123        _mesa_error_no_memory(__func__);
124        return;
125     }
126 
127     scope->next = table->current_scope;
128     table->current_scope = scope;
129     table->depth++;
130 }
131 
132 
133 static struct symbol *
find_symbol(struct _mesa_symbol_table * table,const char * name)134 find_symbol(struct _mesa_symbol_table *table, const char *name)
135 {
136    struct hash_entry *entry = _mesa_hash_table_search(table->ht, name);
137    return entry ? (struct symbol *) entry->data : NULL;
138 }
139 
140 
141 /**
142  * Determine the scope "distance" of a symbol from the current scope
143  *
144  * \return
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.
148  */
149 int
_mesa_symbol_table_symbol_scope(struct _mesa_symbol_table * table,const char * name)150 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
151                                 const char *name)
152 {
153    struct symbol *const sym = find_symbol(table, name);
154 
155    if (sym) {
156       assert(sym->depth <= table->depth);
157       return sym->depth - table->depth;
158    }
159 
160    return -1;
161 }
162 
163 
164 void *
_mesa_symbol_table_find_symbol(struct _mesa_symbol_table * table,const char * name)165 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
166                                const char *name)
167 {
168    struct symbol *const sym = find_symbol(table, name);
169    if (sym)
170       return sym->data;
171 
172    return NULL;
173 }
174 
175 
176 int
_mesa_symbol_table_add_symbol(struct _mesa_symbol_table * table,const char * name,void * declaration)177 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
178                               const char *name, void *declaration)
179 {
180    struct symbol *new_sym;
181    struct symbol *sym = find_symbol(table, name);
182 
183    if (sym && sym->depth == table->depth)
184       return -1;
185 
186    new_sym = calloc(1, sizeof(*sym));
187    if (new_sym == NULL) {
188       _mesa_error_no_memory(__func__);
189       return -1;
190    }
191 
192    if (sym) {
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;
196    } else {
197       new_sym->name = strdup(name);
198       if (new_sym->name == NULL) {
199          free(new_sym);
200          _mesa_error_no_memory(__func__);
201          return -1;
202       }
203    }
204 
205    new_sym->next_with_same_scope = table->current_scope->symbols;
206    new_sym->data = declaration;
207    new_sym->depth = table->depth;
208 
209    table->current_scope->symbols = new_sym;
210 
211    _mesa_hash_table_insert(table->ht, new_sym->name, new_sym);
212 
213    return 0;
214 }
215 
216 int
_mesa_symbol_table_replace_symbol(struct _mesa_symbol_table * table,const char * name,void * declaration)217 _mesa_symbol_table_replace_symbol(struct _mesa_symbol_table *table,
218                                   const char *name,
219                                   void *declaration)
220 {
221     struct symbol *sym = find_symbol(table, name);
222 
223     /* If the symbol doesn't exist, it cannot be replaced. */
224     if (sym == NULL)
225        return -1;
226 
227     sym->data = declaration;
228     return 0;
229 }
230 
231 int
_mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table * table,const char * name,void * declaration)232 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
233                                      const char *name, void *declaration)
234 {
235    struct scope_level *top_scope;
236    struct symbol *inner_sym = NULL;
237    struct symbol *sym = find_symbol(table, name);
238 
239    while (sym) {
240       if (sym->depth == 0)
241          return -1;
242 
243       inner_sym = sym;
244 
245       /* Get symbol from the outer scope with the same name */
246       sym = sym->next_with_same_name;
247    }
248 
249    /* Find the top-level scope */
250    for (top_scope = table->current_scope; top_scope->next != NULL;
251         top_scope = top_scope->next) {
252       /* empty */
253    }
254 
255    sym = calloc(1, sizeof(*sym));
256    if (sym == NULL) {
257       _mesa_error_no_memory(__func__);
258       return -1;
259    }
260 
261    if (inner_sym) {
262       /* In case we add the global out of order store a link to the global
263        * symbol in global.
264        */
265       inner_sym->next_with_same_name = sym;
266 
267       sym->name = inner_sym->name;
268    } else {
269       sym->name = strdup(name);
270       if (sym->name == NULL) {
271          free(sym);
272          _mesa_error_no_memory(__func__);
273          return -1;
274       }
275    }
276 
277    sym->next_with_same_scope = top_scope->symbols;
278    sym->data = declaration;
279 
280    top_scope->symbols = sym;
281 
282    _mesa_hash_table_insert(table->ht, sym->name, sym);
283 
284    return 0;
285 }
286 
287 
288 
289 struct _mesa_symbol_table *
_mesa_symbol_table_ctor(void)290 _mesa_symbol_table_ctor(void)
291 {
292     struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
293 
294     if (table != NULL) {
295        table->ht = _mesa_hash_table_create(NULL, _mesa_hash_string,
296                                            _mesa_key_string_equal);
297 
298        _mesa_symbol_table_push_scope(table);
299     }
300 
301     return table;
302 }
303 
304 
305 void
_mesa_symbol_table_dtor(struct _mesa_symbol_table * table)306 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
307 {
308    while (table->current_scope != NULL) {
309       _mesa_symbol_table_pop_scope(table);
310    }
311 
312    _mesa_hash_table_destroy(table->ht, NULL);
313    free(table);
314 }
315