/* Symbol table support
Copyright 1998-2005 James Bowman
Copyright 2016 Molnár Károly
*/
#include "stdhdr.h"
#include "libgputils.h"
#define HASH_TABLE_SIZE_MIN 5
struct symbol {
const char *name;
void *annotation;
hash128_t hash;
};
struct symbol_table {
symbol_table_t *prev;
symbol_t **symbol_array;
size_t symbol_array_size;
size_t num_symbol;
bool case_insensitive;
};
/*------------------------------------------------------------------------------------------------*/
static symbol_t* _make_symbol(const char *String, hash128_t *Hash) {
symbol_t *sym;
if (!String) return 0;
sym = new symbol_t;
sym->name = GP_Strdup(String);
sym->hash = *Hash;
sym->annotation = 0;
return sym;
}
/*------------------------------------------------------------------------------------------------*/
static symbol_t* _get_symbol_from_table(const symbol_table_t *Table, hash128_t *Hash) {
assert(Table);
assert(Hash);
if (!Table->symbol_array || !Table->num_symbol) return 0;
symbol_t **base = Table->symbol_array;
size_t len = Table->num_symbol;
do{
size_t mid = len >> 1;
symbol_t **current = &base[mid];
if (*Hash==(*current)->hash) return *current;/* Found the symbol. */
if (len == 1) {
/* This is different int the least from the sought element. */
break;
}else if (*Hash < (*current)->hash) len = mid;
else{
len -= mid;
base = current;
}
}while (len > 0);
return NULL;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(symbol_table_t*) gp_sym_push_table(symbol_table_t *Table, bool Case_insensitive) {
symbol_table_t *new_table = new symbol_table_t;
memset(new_table,0,sizeof*new_table);
new_table->prev = Table;
new_table->case_insensitive = Case_insensitive;
return new_table;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(symbol_table_t*) gp_sym_pop_table(symbol_table_t *Table) {
assert(Table);
return Table->prev;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(void) gp_sym_set_guest_table(symbol_table_t *Table_host, symbol_table_t *Table_guest) {
assert(Table_host);
Table_host->prev = Table_guest;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(symbol_table_t*) gp_sym_get_guest_table(symbol_table_t *Table) {
assert(Table);
return Table->prev;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(symbol_t*) gp_sym_add_symbol(symbol_table_t *Table, const char *Name) {
symbol_t **base;
symbol_t **current;
symbol_t *sym;
size_t mid;
size_t idx;
size_t len;
assert(Table);
assert(Name);
assert(Table->num_symbol <= UINT32_MAX);
if (!Table->symbol_array) {
Table->symbol_array = new symbol_t*[HASH_TABLE_SIZE_MIN];
Table->symbol_array_size = HASH_TABLE_SIZE_MIN;
Table->num_symbol = 0;
}
else if (Table->num_symbol >= Table->symbol_array_size) {
/* Doubles the size of the table. */
len = Table->symbol_array_size * 2;
Table->symbol_array = (symbol_t **)GP_Realloc(Table->symbol_array, len * sizeof(symbol_t *));
Table->symbol_array_size = len;
}
hash128_t hash(Name, Table->case_insensitive);
if (!Table->num_symbol) {
/* Empty the table. */
sym = _make_symbol(Name, &hash);
Table->symbol_array[0] = sym;
Table->num_symbol = 1;
return sym;
}
base = Table->symbol_array;
len = Table->num_symbol;
do {
mid = len >> 1;
current = &base[mid];
if (hash == (*current)->hash) return *current;/* Found the symbol. */
if (len == 1) {
/* This is different in the least from the sought element. */
base = Table->symbol_array;
idx = current - base;
if (hash > (*current)->hash) ++idx; /* The new element is greather than this. */
len = (Table->num_symbol - idx) * sizeof(symbol_t *);
if (len > 0) {
/* The pnew element will not be the end of the table. */
memmove(&base[idx + 1], &base[idx], len);
}
sym = _make_symbol(Name, &hash);
base[idx] = sym;
++(Table->num_symbol);
return sym;
}
else if (hash < (*current)->hash) len = mid;
else {
len -= mid;
base = current;
}
}
while (len > 0);
return NULL;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(bool) gp_sym_remove_symbol_with_index(symbol_table_t *Table, size_t Index) {
symbol_t **base;
symbol_t *sym;
size_t len;
assert(!(Table == NULL));
if ((Table->symbol_array == NULL) || (Table->num_symbol == 0)) {
return false;
}
if (Index >= Table->num_symbol) {
return false;
}
len = (Table->num_symbol - Index - 1) * sizeof(symbol_t *);
base = Table->symbol_array;
sym = base[Index];
if (len > 0) {
memmove(&base[Index], &base[Index + 1], len);
}
--(Table->num_symbol);
if (sym->name) free((void*)sym->name);
delete sym;
return true;
}
/*------------------------------------------------------------------------------------------------*/
/* FIXME: gp_sym_remove_symbol does not search all of the symbol tables in the stack.
Maybe this is ok, but it seems wrong. */
FUNC(bool) gp_sym_remove_symbol(symbol_table_t *Table, const char *Name) {
symbol_t **base;
symbol_t **current;
size_t mid;
size_t len;
assert(Table);
assert(Name);
if (!Table->symbol_array || !Table->num_symbol) return false;
hash128_t hash(Name,Table->case_insensitive);
base = Table->symbol_array;
len = Table->num_symbol;
do {
mid = len >> 1;
current = &base[mid];
if (hash==(*current)->hash) {
/* Found the symbol. */
return gp_sym_remove_symbol_with_index(Table, current - Table->symbol_array);
}
if (len == 1) {
/* This is different int the least from the sought element. */
return false;
}
else if (hash < (*current)->hash) len = mid;
else {
len -= mid;
base = current;
}
}
while (len > 0);
return false;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(size_t) gp_sym_get_symbol_count(const symbol_table_t *Table) {
assert(Table);
return Table->num_symbol;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(symbol_t*) gp_sym_get_symbol(const symbol_table_t *Table, const char *Name) {
symbol_t *sym;
hash128_t hash;
bool first;
bool prev_case;
assert(Table);
assert(Name);
first = true;
prev_case = false;
while (Table) {
if (first || (Table->case_insensitive != prev_case)) {
hash.reset();
hash.hash(Name,Table->case_insensitive);
}
sym = _get_symbol_from_table(Table, &hash);
if (sym) {
return sym;
}
first = false;
prev_case = Table->case_insensitive;
/* If sym is still NULL, we didn't match. Try the prev table on the stack. */
Table = Table->prev;
}
return NULL;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(symbol_t*) gp_sym_get_symbol_len(const symbol_table_t *Table, const char *Name, size_t Len) {
symbol_t *sym;
hash128_t hash;
bool first;
bool prev_case;
assert(Table);
assert(Name);
first = true;
prev_case = false;
while (Table) {
if (first || (Table->case_insensitive != prev_case)) {
hash.reset();
hash.hash(Name, Len, Table->case_insensitive);
}
sym = _get_symbol_from_table(Table, &hash);
if (sym) {
return sym;
}
first = false;
prev_case = Table->case_insensitive;
/* If sym is still NULL, we didn't match. Try the prev table on the stack. */
Table = Table->prev;
}
return NULL;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(symbol_t*) gp_sym_get_symbol_with_index(const symbol_table_t *Table, size_t Index) {
assert(Table);
assert(Index < Table->num_symbol);
return Table->symbol_array[Index];
}
/*------------------------------------------------------------------------------------------------*/
FUNC(const symbol_t**) gp_sym_clone_symbol_array(const symbol_table_t *Table, symbol_compare_t Cmp) {
assert(Table);
if (!Table->num_symbol) return NULL;
size_t size = Table->num_symbol * sizeof(symbol_t *);
symbol_t**array = new symbol_t*[Table->num_symbol];
memcpy(array, Table->symbol_array, size);
if (Cmp) qsort(array, Table->num_symbol, sizeof(symbol_t*), Cmp);
return (const symbol_t**)array;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(void) gp_sym_annotate_symbol(symbol_t *Sym, void *Value) {
assert(Sym);
Sym->annotation = Value;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(const char*) gp_sym_get_symbol_name(const symbol_t *Sym) {
assert(Sym);
return Sym->name;
}
/*------------------------------------------------------------------------------------------------*/
FUNC(void*) gp_sym_get_symbol_annotation(const symbol_t *Sym) {
assert(Sym);
return Sym->annotation;
}
/*------------------------------------------------------------------------------------------------*/
CFUNC(int) gp_sym_compare_fn(const void *P0, const void *P1) {
const symbol_t &sym0 = **(const symbol_t **)P0;
const symbol_t &sym1 = **(const symbol_t **)P1;
return strcmp(sym0.name, sym1.name);
}
/*------------------------------------------------------------------------------------------------*/
int _cdecl gp_sym_version_compare_fn(const void *P0, const void *P1) {
const symbol_t &sym0 = **(const symbol_t **)P0;
const symbol_t &sym1 = **(const symbol_t **)P1;
return strverscmp(sym0.name, sym1.name);
}
| Detected encoding: UTF-8 | 0
|