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