fraigVec.c File Reference

#include "fraigInt.h"

Include dependency graph for fraigVec.c:

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START Fraig_NodeVec_t *	Fraig_NodeVecAlloc (int nCap)
	DECLARATIONS ///.
void	Fraig_NodeVecFree (Fraig_NodeVec_t *p)
Fraig_NodeVec_t *	Fraig_NodeVecDup (Fraig_NodeVec_t *pVec)
Fraig_Node_t **	Fraig_NodeVecReadArray (Fraig_NodeVec_t *p)
int	Fraig_NodeVecReadSize (Fraig_NodeVec_t *p)
void	Fraig_NodeVecGrow (Fraig_NodeVec_t *p, int nCapMin)
void	Fraig_NodeVecShrink (Fraig_NodeVec_t *p, int nSizeNew)
void	Fraig_NodeVecClear (Fraig_NodeVec_t *p)
void	Fraig_NodeVecPush (Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
int	Fraig_NodeVecPushUnique (Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
void	Fraig_NodeVecPushOrder (Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
int	Fraig_NodeVecPushUniqueOrder (Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
void	Fraig_NodeVecPushOrderByLevel (Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
int	Fraig_NodeVecPushUniqueOrderByLevel (Fraig_NodeVec_t *p, Fraig_Node_t *pNode)
Fraig_Node_t *	Fraig_NodeVecPop (Fraig_NodeVec_t *p)
void	Fraig_NodeVecRemove (Fraig_NodeVec_t *p, Fraig_Node_t *Entry)
void	Fraig_NodeVecWriteEntry (Fraig_NodeVec_t *p, int i, Fraig_Node_t *Entry)
Fraig_Node_t *	Fraig_NodeVecReadEntry (Fraig_NodeVec_t *p, int i)
int	Fraig_NodeVecCompareLevelsIncreasing (Fraig_Node_t **pp1, Fraig_Node_t **pp2)
int	Fraig_NodeVecCompareLevelsDecreasing (Fraig_Node_t **pp1, Fraig_Node_t **pp2)
int	Fraig_NodeVecCompareNumbers (Fraig_Node_t **pp1, Fraig_Node_t **pp2)
int	Fraig_NodeVecCompareRefCounts (Fraig_Node_t **pp1, Fraig_Node_t **pp2)
void	Fraig_NodeVecSortByLevel (Fraig_NodeVec_t *p, int fIncreasing)
void	Fraig_NodeVecSortByNumber (Fraig_NodeVec_t *p)
void	Fraig_NodeVecSortByRefCount (Fraig_NodeVec_t *p)

Function Documentation

Fraig_NodeVecAlloc()

ABC_NAMESPACE_IMPL_START Fraig_NodeVec_t * Fraig_NodeVecAlloc

(

int

nCap

)

DECLARATIONS ///.

CFile****************************************************************

FileName [fraigVec.c]

PackageName [FRAIG: Functionally reduced AND-INV graphs.]

Synopsis [Vector of FRAIG nodes.]

Author [Alan Mishchenko alanm.nosp@m.i@ee.nosp@m.cs.be.nosp@m.rkel.nosp@m.ey.ed.nosp@m.u]

Affiliation [UC Berkeley]

Date [Ver. 2.0. Started - October 1, 2004]

Revision [

Id

fraigVec.c,v 1.7 2005/07/08 01:01:34 alanmi Exp

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

Synopsis [Allocates a vector with the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 43 of file fraigVec.c.

{
    Fraig_NodeVec_t * p;
    p = ABC_ALLOC( Fraig_NodeVec_t, 1 );
    if ( nCap > 0 && nCap < 8 )
        nCap = 8;
    p->nSize  = 0;
    p->nCap   = nCap;
    p->pArray = p->nCap? ABC_ALLOC( Fraig_Node_t *, p->nCap ) : NULL;
    return p;
}

Here is the caller graph for this function:

Fraig_NodeVecClear()

void Fraig_NodeVecClear

(

Fraig_NodeVec_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 173 of file fraigVec.c.

{
    p->nSize = 0;
}

Fraig_NodeVecCompareLevelsDecreasing()

int Fraig_NodeVecCompareLevelsDecreasing	(	Fraig_Node_t **	pp1,
		Fraig_Node_t **	pp2 )

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

Synopsis [Comparison procedure for two clauses.]

Description []

SideEffects []

SeeAlso []

Definition at line 426 of file fraigVec.c.

{
    int Level1 = Fraig_Regular(*pp1)->Level;
    int Level2 = Fraig_Regular(*pp2)->Level;
    if ( Level1 > Level2 )
        return -1;
    if ( Level1 < Level2 )
        return 1;
    return 0; 
}

Here is the caller graph for this function:

Fraig_NodeVecCompareLevelsIncreasing()

int Fraig_NodeVecCompareLevelsIncreasing	(	Fraig_Node_t **	pp1,
		Fraig_Node_t **	pp2 )

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

Synopsis [Comparison procedure for two clauses.]

Description []

SideEffects []

SeeAlso []

Definition at line 404 of file fraigVec.c.

{
    int Level1 = Fraig_Regular(*pp1)->Level;
    int Level2 = Fraig_Regular(*pp2)->Level;
    if ( Level1 < Level2 )
        return -1;
    if ( Level1 > Level2 )
        return 1;
    return 0; 
}

Here is the caller graph for this function:

Fraig_NodeVecCompareNumbers()

int Fraig_NodeVecCompareNumbers	(	Fraig_Node_t **	pp1,
		Fraig_Node_t **	pp2 )

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

Synopsis [Comparison procedure for two clauses.]

Description []

SideEffects []

SeeAlso []

Definition at line 448 of file fraigVec.c.

{
    int Num1 = Fraig_Regular(*pp1)->Num;
    int Num2 = Fraig_Regular(*pp2)->Num;
    if ( Num1 < Num2 )
        return -1;
    if ( Num1 > Num2 )
        return 1;
    return 0; 
}

Here is the caller graph for this function:

Fraig_NodeVecCompareRefCounts()

int Fraig_NodeVecCompareRefCounts	(	Fraig_Node_t **	pp1,
		Fraig_Node_t **	pp2 )

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

Synopsis [Comparison procedure for two clauses.]

Description []

SideEffects []

SeeAlso []

Definition at line 470 of file fraigVec.c.

{
    int nRefs1 = Fraig_Regular(*pp1)->nRefs;
    int nRefs2 = Fraig_Regular(*pp2)->nRefs;
 
    if ( nRefs1 < nRefs2 )
        return -1;
    if ( nRefs1 > nRefs2 )
        return 1;
 
    nRefs1 = Fraig_Regular(*pp1)->Level;
    nRefs2 = Fraig_Regular(*pp2)->Level;
 
    if ( nRefs1 < nRefs2 )
        return -1;
    if ( nRefs1 > nRefs2 )
        return 1;
    return 0; 
}

Here is the caller graph for this function:

Fraig_NodeVecDup()

Fraig_NodeVec_t * Fraig_NodeVecDup

(

Fraig_NodeVec_t *

pVec

)

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

Synopsis [Duplicates the integer array.]

Description []

SideEffects []

SeeAlso []

Definition at line 83 of file fraigVec.c.

{
    Fraig_NodeVec_t * p;
    p = ABC_ALLOC( Fraig_NodeVec_t, 1 );
    p->nSize  = pVec->nSize;
    p->nCap   = pVec->nCap;
    p->pArray = p->nCap? ABC_ALLOC( Fraig_Node_t *, p->nCap ) : NULL;
    memcpy( p->pArray, pVec->pArray, sizeof(Fraig_Node_t *) * pVec->nSize );
    return p;
}

Here is the call graph for this function:

Fraig_NodeVecFree()

void Fraig_NodeVecFree

(

Fraig_NodeVec_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 66 of file fraigVec.c.

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

Here is the caller graph for this function:

Fraig_NodeVecGrow()

void Fraig_NodeVecGrow	(	Fraig_NodeVec_t *	p,
		int	nCapMin )

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

Synopsis [Resizes the vector to the given capacity.]

Description []

SideEffects []

SeeAlso []

Definition at line 137 of file fraigVec.c.

{
    if ( p->nCap >= nCapMin )
        return;
    p->pArray = ABC_REALLOC( Fraig_Node_t *, p->pArray, nCapMin ); 
    p->nCap   = nCapMin;
}

Here is the caller graph for this function:

Fraig_NodeVecPop()

Fraig_Node_t * Fraig_NodeVecPop

(

Fraig_NodeVec_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 331 of file fraigVec.c.

{
    return p->pArray[--p->nSize];
}

Fraig_NodeVecPush()

void Fraig_NodeVecPush	(	Fraig_NodeVec_t *	p,
		Fraig_Node_t *	Entry )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 189 of file fraigVec.c.

{
    if ( p->nSize == p->nCap )
    {
        if ( p->nCap < 16 )
            Fraig_NodeVecGrow( p, 16 );
        else
            Fraig_NodeVecGrow( p, 2 * p->nCap );
    }
    p->pArray[p->nSize++] = Entry;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fraig_NodeVecPushOrder()

void Fraig_NodeVecPushOrder	(	Fraig_NodeVec_t *	p,
		Fraig_Node_t *	pNode )

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

Synopsis [Inserts a new node in the order by arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 233 of file fraigVec.c.

{
    Fraig_Node_t * pNode1, * pNode2;
    int i;
    Fraig_NodeVecPush( p, pNode );
    // find the p of the node
    for ( i = p->nSize-1; i > 0; i-- )
    {
        pNode1 = p->pArray[i  ];
        pNode2 = p->pArray[i-1];
        if ( pNode1 >= pNode2 )
            break;
        p->pArray[i  ] = pNode2;
        p->pArray[i-1] = pNode1;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fraig_NodeVecPushOrderByLevel()

void Fraig_NodeVecPushOrderByLevel	(	Fraig_NodeVec_t *	p,
		Fraig_Node_t *	pNode )

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

Synopsis [Inserts a new node in the order by arrival times.]

Description []

SideEffects []

SeeAlso []

Definition at line 282 of file fraigVec.c.

{
    Fraig_Node_t * pNode1, * pNode2;
    int i;
    Fraig_NodeVecPush( p, pNode );
    // find the p of the node
    for ( i = p->nSize-1; i > 0; i-- )
    {
        pNode1 = p->pArray[i  ];
        pNode2 = p->pArray[i-1];
        if ( Fraig_Regular(pNode1)->Level <= Fraig_Regular(pNode2)->Level )
            break;
        p->pArray[i  ] = pNode2;
        p->pArray[i-1] = pNode1;
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fraig_NodeVecPushUnique()

int Fraig_NodeVecPushUnique	(	Fraig_NodeVec_t *	p,
		Fraig_Node_t *	Entry )

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

Synopsis [Add the element while ensuring uniqueness.]

Description [Returns 1 if the element was found, and 0 if it was new. ]

SideEffects []

SeeAlso []

Definition at line 212 of file fraigVec.c.

{
    int i;
    for ( i = 0; i < p->nSize; i++ )
        if ( p->pArray[i] == Entry )
            return 1;
    Fraig_NodeVecPush( p, Entry );
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fraig_NodeVecPushUniqueOrder()

int Fraig_NodeVecPushUniqueOrder	(	Fraig_NodeVec_t *	p,
		Fraig_Node_t *	pNode )

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

Synopsis [Add the element while ensuring uniqueness in the order.]

Description [Returns 1 if the element was found, and 0 if it was new. ]

SideEffects []

SeeAlso []

Definition at line 261 of file fraigVec.c.

{
    int i;
    for ( i = 0; i < p->nSize; i++ )
        if ( p->pArray[i] == pNode )
            return 1;
    Fraig_NodeVecPushOrder( p, pNode );
    return 0;
}

Here is the call graph for this function:

Fraig_NodeVecPushUniqueOrderByLevel()

int Fraig_NodeVecPushUniqueOrderByLevel	(	Fraig_NodeVec_t *	p,
		Fraig_Node_t *	pNode )

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

Synopsis [Add the element while ensuring uniqueness in the order.]

Description [Returns 1 if the element was found, and 0 if it was new. ]

SideEffects []

SeeAlso []

Definition at line 310 of file fraigVec.c.

{
    int i;
    for ( i = 0; i < p->nSize; i++ )
        if ( p->pArray[i] == pNode )
            return 1;
    Fraig_NodeVecPushOrderByLevel( p, pNode );
    return 0;
}

Here is the call graph for this function:

Fraig_NodeVecReadArray()

Fraig_Node_t ** Fraig_NodeVecReadArray

(

Fraig_NodeVec_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 105 of file fraigVec.c.

{
    return p->pArray;
}

Fraig_NodeVecReadEntry()

Fraig_Node_t * Fraig_NodeVecReadEntry	(	Fraig_NodeVec_t *	p,
		int	i )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 387 of file fraigVec.c.

{
    assert( i >= 0 && i < p->nSize );
    return p->pArray[i];
}

Fraig_NodeVecReadSize()

int Fraig_NodeVecReadSize

(

Fraig_NodeVec_t *

p

)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 121 of file fraigVec.c.

{
    return p->nSize;
}

Fraig_NodeVecRemove()

void Fraig_NodeVecRemove	(	Fraig_NodeVec_t *	p,
		Fraig_Node_t *	Entry )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 347 of file fraigVec.c.

{
    int i;
    for ( i = 0; i < p->nSize; i++ )
        if ( p->pArray[i] == Entry )
            break;
    assert( i < p->nSize );
    for ( i++; i < p->nSize; i++ )
        p->pArray[i-1] = p->pArray[i];
    p->nSize--;
}

Fraig_NodeVecShrink()

void Fraig_NodeVecShrink	(	Fraig_NodeVec_t *	p,
		int	nSizeNew )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 156 of file fraigVec.c.

{
    assert( p->nSize >= nSizeNew );
    p->nSize = nSizeNew;
}

Fraig_NodeVecSortByLevel()

void Fraig_NodeVecSortByLevel	(	Fraig_NodeVec_t *	p,
		int	fIncreasing )

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

Synopsis [Sorting the entries by their integer value.]

Description []

SideEffects []

SeeAlso []

Definition at line 501 of file fraigVec.c.

{
    if ( fIncreasing )
        qsort( (void *)p->pArray, (size_t)p->nSize, sizeof(Fraig_Node_t *), 
                (int (*)(const void *, const void *)) Fraig_NodeVecCompareLevelsIncreasing );
    else 
        qsort( (void *)p->pArray, (size_t)p->nSize, sizeof(Fraig_Node_t *), 
                (int (*)(const void *, const void *)) Fraig_NodeVecCompareLevelsDecreasing );
}

Here is the call graph for this function:

Fraig_NodeVecSortByNumber()

void Fraig_NodeVecSortByNumber

(

Fraig_NodeVec_t *

p

)

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

Synopsis [Sorting the entries by their integer value.]

Description []

SideEffects []

SeeAlso []

Definition at line 522 of file fraigVec.c.

{
    qsort( (void *)p->pArray, (size_t)p->nSize, sizeof(Fraig_Node_t *), 
            (int (*)(const void *, const void *)) Fraig_NodeVecCompareNumbers );
}

Here is the call graph for this function:

Fraig_NodeVecSortByRefCount()

void Fraig_NodeVecSortByRefCount

(

Fraig_NodeVec_t *

p

)

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

Synopsis [Sorting the entries by their integer value.]

Description []

SideEffects []

SeeAlso []

Definition at line 539 of file fraigVec.c.

{
    qsort( (void *)p->pArray, (size_t)p->nSize, sizeof(Fraig_Node_t *), 
            (int (*)(const void *, const void *)) Fraig_NodeVecCompareRefCounts );
}

Here is the call graph for this function:

Fraig_NodeVecWriteEntry()

void Fraig_NodeVecWriteEntry	(	Fraig_NodeVec_t *	p,
		int	i,
		Fraig_Node_t *	Entry )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 370 of file fraigVec.c.

{
    assert( i >= 0 && i < p->nSize );
    p->pArray[i] = Entry;
}