src/mesa/shader/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 #include <stdlib.h>
  24 #include <stdio.h>
  25 #include <string.h>
  26 #include <errno.h>
  27 #include <assert.h>
  28
  29 #include "symbol_table.h"
  30 #include "hash_table.h"
  31
  32 struct symbol {
  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     /**
  43      * Link to the next symbol in the table with the same scope
  44      *
  45      * The linked list of symbols with the same scope is unordered.  Symbols
  46      * in this list my have unique names.
  47      */
  48     struct symbol *next_with_same_scope;
  49
  50
  51     /**
  52      * Header information for the list of symbols with the same name.
  53      */
  54     struct symbol_header *hdr;
  55
  56
  57     /**
  58      * Name space of the symbol
  59      *
  60      * Name space are arbitrary user assigned integers.  No two symbols can
  61      * exist in the same name space at the same scope level.
  62      */
  63     int name_space;
  64
  65
  66     /**
  67      * Arbitrary user supplied data.
  68      */
  69     void *data;
  70 };
  71
  72
  73 /**
  74  */
  75 struct symbol_header {
  76     /** Linkage in list of all headers in a given symbol table. */
  77     struct symbol_header *next;
  78
  79     /** Symbol name. */
  80     const char *name;
  81
  82     /** Linked list of symbols with the same name. */
  83     struct symbol *symbols;
  84 };
  85
  86
  87 /**
  88  * Element of the scope stack.
  89  */
  90 struct scope_level {
  91     /** Link to next (inner) scope level. */
  92     struct scope_level *next;
  93
  94     /** Linked list of symbols with the same scope. */
  95     struct symbol *symbols;
  96 };
  97
  98
  99 /**
 100  *
 101  */
 102 struct _mesa_symbol_table {
 103     /** Hash table containing all symbols in the symbol table. */
 104     struct hash_table *ht;
 105
 106     /** Top of scope stack. */
 107     struct scope_level *current_scope;
 108
 109     /** List of all symbol headers in the table. */
 110     struct symbol_header *hdr;
 111 };
 112
 113
 114 struct _mesa_symbol_table_iterator {
 115     /**
 116      * Name space of symbols returned by this iterator.
 117      */
 118     int name_space;
 119
 120
 121     /**
 122      * Currently iterated symbol
 123      *
 124      * The next call to \c _mesa_symbol_table_iterator_get will return this
 125      * value.  It will also update this value to the value that should be
 126      * returned by the next call.
 127      */
 128     struct symbol *curr;
 129 };
 130
 131
 132 static void
 133 check_symbol_table(struct _mesa_symbol_table *table)
 134 {
 135 #if 1
 136     struct scope_level *scope;
 137
 138     for (scope = table->current_scope; scope != NULL; scope = scope->next) {
 139         struct symbol *sym;
 140
 141         for (sym = scope->symbols
 142              ; sym != NULL
 143              ; sym = sym->next_with_same_name) {
 144             const struct symbol_header *const hdr = sym->hdr;
 145             struct symbol *sym2;
 146
 147             for (sym2 = hdr->symbols
 148                  ; sym2 != NULL
 149                  ; sym2 = sym2->next_with_same_name) {
 150                 assert(sym2->hdr == hdr);
 151             }
 152         }
 153     }
 154 #endif
 155 }
 156
 157 void
 158 _mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
 159 {
 160     struct scope_level *const scope = table->current_scope;
 161     struct symbol *sym = scope->symbols;
 162
 163     table->current_scope = scope->next;
 164
 165     free(scope);
 166
 167     while (sym != NULL) {
 168         struct symbol *const next = sym->next_with_same_scope;
 169         struct symbol_header *const hdr = sym->hdr;
 170
 171         assert(hdr->symbols == sym);
 172
 173         hdr->symbols = sym->next_with_same_name;
 174
 175         free(sym);
 176
 177         sym = next;
 178     }
 179
 180     check_symbol_table(table);
 181 }
 182
 183
 184 void
 185 _mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
 186 {
 187     struct scope_level *const scope = calloc(1, sizeof(*scope));
 188
 189     scope->next = table->current_scope;
 190     table->current_scope = scope;
 191 }
 192
 193
 194 static struct symbol_header *
 195 find_symbol(struct _mesa_symbol_table *table, const char *name)
 196 {
 197     return (struct symbol_header *) hash_table_find(table->ht, name);
 198 }
 199
 200
 201 struct _mesa_symbol_table_iterator *
 202 _mesa_symbol_table_iterator_ctor(struct _mesa_symbol_table *table,
 203                                  int name_space, const char *name)
 204 {
 205     struct _mesa_symbol_table_iterator *iter = calloc(1, sizeof(*iter));
 206     struct symbol_header *const hdr = find_symbol(table, name);
 207
 208     iter->name_space = name_space;
 209
 210     if (hdr != NULL) {
 211         struct symbol *sym;
 212
 213         for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
 214             assert(sym->hdr == hdr);
 215
 216             if ((name_space == -1) || (sym->name_space == name_space)) {
 217                 iter->curr = sym;
 218                 break;
 219             }
 220         }
 221     }
 222
 223     return iter;
 224 }
 225
 226
 227 void
 228 _mesa_symbol_table_iterator_dtor(struct _mesa_symbol_table_iterator *iter)
 229 {
 230     free(iter);
 231 }
 232
 233
 234 void *
 235 _mesa_symbol_table_iterator_get(struct _mesa_symbol_table_iterator *iter)
 236 {
 237     return (iter->curr == NULL) ? NULL : iter->curr->data;
 238 }
 239
 240
 241 int
 242 _mesa_symbol_table_iterator_next(struct _mesa_symbol_table_iterator *iter)
 243 {
 244     struct symbol_header *hdr;
 245
 246     if (iter->curr == NULL) {
 247         return 0;
 248     }
 249
 250     hdr = iter->curr->hdr;
 251     iter->curr = iter->curr->next_with_same_name;
 252
 253     while (iter->curr != NULL) {
 254         assert(iter->curr->hdr == hdr);
 255
 256         if ((iter->name_space == -1)
 257             || (iter->curr->name_space == iter->name_space)) {
 258             return 1;
 259         }
 260
 261         iter->curr = iter->curr->next_with_same_name;
 262     }
 263
 264     return 0;
 265 }
 266
 267
 268 void *
 269 _mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
 270                                int name_space, const char *name)
 271 {
 272     struct symbol_header *const hdr = find_symbol(table, name);
 273
 274     if (hdr != NULL) {
 275         struct symbol *sym;
 276
 277
 278         for (sym = hdr->symbols; sym != NULL; sym = sym->next_with_same_name) {
 279             assert(sym->hdr == hdr);
 280
 281             if ((name_space == -1) || (sym->name_space == name_space)) {
 282                 return sym->data;
 283             }
 284         }
 285     }
 286
 287     return NULL;
 288 }
 289
 290
 291 int
 292 _mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
 293                               int name_space, const char *name,
 294                               void *declaration)
 295 {
 296     struct symbol_header *hdr;
 297     struct symbol *sym;
 298
 299     check_symbol_table(table);
 300
 301     hdr = find_symbol(table, name);
 302
 303     check_symbol_table(table);
 304
 305     if (hdr == NULL) {
 306         hdr = calloc(1, sizeof(*hdr));
 307         hdr->name = name;
 308
 309         hash_table_insert(table->ht, hdr, name);
 310         hdr->next = table->hdr;
 311         table->hdr = hdr;
 312     }
 313
 314     check_symbol_table(table);
 315
 316     sym = calloc(1, sizeof(*sym));
 317     sym->next_with_same_name = hdr->symbols;
 318     sym->next_with_same_scope = table->current_scope->symbols;
 319     sym->hdr = hdr;
 320     sym->name_space = name_space;
 321     sym->data = declaration;
 322
 323     assert(sym->hdr == hdr);
 324
 325     hdr->symbols = sym;
 326     table->current_scope->symbols = sym;
 327
 328     check_symbol_table(table);
 329     return 0;
 330 }
 331
 332
 333 struct _mesa_symbol_table *
 334 _mesa_symbol_table_ctor(void)
 335 {
 336     struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
 337
 338     if (table != NULL) {
 339        table->ht = hash_table_ctor(32, hash_table_string_hash,
 340                                    hash_table_string_compare);
 341
 342        _mesa_symbol_table_push_scope(table);
 343     }
 344
 345     return table;
 346 }
 347
 348
 349 void
 350 _mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
 351 {
 352    struct symbol_header *hdr;
 353    struct symbol_header *next;
 354
 355    while (table->current_scope != NULL) {
 356       _mesa_symbol_table_pop_scope(table);
 357    }
 358
 359    for (hdr = table->hdr; hdr != NULL; hdr = next) {
 360        next = hdr->next;
 361        _mesa_free(hdr);
 362    }
 363
 364    hash_table_dtor(table->ht);
 365    free(table);
 366 }