// ========== Copyright Header Begin ==========================================
// 
// OpenSPARC T2 Processor File: XactorBinTree.vr
// Copyright (C) 1995-2007 Sun Microsystems, Inc. All Rights Reserved
// 4150 Network Circle, Santa Clara, California 95054, U.S.A.
//
// * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 
//
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; version 2 of the License.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
// 
// For the avoidance of doubt, and except that if any non-GPL license 
// choice is available it will apply instead, Sun elects to use only 
// the General Public License version 2 (GPLv2) at this time for any 
// software where a choice of GPL license versions is made 
// available with the language indicating that GPLv2 or any later version 
// may be used, or where a choice of which version of the GPL is applied is 
// otherwise unspecified. 
//
// Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 
// CA 95054 USA or visit www.sun.com if you need additional information or 
// have any questions. 
// 
// ========== Copyright Header End ============================================
#include <vera_defines.vrh>
#include "XactorUtilities.vrh"
#include "XactorBasePacket.vrh"
#include "XactorBaseExpectDataStruct.vrh"
#include "XactorDefines.vri"
#include "XactorComponentsDefines.vri"

typedef class TreeNode;

// This class declares and implements the node used by the binary tree data structure.
class TreeNode {

  event RemoveEvents[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS]; // Removed is an event flag that will be 
                                                      // triggered when the node is removed
  XactorBasePacket Item; // Xactor Packet
  TreeNode Left; // Pointer to the left node
  TreeNode Right; // Pointer to the right node
  TreeNode Parent; // Pointer to the parent node

  task new (XactorBasePacket i,
	    var event e[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS]
	    ) {

    integer EventCnt;
    
    for(EventCnt = 0; EventCnt <= XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS - 1; EventCnt++) {
      RemoveEvents[EventCnt] = e[EventCnt];
    }

    Item = i;
    Left = null;
    Right = null;
    Parent = null;
  }
}

// This is the class that declares and implements the binary tree 
// data structure.
class XactorBinTree extends XactorBaseExpectDataStruct {

  // Head node of the binary tree
  protected TreeNode Head;

  task new ();

  virtual protected task AssignEvent(var event Dest[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS], 
				     var event Src[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS]
				     );

  // Local method. Will search Key within the binary tree. 
  virtual protected function TreeNode WCTreeSearch(TreeNode x, 
						   XactorBasePacket Key
						   );

  // Local method. Will search Key within the binary tree. 
  virtual protected function TreeNode TreeSearch(TreeNode x, 
						 XactorBasePacket Key
						 );

  // Local method. Will search Key within the binary tree. 
  virtual protected function TreeNode RefTreeSearch(TreeNode x, 
						    XactorBasePacket Key
						    );

  // Local method. Will return the left most node of the tree (the one
  // with the minimum value)
  virtual protected function TreeNode TreeMin(TreeNode x);

  // Local method. Returns the successor to node x
  virtual protected function TreeNode TreeSuccessor(TreeNode x);

  // Public method. Inserts a new node with the specified values.
  virtual task Insert (XactorBasePacket Item,
		       var event e[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS]
		       );

  virtual protected task DeleteNode (var TreeNode z);

  // Checks if there are duplicated packets after a node is deleted. 
  // No Wildcards
  virtual protected task CheckDuplicatedExpects (XactorBasePacket Key,
						 TreeNode NodePtr
						 );

  // Public method. Deletes a node with the specified values and returns 
  // Success = 1 if the node was found and deleted and Success = 0 otherwise.
  virtual task Delete (XactorBasePacket Key,
		       var bit Success
		       );

  // Public method. Deletes a node with the specified values and returns 
  // Success = 1 if the node was found and deleted and Success = 0 otherwise.
  virtual task RefDelete (XactorBasePacket Key,
			  var bit Success
			  );

  // Checks for duplicated expects after a node is deleted
  // Use of wildcards
  virtual protected task CheckWCDuplicatedExpects (XactorBasePacket Key,
						   TreeNode NodePtr
						   );
 
  // Using Wildcards, deletes first node that match Key
  virtual task WildCardDelete1 (XactorBasePacket Key,
				var bit Success
				);

  // Local method. Will do and inorder traversal of the binary tree
  // and will return the number of nodes through Counter
  virtual protected task InorderCount(TreeNode Node,
				      var integer Counter
				      );
 
  // Public method. Will return the number of nodes in the binary tree.
  virtual function integer CountNodes();
  
  // Local method. will do an inorder walk of the binary tree and will
  // print every node. Each "compressed" expected value is decoded by
  // a packet object. Once decoded, each field will be stored within the
  // same packet and printed.
  virtual protected task InorderPrint(TreeNode Node);

  // Public method. Calls InorderPrint to print the nodes within the
  // binary tree.
  virtual task PrintNodes();

  // Public method. Returns 1 if Item is within the binary tree and
  // 0 otherwise. Accepts "wildcards"
  virtual function bit InStructure(XactorBasePacket Item);

  // Public method. Returns 1 if the binary tree is empty and 0 otherwise.
  virtual function bit Empty();

  // Local method. Inorder walk of the binary tree. It triggers the event
  // of every node.
  virtual protected task InorderReset(TreeNode Node);

  // Public method. Calls InorderReset and after that, it deletes the complete
  // binary tree.
  virtual task Reset();

}

  ////////////////
 // Definitions
////////////////

task XactorBinTree::new () {
  Head = null;
}

task XactorBinTree::AssignEvent(var event Dest[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS], 
				var event Src[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS]
				) {
  integer EventCnt;

  for(EventCnt = 0; EventCnt <= XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS - 1; EventCnt++) {
    Dest[EventCnt] = Src[EventCnt];
  }
}

// Local method. Will search Key within the binary tree. 
function TreeNode XactorBinTree::WCTreeSearch(TreeNode x, 
					      XactorBasePacket Key
					      ) {
  if((x == null) || (x.Item.PktCompare("=?=", Key)))
    WCTreeSearch = x;
  else {
    if(x.Item.PktCompare(">", Key))
      WCTreeSearch = WCTreeSearch(x.Left, Key);
    else
      WCTreeSearch = WCTreeSearch(x.Right, Key);
  }
}

// Local method. Will search Key within the binary tree. 
function TreeNode XactorBinTree::TreeSearch(TreeNode x, 
					    XactorBasePacket Key
					    ) {
  if((x == null) || (x.Item.PktCompare("===", Key)))
    TreeSearch = x;
  else {
    if(x.Item.PktCompare(">", Key))
      TreeSearch = TreeSearch(x.Left, Key);
    else
      TreeSearch = TreeSearch(x.Right, Key);
  }
}

// Local method. Will search Key within the binary tree. 
function TreeNode XactorBinTree::RefTreeSearch(TreeNode x, 
					       XactorBasePacket Key
					       ) {
  if((x == null) || (x.Item === Key))
    RefTreeSearch = x;
  else {
    if(x.Item.PktCompare(">", Key))
      RefTreeSearch = RefTreeSearch(x.Left, Key);
    else
      RefTreeSearch = RefTreeSearch(x.Right, Key);
  }
}

// Local method. Will return the left most node of the tree (the one
// with the minimum value)
function TreeNode XactorBinTree::TreeMin(TreeNode x) {
  while(x.Left != null)
    x = x.Left;
  TreeMin = x;
}

// Local method. Returns the successor to node x
function TreeNode XactorBinTree::TreeSuccessor(TreeNode x) {
  TreeNode y;
  
  if(x.Right != null)
    TreeSuccessor = TreeMin(x.Right);
  else {
    y = x.Parent;
    while((y != null) && (x == y.Right)) {
      x = y;
      y = y.Parent;
    }
    TreeSuccessor = y;
  }
}

// Public method. Inserts a new node with the specified values.
task XactorBinTree::Insert (XactorBasePacket Item,
			    var event e[XACT_EXPECT_DATA_STRUCT_REMOVE_EVENTS]
			    ) {
  TreeNode x;
  TreeNode y;
  TreeNode z;
  
  z = new(Item, e);    
  y = null;
  x = Head;
  
  if(Head != null) 
    while(x != null) {
      y = x;
      if((x.Item.PktCompare("<", z.Item)) || (x.Item.PktCompare("=?=", z.Item))) {
	if(x.Item.PktCompare("=?=", z.Item)) {
	  x.Item.PktDisplay(RTYP_XACTOR_FMWORK_DUP_EXPECT_ERR, "Posting a duplicated Expect");
	}
	x = x.Right;
      }
      else {
	x = x.Left;
      }
    }
  
  z.Parent = y;
  if(y == null)
    Head = z;
  else {
    if((y.Item.PktCompare("<", z.Item)) || (y.Item.PktCompare("=?=", z.Item)))
      y.Right = z;
    else
      y.Left = z;
  }
}

task XactorBinTree::DeleteNode (var TreeNode z) {
  
  TreeNode y;
  TreeNode x;
  
  if((z.Left == null) || (z.Right == null))
    y = z;
  else
    y = TreeSuccessor(z);
  
  if(y.Left != null)
    x = y.Left;
  else
    x = y.Right;
  
  if(x != null)
    x.Parent = y.Parent;
  
  if(y.Parent == null)
    Head = x;
  else {
    if(y == y.Parent.Left)
      y.Parent.Left = x;
    else
      y.Parent.Right = x;
  }
  if(y != z) {
    AssignEvent(z.RemoveEvents, y.RemoveEvents);
    z.Item = y.Item;
  }
}

// Checks if there are duplicated packets after a node is deleted. 
// No Wildcards
task XactorBinTree::CheckDuplicatedExpects (XactorBasePacket Key,
					    TreeNode NodePtr
					    ) {
  TreeNode z;
  
  z = TreeSearch(NodePtr, Key);
  
  if(z !== null) {
    z.Item.PktDisplay(RTYP_XACTOR_FMWORK_SAMPLED_DUP_XACTION_ERR, "Sampled Transaction satisfies duplicated Expect");
    if(z.Right != null) {
      CheckDuplicatedExpects (Key,
			      z.Right
			      );				
    }
  }
}

// Public method. Deletes a node with the specified values and returns 
// Success = 1 if the node was found and deleted and Success = 0 otherwise.
task XactorBinTree::Delete (XactorBasePacket Key,
			    var bit Success
			    ) {
  TreeNode z;
  
  z = TreeSearch(Head, Key);
  
  if(z !== null) {
    Key.SetID(z.Item.GetID());
    if(z.Right != null)
      CheckDuplicatedExpects(Key,
			     z.Right
			     );
    trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_EVENT]); // Remove event
    trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_BY_XACTOR_EVENT]); // Removed by xactor

    Success = 1'b1;
    DeleteNode(z);
  }
  else {
    Success = 1'b0;
  }
}

// Public method. Deletes a node with the specified values and returns 
// Success = 1 if the node was found and deleted and Success = 0 otherwise.
task XactorBinTree::RefDelete (XactorBasePacket Key,
			       var bit Success
			       ) {
  TreeNode z;
  
  z = RefTreeSearch(Head, Key);
  
  if(z !== null) {
    Key.SetID(z.Item.GetID());

    trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_EVENT]); // Remove event
    trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_BY_USER_EVENT]); // Removed by user

    Success = 1'b1;    
    DeleteNode(z);
  }
  else {
    Success = 1'b0;
  }
}


// Checks for duplicated expects after a node is deleted
// Use of wildcards
task XactorBinTree::CheckWCDuplicatedExpects (XactorBasePacket Key,
					      TreeNode NodePtr
					      ) {
  TreeNode z;
  
  z = WCTreeSearch(NodePtr, Key);
  
  if(z !== null) {
    z.Item.PktDisplay(RTYP_XACTOR_FMWORK_SAMPLED_DUP_XACTION_ERR, "Sampled Transaction satisfies duplicated Expect");
    if(z.Right !== null) {
      CheckWCDuplicatedExpects (Key,
				z.Right
				);				
    }
  }
}

// Using Wildcards, deletes first node that match Key
task XactorBinTree::WildCardDelete1 (XactorBasePacket Key,
				     var bit Success
				     ) {
  TreeNode z;
  
  z = WCTreeSearch(Head, Key);
  
  if(z != null) {
    Key.SetID(z.Item.GetID());
    z.Item.PktCopy(Key); // Copy contents of sampled packet to expected packet
    if(z.Right != null)
      CheckWCDuplicatedExpects(Key, z.Right);

    trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_EVENT]); // Remove event
    trigger(ON, z.RemoveEvents[XACT_COMP_EXPECT_REMOVED_BY_XACTOR_EVENT]); // Removed by xactor

    Success = 1'b1;    
    DeleteNode(z);
  }
  else
    Success = 1'b0;
}

// Local method. Will do and inorder traversal of the binary tree
// and will return the number of nodes through Counter
task XactorBinTree::InorderCount(TreeNode Node,
				 var integer Counter
				 ) {
  if(Node != null) {
    InorderCount(Node.Left, Counter);
    Counter++;
    InorderCount(Node.Right, Counter);
  }
}

// Public method. Will return the number of nodes in the binary tree.
function integer XactorBinTree::CountNodes() {
  integer Counter = 0;
  
  if(Head != null)
    InorderCount(Head, Counter);        
  
  CountNodes = Counter;
}

// Local method. will do an inorder walk of the binary tree and will
// print every node. Each "compressed" expected value is decoded by
// a packet object. Once decoded, each field will be stored within the
// same packet and printed.
task XactorBinTree::InorderPrint(TreeNode Node
				 ) {
  if(Node != null) {
    InorderPrint(Node.Left);
    Node.Item.PktDisplay(RTYP_INFO, "Dump Expect List");
    InorderPrint(Node.Right);
  }    
}

// Public method. Calls InorderPrint to print the nodes within the
// binary tree.
task XactorBinTree::PrintNodes() {
  if(Head != null)       
    InorderPrint(Head);
}  

// Public method. Returns 1 if Item is within the binary tree and
// 0 otherwise. Accepts "wildcards"
function bit XactorBinTree::InStructure (XactorBasePacket Item
					 ) {
  TreeNode x;
  
  x = TreeSearch(Head, Item);
  
  if(x != null)
    InStructure = 1'b1;
  else
    InStructure = 1'b0;
}

// Public method. Returns 1 if the binary tree is empty and 0 otherwise.
function bit XactorBinTree::Empty() {
  if (Head == null)
    Empty = 1'b1;
  else
    Empty = 1'b0;
}

// Local method. Inorder walk of the binary tree. It triggers the event
// of every node.
task XactorBinTree::InorderReset(TreeNode Node
				 ) {
  if(Node != null) {
    InorderReset(Node.Left);
    trigger(ON, Node.RemoveEvents[XACT_COMP_EXPECT_REMOVED_EVENT]); // Trigger remove event
    trigger(ON, Node.RemoveEvents[XACT_COMP_EXPECT_REMOVED_BY_USER_EVENT]); // Trigger removed
                                                                            // by user event
    InorderReset(Node.Right);
  }    
}  

// Public method. Calls InorderReset and after that, it deletes the complete
// binary tree.
task XactorBinTree::Reset() {
  if(Head != null)
    InorderReset(Head);
  
  Head = null;
}