Index: generic/src/adt/btree.c
===================================================================
--- generic/src/adt/btree.c	(revision 9aa72b42058acb9ec55cd96d960e524465201dc6)
+++ generic/src/adt/btree.c	(revision 9aa72b42058acb9ec55cd96d960e524465201dc6)
@@ -0,0 +1,428 @@
+/*
+ * Copyright (C) 2006 Jakub Jermar
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * This B-tree has the following properties:
+ * - it is a ballanced 2-3-4 tree (i.e. M = 4)
+ * - values (i.e. pointers to values) are stored only in leaves
+ * - leaves are linked in a list
+ * - technically, it is a B+-tree (because of the previous properties)
+ *
+ * Some of the functions below take pointer to the right-hand
+ * side subtree pointer as parameter. Note that this is sufficient
+ * because:
+ * 	- New root node is passed the left-hand side subtree pointer
+ * 	  directly.
+ * 	- node_split() always creates the right sibling and preserves
+ * 	  the original node (which becomes the left sibling).
+ * 	  There is always pointer to the left-hand side subtree
+ * 	  (i.e. left sibling) in the parent node.
+ */
+
+#include <adt/btree.h>
+#include <adt/list.h>
+#include <mm/slab.h>
+#include <debug.h>
+#include <panic.h>
+#include <typedefs.h>
+#include <print.h>
+
+static void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node);
+static void node_initialize(btree_node_t *node);
+static void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
+static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
+
+#define ROOT_NODE(n)		(!(n)->parent)
+#define INDEX_NODE(n)		((n)->subtree[0] != NULL)
+#define LEAF_NODE(n)		((n)->subtree[0] == NULL)
+
+#define MEDIAN_LOW_INDEX(n)	(((n)->keys-1)/2)
+#define MEDIAN_HIGH_INDEX(n)	((n)->keys/2)
+#define MEDIAN_LOW(n)		((n)->key[MEDIAN_LOW_INDEX((n))]);
+#define MEDIAN_HIGH(n)		((n)->key[MEDIAN_HIGH_INDEX((n))]);
+
+/** Create empty B-tree.
+ *
+ * @param t B-tree.
+ */
+void btree_create(btree_t *t)
+{
+	list_initialize(&t->leaf_head);
+	t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
+	node_initialize(t->root);
+	list_append(&t->root->leaf_link, &t->leaf_head);
+}
+
+/** Destroy empty B-tree. */
+void btree_destroy(btree_t *t)
+{
+	ASSERT(!t->root->keys);
+	free(t->root);
+}
+
+/** Insert key-value pair into B-tree.
+ *
+ * @param t B-tree.
+ * @param key Key to be inserted.
+ * @param value Value to be inserted.
+ * @param leaf_node Leaf node where the insertion should begin.
+ */ 
+void btree_insert(btree_t *t, __native key, void *value, btree_node_t *leaf_node)
+{
+	btree_node_t *lnode;
+	
+	ASSERT(value);
+	
+	lnode = leaf_node;
+	if (!lnode) {
+		if (btree_search(t, key, &lnode)) {
+			panic("B-tree %P already contains key %d\n", t, key);
+		}
+	}
+	
+	_btree_insert(t, key, value, NULL, lnode);
+}
+
+/** Recursively insert into B-tree.
+ *
+ * @param t B-tree.
+ * @param key Key to be inserted.
+ * @param value Value to be inserted.
+ * @param rsubtree Right subtree of the inserted key.
+ * @param node Start inserting into this node.
+ */
+void _btree_insert(btree_t *t, __native key, void *value, btree_node_t *rsubtree, btree_node_t *node)
+{
+	if (node->keys < BTREE_MAX_KEYS) {
+		/*
+		 * Node conatins enough space, the key can be stored immediately.
+		 */
+		node_insert_key(node, key, value, rsubtree);
+	} else {
+		btree_node_t *rnode;
+		__native median;
+		
+		/*
+		 * Node is full.
+		 * Split it and insert the smallest key from the node containing
+		 * bigger keys (i.e. the original node) into its parent.
+		 */
+
+		rnode = node_split(node, key, value, rsubtree, &median);
+
+		if (LEAF_NODE(node)) {
+			list_append(&rnode->leaf_link, &node->leaf_link);
+		}
+		
+		if (ROOT_NODE(node)) {
+			/*
+			 * We split the root node. Create new root.
+			 */
+		
+			t->root = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
+			node->parent = t->root;
+			rnode->parent = t->root;
+			node_initialize(t->root);
+			
+			/*
+			 * Left-hand side subtree will be the old root (i.e. node).
+			 * Right-hand side subtree will be rnode.
+			 */			
+			t->root->subtree[0] = node;
+
+			t->root->depth = node->depth + 1;
+		}
+		_btree_insert(t, median, NULL, rnode, node->parent);
+	}	
+		
+}
+
+/* TODO */
+void btree_remove(btree_t *t, __native key)
+{
+}
+
+/** Search key in a B-tree.
+ *
+ * @param t B-tree.
+ * @param key Key to be searched.
+ * @param leaf_node Address where to put pointer to visited leaf node.
+ *
+ * @return Pointer to value or NULL if there is no such key.
+ */
+void *btree_search(btree_t *t, __native key, btree_node_t **leaf_node)
+{
+	btree_node_t *cur, *next;
+	void *val = NULL;
+	
+	/*
+	 * Iteratively descend to the leaf that can contain searched key.
+	 */
+	for (cur = t->root; cur; cur = next) {
+		int i;
+	
+		/* Last iteration will set this with proper leaf node address. */
+		*leaf_node = cur;
+		for (i = 0; i < cur->keys; i++) {
+			if (key <= cur->key[i]) {
+				val = cur->value[i];
+				next = cur->subtree[i];
+				
+				/*
+				 * Check if there is anywhere to descend.
+				 */
+				if (!next) {
+					/*
+					 * Leaf-level.
+					 */
+					return (key == cur->key[i]) ? val : NULL;
+				}
+				goto descend;
+			}
+		}
+		next = cur->subtree[i];
+	descend:
+		;
+	}
+
+	/*
+	 * The key was not found in the *leaf_node and is greater than any of its keys.
+	 */
+	return NULL;
+}
+
+/** Get pointer to value with the smallest key within the node.
+ *
+ * Can be only used on leaf-level nodes.
+ *
+ * @param node B-tree node.
+ *
+ * @return Pointer to value assiciated with the smallest key.
+ */
+void *btree_node_min(btree_node_t *node)
+{
+	ASSERT(LEAF_NODE(node));
+	ASSERT(node->keys);
+	return node->value[0];
+}
+
+/** Get pointer to value with the biggest key within the node.
+ *
+ * Can be only used on leaf-level nodes.
+ *
+ * @param node B-tree node.
+ *
+ * @return Pointer to value assiciated with the biggest key.
+ */
+void *btree_node_max(btree_node_t *node)
+{
+	ASSERT(LEAF_NODE(node));
+	ASSERT(node->keys);
+	return node->value[node->keys - 1];
+}
+
+/** Initialize B-tree node.
+ *
+ * @param node B-tree node.
+ */
+void node_initialize(btree_node_t *node)
+{
+	int i;
+
+	node->keys = 0;
+	
+	/* Clean also space for the extra key. */
+	for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
+		node->key[i] = 0;
+		node->value[i] = NULL;
+		node->subtree[i] = NULL;
+	}
+	node->subtree[i] = NULL;
+	
+	node->parent = NULL;
+	
+	link_initialize(&node->leaf_link);
+
+	link_initialize(&node->bfs_link);
+	node->depth = 0;
+}
+
+/** Insert key-value-left-subtree triplet into B-tree non-full node.
+ *
+ * It is actually possible to have more keys than BTREE_MAX_KEYS.
+ * This feature is used during splitting the node when the
+ * number of keys is BTREE_MAX_KEYS + 1.
+ *
+ * @param node B-tree node into wich the new key is to be inserted.
+ * @param key The key to be inserted.
+ * @param value Pointer to value to be inserted.
+ * @param rsubtree Pointer to the right subtree.
+ */ 
+void node_insert_key(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree)
+{
+	int i;
+
+	for (i = 0; i < node->keys; i++) {
+		if (key < node->key[i]) {
+			int j;
+		
+			for (j = node->keys; j > i; j--) {
+				node->key[j] = node->key[j - 1];
+				node->value[j] = node->value[j - 1];
+				node->subtree[j + 1] = node->subtree[j];
+			}
+			break;	
+		}
+	}
+
+	node->key[i] = key;
+	node->value[i] = value;
+	node->subtree[i + 1] = rsubtree;
+			
+	node->keys++;
+}
+
+/** Split full B-tree node and insert new key-value-left-subtree triplet.
+ *
+ * This function will split a node and return pointer to a newly created
+ * node containing keys greater than the lesser of medians (or median)
+ * of the old keys and the newly added key. It will also write the
+ * median key to a memory address supplied by the caller.
+ *
+ * If the node being split is an index node, the median will be
+ * removed from the original node. If the node is a leaf node,
+ * the median will be preserved.
+ *
+ * @param node B-tree node wich is going to be split.
+ * @param key The key to be inserted.
+ * @param value Pointer to the value to be inserted.
+ * @param rsubtree Pointer to the right subtree of the key being added.
+ * @param median Address in memory, where the median key will be stored.
+ *
+ * @return Newly created right sibling of node.
+ */ 
+btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median)
+{
+	btree_node_t *rnode;
+	int i, j;
+
+	ASSERT(median);
+	ASSERT(node->keys == BTREE_MAX_KEYS);
+	
+	/*
+	 * Use the extra space to store the extra node.
+	 */
+	node_insert_key(node, key, value, rsubtree);
+
+	/*
+	 * Compute median of keys.
+	 */
+	*median = MEDIAN_LOW(node);
+		
+	rnode = (btree_node_t *) malloc(sizeof(btree_node_t), 0);
+	node_initialize(rnode);
+	rnode->parent = node->parent;
+	rnode->depth = node->depth;
+	
+	/*
+	 * Copy big keys, values and subtree pointers to the new right sibling.
+	 */
+	for (i = MEDIAN_LOW_INDEX(node) + 1, j = 0; i < node->keys; i++, j++) {
+		rnode->key[j] = node->key[i];
+		rnode->value[j] = node->value[i];
+		rnode->subtree[j] = node->subtree[i];
+		
+		/*
+		 * Fix parent links in subtrees.
+		 */
+		if (rnode->subtree[j])
+			rnode->subtree[j]->parent = rnode;
+			
+	}
+	rnode->subtree[j] = node->subtree[i];
+	if (rnode->subtree[j])
+		rnode->subtree[j]->parent = rnode;
+	rnode->keys = j;
+	
+	/*
+	 * Shrink the old node.
+	 * If this is an index node, remove the median.
+	 */
+	node->keys = MEDIAN_LOW_INDEX(node) + 1;
+	if (INDEX_NODE(node))
+		node->keys--;
+		
+	return rnode;
+}
+
+/** Print B-tree.
+ *
+ * @param t Print out B-tree.
+ */
+void btree_print(btree_t *t)
+{
+	int i, depth = t->root->depth;
+	link_t head;
+	
+	list_initialize(&head);
+	list_append(&t->root->bfs_link, &head);
+
+	/*
+	 * Use BFS search to print out the tree.
+	 * Levels are distinguished from one another by node->depth.
+	 */	
+	while (!list_empty(&head)) {
+		link_t *hlp;
+		btree_node_t *node;
+		
+		hlp = head.next;
+		ASSERT(hlp != &head);
+		node = list_get_instance(hlp, btree_node_t, bfs_link);
+		list_remove(hlp);
+		
+		ASSERT(node);
+		
+		if (node->depth != depth) {
+			printf("\n");
+			depth = node->depth;
+		}
+
+		printf("(");
+		for (i = 0; i < node->keys; i++) {
+			printf("%d,", node->key[i]);
+			if (node->depth && node->subtree[i]) {
+				list_append(&node->subtree[i]->bfs_link, &head);
+			}
+		}
+		if (node->depth && node->subtree[i]) {
+			list_append(&node->subtree[i]->bfs_link, &head);
+		}
+		printf(")");
+	}
+	printf("\n");
+}