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

12 files changed, 448 insertions, 68 deletions

diff --git a/src/apps/init/main.c b/src/apps/init/main.c
index 6a9cd5f..f7259ff 100644
--- a/src/apps/init/main.c
+++ b/src/apps/init/main.c
@@ -11,3 +11,4 @@ int main(int argc, char **argv) {
 	return 0;
 }
 
+/* vim: set ts=4 sw=4 tw=0 noet :*/
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 :*/
diff --git a/src/common/libalgo/Makefile b/src/common/libalgo/Makefile
index 3e021c4..fe6dbc6 100644
--- a/src/common/libalgo/Makefile
+++ b/src/common/libalgo/Makefile
@@ -1,4 +1,4 @@
-OBJ = hashtbl.o
+OBJ = keyval.o hashtbl.o btree.o
 
 LIB = 
 
diff --git a/src/common/libalgo/btree.c b/src/common/libalgo/btree.c
new file mode 100644
index 0000000..da0e25b
--- /dev/null
+++ b/src/common/libalgo/btree.c
@@ -0,0 +1,295 @@
+#include <malloc.h>
+#include <debug.h>
+
+#include <btree.h>
+
+typedef struct btree_item {
+	void *key, *val;
+
+	int height;
+	struct btree_item *left, *right;
+} btree_item_t;
+
+struct btree {
+	key_cmp_fun_t cf;
+	kv_iter_fun_t releasef;
+
+	btree_item_t *root;
+	int nitems;
+};
+
+btree_t* create_btree(key_cmp_fun_t cf, kv_iter_fun_t relf) {
+	btree_t* t = (btree_t*)malloc(sizeof(btree_t));
+
+	if (t == 0) return 0;
+
+	t->cf = cf;
+	t->releasef = relf;
+
+	t->root = 0;
+	t->nitems = 0;
+
+	return t;
+}
+
+void delete_btree(btree_t *t) {
+	void delete_item_rec(btree_item_t *i,kv_iter_fun_t relf) {
+		if (i == 0) return;
+
+		delete_item_rec(i->left, relf);
+		delete_item_rec(i->right, relf);
+
+		relf(i->key, i->val);
+		free(i);
+	}
+
+	delete_item_rec(t->root, t->releasef);
+
+	free(t);
+}
+
+size_t btree_count(btree_t *i) {
+	return i->nitems;
+}
+
+// ============== //
+// TREE ROTATIONS //
+// ============== //
+
+static int height(btree_item_t *i) {
+	if (i == 0) return 0;
+	return i->height;
+}
+
+static void recalc_height(btree_item_t *i) {
+	if (i == 0) return;
+
+	i->height = MAX(height(i->left), height(i->right)) + 1;
+}
+
+static btree_item_t* rotate_left(btree_item_t *i) {
+	// I(X(a, b), Y) -> a X b I Y -> X(a, I(b, Y))
+
+	btree_item_t *x = i->left;
+	if (x == 0) return i;
+	btree_item_t *b = x->right;
+
+	x->right = i;
+	i->left = b;
+
+	recalc_height(i);
+	recalc_height(x);
+
+	return x;
+}
+
+static btree_item_t* rotate_right(btree_item_t *i) {
+	// I(X, Y(a,b)) -> X I a Y b -> Y(I(X, a), b)
+
+	btree_item_t *y = i->right;
+	if (y == 0) return i;
+	btree_item_t *a = y->left;
+
+	y->left = i;
+	i->right = a;
+
+	recalc_height(i);
+	recalc_height(y);
+
+	return y;
+}
+
+static btree_item_t* equilibrate(btree_item_t *i) {
+	if (i == 0) return 0;
+
+	while (height(i->left) - height(i->right) >= 2)
+		i = rotate_left(i);
+
+	while (height(i->right) - height(i->left) >= 2)
+		i = rotate_right(i);
+	
+	return i;
+}
+
+// =================== //
+// ADDING AND DELETING //
+// =================== //
+
+bool btree_add(btree_t *t, void* key, void* val) {
+	btree_item_t* insert(btree_t *t, btree_item_t *root, btree_item_t *i) {
+		if (root == 0) return i;
+
+		if (t->cf(i->key, root->key) <= 0) {
+			root->left = insert(t, root->left, i);
+		} else {
+			root->right = insert(t, root->right, i);
+		}
+		recalc_height(root);
+
+		return equilibrate(root);
+	}
+
+	btree_item_t *x = (btree_item_t*)malloc(sizeof(btree_item_t));
+	if (x == 0) return false;
+
+	x->key = key;
+	x->val = val;
+	x->left = x->right = 0;
+	recalc_height(x);
+
+	t->root = insert(t, t->root, x);
+	t->nitems++;
+
+	return true;
+}
+
+void btree_remove(btree_t *t, const void* key) {
+	btree_item_t *extract_smallest(btree_item_t *i, btree_item_t **out_smallest) {
+		ASSERT(i != 0);
+		if (i->left == 0) {
+			*out_smallest = i;
+			return i->right;
+		} else {
+			i->left = extract_smallest(i->left, out_smallest);
+			recalc_height(i);
+			return equilibrate(i);
+		}
+	}
+
+	btree_item_t *remove_aux(btree_t *t, btree_item_t *i, const void* key) {
+		if (i == 0) return 0;
+
+		int c = t->cf(key, i->key);
+		if (c < 0) {
+			i->left = remove_aux(t, i->left, key);
+			return equilibrate(i);
+		} else if (c > 0) {
+			i->right = remove_aux(t, i->right, key);
+			return equilibrate(i);
+		} else {
+			// remove item i
+
+			btree_item_t *new_i;
+			if (i->right == 0 || i->left == 0) {
+				new_i = (i->right == 0 ? i->left : i->right);
+			} else {
+				btree_item_t *new_i_right = extract_smallest(i->right, &new_i);
+
+				new_i->left = i->left;
+				new_i->right = new_i_right;
+
+				recalc_height(new_i);
+				new_i = equilibrate(new_i);
+			}
+
+			t->releasef(i->key, i->val);
+			free(i);
+			t->nitems--;
+
+			return remove_aux(t, new_i, key);	// loop because several elements may correspond
+		}
+	}
+
+	t->root = remove_aux(t, t->root, key);
+}
+
+// ======================== //
+// LOOKING UP AND ITERATING //
+// ======================== //
+
+void* btree_find(btree_t *t, const void* key) {
+	btree_item_t *find_aux(btree_t *t, btree_item_t *i, const void* key) {
+		if (i == 0) return 0;
+
+		int c = t->cf(key, i->key);
+		if (c == 0) {
+			return i;
+		} else if (c < 0) {
+			return find_aux(t, i->left, key);
+		} else {
+			return find_aux(t, i->right, key);
+		}
+	}
+
+	btree_item_t *i = find_aux(t, t->root, key);
+
+	if (i == 0) return 0;
+	return i->val;
+}
+
+void* btree_lower(btree_t *t, const void* key) {
+	btree_item_t *find_aux(btree_t *t, btree_item_t *i, const void* key) {
+		if (i == 0) return 0;
+
+		int c = t->cf(key, i->key);
+		if (c == 0) {
+			return i;
+		} else if (c < 0) {
+			return find_aux(t, i->left, key);
+		} else {
+			btree_item_t *r = find_aux(t, i->right, key);
+			if (r == 0) r = i;
+			return r;
+		}
+	}
+
+	btree_item_t *i = find_aux(t, t->root, key);
+
+	if (i == 0) return 0;
+	return i->val;
+}
+
+void* btree_upper(btree_t *t, const void* key) {
+	btree_item_t *find_aux(btree_t *t, btree_item_t *i, const void* key) {
+		if (i == 0) return 0;
+
+		int c = t->cf(key, i->key);
+		if (c == 0) {
+			return i;
+		} else if (c < 0) {
+			btree_item_t *r = find_aux(t, i->left, key);
+			if (r == 0) r = i;
+			return r;
+		} else {
+			return find_aux(t, i->right, key);
+		}
+	}
+
+	btree_item_t *i = find_aux(t, t->root, key);
+
+	if (i == 0) return 0;
+	return i->val;
+}
+
+void btree_iter(btree_t *t, kv_iter_fun_t f) {
+	void iter_aux(btree_item_t *i, kv_iter_fun_t f) {
+		if (i == 0) return;
+
+		iter_aux(i->left, f);
+		f(i->key, i->val);
+		iter_aux(i->right, f);
+	}
+
+	iter_aux(t->root, f);
+}
+
+void btree_iter_on(btree_t *t, const void* key, kv_iter_fun_t f) {
+	void iter_aux(btree_t *t, btree_item_t *i, const void* key, kv_iter_fun_t f) {
+		if (i == 0) return;
+
+		int c = t->cf(key, i->key);
+		if (c == 0) {
+			iter_aux(t, i->left, key, f);
+			f(i->key, i->val);
+			iter_aux(t, i->right, key, f);
+		} else if (c < 0) {
+			iter_aux(t, i->left, key, f);
+		} else {
+			iter_aux(t, i->right, key, f);
+		}
+	}
+
+	iter_aux(t, t->root, key, f);
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/libalgo/hashtbl.c b/src/common/libalgo/hashtbl.c
index b4720c3..f490632 100644
--- a/src/common/libalgo/hashtbl.c
+++ b/src/common/libalgo/hashtbl.c
@@ -1,6 +1,6 @@
-#include <hashtbl.h>
 #include <malloc.h>
-#include <string.h>
+
+#include <hashtbl.h>
 
 #define DEFAULT_HT_INIT_SIZE 16
 #define SLOT_OF_HASH(k, nslots) (((size_t)(k)*21179)%(size_t)(nslots))
@@ -109,16 +109,6 @@ bool hashtbl_add(hashtbl_t *ht, void* key, void* v) {
 	return true;
 }
 
-void* hashtbl_find(hashtbl_t* ht, const void* key) {
-	size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size);
-
-	for (hashtbl_item_t *i = ht->items[slot]; i != 0; i = i->next) {
-		if (ht->ef(i->key, key)) return i->val;
-	}
-
-	return 0;
-}
-
 void hashtbl_remove(hashtbl_t* ht, const void* key) {
 	size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size);
 
@@ -148,45 +138,26 @@ void hashtbl_remove(hashtbl_t* ht, const void* key) {
 	hashtbl_check_size(ht);
 }
 
-size_t hashtbl_count(hashtbl_t* ht) {
-	return ht->nitems;
-}
-
-// ================================== //
-// UTILITY FUNCTIONS (HASH, EQ, FREE) //
-// ================================== //
-
-hash_t id_hash_fun(const void* v) {
-	return (hash_t)v;
-}
+void* hashtbl_find(hashtbl_t* ht, const void* key) {
+	size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size);
 
-hash_t str_hash_fun(const void* v) {
-	hash_t h = 712;
-	for (char* s = (char*)v; *s != 0; s++) {
-		h = h * 101 + *s;
+	for (hashtbl_item_t *i = ht->items[slot]; i != 0; i = i->next) {
+		if (ht->ef(i->key, key)) return i->val;
 	}
-	return h;
-}
-
-bool id_key_eq_fun(const void* a, const void* b) {
-	return a == b;
-}
-
-bool str_key_eq_fun(const void* a, const void* b) {
-	return strcmp((const char*)a, (const char*)b) == 0;
-}
 
-void free_key(void* key, void* val) {
-	free(key);
+	return 0;
 }
 
-void free_val(void* key, void* val) {
-	free(val);
+void hashtbl_iter(hashtbl_t *ht, kv_iter_fun_t f) {
+	for (size_t s = 0; s < ht->size; s++) {
+		for (hashtbl_item_t *i = ht->items[s]; i != 0; i = i->next) {
+			f(i->key, i->val);
+		}
+	}
 }
 
-void free_key_val(void* key, void* val) {
-	free(key);
-	free(val);
+size_t hashtbl_count(hashtbl_t* ht) {
+	return ht->nitems;
 }
 
 /* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/libalgo/keyval.c b/src/common/libalgo/keyval.c
new file mode 100644
index 0000000..0368aed
--- /dev/null
+++ b/src/common/libalgo/keyval.c
@@ -0,0 +1,51 @@
+#include <malloc.h>
+#include <string.h>
+
+#include <algo.h>
+
+// Hashing and comparing
+
+hash_t id_hash_fun(const void* v) {
+	return (hash_t)v;
+}
+
+hash_t str_hash_fun(const void* v) {
+	hash_t h = 712;
+	for (char* s = (char*)v; *s != 0; s++) {
+		h = h * 101 + *s;
+	}
+	return h;
+}
+
+bool id_key_eq_fun(const void* a, const void* b) {
+	return a == b;
+}
+
+bool str_key_eq_fun(const void* a, const void* b) {
+	return strcmp((const char*)a, (const char*)b) == 0;
+}
+
+int id_key_cmp_fun(const void* a, const void* b) {
+	return (b == a ? 0 : (b > a ? 1 : -1));
+}
+
+int str_key_cmp_fun(const void* a, const void* b) {
+	return strcmp((const char*)a, (const char*)b);
+}
+
+// Freeing functions
+
+void free_key(void* key, void* val) {
+	free(key);
+}
+
+void free_val(void* key, void* val) {
+	free(val);
+}
+
+void free_key_val(void* key, void* val) {
+	free(key);
+	free(val);
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/lib/libkogata/debug.c b/src/lib/libkogata/debug.c
index 27c9e28..9688877 100644
--- a/src/lib/libkogata/debug.c
+++ b/src/lib/libkogata/debug.c
@@ -11,3 +11,5 @@ void panic_assert(const char* assert, const char* file, int line) {
 	// TODO
 	while(true);
 }
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/lib/libkogata/malloc.c b/src/lib/libkogata/malloc.c
index c776cdf..272dd7d 100644
--- a/src/lib/libkogata/malloc.c
+++ b/src/lib/libkogata/malloc.c
@@ -9,3 +9,4 @@ void free(void* ptr) {
 	// TODO
 }
 
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/lib/libkogata/start.c b/src/lib/libkogata/start.c
index 9ba7edf..984a3cd 100644
--- a/src/lib/libkogata/start.c
+++ b/src/lib/libkogata/start.c
@@ -10,3 +10,4 @@ void __libkogata_start() {
 	exit(ret);
 }
 
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/lib/libkogata/syscall.c b/src/lib/libkogata/syscall.c
index 342426b..b9cefa7 100644
--- a/src/lib/libkogata/syscall.c
+++ b/src/lib/libkogata/syscall.c
@@ -14,3 +14,5 @@ void yield() {
 void exit(int code) {
 	asm volatile("int $0x40"::"a"(SC_EXIT),"b"(code));
 }
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/