fxuHeapD.c File Reference

#include "fxuInt.h"

Include dependency graph for fxuHeapD.c:

Go to the source code of this file.

Macros
#define	FXU_HEAP_DOUBLE_WEIGHT(pDiv)
	DECLARATIONS ///.
#define	FXU_HEAP_DOUBLE_CURRENT(p, pDiv)
#define	FXU_HEAP_DOUBLE_PARENT_EXISTS(p, pDiv)
#define	FXU_HEAP_DOUBLE_CHILD1_EXISTS(p, pDiv)
#define	FXU_HEAP_DOUBLE_CHILD2_EXISTS(p, pDiv)
#define	FXU_HEAP_DOUBLE_PARENT(p, pDiv)
#define	FXU_HEAP_DOUBLE_CHILD1(p, pDiv)
#define	FXU_HEAP_DOUBLE_CHILD2(p, pDiv)
#define	FXU_HEAP_DOUBLE_ASSERT(p, pDiv)

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

Macro Definition Documentation

FXU_HEAP_DOUBLE_ASSERT

#define FXU_HEAP_DOUBLE_ASSERT	(		p,
			pDiv )

Value:

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

Definition at line 36 of file fxuHeapD.c.

FXU_HEAP_DOUBLE_CHILD1

#define FXU_HEAP_DOUBLE_CHILD1	(		p,
			pDiv )

Value:

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

Definition at line 34 of file fxuHeapD.c.

FXU_HEAP_DOUBLE_CHILD1_EXISTS

#define FXU_HEAP_DOUBLE_CHILD1_EXISTS	(		p,
			pDiv )

Value:

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

Definition at line 31 of file fxuHeapD.c.

FXU_HEAP_DOUBLE_CHILD2

#define FXU_HEAP_DOUBLE_CHILD2	(		p,
			pDiv )

Value:

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

Definition at line 35 of file fxuHeapD.c.

FXU_HEAP_DOUBLE_CHILD2_EXISTS

#define FXU_HEAP_DOUBLE_CHILD2_EXISTS	(		p,
			pDiv )

Value:

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

Definition at line 32 of file fxuHeapD.c.

FXU_HEAP_DOUBLE_CURRENT

#define FXU_HEAP_DOUBLE_CURRENT	(		p,
			pDiv )

Value:

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

Definition at line 29 of file fxuHeapD.c.

FXU_HEAP_DOUBLE_PARENT

#define FXU_HEAP_DOUBLE_PARENT	(		p,
			pDiv )

Value:

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

Definition at line 33 of file fxuHeapD.c.

FXU_HEAP_DOUBLE_PARENT_EXISTS

#define FXU_HEAP_DOUBLE_PARENT_EXISTS	(		p,
			pDiv )

Value:

((pDiv)->HNum > 1)

Definition at line 30 of file fxuHeapD.c.

FXU_HEAP_DOUBLE_WEIGHT

#define FXU_HEAP_DOUBLE_WEIGHT

(

pDiv

)

Value:

((pDiv)->Weight)

DECLARATIONS ///.

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

]

Definition at line 28 of file fxuHeapD.c.

Function Documentation

Fxu_HeapDoubleCheck()

void Fxu_HeapDoubleCheck

(

Fxu_HeapDouble *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 152 of file fxuHeapD.c.

{
    Fxu_Double * pDiv;
    Fxu_HeapDoubleForEachItem( p, pDiv )
    {
        assert( pDiv->HNum == p->i );
        Fxu_HeapDoubleCheckOne( p, pDiv );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fxu_HeapDoubleCheckOne()

void Fxu_HeapDoubleCheckOne	(	Fxu_HeapDouble *	p,
		Fxu_Double *	pDiv )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 173 of file fxuHeapD.c.

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

Here is the caller graph for this function:

Fxu_HeapDoubleDelete()

void Fxu_HeapDoubleDelete	(	Fxu_HeapDouble *	p,
		Fxu_Double *	pDiv )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 250 of file fxuHeapD.c.

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

Here is the call graph for this function:

Here is the caller graph for this function:

Fxu_HeapDoubleGetMax()

Fxu_Double * Fxu_HeapDoubleGetMax

(

Fxu_HeapDouble *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 291 of file fxuHeapD.c.

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

Here is the caller graph for this function:

Fxu_HeapDoubleInsert()

void Fxu_HeapDoubleInsert	(	Fxu_HeapDouble *	p,
		Fxu_Double *	pDiv )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 201 of file fxuHeapD.c.

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

Here is the caller graph for this function:

Fxu_HeapDoublePrint()

void Fxu_HeapDoublePrint	(	FILE *	pFile,
		Fxu_HeapDouble *	p )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 117 of file fxuHeapD.c.

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

Here is the call graph for this function:

Fxu_HeapDoubleReadMax()

Fxu_Double * Fxu_HeapDoubleReadMax

(

Fxu_HeapDouble *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 273 of file fxuHeapD.c.

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

Fxu_HeapDoubleReadMaxWeight()

int Fxu_HeapDoubleReadMaxWeight

(

Fxu_HeapDouble *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 319 of file fxuHeapD.c.

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

Here is the caller graph for this function:

Fxu_HeapDoubleStart()

Fxu_HeapDouble * Fxu_HeapDoubleStart

(

)

FUNCTION DEFINITIONS ///.

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 58 of file fxuHeapD.c.

{
    Fxu_HeapDouble * p;
    p = ABC_ALLOC( Fxu_HeapDouble, 1 );
    memset( p, 0, sizeof(Fxu_HeapDouble) );
    p->nItems      = 0;
    p->nItemsAlloc = 10000;
    p->pTree       = ABC_ALLOC( Fxu_Double *, p->nItemsAlloc + 1 );
    p->pTree[0]    = NULL;
    return p;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fxu_HeapDoubleStop()

void Fxu_HeapDoubleStop

(

Fxu_HeapDouble *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 99 of file fxuHeapD.c.

{
    ABC_FREE( p->pTree );
    ABC_FREE( p );
}

Here is the caller graph for this function:

Fxu_HeapDoubleUpdate()

void Fxu_HeapDoubleUpdate	(	Fxu_HeapDouble *	p,
		Fxu_Double *	pDiv )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 223 of file fxuHeapD.c.

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

Here is the caller graph for this function: