| /* |
| * Copyright © 2008 Intel Corporation |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice (including the next |
| * paragraph) shall be included in all copies or substantial portions of the |
| * Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| * DEALINGS IN THE SOFTWARE. |
| */ |
| |
| #include "main/imports.h" |
| #include "symbol_table.h" |
| #include "hash_table.h" |
| |
| struct symbol { |
| /** |
| * Link to the next symbol in the table with the same name |
| * |
| * The linked list of symbols with the same name is ordered by scope |
| * from inner-most to outer-most. |
| */ |
| struct symbol *next_with_same_name; |
| |
| |
| /** |
| * Link to the next symbol in the table with the same scope |
| * |
| * The linked list of symbols with the same scope is unordered. Symbols |
| * in this list my have unique names. |
| */ |
| struct symbol *next_with_same_scope; |
| |
| |
| /** |
| * Header information for the list of symbols with the same name. |
| */ |
| struct symbol_header *hdr; |
| |
| |
| /** |
| * Name space of the symbol |
| * |
| * Name space are arbitrary user assigned integers. No two symbols can |
| * exist in the same name space at the same scope level. |
| */ |
| int name_space; |
| |
| /** Scope depth where this symbol was defined. */ |
| unsigned depth; |
| |
| /** |
| * Arbitrary user supplied data. |
| */ |
| void *data; |
| }; |
| |
| |
| /** |
| */ |
| struct symbol_header { |
| /** Linkage in list of all headers in a given symbol table. */ |
| struct symbol_header *next; |
| |
| /** Symbol name. */ |
| char *name; |
| |
| /** Linked list of symbols with the same name. */ |
| struct symbol *symbols; |
| }; |
| |
| |
| /** |
| * Element of the scope stack. |
| */ |
| struct scope_level { |
| /** Link to next (inner) scope level. */ |
| struct scope_level *next; |
| |
| /** Linked list of symbols with the same scope. */ |
| struct symbol *symbols; |
| }; |
| |
| |
| /** |
| * |
| */ |
| struct _mesa_symbol_table { |
| /** Hash table containing all symbols in the symbol table. */ |
| struct hash_table *ht; |
| |
| /** Top of scope stack. */ |
| struct scope_level *current_scope; |
| |
| /** List of all symbol headers in the table. */ |
| struct symbol_header *hdr; |
| |
| /** Current scope depth. */ |
| unsigned depth; |
| }; |
| |
| |
| static void |
| check_symbol_table(struct _mesa_symbol_table *table) |
| { |
| #if !defined(NDEBUG) |
| struct scope_level *scope; |
| |
| for (scope = table->current_scope; scope != NULL; scope = scope->next) { |
| struct symbol *sym; |
| |
| for (sym = scope->symbols |
| ; sym != NULL |
| ; sym = sym->next_with_same_name) { |
| const struct symbol_header *const hdr = sym->hdr; |
| struct symbol *sym2; |
| |
| for (sym2 = hdr->symbols |
| ; sym2 != NULL |
| ; sym2 = sym2->next_with_same_name) { |
| assert(sym2->hdr == hdr); |
| } |
| } |
| } |
| #else |
| (void) table; |
| #endif /* !defined(NDEBUG) */ |
| } |
| |
| void |
| _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table) |
| { |
| struct scope_level *const scope = table->current_scope; |
| struct symbol *sym = scope->symbols; |
| |
| table->current_scope = scope->next; |
| table->depth--; |
| |
| free(scope); |
| |
| while (sym != NULL) { |
| struct symbol *const next = sym->next_with_same_scope; |
| struct symbol_header *const hdr = sym->hdr; |
| |
| assert(hdr->symbols == sym); |
| |
| hdr->symbols = sym->next_with_same_name; |
| |
| free(sym); |
| |
| sym = next; |
| } |
| |
| check_symbol_table(table); |
| } |
| |
| |
| void |
| _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table) |
| { |
| struct scope_level *const scope = calloc(1, sizeof(*scope)); |
| |
| if (scope == NULL) { |
| _mesa_error_no_memory(__func__); |
| return; |
| } |
| |
| scope->next = table->current_scope; |
| table->current_scope = scope; |
| table->depth++; |
| } |
| |
| |
| static struct symbol_header * |
| find_symbol(struct _mesa_symbol_table *table, const char *name) |
| { |
| return (struct symbol_header *) hash_table_find(table->ht, name); |
| } |
| |
| |
| /** |
| * Determine the scope "distance" of a symbol from the current scope |
| * |
| * \return |
| * A non-negative number for the number of scopes between the current scope |
| * and the scope where a symbol was defined. A value of zero means the current |
| * scope. A negative number if the symbol does not exist. |
| */ |
| int |
| _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table, |
| int name_space, const char *name) |
| { |
| struct symbol_header *const hdr = find_symbol(table, name); |
| struct symbol *sym; |
| |
| if (hdr != NULL) { |
| for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) { |
| assert(sym->hdr == hdr); |
| |
| if ((name_space == -1) || (sym->name_space == name_space)) { |
| assert(sym->depth <= table->depth); |
| return sym->depth - table->depth; |
| } |
| } |
| } |
| |
| return -1; |
| } |
| |
| |
| void * |
| _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table, |
| int name_space, const char *name) |
| { |
| struct symbol_header *const hdr = find_symbol(table, name); |
| |
| if (hdr != NULL) { |
| struct symbol *sym; |
| |
| |
| for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) { |
| assert(sym->hdr == hdr); |
| |
| if ((name_space == -1) || (sym->name_space == name_space)) { |
| return sym->data; |
| } |
| } |
| } |
| |
| return NULL; |
| } |
| |
| |
| int |
| _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table, |
| int name_space, const char *name, |
| void *declaration) |
| { |
| struct symbol_header *hdr; |
| struct symbol *sym; |
| |
| check_symbol_table(table); |
| |
| hdr = find_symbol(table, name); |
| |
| check_symbol_table(table); |
| |
| if (hdr == NULL) { |
| hdr = calloc(1, sizeof(*hdr)); |
| if (hdr == NULL) { |
| _mesa_error_no_memory(__func__); |
| return -1; |
| } |
| |
| hdr->name = strdup(name); |
| if (hdr->name == NULL) { |
| free(hdr); |
| _mesa_error_no_memory(__func__); |
| return -1; |
| } |
| |
| hash_table_insert(table->ht, hdr, hdr->name); |
| hdr->next = table->hdr; |
| table->hdr = hdr; |
| } |
| |
| check_symbol_table(table); |
| |
| /* If the symbol already exists in this namespace at this scope, it cannot |
| * be added to the table. |
| */ |
| for (sym = hdr->symbols |
| ; (sym != NULL) && (sym->name_space != name_space) |
| ; sym = sym->next_with_same_name) { |
| /* empty */ |
| } |
| |
| if (sym && (sym->depth == table->depth)) |
| return -1; |
| |
| sym = calloc(1, sizeof(*sym)); |
| if (sym == NULL) { |
| _mesa_error_no_memory(__func__); |
| return -1; |
| } |
| |
| sym->next_with_same_name = hdr->symbols; |
| sym->next_with_same_scope = table->current_scope->symbols; |
| sym->hdr = hdr; |
| sym->name_space = name_space; |
| sym->data = declaration; |
| sym->depth = table->depth; |
| |
| assert(sym->hdr == hdr); |
| |
| hdr->symbols = sym; |
| table->current_scope->symbols = sym; |
| |
| check_symbol_table(table); |
| return 0; |
| } |
| |
| |
| int |
| _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table, |
| int name_space, const char *name, |
| void *declaration) |
| { |
| struct symbol_header *hdr; |
| struct symbol *sym; |
| struct symbol *curr; |
| struct scope_level *top_scope; |
| |
| check_symbol_table(table); |
| |
| hdr = find_symbol(table, name); |
| |
| check_symbol_table(table); |
| |
| if (hdr == NULL) { |
| hdr = calloc(1, sizeof(*hdr)); |
| if (hdr == NULL) { |
| _mesa_error_no_memory(__func__); |
| return -1; |
| } |
| |
| hdr->name = strdup(name); |
| |
| hash_table_insert(table->ht, hdr, hdr->name); |
| hdr->next = table->hdr; |
| table->hdr = hdr; |
| } |
| |
| check_symbol_table(table); |
| |
| /* If the symbol already exists in this namespace at this scope, it cannot |
| * be added to the table. |
| */ |
| for (sym = hdr->symbols |
| ; (sym != NULL) && (sym->name_space != name_space) |
| ; sym = sym->next_with_same_name) { |
| /* empty */ |
| } |
| |
| if (sym && sym->depth == 0) |
| return -1; |
| |
| /* Find the top-level scope */ |
| for (top_scope = table->current_scope |
| ; top_scope->next != NULL |
| ; top_scope = top_scope->next) { |
| /* empty */ |
| } |
| |
| sym = calloc(1, sizeof(*sym)); |
| if (sym == NULL) { |
| _mesa_error_no_memory(__func__); |
| return -1; |
| } |
| |
| sym->next_with_same_scope = top_scope->symbols; |
| sym->hdr = hdr; |
| sym->name_space = name_space; |
| sym->data = declaration; |
| |
| assert(sym->hdr == hdr); |
| |
| /* Since next_with_same_name is ordered by scope, we need to append the |
| * new symbol to the _end_ of the list. |
| */ |
| if (hdr->symbols == NULL) { |
| hdr->symbols = sym; |
| } else { |
| for (curr = hdr->symbols |
| ; curr->next_with_same_name != NULL |
| ; curr = curr->next_with_same_name) { |
| /* empty */ |
| } |
| curr->next_with_same_name = sym; |
| } |
| top_scope->symbols = sym; |
| |
| check_symbol_table(table); |
| return 0; |
| } |
| |
| |
| |
| struct _mesa_symbol_table * |
| _mesa_symbol_table_ctor(void) |
| { |
| struct _mesa_symbol_table *table = calloc(1, sizeof(*table)); |
| |
| if (table != NULL) { |
| table->ht = hash_table_ctor(32, hash_table_string_hash, |
| hash_table_string_compare); |
| |
| _mesa_symbol_table_push_scope(table); |
| } |
| |
| return table; |
| } |
| |
| |
| void |
| _mesa_symbol_table_dtor(struct _mesa_symbol_table *table) |
| { |
| struct symbol_header *hdr; |
| struct symbol_header *next; |
| |
| while (table->current_scope != NULL) { |
| _mesa_symbol_table_pop_scope(table); |
| } |
| |
| for (hdr = table->hdr; hdr != NULL; hdr = next) { |
| next = hdr->next; |
| free(hdr->name); |
| free(hdr); |
| } |
| |
| hash_table_dtor(table->ht); |
| free(table); |
| } |