summaryrefslogtreecommitdiffstats
path: root/src/abc8/aig/aigTable.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/abc8/aig/aigTable.c')
-rw-r--r--src/abc8/aig/aigTable.c289
1 files changed, 289 insertions, 0 deletions
diff --git a/src/abc8/aig/aigTable.c b/src/abc8/aig/aigTable.c
new file mode 100644
index 00000000..357b63c3
--- /dev/null
+++ b/src/abc8/aig/aigTable.c
@@ -0,0 +1,289 @@
+/**CFile****************************************************************
+
+ FileName [aigTable.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [AIG package.]
+
+ Synopsis [Structural hashing table.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - April 28, 2007.]
+
+ Revision [$Id: aigTable.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "aig.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+// hashing the node
+static unsigned long Aig_Hash( Aig_Obj_t * pObj, int TableSize )
+{
+ unsigned long Key = Aig_ObjIsExor(pObj) * 1699;
+ Key ^= Aig_ObjFanin0(pObj)->Id * 7937;
+ Key ^= Aig_ObjFanin1(pObj)->Id * 2971;
+ Key ^= Aig_ObjFaninC0(pObj) * 911;
+ Key ^= Aig_ObjFaninC1(pObj) * 353;
+ return Key % TableSize;
+}
+
+// returns the place where this node is stored (or should be stored)
+static Aig_Obj_t ** Aig_TableFind( Aig_Man_t * p, Aig_Obj_t * pObj )
+{
+ Aig_Obj_t ** ppEntry;
+ if ( Aig_ObjIsLatch(pObj) )
+ {
+ assert( Aig_ObjChild0(pObj) && Aig_ObjChild1(pObj) == NULL );
+ }
+ else
+ {
+ assert( Aig_ObjChild0(pObj) && Aig_ObjChild1(pObj) );
+ assert( Aig_ObjFanin0(pObj)->Id < Aig_ObjFanin1(pObj)->Id );
+ }
+ for ( ppEntry = p->pTable + Aig_Hash(pObj, p->nTableSize); *ppEntry; ppEntry = &(*ppEntry)->pNext )
+ if ( *ppEntry == pObj )
+ return ppEntry;
+ assert( *ppEntry == NULL );
+ return ppEntry;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Resizes the table.]
+
+ Description [Typically this procedure should not be called.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Aig_TableResize( Aig_Man_t * p )
+{
+ Aig_Obj_t * pEntry, * pNext;
+ Aig_Obj_t ** pTableOld, ** ppPlace;
+ int nTableSizeOld, Counter, i, clk;
+clk = clock();
+ // save the old table
+ pTableOld = p->pTable;
+ nTableSizeOld = p->nTableSize;
+ // get the new table
+ p->nTableSize = Aig_PrimeCudd( 2 * Aig_ManNodeNum(p) );
+ p->pTable = ALLOC( Aig_Obj_t *, p->nTableSize );
+ memset( p->pTable, 0, sizeof(Aig_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 = Aig_TableFind( p, pEntry );
+ assert( *ppPlace == NULL ); // should not be there
+ // add the entry to the list
+ *ppPlace = pEntry;
+ pEntry->pNext = NULL;
+ Counter++;
+ }
+ assert( Counter == Aig_ManNodeNum(p) );
+// 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 [Checks if node with the given attributes is in the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Aig_Obj_t * Aig_TableLookup( Aig_Man_t * p, Aig_Obj_t * pGhost )
+{
+ Aig_Obj_t * pEntry;
+ assert( !Aig_IsComplement(pGhost) );
+ if ( pGhost->Type == AIG_OBJ_LATCH )
+ {
+ assert( Aig_ObjChild0(pGhost) && Aig_ObjChild1(pGhost) == NULL );
+ if ( !Aig_ObjRefs(Aig_ObjFanin0(pGhost)) )
+ return NULL;
+ }
+ else
+ {
+ assert( pGhost->Type == AIG_OBJ_AND );
+ assert( Aig_ObjChild0(pGhost) && Aig_ObjChild1(pGhost) );
+ assert( Aig_ObjFanin0(pGhost)->Id < Aig_ObjFanin1(pGhost)->Id );
+ if ( !Aig_ObjRefs(Aig_ObjFanin0(pGhost)) || !Aig_ObjRefs(Aig_ObjFanin1(pGhost)) )
+ return NULL;
+ }
+ for ( pEntry = p->pTable[Aig_Hash(pGhost, p->nTableSize)]; pEntry; pEntry = pEntry->pNext )
+ {
+ if ( Aig_ObjChild0(pEntry) == Aig_ObjChild0(pGhost) &&
+ Aig_ObjChild1(pEntry) == Aig_ObjChild1(pGhost) &&
+ Aig_ObjType(pEntry) == Aig_ObjType(pGhost) )
+ return pEntry;
+ }
+ return NULL;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Checks if node with the given attributes is in the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Aig_Obj_t * Aig_TableLookupTwo( Aig_Man_t * p, Aig_Obj_t * pFanin0, Aig_Obj_t * pFanin1 )
+{
+ Aig_Obj_t * pGhost;
+ // consider simple cases
+ if ( pFanin0 == pFanin1 )
+ return pFanin0;
+ if ( pFanin0 == Aig_Not(pFanin1) )
+ return Aig_ManConst0(p);
+ if ( Aig_Regular(pFanin0) == Aig_ManConst1(p) )
+ return pFanin0 == Aig_ManConst1(p) ? pFanin1 : Aig_ManConst0(p);
+ if ( Aig_Regular(pFanin1) == Aig_ManConst1(p) )
+ return pFanin1 == Aig_ManConst1(p) ? pFanin0 : Aig_ManConst0(p);
+ pGhost = Aig_ObjCreateGhost( p, pFanin0, pFanin1, AIG_OBJ_AND );
+ return Aig_TableLookup( p, pGhost );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Adds the new node to the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Aig_TableInsert( Aig_Man_t * p, Aig_Obj_t * pObj )
+{
+ Aig_Obj_t ** ppPlace;
+ if ( p->pTable == NULL )
+ return;
+ assert( !Aig_IsComplement(pObj) );
+ assert( Aig_TableLookup(p, pObj) == NULL );
+ if ( (pObj->Id & 0xFF) == 0 && 2 * p->nTableSize < Aig_ManNodeNum(p) )
+ Aig_TableResize( p );
+ ppPlace = Aig_TableFind( p, pObj );
+ assert( *ppPlace == NULL );
+ *ppPlace = pObj;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Deletes the node from the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Aig_TableDelete( Aig_Man_t * p, Aig_Obj_t * pObj )
+{
+ Aig_Obj_t ** ppPlace;
+ if ( p->pTable == NULL )
+ return;
+ assert( !Aig_IsComplement(pObj) );
+ ppPlace = Aig_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 Aig_TableCountEntries( Aig_Man_t * p )
+{
+ Aig_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 [Profiles the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+void Aig_TableProfile( Aig_Man_t * p )
+{
+ Aig_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 [Profiles the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+void Aig_TableClear( Aig_Man_t * p )
+{
+ FREE( p->pTable );
+ p->nTableSize = 0;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-02 15:30:36 +0000