← Back to branch summary

~mmach/netext73/mesa-haswell

« back to all changes in this revision

Viewing changes to src/mesa/program/symbol_table.c

  • Committer: mmach
  • Date: 2022-09-22 19:56:13 UTC
  • Revision ID: netbit73@gmail.com-20220922195613-wtik9mmy20tmor0i
2022-09-22 21:17:09

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/mesa/program/symbol_table.c
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
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
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 *
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
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
 
 
164
 
void *
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
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
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
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 *
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
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
 
}