diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2005-08-06 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2005-08-06 08:01:00 -0700 |
commit | d0e834d1a615f8e0e9d04c2ac97811f63562bd0b (patch) | |
tree | 0973181bfb5ee7d556cc95bd640de16fee771e89 /src/opt/fxu/fxuHeapD.c | |
parent | 888e5bed5d7f56a5d86d91a6e8e88f3e5a3454dc (diff) | |
download | abc-d0e834d1a615f8e0e9d04c2ac97811f63562bd0b.tar.gz abc-d0e834d1a615f8e0e9d04c2ac97811f63562bd0b.tar.bz2 abc-d0e834d1a615f8e0e9d04c2ac97811f63562bd0b.zip |
Version abc50806
Diffstat (limited to 'src/opt/fxu/fxuHeapD.c')
-rw-r--r-- | src/opt/fxu/fxuHeapD.c | 445 |
1 files changed, 445 insertions, 0 deletions
diff --git a/src/opt/fxu/fxuHeapD.c b/src/opt/fxu/fxuHeapD.c new file mode 100644 index 00000000..7c123249 --- /dev/null +++ b/src/opt/fxu/fxuHeapD.c @@ -0,0 +1,445 @@ +/**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 DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**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 /// +//////////////////////////////////////////////////////////////////////// + + |