diff options
Diffstat (limited to 'src/opt/fxu/fxuHeapS.c')
| -rw-r--r-- | src/opt/fxu/fxuHeapS.c | 444 |
1 files changed, 444 insertions, 0 deletions
diff --git a/src/opt/fxu/fxuHeapS.c b/src/opt/fxu/fxuHeapS.c new file mode 100644 index 00000000..eaca8363 --- /dev/null +++ b/src/opt/fxu/fxuHeapS.c @@ -0,0 +1,444 @@ +/**CFile**************************************************************** + + FileName [fxuHeapS.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [The priority queue for variables.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuHeapS.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define FXU_HEAP_SINGLE_WEIGHT(pSingle) ((pSingle)->Weight) +#define FXU_HEAP_SINGLE_CURRENT(p, pSingle) ((p)->pTree[(pSingle)->HNum]) +#define FXU_HEAP_SINGLE_PARENT_EXISTS(p, pSingle) ((pSingle)->HNum > 1) +#define FXU_HEAP_SINGLE_CHILD1_EXISTS(p, pSingle) (((pSingle)->HNum << 1) <= p->nItems) +#define FXU_HEAP_SINGLE_CHILD2_EXISTS(p, pSingle) ((((pSingle)->HNum << 1)+1) <= p->nItems) +#define FXU_HEAP_SINGLE_PARENT(p, pSingle) ((p)->pTree[(pSingle)->HNum >> 1]) +#define FXU_HEAP_SINGLE_CHILD1(p, pSingle) ((p)->pTree[(pSingle)->HNum << 1]) +#define FXU_HEAP_SINGLE_CHILD2(p, pSingle) ((p)->pTree[((pSingle)->HNum << 1)+1]) +#define FXU_HEAP_SINGLE_ASSERT(p, pSingle) assert( (pSingle)->HNum >= 1 && (pSingle)->HNum <= p->nItemsAlloc ) + +static void Fxu_HeapSingleResize( Fxu_HeapSingle * p ); +static void Fxu_HeapSingleSwap( Fxu_Single ** pSingle1, Fxu_Single ** pSingle2 ); +static void Fxu_HeapSingleMoveUp( Fxu_HeapSingle * p, Fxu_Single * pSingle ); +static void Fxu_HeapSingleMoveDn( Fxu_HeapSingle * p, Fxu_Single * pSingle ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_HeapSingle * Fxu_HeapSingleStart() +{ + Fxu_HeapSingle * p; + p = ALLOC( Fxu_HeapSingle, 1 ); + memset( p, 0, sizeof(Fxu_HeapSingle) ); + p->nItems = 0; + p->nItemsAlloc = 2000; + p->pTree = ALLOC( Fxu_Single *, p->nItemsAlloc + 10 ); + p->pTree[0] = NULL; + return p; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleResize( Fxu_HeapSingle * p ) +{ + p->nItemsAlloc *= 2; + p->pTree = REALLOC( Fxu_Single *, p->pTree, p->nItemsAlloc + 10 ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleStop( Fxu_HeapSingle * p ) +{ + int i; + i = 0; + free( p->pTree ); + i = 1; + free( p ); +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSinglePrint( FILE * pFile, Fxu_HeapSingle * p ) +{ + Fxu_Single * pSingle; + int Counter = 1; + int Degree = 1; + + Fxu_HeapSingleCheck( p ); + fprintf( pFile, "The contents of the heap:\n" ); + fprintf( pFile, "Level %d: ", Degree ); + Fxu_HeapSingleForEachItem( p, pSingle ) + { + assert( Counter == p->pTree[Counter]->HNum ); + fprintf( pFile, "%2d=%3d ", Counter, FXU_HEAP_SINGLE_WEIGHT(p->pTree[Counter]) ); + if ( ++Counter == (1 << Degree) ) + { + fprintf( pFile, "\n" ); + Degree++; + fprintf( pFile, "Level %d: ", Degree ); + } + } + fprintf( pFile, "\n" ); + fprintf( pFile, "End of the heap printout.\n" ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleCheck( Fxu_HeapSingle * p ) +{ + Fxu_Single * pSingle; + Fxu_HeapSingleForEachItem( p, pSingle ) + { + assert( pSingle->HNum == p->i ); + Fxu_HeapSingleCheckOne( p, pSingle ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleCheckOne( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + int Weight1, Weight2; + if ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,pSingle) ) + { + Weight1 = FXU_HEAP_SINGLE_WEIGHT(pSingle); + Weight2 = FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD1(p,pSingle) ); + assert( Weight1 >= Weight2 ); + } + if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,pSingle) ) + { + Weight1 = FXU_HEAP_SINGLE_WEIGHT(pSingle); + Weight2 = FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD2(p,pSingle) ); + assert( Weight1 >= Weight2 ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleInsert( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + if ( p->nItems == p->nItemsAlloc ) + Fxu_HeapSingleResize( p ); + // put the last entry to the last place and move up + p->pTree[++p->nItems] = pSingle; + pSingle->HNum = p->nItems; + // move the last entry up if necessary + Fxu_HeapSingleMoveUp( p, pSingle ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleUpdate( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + FXU_HEAP_SINGLE_ASSERT(p,pSingle); + if ( FXU_HEAP_SINGLE_PARENT_EXISTS(p,pSingle) && + FXU_HEAP_SINGLE_WEIGHT(pSingle) > FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_PARENT(p,pSingle) ) ) + Fxu_HeapSingleMoveUp( p, pSingle ); + else if ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,pSingle) && + FXU_HEAP_SINGLE_WEIGHT(pSingle) < FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD1(p,pSingle) ) ) + Fxu_HeapSingleMoveDn( p, pSingle ); + else if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,pSingle) && + FXU_HEAP_SINGLE_WEIGHT(pSingle) < FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD2(p,pSingle) ) ) + Fxu_HeapSingleMoveDn( p, pSingle ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleDelete( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + int Place = pSingle->HNum; + FXU_HEAP_SINGLE_ASSERT(p,pSingle); + // put the last entry to the deleted place + // decrement the number of entries + p->pTree[Place] = p->pTree[p->nItems--]; + p->pTree[Place]->HNum = Place; + // move the top entry down if necessary + Fxu_HeapSingleUpdate( p, p->pTree[Place] ); + pSingle->HNum = 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Single * Fxu_HeapSingleReadMax( Fxu_HeapSingle * p ) +{ + if ( p->nItems == 0 ) + return NULL; + return p->pTree[1]; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Single * Fxu_HeapSingleGetMax( Fxu_HeapSingle * p ) +{ + Fxu_Single * pSingle; + if ( p->nItems == 0 ) + return NULL; + // prepare the return value + pSingle = p->pTree[1]; + pSingle->HNum = 0; + // put the last entry on top + // decrement the number of entries + p->pTree[1] = p->pTree[p->nItems--]; + p->pTree[1]->HNum = 1; + // move the top entry down if necessary + Fxu_HeapSingleMoveDn( p, p->pTree[1] ); + return pSingle; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_HeapSingleReadMaxWeight( Fxu_HeapSingle * p ) +{ + if ( p->nItems == 0 ) + return -1; + return FXU_HEAP_SINGLE_WEIGHT(p->pTree[1]); +} + + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleSwap( Fxu_Single ** pSingle1, Fxu_Single ** pSingle2 ) +{ + Fxu_Single * pSingle; + int Temp; + pSingle = *pSingle1; + *pSingle1 = *pSingle2; + *pSingle2 = pSingle; + Temp = (*pSingle1)->HNum; + (*pSingle1)->HNum = (*pSingle2)->HNum; + (*pSingle2)->HNum = Temp; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleMoveUp( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + Fxu_Single ** ppSingle, ** ppPar; + ppSingle = &FXU_HEAP_SINGLE_CURRENT(p, pSingle); + while ( FXU_HEAP_SINGLE_PARENT_EXISTS(p,*ppSingle) ) + { + ppPar = &FXU_HEAP_SINGLE_PARENT(p,*ppSingle); + if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) > FXU_HEAP_SINGLE_WEIGHT(*ppPar) ) + { + Fxu_HeapSingleSwap( ppSingle, ppPar ); + ppSingle = ppPar; + } + else + break; + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleMoveDn( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + Fxu_Single ** ppChild1, ** ppChild2, ** ppSingle; + ppSingle = &FXU_HEAP_SINGLE_CURRENT(p, pSingle); + while ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,*ppSingle) ) + { // if Child1 does not exist, Child2 also does not exists + + // get the children + ppChild1 = &FXU_HEAP_SINGLE_CHILD1(p,*ppSingle); + if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,*ppSingle) ) + { + ppChild2 = &FXU_HEAP_SINGLE_CHILD2(p,*ppSingle); + + // consider two cases + if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild1) && + FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild2) ) + { // Var is larger than both, skip + break; + } + else + { // Var is smaller than one of them, then swap it with larger + if ( FXU_HEAP_SINGLE_WEIGHT(*ppChild1) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild2) ) + { + Fxu_HeapSingleSwap( ppSingle, ppChild1 ); + // update the pointer + ppSingle = ppChild1; + } + else + { + Fxu_HeapSingleSwap( ppSingle, ppChild2 ); + // update the pointer + ppSingle = ppChild2; + } + } + } + else // Child2 does not exist + { + // consider two cases + if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild1) ) + { // Var is larger than Child1, skip + break; + } + else + { // Var is smaller than Child1, then swap them + Fxu_HeapSingleSwap( ppSingle, ppChild1 ); + // update the pointer + ppSingle = ppChild1; + } + } + } +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// |