Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Added mojoshader_common.c with first shot at generic hashtable.
- Loading branch information
Showing
3 changed files
with
153 additions
and
0 deletions.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,132 @@ | ||
#define __MOJOSHADER_INTERNAL__ 1 | ||
#include "mojoshader_internal.h" | ||
|
||
typedef struct HashItem | ||
{ | ||
const void *key; | ||
const void *value; | ||
struct HashItem *next; | ||
} HashItem; | ||
|
||
struct HashTable | ||
{ | ||
HashItem **table; | ||
uint32 table_len; | ||
int stackable; | ||
HashTable_HashFn hash; | ||
HashTable_KeyMatchFn keymatch; | ||
HashTable_NukeFn nuke; | ||
MOJOSHADER_malloc malloc; | ||
MOJOSHADER_free free; | ||
void *malloc_data; | ||
}; | ||
|
||
int hash_find(const HashTable *table, const void *key, const void **_value) | ||
{ | ||
HashItem *i; | ||
const uint32 hash = table->hash(key) & table->table_len; | ||
for (i = table->table[hash]; i != NULL; i = i->next) | ||
{ | ||
if (table->keymatch(key, i->key)) | ||
{ | ||
if (_value != NULL) | ||
*_value = i->value; | ||
return 1; | ||
} // if | ||
} // for | ||
|
||
return 0; | ||
} // hash_find | ||
|
||
int hash_insert(HashTable *table, const void *key, const void *value) | ||
{ | ||
HashItem *item = NULL; | ||
const uint32 hash = table->hash(key) & table->table_len; | ||
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); | ||
if (item == NULL) | ||
return -1; | ||
|
||
item->key = key; | ||
item->value = value; | ||
item->next = table->table[hash]; | ||
table->table[hash] = item; | ||
|
||
return 1; | ||
} // hash_insert | ||
|
||
int hash_init(HashTable *table, 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) | ||
{ | ||
const uint32 alloc_len = sizeof (HashItem *) * initial_table_size; | ||
|
||
memset(table, '\0', sizeof (HashTable)); | ||
table->table = (HashItem **) m(alloc_len, d); | ||
if (table->table == NULL) | ||
return 0; | ||
|
||
memset(table->table, '\0', alloc_len); | ||
table->table_len = initial_table_size; | ||
table->stackable = stackable; | ||
table->hash = hashfn; | ||
table->keymatch = keymatchfn; | ||
table->nuke = nukefn; | ||
table->malloc = m; | ||
table->free = f; | ||
table->malloc_data = d; | ||
return 1; | ||
} // hash_init | ||
|
||
void hash_deinit(HashTable *table) | ||
{ | ||
uint32 i; | ||
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); | ||
item = next; | ||
} // while | ||
} // for | ||
|
||
table->free(table->table, table->malloc_data); | ||
memset(table, '\0', sizeof (HashTable)); | ||
} // hash_deinit | ||
|
||
int hash_remove(HashTable *table, const void *key) | ||
{ | ||
HashItem *item = NULL; | ||
HashItem *prev = NULL; | ||
const uint32 hash = table->hash(key) & table->table_len; | ||
for (item = table->table[hash]; item != NULL; item = item->next) | ||
{ | ||
if (table->keymatch(key, item->key)) | ||
{ | ||
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); | ||
return 1; | ||
} // if | ||
|
||
prev = item; | ||
} // for | ||
|
||
return 0; | ||
} // hash_remove | ||
|
||
// end of mojoshader_common.c ... | ||
|
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters