Quicksort en assembleur

.global _start
    
.data
size: .word 9
array: .word 2, 6, 3, 8, 5, 4, 1, 9, 7

    
_start:

    ldr r0, =array          // chargement de l'adresse du tableau dans r0
    mov r1, #0              // i = 0 = left
    ldr r2, =size
    ldr r2, [r2]            // j = 9 = right
        
    
        
        
quicksort:
// lt = less than <
// ge = greater than >=    

	push {r10}				// sauvegarde du r10 = pivot = target[i]
	push {lr}

    cmp r1, r2
    bge fin_si              // termine si i>=j

        
    whileiinfj:
    cmp r1, r2
    bge whileiinfj          // termine si i>=j sinon    
    
        
        
    ldr r10, [r0]           // pivot = valeur de l'index 0 dans r10
        whiletmpi:
        ldr r11, [r0]       // tmpi = valeur de l'index 0 dans r11
        cmp r11, r10
        bge whiletmpi       // termine si tmpi>=pivot sinon
        add r1, r1, #4      // calcul nouvel index i
        ldr r11, [r0, r1]   // tmpi = target[i] ou valeur du nouvel index i
        b whiletmpi
            
            
    ldr r12, [r0, r2]       // tmpj = valeur de l'index max dans r12            
        whiletmpj:
        cmp r10, r12        // compare pivot et tmpj
        bge whiletmpj       // termine si pivot>=tmpj sinon
        sub r2, r2, #4      // calcul nouvel index j
        ldr r12, [r0, r2]   // tmpj = target[j]
        b whiletmpj
    
    cmp r1, r2              // compare i et j
    bge fin_si              // termine si i>=j sinon
    ldr r12, [r0, r1]       // tmpj = target[i]             
    ldr r11, [r0, r2]       // tmpi = target[j]
    add r1, r1, #4          // i = i+1
    sub r2, r2, #4          // j = j-1
        
    b whileiinfj            // retourne en début de boucle whileiinfj	
	
	
	
	mov r2, r1				// paramètre r2 right = i
	sub r2, r2, #1			// paramètre r2 right = i-1            
    bl quicksort            // appel de la fonction dans la fonction
	
	mov r1, r2				// paramètre r1 left = j
	add r1, r1, #1			// paramètre r1 left = j+1 
    bl quicksort            // appel de la fonction dans la fonction  
   
      
   
	fin_si:                 // sort de la fonction
	pop {r10}           	// paramètre: restaure la valeur sauvegarde de r10
	pop {lr}
	
	
    bx lr                   // sort de la fonction  
                    




ldr r10, =array				// paramètre array
mov r1, #0					// paramètre 0
ldr r2, =size				// paramètre SIZE
sub r2, r2, #1				// paramètre SIZE-1
bl quicksort                // appel de la fonction avec paramètres

b .                         // boucle infinie

    push {r2}               // sauvegarder j
	sub r2, r1, #1			// paramètre r2 right = i-1            
    mov r1, r8              // on avait mémorisé dans r8 la valeur de left
    bl quicksort            // appel de la fonction dans la fonction
    pop {r2}                // retrouver j

	add r1, r2, #1			// paramètre r1 left = j+1
    move r2, r9             // on avait mémorisé dans r9 la valeur de right
    bl quicksort            // appel de la fonction dans la fonction  

    push {r8,r9,r10,r11,r12,lr}

    pop {r8,r9,r10,r11,r12,pc}

//ATTENTION: une fonction ne doit pas modifier les registres allant de r4 à r11. Pour avoir le droit de modifier ces registres si
//r0,r1,r2,r3 ne vous suffisent pas, alors il faut sauvegarder les registres que vous utilisez et annuler toutes vos modifications
//avant de quitter la fonction. Par exemple, les instructions push{r4,r5,r6} et pop{r4,r5,r6} permettent respectivement de sauvegarder
//les registres r4,r5,r6 et de les restaurer à leur état d'origine. (en utilisant la pile).

.text
.global _start


.data
size: .word 9
array: .word 2, 6, 3, 8, 5, 4, 1, 9, 7

    
_start:

    ldr r0, =array              // chargement de l'adresse du tableau dans r0
    mov r1, #0                  // i = 0 = left
    ldr r2, =size
    ldr r2, [r2]                // j = 9 = right
    
    
    ldr r10, =array             // paramètre array
    mov r1, #0                  // paramètre 0
    ldr r2, =size               // paramètre SIZE
    sub r2, r2, #1              // paramètre SIZE-1
    bl quicksort                // appel de la fonction avec paramètres
    b .                         // boucle infinie
        
    
        
        
quicksort:
// lt = less than <
// ge = greater than >=    

    push {r8,r9,r10,r11,r12,lr}    // sauvegarde des registres
    

    cmp r1, r2
    bge fin_si                  // termine si i>=j

        
    whileiinfj:
        cmp r1, r2
        bge whileiinfj          // termine si i>=j sinon        
        ldr r10, [r0]           // pivot = valeur de l'index 0 dans r10
        whiletmpi:
            ldr r11, [r0]       // tmpi = valeur de l'index 0 dans r11
            cmp r11, r10
            bge whiletmpi       // termine si tmpi>=pivot sinon
            add r1, r1, #4      // calcul nouvel index i
            ldr r11, [r0, r1]   // tmpi = target[i] ou valeur du nouvel index i
            b whiletmpi            
            
            
        ldr r12, [r0, r2]       // tmpj = valeur de l'index max dans r12            
        whiletmpj:
            cmp r10, r12        // compare pivot et tmpj
            bge whiletmpj       // termine si pivot>=tmpj sinon
            sub r2, r2, #4      // calcul nouvel index j
            ldr r12, [r0, r2]   // tmpj = target[j]
            b whiletmpj
    
    
        cmp r1, r2              // compare i et j
            bge fin_si          // termine si i>=j sinon
            ldr r12, [r0, r1]   // tmpj = target[i]             
            ldr r11, [r0, r2]   // tmpi = target[j]
            add r1, r1, #4      // i = i+1
            sub r2, r2, #4      // j = j-1
        
        b whileiinfj            // retourne en début de boucle whileiinfj    
    
    
    mov r2, r1                  // paramètre r2 right = i
    sub r2, r2, #1              // paramètre r2 right = i-1            
    bl quicksort                // appel de la fonction dans la fonction
    
    mov r1, r2                  // paramètre r1 left = j
    add r1, r1, #1              // paramètre r1 left = j+1 
    bl quicksort                // appel de la fonction dans la fonction  
   
      
   
    fin_si:                     // sort de la fonction
    pop {r8,r9,r10,r11,r12,pc}  // paramètre: restaure la valeur sauvegarde des registres
    
    
    
    bx lr                       // sort de la fonction

whiletmpi:
            ldr r11, [r0]       // tmpi = valeur de l'index 0 dans r11
            cmp r11, r10
            bge whiletmpi       // termine si tmpi>=pivot sinon
            add r1, r1, #4      // calcul nouvel index i
            ldr r11, [r0, r1]   // tmpi = target[i] ou valeur du nouvel index i
            b whiletmpi

whiletmpi:

whiletmpi:
            ldr r11, [r0, r1,shl 2]   // tmpi = target[i] ou valeur du nouvel index i, LE FOIS 4 EST ICI
            cmp r11, r10
            bge sortwhiletmpi       // termine si tmpi>=pivot sinon
            add r1, r1, #1      // calcul nouvel index i C'EST BIEN L'INDEX i
            b whiletmpi
sortwhiletmpi:

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
/* Définition des fonctions de tri */
/// tri à bulle croissante
void tri_a_bulle_c(int *t,int n){
    int j =0;int tmp =0;int test =1;
    while(test){
        test = FALSE;
        for(j =0; j < n-1; j++){
            if(t[j] > t[j+1]){
                    tmp = t[j+1];
                    t[j+1] = t[j];t[j] = tmp;
                    test = TRUE;
            }
        }
    }
}
/// tri à bulle
void tri_a_bulle_d(int *t,int n){
    int j =0;int tmp =0;int test =1;
    while(test){
        test = FALSE;
        for(j =n-1; j >0; j--){
            if(t[j] > t[j-1]){
                    tmp = t[j-1];
                    t[j-1] = t[j];
                    t[j] = tmp;
                    test = TRUE;
            }
        }
    }
}

/// tri par sélection croissance
void tri_selection_c(int *t, int n){
        int i, min, j , tmp;
        for(i =0; i < n -1; i++){
                min = i;
                for(j = i+1; j < n ; j++)
                    if(t[j] < t[min])
                        min = j;
                if(min != i){
                        tmp = t[i];
                        t[i] = t[min];
                        t[min] = tmp;
                }
        }
}
/// tri par sélection descroissance
void tri_selection_d(int *t, int n){
        int i, min, j , tmp;
        for(i =n-1; i <0; i--){
                min = i;
                for(j = i-1; j >0 ; j--)
                    if(t[j] > t[min])
                        min = j;
                if(min != i){
                        tmp = t[i];
                        t[i] = t[min];
                        t[min] = tmp;
                }
        }
}


/// tri par insertion croissance
void tri_insertion_c(int *t,int n){
        int i,p,j;
        int x;
        for(i =1; i < n; i++){
            x = t[i];p = i-1;
            while(t[p] > x && p-- >0){}
            p++;
            for(j = i-1; j >= p; j--){
                t[j+1] = t[j];
            }
            t[p] = x;
        }
}
/// tri par insertion
void tri_insertion_d(int *t,int n){
int i,j,x;
    for(i=1;i<=n-1;i++)
  {
      x=t[i];
      j=i;
      while((j>0) &&(t[j-1]<x))
      {
        t[j]=t[j-1];
        j=j-1;
      }
      t[j]=x;
  }

}


/* Fin de la définition des fonctions de tri */

int main(){
    int nb_entiers; /// nombre d'entiers à entrer
    int i;          /// compteur
    int num;       /// présentation
        printf("Programme : Algorithmes De Tri / %c Version 01 Le 19/10/2014\n",184);
        printf("R%calis%c par: Ahmed OUMEZZINE / 1%cre GENIE INFORMATIQUE \n",130,130,138);
        printf("Esprim - Young Developers\n\n");
/// lire nb_entiers
        printf("Donner le nombre d'entiers que vous voulez trier: ");
        scanf("%d",&nb_entiers);
/// allouer la mémoire pour tab[nb_entiers]
    int tab[nb_entiers];       /// tableau des entiers
/// remplir tab[nb_entiers]
        printf("\n");
        for(i=0;i<nb_entiers;i++){
        printf("Donner l'entier %d: ",i+1);
        scanf("%d",&tab[i]);
        }
/// liste des algorithmes de tri
        printf("\n1. Le tri %c bulle\n",133);
        printf("2. Le tri par s%cl%cction\n",130,130);
        printf("3. Le tri par insertion\n");
        printf("4. Le tri %c bulle D\n",133);
        printf("5. Le tri par s%cl%cction D\n",130,130);
        printf("6. Le tri par insertion D\n");

/// choisir l'algorithme à appliquer
        do{
            printf("\nVeuillez saisir le num%cro de de l'algorithme de tri %c appliquer: ",130,133);
        scanf("%d",&num);
        if((num>6)||(num<1))
            printf("\n(!) Ce num%cro ne figure pas dans la liste !\n",130);
        }while((num>6)||(num<1));
/// appliquer l'algorithme choisi
        if(num==1) tri_a_bulle_c(tab,nb_entiers);
        if(num==2) tri_selection_c(tab,nb_entiers);
        if(num==3) tri_insertion_c(tab,nb_entiers);
        if(num==4) tri_a_bulle_d(tab,nb_entiers);
        if(num==5) tri_selection_d(tab,nb_entiers);
        if(num==6) tri_insertion_d(tab,nb_entiers);

/// résultat
        printf("\nTRI%cS! : ",144);
        for(i=0;i<nb_entiers;i++)
            printf("%3d",tab[i]);
        printf("\n\n");
        system("PAUSE");
        return 0;
}

*
 * Btree example for DynnOS
 *

 *
 *
 */


/* 
** 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;
}