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 } 313
