/**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" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// 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 = ABC_ALLOC( Fxu_HeapSingle, 1 ); memset( p, 0, sizeof(Fxu_HeapSingle) ); p->nItems = 0; p->nItemsAlloc = 2000; p->pTree = ABC_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 = ABC_REALLOC( Fxu_Single *, p->pTree, p->nItemsAlloc + 10 ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fxu_HeapSingleStop( Fxu_HeapSingle * p ) { int i; i = 0; ABC_FREE( p->pTree ); i = 1; ABC_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 /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END