/***************************************************************************
 *     Copyright (c) 2007 Broadcom Corporation
 *     All Rights Reserved
 *     Confidential Property of Broadcom Corporation
 *
 *  THIS SOFTWARE MAY ONLY BE USED SUBJECT TO AN EXECUTED SOFTWARE LICENSE
 *  AGREEMENT  BETWEEN THE USER AND BROADCOM.  YOU HAVE NO RIGHT TO USE OR
 *  EXPLOIT THIS MATERIAL EXCEPT SUBJECT TO THE TERMS OF SUCH AN AGREEMENT.
 *
 * $brcm_Workfile: baa_tree.c $
 * $brcm_Revision: 2 $
 * $brcm_Date: 7/8/09 11:48a $
 *
 * Module Description:
 *
 * Interface for AA tree, type of binary search tree
 * Revision History:
 *
 * $brcm_Log: /BSEAV/lib/utils/baa_tree.c $
 * 
 * 2   7/8/09 11:48a vsilyaev
 * PR 55989: Fixed use of typecasting
 * 
 * 1   8/6/07 3:59p vsilyaev
 * PR 33812: Initial implementation of AA binary search tree
 * 
 ***************************************************************************/

#include "bstd.h"
#include "baa_tree.h"
BDBG_MODULE(baa_tree);


#define B_AA_NODE_LEVEL(node) ((node)->aa_node.aan_level)
#define B_AA_LAST_NODE(tree) (&(tree)->aat_root)
#define B_AA_ROOT_NODE(tree) (&(tree)->aat_root)


void 
baat_init(struct baa_tree_head *tree)
{
	tree->aat_root.aa_node.aan_level = 0;
	tree->aat_root.aa_node.aan_left = B_AA_LAST_NODE(tree);
	tree->aat_root.aa_node.aan_right = B_AA_LAST_NODE(tree);
	tree->aat_root.aa_node.aan_parent = B_AA_ROOT_NODE(tree);
	return;
}


struct baa_tree_node *
baat_first(const struct baa_tree_head *tree, unsigned off) 
{
	struct baa_tree_node *root = tree->aat_root.aa_node.aan_left;
	struct baa_tree_node *parent = NULL;
	while(root!=B_AA_LAST_NODE(tree)) {
		parent = root;
		root = root->aa_node.aan_left;
	}
    if(parent) {
	    return B_AA_TREE_CAST(parent, baa_tree_node, off);
    } else {
	    return NULL;
    }
}

struct baa_tree_node *
baat_last(const struct baa_tree_head *tree, unsigned off) 
{
	struct baa_tree_node *root = tree->aat_root.aa_node.aan_left;
	struct baa_tree_node *parent = NULL;
	while(root!=B_AA_LAST_NODE(tree)) {
		parent = root;
		root = root->aa_node.aan_right;
	}
    if(parent) {
	    return B_AA_TREE_CAST(parent, baa_tree_node, off);
    } else {
        return NULL;
    }
}

struct baa_tree_node *
baat_next(struct baa_tree_head *tree, struct baa_tree_node *node, unsigned off)
{
	struct baa_tree_node *next;
	node = B_AA_TREE_NODE(node, off);

	next = node->aa_node.aan_right;
	if(B_AA_LAST_NODE(tree)!=next) {
		node = next;
		while(B_AA_LAST_NODE(tree)!=(next=node->aa_node.aan_left)) {
			node = next;
		}
	} else {
		while( (B_AA_ROOT_NODE(tree) != (next=node->aa_node.aan_parent)) && (node==next->aa_node.aan_right)) {
			node = next;
		}
		node = next;
		if(node==B_AA_ROOT_NODE(tree)) {
			return NULL;
		}
	}
	return B_AA_TREE_CAST(node, baa_tree_node, off);
}

struct baa_tree_node *
baat_prev(struct baa_tree_head *tree, struct baa_tree_node *node, unsigned off)
{
	struct baa_tree_node *prev;

	node = B_AA_TREE_NODE(node, off);

	prev = node->aa_node.aan_left;
	if(B_AA_LAST_NODE(tree)!=prev) {
		node = prev;
		while(B_AA_LAST_NODE(tree)!=(prev=node->aa_node.aan_right)) {
			node = prev;
		}
	} else {
		while( (B_AA_ROOT_NODE(tree) != (prev=node->aa_node.aan_parent)) && (node==prev->aa_node.aan_left)) {
			node = prev;
		}
		node = prev;
		if(node==B_AA_ROOT_NODE(tree)) {
			return NULL;
		}
	}
	return B_AA_TREE_CAST(node, baa_tree_node, off);
}

static void 
baat_skew(struct baa_tree_node *parent)
{
	struct baa_tree_node *new_parent = parent->aa_node.aan_left;

	BDBG_ASSERT(new_parent);

	if(parent->aa_node.aan_parent->aa_node.aan_left == parent) {
		parent->aa_node.aan_parent->aa_node.aan_left = new_parent;
	} else {
		parent->aa_node.aan_parent->aa_node.aan_right = new_parent;
	}
	new_parent->aa_node.aan_parent = parent->aa_node.aan_parent;
	parent->aa_node.aan_parent = new_parent;

	parent->aa_node.aan_left = new_parent->aa_node.aan_right;
	parent->aa_node.aan_left->aa_node.aan_parent = parent;
	new_parent->aa_node.aan_right = parent;

	parent->aa_node.aan_level = B_AA_NODE_LEVEL(parent->aa_node.aan_left)+1;

	return;
}

static bool 
baat_split(struct baa_tree_head *tree, struct baa_tree_node *parent)
{
	struct baa_tree_node *new_parent = parent->aa_node.aan_right;

	if(B_AA_LAST_NODE(tree)!=new_parent && parent->aa_node.aan_right->aa_node.aan_right->aa_node.aan_level == parent->aa_node.aan_level) {
		if(parent->aa_node.aan_parent->aa_node.aan_left == parent) {
			parent->aa_node.aan_parent->aa_node.aan_left = new_parent;
		} else {
			parent->aa_node.aan_parent->aa_node.aan_right = new_parent;
		}
		new_parent->aa_node.aan_parent = parent->aa_node.aan_parent;
		parent->aa_node.aan_parent = new_parent;

		parent->aa_node.aan_right = new_parent->aa_node.aan_left;
		parent->aa_node.aan_right->aa_node.aan_parent = parent;
		new_parent->aa_node.aan_left = parent;
		new_parent->aa_node.aan_level++;
		return true;
	}
	return false;
}


void 
baat_insert_node(struct baa_tree_head *tree, struct baa_tree_node *new_node, struct baa_tree_node *parent, int cmp)
{
	struct baa_tree_node *node;

	if(cmp<0) {
		parent->aa_node.aan_left = new_node;
	} else {
		parent->aa_node.aan_right = new_node;
	} 
	new_node->aa_node.aan_level = 1;
	new_node->aa_node.aan_left = B_AA_LAST_NODE(tree);
	new_node->aa_node.aan_right = B_AA_LAST_NODE(tree);
	new_node->aa_node.aan_parent = parent;
	for(node=parent; node!= B_AA_ROOT_NODE(tree) ; node = node->aa_node.aan_parent) {
		if(node->aa_node.aan_level != B_AA_NODE_LEVEL(node->aa_node.aan_left) + 1) {
			baat_skew(node);
			if( (node->aa_node.aan_level != node->aa_node.aan_right->aa_node.aan_level)) {
				node = node->aa_node.aan_parent;
			}
		}
		if(!baat_split(tree, node->aa_node.aan_parent)) {
			break;
		}
	}
}



void 
baat_remove(struct baa_tree_head *tree, struct baa_tree_node *node)
{
	 struct baa_tree_node *leaf;
	 struct baa_tree_node *parent;

	 if(B_AA_LAST_NODE(tree)!=node->aa_node.aan_left) {
		 for(leaf=node->aa_node.aan_left;B_AA_LAST_NODE(tree)!=leaf->aa_node.aan_right;leaf=leaf->aa_node.aan_right) {
		 }
	 } else {
		 if(B_AA_LAST_NODE(tree)!=node->aa_node.aan_right) {
			 leaf = node->aa_node.aan_right;
		 } else {
			 leaf = node;
		 }
	 }
	 parent = leaf->aa_node.aan_parent == node ? leaf : leaf->aa_node.aan_parent;
	 if(leaf->aa_node.aan_parent->aa_node.aan_left == leaf) {
		 leaf->aa_node.aan_parent->aa_node.aan_left = B_AA_LAST_NODE(tree);
	 } else {
		 leaf->aa_node.aan_parent->aa_node.aan_right = B_AA_LAST_NODE(tree);
	 }
	 if(node!=leaf) { /* swap leaf and node */
		 if(node->aa_node.aan_parent->aa_node.aan_left == node) {
			 node->aa_node.aan_parent->aa_node.aan_left = leaf;
		 } else {
			 node->aa_node.aan_parent->aa_node.aan_right = leaf;
		 }
		 leaf->aa_node.aan_parent = node->aa_node.aan_parent;
		 node->aa_node.aan_left->aa_node.aan_parent = leaf;
		 leaf->aa_node.aan_left = node->aa_node.aan_left;

		 node->aa_node.aan_right->aa_node.aan_parent = leaf;
		 leaf->aa_node.aan_right = node->aa_node.aan_right;

		 leaf->aa_node.aan_level = node->aa_node.aan_level;
	 }
	 while(parent!=B_AA_ROOT_NODE(tree)) {
		 if(parent->aa_node.aan_level > B_AA_NODE_LEVEL(parent->aa_node.aan_left)+1) {
			 parent->aa_node.aan_level--;
			 if(baat_split(tree, parent)) {
				 if(baat_split(tree, parent)) {
					 baat_skew(parent->aa_node.aan_parent->aa_node.aan_parent);
					 break;
				 }
			 }
			 parent = parent->aa_node.aan_parent;
		 } else if(parent->aa_node.aan_level <= B_AA_NODE_LEVEL(parent->aa_node.aan_right)+1) {
			 break;
		 } else {
			 baat_skew(parent);
			 if(parent->aa_node.aan_level > parent->aa_node.aan_parent->aa_node.aan_level) {
				 baat_skew(parent);
				 baat_split(tree, parent->aa_node.aan_parent->aa_node.aan_parent);
				 break;
			 }
			 parent = parent->aa_node.aan_parent->aa_node.aan_parent;
		 }
	 }
     return;
}