aboutsummaryrefslogtreecommitdiff
path: root/mesalib/src/mesa/program/symbol_table.c
diff options
context:
space:
mode:
Diffstat (limited to 'mesalib/src/mesa/program/symbol_table.c')
-rw-r--r--mesalib/src/mesa/program/symbol_table.c901
1 files changed, 488 insertions, 413 deletions
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);
+}