From 807c6931fe683fd844ceec1b023232181e6aae03 Mon Sep 17 00:00:00 2001 From: marha Date: Tue, 28 Dec 2010 16:10:20 +0000 Subject: xserver and mesa git update 28-12-2010 --- mesalib/src/mesa/program/symbol_table.c | 901 +++++++++++++++++--------------- 1 file changed, 488 insertions(+), 413 deletions(-) (limited to 'mesalib/src/mesa/program/symbol_table.c') diff --git a/mesalib/src/mesa/program/symbol_table.c b/mesalib/src/mesa/program/symbol_table.c index 09e7cb44e..45aeb97b1 100644 --- a/mesalib/src/mesa/program/symbol_table.c +++ b/mesalib/src/mesa/program/symbol_table.c @@ -1,413 +1,488 @@ -/* - * 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; -}; - - -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 = 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 == 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->name); - free(hdr); - } - - hash_table_dtor(table->ht); - free(table); -} +/* + * 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; +}; + + +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 = 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 == 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; +} + + +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)); + 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)); + 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); +} -- cgit v1.2.3