Added mojoshader_common.c with first shot at generic hashtable.

icculus · Apr 5, 2009 · 493d81c · 493d81c
1 parent fb5c6ee
commit 493d81c
Show file tree

Hide file tree

Showing 3 changed files with 153 additions and 0 deletions.
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -63,6 +63,7 @@ ADD_CUSTOM_COMMAND(
 
 ADD_LIBRARY(mojoshader STATIC
     mojoshader.c
+    mojoshader_common.c
     mojoshader_compiler.c
     mojoshader_preprocessor.c
     mojoshader_lexer.c

diff --git a/mojoshader_common.c b/mojoshader_common.c
@@ -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 ...
+
diff --git a/mojoshader_internal.h b/mojoshader_internal.h
@@ -124,6 +124,26 @@ static inline int Min(const int a, const int b)
     return ((a < b) ? a : b);
 } // Min
 
+
+// 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);
+
+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);
+void hash_deinit(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);
+
+
 // This is the ID for a D3DXSHADER_CONSTANTTABLE in the bytecode comments.
 #define CTAB_ID 0x42415443  // 0x42415443 == 'CTAB'
 #define CTAB_SIZE 28  // sizeof (D3DXSHADER_CONSTANTTABLE).