diff options
author | Eric Anholt <[email protected]> | 2010-07-26 17:47:59 -0700 |
---|---|---|
committer | Eric Anholt <[email protected]> | 2010-07-26 17:53:27 -0700 |
commit | afe125e0a18ac3886c45c7e6b02b122fb2d327b5 (patch) | |
tree | 78621707e71154c0b388b0baacffc26432b7e992 /src/mesa/program/symbol_table.c | |
parent | d64343f1ae84979bd154475badf11af8a9bfc2eb (diff) | |
parent | 5403ca79b225605c79f49866a6497c97da53be3b (diff) |
Merge remote branch 'origin/master' into glsl2
This pulls in multiple i965 driver fixes which will help ensure better
testing coverage during development, and also gets past the conflicts
of the src/mesa/shader -> src/mesa/program move.
Conflicts:
src/mesa/Makefile
src/mesa/main/shaderapi.c
src/mesa/main/shaderobj.h
Diffstat (limited to 'src/mesa/program/symbol_table.c')
-rw-r--r-- | src/mesa/program/symbol_table.c | 412 |
1 files changed, 412 insertions, 0 deletions
diff --git a/src/mesa/program/symbol_table.c b/src/mesa/program/symbol_table.c new file mode 100644 index 00000000000..3fea5ee1f1f --- /dev/null +++ b/src/mesa/program/symbol_table.c @@ -0,0 +1,412 @@ +/* + * 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. */ + const 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; +}; + + +struct _mesa_symbol_table_iterator { + /** + * Name space of symbols returned by this iterator. + */ + int name_space; + + + /** + * Currently iterated symbol + * + * The next call to \c _mesa_symbol_table_iterator_get will return this + * value. It will also update this value to the value that should be + * returned by the next call. + */ + struct symbol *curr; +}; + + +static void +check_symbol_table(struct _mesa_symbol_table *table) +{ +#if 1 + 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); + } + } + } +#endif +} + +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)); + + 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); +} + + +struct _mesa_symbol_table_iterator * +_mesa_symbol_table_iterator_ctor(struct _mesa_symbol_table *table, + int name_space, const char *name) +{ + struct _mesa_symbol_table_iterator *iter = calloc(1, sizeof(*iter)); + struct symbol_header *const hdr = find_symbol(table, name); + + iter->name_space = name_space; + + 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)) { + iter->curr = sym; + break; + } + } + } + + return iter; +} + + +void +_mesa_symbol_table_iterator_dtor(struct _mesa_symbol_table_iterator *iter) +{ + free(iter); +} + + +void * +_mesa_symbol_table_iterator_get(struct _mesa_symbol_table_iterator *iter) +{ + return (iter->curr == NULL) ? NULL : iter->curr->data; +} + + +int +_mesa_symbol_table_iterator_next(struct _mesa_symbol_table_iterator *iter) +{ + struct symbol_header *hdr; + + if (iter->curr == NULL) { + return 0; + } + + hdr = iter->curr->hdr; + iter->curr = iter->curr->next_with_same_name; + + while (iter->curr != NULL) { + assert(iter->curr->hdr == hdr); + + if ((iter->name_space == -1) + || (iter->curr->name_space == iter->name_space)) { + return 1; + } + + iter->curr = iter->curr->next_with_same_name; + } + + return 0; +} + + +/** + * 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)); + hdr->name = name; + + hash_table_insert(table->ht, 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)); + 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; +} + + +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); + } + + hash_table_dtor(table->ht); + free(table); +} |