diff options
Diffstat (limited to 'src/aig/dar/darTable.c')
| -rw-r--r-- | src/aig/dar/darTable.c | 262 |
1 files changed, 262 insertions, 0 deletions
diff --git a/src/aig/dar/darTable.c b/src/aig/dar/darTable.c new file mode 100644 index 00000000..8b4bfaf3 --- /dev/null +++ b/src/aig/dar/darTable.c @@ -0,0 +1,262 @@ +/**CFile**************************************************************** + + FileName [darTable.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [DAG-aware AIG rewriting.] + + Synopsis [Structural hashing table.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - April 28, 2007.] + + Revision [$Id: darTable.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "dar.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// hashing the node +static unsigned long Dar_Hash( Dar_Obj_t * pObj, int TableSize ) +{ + unsigned long Key = Dar_ObjIsExor(pObj) * 1699; + Key ^= (long)Dar_ObjFanin0(pObj) * 7937; + Key ^= (long)Dar_ObjFanin1(pObj) * 2971; + Key ^= Dar_ObjFaninC0(pObj) * 911; + Key ^= Dar_ObjFaninC1(pObj) * 353; + return Key % TableSize; +} + +// returns the place where this node is stored (or should be stored) +static Dar_Obj_t ** Dar_TableFind( Dar_Man_t * p, Dar_Obj_t * pObj ) +{ + Dar_Obj_t ** ppEntry; + assert( Dar_ObjChild0(pObj) && Dar_ObjChild1(pObj) ); + assert( Dar_ObjFanin0(pObj)->Id < Dar_ObjFanin1(pObj)->Id ); + for ( ppEntry = p->pTable + Dar_Hash(pObj, p->nTableSize); *ppEntry; ppEntry = &(*ppEntry)->pNext ) + if ( *ppEntry == pObj ) + return ppEntry; + assert( *ppEntry == NULL ); + return ppEntry; +} + +static void Dar_TableResize( Dar_Man_t * p ); +static unsigned int Cudd_PrimeAig( unsigned int p ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Checks if node with the given attributes is in the hash table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Dar_Obj_t * Dar_TableLookup( Dar_Man_t * p, Dar_Obj_t * pGhost ) +{ + Dar_Obj_t * pEntry; + assert( !Dar_IsComplement(pGhost) ); + assert( Dar_ObjChild0(pGhost) && Dar_ObjChild1(pGhost) ); + assert( Dar_ObjFanin0(pGhost)->Id < Dar_ObjFanin1(pGhost)->Id ); + if ( !Dar_ObjRefs(Dar_ObjFanin0(pGhost)) || !Dar_ObjRefs(Dar_ObjFanin1(pGhost)) ) + return NULL; + for ( pEntry = p->pTable[Dar_Hash(pGhost, p->nTableSize)]; pEntry; pEntry = pEntry->pNext ) + { + if ( Dar_ObjChild0(pEntry) == Dar_ObjChild0(pGhost) && + Dar_ObjChild1(pEntry) == Dar_ObjChild1(pGhost) && + Dar_ObjType(pEntry) == Dar_ObjType(pGhost) ) + return pEntry; + } + return NULL; +} + +/**Function************************************************************* + + Synopsis [Adds the new node to the hash table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Dar_TableInsert( Dar_Man_t * p, Dar_Obj_t * pObj ) +{ + Dar_Obj_t ** ppPlace; + assert( !Dar_IsComplement(pObj) ); + assert( Dar_TableLookup(p, pObj) == NULL ); + if ( (pObj->Id & 0xFF) == 0 && 2 * p->nTableSize < Dar_ManNodeNum(p) ) + Dar_TableResize( p ); + ppPlace = Dar_TableFind( p, pObj ); + assert( *ppPlace == NULL ); + *ppPlace = pObj; +} + +/**Function************************************************************* + + Synopsis [Deletes the node from the hash table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Dar_TableDelete( Dar_Man_t * p, Dar_Obj_t * pObj ) +{ + Dar_Obj_t ** ppPlace; + assert( !Dar_IsComplement(pObj) ); + ppPlace = Dar_TableFind( p, pObj ); + assert( *ppPlace == pObj ); // node should be in the table + // remove the node + *ppPlace = pObj->pNext; + pObj->pNext = NULL; +} + +/**Function************************************************************* + + Synopsis [Count the number of nodes in the table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Dar_TableCountEntries( Dar_Man_t * p ) +{ + Dar_Obj_t * pEntry; + int i, Counter = 0; + for ( i = 0; i < p->nTableSize; i++ ) + for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext ) + Counter++; + return Counter; +} + +/**Function************************************************************* + + Synopsis [Resizes the table.] + + Description [Typically this procedure should not be called.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Dar_TableResize( Dar_Man_t * p ) +{ + Dar_Obj_t * pEntry, * pNext; + Dar_Obj_t ** pTableOld, ** ppPlace; + int nTableSizeOld, Counter, nEntries, i, clk; +clk = clock(); + // save the old table + pTableOld = p->pTable; + nTableSizeOld = p->nTableSize; + // get the new table + p->nTableSize = Cudd_PrimeAig( 2 * Dar_ManNodeNum(p) ); + p->pTable = ALLOC( Dar_Obj_t *, p->nTableSize ); + memset( p->pTable, 0, sizeof(Dar_Obj_t *) * p->nTableSize ); + // rehash the entries from the old table + Counter = 0; + for ( i = 0; i < nTableSizeOld; i++ ) + for ( pEntry = pTableOld[i], pNext = pEntry? pEntry->pNext : NULL; pEntry; pEntry = pNext, pNext = pEntry? pEntry->pNext : NULL ) + { + // get the place where this entry goes in the table + ppPlace = Dar_TableFind( p, pEntry ); + assert( *ppPlace == NULL ); // should not be there + // add the entry to the list + *ppPlace = pEntry; + pEntry->pNext = NULL; + Counter++; + } + nEntries = Dar_ManNodeNum(p); + assert( Counter == nEntries ); + printf( "Increasing the structural table size from %6d to %6d. ", nTableSizeOld, p->nTableSize ); + PRT( "Time", clock() - clk ); + // replace the table and the parameters + free( pTableOld ); +} + +/**Function******************************************************************** + + Synopsis [Profiles the hash table.] + + Description [] + + SideEffects [] + + SeeAlso [] + +******************************************************************************/ +void Dar_TableProfile( Dar_Man_t * p ) +{ + Dar_Obj_t * pEntry; + int i, Counter; + for ( i = 0; i < p->nTableSize; i++ ) + { + Counter = 0; + for ( pEntry = p->pTable[i]; pEntry; pEntry = pEntry->pNext ) + Counter++; + if ( Counter ) + printf( "%d ", Counter ); + } +} + +/**Function******************************************************************** + + Synopsis [Returns the next prime >= p.] + + Description [Copied from CUDD, for stand-aloneness.] + + SideEffects [None] + + SeeAlso [] + +******************************************************************************/ +unsigned int Cudd_PrimeAig( unsigned int p) +{ + int i,pn; + p--; + do { + p++; + if (p&1) { + pn = 1; + i = 3; + while ((unsigned) (i * i) <= p) { + if (p % i == 0) { + pn = 0; + break; + } + i += 2; + } + } else { + pn = 0; + } + } while (!pn); + return(p); + +} /* end of Cudd_Prime */ + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |