Revision control
Copy as Markdown
Other Tools
/*
* Copyright © 2008 Intel Corporation
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice (including the next
* paragraph) shall be included in all copies or substantial portions of the
* Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
*/
#include "main/errors.h"
#include "symbol_table.h"
#include "util/hash_table.h"
#include "util/u_string.h"
struct symbol {
/** Symbol name. */
char *name;
/**
* Link to the next symbol in the table with the same name
*
* The linked list of symbols with the same name is ordered by scope
* from inner-most to outer-most.
*/
struct symbol *next_with_same_name;
/**
* Link to the next symbol in the table with the same scope
*
* The linked list of symbols with the same scope is unordered. Symbols
* in this list my have unique names.
*/
struct symbol *next_with_same_scope;
/** Scope depth where this symbol was defined. */
unsigned depth;
/**
* Arbitrary user supplied data.
*/
void *data;
};
/**
* Element of the scope stack.
*/
struct scope_level {
/** Link to next (inner) scope level. */
struct scope_level *next;
/** Linked list of symbols with the same scope. */
struct symbol *symbols;
};
/**
*
*/
struct _mesa_symbol_table {
/** Hash table containing all symbols in the symbol table. */
struct hash_table *ht;
/** Top of scope stack. */
struct scope_level *current_scope;
/** Current scope depth. */
unsigned depth;
};
void
_mesa_symbol_table_pop_scope(struct _mesa_symbol_table *table)
{
struct scope_level *const scope = table->current_scope;
struct symbol *sym = scope->symbols;
table->current_scope = scope->next;
table->depth--;
free(scope);
while (sym != NULL) {
struct symbol *const next = sym->next_with_same_scope;
struct hash_entry *hte = _mesa_hash_table_search(table->ht,
sym->name);
if (sym->next_with_same_name) {
/* If there is a symbol with this name in an outer scope update
* the hash table to point to it.
*/
hte->key = sym->next_with_same_name->name;
hte->data = sym->next_with_same_name;
} else {
_mesa_hash_table_remove(table->ht, hte);
free(sym->name);
}
free(sym);
sym = next;
}
}
void
_mesa_symbol_table_push_scope(struct _mesa_symbol_table *table)
{
struct scope_level *const scope = calloc(1, sizeof(*scope));
if (scope == NULL) {
_mesa_error_no_memory(__func__);
return;
}
scope->next = table->current_scope;
table->current_scope = scope;
table->depth++;
}
static struct symbol *
find_symbol(struct _mesa_symbol_table *table, const char *name)
{
struct hash_entry *entry = _mesa_hash_table_search(table->ht, name);
return entry ? (struct symbol *) entry->data : NULL;
}
/**
* Determine the scope "distance" of a symbol from the current scope
*
* \return
* A non-negative number for the number of scopes between the current scope
* and the scope where a symbol was defined. A value of zero means the current
* scope. A negative number if the symbol does not exist.
*/
int
_mesa_symbol_table_symbol_scope(struct _mesa_symbol_table *table,
const char *name)
{
struct symbol *const sym = find_symbol(table, name);
if (sym) {
assert(sym->depth <= table->depth);
return sym->depth - table->depth;
}
return -1;
}
void *
_mesa_symbol_table_find_symbol(struct _mesa_symbol_table *table,
const char *name)
{
struct symbol *const sym = find_symbol(table, name);
if (sym)
return sym->data;
return NULL;
}
int
_mesa_symbol_table_add_symbol(struct _mesa_symbol_table *table,
const char *name, void *declaration)
{
struct symbol *new_sym;
struct symbol *sym = find_symbol(table, name);
if (sym && sym->depth == table->depth)
return -1;
new_sym = calloc(1, sizeof(*sym));
if (new_sym == NULL) {
_mesa_error_no_memory(__func__);
return -1;
}
if (sym) {
/* Store link to symbol in outer scope with the same name */
new_sym->next_with_same_name = sym;
new_sym->name = sym->name;
} else {
new_sym->name = strdup(name);
if (new_sym->name == NULL) {
free(new_sym);
_mesa_error_no_memory(__func__);
return -1;
}
}
new_sym->next_with_same_scope = table->current_scope->symbols;
new_sym->data = declaration;
new_sym->depth = table->depth;
table->current_scope->symbols = new_sym;
_mesa_hash_table_insert(table->ht, new_sym->name, new_sym);
return 0;
}
int
_mesa_symbol_table_replace_symbol(struct _mesa_symbol_table *table,
const char *name,
void *declaration)
{
struct symbol *sym = find_symbol(table, name);
/* If the symbol doesn't exist, it cannot be replaced. */
if (sym == NULL)
return -1;
sym->data = declaration;
return 0;
}
int
_mesa_symbol_table_add_global_symbol(struct _mesa_symbol_table *table,
const char *name, void *declaration)
{
struct scope_level *top_scope;
struct symbol *inner_sym = NULL;
struct symbol *sym = find_symbol(table, name);
while (sym) {
if (sym->depth == 0)
return -1;
inner_sym = sym;
/* Get symbol from the outer scope with the same name */
sym = sym->next_with_same_name;
}
/* Find the top-level scope */
for (top_scope = table->current_scope; top_scope->next != NULL;
top_scope = top_scope->next) {
/* empty */
}
sym = calloc(1, sizeof(*sym));
if (sym == NULL) {
_mesa_error_no_memory(__func__);
return -1;
}
if (inner_sym) {
/* In case we add the global out of order store a link to the global
* symbol in global.
*/
inner_sym->next_with_same_name = sym;
sym->name = inner_sym->name;
} else {
sym->name = strdup(name);
if (sym->name == NULL) {
free(sym);
_mesa_error_no_memory(__func__);
return -1;
}
}
sym->next_with_same_scope = top_scope->symbols;
sym->data = declaration;
top_scope->symbols = sym;
_mesa_hash_table_insert(table->ht, sym->name, sym);
return 0;
}
struct _mesa_symbol_table *
_mesa_symbol_table_ctor(void)
{
struct _mesa_symbol_table *table = calloc(1, sizeof(*table));
if (table != NULL) {
table->ht = _mesa_hash_table_create(NULL, _mesa_hash_string,
_mesa_key_string_equal);
_mesa_symbol_table_push_scope(table);
}
return table;
}
void
_mesa_symbol_table_dtor(struct _mesa_symbol_table *table)
{
while (table->current_scope != NULL) {
_mesa_symbol_table_pop_scope(table);
}
_mesa_hash_table_destroy(table->ht, NULL);
free(table);
}