5 files changed, 322 insertions, 1 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);
+}
diff --git a/HashTable.h b/HashTable.h
new file mode 100644
index 0000000..d32f890
--- /dev/null
+++ b/HashTable.h
@@ -0,0 +1,24 @@
+#ifndef _HASHTABLE
+#define _HASHTABLE
+
+#include "Types.h"
+#include "MemoryManager.h"
+
+typedef void* HashTable;
+
+HashTable H_new(MemoryManager *mm, usize size);
+Result    H_free(HashTable* ht);
+Result    H_freevals(HashTable* ht);
+Result    H_freeat(HashTable ht, const char *key);
+usize     H_size(HashTable ht);
+usize     H_count(HashTable ht);
+Result    H_insert(HashTable ht, const char *key, void *value);
+Result    H_insertstr(HashTable ht, const char *key, const char *value);
+Result    H_inserti(HashTable ht, const char *key, int value);
+Result    H_insertf(HashTable ht, const char *key, double value);
+void*     H_get(HashTable ht, const char* key);
+char*     H_getstr(HashTable ht, const char* key);
+int*      H_geti(HashTable ht, const char* key);
+double*   H_getf(HashTable ht, const char* key);
+
+#endif /* _HASHTABLE */
diff --git a/MemoryManager.c b/MemoryManager.c
index 98e70e7..53f906e 100644
--- a/MemoryManager.c
+++ b/MemoryManager.c
@@ -1,6 +1,7 @@
 #include "MemoryManager.h"
 #include "Types.h"
 #include <stdlib.h>
+#include <string.h>
 
 Result
 std_alloc(MemoryManager mm, void **ptr, usize size) {
@@ -44,3 +45,19 @@ M_std() {
         .destroy = &std_destroy,
     };
 }
+
+char*
+M_strdup(MemoryManager mm, const char* str) {
+    if (NULL == str)
+        return NULL;
+
+    char* newstr = NULL;
+    if (R_Ok != mm.alloc(mm, (void**)&newstr, strlen(str) + 1) ||
+        NULL == newstr)
+    {
+        return NULL;
+    }
+
+    strcpy(newstr, str);
+    return newstr;
+}
diff --git a/MemoryManager.h b/MemoryManager.h
index 95f864c..3f1461b 100644
--- a/MemoryManager.h
+++ b/MemoryManager.h
@@ -13,4 +13,8 @@ typedef struct MemoryManager {
 
 MemoryManager M_std();
 
+/* Helper functions */
+
+char* M_strdup(MemoryManager mm, const char* str);
+
 #endif /* _MEMORY_MANAGER */
diff --git a/example.c b/example.c
index 4081c21..3b1bbb6 100644
--- a/example.c
+++ b/example.c
@@ -1,3 +1,5 @@
+#include "HashTable.h"
+#include "Types.h"
 #include "Vector.h"
 #include "String.h"
 #include "BumpAlloc.h"
@@ -6,7 +8,7 @@
 int
 main() {
     MemoryManager g = M_bump(KiB(2)),
-                  t = M_bump(KiB(3));
+                  t = M_bump(KiB(4));
 
     String *hexes = V_new(&g, sizeof(String), 8);
 
@@ -26,7 +28,22 @@ main() {
 
     printf("%s", all);
 
+    MemoryManager T = M_std();
+
+    HashTable tet = H_new(&T, 16);
+    PRINT_NOTOK(H_insertstr(tet, "Hello", "World"));
+    PRINT_NOTOK(H_insertf(tet, "a", 1.414));
+    PRINT_NOTOK(H_inserti(tet, "+", 4829));
+
+    printf("Table: %s [%p] %f %d\n",
+           H_getstr(tet, "Hello"), H_getstr(tet, "Hello"),
+           H_getf(tet, "a") == NULL ? 0.0 :  *H_getf(tet, "a"),
+           H_geti(tet, "+") == NULL ? 0    : *H_geti(tet, "+"));
+    PRINT_NOTOK(H_freevals(&tet));
+    PRINT_NOTOK(H_free(&tet));
+
     PRINT_NOTOK(g.destroy(&g));
     PRINT_NOTOK(t.destroy(&t));
+    PRINT_NOTOK(T.destroy(&T));
     return 0;
 }