1 files changed, 377 insertions, 0 deletions
diff --git a/symbol_table.c b/symbol_table.c
new file mode 100644
index 0000000..4e043d1
--- /dev/null
+++ b/symbol_table.c
@@ -0,0 +1,377 @@
+/*
+ * 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;
+
+    
+    /**
+     * Arbitrary user supplied data.
+     */
+    void *data;
+
+   /** Scope depth where this symbol was defined. */
+   unsigned depth;
+};
+
+
+/**
+ */
+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;
+}
+
+
+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 at this scope, it cannot be added to the
+     * table.
+     */
+    if (hdr->symbols && (hdr->symbols->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;
+       _mesa_free(hdr);
+   }
+
+   hash_table_dtor(table->ht);
+   free(table);
+}