btree.c

/*
 * Btree example for DynnOS
 *
 * Quenza simple license
 * 2013, Dinux
 *
 *
 */


/* 
** B-Tree definition :
** Assume the degree of the tree is d(d>=2).
**   1. Every node has at most 2d children.
**   2. Every node (except root) has at least d children.
**   3. The root has at least 2 children if it is not a leaf node.
**   4. A non-leaf node with K children contains K-1 keys. And :
**      K[1]<=K[2]<=K[3]<=...<=K[K-1].
**   5. All leaves appear in the same level.
*/

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define EMPTY 0

#define NODE_ORDER		3 /*The degree of the tree.*/
#define NODE_POINTERS	(NODE_ORDER*2)
#define NODE_KEYS		NODE_POINTERS-1

typedef unsigned char bool;

typedef struct tree_node {
	int key_array[NODE_KEYS];
	struct tree_node *child_array[NODE_POINTERS];
	unsigned int key_index;
	bool leaf;
} node_t;

typedef struct {
	node_t *node_pointer;
	int key;
	bool found;
	unsigned int depth;
} result_t;

typedef struct {
	node_t *root;
	unsigned short order;
	bool lock;
} btree_t;

static int BTreeGetLeftMax(node_t *T);
static int BTreeGetRightMin(node_t *T);
/* The AllocateNode operation allocate a b-tree node.And then set the node's
** properties to the defualt value :
**   BTreeNode => K[i] = 0
**   BTreeNode => child_array[i] = NULL
**   BTreeNode => key_index = 0
**   BTreeNode => isLeaf = 1;
*/
static node_t *create_node()
{
	int i;
	node_t *new_node = (node_t *)malloc(sizeof(node_t));

	if(!new_node){
		printf("Out of memory");
		exit(0);
	}

	// Set Keys
	for(i = 0;i < NODE_KEYS; i++){
		new_node->key_array[i] = 0;
	}

	// Set ptr
	for(i = 0;i < NODE_POINTERS; i++){
		new_node->child_array[i] = NULL;
	}

	new_node->key_index = EMPTY;
	new_node->leaf = TRUE;

	return new_node;
}
/* The CreatBTree operation creates an empty b-tree by allocating a new root
** that has no keys and is a leaf node.Only the root node is permitted to
** have this properties.
*/
btree_t *create_btree()
{
	btree_t *new_root = (btree_t *)malloc(sizeof(btree_t));

	if(!new_root){
		return NULL;
	}

	node_t *head = create_node();

	if(!head){
		return NULL;
	}

	new_root->order = NODE_ORDER;
	new_root->root = head;
	new_root->lock = FALSE;

	return new_root;
}

static result_t *get_resultset()
{
	result_t *ret = (result_t *)malloc(sizeof(result_t));

	if(!ret){
		printf("ERROR! Out of memory.");
		exit(0);
	}

	ret->node_pointer = NULL;
	ret->key = 0;
	ret->found = FALSE;
	ret->depth = 0;

	return ret;
}

void print_node(node_t *n)
{
	int i, q;

	printf(">>-----0x%x-----\n", n);
	printf("  Index: %d\n", n->key_index);
	printf("   Leaf: ");
	if(n->leaf){
		printf("TRUE\n");
	}else{
		printf("FALSE\n");
	}

	printf("  Array:");
	for(i = 0; i < n->key_index; i++){
		printf(" [%d : %d]", i, n->key_array[i]);
	}

	printf("\n  Child:");
	if(n->leaf){
		printf(" NONE");
	}else{
		for(q = 0; q < NODE_POINTERS; q++){
			printf(" [%d : %x]", q, n->child_array[q]);
		}
	}

	printf("\n<<------------------\n");
}

/* The BTreeSearch operation is to search X in T.Recursively traverse the tree
** from top to bottom.At each level, BTreeSearch choose the maximum key whose
** value is greater than or equal to the desired value X.If equal to the
** desired ,found.Otherwise continue to traverse.
*/
result_t *search(int key, node_t *node)
{
	print_node(node);
	int i = 0;

	while((i < node->key_index) && (key > node->key_array[i])){
		//printf("it %d is <= %d and key %d > than %d\n", i, node->key_index, key, node->key_array[i]);
		i++;
	}
//printf("end iterator: %d\n", i);

//printf("better: \n");
/*
	int c = 0;

	while((c < node->key_index) && (key > node->key_array[c])){
		printf("it %d is <= %d and key %d > than %d\n", c, node->key_index, key, node->key_array[c]);
		c++;
	}
*/
	// HACK /// may not be working 
	if(i == 6){
		i--;
	}

	// Check if we found it
	if((i <= node->key_index) && (key == node->key_array[i])){
		result_t *result = get_resultset();
		result->node_pointer = node;
		result->key = i;
		result->found = TRUE;
		return result;
	}

	// Not found check leaf or child
	if(node->leaf){
		result_t *result = get_resultset();
		result->node_pointer = node;
		result->found = FALSE;
		return result;
	}else{
		result_t *result = get_resultset();
		return search(key, node->child_array[i]);
	}
}
/* The split_child operation moves the median key of node child_array into
** its parent ptrParent where child_array is the ith child of ptrParent.
*/
static void split_child(node_t *parent_node, int i, node_t *child_array)
{
	int j;

	//Allocate a new node to store child_array's node.
	node_t *new_node = create_node();
	new_node->leaf = child_array->leaf;
	new_node->key_index = NODE_ORDER-1;

	//Move child_array's right half nodes to the new node.
	for(j = 0;j < NODE_ORDER-1;j++){
		new_node->key_array[j] = child_array->key_array[NODE_ORDER+j];
	}

	//If child_array is not leaf node,then move child_array's [child_array]s to the new
	//node's [child_array]s.
	if(child_array->leaf == 0){
		for(j = 0;j < NODE_ORDER;j++){
			new_node->child_array[j] = child_array->child_array[NODE_ORDER+j];
		}
	}
	child_array->key_index = NODE_ORDER-1;

	//Right shift ptrParent's [child_array] from index i
	for(j = parent_node->key_index;j>=i;j--){
		parent_node->child_array[j+1] = parent_node->child_array[j];
	}

	//Set ptrParent's ith child_array to the newNode.
	parent_node->child_array[i] = new_node;

	//Right shift ptrParent's Keys from index i-1
	for(j = parent_node->key_index;j>=i;j--){
		parent_node->key_array[j] = parent_node->key_array[j-1];
	}

	//Set ptrParent's [i-1]th Key to child_array's median [child_array]
	parent_node->key_array[i-1] = child_array->key_array[NODE_ORDER-1];

	//Increase ptrParent's Key number.
	parent_node->key_index++;
}
/* The BTreeInsertNonFull operation insert X into a non-full node T.before
** execute this operation,guarantee T is not a full node.
*/
static void insert_nonfull(node_t *n, int key){
	int i = n->key_index;
	
	if(n->leaf){
		// Shift until we fit
		while(i>=1 && key<n->key_array[i-1]){
			n->key_array[i] = n->key_array[i-1];
			i--;
		}
		n->key_array[i] = key;
		n->key_index++;
	}else{
		// Find the position i to insert.
		while(i>=1 && key<n->key_array[i-1]){
			i--;
		}
		//If T's ith child_array is full,split first.
		if(n->child_array[i]->key_index == NODE_KEYS){
			split_child(n, i+1, n->child_array[i]);
			if(key > n->key_array[i]){
				i++;
			}
		}
		//Recursive insert.
		insert_nonfull(n->child_array[i], key);
	}
}
/* The BTreeInsert operation insert key into T.Before insert ,this operation
** check whether T's root node is full(root->key_index == 2*d -1) or not.If full,
** execute split_child to guarantee the parent never become full.And then
** execute BTreeInsertNonFull to insert X into a non-full node.
*/
node_t *insert(int key, btree_t *b)
{
	if(!b->lock){
		node_t *root = b->root;
		if(root->key_index == NODE_KEYS){ //If node root is full,split it.
			node_t *newNode = create_node();
			b->root = newNode; //Set the new node to T's Root.
			newNode->leaf = 0;
			newNode->key_index = 0;
			newNode->child_array[0] = root;
			split_child(newNode, 1, root);//Root is 1th child of newNode.
			insert_nonfull(newNode, key); //Insert X into non-full node.
		}else{ //If not full,just insert X in T.
			insert_nonfull(b->root, key);
		}
	}else{
		printf("Tree is locked\n");
	}

	return b->root;
}
/* The merge_children operation merge the root->K[index] and its two child
** and then set chlid1 to the new root.
*/
static void merge_children(node_t *root, int index, node_t *child1, node_t *child2){
	child1->key_index = NODE_KEYS;
	int i;
	//Move child2's key to child1's right half.
	for(i=NODE_ORDER;i<NODE_KEYS;i++)
		child1->key_array[i] = child2->key_array[i-NODE_ORDER];
	child1->key_array[NODE_ORDER-1] = root->key_array[index]; //Shift root->K[index] down.
	//If child2 is not a leaf node,must copy child2's [ptrchlid] to the new
	//root(child1)'s [child_array].
	if(0 == child2->leaf){
		for(i=NODE_ORDER;i<NODE_POINTERS;i++)
			child1->child_array[i] = child2->child_array[i-NODE_ORDER];
	}
	//Now update the root.
	for(i=index+1;i<root->key_index;i++){
		root->key_array[i-1] = root->key_array[i];
		root->child_array[i] = root->child_array[i+1];
	}
	root->key_index--;
	free(child2);
}
/* The BTreeBorrowFromLeft operation borrows a key from leftPtr.curPtr borrow
** a node from leftPtr.root->K[index] shift down to curPtr,shift leftPtr's
** right-max key up to root->K[index].
*/
static void BTreeBorrowFromLeft(node_t *root, int index, node_t *leftPtr, node_t *curPtr){
	curPtr->key_index++;
	int i;
	for(i=curPtr->key_index-1;i>0;i--)
		curPtr->key_array[i] = curPtr->key_array[i-1];
	curPtr->key_array[0] = root->key_array[index];
	root->key_array[index] = leftPtr->key_array[leftPtr->key_index-1];
	if(0 == leftPtr->leaf)
		for(i=curPtr->key_index;i>0;i--)
			curPtr->child_array[i] = curPtr->child_array[i-1];
	curPtr->child_array[0] = leftPtr->child_array[leftPtr->key_index];
	leftPtr->key_index--;
}
/* The BTreeBorrowFromLeft operation borrows a key from rightPtr.curPtr borrow
** a node from rightPtr.root->K[index] shift down to curPtr,shift RightPtr's
** left-min key up to root->K[index].
*/
static void BTreeBorrowFromRight(node_t *root, int index, node_t *rightPtr, node_t *curPtr){
	curPtr->key_index++;
	curPtr->key_array[curPtr->key_index-1] = root->key_array[index];
	root->key_array[index] = rightPtr->key_array[0];
	int i;
	for(i=0;i<rightPtr->key_index-1;i++)
		rightPtr->key_array[i] = rightPtr->key_array[i+1];
	if(0 == rightPtr->leaf){
		curPtr->child_array[curPtr->key_index] = rightPtr->child_array[0];
		for(i=0;i<rightPtr->key_index;i++)
			rightPtr->child_array[i] = rightPtr->child_array[i+1];
	}
	rightPtr->key_index--;
}
/* The BTreeDeleteNoNone operation recursively delete X in root,handle both leaf
** and internal node:
**   1. If X in a leaf node,just delete it.
**   2. If X in a internal node P:
**      a): If P's left neighbor -> prePtr has at least d keys,replace X with
**      	prePtr's right-max key and then recursively delete it.
**      b): If P's right neighbor -> nexPtr has at least d keys,replace X with
**      	nexPtr's left-min key and then recursively delete it.
**      c): If both of prePtr and nexPtr have d-1 keys,merge X and nexPtr into
**      	prePtr.Now prePtr have 2*d-1 keys,and then recursively delete X in
**      	prePtr.
**   3. If X not in a internal node P,X must in P->child_array[i] zone.If child_array[i]
**      only has d-1 keys:
**      a): If child_array[i]'s neighbor have at least d keys,borrow a key from
**      	child_array[i]'s neighbor.
**      b): If both of child_array[i]'s left and right neighbor have d-1 keys,merge
**      	child_array[i] with one of its neighbor.
**      finally,recursively delete X.
*/
static void BTreeDeleteNoNone(int X, node_t *root){
	int i;
	//Is root is a leaf node ,just delete it.
	if(1 == root->leaf){
		i=0;
		while( (i<root->key_index) && (X>root->key_array[i])) //Find the index of X.
			i++;
		//If exists or not.
		if(X == root->key_array[i]){
			for(;i<root->key_index-1;i++)
				root->key_array[i] = root->key_array[i+1];
			root->key_index--;
		}
		else{
			printf("Node not found.\n");
			return ;
		}
	}
	else{  //X is in a internal node.
		i = 0;
		node_t *prePtr = NULL, *nexPtr = NULL;
		//Find the index;
		while( (i<root->key_index) && (X>root->key_array[i]) )
			i++;
		if( (i<root->key_index) && (X == root->key_array[i]) ){ //Find it in this level.
			prePtr = root->child_array[i];
			nexPtr = root->child_array[i+1];
			/*If prePtr at least have d keys,replace X by X's precursor in
			 *prePtr*/
			if(prePtr->key_index > NODE_ORDER-1){
				int aPrecursor = BTreeGetLeftMax(prePtr);
				root->key_array[i] = aPrecursor;
				//Recursively delete aPrecursor in prePtr.
				BTreeDeleteNoNone(aPrecursor,prePtr);
			}
			else
			if(nexPtr->key_index > NODE_ORDER-1){
			/*If nexPtr at least have d keys,replace X by X's successor in
			 * nexPtr*/
				int aSuccessor = BTreeGetRightMin(nexPtr);
				root->key_array[i] = aSuccessor;
				BTreeDeleteNoNone(aSuccessor,nexPtr);
			}
			else{
			/*If both of root's two child have d-1 keys,then merge root->K[i]
			 * and prePtr nexPtr. Recursively delete X in the prePtr.*/
				merge_children(root,i,prePtr,nexPtr);
				BTreeDeleteNoNone(X,prePtr);
			}
		}
		else{ //Not find in this level,delete it in the next level.
			prePtr = root->child_array[i];
			node_t *leftBro = NULL;
			if(i<root->key_index)
				nexPtr = root->child_array[i+1];
			if(i>0)
				leftBro = root->child_array[i-1];
			/*root->child_array[i] need to borrow from or merge with his neighbor
			 * and then recursively delete. */
			if(NODE_ORDER-1 == prePtr->key_index){
			//If left-neighbor have at least d-1 keys,borrow.
				if( (leftBro != NULL) && (leftBro->key_index > NODE_ORDER-1))
					BTreeBorrowFromLeft(root,i-1,leftBro,prePtr);
				else //Borrow from right-neighbor
				if( (nexPtr != NULL) && (nexPtr->key_index > NODE_ORDER-1))
					BTreeBorrowFromRight(root,i,nexPtr,prePtr);
				//OR,merge with its neighbor.
				else if(leftBro != NULL){
					//Merge with left-neighbor
					merge_children(root,i-1,leftBro,prePtr);
					prePtr = leftBro;
				}
				else //Merge with right-neighbor
					merge_children(root,i,prePtr,nexPtr);
			}
			/*Now prePtr at least have d keys,just recursively delete X in
			 * prePtr*/
			BTreeDeleteNoNone(X,prePtr);
		}
	}
}
/*Get T's left-max key*/
static int BTreeGetLeftMax(node_t *T){
	if(0 == T->leaf){
		return BTreeGetLeftMax(T->child_array[T->key_index]);
	}else{
		return T->key_array[T->key_index-1];
	}
}
/*Get T's right-min key*/
static int BTreeGetRightMin(node_t *T){
	if(0 == T->leaf){
		return BTreeGetRightMin(T->child_array[0]);
	}else{
		return T->key_array[0];
	}
}
/* The BTreeDelete operation delete X from T up-to-down and no-backtrack.
** Before delete,check if it's necessary to merge the root and its children
** to reduce the tree's height.Execute BTreeDeleteNoNone to recursively delete
*/
node_t *delete(int key, btree_t *b)
{
	if(!b->lock){
		//if the root of T only have 1 key and both of T's two child have d-1
		//key,then merge the children and the root. Guarantee not need to backtrack.
		if(b->root->key_index == 1){
			node_t *child1 = b->root->child_array[0];
			node_t *child2 = b->root->child_array[1];
			if((!child1) && (!child2)){
				if((NODE_ORDER-1 == child1->key_index) && (NODE_ORDER-1 == child2->key_index)){
					//Merge the children and set child1 to the new root.
					merge_children(b->root, 0, child1, child2);
					free(b->root);
					BTreeDeleteNoNone(key, child1);
					return child1;
				}
			}
		}
		BTreeDeleteNoNone(key, b->root);
	}else{
		printf("Tree is locked\n");
	}
	return b->root;
}

void tree_unlock(btree_t *r)
{
	r->lock = FALSE;
}

bool tree_lock(btree_t *r)
{
	if(r->lock){
		return FALSE;
	}	
	r->lock = TRUE;

	return TRUE;
}

//---------------------------------TEST APP ------------------------------------------

void console(btree_t *b)
{
	int number;
	char name[256];

	printf("BTree> ");
	scanf("%s", name);
	
	if(!strcmp("add", name)){
		scanf("%d", &number);
		if(number){
			b->root = insert(number, b);
		}
		printf("Insert %d\n", number);
	}else if(!strcmp("del", name)){
		scanf("%d", &number);
		if(number){
			b->root = delete(number, b);
		}
		printf("Delete %d\n", number);
	}else if(!strcmp("search", name)){
		scanf("%d", &number);
		if(number){
			result_t *rs = search(number, b->root);
			if(rs->found){
				printf("Found\n");
				print_node(rs->node_pointer);
			}else{
				printf("Not found\n");
			}
		}
	}else if(!strcmp("tree", name)){
		printf("  Order: %d\n", b->order);
		printf("   Lock: ", b->lock);
		if(b->lock){
			printf("TRUE\n");
		}else{
			printf("FALSE\n");
		}
		print_node(b->root);
	}else if(!strcmp("lock", name)){
		tree_lock(b);
	}else if(!strcmp("unlock", name)){
		tree_unlock(b);
	}else if(!strcmp("exit", name)){
		exit(0);
	}else if(!strcmp("quit", name)){
		exit(0);
	}else{
		printf("Unknown [%s]\n", name);
	}

	return;
}

int main(int argc, char *argv[])
{
	int test[] = {1, -11, 12, 13, 15, 16, 17, 18, 19, 20, 25, 28, 29, 31,
				 35, 36, 39, 41, 42, 45, 55, 58, 59, 61, 67, 71, 73, 74,
				 76, 80, 81, 82, 83, 88, 89, 99, 83, 91, 93, 94, 95, 98};
	int test2[] = {-23, -234, -24, -3, -38, -82, -49, -72, -84, -27, -22,
				   -35, -9, -29, -374, -84, -24 , -92, -83, -372, -756};
	int todelete[] = {15, 19};

	btree_t *main = create_btree();
	int i;

	for(i=0; i<sizeof(test)/sizeof(int); i++){
		main->root = insert(test[i], main);
	}

	for(i=0; i<sizeof(test2)/sizeof(int); i++){
		main->root = insert(test2[i], main);
	}

	for(i=0; i<sizeof(todelete)/sizeof(int); i++){
		main->root = delete(todelete[i], main);
	}

	// Run console for easy testing
	for(;;){
		console(main);
	}

	return 0;
}