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 #include "util/u_string.h" 28 29 struct symbol { 30 /** Symbol name. */ 31 char *name; 32 33 /** 34 * Link to the next symbol in the table with the same name 35 * 36 * The linked list of symbols with the same name is ordered by scope 37 * from inner-most to outer-most. 38 */ 39 struct symbol *next_with_same_name; 40 41 /** 42 * Link to the next symbol in the table with the same scope 43 * 44 * The linked list of symbols with the same scope is unordered. Symbols 45 * in this list my have unique names. 46 */ 47 struct symbol *next_with_same_scope; 48 49 /** Scope depth where this symbol was defined. */ 50 unsigned depth; 51 52 /** 53 * Arbitrary user supplied data. 54 */ 55 void *data; 56 }; 57 58 59 /** 60 * Element of the scope stack. 61 */ 62 struct scope_level { 63 /** Link to next (inner) scope level. */ 64 struct scope_level *next; 65 66 /** Linked list of symbols with the same scope. */ 67 struct symbol *symbols; 68 }; 69 70 71 /** 72 * 73 */ 74 struct _mesa_symbol_table { 75 /** Hash table containing all symbols in the symbol table. */ 76 struct hash_table *ht; 77 78 /** Top of scope stack. */ 79 struct scope_level *current_scope; 80 81 /** Current scope depth. */ 82 unsigned depth; 83 }; 84 85 void 86 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table) 87 { 88 struct scope_level *const scope = table->current_scope; 89 struct symbol *sym = scope->symbols; 90 91 table->current_scope = scope->next; 92 table->depth--; 93 94 free(scope); 95 96 while (sym != NULL) { 97 struct symbol *const next = sym->next_with_same_scope; 98 struct hash_entry *hte = _mesa_hash_table_search(table->ht, 99 sym->name); 100 if (sym->next_with_same_name) { 101 /* If there is a symbol with this name in an outer scope update 102 * the hash table to point to it. 103 */ 104 hte->key = sym->next_with_same_name->name; 105 hte->data = sym->next_with_same_name; 106 } else { 107 _mesa_hash_table_remove(table->ht, hte); 108 free(sym->name); 109 } 110 111 free(sym); 112 sym = next; 113 } 114 } 115 116 117 void 118 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table) 119 { 120 struct scope_level *const scope = calloc(1, sizeof(*scope)); 121 if (scope == NULL) { 122 _mesa_error_no_memory(__func__); 123 return; 124 } 125 126 scope->next = table->current_scope; 127 table->current_scope = scope; 128 table->depth++; 129 } 130 131 132 static struct symbol * 133 find_symbol(struct _mesa_symbol_table *table, const char *name) 134 { 135 struct hash_entry *entry = _mesa_hash_table_search(table->ht, name); 136 return entry ? (struct symbol *) entry->data : NULL; 137 } 138 139 140 /** 141 * Determine the scope "distance" of a symbol from the current scope 142 * 143 * \return 144 * A non-negative number for the number of scopes between the current scope 145 * and the scope where a symbol was defined. A value of zero means the current 146 * scope. A negative number if the symbol does not exist. 147 */ 148 int 149 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table, 150 const char *name) 151 { 152 struct symbol *const sym = find_symbol(table, name); 153 154 if (sym) { 155 assert(sym->depth <= table->depth); 156 return sym->depth - table->depth; 157 } 158 159 return -1; 160 } 161 162 163 void * 164 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table, 165 const char *name) 166 { 167 struct symbol *const sym = find_symbol(table, name); 168 if (sym) 169 return sym->data; 170 171 return NULL; 172 } 173 174 175 int 176 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table, 177 const char *name, void *declaration) 178 { 179 struct symbol *new_sym; 180 struct symbol *sym = find_symbol(table, name); 181 182 if (sym && sym->depth == table->depth) 183 return -1; 184 185 new_sym = calloc(1, sizeof(*sym)); 186 if (new_sym == NULL) { 187 _mesa_error_no_memory(__func__); 188 return -1; 189 } 190 191 if (sym) { 192 /* Store link to symbol in outer scope with the same name */ 193 new_sym->next_with_same_name = sym; 194 new_sym->name = sym->name; 195 } else { 196 new_sym->name = util_strdup(name); 197 if (new_sym->name == NULL) { 198 free(new_sym); 199 _mesa_error_no_memory(__func__); 200 return -1; 201 } 202 } 203 204 new_sym->next_with_same_scope = table->current_scope->symbols; 205 new_sym->data = declaration; 206 new_sym->depth = table->depth; 207 208 table->current_scope->symbols = new_sym; 209 210 _mesa_hash_table_insert(table->ht, new_sym->name, new_sym); 211 212 return 0; 213 } 214 215 int 216 _mesa_symbol_table_replace_symbol(struct _mesa_symbol_table *table, 217 const char *name, 218 void *declaration) 219 { 220 struct symbol *sym = find_symbol(table, name); 221 222 /* If the symbol doesn't exist, it cannot be replaced. */ 223 if (sym == NULL) 224 return -1; 225 226 sym->data = declaration; 227 return 0; 228 } 229 230 int 231 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table, 232 const char *name, void *declaration) 233 { 234 struct scope_level *top_scope; 235 struct symbol *inner_sym = NULL; 236 struct symbol *sym = find_symbol(table, name); 237 238 while (sym) { 239 if (sym->depth == 0) 240 return -1; 241 242 inner_sym = sym; 243 244 /* Get symbol from the outer scope with the same name */ 245 sym = sym->next_with_same_name; 246 } 247 248 /* Find the top-level scope */ 249 for (top_scope = table->current_scope; top_scope->next != NULL; 250 top_scope = top_scope->next) { 251 /* empty */ 252 } 253 254 sym = calloc(1, sizeof(*sym)); 255 if (sym == NULL) { 256 _mesa_error_no_memory(__func__); 257 return -1; 258 } 259 260 if (inner_sym) { 261 /* In case we add the global out of order store a link to the global 262 * symbol in global. 263 */ 264 inner_sym->next_with_same_name = sym; 265 266 sym->name = inner_sym->name; 267 } else { 268 sym->name = util_strdup(name); 269 if (sym->name == NULL) { 270 free(sym); 271 _mesa_error_no_memory(__func__); 272 return -1; 273 } 274 } 275 276 sym->next_with_same_scope = top_scope->symbols; 277 sym->data = declaration; 278 279 top_scope->symbols = sym; 280 281 _mesa_hash_table_insert(table->ht, sym->name, sym); 282 283 return 0; 284 } 285 286 287 288 struct _mesa_symbol_table * 289 _mesa_symbol_table_ctor(void) 290 { 291 struct _mesa_symbol_table *table = calloc(1, sizeof(*table)); 292 293 if (table != NULL) { 294 table->ht = _mesa_hash_table_create(NULL, _mesa_key_hash_string, 295 _mesa_key_string_equal); 296 297 _mesa_symbol_table_push_scope(table); 298 } 299 300 return table; 301 } 302 303 304 void 305 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table) 306 { 307 while (table->current_scope != NULL) { 308 _mesa_symbol_table_pop_scope(table); 309 } 310 311 _mesa_hash_table_destroy(table->ht, NULL); 312 free(table); 313 } 314
