Index: generic/src/adt/btree.c
===================================================================
--- generic/src/adt/btree.c	(revision 0cb56f5db21f80d518ed87fdf28a0b52e34a0612)
+++ generic/src/adt/btree.c	(revision 5b04fc75c4e9e21145afd331bebd1892939b8ba2)
@@ -50,10 +50,10 @@
 static void _btree_remove(btree_t *t, __native key, btree_node_t *node);
 static void node_initialize(btree_node_t *node);
-static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
+static void node_insert_key_and_lsubtree(btree_node_t *node, __native key, void *value, btree_node_t *lsubtree);
 static void node_insert_key_and_rsubtree(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree);
+static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
+static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
 static btree_node_t *node_split(btree_node_t *node, __native key, void *value, btree_node_t *rsubtree, __native *median);
 static btree_node_t *node_combine(btree_node_t *node);
-static void node_remove_key_and_lsubtree(btree_node_t *node, __native key);
-static void node_remove_key_and_rsubtree(btree_node_t *node, __native key);
 static index_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, index_t idx);
@@ -155,5 +155,5 @@
 
 		if (LEAF_NODE(node)) {
-			list_append(&rnode->leaf_link, &node->leaf_link);
+			list_prepend(&rnode->leaf_link, &node->leaf_link);
 		}
 		
@@ -190,5 +190,4 @@
 	btree_node_t *lnode;
 	
-	panic("%s needs testing and is disabled in revision %s\n", __FUNCTION__, REVISION);
 	lnode = leaf_node;
 	if (!lnode) {
@@ -437,127 +436,4 @@
 }
 
-/** Split full B-tree node and insert new key-value-right-subtree triplet.
- *
- * This function will split a node and return 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, __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_and_rsubtree(node, key, value, rsubtree);
-
-	/*
-	 * Compute median of keys.
-	 */
-	*median = MEDIAN_HIGH(node);
-		
-	/*
-	 * Allocate and initialize new right sibling.
-	 */
-	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.
-	 * If this is an index node, do not copy the median.
-	 */
-	i = (int) 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)
-{
-	index_t idx;
-	btree_node_t *rnode;
-	int 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;
-}
-
 /** Remove key and its left subtree pointer from B-tree node.
  *
@@ -615,4 +491,127 @@
 }
 
+/** Split full B-tree node and insert new key-value-right-subtree triplet.
+ *
+ * This function will split a node and return 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, __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_and_rsubtree(node, key, value, rsubtree);
+
+	/*
+	 * Compute median of keys.
+	 */
+	*median = MEDIAN_HIGH(node);
+		
+	/*
+	 * Allocate and initialize new right sibling.
+	 */
+	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.
+	 * If this is an index node, do not copy the median.
+	 */
+	i = (int) 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)
+{
+	index_t idx;
+	btree_node_t *rnode;
+	int 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.
  *
@@ -879,6 +878,7 @@
 {
 	int i, depth = t->root->depth;
-	link_t head;
-	
+	link_t head, *cur;
+
+	printf("Printing B-tree:\n");
 	list_initialize(&head);
 	list_append(&t->root->bfs_link, &head);
@@ -906,5 +906,5 @@
 		printf("(");
 		for (i = 0; i < node->keys; i++) {
-			printf("%d,", node->key[i]);
+			printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
 			if (node->depth && node->subtree[i]) {
 				list_append(&node->subtree[i]->bfs_link, &head);
@@ -917,3 +917,18 @@
 	}
 	printf("\n");
-}
+	
+	printf("Printing list of leaves:\n");
+	for (cur = t->leaf_head.next; cur != &t->leaf_head; cur = cur->next) {
+		btree_node_t *node;
+		
+		node = list_get_instance(cur, btree_node_t, leaf_link);
+		
+		ASSERT(node);
+
+		printf("(");
+		for (i = 0; i < node->keys; i++)
+			printf("%d%s", node->key[i], i < node->keys - 1 ? "," : "");
+		printf(")");
+	}
+	printf("\n");
+}