1 files changed, 259 insertions, 0 deletions
diff --git a/HashTable.c b/HashTable.c
new file mode 100644
index 0000000..ed49ee7
--- /dev/null
+++ b/HashTable.c
@@ -0,0 +1,259 @@
+#include "HashTable.h"
+#include "Types.h"
+#include <stdio.h>
+#include <string.h>
+
+// Fowler/Noll/Vo 32-bit hash implementation
+// http://www.isthe.com/chongo/tech/comp/fnv/index.html
+// https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1_hash
+
+#define FNV_OFFSET_BASIS 2166136261
+#define FNV_PRIME        16777619
+typedef u32 fnv_int;
+
+static fnv_int fnv1_hash(const char* str) {
+    fnv_int hash = FNV_OFFSET_BASIS;
+    while (*str != '\0') {
+        hash *= FNV_PRIME;
+        hash ^= *(str++);
+    }
+    return hash;
+}
+
+struct HashTableMeta {
+    MemoryManager *mm;
+    usize size;
+    usize count;
+};
+
+static inline struct HashTableMeta*
+H_metadata(HashTable ht) {
+    return ht - sizeof(struct HashTableMeta);
+}
+
+static inline const char**
+H_keys(HashTable ht) {
+    return ht;
+}
+
+static inline void**
+H_vals(HashTable ht) {
+    return ht + H_metadata(ht)->size * sizeof(const char*);
+}
+
+static inline Result
+H_find_hash(HashTable ht, const char *key, fnv_int *hash) {
+    if (NULL == ht || NULL == key)
+        return R_NullArgument;
+
+    struct HashTableMeta *htm = H_metadata(ht);
+
+    *hash = fnv1_hash(key) % htm->size;
+    fnv_int hash_orig = *hash;
+
+    do {
+        if (H_keys(ht)[*hash] == NULL)
+            return R_NotFound;
+
+        if (0 == strcmp(H_keys(ht)[*hash], key))
+            return R_Ok;
+
+        *hash = (*hash + 1) % htm->size;
+    } while (*hash != hash_orig);
+
+    return R_NotFound;
+}
+
+HashTable
+H_new(MemoryManager *mm, usize size) {
+    if (NULL == mm)
+        return NULL;
+
+    struct HashTableMeta htm = {
+        .mm = mm,
+        .size = size,
+        .count = 0,
+    };
+
+    void* start = NULL;
+    if (R_Ok != mm->alloc(*mm, &start, sizeof(htm) + size * sizeof(const char*) + size * sizeof(void*)) ||
+        NULL == start)
+    {
+        return NULL;
+    }
+
+    memcpy(start, &htm, sizeof(htm));
+    start += sizeof(htm);
+    memset(start, 0, size * sizeof(const char*) + size * sizeof(void*));
+
+    return start;
+}
+
+Result
+H_free(HashTable* ht) {
+    if (NULL == ht || NULL == *ht)
+        return R_NullArgument;
+
+    struct HashTableMeta *htm = H_metadata(*ht);
+
+    for (usize i = 0; i < htm->size; ++i) {
+        if (NULL != H_keys(*ht)[i])
+            RETURN_NOTOK(htm->mm->free(*htm->mm, (void**)(H_keys(*ht) + i)));
+    }
+
+    *ht = htm;
+    return htm->mm->free(*htm->mm, ht);
+}
+
+Result
+H_freevals(HashTable* ht) {
+    if (NULL == ht || NULL == *ht)
+        return R_NullArgument;
+
+    struct HashTableMeta *htm = H_metadata(*ht);
+
+    for (usize i = 0; i < htm->size; ++i) {
+        htm->mm->free(*htm->mm, (void**)(H_vals(*ht) + i));
+    }
+
+    return R_Ok;
+}
+
+Result
+H_freeat(HashTable ht, const char* key) {
+    if (NULL == ht || NULL == key)
+        return R_NullArgument;
+
+    fnv_int hash = 0;
+    RETURN_NOTOK(H_find_hash(ht, key, &hash));
+
+    struct HashTableMeta *htm = H_metadata(ht);
+
+    RETURN_NOTOK(htm->mm->free(*htm->mm, H_vals(ht) + hash));
+    RETURN_NOTOK(htm->mm->free(*htm->mm, (void**)(H_keys(ht) + hash)));
+    --htm->count;
+
+    return R_Ok;
+}
+
+usize
+H_size(HashTable ht) {
+    if (NULL == ht)
+        return 0;
+    return H_metadata(ht)->size;
+}
+
+usize
+H_count(HashTable ht) {
+    if (NULL == ht)
+        return 0;
+    return H_metadata(ht)->count;
+}
+
+Result
+H_insert(HashTable ht, const char *key, void *value) {
+    if (NULL == ht || NULL == key)
+        return R_NullArgument;
+
+    struct HashTableMeta *htm = H_metadata(ht);
+
+    if (htm->count >= htm->size)
+        return R_OutOfMemory;
+
+    fnv_int hash = fnv1_hash(key) % htm->size;
+    while (NULL != H_keys(ht)[hash]) {
+        hash = (hash + 1) % htm->size;
+    }
+
+    H_keys(ht)[hash] = M_strdup(*htm->mm, key);
+    H_vals(ht)[hash] = value;
+    ++htm->count;
+
+    return R_Ok;
+}
+
+Result
+H_insertstr(HashTable ht, const char *key, const char *value) {
+    if (NULL == ht || NULL == key)
+        return R_NullArgument;
+
+    MemoryManager *mm = H_metadata(ht)->mm;
+
+    char* copy = M_strdup(*mm, value);
+    Result r = H_insert(ht, key, copy);
+
+    if (R_Ok != r) {
+        mm->free(*mm, (void**)&copy);
+    }
+    return r;
+}
+
+Result
+H_inserti(HashTable ht, const char *key, int value) {
+    if (NULL == ht || NULL == key)
+        return R_NullArgument;
+
+    MemoryManager *mm = H_metadata(ht)->mm;
+
+    int* copy = NULL;
+    RETURN_NOTOK(
+        mm->alloc(*mm, (void**)&copy, sizeof(int)));
+    memcpy(copy, &value, sizeof(int));
+
+    Result r = H_insert(ht, key, copy);
+
+    if (R_Ok != r) {
+        mm->free(*mm, (void**)&copy);
+    }
+
+    return r;
+}
+
+Result
+H_insertf(HashTable ht, const char *key, double value) {
+    if (NULL == ht || NULL == key)
+        return R_NullArgument;
+
+    MemoryManager *mm = H_metadata(ht)->mm;
+
+    float* copy = NULL;
+    RETURN_NOTOK(
+        mm->alloc(*mm, (void**)&copy, sizeof(double)));
+    memcpy(copy, &value, sizeof(double));
+
+    Result r = H_insert(ht, key, copy);
+
+    if (R_Ok != r) {
+        mm->free(*mm, (void**)&copy);
+    }
+    return r;
+}
+
+void*
+H_get(HashTable ht, const char* key) {
+    if (NULL == ht || NULL == key)
+        return NULL;
+
+    struct HashTableMeta *htm = H_metadata(ht);
+
+    fnv_int hash = 0;
+    if (R_Ok != H_find_hash(ht, key, &hash))
+        return NULL;
+
+    return H_vals(ht)[hash];
+}
+
+inline char*
+H_getstr(HashTable ht, const char* key) {
+    return H_get(ht, key);
+}
+
+inline int*
+H_geti(HashTable ht, const char* key) {
+    return H_get(ht, key);
+}
+
+inline double*
+H_getf(HashTable ht, const char* key) {
+    return H_get(ht, key);
+}