| /**CFile**************************************************************** |
| |
| FileName [fraigTable.c] |
| |
| PackageName [FRAIG: Functionally reduced AND-INV graphs.] |
| |
| Synopsis [Structural and functional hash tables.] |
| |
| Author [Alan Mishchenko <alanmi@eecs.berkeley.edu>] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 2.0. Started - October 1, 2004] |
| |
| Revision [$Id: fraigTable.c,v 1.7 2005/07/08 01:01:34 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "fraigInt.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| static void Fraig_TableResizeS( Fraig_HashTable_t * p ); |
| static void Fraig_TableResizeF( Fraig_HashTable_t * p, int fUseSimR ); |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Allocates the hash table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Fraig_HashTable_t * Fraig_HashTableCreate( int nSize ) |
| { |
| 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; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Deallocates the supergate hash table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fraig_HashTableFree( Fraig_HashTable_t * p ) |
| { |
| ABC_FREE( p->pBins ); |
| ABC_FREE( p ); |
| } |
| |
| /**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 [] |
| |
| ***********************************************************************/ |
| int Fraig_HashTableLookupS( Fraig_Man_t * pMan, Fraig_Node_t * p1, Fraig_Node_t * p2, Fraig_Node_t ** ppNodeRes ) |
| { |
| 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; |
| } |
| |
| |
| /**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 [] |
| |
| ***********************************************************************/ |
| Fraig_Node_t * Fraig_HashTableLookupF( Fraig_Man_t * pMan, Fraig_Node_t * pNode ) |
| { |
| 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; |
| } |
| |
| /**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 [] |
| |
| ***********************************************************************/ |
| Fraig_Node_t * Fraig_HashTableLookupF0( Fraig_Man_t * pMan, Fraig_Node_t * pNode ) |
| { |
| 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; |
| } |
| |
| /**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 [] |
| |
| ***********************************************************************/ |
| void Fraig_HashTableInsertF0( Fraig_Man_t * pMan, Fraig_Node_t * pNode ) |
| { |
| Fraig_HashTable_t * p = pMan->pTableF0; |
| unsigned Key = pNode->uHashD % p->nBins; |
| |
| pNode->pNextF = p->pBins[Key]; |
| p->pBins[Key] = pNode; |
| p->nEntries++; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Resizes the table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fraig_TableResizeS( Fraig_HashTable_t * p ) |
| { |
| Fraig_Node_t ** pBinsNew; |
| Fraig_Node_t * pEnt, * pEnt2; |
| int nBinsNew, Counter, i; |
| abctime clk; |
| unsigned Key; |
| |
| clk = Abc_Clock(); |
| // get the new table size |
| nBinsNew = Abc_PrimeCudd(2 * p->nBins); |
| // allocate a new array |
| pBinsNew = ABC_ALLOC( Fraig_Node_t *, nBinsNew ); |
| memset( pBinsNew, 0, sizeof(Fraig_Node_t *) * nBinsNew ); |
| // rehash the entries from the old table |
| Counter = 0; |
| for ( i = 0; i < p->nBins; i++ ) |
| Fraig_TableBinForEachEntrySafeS( p->pBins[i], pEnt, pEnt2 ) |
| { |
| Key = Fraig_HashKey2( pEnt->p1, pEnt->p2, nBinsNew ); |
| pEnt->pNextS = pBinsNew[Key]; |
| pBinsNew[Key] = pEnt; |
| Counter++; |
| } |
| assert( Counter == p->nEntries ); |
| // printf( "Increasing the structural table size from %6d to %6d. ", p->nBins, nBinsNew ); |
| // ABC_PRT( "Time", Abc_Clock() - clk ); |
| // replace the table and the parameters |
| ABC_FREE( p->pBins ); |
| p->pBins = pBinsNew; |
| p->nBins = nBinsNew; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Resizes the table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fraig_TableResizeF( Fraig_HashTable_t * p, int fUseSimR ) |
| { |
| Fraig_Node_t ** pBinsNew; |
| Fraig_Node_t * pEnt, * pEnt2; |
| int nBinsNew, Counter, i; |
| abctime clk; |
| unsigned Key; |
| |
| clk = Abc_Clock(); |
| // get the new table size |
| nBinsNew = Abc_PrimeCudd(2 * p->nBins); |
| // allocate a new array |
| pBinsNew = ABC_ALLOC( Fraig_Node_t *, nBinsNew ); |
| memset( pBinsNew, 0, sizeof(Fraig_Node_t *) * nBinsNew ); |
| // rehash the entries from the old table |
| Counter = 0; |
| for ( i = 0; i < p->nBins; i++ ) |
| Fraig_TableBinForEachEntrySafeF( p->pBins[i], pEnt, pEnt2 ) |
| { |
| if ( fUseSimR ) |
| Key = pEnt->uHashR % nBinsNew; |
| else |
| Key = pEnt->uHashD % nBinsNew; |
| pEnt->pNextF = pBinsNew[Key]; |
| pBinsNew[Key] = pEnt; |
| Counter++; |
| } |
| assert( Counter == p->nEntries ); |
| // printf( "Increasing the functional table size from %6d to %6d. ", p->nBins, nBinsNew ); |
| // ABC_PRT( "Time", Abc_Clock() - clk ); |
| // replace the table and the parameters |
| ABC_FREE( p->pBins ); |
| p->pBins = pBinsNew; |
| p->nBins = nBinsNew; |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compares two pieces of simulation info.] |
| |
| Description [Returns 1 if they are equal.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Fraig_CompareSimInfo( Fraig_Node_t * pNode1, Fraig_Node_t * pNode2, int iWordLast, int fUseRand ) |
| { |
| 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; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Find the number of the different pattern.] |
| |
| Description [Returns -1 if there is no such pattern] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Fraig_FindFirstDiff( Fraig_Node_t * pNode1, Fraig_Node_t * pNode2, int fCompl, int iWordLast, int fUseRand ) |
| { |
| 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; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compares two pieces of simulation info.] |
| |
| Description [Returns 1 if they are equal.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| int Fraig_CompareSimInfoUnderMask( Fraig_Node_t * pNode1, Fraig_Node_t * pNode2, int iWordLast, int fUseRand, unsigned * puMask ) |
| { |
| 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; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Compares two pieces of simulation info.] |
| |
| Description [Returns 1 if they are equal.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fraig_CollectXors( Fraig_Node_t * pNode1, Fraig_Node_t * pNode2, int iWordLast, int fUseRand, unsigned * puMask ) |
| { |
| 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] ); |
| } |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prints stats of the structural table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fraig_TablePrintStatsS( Fraig_Man_t * pMan ) |
| { |
| 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" ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prints stats of the structural table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fraig_TablePrintStatsF( Fraig_Man_t * pMan ) |
| { |
| 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" ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Prints stats of the structural table.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Fraig_TablePrintStatsF0( Fraig_Man_t * pMan ) |
| { |
| 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" ); |
| } |
| |
| /**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 [] |
| |
| ***********************************************************************/ |
| int Fraig_TableRehashF0( Fraig_Man_t * pMan, int fLinkEquiv ) |
| { |
| 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; |
| } |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
