diff options
author | Katharina Fey <kookie@spacekookie.de> | 2019-07-13 06:40:05 +0100 |
---|---|---|
committer | Katharina Fey <kookie@spacekookie.de> | 2019-07-13 06:47:21 +0100 |
commit | 9130e47b171c5182ffe6c14eb710fdcb73943de4 (patch) | |
tree | ca76fcc58130b53c794c99adc7658b3b51075639 /hash.c | |
parent | d0cca976be6fb90f3724911c8a124bce56b3c5f9 (diff) |
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.
Diffstat (limited to 'hash.c')
-rw-r--r-- | hash.c | 73 |
1 files changed, 73 insertions, 0 deletions
@@ -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; +} + |