| /**CFile**************************************************************** |
| |
| FileName [fxuHeapD.c] |
| |
| PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] |
| |
| Synopsis [The priority queue for double cube divisors.] |
| |
| Author [MVSIS Group] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - February 1, 2003.] |
| |
| Revision [$Id: fxuHeapD.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "fxuInt.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| #define FXU_HEAP_DOUBLE_WEIGHT(pDiv) ((pDiv)->Weight) |
| #define FXU_HEAP_DOUBLE_CURRENT(p, pDiv) ((p)->pTree[(pDiv)->HNum]) |
| #define FXU_HEAP_DOUBLE_PARENT_EXISTS(p, pDiv) ((pDiv)->HNum > 1) |
| #define FXU_HEAP_DOUBLE_CHILD1_EXISTS(p, pDiv) (((pDiv)->HNum << 1) <= p->nItems) |
| #define FXU_HEAP_DOUBLE_CHILD2_EXISTS(p, pDiv) ((((pDiv)->HNum << 1)+1) <= p->nItems) |
| #define FXU_HEAP_DOUBLE_PARENT(p, pDiv) ((p)->pTree[(pDiv)->HNum >> 1]) |
| #define FXU_HEAP_DOUBLE_CHILD1(p, pDiv) ((p)->pTree[(pDiv)->HNum << 1]) |
| #define FXU_HEAP_DOUBLE_CHILD2(p, pDiv) ((p)->pTree[((pDiv)->HNum << 1)+1]) |
| #define FXU_HEAP_DOUBLE_ASSERT(p, pDiv) assert( (pDiv)->HNum >= 1 && (pDiv)->HNum <= p->nItemsAlloc ) |
| |
| static void Fxu_HeapDoubleResize( Fxu_HeapDouble * p ); |
| static void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 ); |
| static void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv ); |
| static void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv ); |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Fxu_HeapDouble * Fxu_HeapDoubleStart() |
| { |
| Fxu_HeapDouble * p; |
| p = ABC_ALLOC( Fxu_HeapDouble, 1 ); |
| memset( p, 0, sizeof(Fxu_HeapDouble) ); |
| p->nItems = 0; |
| p->nItemsAlloc = 10000; |
| p->pTree = ABC_ALLOC( Fxu_Double *, p->nItemsAlloc + 1 ); |
| p->pTree[0] = NULL; |
| return p; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoubleResize( Fxu_HeapDouble * p ) |
| { |
| p->nItemsAlloc *= 2; |
| p->pTree = ABC_REALLOC( Fxu_Double *, p->pTree, p->nItemsAlloc + 1 ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoubleStop( Fxu_HeapDouble * p ) |
| { |
| ABC_FREE( p->pTree ); |
| ABC_FREE( p ); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoublePrint( FILE * pFile, Fxu_HeapDouble * p ) |
| { |
| Fxu_Double * pDiv; |
| int Counter = 1; |
| int Degree = 1; |
| |
| Fxu_HeapDoubleCheck( p ); |
| fprintf( pFile, "The contents of the heap:\n" ); |
| fprintf( pFile, "Level %d: ", Degree ); |
| Fxu_HeapDoubleForEachItem( p, pDiv ) |
| { |
| assert( Counter == p->pTree[Counter]->HNum ); |
| fprintf( pFile, "%2d=%3d ", Counter, FXU_HEAP_DOUBLE_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_HeapDoubleCheck( Fxu_HeapDouble * p ) |
| { |
| Fxu_Double * pDiv; |
| Fxu_HeapDoubleForEachItem( p, pDiv ) |
| { |
| assert( pDiv->HNum == p->i ); |
| Fxu_HeapDoubleCheckOne( p, pDiv ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoubleCheckOne( Fxu_HeapDouble * p, Fxu_Double * pDiv ) |
| { |
| int Weight1, Weight2; |
| if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) ) |
| { |
| Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv); |
| Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) ); |
| assert( Weight1 >= Weight2 ); |
| } |
| if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) ) |
| { |
| Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv); |
| Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) ); |
| assert( Weight1 >= Weight2 ); |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoubleInsert( Fxu_HeapDouble * p, Fxu_Double * pDiv ) |
| { |
| if ( p->nItems == p->nItemsAlloc ) |
| Fxu_HeapDoubleResize( p ); |
| // put the last entry to the last place and move up |
| p->pTree[++p->nItems] = pDiv; |
| pDiv->HNum = p->nItems; |
| // move the last entry up if necessary |
| Fxu_HeapDoubleMoveUp( p, pDiv ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoubleUpdate( Fxu_HeapDouble * p, Fxu_Double * pDiv ) |
| { |
| //printf( "Updating divisor %d.\n", pDiv->Num ); |
| |
| FXU_HEAP_DOUBLE_ASSERT(p,pDiv); |
| if ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,pDiv) && |
| FXU_HEAP_DOUBLE_WEIGHT(pDiv) > FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_PARENT(p,pDiv) ) ) |
| Fxu_HeapDoubleMoveUp( p, pDiv ); |
| else if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) && |
| FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) ) ) |
| Fxu_HeapDoubleMoveDn( p, pDiv ); |
| else if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) && |
| FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) ) ) |
| Fxu_HeapDoubleMoveDn( p, pDiv ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoubleDelete( Fxu_HeapDouble * p, Fxu_Double * pDiv ) |
| { |
| FXU_HEAP_DOUBLE_ASSERT(p,pDiv); |
| // put the last entry to the deleted place |
| // decrement the number of entries |
| p->pTree[pDiv->HNum] = p->pTree[p->nItems--]; |
| p->pTree[pDiv->HNum]->HNum = pDiv->HNum; |
| // move the top entry down if necessary |
| Fxu_HeapDoubleUpdate( p, p->pTree[pDiv->HNum] ); |
| pDiv->HNum = 0; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Fxu_Double * Fxu_HeapDoubleReadMax( Fxu_HeapDouble * p ) |
| { |
| if ( p->nItems == 0 ) |
| return NULL; |
| return p->pTree[1]; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Fxu_Double * Fxu_HeapDoubleGetMax( Fxu_HeapDouble * p ) |
| { |
| Fxu_Double * pDiv; |
| if ( p->nItems == 0 ) |
| return NULL; |
| // prepare the return value |
| pDiv = p->pTree[1]; |
| pDiv->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_HeapDoubleMoveDn( p, p->pTree[1] ); |
| return pDiv; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Fxu_HeapDoubleReadMaxWeight( Fxu_HeapDouble * p ) |
| { |
| if ( p->nItems == 0 ) |
| return -1; |
| else |
| return FXU_HEAP_DOUBLE_WEIGHT(p->pTree[1]); |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 ) |
| { |
| Fxu_Double * pDiv; |
| int Temp; |
| pDiv = *pDiv1; |
| *pDiv1 = *pDiv2; |
| *pDiv2 = pDiv; |
| Temp = (*pDiv1)->HNum; |
| (*pDiv1)->HNum = (*pDiv2)->HNum; |
| (*pDiv2)->HNum = Temp; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv ) |
| { |
| Fxu_Double ** ppDiv, ** ppPar; |
| ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv); |
| while ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,*ppDiv) ) |
| { |
| ppPar = &FXU_HEAP_DOUBLE_PARENT(p,*ppDiv); |
| if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) > FXU_HEAP_DOUBLE_WEIGHT(*ppPar) ) |
| { |
| Fxu_HeapDoubleSwap( ppDiv, ppPar ); |
| ppDiv = ppPar; |
| } |
| else |
| break; |
| } |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv ) |
| { |
| Fxu_Double ** ppChild1, ** ppChild2, ** ppDiv; |
| ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv); |
| while ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,*ppDiv) ) |
| { // if Child1 does not exist, Child2 also does not exists |
| |
| // get the children |
| ppChild1 = &FXU_HEAP_DOUBLE_CHILD1(p,*ppDiv); |
| if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,*ppDiv) ) |
| { |
| ppChild2 = &FXU_HEAP_DOUBLE_CHILD2(p,*ppDiv); |
| |
| // consider two cases |
| if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) && |
| FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) ) |
| { // Div is larger than both, skip |
| break; |
| } |
| else |
| { // Div is smaller than one of them, then swap it with larger |
| if ( FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) ) |
| { |
| Fxu_HeapDoubleSwap( ppDiv, ppChild1 ); |
| // update the pointer |
| ppDiv = ppChild1; |
| } |
| else |
| { |
| Fxu_HeapDoubleSwap( ppDiv, ppChild2 ); |
| // update the pointer |
| ppDiv = ppChild2; |
| } |
| } |
| } |
| else // Child2 does not exist |
| { |
| // consider two cases |
| if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) ) |
| { // Div is larger than Child1, skip |
| break; |
| } |
| else |
| { // Div is smaller than Child1, then swap them |
| Fxu_HeapDoubleSwap( ppDiv, ppChild1 ); |
| // update the pointer |
| ppDiv = ppChild1; |
| } |
| } |
| } |
| } |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
