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