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