From 9130e47b171c5182ffe6c14eb710fdcb73943de4 Mon Sep 17 00:00:00 2001 From: Katharina Fey 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. --- bowl.c | 19 ++++++++++++++++--- 1 file changed, 16 insertions(+), 3 deletions(-) (limited to 'bowl.c') diff --git a/bowl.c b/bowl.c index 4eeeb59..3cb36b9 100644 --- a/bowl.c +++ b/bowl.c @@ -1,5 +1,6 @@ #include "bowl.h" #include "array.h" +#include "hash.h" #include #include @@ -37,7 +38,7 @@ err_t bowl_malloc(struct bowl **ptr, bowl_t type) return OK; } -err_t bowl_insert(struct bowl *self, struct bowl *new) +err_t bowl_append(struct bowl *self, struct bowl *new) { CHECK(self, INVALID_PARAMS) CHECK(new, INVALID_PARAMS) @@ -52,7 +53,19 @@ err_t bowl_insert(struct bowl *self, struct bowl *new) return OK; } -err_t bowl_insert_key(struct bowl *self, size_t idx, struct bowl *child) +err_t bowl_insert_key(struct bowl *self, char *key, struct bowl *child) +{ + CHECK(self, INVALID_PARAMS) + CHECK(child, INVALID_PARAMS) + CHECK(key, INVALID_PARAMS) + + switch(self->type) { + case HASH: return hash_insert_key(self, key, child); + default: return INVALID_PARAMS; + } +} + +err_t bowl_insert_idx(struct bowl *self, size_t idx, struct bowl *child) { CHECK(self, INVALID_PARAMS) CHECK(child, INVALID_PARAMS) @@ -66,7 +79,7 @@ err_t bowl_insert_key(struct bowl *self, size_t idx, struct bowl *child) } } -err_t bowl_swap_key(struct bowl *self, size_t idx, struct bowl *child, struct bowl **prev) +err_t bowl_swap_idx(struct bowl *self, size_t idx, struct bowl *child, struct bowl **prev) { CHECK(self, INVALID_PARAMS) CHECK(child, INVALID_PARAMS) -- cgit v1.2.3