From 5c165c012408b9e02f3017d3d2f3bc9b3256b58e Mon Sep 17 00:00:00 2001
From: Sam Lantinga <[EMAIL REDACTED]>
Date: Thu, 20 Oct 2011 02:23:01 -0400
Subject: [PATCH] Added Ryan's simple hashtable implementation. Did I mention
Ryan rocks? :) This will be used to cache strings in the font server once the
1.3 conversion is complete.
---
Makefile.am | 2 +
hashtable.c | 188 ++++++++++++++++++++++++++++++++++++++++++++++++++++
hashtable.h | 40 +++++++++++
3 files changed, 230 insertions(+)
create mode 100644 hashtable.c
create mode 100644 hashtable.h
diff --git a/Makefile.am b/Makefile.am
index 814b0ea4..11461d80 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -15,6 +15,8 @@ Maelstrom_SOURCES = \
dialog.h \
fastrand.cpp \
fastrand.h \
+ hashtable.c \
+ hashtable.h \
init.cpp \
load.cpp \
load.h \
diff --git a/hashtable.c b/hashtable.c
new file mode 100644
index 00000000..d991e57d
--- /dev/null
+++ b/hashtable.c
@@ -0,0 +1,188 @@
+/*
+ This software is provided 'as-is', without any express or implied
+ warranty. In no event will the authors be held liable for any damages
+ arising from the use of this software.
+
+ Permission is granted to anyone to use this software for any purpose,
+ including commercial applications, and to alter it and redistribute it
+ freely, subject to the following restrictions:
+
+ 1. The origin of this software must not be misrepresented; you must not
+ claim that you wrote the original software. If you use this software
+ in a product, an acknowledgment in the product documentation would be
+ appreciated but is not required.
+ 2. Altered source versions must be plainly marked as such, and must not be
+ misrepresented as being the original software.
+ 3. This notice may not be removed or altered from any source distribution.
+*/
+#include <stdlib.h>
+#include <string.h>
+
+#include "hashtable.h"
+
+typedef struct HashItem
+{
+ const void *key;
+ const void *value;
+ struct HashItem *next;
+} HashItem;
+
+struct HashTable
+{
+ HashItem **table;
+ unsigned table_len;
+ void *data;
+ HashTable_HashFn hash;
+ HashTable_KeyMatchFn keymatch;
+ HashTable_NukeFn nuke;
+};
+
+static inline unsigned 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;
+ void *data = table->data;
+ const unsigned hash = calc_hash(table, key);
+ HashItem *prev = NULL;
+ for (i = table->table[hash]; i != NULL; i = i->next)
+ {
+ 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.
+ if (prev != NULL)
+ {
+ prev->next = i->next;
+ i->next = table->table[hash];
+ table->table[hash] = i;
+ } // if
+
+ return 1;
+ } // if
+
+ prev = i;
+ } // for
+
+ return 0;
+} // hash_find
+
+int hash_insert(HashTable *table, const void *key, const void *value)
+{
+ HashItem *item = NULL;
+ const unsigned hash = calc_hash(table, key);
+ if (hash_find(table, key, NULL))
+ return 0;
+
+ // !!! FIXME: grow and rehash table if it gets too saturated.
+ item = (HashItem *) malloc(sizeof (HashItem));
+ 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_remove(HashTable *table, const void *key)
+{
+ HashItem *item = NULL;
+ HashItem *prev = NULL;
+ void *data = table->data;
+ const unsigned hash = calc_hash(table, key);
+ for (item = table->table[hash]; item != NULL; item = item->next)
+ {
+ 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, data);
+ free(item);
+ return 1;
+ } // if
+
+ prev = item;
+ } // for
+
+ return 0;
+} // hash_remove
+
+HashTable *hash_create(void *data, const HashTable_HashFn hashfn,
+ const HashTable_KeyMatchFn keymatchfn,
+ const HashTable_NukeFn nukefn)
+{
+ const unsigned initial_table_size = 256;
+ const unsigned alloc_len = sizeof (HashItem *) * initial_table_size;
+ HashTable *table = (HashTable *) malloc(sizeof (HashTable));
+ if (table == NULL)
+ return NULL;
+ memset(table, '\0', sizeof (HashTable));
+
+ table->table = (HashItem **) malloc(alloc_len);
+ if (table->table == NULL)
+ {
+ free(table);
+ return NULL;
+ } // if
+
+ memset(table->table, '\0', alloc_len);
+ table->table_len = initial_table_size;
+ table->data = data;
+ table->hash = hashfn;
+ table->keymatch = keymatchfn;
+ table->nuke = nukefn;
+ return table;
+} // hash_create
+
+void hash_destroy(HashTable *table)
+{
+ unsigned i;
+ void *data = table->data;
+ 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, data);
+ free(item);
+ item = next;
+ } // while
+ } // for
+
+ free(table->table);
+ free(table);
+} // hash_destroy
+
+
+// this is djb's xor hashing function.
+static inline unsigned hash_string_djbxor(const char *str, size_t len)
+{
+ register unsigned hash = 5381;
+ while (len--)
+ hash = ((hash << 5) + hash) ^ *(str++);
+ return hash;
+} // hash_string_djbxor
+
+unsigned hash_hash_string(const void *sym, void *data)
+{
+ (void) data;
+ return hash_string_djbxor((const char*) sym, strlen((const char *) sym));
+} // hash_hash_string
+
+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
diff --git a/hashtable.h b/hashtable.h
new file mode 100644
index 00000000..e11b28c9
--- /dev/null
+++ b/hashtable.h
@@ -0,0 +1,40 @@
+/*
+ This software is provided 'as-is', without any express or implied
+ warranty. In no event will the authors be held liable for any damages
+ arising from the use of this software.
+
+ Permission is granted to anyone to use this software for any purpose,
+ including commercial applications, and to alter it and redistribute it
+ freely, subject to the following restrictions:
+
+ 1. The origin of this software must not be misrepresented; you must not
+ claim that you wrote the original software. If you use this software
+ in a product, an acknowledgment in the product documentation would be
+ appreciated but is not required.
+ 2. Altered source versions must be plainly marked as such, and must not be
+ misrepresented as being the original software.
+ 3. This notice may not be removed or altered from any source distribution.
+*/
+
+#ifndef _hashtable_h
+#define _hashtable_h
+
+// Hashtables...
+
+typedef struct HashTable HashTable;
+typedef unsigned (*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);
+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);
+
+unsigned hash_hash_string(const void *sym, void *unused);
+int hash_keymatch_string(const void *a, const void *b, void *unused);
+
+#endif // _hashtable_h