Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

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