src/opt/fxu/fxuHeapD.c File Reference

#include "fxuInt.h"
Include dependency graph for fxuHeapD.c:

Go to the source code of this file.

Defines

#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 )

Functions

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)
Fxu_HeapDouble * Fxu_HeapDoubleStart ()
void Fxu_HeapDoubleStop (Fxu_HeapDouble *p)
void Fxu_HeapDoublePrint (FILE *pFile, Fxu_HeapDouble *p)
void Fxu_HeapDoubleCheck (Fxu_HeapDouble *p)
void Fxu_HeapDoubleCheckOne (Fxu_HeapDouble *p, Fxu_Double *pDiv)
void Fxu_HeapDoubleInsert (Fxu_HeapDouble *p, Fxu_Double *pDiv)
void Fxu_HeapDoubleUpdate (Fxu_HeapDouble *p, Fxu_Double *pDiv)
void Fxu_HeapDoubleDelete (Fxu_HeapDouble *p, Fxu_Double *pDiv)
Fxu_Double * Fxu_HeapDoubleReadMax (Fxu_HeapDouble *p)
Fxu_Double * Fxu_HeapDoubleGetMax (Fxu_HeapDouble *p)
int Fxu_HeapDoubleReadMaxWeight (Fxu_HeapDouble *p)

Define Documentation

#define FXU_HEAP_DOUBLE_ASSERT ( p,
pDiv   )     assert( (pDiv)->HNum >= 1 && (pDiv)->HNum <= p->nItemsAlloc )

Definition at line 33 of file fxuHeapD.c.

#define FXU_HEAP_DOUBLE_CHILD1 ( p,
pDiv   )     ((p)->pTree[(pDiv)->HNum << 1])

Definition at line 31 of file fxuHeapD.c.

#define FXU_HEAP_DOUBLE_CHILD1_EXISTS ( p,
pDiv   )     (((pDiv)->HNum << 1) <= p->nItems)

Definition at line 28 of file fxuHeapD.c.

#define FXU_HEAP_DOUBLE_CHILD2 ( p,
pDiv   )     ((p)->pTree[((pDiv)->HNum << 1)+1])

Definition at line 32 of file fxuHeapD.c.

#define FXU_HEAP_DOUBLE_CHILD2_EXISTS ( p,
pDiv   )     ((((pDiv)->HNum << 1)+1) <= p->nItems)

Definition at line 29 of file fxuHeapD.c.

#define FXU_HEAP_DOUBLE_CURRENT ( p,
pDiv   )     ((p)->pTree[(pDiv)->HNum])

Definition at line 26 of file fxuHeapD.c.

#define FXU_HEAP_DOUBLE_PARENT ( p,
pDiv   )     ((p)->pTree[(pDiv)->HNum >> 1])

Definition at line 30 of file fxuHeapD.c.

#define FXU_HEAP_DOUBLE_PARENT_EXISTS ( p,
pDiv   )     ((pDiv)->HNum > 1)

Definition at line 27 of file fxuHeapD.c.

#define FXU_HEAP_DOUBLE_WEIGHT ( pDiv   )     ((pDiv)->Weight)

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

] DECLARATIONS ///

Definition at line 25 of file fxuHeapD.c.

Function Documentation

void Fxu_HeapDoubleCheck ( Fxu_HeapDouble *  p  ) 

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 149 of file fxuHeapD.c.

00150 {
00151         Fxu_Double * pDiv;
00152         Fxu_HeapDoubleForEachItem( p, pDiv )
00153         {
00154                 assert( pDiv->HNum == p->i );
00155         Fxu_HeapDoubleCheckOne( p, pDiv );
00156         }
00157 }

void Fxu_HeapDoubleCheckOne ( Fxu_HeapDouble *  p,
Fxu_Double *  pDiv 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 170 of file fxuHeapD.c.

00171 {
00172     int Weight1, Weight2;
00173         if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) )
00174         {
00175         Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv);
00176         Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) );
00177         assert( Weight1 >= Weight2 );
00178         }
00179         if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) )
00180         {
00181         Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv);
00182         Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) );
00183         assert( Weight1 >= Weight2 );
00184         }
00185 }

void Fxu_HeapDoubleDelete ( Fxu_HeapDouble *  p,
Fxu_Double *  pDiv 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 247 of file fxuHeapD.c.

00248 {
00249         FXU_HEAP_DOUBLE_ASSERT(p,pDiv);
00250         // put the last entry to the deleted place
00251         // decrement the number of entries
00252         p->pTree[pDiv->HNum] = p->pTree[p->nItems--];
00253         p->pTree[pDiv->HNum]->HNum = pDiv->HNum;
00254         // move the top entry down if necessary
00255         Fxu_HeapDoubleUpdate( p, p->pTree[pDiv->HNum] );
00256     pDiv->HNum = 0;
00257 }

Fxu_Double* Fxu_HeapDoubleGetMax ( Fxu_HeapDouble *  p  ) 

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 288 of file fxuHeapD.c.

00289 {
00290         Fxu_Double * pDiv;
00291         if ( p->nItems == 0 )
00292                 return NULL;
00293         // prepare the return value
00294         pDiv = p->pTree[1];
00295         pDiv->HNum = 0;
00296         // put the last entry on top
00297         // decrement the number of entries
00298         p->pTree[1] = p->pTree[p->nItems--];
00299         p->pTree[1]->HNum = 1;
00300         // move the top entry down if necessary
00301         Fxu_HeapDoubleMoveDn( p, p->pTree[1] );
00302         return pDiv;     
00303 }

void Fxu_HeapDoubleInsert ( Fxu_HeapDouble *  p,
Fxu_Double *  pDiv 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 198 of file fxuHeapD.c.

00199 {
00200         if ( p->nItems == p->nItemsAlloc )
00201                 Fxu_HeapDoubleResize( p );
00202         // put the last entry to the last place and move up
00203         p->pTree[++p->nItems] = pDiv;
00204         pDiv->HNum = p->nItems;
00205         // move the last entry up if necessary
00206         Fxu_HeapDoubleMoveUp( p, pDiv );
00207 }

void Fxu_HeapDoubleMoveDn ( Fxu_HeapDouble *  p,
Fxu_Double *  pDiv 
) [static]

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 388 of file fxuHeapD.c.

00389 {
00390         Fxu_Double ** ppChild1, ** ppChild2, ** ppDiv;
00391         ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv);
00392         while ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,*ppDiv) )
00393         { // if Child1 does not exist, Child2 also does not exists
00394 
00395                 // get the children
00396                 ppChild1 = &FXU_HEAP_DOUBLE_CHILD1(p,*ppDiv);
00397         if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,*ppDiv) )
00398         {
00399             ppChild2 = &FXU_HEAP_DOUBLE_CHILD2(p,*ppDiv);
00400 
00401             // consider two cases
00402             if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) &&
00403                  FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) )
00404             { // Div is larger than both, skip
00405                 break;
00406             }
00407             else
00408             { // Div is smaller than one of them, then swap it with larger 
00409                 if ( FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) )
00410                 {
00411                                 Fxu_HeapDoubleSwap( ppDiv, ppChild1 );
00412                             // update the pointer
00413                             ppDiv = ppChild1;
00414                 }
00415                 else
00416                 {
00417                                 Fxu_HeapDoubleSwap( ppDiv, ppChild2 );
00418                             // update the pointer
00419                             ppDiv = ppChild2;
00420                 }
00421             }
00422         }
00423         else // Child2 does not exist
00424         {
00425             // consider two cases
00426             if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) )
00427             { // Div is larger than Child1, skip
00428                 break;
00429             }
00430             else
00431             { // Div is smaller than Child1, then swap them
00432                             Fxu_HeapDoubleSwap( ppDiv, ppChild1 );
00433                         // update the pointer
00434                         ppDiv = ppChild1;
00435             }
00436         }
00437         }
00438 }

void Fxu_HeapDoubleMoveUp ( Fxu_HeapDouble *  p,
Fxu_Double *  pDiv 
) [static]

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 360 of file fxuHeapD.c.

00361 {
00362         Fxu_Double ** ppDiv, ** ppPar;
00363         ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv);
00364         while ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,*ppDiv) )
00365         {
00366                 ppPar = &FXU_HEAP_DOUBLE_PARENT(p,*ppDiv);
00367                 if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) > FXU_HEAP_DOUBLE_WEIGHT(*ppPar) )
00368                 {
00369                         Fxu_HeapDoubleSwap( ppDiv, ppPar );
00370                         ppDiv = ppPar;
00371                 }
00372                 else
00373                         break;
00374         }
00375 }

void Fxu_HeapDoublePrint ( FILE *  pFile,
Fxu_HeapDouble *  p 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 114 of file fxuHeapD.c.

00115 {
00116         Fxu_Double * pDiv;
00117         int Counter = 1;
00118         int Degree  = 1;
00119 
00120         Fxu_HeapDoubleCheck( p );
00121         fprintf( pFile, "The contents of the heap:\n" );
00122         fprintf( pFile, "Level %d:  ", Degree );
00123         Fxu_HeapDoubleForEachItem( p, pDiv )
00124         {
00125                 assert( Counter == p->pTree[Counter]->HNum );
00126                 fprintf( pFile, "%2d=%3d  ", Counter, FXU_HEAP_DOUBLE_WEIGHT(p->pTree[Counter]) );
00127                 if ( ++Counter == (1 << Degree) )
00128                 {
00129                         fprintf( pFile, "\n" );
00130                         Degree++;
00131                         fprintf( pFile, "Level %d:  ", Degree );
00132                 }
00133         }
00134         fprintf( pFile, "\n" );
00135         fprintf( pFile, "End of the heap printout.\n" );
00136 }

Fxu_Double* Fxu_HeapDoubleReadMax ( Fxu_HeapDouble *  p  ) 

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 270 of file fxuHeapD.c.

00271 {
00272         if ( p->nItems == 0 )
00273                 return NULL;
00274         return p->pTree[1];      
00275 }

int Fxu_HeapDoubleReadMaxWeight ( Fxu_HeapDouble *  p  ) 

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 316 of file fxuHeapD.c.

00317 {
00318         if ( p->nItems == 0 )
00319                 return -1;
00320         else
00321                 return FXU_HEAP_DOUBLE_WEIGHT(p->pTree[1]);
00322 }

void Fxu_HeapDoubleResize ( Fxu_HeapDouble *  p  )  [static]

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 79 of file fxuHeapD.c.

00080 {
00081         p->nItemsAlloc *= 2;
00082         p->pTree = REALLOC( Fxu_Double *, p->pTree, p->nItemsAlloc + 1 );
00083 }

Fxu_HeapDouble* Fxu_HeapDoubleStart (  ) 

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 55 of file fxuHeapD.c.

00056 {
00057         Fxu_HeapDouble * p;
00058         p = ALLOC( Fxu_HeapDouble, 1 );
00059         memset( p, 0, sizeof(Fxu_HeapDouble) );
00060         p->nItems      = 0;
00061         p->nItemsAlloc = 10000;
00062         p->pTree       = ALLOC( Fxu_Double *, p->nItemsAlloc + 1 );
00063         p->pTree[0]    = NULL;
00064         return p;
00065 }

void Fxu_HeapDoubleStop ( Fxu_HeapDouble *  p  ) 

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 96 of file fxuHeapD.c.

00097 {
00098         free( p->pTree );
00099         free( p );
00100 }

void Fxu_HeapDoubleSwap ( Fxu_Double **  pDiv1,
Fxu_Double **  pDiv2 
) [static]

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 337 of file fxuHeapD.c.

00338 {
00339         Fxu_Double * pDiv;
00340         int Temp;
00341         pDiv   = *pDiv1;
00342         *pDiv1 = *pDiv2;
00343         *pDiv2 = pDiv;
00344         Temp          = (*pDiv1)->HNum;
00345         (*pDiv1)->HNum = (*pDiv2)->HNum;
00346         (*pDiv2)->HNum = Temp;
00347 }

void Fxu_HeapDoubleUpdate ( Fxu_HeapDouble *  p,
Fxu_Double *  pDiv 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 220 of file fxuHeapD.c.

00221 {
00222 //printf( "Updating divisor %d.\n", pDiv->Num );
00223 
00224         FXU_HEAP_DOUBLE_ASSERT(p,pDiv);
00225         if ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,pDiv) && 
00226          FXU_HEAP_DOUBLE_WEIGHT(pDiv) > FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_PARENT(p,pDiv) ) )
00227                 Fxu_HeapDoubleMoveUp( p, pDiv );
00228         else if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) && 
00229         FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) ) )
00230                 Fxu_HeapDoubleMoveDn( p, pDiv );
00231         else if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) && 
00232         FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) ) )
00233                 Fxu_HeapDoubleMoveDn( p, pDiv );
00234 }

Generated on Tue Jan 5 12:19:26 2010 for abc70930 by  doxygen 1.6.1