1 files changed, 61 insertions, 0 deletions
diff --git a/include/kpl/tree.h b/include/kpl/tree.h
new file mode 100644
index 0000000..8e52524
--- /dev/null
+++ b/include/kpl/tree.h
@@ -0,0 +1,61 @@
+/*
+ * KPL tree
+ */
+
+#pragma once
+
+// tree_duplicate is a linked stack
+#define KPL_TREE_HEADER(STRUCT_NAME) \
+    struct STRUCT_NAME *tree_left, *tree_right, *tree_duplicate; \
+    int32_t tree_height
+
+/*
+ * Recursive AVL saves 8 bytes per object (no need for parent pointer) and keeps the insertion and finding simple
+ */
+typedef struct _kpl_tree_node {
+    KPL_TREE_HEADER(_kpl_tree_node);
+} kpl_tree_node;
+
+typedef enum : int32_t {
+   KPL_TREE_TREE_HEIGHT_INIT = 1
+} kpl_tree_enum;
+
+/*
+ * -1 search left, 1 search right, 0 found
+ */
+typedef int32_t kpl_tree_node_compare_fn(const void *node_a, const void *node_b);
+
+typedef void kpl_tree_node_free_fn(void *node);
+
+/*
+ * KPL needs tree with insertion and find operations, deletion is not needed, all nodes are freed on tree free
+ */
+typedef struct {
+    kpl_tree_node *root_node;
+    kpl_tree_node_compare_fn *node_compare_fn;
+    kpl_tree_node_free_fn *node_free_fn;
+} kpl_tree;
+
+#define KPL_TREE_INIT_STATIC(COMPARE_FN, FREE_FN) \
+    (kpl_tree) { .root_node = NULL, .node_compare_fn = COMPARE_FN, .node_free_fn = FREE_FN }
+
+inline void kpl_tree_init(kpl_tree *tree, kpl_tree_node_compare_fn node_compare_fn,
+    kpl_tree_node_free_fn node_free_fn) {
+    tree->root_node = NULL;
+    tree->node_compare_fn = node_compare_fn;
+    tree->node_free_fn = node_free_fn;
+}
+
+void kpl_tree_free(kpl_tree *tree);
+
+/*
+ * *find is stack allocated
+ * NULL for not found
+ */
+void *kpl_tree_find(kpl_tree *tree, const void *find_node);
+
+/*
+ * *insert is heap allocated
+ * All inserts succeed, duplicates are added to *tree_duplicate
+ */
+void kpl_tree_insert(kpl_tree *tree, void *insert_node);