Index: kernel/generic/src/adt/btree.c
===================================================================
--- kernel/generic/src/adt/btree.c	(revision 98000fb4ea6015506f059c9b121e417ce991ecfd)
+++ kernel/generic/src/adt/btree.c	(revision e2ea4ab14e798b10a6c6f159a2c23a21cd60e44a)
@@ -33,5 +33,5 @@
 /**
  * @file
- * @brief	B+tree implementation.
+ * @brief B+tree implementation.
  *
  * This file implements B+tree type and operations.
@@ -54,39 +54,48 @@
 #include <print.h>
 
-static void btree_destroy_subtree(btree_node_t *root);
-static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
-static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
-static void node_initialize(btree_node_t *node);
-static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
-static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
-static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
-static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
-static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median);
-static btree_node_t *node_combine(btree_node_t *node);
-static size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
-static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
-static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
-static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
-static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
-static bool try_rotation_from_left(btree_node_t *rnode);
-static bool try_rotation_from_right(btree_node_t *lnode);
-
-#define ROOT_NODE(n)		(!(n)->parent)
-#define INDEX_NODE(n)		((n)->subtree[0] != NULL)
-#define LEAF_NODE(n)		((n)->subtree[0] == NULL)
-
-#define FILL_FACTOR		((BTREE_M-1)/2)
-
-#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))]);
-
 static slab_cache_t *btree_node_slab;
+
+#define ROOT_NODE(n)   (!(n)->parent)
+#define INDEX_NODE(n)  ((n)->subtree[0] != NULL)
+#define LEAF_NODE(n)   ((n)->subtree[0] == NULL)
+
+#define FILL_FACTOR  ((BTREE_M - 1) / 2)
+
+#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))]);
 
 /** Initialize B-trees. */
 void btree_init(void)
 {
-	btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
+	btree_node_slab = slab_cache_create("btree_node_slab",
+	    sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
+}
+
+/** Initialize B-tree node.
+ *
+ * @param node B-tree node.
+ *
+ */
+static void node_initialize(btree_node_t *node)
+{
+	unsigned 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;
 }
 
@@ -94,4 +103,5 @@
  *
  * @param t B-tree.
+ *
  */
 void btree_create(btree_t *t)
@@ -103,41 +113,13 @@
 }
 
-/** Destroy empty B-tree. */
-void btree_destroy(btree_t *t)
-{
-	btree_destroy_subtree(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, btree_key_t 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 %" PRIu64 ".", t, key);
-		}
-	}
-	
-	_btree_insert(t, key, value, NULL, lnode);
-}
-
 /** Destroy subtree rooted in a node.
  *
  * @param root Root of the subtree.
- */
-void btree_destroy_subtree(btree_node_t *root)
+ *
+ */
+static void btree_destroy_subtree(btree_node_t *root)
 {
 	size_t i;
-
+	
 	if (root->keys) {
 		for (i = 0; i < root->keys + 1; i++) { 
@@ -146,16 +128,430 @@
 		}
 	}
+	
 	slab_free(btree_node_slab, root);
 }
 
+/** Destroy empty B-tree. */
+void btree_destroy(btree_t *t)
+{
+	btree_destroy_subtree(t->root);
+}
+
+/** Insert key-value-rsubtree triplet into B-tree 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. Insert by left rotation
+ * also makes use of this feature.
+ *
+ * @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.
+ *
+ */
+static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key,
+    void *value, btree_node_t *rsubtree)
+{
+	size_t i;
+	
+	for (i = 0; i < node->keys; i++) {
+		if (key < node->key[i]) {
+			size_t 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++;
+}
+
+/** Find key by its left or right subtree.
+ *
+ * @param node    B-tree node.
+ * @param subtree Left or right subtree of a key found in node.
+ * @param right   If true, subtree is a right subtree. If false,
+ *                subtree is a left subtree.
+ *
+ * @return Index of the key associated with the subtree.
+ *
+ */
+static size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree,
+    bool right)
+{
+	size_t i;
+	
+	for (i = 0; i < node->keys + 1; i++) {
+		if (subtree == node->subtree[i])
+			return i - (int) (right != false);
+	}
+	
+	panic("Node %p does not contain subtree %p.", node, subtree);
+}
+
+/** Remove key and its left subtree pointer from B-tree node.
+ *
+ * Remove the key and eliminate gaps in node->key array.
+ * Note that the value pointer and the left subtree pointer
+ * is removed from the node as well.
+ *
+ * @param node B-tree node.
+ * @param key  Key to be removed.
+ *
+ */
+static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
+{
+	size_t i;
+	size_t j;
+	
+	for (i = 0; i < node->keys; i++) {
+		if (key == node->key[i]) {
+			for (j = i + 1; j < node->keys; j++) {
+				node->key[j - 1] = node->key[j];
+				node->value[j - 1] = node->value[j];
+				node->subtree[j - 1] = node->subtree[j];
+			}
+			
+			node->subtree[j - 1] = node->subtree[j];
+			node->keys--;
+			
+			return;
+		}
+	}
+	
+	panic("Node %p does not contain key %" PRIu64 ".", node, key);
+}
+
+/** Remove key and its right subtree pointer from B-tree node.
+ *
+ * Remove the key and eliminate gaps in node->key array.
+ * Note that the value pointer and the right subtree pointer
+ * is removed from the node as well.
+ *
+ * @param node B-tree node.
+ * @param key  Key to be removed.
+ *
+ */
+static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
+{
+	size_t i, j;
+	
+	for (i = 0; i < node->keys; i++) {
+		if (key == node->key[i]) {
+			for (j = i + 1; j < node->keys; j++) {
+				node->key[j - 1] = node->key[j];
+				node->value[j - 1] = node->value[j];
+				node->subtree[j] = node->subtree[j + 1];
+			}
+			
+			node->keys--;
+			return;
+		}
+	}
+	
+	panic("Node %p does not contain key %" PRIu64 ".", node, key);
+}
+
+/** Insert key-value-lsubtree triplet into B-tree node.
+ *
+ * It is actually possible to have more keys than BTREE_MAX_KEYS.
+ * This feature is used during insert by right rotation.
+ *
+ * @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 lsubtree Pointer to the left subtree.
+ *
+ */
+static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key,
+    void *value, btree_node_t *lsubtree)
+{
+	size_t i;
+	
+	for (i = 0; i < node->keys; i++) {
+		if (key < node->key[i]) {
+			size_t 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];
+			}
+			
+			node->subtree[j + 1] = node->subtree[j];
+			break;
+		}
+	}
+	
+	node->key[i] = key;
+	node->value[i] = value;
+	node->subtree[i] = lsubtree;
+	
+	node->keys++;
+}
+
+/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
+ *
+ * The biggest key and its value and right subtree is rotated
+ * from the left node to the right. If the node is an index node,
+ * than the parent node key belonging to the left node takes part
+ * in the rotation.
+ *
+ * @param lnode Left sibling.
+ * @param rnode Right sibling.
+ * @param idx   Index of the parent node key that is taking part
+ *              in the rotation.
+ *
+ */
+static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
+{
+	btree_key_t key = lnode->key[lnode->keys - 1];
+	
+	if (LEAF_NODE(lnode)) {
+		void *value = lnode->value[lnode->keys - 1];
+		
+		node_remove_key_and_rsubtree(lnode, key);
+		node_insert_key_and_lsubtree(rnode, key, value, NULL);
+		lnode->parent->key[idx] = key;
+	} else {
+		btree_node_t *rsubtree = lnode->subtree[lnode->keys];
+		
+		node_remove_key_and_rsubtree(lnode, key);
+		node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
+		lnode->parent->key[idx] = key;
+		
+		/* Fix parent link of the reconnected right subtree. */
+		rsubtree->parent = rnode;
+	}
+}
+
+/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
+ *
+ * The smallest key and its value and left subtree is rotated
+ * from the right node to the left. If the node is an index node,
+ * than the parent node key belonging to the right node takes part
+ * in the rotation.
+ *
+ * @param lnode Left sibling.
+ * @param rnode Right sibling.
+ * @param idx   Index of the parent node key that is taking part
+ *              in the rotation.
+ *
+ */
+static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
+{
+	btree_key_t key = rnode->key[0];
+	
+	if (LEAF_NODE(rnode)) {
+		void *value = rnode->value[0];
+		
+		node_remove_key_and_lsubtree(rnode, key);
+		node_insert_key_and_rsubtree(lnode, key, value, NULL);
+		rnode->parent->key[idx] = rnode->key[0];
+	} else {
+		btree_node_t *lsubtree = rnode->subtree[0];
+		
+		node_remove_key_and_lsubtree(rnode, key);
+		node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
+		rnode->parent->key[idx] = key;
+		
+		/* Fix parent link of the reconnected left subtree. */
+		lsubtree->parent = lnode;
+	}
+}
+
+/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
+ *
+ * Left sibling of the node (if it exists) is checked for free space.
+ * If there is free space, the key is inserted and the smallest key of
+ * the node is moved there. The index node which is the parent of both
+ * nodes is fixed.
+ *
+ * @param node     B-tree node.
+ * @param inskey   Key to be inserted.
+ * @param insvalue Value to be inserted.
+ * @param rsubtree Right subtree of inskey.
+ *
+ * @return True if the rotation was performed, false otherwise.
+ *
+ */
+static bool try_insert_by_rotation_to_left(btree_node_t *node,
+    btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
+{
+	size_t idx;
+	btree_node_t *lnode;
+	
+	/*
+	 * If this is root node, the rotation can not be done.
+	 */
+	if (ROOT_NODE(node))
+		return false;
+	
+	idx = find_key_by_subtree(node->parent, node, true);
+	if ((int) idx == -1) {
+		/*
+		 * If this node is the leftmost subtree of its parent,
+		 * the rotation can not be done.
+		 */
+		return false;
+	}
+	
+	lnode = node->parent->subtree[idx];
+	if (lnode->keys < BTREE_MAX_KEYS) {
+		/*
+		 * The rotaion can be done. The left sibling has free space.
+		 */
+		node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
+		rotate_from_right(lnode, node, idx);
+		return true;
+	}
+	
+	return false;
+}
+
+/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
+ *
+ * Right sibling of the node (if it exists) is checked for free space.
+ * If there is free space, the key is inserted and the biggest key of
+ * the node is moved there. The index node which is the parent of both
+ * nodes is fixed.
+ *
+ * @param node     B-tree node.
+ * @param inskey   Key to be inserted.
+ * @param insvalue Value to be inserted.
+ * @param rsubtree Right subtree of inskey.
+ *
+ * @return True if the rotation was performed, false otherwise.
+ *
+ */
+static bool try_insert_by_rotation_to_right(btree_node_t *node,
+    btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
+{
+	size_t idx;
+	btree_node_t *rnode;
+	
+	/*
+	 * If this is root node, the rotation can not be done.
+	 */
+	if (ROOT_NODE(node))
+		return false;
+	
+	idx = find_key_by_subtree(node->parent, node, false);
+	if (idx == node->parent->keys) {
+		/*
+		 * If this node is the rightmost subtree of its parent,
+		 * the rotation can not be done.
+		 */
+		return false;
+	}
+	
+	rnode = node->parent->subtree[idx + 1];
+	if (rnode->keys < BTREE_MAX_KEYS) {
+		/*
+		 * The rotaion can be done. The right sibling has free space.
+		 */
+		node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
+		rotate_from_left(node, rnode, idx);
+		return true;
+	}
+	
+	return false;
+}
+
+/** Split full B-tree node and insert new key-value-right-subtree triplet.
+ *
+ * This function will split a node and return a pointer to a newly created
+ * node containing keys greater than or equal to the greater 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 not be
+ * included in the new node. If the node is a leaf node,
+ * the median will be copied there.
+ *
+ * @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.
+ *
+ */
+static btree_node_t *node_split(btree_node_t *node, btree_key_t key,
+    void *value, btree_node_t *rsubtree, btree_key_t *median)
+{
+	btree_node_t *rnode;
+	size_t i;
+	size_t j;
+	
+	ASSERT(median);
+	ASSERT(node->keys == BTREE_MAX_KEYS);
+	
+	/*
+	 * Use the extra space to store the extra node.
+	 */
+	node_insert_key_and_rsubtree(node, key, value, rsubtree);
+	
+	/*
+	 * Compute median of keys.
+	 */
+	*median = MEDIAN_HIGH(node);
+	
+	/*
+	 * Allocate and initialize new right sibling.
+	 */
+	rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
+	node_initialize(rnode);
+	rnode->parent = node->parent;
+	rnode->depth = node->depth;
+	
+	/*
+	 * Copy big keys, values and subtree pointers to the new right sibling.
+	 * If this is an index node, do not copy the median.
+	 */
+	i = (size_t) INDEX_NODE(node);
+	for (i += MEDIAN_HIGH_INDEX(node), 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;  /* Set number of keys of the new node. */
+	node->keys /= 2;  /* Shrink the old node. */
+	
+	return rnode;
+}
+
 /** Recursively insert into B-tree.
  *
- * @param t B-tree.
- * @param key Key to be inserted.
- * @param value Value to be inserted.
+ * @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, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
+ * @param node     Start inserting into this node.
+ *
+ */
+static void _btree_insert(btree_t *t, btree_key_t key, void *value,
+    btree_node_t *rsubtree, btree_node_t *node)
 {
 	if (node->keys < BTREE_MAX_KEYS) {
@@ -183,7 +579,7 @@
 		 * bigger keys (i.e. the new node) into its parent.
 		 */
-
+		
 		rnode = node_split(node, key, value, rsubtree, &median);
-
+		
 		if (LEAF_NODE(node)) {
 			list_prepend(&rnode->leaf_link, &node->leaf_link);
@@ -202,44 +598,174 @@
 			 * 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);
-	}	
-		
-}
-
-/** Remove B-tree node.
- *
- * @param t B-tree.
- * @param key Key to be removed from the B-tree along with its associated value.
- * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
- */
-void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
+	}
+}
+
+/** 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, btree_key_t 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 does not contain key %" PRIu64 ".", t, key);
-		}
-	}
-	
-	_btree_remove(t, key, lnode);
+		if (btree_search(t, key, &lnode))
+			panic("B-tree %p already contains key %" PRIu64 ".", t, key);
+	}
+	
+	_btree_insert(t, key, value, NULL, lnode);
+}
+
+/** Rotate in a key from the left sibling or from the index node, if this operation can be done.
+ *
+ * @param rnode Node into which to add key from its left sibling
+ *              or from the index node.
+ *
+ * @return True if the rotation was performed, false otherwise.
+ *
+ */
+static bool try_rotation_from_left(btree_node_t *rnode)
+{
+	size_t idx;
+	btree_node_t *lnode;
+	
+	/*
+	 * If this is root node, the rotation can not be done.
+	 */
+	if (ROOT_NODE(rnode))
+		return false;
+	
+	idx = find_key_by_subtree(rnode->parent, rnode, true);
+	if ((int) idx == -1) {
+		/*
+		 * If this node is the leftmost subtree of its parent,
+		 * the rotation can not be done.
+		 */
+		return false;
+	}
+	
+	lnode = rnode->parent->subtree[idx];
+	if (lnode->keys > FILL_FACTOR) {
+		rotate_from_left(lnode, rnode, idx);
+		return true;
+	}
+	
+	return false;
+}
+
+/** Rotate in a key from the right sibling or from the index node, if this operation can be done.
+ *
+ * @param lnode Node into which to add key from its right sibling
+ *              or from the index node.
+ *
+ * @return True if the rotation was performed, false otherwise.
+ *
+ */
+static bool try_rotation_from_right(btree_node_t *lnode)
+{
+	size_t idx;
+	btree_node_t *rnode;
+	
+	/*
+	 * If this is root node, the rotation can not be done.
+	 */
+	if (ROOT_NODE(lnode))
+		return false;
+	
+	idx = find_key_by_subtree(lnode->parent, lnode, false);
+	if (idx == lnode->parent->keys) {
+		/*
+		 * If this node is the rightmost subtree of its parent,
+		 * the rotation can not be done.
+		 */
+		return false;
+	}
+	
+	rnode = lnode->parent->subtree[idx + 1];
+	if (rnode->keys > FILL_FACTOR) {
+		rotate_from_right(lnode, rnode, idx);
+		return true;
+	}
+	
+	return false;
+}
+
+/** Combine node with any of its siblings.
+ *
+ * The siblings are required to be below the fill factor.
+ *
+ * @param node Node to combine with one of its siblings.
+ *
+ * @return Pointer to the rightmost of the two nodes.
+ *
+ */
+static btree_node_t *node_combine(btree_node_t *node)
+{
+	size_t idx;
+	btree_node_t *rnode;
+	size_t i;
+	
+	ASSERT(!ROOT_NODE(node));
+	
+	idx = find_key_by_subtree(node->parent, node, false);
+	if (idx == node->parent->keys) {
+		/*
+		 * Rightmost subtree of its parent, combine with the left sibling.
+		 */
+		idx--;
+		rnode = node;
+		node = node->parent->subtree[idx];
+	} else
+		rnode = node->parent->subtree[idx + 1];
+	
+	/* Index nodes need to insert parent node key in between left and right node. */
+	if (INDEX_NODE(node))
+		node->key[node->keys++] = node->parent->key[idx];
+	
+	/* Copy the key-value-subtree triplets from the right node. */
+	for (i = 0; i < rnode->keys; i++) {
+		node->key[node->keys + i] = rnode->key[i];
+		node->value[node->keys + i] = rnode->value[i];
+		
+		if (INDEX_NODE(node)) {
+			node->subtree[node->keys + i] = rnode->subtree[i];
+			rnode->subtree[i]->parent = node;
+		}
+	}
+	
+	if (INDEX_NODE(node)) {
+		node->subtree[node->keys + i] = rnode->subtree[i];
+		rnode->subtree[i]->parent = node;
+	}
+	
+	node->keys += rnode->keys;
+	return rnode;
 }
 
 /** Recursively remove B-tree node.
  *
- * @param t B-tree.
- * @param key Key to be removed from the B-tree along with its associated value.
+ * @param t    B-tree.
+ * @param key  Key to be removed from the B-tree along with its associated value.
  * @param node Node where the key being removed resides.
- */
-void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
+ *
+ */
+static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
 {
 	if (ROOT_NODE(node)) {
-		if (node->keys == 1 && node->subtree[0]) {
+		if ((node->keys == 1) && (node->subtree[0])) {
 			/*
 			 * Free the current root and set new root.
@@ -257,4 +783,5 @@
 			node_remove_key_and_rsubtree(node, key);
 		}
+		
 		return;
 	}
@@ -271,5 +798,5 @@
 	if (node->keys > FILL_FACTOR) {
 		size_t i;
-
+		
 		/*
 		 * The key can be immediatelly removed.
@@ -280,13 +807,14 @@
 		 */
 		node_remove_key_and_rsubtree(node, key);
+		
 		for (i = 0; i < node->parent->keys; i++) {
 			if (node->parent->key[i] == key)
 				node->parent->key[i] = node->key[0];
 		}
-		
 	} else {
 		size_t idx;
-		btree_node_t *rnode, *parent;
-
+		btree_node_t *rnode;
+		btree_node_t *parent;
+		
 		/*
 		 * The node is below the fill factor as well as its left and right sibling.
@@ -298,6 +826,8 @@
 		node_remove_key_and_rsubtree(node, key);
 		rnode = node_combine(node);
+		
 		if (LEAF_NODE(rnode))
 			list_remove(&rnode->leaf_link);
+		
 		idx = find_key_by_subtree(parent, rnode, true);
 		ASSERT((int) idx != -1);
@@ -307,11 +837,34 @@
 }
 
+/** Remove B-tree node.
+ *
+ * @param t         B-tree.
+ * @param key       Key to be removed from the B-tree along
+ *                  with its associated value.
+ * @param leaf_node If not NULL, pointer to the leaf node where
+ *                  the key is found.
+ *
+ */
+void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
+{
+	btree_node_t *lnode;
+	
+	lnode = leaf_node;
+	if (!lnode) {
+		if (!btree_search(t, key, &lnode))
+			panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
+	}
+	
+	_btree_remove(t, key, lnode);
+}
+
 /** Search key in a B-tree.
  *
- * @param t B-tree.
- * @param key Key to be searched.
+ * @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, btree_key_t key, btree_node_t **leaf_node)
@@ -323,6 +876,8 @@
 	 */
 	for (cur = t->root; cur; cur = next) {
-
-		/* Last iteration will set this with proper leaf node address. */
+		/*
+		 * Last iteration will set this with proper
+		 * leaf node address.
+		 */
 		*leaf_node = cur;
 		
@@ -337,5 +892,5 @@
 			void *val;
 			size_t i;
-		
+			
 			/*
 			 * Now if the key is smaller than cur->key[i]
@@ -347,26 +902,29 @@
 					next = cur->subtree[i];
 					val = cur->value[i - 1];
-
+					
 					if (LEAF_NODE(cur))
 						return key == cur->key[i - 1] ? val : NULL;
-
+					
 					goto descend;
-				} 
+				}
 			}
 			
 			/*
-			 * Last possibility is that the key is in the rightmost subtree.
+			 * Last possibility is that the key is
+			 * in the rightmost subtree.
 			 */
 			next = cur->subtree[i];
 			val = cur->value[i - 1];
+			
 			if (LEAF_NODE(cur))
 				return key == cur->key[i - 1] ? val : NULL;
 		}
 		descend:
-			;
-	}
-
+		;
+	}
+	
 	/*
-	 * The key was not found in the *leaf_node and is smaller than any of its keys.
+	 * The key was not found in the *leaf_node and
+	 * is smaller than any of its keys.
 	 */
 	return NULL;
@@ -375,12 +933,15 @@
 /** Return pointer to B-tree leaf node's left neighbour.
  *
- * @param t B-tree.
+ * @param t    B-tree.
  * @param node Node whose left neighbour will be returned.
  *
- * @return Left neighbour of the node or NULL if the node does not have the left neighbour.
+ * @return Left neighbour of the node or NULL if the node
+ *         does not have the left neighbour.
+ *
  */
 btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node)
 {
 	ASSERT(LEAF_NODE(node));
+	
 	if (node->leaf_link.prev != &t->leaf_head)
 		return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
@@ -391,12 +952,15 @@
 /** Return pointer to B-tree leaf node's right neighbour.
  *
- * @param t B-tree.
+ * @param t    B-tree.
  * @param node Node whose right neighbour will be returned.
  *
- * @return Right neighbour of the node or NULL if the node does not have the right neighbour.
+ * @return Right neighbour of the node or NULL if the node
+ *         does not have the right neighbour.
+ *
  */
 btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node)
 {
 	ASSERT(LEAF_NODE(node));
+	
 	if (node->leaf_link.next != &t->leaf_head)
 		return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
@@ -405,537 +969,8 @@
 }
 
-/** 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-lsubtree triplet into B-tree node.
- *
- * It is actually possible to have more keys than BTREE_MAX_KEYS.
- * This feature is used during insert by right rotation.
- *
- * @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 lsubtree Pointer to the left subtree.
- */ 
-void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
-{
-	size_t i;
-
-	for (i = 0; i < node->keys; i++) {
-		if (key < node->key[i]) {
-			size_t 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];
-			}
-			node->subtree[j + 1] = node->subtree[j];
-			break;	
-		}
-	}
-	node->key[i] = key;
-	node->value[i] = value;
-	node->subtree[i] = lsubtree;
-			
-	node->keys++;
-}
-
-/** Insert key-value-rsubtree triplet into B-tree 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. Insert by left rotation
- * also makes use of this feature.
- *
- * @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_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
-{
-	size_t i;
-
-	for (i = 0; i < node->keys; i++) {
-		if (key < node->key[i]) {
-			size_t 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++;
-}
-
-/** Remove key and its left subtree pointer from B-tree node.
- *
- * Remove the key and eliminate gaps in node->key array.
- * Note that the value pointer and the left subtree pointer
- * is removed from the node as well.
- *
- * @param node B-tree node.
- * @param key Key to be removed.
- */
-void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
-{
-	size_t i, j;
-	
-	for (i = 0; i < node->keys; i++) {
-		if (key == node->key[i]) {
-			for (j = i + 1; j < node->keys; j++) {
-				node->key[j - 1] = node->key[j];
-				node->value[j - 1] = node->value[j];
-				node->subtree[j - 1] = node->subtree[j];
-			}
-			node->subtree[j - 1] = node->subtree[j];
-			node->keys--;
-			return;
-		}
-	}
-	panic("Node %p does not contain key %" PRIu64 ".", node, key);
-}
-
-/** Remove key and its right subtree pointer from B-tree node.
- *
- * Remove the key and eliminate gaps in node->key array.
- * Note that the value pointer and the right subtree pointer
- * is removed from the node as well.
- *
- * @param node B-tree node.
- * @param key Key to be removed.
- */
-void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
-{
-	size_t i, j;
-	
-	for (i = 0; i < node->keys; i++) {
-		if (key == node->key[i]) {
-			for (j = i + 1; j < node->keys; j++) {
-				node->key[j - 1] = node->key[j];
-				node->value[j - 1] = node->value[j];
-				node->subtree[j] = node->subtree[j + 1];
-			}
-			node->keys--;
-			return;
-		}
-	}
-	panic("Node %p does not contain key %" PRIu64 ".", node, key);
-}
-
-/** Split full B-tree node and insert new key-value-right-subtree triplet.
- *
- * This function will split a node and return a pointer to a newly created
- * node containing keys greater than or equal to the greater 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 not be
- * included in the new node. If the node is a leaf node,
- * the median will be copied there.
- *
- * @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, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
-{
-	btree_node_t *rnode;
-	size_t i, j;
-
-	ASSERT(median);
-	ASSERT(node->keys == BTREE_MAX_KEYS);
-
-	/*
-	 * Use the extra space to store the extra node.
-	 */
-	node_insert_key_and_rsubtree(node, key, value, rsubtree);
-
-	/*
-	 * Compute median of keys.
-	 */
-	*median = MEDIAN_HIGH(node);
-		
-	/*
-	 * Allocate and initialize new right sibling.
-	 */
-	rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
-	node_initialize(rnode);
-	rnode->parent = node->parent;
-	rnode->depth = node->depth;
-	
-	/*
-	 * Copy big keys, values and subtree pointers to the new right sibling.
-	 * If this is an index node, do not copy the median.
-	 */
-	i = (size_t) INDEX_NODE(node);
-	for (i += MEDIAN_HIGH_INDEX(node), 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;	/* Set number of keys of the new node. */
-	node->keys /= 2;	/* Shrink the old node. */
-		
-	return rnode;
-}
-
-/** Combine node with any of its siblings.
- *
- * The siblings are required to be below the fill factor.
- *
- * @param node Node to combine with one of its siblings.
- *
- * @return Pointer to the rightmost of the two nodes.
- */
-btree_node_t *node_combine(btree_node_t *node)
-{
-	size_t idx;
-	btree_node_t *rnode;
-	size_t i;
-
-	ASSERT(!ROOT_NODE(node));
-	
-	idx = find_key_by_subtree(node->parent, node, false);
-	if (idx == node->parent->keys) {
-		/*
-		 * Rightmost subtree of its parent, combine with the left sibling.
-		 */
-		idx--;
-		rnode = node;
-		node = node->parent->subtree[idx];
-	} else {
-		rnode = node->parent->subtree[idx + 1];
-	}
-
-	/* Index nodes need to insert parent node key in between left and right node. */
-	if (INDEX_NODE(node))
-		node->key[node->keys++] = node->parent->key[idx];
-	
-	/* Copy the key-value-subtree triplets from the right node. */
-	for (i = 0; i < rnode->keys; i++) {
-		node->key[node->keys + i] = rnode->key[i];
-		node->value[node->keys + i] = rnode->value[i];
-		if (INDEX_NODE(node)) {
-			node->subtree[node->keys + i] = rnode->subtree[i];
-			rnode->subtree[i]->parent = node;
-		}
-	}
-	if (INDEX_NODE(node)) {
-		node->subtree[node->keys + i] = rnode->subtree[i];
-		rnode->subtree[i]->parent = node;
-	}
-
-	node->keys += rnode->keys;
-
-	return rnode;
-}
-
-/** Find key by its left or right subtree.
- *
- * @param node B-tree node.
- * @param subtree Left or right subtree of a key found in node.
- * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
- *
- * @return Index of the key associated with the subtree.
- */ 
-size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
-{
-	size_t i;
-	
-	for (i = 0; i < node->keys + 1; i++) {
-		if (subtree == node->subtree[i])
-			return i - (int) (right != false);
-	}
-	panic("Node %p does not contain subtree %p.", node, subtree);
-}
-
-/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
- *
- * The biggest key and its value and right subtree is rotated from the left node
- * to the right. If the node is an index node, than the parent node key belonging to
- * the left node takes part in the rotation.
- *
- * @param lnode Left sibling.
- * @param rnode Right sibling.
- * @param idx Index of the parent node key that is taking part in the rotation.
- */
-void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
-{
-	btree_key_t key;
-
-	key = lnode->key[lnode->keys - 1];
-		
-	if (LEAF_NODE(lnode)) {
-		void *value;
-
-		value = lnode->value[lnode->keys - 1];
-		node_remove_key_and_rsubtree(lnode, key);
-		node_insert_key_and_lsubtree(rnode, key, value, NULL);
-		lnode->parent->key[idx] = key;
-	} else {
-		btree_node_t *rsubtree;
-
-		rsubtree = lnode->subtree[lnode->keys];
-		node_remove_key_and_rsubtree(lnode, key);
-		node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
-		lnode->parent->key[idx] = key;
-
-		/* Fix parent link of the reconnected right subtree. */
-		rsubtree->parent = rnode;
-	}
-
-}
-
-/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
- *
- * The smallest key and its value and left subtree is rotated from the right node
- * to the left. If the node is an index node, than the parent node key belonging to
- * the right node takes part in the rotation.
- *
- * @param lnode Left sibling.
- * @param rnode Right sibling.
- * @param idx Index of the parent node key that is taking part in the rotation.
- */
-void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
-{
-	btree_key_t key;
-
-	key = rnode->key[0];
-		
-	if (LEAF_NODE(rnode)) {
-		void *value;
-
-		value = rnode->value[0];
-		node_remove_key_and_lsubtree(rnode, key);
-		node_insert_key_and_rsubtree(lnode, key, value, NULL);
-		rnode->parent->key[idx] = rnode->key[0];
-	} else {
-		btree_node_t *lsubtree;
-
-		lsubtree = rnode->subtree[0];
-		node_remove_key_and_lsubtree(rnode, key);
-		node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
-		rnode->parent->key[idx] = key;
-
-		/* Fix parent link of the reconnected left subtree. */
-		lsubtree->parent = lnode;
-	}
-
-}
-
-/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
- *
- * Left sibling of the node (if it exists) is checked for free space.
- * If there is free space, the key is inserted and the smallest key of
- * the node is moved there. The index node which is the parent of both
- * nodes is fixed.
- *
- * @param node B-tree node.
- * @param inskey Key to be inserted.
- * @param insvalue Value to be inserted.
- * @param rsubtree Right subtree of inskey.
- *
- * @return True if the rotation was performed, false otherwise.
- */
-bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
-{
-	size_t idx;
-	btree_node_t *lnode;
-
-	/*
-	 * If this is root node, the rotation can not be done.
-	 */
-	if (ROOT_NODE(node))
-		return false;
-	
-	idx = find_key_by_subtree(node->parent, node, true);
-	if ((int) idx == -1) {
-		/*
-		 * If this node is the leftmost subtree of its parent,
-		 * the rotation can not be done.
-		 */
-		return false;
-	}
-		
-	lnode = node->parent->subtree[idx];
-	if (lnode->keys < BTREE_MAX_KEYS) {
-		/*
-		 * The rotaion can be done. The left sibling has free space.
-		 */
-		node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
-		rotate_from_right(lnode, node, idx);
-		return true;
-	}
-
-	return false;
-}
-
-/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
- *
- * Right sibling of the node (if it exists) is checked for free space.
- * If there is free space, the key is inserted and the biggest key of
- * the node is moved there. The index node which is the parent of both
- * nodes is fixed.
- *
- * @param node B-tree node.
- * @param inskey Key to be inserted.
- * @param insvalue Value to be inserted.
- * @param rsubtree Right subtree of inskey.
- *
- * @return True if the rotation was performed, false otherwise.
- */
-bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
-{
-	size_t idx;
-	btree_node_t *rnode;
-
-	/*
-	 * If this is root node, the rotation can not be done.
-	 */
-	if (ROOT_NODE(node))
-		return false;
-	
-	idx = find_key_by_subtree(node->parent, node, false);
-	if (idx == node->parent->keys) {
-		/*
-		 * If this node is the rightmost subtree of its parent,
-		 * the rotation can not be done.
-		 */
-		return false;
-	}
-		
-	rnode = node->parent->subtree[idx + 1];
-	if (rnode->keys < BTREE_MAX_KEYS) {
-		/*
-		 * The rotaion can be done. The right sibling has free space.
-		 */
-		node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
-		rotate_from_left(node, rnode, idx);
-		return true;
-	}
-
-	return false;
-}
-
-/** Rotate in a key from the left sibling or from the index node, if this operation can be done.
- *
- * @param rnode Node into which to add key from its left sibling or from the index node.
- *
- * @return True if the rotation was performed, false otherwise.
- */
-bool try_rotation_from_left(btree_node_t *rnode)
-{
-	size_t idx;
-	btree_node_t *lnode;
-
-	/*
-	 * If this is root node, the rotation can not be done.
-	 */
-	if (ROOT_NODE(rnode))
-		return false;
-	
-	idx = find_key_by_subtree(rnode->parent, rnode, true);
-	if ((int) idx == -1) {
-		/*
-		 * If this node is the leftmost subtree of its parent,
-		 * the rotation can not be done.
-		 */
-		return false;
-	}
-		
-	lnode = rnode->parent->subtree[idx];
-	if (lnode->keys > FILL_FACTOR) {
-		rotate_from_left(lnode, rnode, idx);
-		return true;
-	}
-	
-	return false;
-}
-
-/** Rotate in a key from the right sibling or from the index node, if this operation can be done.
- *
- * @param lnode Node into which to add key from its right sibling or from the index node.
- *
- * @return True if the rotation was performed, false otherwise.
- */
-bool try_rotation_from_right(btree_node_t *lnode)
-{
-	size_t idx;
-	btree_node_t *rnode;
-
-	/*
-	 * If this is root node, the rotation can not be done.
-	 */
-	if (ROOT_NODE(lnode))
-		return false;
-	
-	idx = find_key_by_subtree(lnode->parent, lnode, false);
-	if (idx == lnode->parent->keys) {
-		/*
-		 * If this node is the rightmost subtree of its parent,
-		 * the rotation can not be done.
-		 */
-		return false;
-	}
-		
-	rnode = lnode->parent->subtree[idx + 1];
-	if (rnode->keys > FILL_FACTOR) {
-		rotate_from_right(lnode, rnode, idx);
-		return true;
-	}	
-
-	return false;
-}
-
 /** Print B-tree.
  *
  * @param t Print out B-tree.
+ *
  */
 void btree_print(btree_t *t)
@@ -944,13 +979,13 @@
 	int depth = t->root->depth;
 	link_t head, *cur;
-
+	
 	printf("Printing B-tree:\n");
 	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;
@@ -968,6 +1003,7 @@
 			depth = node->depth;
 		}
-
+		
 		printf("(");
+		
 		for (i = 0; i < node->keys; i++) {
 			printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
@@ -976,9 +1012,11 @@
 			}
 		}
-		if (node->depth && node->subtree[i]) {
+		
+		if (node->depth && node->subtree[i])
 			list_append(&node->subtree[i]->bfs_link, &head);
-		}
+		
 		printf(")");
 	}
+	
 	printf("\n");
 	
@@ -990,10 +1028,13 @@
 		
 		ASSERT(node);
-
+		
 		printf("(");
+		
 		for (i = 0; i < node->keys; i++)
 			printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : "");
+		
 		printf(")");
 	}
+	
 	printf("\n");
 }
