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