Added QuickSort based on 3-way partitioning.

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;