summaryrefslogtreecommitdiffstats
path: root/src/aig/gia/giaIso.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/aig/gia/giaIso.c')
-rw-r--r--src/aig/gia/giaIso.c218
1 files changed, 1 insertions, 217 deletions
diff --git a/src/aig/gia/giaIso.c b/src/aig/gia/giaIso.c
index 204c3bbc..3ff8ee2f 100644
--- a/src/aig/gia/giaIso.c
+++ b/src/aig/gia/giaIso.c
@@ -137,222 +137,6 @@ static inline void Gia_IsoSetItem( Gia_IsoMan_t * p, int i, unsigned v ) {
/**Function*************************************************************
- Synopsis [QuickSort algorithm as implemented by qsort().]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-int Abc_QuickSortCompare( word * p1, word * p2 )
-{
- if ( (unsigned)(*p1) < (unsigned)(*p2) )
- return -1;
- if ( (unsigned)(*p1) > (unsigned)(*p2) )
- return 1;
- return 0;
-}
-void Abc_QuickSort1( word * pData, int nSize )
-{
- int i, fVerify = 0;
- qsort( (void *)pData, nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSortCompare );
- if ( fVerify )
- for ( i = 1; i < nSize; i++ )
- assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
-}
-
-/**Function*************************************************************
-
- Synopsis [QuickSort algorithm based on 2/3-way partitioning.]
-
- Description [This code is based on the online presentation
- "QuickSort is Optimal" by Robert Sedgewick and Jon Bentley.
- http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf
-
- The first 32-bits of the input data contain values to be compared.
- The last 32-bits contain the user's data. When sorting is finished,
- the 64-bit words are ordered in the increasing order of their value ]
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-#define ABC_SWAP(Type, a, b) { Type t = a; a = b; b = t; }
-static inline void Iso_SelectSort( word * pData, int nSize )
-{
- int i, j, best_i;
- for ( i = 0; i < nSize-1; i++ )
- {
- best_i = i;
- for ( j = i+1; j < nSize; j++ )
- if ( (unsigned)pData[j] < (unsigned)pData[best_i] )
- best_i = j;
- ABC_SWAP( word, pData[i], pData[best_i] );
- }
-}
-void Abc_QuickSort2_rec( word * pData, int l, int r )
-{
- word v = pData[r];
- int i = l-1, j = r;
- if ( l >= r )
- return;
- assert( l < r );
- if ( r - l < 10 )
- {
- Iso_SelectSort( pData + l, r - l + 1 );
- return;
- }
- while ( 1 )
- {
- while ( (unsigned)pData[++i] < (unsigned)v );
- while ( (unsigned)v < (unsigned)pData[--j] )
- if ( j == l )
- break;
- if ( i >= j )
- break;
- ABC_SWAP( word, pData[i], pData[j] );
- }
- ABC_SWAP( word, pData[i], pData[r] );
- Abc_QuickSort2_rec( pData, l, i-1 );
- Abc_QuickSort2_rec( pData, i+1, r );
-}
-void Abc_QuickSort3_rec( word * pData, int l, int r )
-{
- word v = pData[r];
- int k, i = l-1, j = r, p = l-1, q = r;
- if ( l >= r )
- return;
- assert( l < r );
- if ( r - l < 10 )
- {
- Iso_SelectSort( pData + l, r - l + 1 );
- return;
- }
- while ( 1 )
- {
- while ( (unsigned)pData[++i] < (unsigned)v );
- while ( (unsigned)v < (unsigned)pData[--j] )
- if ( j == l )
- break;
- if ( i >= j )
- break;
- ABC_SWAP( word, pData[i], pData[j] );
- if ( (unsigned)pData[i] == (unsigned)v )
- { p++; ABC_SWAP( word, pData[p], pData[i] ); }
- if ( (unsigned)v == (unsigned)pData[j] )
- { q--; ABC_SWAP( word, pData[j], pData[q] ); }
- }
- ABC_SWAP( word, pData[i], pData[r] );
- j = i-1; i = i+1;
- for ( k = l; k < p; k++, j-- )
- ABC_SWAP( word, pData[k], pData[j] );
- for ( k = r-1; k > q; k--, i++ )
- ABC_SWAP( word, pData[i], pData[k] );
- Abc_QuickSort3_rec( pData, l, j );
- Abc_QuickSort3_rec( pData, i, r );
-}
-void Abc_QuickSort2( word * pData, int nSize )
-{
- int i, fVerify = 0;
- Abc_QuickSort2_rec( pData, 0, nSize - 1 );
- if ( fVerify )
- for ( i = 1; i < nSize; i++ )
- assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
-}
-void Abc_QuickSort3( word * pData, int nSize )
-{
- int i, fVerify = 0;
- Abc_QuickSort3_rec( pData, 0, nSize - 1 );
- if ( fVerify )
- for ( i = 1; i < nSize; i++ )
- assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
-}
-
-/**Function*************************************************************
-
- Synopsis [Wrapper around QuickSort to sort entries based on cost.]
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void Abc_QuickSortCostData( int * pCosts, int nSize, word * pData, int * pResult )
-{
- int i;
- for ( i = 0; i < nSize; i++ )
- pData[i] = ((word)i << 32) | pCosts[i];
- Abc_QuickSort3( pData, nSize );
- for ( i = 0; i < nSize; i++ )
- pResult[i] = (int)(pData[i] >> 32);
-}
-int * Abc_QuickSortCost( int * pCosts, int nSize )
-{
- word * pData = ABC_ALLOC( word, nSize );
- int * pResult = ABC_ALLOC( int, nSize );
- Abc_QuickSortCostData( pCosts, nSize, pData, pResult );
- ABC_FREE( pData );
- return pResult;
-}
-
-/**Function*************************************************************
-
- Synopsis []
-
- Description []
-
- SideEffects []
-
- SeeAlso []
-
-***********************************************************************/
-void Abc_QuickSortTest()
-{
- int nSize = 10000000;
- int fVerbose = 0;
- word * pData1, * pData2;
- int i, clk = clock();
- // generate numbers
- pData1 = ABC_ALLOC( word, nSize );
- pData2 = ABC_ALLOC( word, nSize );
- srand( 1111 );
- for ( i = 0; i < nSize; i++ )
- pData2[i] = pData1[i] = ((word)i << 32) | rand();
- Abc_PrintTime( 1, "Prepare ", clock() - clk );
- // perform sorting
- clk = clock();
- Abc_QuickSort3( pData1, nSize );
- Abc_PrintTime( 1, "Sort new", clock() - clk );
- // print the result
- if ( fVerbose )
- {
- for ( i = 0; i < nSize; i++ )
- printf( "(%d,%d) ", (int)(pData1[i] >> 32), (int)pData1[i] );
- printf( "\n" );
- }
- // create new numbers
- clk = clock();
- Abc_QuickSort1( pData2, nSize );
- Abc_PrintTime( 1, "Sort old", clock() - clk );
- // print the result
- if ( fVerbose )
- {
- for ( i = 0; i < nSize; i++ )
- printf( "(%d,%d) ", (int)(pData2[i] >> 32), (int)pData2[i] );
- printf( "\n" );
- }
- ABC_FREE( pData1 );
- ABC_FREE( pData2 );
-}
-
-
-/**Function*************************************************************
-
Synopsis []
Description []
@@ -619,7 +403,7 @@ void Gia_IsoSort( Gia_IsoMan_t * p )
}
// sort objects
clk = clock();
- Abc_QuickSort3( p->pStoreW + iBegin, nSize );
+ Abc_QuickSort3( p->pStoreW + iBegin, nSize, 0 );
p->timeSort += clock() - clk;
// divide into new classes
iBeginOld = iBegin;
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-04 21:14:16 +0000