fraigTable.c File Reference

#include "fraigInt.h"

Include dependency graph for fraigTable.c:

Go to the source code of this file.

Functions
Fraig_HashTable_t *	Fraig_HashTableCreate (int nSize)
	FUNCTION DEFINITIONS ///.
void	Fraig_HashTableFree (Fraig_HashTable_t *p)
int	Fraig_HashTableLookupS (Fraig_Man_t *pMan, Fraig_Node_t *p1, Fraig_Node_t *p2, Fraig_Node_t **ppNodeRes)
Fraig_Node_t *	Fraig_HashTableLookupF (Fraig_Man_t *pMan, Fraig_Node_t *pNode)
Fraig_Node_t *	Fraig_HashTableLookupF0 (Fraig_Man_t *pMan, Fraig_Node_t *pNode)
void	Fraig_HashTableInsertF0 (Fraig_Man_t *pMan, Fraig_Node_t *pNode)
int	Fraig_CompareSimInfo (Fraig_Node_t *pNode1, Fraig_Node_t *pNode2, int iWordLast, int fUseRand)
int	Fraig_FindFirstDiff (Fraig_Node_t *pNode1, Fraig_Node_t *pNode2, int fCompl, int iWordLast, int fUseRand)
int	Fraig_CompareSimInfoUnderMask (Fraig_Node_t *pNode1, Fraig_Node_t *pNode2, int iWordLast, int fUseRand, unsigned *puMask)
void	Fraig_CollectXors (Fraig_Node_t *pNode1, Fraig_Node_t *pNode2, int iWordLast, int fUseRand, unsigned *puMask)
void	Fraig_TablePrintStatsS (Fraig_Man_t *pMan)
void	Fraig_TablePrintStatsF (Fraig_Man_t *pMan)
void	Fraig_TablePrintStatsF0 (Fraig_Man_t *pMan)
int	Fraig_TableRehashF0 (Fraig_Man_t *pMan, int fLinkEquiv)

Function Documentation

Fraig_CollectXors()

void Fraig_CollectXors	(	Fraig_Node_t *	pNode1,
		Fraig_Node_t *	pNode2,
		int	iWordLast,
		int	fUseRand,
		unsigned *	puMask )

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

Synopsis [Compares two pieces of simulation info.]

Description [Returns 1 if they are equal.]

SideEffects []

SeeAlso []

Definition at line 478 of file fraigTable.c.

{
    unsigned * pSims1, * pSims2;
    int i;
    assert( !Fraig_IsComplement(pNode1) );
    assert( !Fraig_IsComplement(pNode2) );
    // get hold of simulation info
    pSims1 = fUseRand? pNode1->puSimR : pNode1->puSimD;
    pSims2 = fUseRand? pNode2->puSimR : pNode2->puSimD;    
    // check the simulation info
    for ( i = 0; i < iWordLast; i++ )
        puMask[i] = ( pSims1[i] ^ pSims2[i] );
}

Fraig_CompareSimInfo()

int Fraig_CompareSimInfo	(	Fraig_Node_t *	pNode1,
		Fraig_Node_t *	pNode2,
		int	iWordLast,
		int	fUseRand )

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

Synopsis [Compares two pieces of simulation info.]

Description [Returns 1 if they are equal.]

SideEffects []

SeeAlso []

Definition at line 351 of file fraigTable.c.

{
    int i;
    assert( !Fraig_IsComplement(pNode1) );
    assert( !Fraig_IsComplement(pNode2) );
    if ( fUseRand )
    {
        // if their signatures differ, skip
        if ( pNode1->uHashR != pNode2->uHashR )
            return 0;
        // check the simulation info
        for ( i = 0; i < iWordLast; i++ )
            if ( pNode1->puSimR[i] != pNode2->puSimR[i] )
                return 0;
    }
    else
    {
        // if their signatures differ, skip
        if ( pNode1->uHashD != pNode2->uHashD )
            return 0;
        // check the simulation info
        for ( i = 0; i < iWordLast; i++ )
            if ( pNode1->puSimD[i] != pNode2->puSimD[i] )
                return 0;
    }
    return 1;
}

Here is the caller graph for this function:

Fraig_CompareSimInfoUnderMask()

int Fraig_CompareSimInfoUnderMask	(	Fraig_Node_t *	pNode1,
		Fraig_Node_t *	pNode2,
		int	iWordLast,
		int	fUseRand,
		unsigned *	puMask )

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

Synopsis [Compares two pieces of simulation info.]

Description [Returns 1 if they are equal.]

SideEffects []

SeeAlso []

Definition at line 451 of file fraigTable.c.

{
    unsigned * pSims1, * pSims2;
    int i;
    assert( !Fraig_IsComplement(pNode1) );
    assert( !Fraig_IsComplement(pNode2) );
    // get hold of simulation info
    pSims1 = fUseRand? pNode1->puSimR : pNode1->puSimD;
    pSims2 = fUseRand? pNode2->puSimR : pNode2->puSimD;    
    // check the simulation info
    for ( i = 0; i < iWordLast; i++ )
        if ( (pSims1[i] & puMask[i]) != (pSims2[i] & puMask[i]) )
            return 0;
    return 1;
}

Fraig_FindFirstDiff()

int Fraig_FindFirstDiff	(	Fraig_Node_t *	pNode1,
		Fraig_Node_t *	pNode2,
		int	fCompl,
		int	iWordLast,
		int	fUseRand )

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

Synopsis [Find the number of the different pattern.]

Description [Returns -1 if there is no such pattern]

SideEffects []

SeeAlso []

Definition at line 390 of file fraigTable.c.

{
    int i, v;
    assert( !Fraig_IsComplement(pNode1) );
    assert( !Fraig_IsComplement(pNode2) );
    // take into account possible internal complementation
    fCompl ^= pNode1->fInv;
    fCompl ^= pNode2->fInv;
    // find the pattern
    if ( fCompl )
    {
        if ( fUseRand )
        {
            for ( i = 0; i < iWordLast; i++ )
                if ( pNode1->puSimR[i] != ~pNode2->puSimR[i] )
                    for ( v = 0; v < 32; v++ )
                        if ( (pNode1->puSimR[i] ^ ~pNode2->puSimR[i]) & (1 << v) )
                            return i * 32 + v;
        }
        else
        {
            for ( i = 0; i < iWordLast; i++ )
                if ( pNode1->puSimD[i] !=  ~pNode2->puSimD[i] )
                    for ( v = 0; v < 32; v++ )
                        if ( (pNode1->puSimD[i] ^ ~pNode2->puSimD[i]) & (1 << v) )
                            return i * 32 + v;
        }
    }
    else
    {
        if ( fUseRand )
        {
            for ( i = 0; i < iWordLast; i++ )
                if ( pNode1->puSimR[i] != pNode2->puSimR[i] )
                    for ( v = 0; v < 32; v++ )
                        if ( (pNode1->puSimR[i] ^ pNode2->puSimR[i]) & (1 << v) )
                            return i * 32 + v;
        }
        else
        {
            for ( i = 0; i < iWordLast; i++ )
                if ( pNode1->puSimD[i] !=  pNode2->puSimD[i] )
                    for ( v = 0; v < 32; v++ )
                        if ( (pNode1->puSimD[i] ^ pNode2->puSimD[i]) & (1 << v) )
                            return i * 32 + v;
        }
    }
    return -1;
}

Here is the caller graph for this function:

Fraig_HashTableCreate()

Fraig_HashTable_t * Fraig_HashTableCreate

(

int

nSize

)

FUNCTION DEFINITIONS ///.

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

Synopsis [Allocates the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file fraigTable.c.

{
    Fraig_HashTable_t * p;
    // allocate the table
    p = ABC_ALLOC( Fraig_HashTable_t, 1 );
    memset( p, 0, sizeof(Fraig_HashTable_t) );
    // allocate and clean the bins
    p->nBins = Abc_PrimeCudd(nSize);
    p->pBins = ABC_ALLOC( Fraig_Node_t *, p->nBins );
    memset( p->pBins, 0, sizeof(Fraig_Node_t *) * p->nBins );
    return p;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fraig_HashTableFree()

void Fraig_HashTableFree

(

Fraig_HashTable_t *

p

)

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

Synopsis [Deallocates the supergate hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 70 of file fraigTable.c.

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

Here is the caller graph for this function:

Fraig_HashTableInsertF0()

void Fraig_HashTableInsertF0	(	Fraig_Man_t *	pMan,
		Fraig_Node_t *	pNode )

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

Synopsis [Insert the entry in the functional hash table.]

Description [Unconditionally add the node to the corresponding linked list in the table.]

SideEffects []

SeeAlso []

Definition at line 237 of file fraigTable.c.

{
    Fraig_HashTable_t * p = pMan->pTableF0;
    unsigned Key = pNode->uHashD % p->nBins;
 
    pNode->pNextF = p->pBins[Key];
    p->pBins[Key] = pNode;
    p->nEntries++;
}

Fraig_HashTableLookupF()

Fraig_Node_t * Fraig_HashTableLookupF	(	Fraig_Man_t *	pMan,
		Fraig_Node_t *	pNode )

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

Synopsis [Insert the entry in the functional hash table.]

Description [If the entry with the same key exists, return it right away.
If the entry with the same key does not exists, inserts it and returns NULL. ]

SideEffects []

SeeAlso []

Definition at line 136 of file fraigTable.c.

{
    Fraig_HashTable_t * p = pMan->pTableF;
    Fraig_Node_t * pEnt, * pEntD;
    unsigned Key;
 
    // go through the hash table entries
    Key = pNode->uHashR % p->nBins;
    Fraig_TableBinForEachEntryF( p->pBins[Key], pEnt )
    {
        // if their simulation info differs, skip
        if ( !Fraig_CompareSimInfo( pNode, pEnt, pMan->nWordsRand, 1 ) )
            continue;
        // equivalent up to the complement
        Fraig_TableBinForEachEntryD( pEnt, pEntD )
        {
            // if their simulation info differs, skip
            if ( !Fraig_CompareSimInfo( pNode, pEntD, pMan->iWordStart, 0 ) )
                continue;
            // found a simulation-equivalent node
            return pEntD; 
        }
        // did not find a simulation equivalent node
        // add the node to the corresponding linked list
        pNode->pNextD = pEnt->pNextD;
        pEnt->pNextD  = pNode;
        // return NULL, because there is no functional equivalence in this case
        return NULL;
    }
 
    // check if it is a good time for table resizing
    if ( p->nEntries >= 2 * p->nBins )
    {
        Fraig_TableResizeF( p, 1 );
        Key = pNode->uHashR % p->nBins;
    }
 
    // add the node to the corresponding linked list in the table
    pNode->pNextF = p->pBins[Key];
    p->pBins[Key] = pNode;
    p->nEntries++;
    // return NULL, because there is no functional equivalence in this case
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fraig_HashTableLookupF0()

Fraig_Node_t * Fraig_HashTableLookupF0	(	Fraig_Man_t *	pMan,
		Fraig_Node_t *	pNode )

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

Synopsis [Insert the entry in the functional hash table.]

Description [If the entry with the same key exists, return it right away.
If the entry with the same key does not exists, inserts it and returns NULL. ]

SideEffects []

SeeAlso []

Definition at line 193 of file fraigTable.c.

{
    Fraig_HashTable_t * p = pMan->pTableF0;
    Fraig_Node_t * pEnt;
    unsigned Key;
 
    // go through the hash table entries
    Key = pNode->uHashD % p->nBins;
    Fraig_TableBinForEachEntryF( p->pBins[Key], pEnt )
    {
        // if their simulation info differs, skip
        if ( !Fraig_CompareSimInfo( pNode, pEnt, pMan->iWordStart, 0 ) )
            continue;
        // found a simulation-equivalent node
        return pEnt; 
    }
 
    // check if it is a good time for table resizing
    if ( p->nEntries >= 2 * p->nBins )
    {
        Fraig_TableResizeF( p, 0 );
        Key = pNode->uHashD % p->nBins;
    }
 
    // add the node to the corresponding linked list in the table
    pNode->pNextF = p->pBins[Key];
    p->pBins[Key] = pNode;
    p->nEntries++;
    // return NULL, because there is no functional equivalence in this case
    return NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fraig_HashTableLookupS()

int Fraig_HashTableLookupS	(	Fraig_Man_t *	pMan,
		Fraig_Node_t *	p1,
		Fraig_Node_t *	p2,
		Fraig_Node_t **	ppNodeRes )

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

Synopsis [Looks up an entry in the structural hash table.]

Description [If the entry with the same children does not exists, creates it, inserts it into the table, and returns 0. If the entry with the same children exists, finds it, and return 1. In both cases, the new/old entry is returned in ppNodeRes.]

SideEffects []

SeeAlso []

Definition at line 90 of file fraigTable.c.

{
    Fraig_HashTable_t * p = pMan->pTableS;
    Fraig_Node_t * pEnt;
    unsigned Key;
 
    // order the arguments
    if ( Fraig_Regular(p1)->Num > Fraig_Regular(p2)->Num )
        pEnt = p1, p1 = p2, p2 = pEnt;
 
    Key = Fraig_HashKey2( p1, p2, p->nBins );
    Fraig_TableBinForEachEntryS( p->pBins[Key], pEnt )
        if ( pEnt->p1 == p1 && pEnt->p2 == p2 )
        {
            *ppNodeRes = pEnt;
            return 1;
        }
    // check if it is a good time for table resizing
    if ( p->nEntries >= 2 * p->nBins )
    {
        Fraig_TableResizeS( p );
        Key = Fraig_HashKey2( p1, p2, p->nBins );
    }
    // create the new node
    pEnt = Fraig_NodeCreate( pMan, p1, p2 );
    // add the node to the corresponding linked list in the table
    pEnt->pNextS = p->pBins[Key];
    p->pBins[Key] = pEnt;
    *ppNodeRes = pEnt;
    p->nEntries++;
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Fraig_TablePrintStatsF()

void Fraig_TablePrintStatsF

(

Fraig_Man_t *

pMan

)

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

Synopsis [Prints stats of the structural table.]

Description []

SideEffects []

SeeAlso []

Definition at line 537 of file fraigTable.c.

{
    Fraig_HashTable_t * pT = pMan->pTableF;
    Fraig_Node_t * pNode;
    int i, Counter;
 
    printf( "Functional table. Table size = %d. Number of entries = %d.\n", pT->nBins, pT->nEntries );
    for ( i = 0; i < pT->nBins; i++ )
    {
        Counter = 0;
        Fraig_TableBinForEachEntryF( pT->pBins[i], pNode )
            Counter++;
        if ( Counter > 1 )
            printf( "{%d} ", Counter );
    }
    printf( "\n" );
}

Fraig_TablePrintStatsF0()

void Fraig_TablePrintStatsF0

(

Fraig_Man_t *

pMan

)

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

Synopsis [Prints stats of the structural table.]

Description []

SideEffects []

SeeAlso []

Definition at line 566 of file fraigTable.c.

{
    Fraig_HashTable_t * pT = pMan->pTableF0;
    Fraig_Node_t * pNode;
    int i, Counter;
 
    printf( "Zero-node table. Table size = %d. Number of entries = %d.\n", pT->nBins, pT->nEntries );
    for ( i = 0; i < pT->nBins; i++ )
    {
        Counter = 0;
        Fraig_TableBinForEachEntryF( pT->pBins[i], pNode )
            Counter++;
        if ( Counter == 0 )
            continue;
/*
        printf( "\nBin = %4d :  Number of entries = %4d\n", i, Counter );
        Fraig_TableBinForEachEntryF( pT->pBins[i], pNode )
            printf( "Node %5d. Hash = %10d.\n", pNode->Num, pNode->uHashD );
*/
    }
    printf( "\n" );
}

Fraig_TablePrintStatsS()

void Fraig_TablePrintStatsS

(

Fraig_Man_t *

pMan

)

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

Synopsis [Prints stats of the structural table.]

Description []

SideEffects []

SeeAlso []

Definition at line 504 of file fraigTable.c.

{
    Fraig_HashTable_t * pT = pMan->pTableS;
    Fraig_Node_t * pNode;
    int i, Counter;
 
    printf( "Structural table. Table size = %d. Number of entries = %d.\n", pT->nBins, pT->nEntries );
    for ( i = 0; i < pT->nBins; i++ )
    {
        Counter = 0;
        Fraig_TableBinForEachEntryS( pT->pBins[i], pNode )
            Counter++;
        if ( Counter > 1 )
        {
            printf( "%d ", Counter );
            if ( Counter > 50 )
                printf( "{%d} ", i );
        }
    }
    printf( "\n" );
}

Fraig_TableRehashF0()

int Fraig_TableRehashF0	(	Fraig_Man_t *	pMan,
		int	fLinkEquiv )

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

Synopsis [Rehashes the table after the simulation info has changed.]

Description [Assumes that the hash values have been updated after performing additional simulation. Rehashes the table using the new hash values. Uses pNextF to link the entries in the bins. Uses pNextD to link the entries with identical hash values. Returns 1 if the identical entries have been found. Note that identical hash values may mean that the simulation data is different.]

SideEffects []

SeeAlso []

Definition at line 604 of file fraigTable.c.

{
    Fraig_HashTable_t * pT = pMan->pTableF0;
    Fraig_Node_t ** pBinsNew;
    Fraig_Node_t * pEntF, * pEntF2, * pEnt, * pEntD2, * pEntN;
    int ReturnValue, Counter, i;
    unsigned Key;
 
    // allocate a new array of bins
    pBinsNew = ABC_ALLOC( Fraig_Node_t *, pT->nBins );
    memset( pBinsNew, 0, sizeof(Fraig_Node_t *) * pT->nBins );
 
    // rehash the entries in the table
    // go through all the nodes in the F-lists (and possible in D-lists, if used)
    Counter = 0;
    ReturnValue = 0;
    for ( i = 0; i < pT->nBins; i++ )
        Fraig_TableBinForEachEntrySafeF( pT->pBins[i], pEntF, pEntF2 )
        Fraig_TableBinForEachEntrySafeD( pEntF, pEnt, pEntD2 )
        {
            // decide where to put entry pEnt
            Key = pEnt->uHashD % pT->nBins;
            if ( fLinkEquiv )
            {
                // go through the entries in the new bin
                Fraig_TableBinForEachEntryF( pBinsNew[Key], pEntN )
                {
                    // if they have different values skip
                    if ( pEnt->uHashD != pEntN->uHashD )
                        continue;
                    // they have the same hash value, add pEnt to the D-list pEnt3
                    pEnt->pNextD  = pEntN->pNextD;
                    pEntN->pNextD = pEnt;
                    ReturnValue = 1;
                    Counter++;
                    break;
                }
                if ( pEntN != NULL ) // already linked
                    continue;
                // we did not find equal entry
            }
            // link the new entry
            pEnt->pNextF  = pBinsNew[Key];
            pBinsNew[Key] = pEnt;
            pEnt->pNextD  = NULL;
            Counter++;
        }
    assert( Counter == pT->nEntries );
    // replace the table and the parameters
    ABC_FREE( pT->pBins );
    pT->pBins = pBinsNew;
    return ReturnValue;
}

Here is the call graph for this function:

Here is the caller graph for this function: