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, 0 insertions, 253 deletions
diff --git a/src/opt/cut/cutTable.c b/src/opt/cut/cutTable.c
deleted file mode 100644
index 5dfaca7b..00000000
--- a/src/opt/cut/cutTable.c
+++ /dev/null
@@ -1,253 +0,0 @@
-/**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-07-15 11:35:52 +0000