diff options
Diffstat (limited to 'klib/rbtree.h')
-rw-r--r-- | klib/rbtree.h | 48 |
1 files changed, 48 insertions, 0 deletions
diff --git a/klib/rbtree.h b/klib/rbtree.h new file mode 100644 index 0000000..4376713 --- /dev/null +++ b/klib/rbtree.h @@ -0,0 +1,48 @@ +#ifndef JOVE_LIB_RBTREE_H +#define JOVE_LIB_RBTREE_H 1 + +#include <stdint.h> +#include <stddef.h> +#include <stdbool.h> +#include "memory.h" + +typedef struct rbnode +{ + struct rbnode *parent; + struct rbnode *children[2]; + intmax_t key; + bool color; + char data[]; +} rbnode_t; + +typedef struct rbtree +{ + rbnode_t *root; + size_t objw; +} rbtree_t; + +/**Instantiate a new tree based on the given type. + * @param tree to instantiate into. + * @param type to instantiate for.*/ +#define rbtree_new(tree, type) __rbtree_new(tree, sizeof(type)) +void __rbtree_new(rbtree_t *tree, size_t objw); + +/**Find the data corresponding to the key in the tree. + * usage: rbtree_find(type)(tree, key); + * @param tree to search through. + * @param key to search for. + * @return */ +void *rbtree_find(rbtree_t *tree, intmax_t key); + +/**Insert a value into the given tree using the given key. + * If the key is already present within the tree, the existing data is + * overwritten. + * @param tree to insert into. + * @param key to insert. + * @param value to insert. + * @return pointer to inserted data. + * */ +void *rbtree_insert(rbtree_t *tree, intmax_t key, void *value); +void *rbtree_reserve(rbtree_t *tree, intmax_t key); + +#endif |