fxuHeapS.c File Reference

#include "fxuInt.h"

Include dependency graph for fxuHeapS.c:

Go to the source code of this file.

Macros
#define	FXU_HEAP_SINGLE_WEIGHT(pSingle)
	DECLARATIONS ///.
#define	FXU_HEAP_SINGLE_CURRENT(p, pSingle)
#define	FXU_HEAP_SINGLE_PARENT_EXISTS(p, pSingle)
#define	FXU_HEAP_SINGLE_CHILD1_EXISTS(p, pSingle)
#define	FXU_HEAP_SINGLE_CHILD2_EXISTS(p, pSingle)
#define	FXU_HEAP_SINGLE_PARENT(p, pSingle)
#define	FXU_HEAP_SINGLE_CHILD1(p, pSingle)
#define	FXU_HEAP_SINGLE_CHILD2(p, pSingle)
#define	FXU_HEAP_SINGLE_ASSERT(p, pSingle)

Functions
Fxu_HeapSingle *	Fxu_HeapSingleStart ()
	FUNCTION DEFINITIONS ///.
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)

Macro Definition Documentation

FXU_HEAP_SINGLE_ASSERT

#define FXU_HEAP_SINGLE_ASSERT	(		p,
			pSingle )

Value:

assert( (pSingle)->HNum >= 1 && (pSingle)->HNum <= p->nItemsAlloc )

Definition at line 36 of file fxuHeapS.c.

FXU_HEAP_SINGLE_CHILD1

#define FXU_HEAP_SINGLE_CHILD1	(		p,
			pSingle )

Value:

((p)->pTree[(pSingle)->HNum << 1])

Definition at line 34 of file fxuHeapS.c.

FXU_HEAP_SINGLE_CHILD1_EXISTS

#define FXU_HEAP_SINGLE_CHILD1_EXISTS	(		p,
			pSingle )

Value:

(((pSingle)->HNum << 1) <= p->nItems)

Definition at line 31 of file fxuHeapS.c.

FXU_HEAP_SINGLE_CHILD2

#define FXU_HEAP_SINGLE_CHILD2	(		p,
			pSingle )

Value:

((p)->pTree[((pSingle)->HNum << 1)+1])

Definition at line 35 of file fxuHeapS.c.

FXU_HEAP_SINGLE_CHILD2_EXISTS

#define FXU_HEAP_SINGLE_CHILD2_EXISTS	(		p,
			pSingle )

Value:

((((pSingle)->HNum << 1)+1) <= p->nItems)

Definition at line 32 of file fxuHeapS.c.

FXU_HEAP_SINGLE_CURRENT

#define FXU_HEAP_SINGLE_CURRENT	(		p,
			pSingle )

Value:

((p)->pTree[(pSingle)->HNum])

Definition at line 29 of file fxuHeapS.c.

FXU_HEAP_SINGLE_PARENT

#define FXU_HEAP_SINGLE_PARENT	(		p,
			pSingle )

Value:

((p)->pTree[(pSingle)->HNum >> 1])

Definition at line 33 of file fxuHeapS.c.

FXU_HEAP_SINGLE_PARENT_EXISTS

#define FXU_HEAP_SINGLE_PARENT_EXISTS	(		p,
			pSingle )

Value:

((pSingle)->HNum > 1)

Definition at line 30 of file fxuHeapS.c.

FXU_HEAP_SINGLE_WEIGHT

#define FXU_HEAP_SINGLE_WEIGHT

(

pSingle

)

Value:

((pSingle)->Weight)

DECLARATIONS ///.

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

]

Definition at line 28 of file fxuHeapS.c.

Function Documentation

Fxu_HeapSingleCheck()

void Fxu_HeapSingleCheck

(

Fxu_HeapSingle *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 155 of file fxuHeapS.c.

{
    Fxu_Single * pSingle;
    Fxu_HeapSingleForEachItem( p, pSingle )
    {
        assert( pSingle->HNum == p->i );
        Fxu_HeapSingleCheckOne( p, pSingle );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fxu_HeapSingleCheckOne()

void Fxu_HeapSingleCheckOne	(	Fxu_HeapSingle *	p,
		Fxu_Single *	pSingle )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 176 of file fxuHeapS.c.

{
    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 );
    }
}

Here is the caller graph for this function:

Fxu_HeapSingleDelete()

void Fxu_HeapSingleDelete	(	Fxu_HeapSingle *	p,
		Fxu_Single *	pSingle )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 251 of file fxuHeapS.c.

{
    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;
}

Here is the call graph for this function:

Fxu_HeapSingleGetMax()

Fxu_Single * Fxu_HeapSingleGetMax

(

Fxu_HeapSingle *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 293 of file fxuHeapS.c.

{
    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;     
}

Here is the caller graph for this function:

Fxu_HeapSingleInsert()

void Fxu_HeapSingleInsert	(	Fxu_HeapSingle *	p,
		Fxu_Single *	pSingle )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 204 of file fxuHeapS.c.

{
    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 );
}

Here is the caller graph for this function:

Fxu_HeapSinglePrint()

void Fxu_HeapSinglePrint	(	FILE *	pFile,
		Fxu_HeapSingle *	p )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 120 of file fxuHeapS.c.

{
    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" );
}

Here is the call graph for this function:

Fxu_HeapSingleReadMax()

Fxu_Single * Fxu_HeapSingleReadMax

(

Fxu_HeapSingle *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 275 of file fxuHeapS.c.

{
    if ( p->nItems == 0 )
        return NULL;
    return p->pTree[1];
}

Here is the caller graph for this function:

Fxu_HeapSingleReadMaxWeight()

int Fxu_HeapSingleReadMaxWeight

(

Fxu_HeapSingle *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 321 of file fxuHeapS.c.

{
    if ( p->nItems == 0 )
        return -1;
    return FXU_HEAP_SINGLE_WEIGHT(p->pTree[1]);
}

Here is the caller graph for this function:

Fxu_HeapSingleStart()

Fxu_HeapSingle * Fxu_HeapSingleStart

(

)

FUNCTION DEFINITIONS ///.

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 58 of file fxuHeapS.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fxu_HeapSingleStop()

void Fxu_HeapSingleStop

(

Fxu_HeapSingle *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 99 of file fxuHeapS.c.

{
    int i;
    i = 0;
    ABC_FREE( p->pTree );
    i = 1;
    ABC_FREE( p );
}

Here is the caller graph for this function:

Fxu_HeapSingleUpdate()

void Fxu_HeapSingleUpdate	(	Fxu_HeapSingle *	p,
		Fxu_Single *	pSingle )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 226 of file fxuHeapS.c.

{
    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 );
}

Here is the caller graph for this function: