mojoshader_common.c
author Ryan C. Gordon <icculus@icculus.org>
Sun, 05 Apr 2009 03:20:53 -0400
changeset 732 e070fea1f8c7
child 733 1b6d68fabe46
permissions -rw-r--r--
Added mojoshader_common.c with first shot at generic hashtable.

#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 ...