Index: tools/converter/btree.c
===================================================================
--- tools/converter/btree.c	(Revision 0)
+++ tools/converter/btree.c	(Revision 0)
@@ -0,0 +1,902 @@
+/*B-tree from lkml before 23.07.2006, licensed under GPLv2.
+ *  btree.c
+ *  Copyright (C) 2006 Vishal Patil (vishpat AT gmail DOT com)
+ *  Copyright (C) 2006 Frederik M.J.V. (comparistion and write functions)
+    TREE_EDITABLE should work, but isn't tested.
+*/
+
+/*LE write function from rockbox, scramble.c Copyright (C) 2002 by Bjørn Stenberg GPL*/
+#include "btree.h"
+
+typedef enum {left = -1,right = 1} position_t;
+
+typedef struct {
+	bt_node * node;
+	unsigned int index;
+}node_pos;
+
+static void print_single_node(btree *btree, bt_node * node);
+static bt_node * allocate_btree_node (unsigned int order);
+static int free_btree_node (bt_node * node);
+
+static node_pos get_btree_node(btree * btree,void * key);
+
+static int delete_key_from_node(btree * btree, node_pos * node_pos);
+static bt_node * merge_nodes(btree * btree, bt_node * n1, bt_key_val * kv ,bt_node * n2);
+static void move_key(btree * btree, bt_node * node, unsigned int index, position_t pos);
+
+static bt_node * merge_siblings(btree * btree, bt_node * parent,unsigned int index,
+					position_t pos);
+static void copy_key_val(btree * btree,bt_key_val * src, bt_key_val * dst);
+
+/**
+*	Used to create a btree with just the root node
+*	@param order The order of the B-tree
+*	@return The an empty B-tree
+*/
+btree * btree_create(unsigned int order) {
+	btree * btree;
+	btree = mem_alloc(sizeof(*btree));
+	btree->order = order;
+	btree->root = allocate_btree_node(order);
+	btree->root->leaf = true;
+	btree->root->nr_active = 0;
+	btree->root->next = NULL;
+	btree->root->level = 0;
+	return btree;
+}
+
+/**
+*       Function used to allocate memory for the btree node
+*       @param order Order of the B-Tree
+*	@param leaf boolean set true for a leaf node
+*       @return The allocated B-tree node
+*/
+static bt_node * allocate_btree_node (unsigned int order) {
+        bt_node * node;
+
+        /*Allocate memory for the node */
+        node = (bt_node *)mem_alloc(sizeof(bt_node));
+
+        /* Initialize the number of active nodes */
+        node->nr_active = 0;
+
+        /* Initialize the keys */
+        node->key_vals = (bt_key_val **)mem_alloc(2*order*sizeof(bt_key_val*) - 1);
+
+        /* Initialize the child pointers */
+        node->children = (bt_node **)mem_alloc(2*order*sizeof(bt_node*));
+
+	/* Use to determine whether it is a leaf */
+	node->leaf = true;
+
+	/* Use to determine the level in the tree */
+	node->level = 0;
+
+	/* Initialize the linked list pointer to NULL */
+	node->next = NULL;
+
+        return node;
+}
+
+/**
+*       Function used to free the memory allocated to the b-tree
+*       @param node The node to be freed
+*       @param order Order of the B-Tree
+*       @return The allocated B-tree node
+*/
+static int free_btree_node (bt_node * node) {
+
+        mem_free(node->children);
+        mem_free(node->key_vals);
+        mem_free(node);
+
+        return 0;
+}
+
+/**
+*	Used to split the child node and adjust the parent so that
+*	it has two children
+*	@param parent Parent Node
+*	@param index Index of the child node
+*	@param child  Full child node
+*
+*/
+static void btree_split_child(btree * btree, bt_node * parent,
+				unsigned int index,
+				bt_node * child) {
+	int i = 0;
+	unsigned int order = btree->order;
+
+	bt_node * new_child = allocate_btree_node(btree->order);
+	new_child->leaf = child->leaf;
+	new_child->level = child->level;
+	new_child->nr_active = btree->order - 1;
+
+	/* Copy the higher order keys to the new child	*/
+	for(i=0;i<order - 1;i++) {
+		new_child->key_vals[i] = child->key_vals[i + order];
+		if(!child->leaf) {
+			new_child->children[i] =
+				child->children[i + order];
+		}
+	}
+
+	/*  Copy the last child pointer */
+	if(!child->leaf) {
+		new_child->children[i] =
+		child->children[i + order];
+	}
+
+	child->nr_active = order - 1;
+
+	for(i = parent->nr_active + 1;i > index + 1;i--) {
+		parent->children[i] = parent->children[i - 1];
+	}
+	parent->children[index + 1] = new_child;
+
+	for(i = parent->nr_active;i > index;i--) {
+		parent->key_vals[i] = parent->key_vals[i - 1];
+	}
+
+	parent->key_vals[index] = child->key_vals[order - 1];
+	parent->nr_active++;
+}
+
+/**
+*	Used to insert a key in the non-full node
+*	@param btree The btree
+*	@param node The node to which the key will be added
+*	@param the key value pair
+*	@return void
+*/
+
+static void btree_insert_nonfull (btree * btree, bt_node * parent_node,
+				bt_key_val * key_val) {
+
+	int i ;
+	bt_node * child;
+	bt_node * node = parent_node;
+
+insert:	i = node->nr_active - 1;
+	if(node->leaf) {
+		while(i >= 0 && btree->compare(key_val->key,node->key_vals[i]->key)<0) {
+			node->key_vals[i + 1] = node->key_vals[i];
+			i--;
+		}
+		node->key_vals[i + 1] = key_val;
+		node->nr_active++;
+	} else {
+		while (i >= 0 && btree->compare(key_val->key,node->key_vals[i]->key)<0) {
+			i--;
+		}
+		i++;
+		child = node->children[i];
+
+		if(child->nr_active == 2*btree->order - 1) {
+			btree_split_child(btree,node,i,child);
+			if(btree->compare(key_val->key,node->key_vals[i]->key)>0) {
+				i++;
+			}
+		}
+		node = node->children[i];
+		goto insert;
+	}
+}
+
+
+/**
+*       Function used to insert node into a B-Tree
+*       @param root Root of the B-Tree
+*       @param node The node to be inserted
+*       @param compare Function used to compare the two nodes of the tree
+*       @return success or failure
+*/
+int btree_insert_key(btree * btree, bt_key_val * key_val) {
+	bt_node * rnode;
+
+	rnode = btree->root;
+	if(rnode->nr_active == (2*btree->order - 1)) {
+		bt_node * new_root;
+		new_root = allocate_btree_node(btree->order);
+		new_root->level = btree->root->level + 1;
+		btree->root = new_root;
+		new_root->leaf = false;
+		new_root->nr_active = 0;
+		new_root->children[0]  = rnode;
+		btree_split_child(btree,new_root,0,rnode);
+		btree_insert_nonfull(btree,new_root,key_val);
+	} else
+		btree_insert_nonfull(btree,rnode,key_val);
+
+        return 0;
+}
+#if TREE_EDITABLE
+/**
+*	Used to get the position of the MAX key within the subtree
+*	@param btree The btree
+*	@param subtree The subtree to be searched
+*	@return The node containing the key and position of the key
+*/
+static node_pos get_max_key_pos(btree * btree, bt_node * subtree) {
+	node_pos node_pos;
+	bt_node * node = subtree;
+
+	while(true) {
+		if(node == NULL) {
+			break;
+		}
+
+		if(node->leaf) {
+			node_pos.node 	= node;
+			node_pos.index 	= node->nr_active - 1;
+			return node_pos;
+		} else {
+			node_pos.node 	= node;
+			node_pos.index 	= node->nr_active - 1;
+			node = node->children[node->nr_active];
+		}
+	}
+	return node_pos;
+}
+
+/**
+*	Used to get the position of the MAX key within the subtree
+*	@param btree The btree
+*	@param subtree The subtree to be searched
+*	@return The node containing the key and position of the key
+*/
+static node_pos get_min_key_pos(btree * btree, bt_node * subtree) {
+	node_pos node_pos;
+	bt_node * node = subtree;
+
+	while(true) {
+		if(node == NULL) {
+			break;
+		}
+
+		if(node->leaf) {
+			node_pos.node 	= node;
+			node_pos.index 	= 0;
+			return node_pos;
+		} else {
+			node_pos.node 	= node;
+			node_pos.index 	= 0;
+			node = node->children[0];
+		}
+	}
+	return node_pos;
+}
+
+/**
+*	Merge nodes n1 and n2 (case 3b from Cormen)
+*	@param btree The btree
+*	@param node The parent node
+*	@param index of the child
+*	@param pos left or right
+*	@return none
+*/
+static bt_node * merge_siblings(btree * btree, bt_node * parent, unsigned int index ,
+					position_t pos) {
+	unsigned int i,j;
+	bt_node * new_node;
+	bt_node * n1, * n2;
+
+        if (index == (parent->nr_active)) {
+               index--;
+	       n1 = parent->children[parent->nr_active - 1];
+	       n2 = parent->children[parent->nr_active];
+        } else {
+               n1 = parent->children[index];
+	       n2 = parent->children[index + 1];
+        }
+
+	/* Merge the current node with the left node */
+	new_node = allocate_btree_node(btree->order);
+	new_node->level = n1->level;
+	new_node->leaf = n1->leaf;
+
+	for(j=0;j<btree->order - 1; j++) {
+		new_node->key_vals[j] =	n1->key_vals[j];
+		new_node->children[j] =	n1->children[j];
+	}
+
+	new_node->key_vals[btree->order - 1] =	parent->key_vals[index];
+	new_node->children[btree->order - 1] =	n1->children[btree->order - 1];
+
+	for(j=0;j<btree->order - 1; j++) {
+		new_node->key_vals[j + btree->order] = 	n2->key_vals[j];
+		new_node->children[j + btree->order] = 	n2->children[j];
+	}
+	new_node->children[2*btree->order - 1] = n2->children[btree->order - 1];
+
+	parent->children[index] = new_node;
+
+	for(j = index;j<parent->nr_active;j++) {
+		parent->key_vals[j] = parent->key_vals[j + 1];
+		parent->children[j + 1] = parent->children[j + 2];
+	}
+
+	new_node->nr_active = n1->nr_active + n2->nr_active + 1;
+	parent->nr_active--;
+
+	for(i=parent->nr_active;i < 2*btree->order - 1; i++) {
+		parent->key_vals[i] = NULL;
+	}
+
+	free_btree_node(n1);
+	free_btree_node(n2);
+
+	if (parent->nr_active == 0 && btree->root == parent) {
+		free_btree_node(parent);
+		btree->root = new_node;
+		if(new_node->level)
+			new_node->leaf = false;
+		else
+			new_node->leaf = true;
+	}
+
+	return new_node;
+	}
+
+/**
+*	Move the key from node to another
+*	@param btree The B-Tree
+*	@param node The parent node
+*	@param index of the key to be moved done
+*	@param pos the position of the child to receive the key
+*	@return none
+*/
+static void move_key(btree * btree, bt_node * node, unsigned int index, position_t pos) {
+	bt_node * lchild;
+	bt_node * rchild;
+	unsigned int i;
+
+	if(pos == right) {
+		index--;
+	}
+	lchild = node->children[index];
+	rchild = node->children[index + 1];
+
+	/* Move the key from the parent to the left child */
+	if(pos == left) {
+		lchild->key_vals[lchild->nr_active] = node->key_vals[index];
+		lchild->children[lchild->nr_active + 1] = rchild->children[0];
+		rchild->children[0] = NULL;
+		lchild->nr_active++;
+
+		node->key_vals[index] = rchild->key_vals[0];
+		rchild->key_vals[0] = NULL;
+
+		for(i=0;i<rchild->nr_active - 1;i++) {
+			rchild->key_vals[i] = rchild->key_vals[i + 1];
+			rchild->children[i] = rchild->children[i + 1];
+		}
+		rchild->children[rchild->nr_active - 1] =
+				rchild->children[rchild->nr_active];
+		rchild->nr_active--;
+	} else {
+		/* Move the key from the parent to the right child */
+		for(i=rchild->nr_active;i > 0 ; i--) {
+			rchild->key_vals[i] = rchild->key_vals[i - 1];
+			rchild->children[i + 1] = rchild->children[i];
+		}
+		rchild->children[1] = rchild->children[0];
+		rchild->children[0] = NULL;
+
+		rchild->key_vals[0] = node->key_vals[index];
+
+		rchild->children[0] = lchild->children[lchild->nr_active];
+		lchild->children[lchild->nr_active] = NULL;
+
+		node->key_vals[index] = lchild->key_vals[lchild->nr_active - 1];
+		lchild->key_vals[lchild->nr_active - 1] = NULL;
+
+		lchild->nr_active--;
+		rchild->nr_active++;
+	}
+}
+
+/**
+*	Merge nodes n1 and n2
+*	@param n1 First node
+*	@param n2 Second node
+*	@return combined node
+*/
+static bt_node * merge_nodes(btree * btree, bt_node * n1, bt_key_val * kv,
+                                                bt_node * n2) {
+	bt_node * new_node;
+	unsigned int i;
+
+	new_node = allocate_btree_node(btree->order);
+	new_node->leaf = true;
+
+	for(i=0;i<n1->nr_active;i++) {
+		new_node->key_vals[i]   = n1->key_vals[i];
+                new_node->children[i]   = n1->children[i];
+	}
+        new_node->children[n1->nr_active] = n1->children[n1->nr_active];
+        new_node->key_vals[n1->nr_active] = kv;
+
+	for(i=0;i<n2->nr_active;i++) {
+		new_node->key_vals[i + n1->nr_active + 1] = n2->key_vals[i];
+                new_node->children[i + n1->nr_active + 1] = n2->children[i];
+	}
+        new_node->children[2*btree->order - 1] = n2->children[n2->nr_active];
+
+        new_node->nr_active = n1->nr_active + n2->nr_active + 1;
+        new_node->leaf = n1->leaf;
+        new_node->level = n1->level;
+
+	free_btree_node(n1);
+	free_btree_node(n2);
+
+	return new_node;
+}
+
+/**
+*	Used to delete a key from the B-tree node
+*	@param btree The btree
+*	@param node The node from which the key is to be deleted
+*	@param key The key to be deleted
+*	@return 0 on success -1 on error
+*/
+
+int delete_key_from_node(btree * btree, node_pos * node_pos) {
+	unsigned int keys_max = 2*btree->order - 1;
+	unsigned int i;
+	bt_key_val * key_val;
+	bt_node * node = node_pos->node;
+
+	if(node->leaf == false) {
+		return -1;
+	}
+
+	key_val = node->key_vals[node_pos->index];
+
+	for(i=node_pos->index;i< keys_max - 1;i++) {
+		node->key_vals[i] = node->key_vals[i + 1];
+	}
+
+	if(key_val->key) {
+		mem_free(key_val->key);
+                key_val->key = NULL;
+	}
+
+	if(key_val->val) {
+		mem_free(key_val->val);
+                key_val->val = NULL;
+	}
+
+	node->nr_active--;
+
+	if(node->nr_active == 0 ) {
+		free_btree_node(node);
+	}
+	return 0;
+}
+
+/**
+*       Function used to delete a node from a  B-Tree
+*       @param btree The B-Tree
+*       @param key Key of the node to be deleted
+*       @param value function to map the key to an unique integer value
+*       @param compare Function used to compare the two nodes of the tree
+*       @return success or failure
+*/
+
+int btree_delete_key(btree * btree,bt_node * subtree,void * key) {
+	unsigned int i,index;
+	bt_node * node = NULL, * rsibling, *lsibling;
+	bt_node * comb_node, * parent;
+	node_pos sub_node_pos;
+	node_pos node_pos;
+	bt_key_val * key_val, * new_key_val;
+
+	node = subtree;
+	parent = NULL;
+
+del_loop:for (i = 0;;i = 0) {
+
+            /* If there are no keys simply return */
+            if(!node->nr_active)
+                return -1;
+
+	    /* Fix the index of the key greater than or equal
+	       to the key that we would like to search */
+
+	    while (i < node->nr_active && btree->compare(key,
+			    node->key_vals[i]->key)>0 ) {
+		    i++;
+	    }
+	    index = i;
+
+	    /* If we find such key break */
+	    if(i < node->nr_active &&
+			btree->compare(key,node->key_vals[i]->key)==0) {
+			break;
+	    }
+        if(node->leaf)
+            return -1;
+
+    	    /* Store the parent node */
+	    parent = node;
+
+	    /* To get a child node */
+	    node = node->children[i];
+
+            /* If NULL not found */
+            if (node == NULL)
+                return -1;
+
+            if (index == (parent->nr_active)) {
+                lsibling =  parent->children[parent->nr_active - 1];
+	    	rsibling = NULL;
+            } else if (index == 0) {
+                lsibling = NULL;
+                rsibling = parent->children[1];
+            } else {
+        	lsibling = parent->children[i - 1];
+	    	rsibling = parent->children[i + 1];
+            }
+
+	    if (node->nr_active == btree->order - 1 && parent) {
+		/* The current node has (t - 1) keys but the right sibling has > (t - 1)
+		   keys */
+		if (rsibling && (rsibling->nr_active > btree->order - 1)) {
+			move_key(btree,parent,i,left);
+		} else
+		/* The current node has (t - 1) keys but the left sibling has (t - 1)
+		   keys */
+		if (lsibling && (lsibling->nr_active > btree->order - 1)) {
+			move_key(btree,parent,i,right);
+		} else
+		/* Left sibling has (t - 1) keys */
+	        if(lsibling && (lsibling->nr_active == btree->order - 1)) {
+		        node = merge_siblings(btree,parent,i,left);
+		} else
+                /* Right sibling has (t - 1) keys */
+	        if(rsibling && (rsibling->nr_active == btree->order - 1)) {
+		        node = merge_siblings(btree,parent,i,right);
+		}
+	    }
+        }
+
+	/* Case 1 : The node containing the key is found and is the leaf node.
+	   Also the leaf node has keys greater than the minimum required.
+	   Simply remove the key */
+	if(node->leaf && (node->nr_active > btree->order - 1)) {
+		node_pos.node = node;
+		node_pos.index = index;
+		delete_key_from_node(btree,&node_pos);
+		return 0;
+	}
+
+	/* If the leaf node is the root permit deletion even if the number of keys is
+	   less than (t - 1) */
+	if(node->leaf && (node == btree->root)) {
+		node_pos.node = node;
+		node_pos.index = index;
+		delete_key_from_node(btree,&node_pos);
+		return 0;
+	}
+
+
+	/* Case 2: The node containing the key is found and is an internal node */
+	if(node->leaf == false) {
+		if(node->children[index]->nr_active > btree->order - 1 ) {
+			sub_node_pos = get_max_key_pos(btree,node->children[index]);
+                        key_val = sub_node_pos.node->key_vals[sub_node_pos.index];
+
+                        new_key_val = (bt_key_val *)mem_alloc(sizeof(bt_key_val));
+                        copy_key_val(btree,key_val,new_key_val);
+        		node->key_vals[index] = new_key_val;
+
+                        btree_delete_key(btree,node->children[index],key_val->key);
+			if(sub_node_pos.node->leaf == false) {
+                                print("Not leaf\n");
+                        }
+		} else if ((node->children[index + 1]->nr_active > btree->order - 1) ) {
+			sub_node_pos =
+                                get_min_key_pos(btree,node->children[index + 1]);
+                        key_val = sub_node_pos.node->key_vals[sub_node_pos.index];
+
+                        new_key_val = (bt_key_val *)mem_alloc(sizeof(bt_key_val));
+                        copy_key_val(btree,key_val,new_key_val);
+        		node->key_vals[index] = new_key_val;
+
+                        btree_delete_key(btree,node->children[index + 1],key_val->key);
+			if(sub_node_pos.node->leaf == false) {
+                                print("Not leaf\n");
+                        }
+
+		} else if (
+			node->children[index]->nr_active == btree->order - 1 &&
+			node->children[index + 1]->nr_active == btree->order - 1) {
+
+			comb_node = merge_nodes(btree,node->children[index],
+                                node->key_vals[index],
+				node->children[index + 1]);
+			node->children[index] = comb_node;
+
+			for(i=index + 1;i<node->nr_active;i++) {
+				node->children[i] = node->children[i + 1];
+				node->key_vals[i - 1] = node->key_vals[i];
+			}
+			node->nr_active--;
+                        if (node->nr_active == 0 && btree->root == node) {
+                                free_btree_node(node);
+                                btree->root = comb_node;
+                        }
+                        node = comb_node;
+                        goto del_loop;
+		}
+          }
+
+	/* Case 3:
+	   In this case start from the top of the tree and continue
+	   moving to the leaf node making sure that each node that
+	   we encounter on the way has atleast 't' (order of the tree)
+	   keys */
+	if(node->leaf && (node->nr_active > btree->order - 1)) {
+	      node_pos.node = node;
+	      node_pos.index = index;
+	      delete_key_from_node(btree,&node_pos);
+	}
+
+        return 0;
+}
+#endif
+/**
+*	Function used to get the node containing the given key
+*	@param btree The btree to be searched
+*	@param key The the key to be searched
+*	@return The node and position of the key within the node
+*/
+node_pos get_btree_node(btree * btree,void * key) {
+	node_pos kp;
+	kp.node=NULL;
+	kp.index=0;
+	bt_node * node;
+	unsigned int i = 0;
+	node = btree->root;
+
+	for (;;i = 0) {
+
+	    /* Fix the index of the key greater than or equal
+	       to the key that we would like to search */
+
+	    while (i < node->nr_active && btree->compare(key, node->key_vals[i]->key)>0 )
+		    i++;
+
+	    /* If we find such key return the key-value pair */
+	    if(i < node->nr_active && btree->compare(key,node->key_vals[i]->key)==0) {
+		    kp.node = node;
+		    kp.index = i;
+		    return kp;
+	    }
+
+	    /* If the node is leaf and if we did not find the key
+	       return NULL */
+	    if(node->leaf){
+	    	return kp;
+	    }
+
+	    /* To got a child node */
+	    node = node->children[i];
+	}
+      	return kp;
+
+}
+
+/**
+*       Used to destory btree
+*       @param btree The B-tree
+*       @return none
+*/
+void btree_destroy(btree * btree) {
+       int i = 0;
+       unsigned int current_level;
+
+       bt_node * head, * tail, * node;
+       bt_node * child, * del_node;
+
+       node = btree->root;
+       current_level = node->level;
+       head = node;
+       tail = node;
+
+       while(true) {
+               if(head == NULL) {
+                       break;
+               }
+               if (head->level < current_level) {
+                       current_level = head->level;
+               }
+
+               if(head->leaf == false) {
+                       for(i = 0 ; i < head->nr_active + 1; i++) {
+                               child = head->children[i];
+                               tail->next = child;
+                               tail = child;
+                               child->next = NULL;
+                       }
+               }
+               del_node = head;
+               head = head->next;
+               free_btree_node(del_node);
+       }
+
+}
+
+/**
+*       Function used to search a node in a B-Tree
+*       @param btree The B-tree to be searched
+*       @param key Key of the node to be search
+*       @return The key-value pair
+*/
+bt_key_val * btree_search(btree * btree,void * key) {
+
+	bt_key_val * key_val = NULL;
+	node_pos kp = get_btree_node(btree,key);
+
+	if(kp.node) {
+		key_val = kp.node->key_vals[kp.index];
+	}
+	return key_val;
+}
+
+/**
+*       Used to copy key value from source to destination
+*       @param src The source key value
+*       @param dst The dest key value
+*       @return none
+*/
+static void copy_key_val(btree * btree, bt_key_val * src, bt_key_val * dst) {
+        unsigned int keysize;
+        unsigned int datasize;
+
+        keysize    = btree->key_size(src->key);
+        dst->key        = (void *)mem_alloc(keysize);
+        bcopy(src->key,dst->key,keysize);
+
+        if(src->val) {
+                datasize   = btree->data_size(src->val);
+                dst->val       = (void *)mem_alloc(datasize);
+                bcopy(src->val,dst->val,datasize);
+        }
+
+}
+#if 0
+/**
+*	Get the max key in the btree
+*	@param btree The btree
+*	@return The max key
+*/
+void * btree_get_max_key(btree * btree) {
+	node_pos node_pos;
+	node_pos = get_max_key_pos(btree,btree->root);
+	return node_pos.node->key_vals[node_pos.index]->key;
+}
+
+/**
+*	Get the min key in the btree
+*	@param btree The btree
+*	@return The max key
+*/
+void * btree_get_min_key(btree * btree) {
+	node_pos node_pos;
+	node_pos = get_min_key_pos(btree,btree->root);
+	return node_pos.node->key_vals[node_pos.index]->key;
+}
+
+#endif
+#ifdef DEBUG
+#include <stdint.h>
+/**
+*	Used to print the keys of the bt_node
+*	@param node The node whose keys are to be printed
+*	@return none
+*/
+
+static void print_single_node(btree *btree, bt_node * node) {
+
+	int i = 0;
+
+	print(" { ");
+	while(i < node->nr_active) {
+		print("(%d)%s(%d) ",btree->key_size(node->key_vals[i]->key),
+			(node->key_vals[i]->key+sizeof(int16_t)),node->level);
+		i++;
+	}
+	print("} (0x%x,%d) ", node,node->leaf);
+}
+
+/**
+*       Function used to print the B-tree
+*       @param root Root of the B-Tree
+*       @param print_key Function used to print the key value
+*       @return none
+*/
+
+void print_subtree(btree *btree,bt_node * node) {
+
+	int i = 0;
+	unsigned int current_level;
+
+	bt_node * head, * tail;
+	bt_node * child;
+
+	current_level = node->level;
+	head = node;
+	tail = node;
+
+	while(true) {
+		if(head == NULL) {
+			break;
+		}
+		if (head->level < current_level) {
+			current_level = head->level;
+			print("\n");
+		}
+		print_single_node(btree,head);
+
+		if(head->leaf == false) {
+			for(i = 0 ; i < head->nr_active + 1; i++) {
+				child = head->children[i];
+				tail->next = child;
+				tail = child;
+				child->next = NULL;
+			}
+		}
+		head = head->next;
+	}
+	print("\n");
+}
+static node_pos get_max_key_pos(btree * btree, bt_node * subtree) {
+	node_pos node_pos;
+	bt_node * node = subtree;
+
+	while(true) {
+		if(node == NULL) {
+			break;
+		}
+
+		if(node->leaf) {
+			node_pos.node 	= node;
+			node_pos.index 	= node->nr_active - 1;
+			return node_pos;
+		} else {
+			node_pos.node 	= node;
+			node_pos.index 	= node->nr_active - 1;
+			node = node->children[node->nr_active];
+		}
+	}
+	return node_pos;
+}
+
+
+uint32_t btree_write(FILE *file,btree *btree,bt_node *node) {
+	long ndestrtfo,tmpfo;
+	unsigned short i,tmp;
+	bt_node * child;
+	ndestrtfo=ftell(file);
+	if(node==0){
+		 printf("NDNL\n");
+		 return 0;
+	}
+	uint32_t rtcldptr=0;
+	uint32_t chldptrs[node->nr_active+1];
+	fseek(file,ndestrtfo+btree->node_write_len(btree,node),SEEK_SET);
+	if(node->leaf==false){
+		for(i=0;i < node->nr_active+1;i++){
+			chldptrs[i]=btree_write(file,btree,node->children[i]);
+		}
+	}
+	tmpfo=ftell(file);
+	fseek(file,ndestrtfo,SEEK_SET);
+	btree->node_write(file,btree,node,chldptrs);
+	fseek(file,tmpfo,SEEK_SET);
+	return (uint32_t)ndestrtfo;
+}
+#endif