Version abc50822

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                                ///
+////////////////////////////////////////////////////////////////////////
+
+