Add binary tree implementation. NOT TESTED, FULL OF BUGS.

1 files changed, 31 insertions, 0 deletions

diff --git a/src/common/include/btree.h b/src/common/include/btree.h
new file mode 100644
index 0000000..34fd2b3
--- /dev/null
+++ b/src/common/include/btree.h
@@ -0,0 +1,31 @@
+#pragma once
+
+#include <algo.h>
+
+// A btree may contain several bindings for the same key (in that case they are not ordered)
+//	- btree_find returns any item with matching key, or null if none exists
+//	- btree_lower returns any item with matching key, or if none returns last item with smaller key
+//	- btree_upper returns any item with matching key, or if none returns first item with bigger key
+//	- btree_remove removes *all bindings* with matching key
+//	- btree_iter_on calls iterator function on all bindings with matching key
+
+// Memory management is same as for hashtbl (a kv_iter_fun_t is called when an item is released)
+
+struct btree;
+typedef struct btree btree_t;
+
+btree_t* create_btree(key_cmp_fun_t cf, kv_iter_fun_t on_release);
+void delete_btree(btree_t *t);
+
+bool btree_add(btree_t *t, void* key, void* val);
+void btree_remove(btree_t *t, const void* key);
+
+void* btree_find(btree_t *i, const void* key);
+void* btree_lower(btree_t *i, const void* key);
+void* btree_upper(btree_t *i, const void* key);
+void btree_iter(btree_t *i, kv_iter_fun_t f);
+void btree_iter_on(btree_t *i, const void* key, kv_iter_fun_t f);
+
+size_t btree_count(btree_t *i);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/