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
30struct 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 */
63struct 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 */
75struct _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
86void
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
118void
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
133static struct symbol *
134find_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 */
149int
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 table->depth - sym->depth;
158   }
159
160   return -1;
161}
162
163
164void *
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
176int
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
216int
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
231int
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
289struct _mesa_symbol_table *
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
305void
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