avltree.cpp

Static Timing Analyzer

#include "datadef.h"

Boolean idAVLTree::Rebalance(idAVLTreeNode *unbal, idAVLTreeNode *unbalp)
{
    Boolean ans;
    idAVLTreeNode *unbalc,*unbalcc;
    if (unbal->bf>1)  /* Left Rotate */
    {   unbalc=unbal->LeftTree;
        if (unbalc->bf==1)  /* Type LL */
        {   unbal->LeftTree=unbalc->RightTree;
            unbalc->RightTree=unbal;
            unbal->bf=unbalc->bf=0;
            ans=TRUE;
        }
        else if (unbalc->bf==0)  /* Type LL (another kind) */
        {   unbal->LeftTree=unbalc->RightTree;
            unbalc->RightTree=unbal;
            unbal->bf=1;
            unbalc->bf=-1;
            ans=FALSE;
        }
        else  /* Type LR */
        {   unbalcc=unbalc->RightTree;
            unbalc->RightTree=unbalcc->LeftTree;
            unbal->LeftTree=unbalcc->RightTree;
            unbalcc->LeftTree=unbalc;
            unbalcc->RightTree=unbal;
            switch (unbalcc->bf)
            {   case 1:   /* Type LRL */
                    unbal->bf=-1;
                    unbalc->bf=0;
                    break;
                case -1:  /* Type LRR */
                    unbalc->bf=1;
                    unbal->bf=0;
                    break;
                case 0:   /* Type LR */
                    unbal->bf=0;
                    unbalc->bf=0;
                    break;
            }
            unbalcc->bf=0;
            unbalc=unbalcc;
            ans=TRUE;
        }
    }
    else if (unbal->bf<-1)  /* Right Rotate */
    {   unbalc=unbal->RightTree;
        if (unbalc->bf==-1)  /* Type RR */
        {   unbal->RightTree=unbalc->LeftTree;
            unbalc->LeftTree=unbal;
            unbal->bf=unbalc->bf=0;
            ans=TRUE;
        }
        else if (unbalc->bf==0)  /* Type RR (another kind) */
        {   unbal->RightTree=unbalc->LeftTree;
            unbalc->LeftTree=unbal;
            unbal->bf=-1;
            unbalc->bf=1;
            ans=FALSE;
        }
        else  /* Type RL */
        {   unbalcc=unbalc->LeftTree;
            unbalc->LeftTree=unbalcc->RightTree;
            unbal->RightTree=unbalcc->LeftTree;
            unbalcc->LeftTree=unbal;
            unbalcc->RightTree=unbalc;
            switch (unbalcc->bf)
            {   case 1:   /* Type RLL */
                    unbalc->bf=-1;
                    unbal->bf=0;
                    break;
                case -1:  /* Type RLR */
                    unbal->bf=1;
                    unbalc->bf=0;
                    break;
                case 0:   /* Type RL */
                    unbal->bf=0;
                    unbalc->bf=0;
                    break;
            }
            unbalcc->bf=0;
            unbalc=unbalcc;
            ans=TRUE;
        }
    }
    if (!unbalp) Root=unbalc;
    else if (unbal==unbalp->LeftTree) unbalp->LeftTree=unbalc;
    else if (unbal==unbalp->RightTree) unbalp->RightTree=unbalc;
    return ans;
}


Boolean idAVLTree::search_delkey(Boolean *result, GateId key,
                                 idAVLTreeNode *curr,idAVLTreeNode *currp)
{
    Boolean ans;
    if (!curr) return FALSE;
    else if (key < curr->elem->id)
    {   if ((search_delkey(result,key,curr->LeftTree,curr))==TRUE)
        {   (curr->bf)--;
            if (curr->bf==0) ans=TRUE;
            else ans=FALSE;
        }
        else ans=FALSE;
    }
    else if (key > curr->elem->id)
    {   if ((search_delkey(result,key,curr->RightTree,curr))==TRUE)
        {   (curr->bf)++;
            if (curr->bf==0) ans=TRUE;
            else ans=FALSE;
        }
        else ans=FALSE;
    }
    else
    {   Gate *moved;
        (*result)=TRUE;
        if (curr->bf<0)
        {   if ((get_rhead(&moved,curr->RightTree,curr,-1))==TRUE)
            {   (curr->bf)++;
                if (curr->bf==0) ans=TRUE;
                else ans=FALSE;
            }
            else ans=FALSE;
            curr->elem=moved;
            return ans;
        }
        else
        {   if (curr->LeftTree)
            {  if ((get_rhead(&moved,curr->LeftTree,curr,1))==TRUE)
                {   (curr->bf)--;
                    if (curr->bf==0) ans=TRUE;
                    else ans=FALSE;
                }
                else ans=FALSE;
                curr->elem=moved;
                return ans;
            }
            else
            {   if (!currp) Root=NULL;
                else if (curr==currp->RightTree) currp->RightTree=NULL;
                else if (curr==currp->LeftTree) currp->LeftTree=NULL;
                delete curr;
                return TRUE;
            }
        }
    }

    if (curr->bf>1 || curr->bf<-1)
    {   if ((Rebalance(curr,currp))==TRUE) ans=TRUE;
        else ans=FALSE;
    }
    return ans;
}


Boolean idAVLTree::get_rhead(Gate **moved, idAVLTreeNode *curr,
                             idAVLTreeNode *curp, int dirc)
{
    if (dirc>0)
    {   if (curr->RightTree)
        {   if ((get_rhead(moved,curr->RightTree,curr,dirc))==TRUE)
            {   (curr->bf)++;
                if (curr->bf>1)
                {   if ((Rebalance(curr,curp))==TRUE) return TRUE;
                    else return FALSE;
                }
                else if (curr->bf==0) return TRUE;
            }
            return FALSE;
        }
        else
        {   *moved=curr->elem;
            if (curr==curp->RightTree) curp->RightTree=curr->LeftTree;
            else curp->LeftTree=curr->LeftTree;
            delete curr;
            return TRUE;
        }
    }
    else
    {   if (curr->LeftTree)
        {   if ((get_rhead(moved,curr->LeftTree,curr,dirc))==TRUE)
            {   (curr->bf)--;
                if (curr->bf<-1)
                {   if ((Rebalance(curr,curp))==TRUE) return TRUE;
                    else return FALSE;
                }
                else if (curr->bf==0) return TRUE;
            }
            return FALSE;
        }
        else
        {   *moved=curr->elem;
            if (curr==curp->LeftTree) curp->LeftTree=curr->RightTree;
            else curp->RightTree=curr->RightTree;
            delete curr;
            return TRUE;
        }
    }
}


void idAVLTree::deltree(idAVLTreeNode *treeroot)
{
    if (treeroot->LeftTree) deltree(treeroot->LeftTree);
    if (treeroot->RightTree) deltree(treeroot->RightTree);
    GateList *curr, *delnode;
    curr = treeroot->elem->fanout;
    while (curr) {
       delnode = curr;
       curr = curr->next;
       delete delnode;
    }
    delete treeroot->elem;
    delete treeroot;
}


void idAVLTree::dumptree(idAVLTreeNode *treeroot,int level)
{
    if (treeroot->LeftTree) dumptree(treeroot->LeftTree,level+1);
    for (int i=0;i<level;i++) printf(" ");
    printf("Gate %d, Type %d, Inputs %d, Fanouts %d (bf=%d)\n",
           treeroot->elem->id,treeroot->elem->type,treeroot->elem->inno,
           treeroot->elem->outno,treeroot->bf);
    GateList *curr = treeroot->elem->fanout;
    while (curr) {
       for (int i=0;i<level;i++) printf(" ");
       printf("--> Gate %d\n",curr->cgate->id);
       curr = curr->next;
    }
    if (treeroot->RightTree) dumptree(treeroot->RightTree,level+1);
}


idAVLTree::idAVLTree(void) { Root=NULL;}


Boolean idAVLTree::IsIn(GateId key)
{
    idAVLTreeNode *tn=Root;
    while (tn)
    {   if (tn->elem->id == key) return TRUE;
        else if (tn->elem->id > key) tn=tn->LeftTree;
        else tn=tn->RightTree;
    }
    return FALSE;
}


Gate *idAVLTree::Find(GateId key)
{
    idAVLTreeNode *tn=Root;
    while (tn)
    {   if (tn->elem->id == key) return tn->elem;
        else if (tn->elem->id > key) tn=tn->LeftTree;
        else tn=tn->RightTree;
    }
    return NULL;
}


Boolean idAVLTree::Insert(Gate *elem)
{
    if (!Root)
    {   Root=new idAVLTreeNode;
        if (Root==NULL) {
            printf("Memory Error in AVLTree!!\n");
            return FALSE;
        }
        Root->elem=elem;
        Root->bf=0;
        Root->LeftTree=Root->RightTree=NULL;
        return TRUE;
    }

    idAVLTreeNode *curr=Root,*currp=NULL,*unbal=Root,*unbalp=NULL;
    while (curr)
    {   if (curr->bf)
        {   unbal=curr;
            unbalp=currp;
        }
        currp=curr;
        if (elem->id < curr->elem->id) curr=curr->LeftTree;
        else if (elem->id > curr->elem->id) curr=curr->RightTree;
        else return FALSE;
    }

    idAVLTreeNode *y=new idAVLTreeNode;
    if (y==NULL) {
        printf("Memory Error in AVLTree!!\n");
        return FALSE;
    }
    y->elem=elem;
    y->bf=0;
    y->LeftTree=y->RightTree=NULL;
    if (elem->id < currp->elem->id) currp->LeftTree=y;
    else currp->RightTree=y;

    if (elem->id < unbal->elem->id)
    {   curr=unbal->LeftTree;
        (unbal->bf)++;
    }
    else
    {   curr=unbal->RightTree;
        (unbal->bf)--;
    }
    while (curr!=y)
    {   if (elem->id < curr->elem->id)
        {   curr->bf=1;
            curr=curr->LeftTree;
        }
        else
        {   curr->bf=-1;
            curr=curr->RightTree;
        }
    }
    if (unbal->bf>1 || unbal->bf<-1) Rebalance(unbal,unbalp);
    return TRUE;
}


Boolean idAVLTree::Delete(GateId key)
{
    Boolean result=FALSE;
    if (Root) search_delkey(&result,key,Root,NULL);
    return result;
}


void idAVLTree::DeleteTree(void)
{
    if (Root) deltree(Root);
    Root=NULL;
}


void idAVLTree::Dump(void)
{
    if (Root) dumptree(Root,0);
}