glsl/mesa: remove unused namespace support from the symbol table

Namespace support seems to have been unused for a very long time.

Previously the hash table entry was never removed and the symbol name
wasn't freed until the symbol table was destroyed.

In theory this could reduced the number of times we need to copy a string
as duplicate names are reused. However in practice there is likely only a
limited number of symbols that are the same and this is likely to cause
other less than optimal behaviour such as the hash_table continuously
growing.

Along with dropping namespace support this change removes entries from
the hash table as they become unused.

Reviewed-by: Samuel Iglesias Gonsálvez <[email protected]>

6 files changed, 128 insertions, 265 deletions

diff --git a/src/compiler/glsl/glsl_symbol_table.cpp b/src/compiler/glsl/glsl_symbol_table.cpp
index 6d7baad4863..3162bb685df 100644
--- a/src/compiler/glsl/glsl_symbol_table.cpp
+++ b/src/compiler/glsl/glsl_symbol_table.cpp
@@ -126,7 +126,7 @@ void glsl_symbol_table::pop_scope()
 
 bool glsl_symbol_table::name_declared_this_scope(const char *name)
 {
-   return _mesa_symbol_table_symbol_scope(table, -1, name) == 0;
+   return _mesa_symbol_table_symbol_scope(table, name) == 0;
 }
 
 bool glsl_symbol_table::add_variable(ir_variable *v)
@@ -152,7 +152,7 @@ bool glsl_symbol_table::add_variable(ir_variable *v)
 	 symbol_table_entry *entry = new(mem_ctx) symbol_table_entry(v);
 	 if (existing != NULL)
 	    entry->f = existing->f;
-	 int added = _mesa_symbol_table_add_symbol(table, -1, v->name, entry);
+	 int added = _mesa_symbol_table_add_symbol(table, v->name, entry);
 	 assert(added == 0);
 	 (void)added;
 	 return true;
@@ -162,13 +162,13 @@ bool glsl_symbol_table::add_variable(ir_variable *v)
 
    /* 1.20+ rules: */
    symbol_table_entry *entry = new(mem_ctx) symbol_table_entry(v);
-   return _mesa_symbol_table_add_symbol(table, -1, v->name, entry) == 0;
+   return _mesa_symbol_table_add_symbol(table, v->name, entry) == 0;
 }
 
 bool glsl_symbol_table::add_type(const char *name, const glsl_type *t)
 {
    symbol_table_entry *entry = new(mem_ctx) symbol_table_entry(t);
-   return _mesa_symbol_table_add_symbol(table, -1, name, entry) == 0;
+   return _mesa_symbol_table_add_symbol(table, name, entry) == 0;
 }
 
 bool glsl_symbol_table::add_interface(const char *name, const glsl_type *i,
@@ -180,7 +180,7 @@ bool glsl_symbol_table::add_interface(const char *name, const glsl_type *i,
       symbol_table_entry *entry =
          new(mem_ctx) symbol_table_entry(i, mode);
       bool add_interface_symbol_result =
-         _mesa_symbol_table_add_symbol(table, -1, name, entry) == 0;
+         _mesa_symbol_table_add_symbol(table, name, entry) == 0;
       assert(add_interface_symbol_result);
       return add_interface_symbol_result;
    } else {
@@ -199,7 +199,7 @@ bool glsl_symbol_table::add_function(ir_function *f)
       }
    }
    symbol_table_entry *entry = new(mem_ctx) symbol_table_entry(f);
-   return _mesa_symbol_table_add_symbol(table, -1, f->name, entry) == 0;
+   return _mesa_symbol_table_add_symbol(table, f->name, entry) == 0;
 }
 
 bool glsl_symbol_table::add_default_precision_qualifier(const char *type_name,
@@ -213,13 +213,13 @@ bool glsl_symbol_table::add_default_precision_qualifier(const char *type_name,
    symbol_table_entry *entry =
       new(mem_ctx) symbol_table_entry(default_specifier);
 
-   return _mesa_symbol_table_add_symbol(table, -1, name, entry) == 0;
+   return _mesa_symbol_table_add_symbol(table, name, entry) == 0;
 }
 
 void glsl_symbol_table::add_global_function(ir_function *f)
 {
    symbol_table_entry *entry = new(mem_ctx) symbol_table_entry(f);
-   int added = _mesa_symbol_table_add_global_symbol(table, -1, f->name, entry);
+   int added = _mesa_symbol_table_add_global_symbol(table, f->name, entry);
    assert(added == 0);
    (void)added;
 }
@@ -261,7 +261,7 @@ int glsl_symbol_table::get_default_precision_qualifier(const char *type_name)
 symbol_table_entry *glsl_symbol_table::get_entry(const char *name)
 {
    return (symbol_table_entry *)
-      _mesa_symbol_table_find_symbol(table, -1, name);
+      _mesa_symbol_table_find_symbol(table, name);
 }
 
 void
diff --git a/src/compiler/glsl/ir_print_visitor.cpp b/src/compiler/glsl/ir_print_visitor.cpp
index cdbe18476a7..703169eb976 100644
--- a/src/compiler/glsl/ir_print_visitor.cpp
+++ b/src/compiler/glsl/ir_print_visitor.cpp
@@ -130,14 +130,14 @@ ir_print_visitor::unique_name(ir_variable *var)
 
    /* If there's no conflict, just use the original name */
    const char* name = NULL;
-   if (_mesa_symbol_table_find_symbol(this->symbols, -1, var->name) == NULL) {
+   if (_mesa_symbol_table_find_symbol(this->symbols, var->name) == NULL) {
       name = var->name;
    } else {
       static unsigned i = 1;
       name = ralloc_asprintf(this->mem_ctx, "%s@%u", var->name, ++i);
    }
    _mesa_hash_table_insert(this->printable_names, var, (void *) name);
-   _mesa_symbol_table_add_symbol(this->symbols, -1, name, var);
+   _mesa_symbol_table_add_symbol(this->symbols, name, var);
    return name;
 }
 
diff --git a/src/mesa/program/program_lexer.l b/src/mesa/program/program_lexer.l
index bb169b930ce..dee66cbf30a 100644
--- a/src/mesa/program/program_lexer.l
+++ b/src/mesa/program/program_lexer.l
@@ -123,7 +123,7 @@ handle_ident(struct asm_parser_state *state, const char *text, YYSTYPE *lval)
 {
    lval->string = strdup(text);
 
-   return (_mesa_symbol_table_find_symbol(state->st, 0, text) == NULL)
+   return (_mesa_symbol_table_find_symbol(state->st, text) == NULL)
       ? IDENTIFIER : USED_IDENTIFIER;
 }
 
diff --git a/src/mesa/program/program_parse.y b/src/mesa/program/program_parse.y
index fc8eed75593..5294d58477a 100644
--- a/src/mesa/program/program_parse.y
+++ b/src/mesa/program/program_parse.y
@@ -724,7 +724,7 @@ extSwizSel: INTEGER
 srcReg: USED_IDENTIFIER /* temporaryReg | progParamSingle */
 	{
 	   struct asm_symbol *const s = (struct asm_symbol *)
-	      _mesa_symbol_table_find_symbol(state->st, 0, $1);
+              _mesa_symbol_table_find_symbol(state->st, $1);
 
 	   free($1);
 
@@ -812,7 +812,7 @@ dstReg: resultBinding
 	| USED_IDENTIFIER /* temporaryReg | vertexResultReg */
 	{
 	   struct asm_symbol *const s = (struct asm_symbol *)
-	      _mesa_symbol_table_find_symbol(state->st, 0, $1);
+              _mesa_symbol_table_find_symbol(state->st, $1);
 
 	   free($1);
 
@@ -841,7 +841,7 @@ dstReg: resultBinding
 progParamArray: USED_IDENTIFIER
 	{
 	   struct asm_symbol *const s = (struct asm_symbol *)
-	      _mesa_symbol_table_find_symbol(state->st, 0, $1);
+              _mesa_symbol_table_find_symbol(state->st, $1);
 
 	   free($1);
 
@@ -914,7 +914,7 @@ addrRegNegOffset: INTEGER
 addrReg: USED_IDENTIFIER
 	{
 	   struct asm_symbol *const s = (struct asm_symbol *)
-	      _mesa_symbol_table_find_symbol(state->st, 0, $1);
+              _mesa_symbol_table_find_symbol(state->st, $1);
 
 	   free($1);
 
@@ -2028,9 +2028,9 @@ legacyTexUnitNum: INTEGER
 ALIAS_statement: ALIAS IDENTIFIER '=' USED_IDENTIFIER
 	{
 	   struct asm_symbol *exist = (struct asm_symbol *)
-	      _mesa_symbol_table_find_symbol(state->st, 0, $2);
+              _mesa_symbol_table_find_symbol(state->st, $2);
 	   struct asm_symbol *target = (struct asm_symbol *)
-	      _mesa_symbol_table_find_symbol(state->st, 0, $4);
+              _mesa_symbol_table_find_symbol(state->st, $4);
 
 	   free($4);
 
@@ -2046,7 +2046,7 @@ ALIAS_statement: ALIAS IDENTIFIER '=' USED_IDENTIFIER
 		      "undefined variable binding in ALIAS statement");
 	      YYERROR;
 	   } else {
-	      _mesa_symbol_table_add_symbol(state->st, 0, $2, target);
+              _mesa_symbol_table_add_symbol(state->st, $2, target);
 	   }
 	}
 	;
@@ -2235,7 +2235,7 @@ declare_variable(struct asm_parser_state *state, char *name, enum asm_type t,
 {
    struct asm_symbol *s = NULL;
    struct asm_symbol *exist = (struct asm_symbol *)
-      _mesa_symbol_table_find_symbol(state->st, 0, name);
+      _mesa_symbol_table_find_symbol(state->st, name);
 
 
    if (exist != NULL) {
@@ -2273,7 +2273,7 @@ declare_variable(struct asm_parser_state *state, char *name, enum asm_type t,
 	 break;
       }
 
-      _mesa_symbol_table_add_symbol(state->st, 0, s->name, s);
+      _mesa_symbol_table_add_symbol(state->st, s->name, s);
       s->next = state->sym;
       state->sym = s;
    }
diff --git a/src/mesa/program/symbol_table.c b/src/mesa/program/symbol_table.c
index 3e5843225ab..23cb7ec26b1 100644
--- a/src/mesa/program/symbol_table.c
+++ b/src/mesa/program/symbol_table.c
@@ -26,6 +26,9 @@
 #include "../../util/hash_table.h"
 
 struct symbol {
+   /** Symbol name. */
+   char *name;
+
     /**
      * Link to the next symbol in the table with the same name
      *
@@ -34,7 +37,6 @@ struct symbol {
      */
     struct symbol *next_with_same_name;
 
-
     /**
      * Link to the next symbol in the table with the same scope
      *
@@ -43,21 +45,6 @@ struct symbol {
      */
     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;
 
@@ -69,20 +56,6 @@ struct symbol {
 
 
 /**
- */
-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 {
@@ -104,41 +77,10 @@ struct _mesa_symbol_table {
     /** 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)
 {
@@ -152,18 +94,22 @@ _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
 
     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;
+        struct hash_entry *hte = _mesa_hash_table_search(table->ht,
+                                                         sym->name);
+        if (sym->next_with_same_name) {
+           /* If there is a symbol with this name in an outer scope update
+            * the hash table to point to it.
+            */
+           hte->key = sym->next_with_same_name->name;
+           hte->data = sym->next_with_same_name;
+        } else {
+           _mesa_hash_table_remove(table->ht, hte);
+           free(sym->name);
+        }
 
         free(sym);
-
         sym = next;
     }
-
-    check_symbol_table(table);
 }
 
 
@@ -171,7 +117,6 @@ 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;
@@ -183,11 +128,11 @@ _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
 }
 
 
-static struct symbol_header *
+static struct symbol *
 find_symbol(struct _mesa_symbol_table *table, const char *name)
 {
    struct hash_entry *entry = _mesa_hash_table_search(table->ht, name);
-   return entry ? (struct symbol_header *) entry->data : NULL;
+   return entry ? (struct symbol *) entry->data : NULL;
 }
 
 
@@ -201,200 +146,126 @@ find_symbol(struct _mesa_symbol_table *table, const char *name)
  */
 int
 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
-				int name_space, const char *name)
+                                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;
-	  }
-       }
-    }
+   struct symbol *const sym = find_symbol(table, name);
 
-    return -1;
+   if (sym) {
+      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)
+                               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);
+   struct symbol *const sym = find_symbol(table, name);
+   if (sym)
+      return sym->data;
 
-            if ((name_space == -1) || (sym->name_space == name_space)) {
-                return sym->data;
-            }
-        }
-    }
-
-    return NULL;
+   return NULL;
 }
 
 
 int
 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
-                              int name_space, const char *name,
-                              void *declaration)
+                              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;
-       }
-
-       _mesa_hash_table_insert(table->ht, hdr->name, hdr);
-       hdr->next = table->hdr;
-       table->hdr = hdr;
-    }
+   struct symbol *new_sym;
+   struct symbol *sym = find_symbol(table, name);
 
-    check_symbol_table(table);
+   if (sym && sym->depth == table->depth)
+      return -1;
 
-    /* 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;
+   new_sym = calloc(1, sizeof(*sym));
+   if (new_sym == NULL) {
+      _mesa_error_no_memory(__func__);
+      return -1;
+   }
 
-    sym = calloc(1, sizeof(*sym));
-    if (sym == NULL) {
-       _mesa_error_no_memory(__func__);
-       return -1;
-    }
+   if (sym) {
+      /* Store link to symbol in outer scope with the same name */
+      new_sym->next_with_same_name = sym;
+      new_sym->name = sym->name;
+   } else {
+      new_sym->name = strdup(name);
+      if (new_sym->name == NULL) {
+         free(new_sym);
+         _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;
+   new_sym->next_with_same_scope = table->current_scope->symbols;
+   new_sym->data = declaration;
+   new_sym->depth = table->depth;
 
-    assert(sym->hdr == hdr);
+   table->current_scope->symbols = new_sym;
 
-    hdr->symbols = sym;
-    table->current_scope->symbols = sym;
+   _mesa_hash_table_insert(table->ht, new_sym->name, new_sym);
 
-    check_symbol_table(table);
-    return 0;
+   return 0;
 }
 
 
 int
 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
-				     int name_space, const char *name,
-				     void *declaration)
+                                     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);
+   struct scope_level *top_scope;
+   struct symbol *inner_sym = NULL;
+   struct symbol *sym = find_symbol(table, name);
 
-    check_symbol_table(table);
+   while (sym) {
+      if (sym->depth == 0)
+         return -1;
 
-    if (hdr == NULL) {
-        hdr = calloc(1, sizeof(*hdr));
-        if (hdr == NULL) {
-           _mesa_error_no_memory(__func__);
-           return -1;
-        }
-
-        hdr->name = strdup(name);
-
-        _mesa_hash_table_insert(table->ht, hdr->name, hdr);
-        hdr->next = table->hdr;
-        table->hdr = hdr;
-    }
-
-    check_symbol_table(table);
+      inner_sym = sym;
 
-    /* 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 */
-    }
+      /* Get symbol from the outer scope with the same name */
+      sym = sym->next_with_same_name;
+   }
 
-    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 */
+   }
 
-    /* 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 = calloc(1, sizeof(*sym));
-    if (sym == NULL) {
-       _mesa_error_no_memory(__func__);
-       return -1;
-    }
+   if (inner_sym) {
+      /* In case we add the global out of order store a link to the global
+       * symbol in global.
+       */
+      inner_sym->next_with_same_name = sym;
+
+      sym->name = inner_sym->name;
+   } else {
+      sym->name = strdup(name);
+      if (sym->name == NULL) {
+         free(sym);
+         _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;
+   sym->next_with_same_scope = top_scope->symbols;
+   sym->data = declaration;
 
-    assert(sym->hdr == hdr);
+   top_scope->symbols = sym;
 
-    /* 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;
+   _mesa_hash_table_insert(table->ht, sym->name, sym);
 
-    check_symbol_table(table);
-    return 0;
+   return 0;
 }
 
 
@@ -418,19 +289,10 @@ _mesa_symbol_table_ctor(void)
 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);
-   }
-
    _mesa_hash_table_destroy(table->ht, NULL);
    free(table);
 }
diff --git a/src/mesa/program/symbol_table.h b/src/mesa/program/symbol_table.h
index 1027f476110..ff1e6f2065a 100644
--- a/src/mesa/program/symbol_table.h
+++ b/src/mesa/program/symbol_table.h
@@ -30,17 +30,18 @@ extern void _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table);
 extern void _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table);
 
 extern int _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *symtab,
-    int name_space, const char *name, void *declaration);
+                                         const char *name, void *declaration);
 
-extern int _mesa_symbol_table_add_global_symbol(
-    struct _mesa_symbol_table *symtab, int name_space, const char *name,
-    void *declaration);
+extern int
+_mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *symtab,
+                                     const char *name,
+                                     void *declaration);
 
 extern int _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
-    int name_space, const char *name);
+                                           const char *name);
 
-extern void *_mesa_symbol_table_find_symbol(
-    struct _mesa_symbol_table *symtab, int name_space, const char *name);
+extern void *_mesa_symbol_table_find_symbol(struct _mesa_symbol_table *symtab,
+                                            const char *name);
 
 extern struct _mesa_symbol_table *_mesa_symbol_table_ctor(void);