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

3 files changed, 79 insertions, 23 deletions

diff --git a/src/common/include/algo.h b/src/common/include/algo.h
new file mode 100644
index 0000000..80af052
--- /dev/null
+++ b/src/common/include/algo.h
@@ -0,0 +1,37 @@
+#pragma once
+
+#include <stdint.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+#define MIN(a, b)   ((a)<(b)?(a):(b))
+#define MAX(a, b)   ((a)>(b)?(a):(b))
+#define ABS(a)		((a)<0?-(a):(a))
+
+// ============================================================= //
+// FUNCTION TYPES FOR KEY-VALUE DATA STRUCTURES (HASHTBL, BTREE) //
+
+typedef uint32_t hash_t;
+typedef hash_t (*hash_fun_t)(const void*);
+
+typedef int (*key_cmp_fun_t)(const void*, const void*);
+typedef bool (*key_eq_fun_t)(const void*, const void*);
+
+typedef void (*kv_iter_fun_t)(void* key, void* value);
+
+// void* is considered as an unsigned integer (and not a pointer)
+hash_t id_hash_fun(const void* v);
+bool id_key_eq_fun(const void* a, const void* b);
+int id_key_cmp_fun(const void* a, const void* b);
+
+// void* considered as char*
+hash_t str_hash_fun(const void* v);
+bool str_key_eq_fun(const void* a, const void* b);
+int str_key_cmp_fun(const void* a, const void* b);
+
+// Freeing functions (they are of type kv_iter_fun_t)
+void free_key(void* key, void* val);
+void free_val(void* key, void* val);
+void free_key_val(void* key, void* val);
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
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 :*/
diff --git a/src/common/include/hashtbl.h b/src/common/include/hashtbl.h
index 46f2978..818cfa0 100644
--- a/src/common/include/hashtbl.h
+++ b/src/common/include/hashtbl.h
@@ -1,42 +1,30 @@
 #pragma once
 
-#include <stdint.h>
-#include <stddef.h>
-#include <stdbool.h>
+#include <algo.h>
 
 // Simple hashtable structure (key -> void*)
-// Supports adding, seeking, removing
+// Supports adding, seeking, removing, iterating
 // When adding a binding to the table, the previous binding for same key (if exists) is removed
 
 // The hashtbl is allocated with malloc/free
-// The keys are not copied in any way by the hashtbl, but there might still be something
-// to free, so the create_hashtbl function is given a key freeing function, usually
-// null when no freeing is required, or the standard free function.
+// The keys/values are not copied by the hastbl, but when a key/value pair is removed from the
+// table some operations may be required (freeing memory), so a kv_iter_fun_t is passed when the
+// table is created which will be called whenever a k/v is released (on hashtbl_remove and delete_hashtbl)
+
+// A hashtbl may have only one binding for a given key (on add, previous binding is removed if necessary)
 
 struct hashtbl;
 typedef struct hashtbl hashtbl_t;
 
-typedef size_t hash_t;
-typedef hash_t (*hash_fun_t)(const void*);
-typedef bool (*key_eq_fun_t)(const void*, const void*);
-typedef void (*kv_iter_fun_t)(void* key, void* value);
-
-hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, kv_iter_fun_t on_release);	// 0 -> default size
+hashtbl_t* create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, kv_iter_fun_t on_release);
 void delete_hashtbl(hashtbl_t* ht);
 
 bool hashtbl_add(hashtbl_t* ht, void* key, void* v);	// true = ok, false on error (OOM for instance)
-void* hashtbl_find(hashtbl_t* ht, const void* key);		// null when not found
 void hashtbl_remove(hashtbl_t* ht, const void* key);
-size_t hashtbl_count(hashtbl_t* ht);
-void hashtbl_iter(hashtbl_t* ht, kv_iter_fun_t f);
 
-hash_t id_hash_fun(const void* v);
-hash_t str_hash_fun(const void* v);
-bool id_key_eq_fun(const void* a, const void* b);
-bool str_key_eq_fun(const void* a, const void* b);
+void* hashtbl_find(hashtbl_t* ht, const void* key);		// null when not found
+void hashtbl_iter(hashtbl_t* ht, kv_iter_fun_t f);
 
-void free_key(void* key, void* val);
-void free_val(void* key, void* val);
-void free_key_val(void* key, void* val);
+size_t hashtbl_count(hashtbl_t* ht);
 
 /* vim: set ts=4 sw=4 tw=0 noet :*/