From 9130e47b171c5182ffe6c14eb710fdcb73943de4 Mon Sep 17 00:00:00 2001
From: Katharina Fey <kookie@spacekookie.de>
Date: Sat, 13 Jul 2019 06:40:05 +0100
Subject: Adding initial support for HASH nodes

This PR adds initial support for HASH data nodes in libbowl.
This allows a performant key-value store lookup in a node tree.
The hashing code implements the "murmur" hash, which has shown
good performance over at [`libcuckoo`]. Currently there is no
extended hashing strategy, which should definitely be changed.

[`libcuckoo`]: https://github.com/qaul/libcuckoo

(currently a collision will cause a recursive re-alloc)

Some of the type-level hacks also begs the question if a PAIR
data node might be warranted, even though it would break the
simple design around bowl->data.
---
 hash.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 73 insertions(+)
 create mode 100644 hash.c

(limited to 'hash.c')

diff --git a/hash.c b/hash.c
new file mode 100644
index 0000000..689bf18
--- /dev/null
+++ b/hash.c
@@ -0,0 +1,73 @@
+#include "bowl.h"
+#include "array.h"
+#include "hash.h"
+#include "utils.h"
+
+#include <malloc.h>
+
+typedef struct {
+    char *key;
+    struct bowl *data;
+} hash_item;
+
+err_t hash_insert_key(struct bowl *self, char *key, struct bowl *child)
+{
+    CHECK(self, INVALID_STATE)
+    CHECK(child, INVALID_STATE)
+    CHECK(key, INVALID_STATE)
+
+    // Even though we're a HASH node, we use an array under the hood
+    struct bowl_arr *arr = self->_pl.array;
+    CHECK(arr, INVALID_STATE)
+
+    size_t idx;
+    err_t e = _hash(key, arr->size, &idx);
+    if(e) return e;
+
+    // If the index is used, rescale and try again
+    if(arr->ptr[idx] != NULL) {
+        struct bowl *prev = self;
+
+        // Allocate new array
+        e = array_malloc(self, arr->size * 2);
+        if(e) return e;
+
+        for(int i = 0; i < arr->size; i++) {
+            if(arr->ptr[i] != NULL) {
+                // FIXME: This is horrible
+                hash_item *item = (hash_item*) arr->ptr[i];
+                e = hash_insert_key(self, item->key, item->data);
+                if(e) return e;
+            }
+        }
+
+        e = array_free(prev);
+        if(e) return e;
+        
+        e = hash_insert_key(self, key, child);
+        if(e) return e;
+
+    } else {
+        hash_item *item = malloc(sizeof(hash_item));
+        CHECK(item, MALLOC_FAILED)
+
+        item->key = calloc(sizeof(char), REAL_STRLEN(key));
+        CHECK(item->key, MALLOC_FAILED)
+        strcpy(item->key, key);
+
+        item->data = child;
+
+        arr->ptr[idx] = (struct bowl*) item;
+    }
+
+    return OK;
+}
+
+err_t hash_remove_key(struct bowl *self, char *key, struct bowl **child)
+{
+    CHECK(self, INVALID_STATE)
+    CHECK(key, INVALID_STATE)
+
+    return OK;
+}
+ 
-- 
cgit v1.2.3