summaryrefslogtreecommitdiffstats
path: root/src/opt/cut/cutTable.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/opt/cut/cutTable.c')
-rw-r--r--src/opt/cut/cutTable.c253
1 files changed, 253 insertions, 0 deletions
diff --git a/src/opt/cut/cutTable.c b/src/opt/cut/cutTable.c
new file mode 100644
index 00000000..5dfaca7b
--- /dev/null
+++ b/src/opt/cut/cutTable.c
@@ -0,0 +1,253 @@
+/**CFile****************************************************************
+
+ FileName [cutTable.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [K-feasible cut computation package.]
+
+ Synopsis [Hashing cuts to prevent duplication.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: cutTable.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "cutInt.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+struct Cut_HashTableStruct_t_
+{
+ int nBins;
+ Cut_Cut_t ** pBins;
+ int nEntries;
+ int * pPlaces;
+ int nPlaces;
+ int timeLookup;
+};
+
+// iterator through all the cuts of the list
+#define Cut_TableListForEachCut( pList, pCut ) \
+ for ( pCut = pList; \
+ pCut; \
+ pCut = pCut->pData )
+#define Cut_TableListForEachCutSafe( pList, pCut, pCut2 ) \
+ for ( pCut = pList, \
+ pCut2 = pCut? pCut->pData: NULL; \
+ pCut; \
+ pCut = pCut2, \
+ pCut2 = pCut? pCut->pData: NULL )
+
+// primes used to compute the hash key
+static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 };
+
+// hashing function
+static inline unsigned Cut_HashKey( Cut_Cut_t * pCut )
+{
+ unsigned i, uRes = pCut->nLeaves * s_HashPrimes[9];
+ for ( i = 0; i < pCut->nLeaves + pCut->fSeq; i++ )
+ uRes += s_HashPrimes[i] * pCut->pLeaves[i];
+ return uRes;
+}
+
+// hashing function
+static inline int Cut_CompareTwo( Cut_Cut_t * pCut1, Cut_Cut_t * pCut2 )
+{
+ unsigned i;
+ if ( pCut1->nLeaves != pCut2->nLeaves )
+ return 1;
+ for ( i = 0; i < pCut1->nLeaves; i++ )
+ if ( pCut1->pLeaves[i] != pCut2->pLeaves[i] )
+ return 1;
+ return 0;
+}
+
+static void Cut_TableResize( Cut_HashTable_t * pTable );
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Starts the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Cut_HashTable_t * Cut_TableStart( int Size )
+{
+ Cut_HashTable_t * pTable;
+ pTable = ALLOC( Cut_HashTable_t, 1 );
+ memset( pTable, 0, sizeof(Cut_HashTable_t) );
+ // allocate the table
+ pTable->nBins = Cudd_PrimeCopy( Size );
+ pTable->pBins = ALLOC( Cut_Cut_t *, pTable->nBins );
+ memset( pTable->pBins, 0, sizeof(Cut_Cut_t *) * pTable->nBins );
+ pTable->pPlaces = ALLOC( int, pTable->nBins );
+ return pTable;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Stops the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Cut_TableStop( Cut_HashTable_t * pTable )
+{
+ FREE( pTable->pPlaces );
+ free( pTable->pBins );
+ free( pTable );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Check the existence of a cut in the lookup table]
+
+ Description [Returns 1 if the entry is found.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Cut_TableLookup( Cut_HashTable_t * pTable, Cut_Cut_t * pCut, int fStore )
+{
+ Cut_Cut_t * pEnt;
+ unsigned Key;
+ int clk = clock();
+
+ Key = Cut_HashKey(pCut) % pTable->nBins;
+ Cut_TableListForEachCut( pTable->pBins[Key], pEnt )
+ {
+ if ( !Cut_CompareTwo( pEnt, pCut ) )
+ {
+pTable->timeLookup += clock() - clk;
+ return 1;
+ }
+ }
+ if ( pTable->nEntries > 2 * pTable->nBins )
+ {
+ Cut_TableResize( pTable );
+ Key = Cut_HashKey(pCut) % pTable->nBins;
+ }
+ // remember the place
+ if ( fStore && pTable->pBins[Key] == NULL )
+ pTable->pPlaces[ pTable->nPlaces++ ] = Key;
+ // add the cut to the table
+ pCut->pData = pTable->pBins[Key];
+ pTable->pBins[Key] = pCut;
+ pTable->nEntries++;
+pTable->timeLookup += clock() - clk;
+ return 0;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Stops the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Cut_TableClear( Cut_HashTable_t * pTable )
+{
+ int i;
+ assert( pTable->nPlaces <= pTable->nBins );
+ for ( i = 0; i < pTable->nPlaces; i++ )
+ {
+ assert( pTable->pBins[ pTable->pPlaces[i] ] );
+ pTable->pBins[ pTable->pPlaces[i] ] = NULL;
+ }
+ pTable->nPlaces = 0;
+ pTable->nEntries = 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Cut_TableResize( Cut_HashTable_t * pTable )
+{
+ Cut_Cut_t ** pBinsNew;
+ Cut_Cut_t * pEnt, * pEnt2;
+ int nBinsNew, Counter, i, clk;
+ unsigned Key;
+
+clk = clock();
+ // get the new table size
+ nBinsNew = Cudd_PrimeCopy( 3 * pTable->nBins );
+ // allocate a new array
+ pBinsNew = ALLOC( Cut_Cut_t *, nBinsNew );
+ memset( pBinsNew, 0, sizeof(Cut_Cut_t *) * nBinsNew );
+ // rehash the entries from the old table
+ Counter = 0;
+ for ( i = 0; i < pTable->nBins; i++ )
+ Cut_TableListForEachCutSafe( pTable->pBins[i], pEnt, pEnt2 )
+ {
+ Key = Cut_HashKey(pEnt) % nBinsNew;
+ pEnt->pData = pBinsNew[Key];
+ pBinsNew[Key] = pEnt;
+ Counter++;
+ }
+ assert( Counter == pTable->nEntries );
+// printf( "Increasing the structural table size from %6d to %6d. ", pMan->nBins, nBinsNew );
+// PRT( "Time", clock() - clk );
+ // replace the table and the parameters
+ free( pTable->pBins );
+ pTable->pBins = pBinsNew;
+ pTable->nBins = nBinsNew;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Stops the hash table.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Cut_TableReadTime( Cut_HashTable_t * pTable )
+{
+ if ( pTable == NULL )
+ return 0;
+ return pTable->timeLookup;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-02 03:36:53 +0000