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 /bowl.h | |
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 'bowl.h')
-rw-r--r-- | bowl.h | 19 |
1 files changed, 11 insertions, 8 deletions
@@ -12,7 +12,7 @@ extern "C" { #define CHECK(ptr, err) if(!ptr) return err; /** Define some generic error codes first that we can propagate **/ -typedef enum err_t { +typedef enum { OK = 0, ERR = -1, NOT_IMPLEMENTED = 1, // A runtime error for missing features @@ -22,7 +22,7 @@ typedef enum err_t { INVALID_STATE = 4, // Calling an operation on an invalid state } err_t; -typedef enum data_t { +typedef enum { LITERAL, // Any string that is \0 terminated INTEGER, // Integer value REAL, // Floating point value @@ -30,7 +30,7 @@ typedef enum data_t { RAW // A platform-length pointer } data_t; -typedef enum bowl_t { +typedef enum { LEAF = 1, ARRAY, HASH, LINKED } bowl_t; @@ -67,14 +67,17 @@ struct b_ptr { /// Allocate memory for an new, empty bowl node err_t bowl_malloc(struct bowl **, bowl_t); -/// Insert one node into another -err_t bowl_insert(struct bowl *, struct bowl *); +/// Insert one node at the end of another +err_t bowl_append(struct bowl *, struct bowl *); + +/// Insert a node under a specific key (relevant for HASH nodes) +err_t bowl_insert_key(struct bowl *, char *key, struct bowl *); /// Insert a node into a specific index of another node -err_t bowl_insert_key(struct bowl *, size_t idx, struct bowl *); +err_t bowl_insert_idx(struct bowl *, size_t idx, struct bowl *); /// Insert and swap a key in place, returning the old one -err_t bowl_swap_key(struct bowl *, size_t idx, struct bowl *, struct bowl **); +err_t bowl_swap_idx(struct bowl *, size_t idx, struct bowl *, struct bowl **); /// Remove a bowl node by it's pointer reference err_t bowl_remove(struct bowl *, struct bowl *); @@ -94,4 +97,4 @@ err_t data_free(struct data *); #ifdef __cplusplus } #endif -#endif // _BOWL_H_
\ No newline at end of file +#endif // _BOWL_H_ |