Skip to content

Commit

Permalink
Implemented StringMap, for future use.
Browse files Browse the repository at this point in the history
  • Loading branch information
@icculus
icculus committed Feb 24, 2010
1 parent 7fa864c commit 03afe4f
Show file tree
Hide file tree
Showing 3 changed files with 132 additions and 37 deletions.
132 changes: 109 additions & 23 deletions mojoshader_common.c
View file
Expand Up @@ -13,26 +13,47 @@ struct HashTable
HashItem **table;
uint32 table_len;
int stackable;
void *data;
HashTable_HashFn hash;
HashTable_KeyMatchFn keymatch;
HashTable_NukeFn nuke;
MOJOSHADER_malloc malloc;
MOJOSHADER_free free;
void *malloc_data;
MOJOSHADER_malloc m;
MOJOSHADER_free f;
void *d;
};

static inline uint32 calc_hash(const HashTable *table, const void *key)
{
return table->hash(key, table->data) & (table->table_len-1);
} // calc_hash

int hash_find(const HashTable *table, const void *key, const void **_value)
{
HashItem *i;
const uint32 hash = table->hash(key) & table->table_len;
void *data = table->data;
const uint32 hash = calc_hash(table, key);
HashItem *prev = NULL;
for (i = table->table[hash]; i != NULL; i = i->next)
{
if (table->keymatch(key, i->key))
if (table->keymatch(key, i->key, data))
{
if (_value != NULL)
*_value = i->value;

// Matched! Move to the front of list for faster lookup next time.
// (stackable tables have to remain in the same order, though!)
if ((!table->stackable) && (prev != NULL))
{
assert(prev->next == i);
prev->next = i->next;
i->next = table->table[hash];
table->table[hash] = i;
} // if

return 1;
} // if

prev = i;
} // for

return 0;
Expand All @@ -41,12 +62,12 @@ int hash_find(const HashTable *table, const void *key, const void **_value)
int hash_insert(HashTable *table, const void *key, const void *value)
{
HashItem *item = NULL;
const uint32 hash = table->hash(key) & table->table_len;
const uint32 hash = calc_hash(table, key);
if ( (!table->stackable) && (hash_find(table, key, NULL)) )
return 0;

// !!! FIXME: grow and rehash table if it gets too saturated.
item = (HashItem *) table->malloc(sizeof (HashItem), table->malloc_data);
item = (HashItem *) table->m(sizeof (HashItem), table->d);
if (item == NULL)
return -1;

Expand All @@ -58,13 +79,13 @@ int hash_insert(HashTable *table, const void *key, const void *value)
return 1;
} // hash_insert

HashTable *hash_create(const uint32 initial_table_size,
const HashTable_HashFn hashfn,
HashTable *hash_create(void *data, const HashTable_HashFn hashfn,
const HashTable_KeyMatchFn keymatchfn,
const HashTable_NukeFn nukefn,
const int stackable,
MOJOSHADER_malloc m, MOJOSHADER_free f, void *d)
{
const uint32 initial_table_size = 256;
const uint32 alloc_len = sizeof (HashItem *) * initial_table_size;
HashTable *table = (HashTable *) m(sizeof (HashTable), d);
if (table == NULL)
Expand All @@ -81,50 +102,55 @@ HashTable *hash_create(const uint32 initial_table_size,
memset(table->table, '\0', alloc_len);
table->table_len = initial_table_size;
table->stackable = stackable;
table->data = data;
table->hash = hashfn;
table->keymatch = keymatchfn;
table->nuke = nukefn;
table->malloc = m;
table->free = f;
table->malloc_data = d;
table->m = m;
table->f = f;
table->d = d;
return table;
} // hash_create

void hash_destroy(HashTable *table)
{
uint32 i;
void *data = table->data;
MOJOSHADER_free f = table->f;
void *d = table->d;
for (i = 0; i < table->table_len; i++)
{
HashItem *item = table->table[i];
while (item != NULL)
{
HashItem *next = item->next;
table->nuke(item->key, item->value);
table->free(item, table->malloc_data);
table->nuke(item->key, item->value, data);
f(item, d);
item = next;
} // while
} // for

table->free(table->table, table->malloc_data);
table->free(table, table->malloc_data);
f(table->table, d);
f(table, d);
} // hash_destroy

int hash_remove(HashTable *table, const void *key)
{
HashItem *item = NULL;
HashItem *prev = NULL;
const uint32 hash = table->hash(key) & table->table_len;
void *data = table->data;
const uint32 hash = calc_hash(table, key);
for (item = table->table[hash]; item != NULL; item = item->next)
{
if (table->keymatch(key, item->key))
if (table->keymatch(key, item->key, data))
{
if (prev != NULL)
prev->next = item->next;
else
table->table[hash] = item->next;

table->nuke(item->key, item->value);
table->free(item, table->malloc_data);
table->nuke(item->key, item->value, data);
table->f(item, table->d);
return 1;
} // if

Expand All @@ -149,18 +175,78 @@ static inline uint32 hash_string(const char *str, size_t len)
return hash_string_djbxor(str, len);
} // hash_string

uint32 hash_hash_string(const void *sym)
uint32 hash_hash_string(const void *sym, void *data)
{
(void) data;
return hash_string(sym, strlen(sym));
} // hash_hash_string

int hash_keymatch_string(const void *a, const void *b)
int hash_keymatch_string(const void *a, const void *b, void *data)
{
(void) data;
return (strcmp((const char *) a, (const char *) b) == 0);
} // hash_keymatch_string


// The string cache...
// string -> string map...

static void stringmap_nuke_noop(const void *key, const void *val, void *d) {}

static void stringmap_nuke(const void *key, const void *val, void *d)
{
StringMap *smap = (StringMap *) d;
smap->f((void *) key, smap->d);
smap->f((void *) val, smap->d);
} // stringmap_nuke

StringMap *stringmap_create(const int copy, MOJOSHADER_malloc m,
MOJOSHADER_free f, void *d)
{
HashTable_NukeFn nuke = copy ? stringmap_nuke : stringmap_nuke_noop;
StringMap *smap;
smap = hash_create(0,hash_hash_string,hash_keymatch_string,nuke,0,m,f,d);
smap->data = smap;
return smap;
} // stringmap_create

void stringmap_destroy(StringMap *smap)
{
return hash_destroy(smap);
} // stringmap_destroy

int stringmap_insert(StringMap *smap, const char *key, const char *value)
{
assert(key != NULL);
if (smap->nuke == stringmap_nuke_noop) // no copy?
return hash_insert(smap, key, value);

int rc = -1;
char *k = (char *) smap->m(strlen(key) + 1, smap->d);
char *v = (char *) v ? smap->m(strlen(value) + 1, smap->d) : NULL;
if ( (!k) || ((!v) && (value)) || ((rc = hash_insert(smap, k, v)) <= 0) )
{
smap->f(k, smap->d);
smap->f(v, smap->d);
} // if

return rc;
} // stringmap_insert

int stringmap_remove(StringMap *smap, const char *key)
{
return hash_remove(smap, key);
} // stringmap_remove

int stringmap_find(const StringMap *smap, const char *key, const char **_value)
{
const void *value = NULL;
const int retval = hash_find(smap, key, &value);
*_value = (const char *) value;
return retval;
} // stringmap_find


// The string cache... !!! FIXME: use StringMap internally for this.

typedef struct StringBucket
{
Expand Down
4 changes: 2 additions & 2 deletions mojoshader_compiler.c
View file
Expand Up @@ -587,14 +587,14 @@ static void fail(Context *ctx, const char *str)
} // fail


static void usertypemap_nuke(const void *k, const void *v) { /* no-op. */ }
static void usertypemap_nuke(const void *k, const void *v, void *d) {/*no-op*/}

static int create_usertypemap(Context *ctx)
{
UserTypeMap *map = &ctx->usertypes;

map->scope = NULL;
map->types = hash_create(255, hash_hash_string, hash_keymatch_string,
map->types = hash_create(ctx, hash_hash_string, hash_keymatch_string,
usertypemap_nuke, 1, ctx->malloc, ctx->free,
ctx->malloc_data);
if (!map->types)
Expand Down
33 changes: 21 additions & 12 deletions mojoshader_internal.h
View file
Expand Up @@ -154,23 +154,32 @@ static inline int Min(const int a, const int b)
// Hashtables...

typedef struct HashTable HashTable;
typedef uint32 (*HashTable_HashFn)(const void *key);
typedef int (*HashTable_KeyMatchFn)(const void *a, const void *b);
typedef void (*HashTable_NukeFn)(const void *key, const void *value);

HashTable *hash_create(const uint32 initial_table_size,
const HashTable_HashFn hashfn,
const HashTable_KeyMatchFn keymatchfn,
const HashTable_NukeFn nukefn,
const int stackable,
MOJOSHADER_malloc m, MOJOSHADER_free f, void *d);
typedef uint32 (*HashTable_HashFn)(const void *key, void *data);
typedef int (*HashTable_KeyMatchFn)(const void *a, const void *b, void *data);
typedef void (*HashTable_NukeFn)(const void *key, const void *value, void *data);

HashTable *hash_create(void *data, const HashTable_HashFn hashfn,
const HashTable_KeyMatchFn keymatchfn,
const HashTable_NukeFn nukefn,
const int stackable,
MOJOSHADER_malloc m, MOJOSHADER_free f, void *d);
void hash_destroy(HashTable *table);
int hash_insert(HashTable *table, const void *key, const void *value);
int hash_remove(HashTable *table, const void *key);
int hash_find(const HashTable *table, const void *key, const void **_value);

uint32 hash_hash_string(const void *sym);
int hash_keymatch_string(const void *a, const void *b);
uint32 hash_hash_string(const void *sym, void *unused);
int hash_keymatch_string(const void *a, const void *b, void *unused);


// String -> String map ...
typedef HashTable StringMap;
StringMap *stringmap_create(const int copy, MOJOSHADER_malloc m,
MOJOSHADER_free f, void *d);
void stringmap_destroy(StringMap *smap);
int stringmap_insert(StringMap *smap, const char *key, const char *value);
int stringmap_remove(StringMap *smap, const char *key);
int stringmap_find(const StringMap *smap, const char *key, const char **_val);


// String caching...
Expand Down

0 comments on commit 03afe4f

Please sign in to comment.