FxchSCHashTable.c File Reference

#include "Fxch.h"

Include dependency graph for FxchSCHashTable.c:

Go to the source code of this file.

Functions
Fxch_SCHashTable_t *	Fxch_SCHashTableCreate (Fxch_Man_t *pFxchMan, int nEntries)
void	Fxch_SCHashTableDelete (Fxch_SCHashTable_t *pSCHashTable)
int	Fxch_SCHashTableInsert (Fxch_SCHashTable_t *pSCHashTable, Vec_Wec_t *vCubes, uint32_t SubCubeID, uint32_t iCube, uint32_t iLit0, uint32_t iLit1, char fUpdate)
int	Fxch_SCHashTableRemove (Fxch_SCHashTable_t *pSCHashTable, Vec_Wec_t *vCubes, uint32_t SubCubeID, uint32_t iCube, uint32_t iLit0, uint32_t iLit1, char fUpdate)
unsigned int	Fxch_SCHashTableMemory (Fxch_SCHashTable_t *pHashTable)
void	Fxch_SCHashTablePrint (Fxch_SCHashTable_t *pHashTable)

Function Documentation

Fxch_SCHashTableCreate()

Fxch_SCHashTable_t * Fxch_SCHashTableCreate	(	Fxch_Man_t *	pFxchMan,
		int	nEntries )

Definition at line 93 of file FxchSCHashTable.c.

{
    Fxch_SCHashTable_t* pSCHashTable = ABC_CALLOC( Fxch_SCHashTable_t, 1 );
    int nBits = Abc_Base2Log( nEntries + 1 );
 
 
    pSCHashTable->pFxchMan = pFxchMan;
    pSCHashTable->SizeMask = (1 << nBits) - 1;
    pSCHashTable->pBins = ABC_CALLOC( Fxch_SCHashTable_Entry_t, pSCHashTable->SizeMask + 1 );
 
    return pSCHashTable;
}

Here is the caller graph for this function:

Fxch_SCHashTableDelete()

void Fxch_SCHashTableDelete

(

Fxch_SCHashTable_t *

pSCHashTable

)

Definition at line 107 of file FxchSCHashTable.c.

{
    unsigned i;
    for ( i = 0; i <= pSCHashTable->SizeMask; i++ )
        ABC_FREE( pSCHashTable->pBins[i].vSCData );
    Vec_IntErase( &pSCHashTable->vSubCube0 );
    Vec_IntErase( &pSCHashTable->vSubCube1 );
    ABC_FREE( pSCHashTable->pBins );
    ABC_FREE( pSCHashTable );
}

Here is the caller graph for this function:

Fxch_SCHashTableInsert()

int Fxch_SCHashTableInsert	(	Fxch_SCHashTable_t *	pSCHashTable,
		Vec_Wec_t *	vCubes,
		uint32_t	SubCubeID,
		uint32_t	iCube,
		uint32_t	iLit0,
		uint32_t	iLit1,
		char	fUpdate )

Definition at line 179 of file FxchSCHashTable.c.

{
    int iNewEntry;
    int Pairs = 0;
    uint32_t BinID;
    Fxch_SCHashTable_Entry_t* pBin;
    Fxch_SubCube_t* pNewEntry;
    int iEntry;
 
    MurmurHash3_x86_32( ( void* ) &SubCubeID, sizeof( int ), 0x9747b28c, &BinID);
    pBin = Fxch_SCHashTableBin( pSCHashTable, BinID );
 
    if ( pBin->vSCData == NULL )
    {
        pBin->vSCData = ABC_CALLOC( Fxch_SubCube_t, 16 );
        pBin->Size = 0;
        pBin->Cap = 16;
    }
    else if ( pBin->Size == pBin->Cap )
    {
        assert(pBin->Cap <= 0xAAAA);
        pBin->Cap = ( pBin->Cap >> 1 ) * 3;
        pBin->vSCData = ABC_REALLOC( Fxch_SubCube_t, pBin->vSCData, pBin->Cap );
    }
 
    iNewEntry = pBin->Size++;
    pBin->vSCData[iNewEntry].Id = SubCubeID;
    pBin->vSCData[iNewEntry].iCube = iCube;
    pBin->vSCData[iNewEntry].iLit0 = iLit0;
    pBin->vSCData[iNewEntry].iLit1 = iLit1;
    pSCHashTable->nEntries++;
 
    if ( pBin->Size == 1 )
        return 0;
 
    pNewEntry = &( pBin->vSCData[iNewEntry] );
    for ( iEntry = 0; iEntry < (int)pBin->Size - 1; iEntry++ )
    {
        Fxch_SubCube_t* pEntry = &( pBin->vSCData[iEntry] );
        int* pOutputID0 = Vec_IntEntryP( pSCHashTable->pFxchMan->vOutputID, pEntry->iCube * pSCHashTable->pFxchMan->nSizeOutputID );
        int* pOutputID1 = Vec_IntEntryP( pSCHashTable->pFxchMan->vOutputID, pNewEntry->iCube * pSCHashTable->pFxchMan->nSizeOutputID );
        int Result = 0;
        int Base;
        int iNewDiv = -1, i, z;
 
        if ( (pEntry->iLit1 != 0 && pNewEntry->iLit1 == 0) || (pEntry->iLit1 == 0 && pNewEntry->iLit1 != 0)  )
            continue;
 
        if ( !Fxch_SCHashTableEntryCompare( pSCHashTable, vCubes, pEntry, pNewEntry ) )
            continue;
 
        if ( ( pEntry->iLit0 == 0 ) || ( pNewEntry->iLit0 == 0 ) )
        {
            Vec_Int_t* vCube0 = Fxch_ManGetCube( pSCHashTable->pFxchMan, pEntry->iCube ),
                     * vCube1 = Fxch_ManGetCube( pSCHashTable->pFxchMan, pNewEntry->iCube );
 
            if ( Vec_IntSize( vCube0 ) > Vec_IntSize( vCube1 ) )
            {
                Vec_IntPush( pSCHashTable->pFxchMan->vSCC, pEntry->iCube );
                Vec_IntPush( pSCHashTable->pFxchMan->vSCC, pNewEntry->iCube );
            }
            else
            {
                Vec_IntPush( pSCHashTable->pFxchMan->vSCC, pNewEntry->iCube );
                Vec_IntPush( pSCHashTable->pFxchMan->vSCC, pEntry->iCube );
            }
 
            continue;
        }
 
        Base = Fxch_DivCreate( pSCHashTable->pFxchMan, pEntry, pNewEntry );
 
        if ( Base < 0 )
            continue;
 
        for ( i = 0; i < pSCHashTable->pFxchMan->nSizeOutputID; i++ )
            Result += Fxch_CountOnes( pOutputID0[i] & pOutputID1[i] );
 
        for ( z = 0; z < Result; z++ )
            iNewDiv = Fxch_DivAdd( pSCHashTable->pFxchMan, fUpdate, 0, Base );
 
        Vec_WecPush( pSCHashTable->pFxchMan->vDivCubePairs, iNewDiv, pEntry->iCube );
        Vec_WecPush( pSCHashTable->pFxchMan->vDivCubePairs, iNewDiv, pNewEntry->iCube );
 
        Pairs++;
    }
 
    return Pairs;
}

Here is the call graph for this function:

Fxch_SCHashTableMemory()

unsigned int Fxch_SCHashTableMemory

(

Fxch_SCHashTable_t *

pHashTable

)

Definition at line 362 of file FxchSCHashTable.c.

{
    unsigned int Memory = sizeof ( Fxch_SCHashTable_t );
 
    Memory += sizeof( Fxch_SubCube_t ) * ( pHashTable->SizeMask + 1 );
 
    return Memory;
}

Here is the caller graph for this function:

Fxch_SCHashTablePrint()

void Fxch_SCHashTablePrint

(

Fxch_SCHashTable_t *

pHashTable

)

Definition at line 371 of file FxchSCHashTable.c.

{
    int Memory;
    printf( "SubCube Hash Table at %p\n", ( void* )pHashTable );
    printf("%20s %20s\n", "nEntries",
                          "Memory Usage (MB)" );
 
    Memory = Fxch_SCHashTableMemory( pHashTable );
    printf("%20d %18.2f\n", pHashTable->nEntries,
                            ( ( double ) Memory / 1048576 ) );
}

Here is the call graph for this function:

Fxch_SCHashTableRemove()

int Fxch_SCHashTableRemove	(	Fxch_SCHashTable_t *	pSCHashTable,
		Vec_Wec_t *	vCubes,
		uint32_t	SubCubeID,
		uint32_t	iCube,
		uint32_t	iLit0,
		uint32_t	iLit1,
		char	fUpdate )

Definition at line 275 of file FxchSCHashTable.c.

{
    int iEntry;
    int Pairs = 0;
    uint32_t BinID;
    Fxch_SCHashTable_Entry_t* pBin;
    Fxch_SubCube_t* pEntry;
    int idx;
 
    MurmurHash3_x86_32( ( void* ) &SubCubeID, sizeof( int ), 0x9747b28c, &BinID);
 
    pBin = Fxch_SCHashTableBin( pSCHashTable, BinID );
 
    if ( pBin->Size == 1 )
    {
        pBin->Size = 0;
        return 0;
    }
 
    for ( iEntry = 0; iEntry < (int)pBin->Size; iEntry++ )
        if ( pBin->vSCData[iEntry].iCube == iCube )
            break;
 
    assert( ( iEntry != (int)pBin->Size ) && ( pBin->Size != 0 ) );
 
    pEntry = &( pBin->vSCData[iEntry] );
    for ( idx = 0; idx < (int)pBin->Size; idx++ )
    if ( idx != iEntry )
    {
        int Base,
            iDiv = -1;
 
        int i, z,
            iCube0,
            iCube1;
 
        Fxch_SubCube_t* pNextEntry = &( pBin->vSCData[idx] );
        Vec_Int_t* vDivCubePairs;
        int* pOutputID0 = Vec_IntEntryP( pSCHashTable->pFxchMan->vOutputID, pEntry->iCube * pSCHashTable->pFxchMan->nSizeOutputID );
        int* pOutputID1 = Vec_IntEntryP( pSCHashTable->pFxchMan->vOutputID, pNextEntry->iCube * pSCHashTable->pFxchMan->nSizeOutputID );
        int Result = 0;
 
        if ( (pEntry->iLit1 != 0 && pNextEntry->iLit1 == 0) || (pEntry->iLit1 == 0 && pNextEntry->iLit1 != 0)  )
            continue;
 
        if ( !Fxch_SCHashTableEntryCompare( pSCHashTable, vCubes, pEntry, pNextEntry )
             || pEntry->iLit0 == 0
             || pNextEntry->iLit0 == 0 )
            continue;
 
        Base = Fxch_DivCreate( pSCHashTable->pFxchMan, pNextEntry, pEntry );
 
        if ( Base < 0 )
            continue;
 
        for ( i = 0; i < pSCHashTable->pFxchMan->nSizeOutputID; i++ )
            Result += Fxch_CountOnes( pOutputID0[i] & pOutputID1[i] );
 
        for ( z = 0; z < Result; z++ )
            iDiv = Fxch_DivRemove( pSCHashTable->pFxchMan, fUpdate, 0, Base );
 
        vDivCubePairs = Vec_WecEntry( pSCHashTable->pFxchMan->vDivCubePairs, iDiv );
        Vec_IntForEachEntryDouble( vDivCubePairs, iCube0, iCube1, i )
            if ( ( iCube0 == (int)pNextEntry->iCube && iCube1 == (int)pEntry->iCube )  ||
                 ( iCube0 == (int)pEntry->iCube && iCube1 == (int)pNextEntry->iCube ) )
            {
                Vec_IntDrop( vDivCubePairs, i+1 );
                Vec_IntDrop( vDivCubePairs, i );
            }
        if ( Vec_IntSize( vDivCubePairs ) == 0 )
            Vec_IntErase( vDivCubePairs );
 
        Pairs++;
    }
 
    memmove(pBin->vSCData + iEntry, pBin->vSCData + iEntry + 1, (pBin->Size - iEntry - 1) * sizeof(*pBin->vSCData));
    pBin->Size -= 1;
 
    return Pairs;
}

Here is the call graph for this function: