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 (void)hdr; 259 260 if ((iter->name_space == -1) 261 || (iter->curr->name_space == iter->name_space)) { 262 return 1; 263 } 264 265 iter->curr = iter->curr->next_with_same_name; 266 } 267 268 return 0; 269 } 270 271 272 /** 273 * Determine the scope "distance" of a symbol from the current scope 274 * 275 * \return 276 * A non-negative number for the number of scopes between the current scope 277 * and the scope where a symbol was defined. A value of zero means the current 278 * scope. A negative number if the symbol does not exist. 279 */ 280 int 281 _mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table, 282 int name_space, const char *name) 283 { 284 struct symbol_header *const hdr = find_symbol(table, name); 285 struct symbol *sym; 286 287 if (hdr != NULL) { 288 for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) { 289 assert(sym->hdr == hdr); 290 291 if ((name_space == -1) || (sym->name_space == name_space)) { 292 assert(sym->depth <= table->depth); 293 return sym->depth - table->depth; 294 } 295 } 296 } 297 298 return -1; 299 } 300 301 302 void * 303 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table, 304 int name_space, const char *name) 305 { 306 struct symbol_header *const hdr = find_symbol(table, name); 307 308 if (hdr != NULL) { 309 struct symbol *sym; 310 311 312 for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) { 313 assert(sym->hdr == hdr); 314 315 if ((name_space == -1) || (sym->name_space == name_space)) { 316 return sym->data; 317 } 318 } 319 } 320 321 return NULL; 322 } 323 324 325 int 326 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table, 327 int name_space, const char *name, 328 void *declaration) 329 { 330 struct symbol_header *hdr; 331 struct symbol *sym; 332 333 check_symbol_table(table); 334 335 hdr = find_symbol(table, name); 336 337 check_symbol_table(table); 338 339 if (hdr == NULL) { 340 hdr = calloc(1, sizeof(*hdr)); 341 hdr->name = strdup(name); 342 343 hash_table_insert(table->ht, hdr, hdr->name); 344 hdr->next = table->hdr; 345 table->hdr = hdr; 346 } 347 348 check_symbol_table(table); 349 350 /* If the symbol already exists in this namespace at this scope, it cannot 351 * be added to the table. 352 */ 353 for (sym = hdr->symbols 354 ; (sym != NULL) && (sym->name_space != name_space) 355 ; sym = sym->next_with_same_name) { 356 /* empty */ 357 } 358 359 if (sym && (sym->depth == table->depth)) 360 return -1; 361 362 sym = calloc(1, sizeof(*sym)); 363 sym->next_with_same_name = hdr->symbols; 364 sym->next_with_same_scope = table->current_scope->symbols; 365 sym->hdr = hdr; 366 sym->name_space = name_space; 367 sym->data = declaration; 368 sym->depth = table->depth; 369 370 assert(sym->hdr == hdr); 371 372 hdr->symbols = sym; 373 table->current_scope->symbols = sym; 374 375 check_symbol_table(table); 376 return 0; 377 } 378 379 380 int 381 _mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table, 382 int name_space, const char *name, 383 void *declaration) 384 { 385 struct symbol_header *hdr; 386 struct symbol *sym; 387 struct symbol *curr; 388 struct scope_level *top_scope; 389 390 check_symbol_table(table); 391 392 hdr = find_symbol(table, name); 393 394 check_symbol_table(table); 395 396 if (hdr == NULL) { 397 hdr = calloc(1, sizeof(*hdr)); 398 hdr->name = strdup(name); 399 400 hash_table_insert(table->ht, hdr, hdr->name); 401 hdr->next = table->hdr; 402 table->hdr = hdr; 403 } 404 405 check_symbol_table(table); 406 407 /* If the symbol already exists in this namespace at this scope, it cannot 408 * be added to the table. 409 */ 410 for (sym = hdr->symbols 411 ; (sym != NULL) && (sym->name_space != name_space) 412 ; sym = sym->next_with_same_name) { 413 /* empty */ 414 } 415 416 if (sym && sym->depth == 0) 417 return -1; 418 419 /* Find the top-level scope */ 420 for (top_scope = table->current_scope 421 ; top_scope->next != NULL 422 ; top_scope = top_scope->next) { 423 /* empty */ 424 } 425 426 sym = calloc(1, sizeof(*sym)); 427 sym->next_with_same_scope = top_scope->symbols; 428 sym->hdr = hdr; 429 sym->name_space = name_space; 430 sym->data = declaration; 431 432 assert(sym->hdr == hdr); 433 434 /* Since next_with_same_name is ordered by scope, we need to append the 435 * new symbol to the _end_ of the list. 436 */ 437 if (hdr->symbols == NULL) { 438 hdr->symbols = sym; 439 } else { 440 for (curr = hdr->symbols 441 ; curr->next_with_same_name != NULL 442 ; curr = curr->next_with_same_name) { 443 /* empty */ 444 } 445 curr->next_with_same_name = sym; 446 } 447 top_scope->symbols = sym; 448 449 check_symbol_table(table); 450 return 0; 451 } 452 453 454 455 struct _mesa_symbol_table * 456 _mesa_symbol_table_ctor(void) 457 { 458 struct _mesa_symbol_table *table = calloc(1, sizeof(*table)); 459 460 if (table != NULL) { 461 table->ht = hash_table_ctor(32, hash_table_string_hash, 462 hash_table_string_compare); 463 464 _mesa_symbol_table_push_scope(table); 465 } 466 467 return table; 468 } 469 470 471 void 472 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table) 473 { 474 struct symbol_header *hdr; 475 struct symbol_header *next; 476 477 while (table->current_scope != NULL) { 478 _mesa_symbol_table_pop_scope(table); 479 } 480 481 for (hdr = table->hdr; hdr != NULL; hdr = next) { 482 next = hdr->next; 483 free(hdr->name); 484 free(hdr); 485 } 486 487 hash_table_dtor(table->ht); 488 free(table); 489 } 490
