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 "hash_table.h" 27 28 struct symbol { 29 /** 30 * Link to the next symbol in the table with the same name 31 * 32 * The linked list of symbols with the same name is ordered by scope 33 * from inner-most to outer-most. 34 */ 35 struct symbol *next_with_same_name; 36 37 38 /** 39 * Link to the next symbol in the table with the same scope 40 * 41 * The linked list of symbols with the same scope is unordered. Symbols 42 * in this list my have unique names. 43 */ 44 struct symbol *next_with_same_scope; 45 46 47 /** 48 * Header information for the list of symbols with the same name. 49 */ 50 struct symbol_header *hdr; 51 52 53 /** 54 * Name space of the symbol 55 * 56 * Name space are arbitrary user assigned integers. No two symbols can 57 * exist in the same name space at the same scope level. 58 */ 59 int name_space; 60 61 /** Scope depth where this symbol was defined. */ 62 unsigned depth; 63 64 /** 65 * Arbitrary user supplied data. 66 */ 67 void *data; 68 }; 69 70 71 /** 72 */ 73 struct symbol_header { 74 /** Linkage in list of all headers in a given symbol table. */ 75 struct symbol_header *next; 76 77 /** Symbol name. */ 78 char *name; 79 80 /** Linked list of symbols with the same name. */ 81 struct symbol *symbols; 82 }; 83 84 85 /** 86 * Element of the scope stack. 87 */ 88 struct scope_level { 89 /** Link to next (inner) scope level. */ 90 struct scope_level *next; 91 92 /** Linked list of symbols with the same scope. */ 93 struct symbol *symbols; 94 }; 95 96 97 /** 98 * 99 */ 100 struct _mesa_symbol_table { 101 /** Hash table containing all symbols in the symbol table. */ 102 struct hash_table *ht; 103 104 /** Top of scope stack. */ 105 struct scope_level *current_scope; 106 107 /** List of all symbol headers in the table. */ 108 struct symbol_header *hdr; 109 110 /** Current scope depth. */ 111 unsigned depth; 112 }; 113 114 115 struct _mesa_symbol_table_iterator { 116 /** 117 * Name space of symbols returned by this iterator. 118 */ 119 int name_space; 120 121 122 /** 123 * Currently iterated symbol 124 * 125 * The next call to \c _mesa_symbol_table_iterator_get will return this 126 * value. It will also update this value to the value that should be 127 * returned by the next call. 128 */ 129 struct symbol *curr; 130 }; 131 132 133 static void 134 check_symbol_table(struct _mesa_symbol_table *table) 135 { 136 #if 1 137 struct scope_level *scope; 138 139 for (scope = table->current_scope; scope != NULL; scope = scope->next) { 140 struct symbol *sym; 141 142 for (sym = scope->symbols 143 ; sym != NULL 144 ; sym = sym->next_with_same_name) { 145 const struct symbol_header *const hdr = sym->hdr; 146 struct symbol *sym2; 147 148 for (sym2 = hdr->symbols 149 ; sym2 != NULL 150 ; sym2 = sym2->next_with_same_name) { 151 assert(sym2->hdr == hdr); 152 } 153 } 154 } 155 #endif 156 } 157 158 void 159 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table) 160 { 161 struct scope_level *const scope = table->current_scope; 162 struct symbol *sym = scope->symbols; 163 164 table->current_scope = scope->next; 165 table->depth--; 166 167 free(scope); 168 169 while (sym != NULL) { 170 struct symbol *const next = sym->next_with_same_scope; 171 struct symbol_header *const hdr = sym->hdr; 172 173 assert(hdr->symbols == sym); 174 175 hdr->symbols = sym->next_with_same_name; 176 177 free(sym); 178 179 sym = next; 180 } 181 182 check_symbol_table(table); 183 } 184 185 186 void 187 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table) 188 { 189 struct scope_level *const scope = calloc(1, sizeof(*scope)); 190 191 scope->next = table->current_scope; 192 table->current_scope = scope; 193 table->depth++; 194 } 195 196 197 static struct symbol_header * 198 find_symbol(struct _mesa_symbol_table *table, const char *name) 199 { 200 return (struct symbol_header *) hash_table_find(table->ht, name); 201 } 202 203 204 struct _mesa_symbol_table_iterator * 205 _mesa_symbol_table_iterator_ctor(struct _mesa_symbol_table *table, 206 int name_space, const char *name) 207 { 208 struct _mesa_symbol_table_iterator *iter = calloc(1, sizeof(*iter)); 209 struct symbol_header *const hdr = find_symbol(table, name); 210 211 iter->name_space = name_space; 212 213 if (hdr != NULL) { 214 struct symbol *sym; 215 216 for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) { 217 assert(sym->hdr == hdr); 218 219 if ((name_space == -1) || (sym->name_space == name_space)) { 220 iter->curr = sym; 221 break; 222 } 223 } 224 } 225 226 return iter; 227 } 228 229 230 void 231 _mesa_symbol_table_iterator_dtor(struct _mesa_symbol_table_iterator *iter) 232 { 233 free(iter); 234 } 235 236 237 void * 238 _mesa_symbol_table_iterator_get(struct _mesa_symbol_table_iterator *iter) 239 { 240 return (iter->curr == NULL) ? NULL : iter->curr->data; 241 } 242 243 244 int 245 _mesa_symbol_table_iterator_next(struct _mesa_symbol_table_iterator *iter) 246 { 247 struct symbol_header *hdr; 248 249 if (iter->curr == NULL) { 250 return 0; 251 } 252 253 hdr = iter->curr->hdr; 254 iter->curr = iter->curr->next_with_same_name; 255 256 while (iter->curr != NULL) { 257 assert(iter->curr->hdr == hdr); 258 259 if ((iter->name_space == -1) 260 || (iter->curr->name_space == iter->name_space)) { 261 return 1; 262 } 263 264 iter->curr = iter->curr->next_with_same_name; 265 } 266 267 return 0; 268 } 269 270 271 /** 272 * Determine the scope "distance" of a symbol from the current scope 273 * 274 * \return 275 * A non-negative number for the number of scopes between the current scope 276 * and the scope where a symbol was defined. A value of zero means the current 277 * scope. A negative number if the symbol does not exist. 278 */ 279 int 280 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table, 281 int name_space, const char *name) 282 { 283 struct symbol_header *const hdr = find_symbol(table, name); 284 struct symbol *sym; 285 286 if (hdr != NULL) { 287 for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) { 288 assert(sym->hdr == hdr); 289 290 if ((name_space == -1) || (sym->name_space == name_space)) { 291 assert(sym->depth <= table->depth); 292 return sym->depth - table->depth; 293 } 294 } 295 } 296 297 return -1; 298 } 299 300 301 void * 302 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table, 303 int name_space, const char *name) 304 { 305 struct symbol_header *const hdr = find_symbol(table, name); 306 307 if (hdr != NULL) { 308 struct symbol *sym; 309 310 311 for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) { 312 assert(sym->hdr == hdr); 313 314 if ((name_space == -1) || (sym->name_space == name_space)) { 315 return sym->data; 316 } 317 } 318 } 319 320 return NULL; 321 } 322 323 324 int 325 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table, 326 int name_space, const char *name, 327 void *declaration) 328 { 329 struct symbol_header *hdr; 330 struct symbol *sym; 331 332 check_symbol_table(table); 333 334 hdr = find_symbol(table, name); 335 336 check_symbol_table(table); 337 338 if (hdr == NULL) { 339 hdr = calloc(1, sizeof(*hdr)); 340 hdr->name = strdup(name); 341 342 hash_table_insert(table->ht, hdr, hdr->name); 343 hdr->next = table->hdr; 344 table->hdr = hdr; 345 } 346 347 check_symbol_table(table); 348 349 /* If the symbol already exists in this namespace at this scope, it cannot 350 * be added to the table. 351 */ 352 for (sym = hdr->symbols 353 ; (sym != NULL) && (sym->name_space != name_space) 354 ; sym = sym->next_with_same_name) { 355 /* empty */ 356 } 357 358 if (sym && (sym->depth == table->depth)) 359 return -1; 360 361 sym = calloc(1, sizeof(*sym)); 362 sym->next_with_same_name = hdr->symbols; 363 sym->next_with_same_scope = table->current_scope->symbols; 364 sym->hdr = hdr; 365 sym->name_space = name_space; 366 sym->data = declaration; 367 sym->depth = table->depth; 368 369 assert(sym->hdr == hdr); 370 371 hdr->symbols = sym; 372 table->current_scope->symbols = sym; 373 374 check_symbol_table(table); 375 return 0; 376 } 377 378 379 int 380 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table, 381 int name_space, const char *name, 382 void *declaration) 383 { 384 struct symbol_header *hdr; 385 struct symbol *sym; 386 struct symbol *curr; 387 struct scope_level *top_scope; 388 389 check_symbol_table(table); 390 391 hdr = find_symbol(table, name); 392 393 check_symbol_table(table); 394 395 if (hdr == NULL) { 396 hdr = calloc(1, sizeof(*hdr)); 397 hdr->name = strdup(name); 398 399 hash_table_insert(table->ht, hdr, hdr->name); 400 hdr->next = table->hdr; 401 table->hdr = hdr; 402 } 403 404 check_symbol_table(table); 405 406 /* If the symbol already exists in this namespace at this scope, it cannot 407 * be added to the table. 408 */ 409 for (sym = hdr->symbols 410 ; (sym != NULL) && (sym->name_space != name_space) 411 ; sym = sym->next_with_same_name) { 412 /* empty */ 413 } 414 415 if (sym && sym->depth == 0) 416 return -1; 417 418 /* Find the top-level scope */ 419 for (top_scope = table->current_scope 420 ; top_scope->next != NULL 421 ; top_scope = top_scope->next) { 422 /* empty */ 423 } 424 425 sym = calloc(1, sizeof(*sym)); 426 sym->next_with_same_scope = top_scope->symbols; 427 sym->hdr = hdr; 428 sym->name_space = name_space; 429 sym->data = declaration; 430 431 assert(sym->hdr == hdr); 432 433 /* Since next_with_same_name is ordered by scope, we need to append the 434 * new symbol to the _end_ of the list. 435 */ 436 if (hdr->symbols == NULL) { 437 hdr->symbols = sym; 438 } else { 439 for (curr = hdr->symbols 440 ; curr->next_with_same_name != NULL 441 ; curr = curr->next_with_same_name) { 442 /* empty */ 443 } 444 curr->next_with_same_name = sym; 445 } 446 top_scope->symbols = sym; 447 448 check_symbol_table(table); 449 return 0; 450 } 451 452 453 454 struct _mesa_symbol_table * 455 _mesa_symbol_table_ctor(void) 456 { 457 struct _mesa_symbol_table *table = calloc(1, sizeof(*table)); 458 459 if (table != NULL) { 460 table->ht = hash_table_ctor(32, hash_table_string_hash, 461 hash_table_string_compare); 462 463 _mesa_symbol_table_push_scope(table); 464 } 465 466 return table; 467 } 468 469 470 void 471 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table) 472 { 473 struct symbol_header *hdr; 474 struct symbol_header *next; 475 476 while (table->current_scope != NULL) { 477 _mesa_symbol_table_pop_scope(table); 478 } 479 480 for (hdr = table->hdr; hdr != NULL; hdr = next) { 481 next = hdr->next; 482 free(hdr->name); 483 free(hdr); 484 } 485 486 hash_table_dtor(table->ht); 487 free(table); 488 } 489
