6 files changed, 576 insertions, 5 deletions

diff --git a/src/common/libkogata/btree.c b/src/common/libkogata/btree.c
new file mode 100644
index 0000000..dc5f11f
--- /dev/null
+++ b/src/common/libkogata/btree.c
@@ -0,0 +1,343 @@
+#include <kogata/malloc.h>
+#include <kogata/debug.h>
+
+#include <kogata/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 _btree_delete_item_rec(btree_item_t *i,kv_iter_fun_t relf) {
+	if (i == 0) return;
+
+	_btree_delete_item_rec(i->left, relf);
+	_btree_delete_item_rec(i->right, relf);
+
+	if (relf) relf(i->key, i->val);
+	free(i);
+}
+void delete_btree(btree_t *t) {
+	_btree_delete_item_rec(t->root, t->releasef);
+
+	free(t);
+}
+
+size_t btree_count(btree_t *i) {
+	return i->nitems;
+}
+
+// ============== //
+// TREE ROTATIONS //
+// ============== //
+
+static inline int height(btree_item_t *i) {
+	if (i == 0) return 0;
+	return i->height;
+}
+
+void btree_recalc_height(btree_item_t *i) {
+	if (i == 0) return;
+
+	i->height = MAX(height(i->left), height(i->right)) + 1;
+}
+
+btree_item_t* btree_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;
+
+	btree_recalc_height(i);
+	btree_recalc_height(x);
+
+	return x;
+}
+
+btree_item_t* btree_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;
+
+	btree_recalc_height(i);
+	btree_recalc_height(y);
+
+	return y;
+}
+
+btree_item_t* btree_equilibrate(btree_item_t *i) {
+	if (i == 0) return 0;
+
+	while (height(i->left) - height(i->right) >= 2)
+		i = btree_rotate_left(i);
+
+	while (height(i->right) - height(i->left) >= 2)
+		i = btree_rotate_right(i);
+	
+	return i;
+}
+
+// =================== //
+// ADDING AND DELETING //
+// =================== //
+
+btree_item_t* _btree_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 = _btree_insert(t, root->left, i);
+	} else {
+		root->right = _btree_insert(t, root->right, i);
+	}
+	btree_recalc_height(root);
+
+	return btree_equilibrate(root);
+}
+bool btree_add(btree_t *t, void* key, void* val) {
+	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;
+	btree_recalc_height(x);
+
+	t->root = _btree_insert(t, t->root, x);
+	t->nitems++;
+
+	return true;
+}
+
+btree_item_t *_btree_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 = _btree_extract_smallest(i->left, out_smallest);
+		btree_recalc_height(i);
+		return btree_equilibrate(i);
+	}
+}
+btree_item_t *_btree_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 = _btree_remove_aux(t, i->left, key);
+		return btree_equilibrate(i);
+	} else if (c > 0) {
+		i->right = _btree_remove_aux(t, i->right, key);
+		return btree_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 = _btree_extract_smallest(i->right, &new_i);
+
+			new_i->left = i->left;
+			new_i->right = new_i_right;
+
+			btree_recalc_height(new_i);
+			new_i = btree_equilibrate(new_i);
+		}
+
+		if (t->releasef) t->releasef(i->key, i->val);
+		free(i);
+		t->nitems--;
+
+		return _btree_remove_aux(t, new_i, key);	// loop because several elements may correspond
+	}
+}
+void btree_remove(btree_t *t, const void* key) {
+	t->root = _btree_remove_aux(t, t->root, key);
+}
+
+btree_item_t *_btree_extract_smallest_v(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 = _btree_extract_smallest_v(i->left, out_smallest);
+		btree_recalc_height(i);
+		return btree_equilibrate(i);
+	}
+}
+btree_item_t *_btree_remove_aux_v(btree_t *t, btree_item_t *i, const void* key, const void* val) {
+	if (i == 0) return 0;
+
+	int c = t->cf(key, i->key);
+	if (c < 0) {
+		i->left = _btree_remove_aux_v(t, i->left, key, val);
+		return btree_equilibrate(i);
+	} else if (c > 0) {
+		i->right = _btree_remove_aux_v(t, i->right, key, val);
+		return btree_equilibrate(i);
+	} else if (i->val == val) {
+		// 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 = _btree_extract_smallest_v(i->right, &new_i);
+
+			new_i->left = i->left;
+			new_i->right = new_i_right;
+
+			btree_recalc_height(new_i);
+			new_i = btree_equilibrate(new_i);
+		}
+
+		if (t->releasef) t->releasef(i->key, i->val);
+		free(i);
+		t->nitems--;
+
+		return _btree_remove_aux_v(t, new_i, key, val);	// loop because several elements may correspond
+	} else {
+		i->left = _btree_remove_aux_v(t, i->left, key, val);
+		i->right = _btree_remove_aux_v(t, i->right, key, val);
+		btree_recalc_height(i);
+		return btree_equilibrate(i);
+	}
+}
+void btree_remove_v(btree_t *t, const void* key, const void* val) {
+	t->root = _btree_remove_aux_v(t, t->root, key, val);
+}
+
+// ======================== //
+// LOOKING UP AND ITERATING //
+// ======================== //
+
+btree_item_t *_btree_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 _btree_find_aux(t, i->left, key);
+	} else {
+		return _btree_find_aux(t, i->right, key);
+	}
+}
+void* btree_find(btree_t *t, const void* key) {
+
+	btree_item_t *i = _btree_find_aux(t, t->root, key);
+
+	if (i == 0) return 0;
+	return i->val;
+}
+
+btree_item_t *_btree_lower_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 _btree_lower_aux(t, i->left, key);
+	} else {
+		btree_item_t *r = _btree_lower_aux(t, i->right, key);
+		if (r == 0) r = i;
+		return r;
+	}
+}
+void* btree_lower(btree_t *t, const void* key, void** actual_key) {
+	btree_item_t *i = _btree_lower_aux(t, t->root, key);
+
+	if (i == 0) return 0;
+	if (actual_key != 0) *actual_key = i->key;
+	return i->val;
+}
+
+btree_item_t *_btree_upper_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 = _btree_upper_aux(t, i->left, key);
+		if (r == 0) r = i;
+		return r;
+	} else {
+		return _btree_upper_aux(t, i->right, key);
+	}
+}
+void* btree_upper(btree_t *t, const void* key, void** actual_key) {
+	btree_item_t *i = _btree_upper_aux(t, t->root, key);
+
+	if (i == 0) return 0;
+	if (actual_key != 0) *actual_key = i->key;
+	return i->val;
+}
+
+
+void _btree_iter_aux(btree_item_t *i, kv_iter_fun_t f) {
+	if (i == 0) return;
+
+	_btree_iter_aux(i->left, f);
+	f(i->key, i->val);
+	_btree_iter_aux(i->right, f);
+}
+void btree_iter(btree_t *t, kv_iter_fun_t f) {
+	_btree_iter_aux(t->root, f);
+}
+
+void _btree_iter_on_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) {
+		_btree_iter_on_aux(t, i->left, key, f);
+		f(i->key, i->val);
+		_btree_iter_on_aux(t, i->right, key, f);
+	} else if (c < 0) {
+		_btree_iter_on_aux(t, i->left, key, f);
+	} else {
+		_btree_iter_on_aux(t, i->right, key, f);
+	}
+}
+void btree_iter_on(btree_t *t, const void* key, kv_iter_fun_t f) {
+	_btree_iter_on_aux(t, t->root, key, f);
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/libkogata/hashtbl.c b/src/common/libkogata/hashtbl.c
new file mode 100644
index 0000000..b0097cd
--- /dev/null
+++ b/src/common/libkogata/hashtbl.c
@@ -0,0 +1,177 @@
+#include <kogata/debug.h>
+#include <kogata/malloc.h>
+
+#include <kogata/hashtbl.h>
+
+#define DEFAULT_HT_INIT_SIZE 16
+#define SLOT_OF_HASH(k, nslots) (((size_t)(k)*21179)%(size_t)(nslots))
+
+typedef struct hashtbl_item {
+	void* key;
+	void* val;
+	struct hashtbl_item *next;
+} hashtbl_item_t;
+
+// When nitems > size * 3/4, size is multiplied by two
+// When nitems < size * 1/4, size is divided by two
+struct hashtbl {
+	key_eq_fun_t ef;
+	hash_fun_t hf;
+	kv_iter_fun_t releasef;
+	size_t size, nitems;
+	hashtbl_item_t **items;
+};
+
+hashtbl_t *create_hashtbl(key_eq_fun_t ef, hash_fun_t hf, kv_iter_fun_t on_release) {
+	hashtbl_t *ht = (hashtbl_t*)malloc(sizeof(hashtbl_t));
+	if (ht == 0) return 0;
+
+	ht->ef = ef;
+	ht->hf = hf;
+	ht->releasef = on_release;
+
+	ht->size = DEFAULT_HT_INIT_SIZE;
+	ht->nitems = 0;
+
+	ht->items = (hashtbl_item_t**)malloc(ht->size * sizeof(hashtbl_item_t*));
+	if (ht->items == 0) {
+		free(ht);
+		return 0;
+	}
+
+	for (size_t i = 0; i < ht->size; i++) ht->items[i] = 0;
+
+	return ht;
+}
+
+void delete_hashtbl(hashtbl_t *ht) {
+	// Free items
+	for (size_t i = 0; i < ht->size; i++) {
+		while (ht->items[i] != 0) {
+			hashtbl_item_t *x = ht->items[i];
+			ht->items[i] = x->next;
+
+			if (ht->releasef) ht->releasef(x->key, x->val);
+			
+			free(x);
+		}
+	}
+
+	// Free table
+	free(ht->items);
+	free(ht);
+}
+
+void hashtbl_check_size(hashtbl_t *ht) {
+	size_t nsize = 0;
+	if (4 * ht->nitems < ht->size) nsize = ht->size / 2;
+	if (4 * ht->nitems > 3 * ht->size) nsize = ht->size * 2;
+
+	if (nsize != 0 && nsize >= DEFAULT_HT_INIT_SIZE) {
+		hashtbl_item_t **nitems = (hashtbl_item_t**)malloc(nsize * sizeof(hashtbl_item_t*));
+		if (nitems == 0) return;	// if we can't realloc, too bad, we just lose space/efficienty
+
+		for (size_t i = 0; i < nsize; i++) nitems[i] = 0;
+
+		// rehash
+		for (size_t i = 0; i < ht->size; i++) {
+			while (ht->items[i] != 0) {
+				hashtbl_item_t *x = ht->items[i];
+				ht->items[i] = x->next;
+
+				size_t slot = SLOT_OF_HASH(ht->hf(x->key), nsize);
+				x->next = nitems[slot];
+				nitems[slot] = x;
+			}
+		}
+		free(ht->items);
+		ht->size = nsize;
+		ht->items = nitems;
+	}
+}
+
+bool hashtbl_add(hashtbl_t *ht, void* key, void* v) {
+	hashtbl_item_t *i = (hashtbl_item_t*)malloc(sizeof(hashtbl_item_t));
+	if (i == 0) return false;	// OOM
+
+	// make sure item is not already present
+	hashtbl_remove(ht, key);
+
+	size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size);
+
+	i->key = key;
+	i->val = v;
+	i->next = ht->items[slot];
+	ht->items[slot] = i;
+	ht->nitems++;
+
+	hashtbl_check_size(ht);
+
+	return true;
+}
+
+void hashtbl_remove(hashtbl_t* ht, const void* key) {
+	size_t slot = SLOT_OF_HASH(ht->hf(key), ht->size);
+
+	if (ht->items[slot] == 0) return;
+
+	hashtbl_item_t *x = 0;
+
+	if (ht->ef(ht->items[slot]->key, key)) {
+		x = ht->items[slot];
+		ht->items[slot] = x->next;
+	} else {
+		for (hashtbl_item_t *i = ht->items[slot]; i->next != 0; i = i->next) {
+			if (ht->ef(i->next->key, key)) {
+				x = i->next;
+				i->next = x->next;
+				break;
+			}
+		}
+	}
+
+	if (x != 0) {
+		ht->nitems--;
+		if (ht->releasef) ht->releasef(x->key, x->val);
+		free(x);
+	}
+	
+	hashtbl_check_size(ht);
+}
+
+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_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);
+		}
+	}
+}
+
+size_t hashtbl_count(hashtbl_t* ht) {
+	return ht->nitems;
+}
+
+bool hashtbl_change(hashtbl_t* ht, void* key, void* newval) {
+	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)) {
+			i->val = newval;
+			return true;
+		}
+	}
+
+	return false;
+}
+
+/* vim: set ts=4 sw=4 tw=0 noet :*/
diff --git a/src/common/libkogata/keyval.c b/src/common/libkogata/keyval.c
new file mode 100644
index 0000000..9541c72
--- /dev/null
+++ b/src/common/libkogata/keyval.c
@@ -0,0 +1,51 @@
+#include <string.h>
+
+#include <kogata/malloc.h>
+#include <kogata/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 (a == b ? 0 : (a < b ? -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/common/libkogata/mutex.c b/src/common/libkogata/mutex.c
index b345ee5..e521330 100644
--- a/src/common/libkogata/mutex.c
+++ b/src/common/libkogata/mutex.c
@@ -1,4 +1,4 @@
-#include <mutex.h>
+#include <kogata/mutex.h>
 
 /*	Internal use only. This function is atomic, meaning it cannot be interrupted by a system task switch. */
 static uint32_t atomic_exchange(uint32_t* ptr, uint32_t newval) {
diff --git a/src/common/libkogata/region_alloc.c b/src/common/libkogata/region_alloc.c
index 1f2fe0f..85c437a 100644
--- a/src/common/libkogata/region_alloc.c
+++ b/src/common/libkogata/region_alloc.c
@@ -1,6 +1,6 @@
-#include <region_alloc.h>
-#include <debug.h>
-#include <mutex.h>
+#include <kogata/region_alloc.h>
+#include <kogata/debug.h>
+#include <kogata/mutex.h>
 
 // we cannot include sys...
 
diff --git a/src/common/libkogata/slab_alloc.c b/src/common/libkogata/slab_alloc.c
index 0736655..6362207 100644
--- a/src/common/libkogata/slab_alloc.c
+++ b/src/common/libkogata/slab_alloc.c
@@ -1,4 +1,4 @@
-#include <slab_alloc.h>
+#include <kogata/slab_alloc.h>
 
 typedef struct object {
 	struct object *next;