/**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