src/opt/fxu/fxuHeapS.c File Reference

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

Go to the source code of this file.

Defines

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

Functions

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)
Fxu_HeapSingle * Fxu_HeapSingleStart ()
void Fxu_HeapSingleStop (Fxu_HeapSingle *p)
void Fxu_HeapSinglePrint (FILE *pFile, Fxu_HeapSingle *p)
void Fxu_HeapSingleCheck (Fxu_HeapSingle *p)
void Fxu_HeapSingleCheckOne (Fxu_HeapSingle *p, Fxu_Single *pSingle)
void Fxu_HeapSingleInsert (Fxu_HeapSingle *p, Fxu_Single *pSingle)
void Fxu_HeapSingleUpdate (Fxu_HeapSingle *p, Fxu_Single *pSingle)
void Fxu_HeapSingleDelete (Fxu_HeapSingle *p, Fxu_Single *pSingle)
Fxu_Single * Fxu_HeapSingleReadMax (Fxu_HeapSingle *p)
Fxu_Single * Fxu_HeapSingleGetMax (Fxu_HeapSingle *p)
int Fxu_HeapSingleReadMaxWeight (Fxu_HeapSingle *p)

Define Documentation

#define FXU_HEAP_SINGLE_ASSERT ( p,
pSingle   )     assert( (pSingle)->HNum >= 1 && (pSingle)->HNum <= p->nItemsAlloc )

Definition at line 33 of file fxuHeapS.c.

#define FXU_HEAP_SINGLE_CHILD1 ( p,
pSingle   )     ((p)->pTree[(pSingle)->HNum << 1])

Definition at line 31 of file fxuHeapS.c.

#define FXU_HEAP_SINGLE_CHILD1_EXISTS ( p,
pSingle   )     (((pSingle)->HNum << 1) <= p->nItems)

Definition at line 28 of file fxuHeapS.c.

#define FXU_HEAP_SINGLE_CHILD2 ( p,
pSingle   )     ((p)->pTree[((pSingle)->HNum << 1)+1])

Definition at line 32 of file fxuHeapS.c.

#define FXU_HEAP_SINGLE_CHILD2_EXISTS ( p,
pSingle   )     ((((pSingle)->HNum << 1)+1) <= p->nItems)

Definition at line 29 of file fxuHeapS.c.

#define FXU_HEAP_SINGLE_CURRENT ( p,
pSingle   )     ((p)->pTree[(pSingle)->HNum])

Definition at line 26 of file fxuHeapS.c.

#define FXU_HEAP_SINGLE_PARENT ( p,
pSingle   )     ((p)->pTree[(pSingle)->HNum >> 1])

Definition at line 30 of file fxuHeapS.c.

#define FXU_HEAP_SINGLE_PARENT_EXISTS ( p,
pSingle   )     ((pSingle)->HNum > 1)

Definition at line 27 of file fxuHeapS.c.

#define FXU_HEAP_SINGLE_WEIGHT ( pSingle   )     ((pSingle)->Weight)

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

] DECLARATIONS ///

Definition at line 25 of file fxuHeapS.c.

Function Documentation

void Fxu_HeapSingleCheck ( Fxu_HeapSingle *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 152 of file fxuHeapS.c.

00153 {
00154         Fxu_Single * pSingle;
00155         Fxu_HeapSingleForEachItem( p, pSingle )
00156         {
00157                 assert( pSingle->HNum == p->i );
00158         Fxu_HeapSingleCheckOne( p, pSingle );
00159         }
00160 }

void Fxu_HeapSingleCheckOne ( Fxu_HeapSingle *  p,
Fxu_Single *  pSingle 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 173 of file fxuHeapS.c.

00174 {
00175     int Weight1, Weight2;
00176         if ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,pSingle) )
00177         {
00178         Weight1 = FXU_HEAP_SINGLE_WEIGHT(pSingle);
00179         Weight2 = FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD1(p,pSingle) );
00180         assert( Weight1 >= Weight2 );
00181         }
00182         if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,pSingle) )
00183         {
00184         Weight1 = FXU_HEAP_SINGLE_WEIGHT(pSingle);
00185         Weight2 = FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD2(p,pSingle) );
00186         assert( Weight1 >= Weight2 );
00187         }
00188 }

void Fxu_HeapSingleDelete ( Fxu_HeapSingle *  p,
Fxu_Single *  pSingle 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 248 of file fxuHeapS.c.

00249 {
00250     int Place = pSingle->HNum;
00251         FXU_HEAP_SINGLE_ASSERT(p,pSingle);
00252         // put the last entry to the deleted place
00253         // decrement the number of entries
00254         p->pTree[Place] = p->pTree[p->nItems--];
00255         p->pTree[Place]->HNum = Place;
00256         // move the top entry down if necessary
00257         Fxu_HeapSingleUpdate( p, p->pTree[Place] );
00258     pSingle->HNum = 0;
00259 }

Fxu_Single* Fxu_HeapSingleGetMax ( Fxu_HeapSingle *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 290 of file fxuHeapS.c.

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

void Fxu_HeapSingleInsert ( Fxu_HeapSingle *  p,
Fxu_Single *  pSingle 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 201 of file fxuHeapS.c.

00202 {
00203         if ( p->nItems == p->nItemsAlloc )
00204                 Fxu_HeapSingleResize( p );
00205         // put the last entry to the last place and move up
00206         p->pTree[++p->nItems] = pSingle;
00207         pSingle->HNum = p->nItems;
00208         // move the last entry up if necessary
00209         Fxu_HeapSingleMoveUp( p, pSingle );
00210 }

void Fxu_HeapSingleMoveDn ( Fxu_HeapSingle *  p,
Fxu_Single *  pSingle 
) [static]

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 389 of file fxuHeapS.c.

00390 {
00391         Fxu_Single ** ppChild1, ** ppChild2, ** ppSingle;
00392         ppSingle = &FXU_HEAP_SINGLE_CURRENT(p, pSingle);
00393         while ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,*ppSingle) )
00394         { // if Child1 does not exist, Child2 also does not exists
00395 
00396                 // get the children
00397                 ppChild1 = &FXU_HEAP_SINGLE_CHILD1(p,*ppSingle);
00398         if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,*ppSingle) )
00399         {
00400             ppChild2 = &FXU_HEAP_SINGLE_CHILD2(p,*ppSingle);
00401 
00402             // consider two cases
00403             if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild1) &&
00404                  FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild2) )
00405             { // Var is larger than both, skip
00406                 break;
00407             }
00408             else
00409             { // Var is smaller than one of them, then swap it with larger 
00410                 if ( FXU_HEAP_SINGLE_WEIGHT(*ppChild1) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild2) )
00411                 {
00412                                 Fxu_HeapSingleSwap( ppSingle, ppChild1 );
00413                             // update the pointer
00414                             ppSingle = ppChild1;
00415                 }
00416                 else
00417                 {
00418                                 Fxu_HeapSingleSwap( ppSingle, ppChild2 );
00419                             // update the pointer
00420                             ppSingle = ppChild2;
00421                 }
00422             }
00423         }
00424         else // Child2 does not exist
00425         {
00426             // consider two cases
00427             if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild1) )
00428             { // Var is larger than Child1, skip
00429                 break;
00430             }
00431             else
00432             { // Var is smaller than Child1, then swap them
00433                             Fxu_HeapSingleSwap( ppSingle, ppChild1 );
00434                         // update the pointer
00435                         ppSingle = ppChild1;
00436             }
00437         }
00438         }
00439 }

void Fxu_HeapSingleMoveUp ( Fxu_HeapSingle *  p,
Fxu_Single *  pSingle 
) [static]

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 361 of file fxuHeapS.c.

00362 {
00363         Fxu_Single ** ppSingle, ** ppPar;
00364         ppSingle = &FXU_HEAP_SINGLE_CURRENT(p, pSingle);
00365         while ( FXU_HEAP_SINGLE_PARENT_EXISTS(p,*ppSingle) )
00366         {
00367                 ppPar = &FXU_HEAP_SINGLE_PARENT(p,*ppSingle);
00368                 if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) > FXU_HEAP_SINGLE_WEIGHT(*ppPar) )
00369                 {
00370                         Fxu_HeapSingleSwap( ppSingle, ppPar );
00371                         ppSingle = ppPar;
00372                 }
00373                 else
00374                         break;
00375         }
00376 }

void Fxu_HeapSinglePrint ( FILE *  pFile,
Fxu_HeapSingle *  p 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 117 of file fxuHeapS.c.

00118 {
00119         Fxu_Single * pSingle;
00120         int Counter = 1;
00121         int Degree  = 1;
00122 
00123         Fxu_HeapSingleCheck( p );
00124         fprintf( pFile, "The contents of the heap:\n" );
00125         fprintf( pFile, "Level %d:  ", Degree );
00126         Fxu_HeapSingleForEachItem( p, pSingle )
00127         {
00128                 assert( Counter == p->pTree[Counter]->HNum );
00129                 fprintf( pFile, "%2d=%3d  ", Counter, FXU_HEAP_SINGLE_WEIGHT(p->pTree[Counter]) );
00130                 if ( ++Counter == (1 << Degree) )
00131                 {
00132                         fprintf( pFile, "\n" );
00133                         Degree++;
00134                         fprintf( pFile, "Level %d:  ", Degree );
00135                 }
00136         }
00137         fprintf( pFile, "\n" );
00138         fprintf( pFile, "End of the heap printout.\n" );
00139 }

Fxu_Single* Fxu_HeapSingleReadMax ( Fxu_HeapSingle *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 272 of file fxuHeapS.c.

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

int Fxu_HeapSingleReadMaxWeight ( Fxu_HeapSingle *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 318 of file fxuHeapS.c.

00319 {
00320         if ( p->nItems == 0 )
00321                 return -1;
00322         return FXU_HEAP_SINGLE_WEIGHT(p->pTree[1]);
00323 }

void Fxu_HeapSingleResize ( Fxu_HeapSingle *  p  )  [static]

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 79 of file fxuHeapS.c.

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

Fxu_HeapSingle* Fxu_HeapSingleStart (  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 55 of file fxuHeapS.c.

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

void Fxu_HeapSingleStop ( Fxu_HeapSingle *  p  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 96 of file fxuHeapS.c.

00097 {
00098     int i;
00099     i = 0;
00100         free( p->pTree );
00101     i = 1;
00102         free( p );
00103 }

void Fxu_HeapSingleSwap ( Fxu_Single **  pSingle1,
Fxu_Single **  pSingle2 
) [static]

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 338 of file fxuHeapS.c.

00339 {
00340         Fxu_Single * pSingle;
00341         int Temp;
00342         pSingle   = *pSingle1;
00343         *pSingle1 = *pSingle2;
00344         *pSingle2 = pSingle;
00345         Temp          = (*pSingle1)->HNum;
00346         (*pSingle1)->HNum = (*pSingle2)->HNum;
00347         (*pSingle2)->HNum = Temp;
00348 }

void Fxu_HeapSingleUpdate ( Fxu_HeapSingle *  p,
Fxu_Single *  pSingle 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 223 of file fxuHeapS.c.

00224 {
00225         FXU_HEAP_SINGLE_ASSERT(p,pSingle);
00226         if ( FXU_HEAP_SINGLE_PARENT_EXISTS(p,pSingle) && 
00227          FXU_HEAP_SINGLE_WEIGHT(pSingle) > FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_PARENT(p,pSingle) ) )
00228                 Fxu_HeapSingleMoveUp( p, pSingle );
00229         else if ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,pSingle) && 
00230         FXU_HEAP_SINGLE_WEIGHT(pSingle) < FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD1(p,pSingle) ) )
00231                 Fxu_HeapSingleMoveDn( p, pSingle );
00232         else if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,pSingle) && 
00233         FXU_HEAP_SINGLE_WEIGHT(pSingle) < FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD2(p,pSingle) ) )
00234                 Fxu_HeapSingleMoveDn( p, pSingle );
00235 }

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