diff options
Diffstat (limited to 'src/opt/fxu/fxuHeapD.c')
| -rw-r--r-- | src/opt/fxu/fxuHeapD.c | 445 |
1 files changed, 0 insertions, 445 deletions
diff --git a/src/opt/fxu/fxuHeapD.c b/src/opt/fxu/fxuHeapD.c deleted file mode 100644 index c81ad818..00000000 --- a/src/opt/fxu/fxuHeapD.c +++ /dev/null @@ -1,445 +0,0 @@ -/**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" - -//////////////////////////////////////////////////////////////////////// -/// 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 = ALLOC( Fxu_HeapDouble, 1 ); - memset( p, 0, sizeof(Fxu_HeapDouble) ); - p->nItems = 0; - p->nItemsAlloc = 10000; - p->pTree = 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 = REALLOC( Fxu_Double *, p->pTree, p->nItemsAlloc + 1 ); -} - -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -void Fxu_HeapDoubleStop( Fxu_HeapDouble * p ) -{ - free( p->pTree ); - 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 /// -//////////////////////////////////////////////////////////////////////// - - |