src/mesa/program/symbol_table.c

   1 /*
   2  * Copyright © 2008 Intel Corporation
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice (including the next
  12  * paragraph) shall be included in all copies or substantial portions of the
  13  * Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  20  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  21  * DEALINGS IN THE SOFTWARE.
  22  */
  23
  24 #include "main/imports.h"
  25 #include "symbol_table.h"
  26 #include "../../util/hash_table.h"
  27
  28 struct symbol {
  29    /** Symbol name. */
  30    char *name;
  31
  32     /**
  33      * Link to the next symbol in the table with the same name
  34      *
  35      * The linked list of symbols with the same name is ordered by scope
  36      * from inner-most to outer-most.
  37      */
  38     struct symbol *next_with_same_name;
  39
  40     /**
  41      * Link to the next symbol in the table with the same scope
  42      *
  43      * The linked list of symbols with the same scope is unordered.  Symbols
  44      * in this list my have unique names.
  45      */
  46     struct symbol *next_with_same_scope;
  47
  48     /** Scope depth where this symbol was defined. */
  49     unsigned depth;
  50
  51     /**
  52      * Arbitrary user supplied data.
  53      */
  54     void *data;
  55 };
  56
  57
  58 /**
  59  * Element of the scope stack.
  60  */
  61 struct scope_level {
  62     /** Link to next (inner) scope level. */
  63     struct scope_level *next;
  64
  65     /** Linked list of symbols with the same scope. */
  66     struct symbol *symbols;
  67 };
  68
  69
  70 /**
  71  *
  72  */
  73 struct _mesa_symbol_table {
  74     /** Hash table containing all symbols in the symbol table. */
  75     struct hash_table *ht;
  76
  77     /** Top of scope stack. */
  78     struct scope_level *current_scope;
  79
  80     /** Current scope depth. */
  81     unsigned depth;
  82 };
  83
  84 void
  85 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
  86 {
  87     struct scope_level *const scope = table->current_scope;
  88     struct symbol *sym = scope->symbols;
  89
  90     table->current_scope = scope->next;
  91     table->depth--;
  92
  93     free(scope);
  94
  95     while (sym != NULL) {
  96         struct symbol *const next = sym->next_with_same_scope;
  97         struct hash_entry *hte = _mesa_hash_table_search(table->ht,
  98                                                          sym->name);
  99         if (sym->next_with_same_name) {
 100            /* If there is a symbol with this name in an outer scope update
 101             * the hash table to point to it.
 102             */
 103            hte->key = sym->next_with_same_name->name;
 104            hte->data = sym->next_with_same_name;
 105         } else {
 106            _mesa_hash_table_remove(table->ht, hte);
 107            free(sym->name);
 108         }
 109
 110         free(sym);
 111         sym = next;
 112     }
 113 }
 114
 115
 116 void
 117 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
 118 {
 119     struct scope_level *const scope = calloc(1, sizeof(*scope));
 120     if (scope == NULL) {
 121        _mesa_error_no_memory(__func__);
 122        return;
 123     }
 124
 125     scope->next = table->current_scope;
 126     table->current_scope = scope;
 127     table->depth++;
 128 }
 129
 130
 131 static struct symbol *
 132 find_symbol(struct _mesa_symbol_table *table, const char *name)
 133 {
 134    struct hash_entry *entry = _mesa_hash_table_search(table->ht, name);
 135    return entry ? (struct symbol *) entry->data : NULL;
 136 }
 137
 138
 139 /**
 140  * Determine the scope "distance" of a symbol from the current scope
 141  *
 142  * \return
 143  * A non-negative number for the number of scopes between the current scope
 144  * and the scope where a symbol was defined.  A value of zero means the current
 145  * scope.  A negative number if the symbol does not exist.
 146  */
 147 int
 148 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
 149                                 const char *name)
 150 {
 151    struct symbol *const sym = find_symbol(table, name);
 152
 153    if (sym) {
 154       assert(sym->depth <= table->depth);
 155       return sym->depth - table->depth;
 156    }
 157
 158    return -1;
 159 }
 160
 161
 162 void *
 163 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
 164                                const char *name)
 165 {
 166    struct symbol *const sym = find_symbol(table, name);
 167    if (sym)
 168       return sym->data;
 169
 170    return NULL;
 171 }
 172
 173
 174 int
 175 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
 176                               const char *name, void *declaration)
 177 {
 178    struct symbol *new_sym;
 179    struct symbol *sym = find_symbol(table, name);
 180
 181    if (sym && sym->depth == table->depth)
 182       return -1;
 183
 184    new_sym = calloc(1, sizeof(*sym));
 185    if (new_sym == NULL) {
 186       _mesa_error_no_memory(__func__);
 187       return -1;
 188    }
 189
 190    if (sym) {
 191       /* Store link to symbol in outer scope with the same name */
 192       new_sym->next_with_same_name = sym;
 193       new_sym->name = sym->name;
 194    } else {
 195       new_sym->name = strdup(name);
 196       if (new_sym->name == NULL) {
 197          free(new_sym);
 198          _mesa_error_no_memory(__func__);
 199          return -1;
 200       }
 201    }
 202
 203    new_sym->next_with_same_scope = table->current_scope->symbols;
 204    new_sym->data = declaration;
 205    new_sym->depth = table->depth;
 206
 207    table->current_scope->symbols = new_sym;
 208
 209    _mesa_hash_table_insert(table->ht, new_sym->name, new_sym);
 210
 211    return 0;
 212 }
 213
 214 int
 215 _mesa_symbol_table_replace_symbol(struct _mesa_symbol_table *table,
 216                                   const char *name,
 217                                   void *declaration)
 218 {
 219     struct symbol *sym = find_symbol(table, name);
 220
 221     /* If the symbol doesn't exist, it cannot be replaced. */
 222     if (sym == NULL)
 223        return -1;
 224
 225     sym->data = declaration;
 226     return 0;
 227 }
 228
 229 int
 230 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
 231                                      const char *name, void *declaration)
 232 {
 233    struct scope_level *top_scope;
 234    struct symbol *inner_sym = NULL;
 235    struct symbol *sym = find_symbol(table, name);
 236
 237    while (sym) {
 238       if (sym->depth == 0)
 239          return -1;
 240
 241       inner_sym = sym;
 242
 243       /* Get symbol from the outer scope with the same name */
 244       sym = sym->next_with_same_name;
 245    }
 246
 247    /* Find the top-level scope */
 248    for (top_scope = table->current_scope; top_scope->next != NULL;
 249         top_scope = top_scope->next) {
 250       /* empty */
 251    }
 252
 253    sym = calloc(1, sizeof(*sym));
 254    if (sym == NULL) {
 255       _mesa_error_no_memory(__func__);
 256       return -1;
 257    }
 258
 259    if (inner_sym) {
 260       /* In case we add the global out of order store a link to the global
 261        * symbol in global.
 262        */
 263       inner_sym->next_with_same_name = sym;
 264
 265       sym->name = inner_sym->name;
 266    } else {
 267       sym->name = strdup(name);
 268       if (sym->name == NULL) {
 269          free(sym);
 270          _mesa_error_no_memory(__func__);
 271          return -1;
 272       }
 273    }
 274
 275    sym->next_with_same_scope = top_scope->symbols;
 276    sym->data = declaration;
 277
 278    top_scope->symbols = sym;
 279
 280    _mesa_hash_table_insert(table->ht, sym->name, sym);
 281
 282    return 0;
 283 }
 284
 285
 286
 287 struct _mesa_symbol_table *
 288 _mesa_symbol_table_ctor(void)
 289 {
 290     struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
 291
 292     if (table != NULL) {
 293        table->ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string,
 294                                            _mesa_key_string_equal);
 295
 296        _mesa_symbol_table_push_scope(table);
 297     }
 298
 299     return table;
 300 }
 301
 302
 303 void
 304 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
 305 {
 306    while (table->current_scope != NULL) {
 307       _mesa_symbol_table_pop_scope(table);
 308    }
 309
 310    _mesa_hash_table_destroy(table->ht, NULL);
 311    free(table);
 312 }