/**CFile****************************************************************
FileName [utilSort.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [Merge sort with user-specified cost.]
Synopsis [Merge sort with user-specified cost.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - Feburary 13, 2011.]
Revision [$Id: utilSort.c,v 1.00 2011/02/11 00:00:00 alanmi Exp $]
***********************************************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "abc_global.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Merging two lists of entries.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_SortMerge( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut )
{
int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
int * pOutBeg = pOut;
while ( p1Beg < p1End && p2Beg < p2End )
{
if ( *p1Beg == *p2Beg )
*pOut++ = *p1Beg++, *pOut++ = *p2Beg++;
else if ( *p1Beg < *p2Beg )
*pOut++ = *p1Beg++;
else // if ( *p1Beg > *p2Beg )
*pOut++ = *p2Beg++;
}
while ( p1Beg < p1End )
*pOut++ = *p1Beg++;
while ( p2Beg < p2End )
*pOut++ = *p2Beg++;
assert( pOut - pOutBeg == nEntries );
}
/**Function*************************************************************
Synopsis [Recursive sorting.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_Sort_rec( int * pInBeg, int * pInEnd, int * pOutBeg )
{
int nSize = pInEnd - pInBeg;
assert( nSize > 0 );
if ( nSize == 1 )
return;
if ( nSize == 2 )
{
if ( pInBeg[0] > pInBeg[1] )
{
pInBeg[0] ^= pInBeg[1];
pInBeg[1] ^= pInBeg[0];
pInBeg[0] ^= pInBeg[1];
}
}
else if ( nSize < 8 )
{
int temp, i, j, best_i;
for ( i = 0; i < nSize-1; i++ )
{
best_i = i;
for ( j = i+1; j < nSize; j++ )
if ( pInBeg[j] < pInBeg[best_i] )
best_i = j;
temp = pInBeg[i];
pInBeg[i] = pInBeg[best_i];
pInBeg[best_i] = temp;
}
}
else
{
Abc_Sort_rec( pInBeg, pInBeg + nSize/2, pOutBeg );
Abc_Sort_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2 );
Abc_SortMerge( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg );
memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
}
}
/**Function*************************************************************
Synopsis [Returns the sorted array of integers.]
Description [This procedure is about 10% faster than qsort().]
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_MergeSort( int * pInput, int nSize )
{
int * pOutput;
if ( nSize < 2 )
return;
pOutput = (int *) malloc( sizeof(int) * nSize );
Abc_Sort_rec( pInput, pInput + nSize, pOutput );
free( pOutput );
}
/**Function*************************************************************
Synopsis [Merging two lists of entries.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_MergeSortCostMerge( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut )
{
int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
int * pOutBeg = pOut;
while ( p1Beg < p1End && p2Beg < p2End )
{
if ( p1Beg[1] == p2Beg[1] )
*pOut++ = *p1Beg++, *pOut++ = *p1Beg++, *pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
else if ( p1Beg[1] < p2Beg[1] )
*pOut++ = *p1Beg++, *pOut++ = *p1Beg++;
else // if ( p1Beg[1] > p2Beg[1] )
*pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
}
while ( p1Beg < p1End )
*pOut++ = *p1Beg++, *pOut++ = *p1Beg++;
while ( p2Beg < p2End )
*pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
assert( pOut - pOutBeg == nEntries );
}
/**Function*************************************************************
Synopsis [Recursive sorting.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_MergeSortCost_rec( int * pInBeg, int * pInEnd, int * pOutBeg )
{
int nSize = (pInEnd - pInBeg)/2;
assert( nSize > 0 );
if ( nSize == 1 )
return;
if ( nSize == 2 )
{
if ( pInBeg[1] > pInBeg[3] )
{
pInBeg[1] ^= pInBeg[3];
pInBeg[3] ^= pInBeg[1];
pInBeg[1] ^= pInBeg[3];
pInBeg[0] ^= pInBeg[2];
pInBeg[2] ^= pInBeg[0];
pInBeg[0] ^= pInBeg[2];
}
}
else if ( nSize < 8 )
{
int temp, i, j, best_i;
for ( i = 0; i < nSize-1; i++ )
{
best_i = i;
for ( j = i+1; j < nSize; j++ )
if ( pInBeg[2*j+1] < pInBeg[2*best_i+1] )
best_i = j;
temp = pInBeg[2*i];
pInBeg[2*i] = pInBeg[2*best_i];
pInBeg[2*best_i] = temp;
temp = pInBeg[2*i+1];
pInBeg[2*i+1] = pInBeg[2*best_i+1];
pInBeg[2*best_i+1] = temp;
}
}
else
{
Abc_MergeSortCost_rec( pInBeg, pInBeg + 2*(nSize/2), pOutBeg );
Abc_MergeSortCost_rec( pInBeg + 2*(nSize/2), pInEnd, pOutBeg + 2*(nSize/2) );
Abc_MergeSortCostMerge( pInBeg, pInBeg + 2*(nSize/2), pInBeg + 2*(nSize/2), pInEnd, pOutBeg );
memcpy( pInBeg, pOutBeg, sizeof(int) * 2 * nSize );
}
}
/**Function*************************************************************
Synopsis [Sorting procedure.]
Description [Returns permutation for the non-decreasing order of costs.]
SideEffects []
SeeAlso []
***********************************************************************/
int * Abc_MergeSortCost( int * pCosts, int nSize )
{
int i, * pResult, * pInput, * pOutput;
pResult = (int *) calloc( sizeof(int), nSize );
if ( nSize < 2 )
return pResult;
pInput = (int *) malloc( sizeof(int) * 2 * nSize );
pOutput = (int *) malloc( sizeof(int) * 2 * nSize );
for ( i = 0; i < nSize; i++ )
pInput[2*i] = i, pInput[2*i+1] = pCosts[i];
Abc_MergeSortCost_rec( pInput, pInput + 2*nSize, pOutput );
for ( i = 0; i < nSize; i++ )
pResult[i] = pInput[2*i];
free( pOutput );
free( pInput );
return pResult;
}
// this implementation uses 3x less memory but is 30% slower due to cache misses
#if 0
/**Function*************************************************************
Synopsis [Merging two lists of entries.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_MergeSortCostMerge( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut, int * pCost )
{
int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
int * pOutBeg = pOut;
while ( p1Beg < p1End && p2Beg < p2End )
{
if ( pCost[*p1Beg] == pCost[*p2Beg] )
*pOut++ = *p1Beg++, *pOut++ = *p2Beg++;
else if ( pCost[*p1Beg] < pCost[*p2Beg] )
*pOut++ = *p1Beg++;
else // if ( pCost[*p1Beg] > pCost[*p2Beg] )
*pOut++ = *p2Beg++;
}
while ( p1Beg < p1End )
*pOut++ = *p1Beg++;
while ( p2Beg < p2End )
*pOut++ = *p2Beg++;
assert( pOut - pOutBeg == nEntries );
}
/**Function*************************************************************
Synopsis [Recursive sorting.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_MergeSortCost_rec( int * pInBeg, int * pInEnd, int * pOutBeg, int * pCost )
{
int nSize = pInEnd - pInBeg;
assert( nSize > 0 );
if ( nSize == 1 )
return;
if ( nSize == 2 )
{
if ( pCost[pInBeg[0]] > pCost[pInBeg[1]] )
{
pInBeg[0] ^= pInBeg[1];
pInBeg[1] ^= pInBeg[0];
pInBeg[0] ^= pInBeg[1];
}
}
else if ( nSize < 8 )
{
int temp, i, j, best_i;
for ( i = 0; i < nSize-1; i++ )
{
best_i = i;
for ( j = i+1; j < nSize; j++ )
if ( pCost[pInBeg[j]] < pCost[pInBeg[best_i]] )
best_i = j;
temp = pInBeg[i];
pInBeg[i] = pInBeg[best_i];
pInBeg[best_i] = temp;
}
}
else
{
Abc_MergeSortCost_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost );
Abc_MergeSortCost_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost );
Abc_MergeSortCostMerge( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost );
memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
}
}
/**Function*************************************************************
Synopsis [Sorting procedure.]
Description [Returns permutation for the non-decreasing order of costs.]
SideEffects []
SeeAlso []
***********************************************************************/
int * Abc_MergeSortCost( int * pCosts, int nSize )
{
int i, * pInput, * pOutput;
pInput = (int *) malloc( sizeof(int) * nSize );
for ( i = 0; i < nSize; i++ )
pInput[i] = i;
if ( nSize < 2 )
return pInput;
pOutput = (int *) malloc( sizeof(int) * nSize );
Abc_MergeSortCost_rec( pInput, pInput + nSize, pOutput, pCosts );
free( pOutput );
return pInput;
}
#endif
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_SortNumCompare( int * pNum1, int * pNum2 )
{
return *pNum1 - *pNum2;
}
/**Function*************************************************************
Synopsis [Testing the sorting procedure.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_SortTest()
{
int fUseNew = 0;
int i, nSize = 50000000;
int * pArray = (int *)malloc( sizeof(int) * nSize );
int * pPerm;
abctime clk;
// generate numbers
srand( 1000 );
for ( i = 0; i < nSize; i++ )
pArray[i] = rand();
// try sorting
if ( fUseNew )
{
int fUseCost = 1;
if ( fUseCost )
{
clk = Abc_Clock();
pPerm = Abc_MergeSortCost( pArray, nSize );
Abc_PrintTime( 1, "New sort", Abc_Clock() - clk );
// check
for ( i = 1; i < nSize; i++ )
assert( pArray[pPerm[i-1]] <= pArray[pPerm[i]] );
free( pPerm );
}
else
{
clk = Abc_Clock();
Abc_MergeSort( pArray, nSize );
Abc_PrintTime( 1, "New sort", Abc_Clock() - clk );
// check
for ( i = 1; i < nSize; i++ )
assert( pArray[i-1] <= pArray[i] );
}
}
else
{
clk = Abc_Clock();
qsort( (void *)pArray, nSize, sizeof(int), (int (*)(const void *, const void *)) Abc_SortNumCompare );
Abc_PrintTime( 1, "Old sort", Abc_Clock() - clk );
// check
for ( i = 1; i < nSize; i++ )
assert( pArray[i-1] <= pArray[i] );
}
free( pArray );
}
/**Function*************************************************************
Synopsis [QuickSort algorithm as implemented by qsort().]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Abc_QuickSort1CompareInc( word * p1, word * p2 )
{
if ( (unsigned)(*p1) < (unsigned)(*p2) )
return -1;
if ( (unsigned)(*p1) > (unsigned)(*p2) )
return 1;
return 0;
}
int Abc_QuickSort1CompareDec( 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 fDecrease )
{
int i, fVerify = 0;
if ( fDecrease )
{
qsort( (void *)pData, nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSort1CompareDec );
if ( fVerify )
for ( i = 1; i < nSize; i++ )
assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
}
else
{
qsort( (void *)pData, nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSort1CompareInc );
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 []
***********************************************************************/
static inline void Abc_SelectSortInc( 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] );
}
}
static inline void Abc_SelectSortDec( 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_QuickSort2Inc_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 )
{
Abc_SelectSortInc( 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_QuickSort2Inc_rec( pData, l, i-1 );
Abc_QuickSort2Inc_rec( pData, i+1, r );
}
void Abc_QuickSort2Dec_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 )
{
Abc_SelectSortDec( 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_QuickSort2Dec_rec( pData, l, i-1 );
Abc_QuickSort2Dec_rec( pData, i+1, r );
}
void Abc_QuickSort3Inc_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 )
{
Abc_SelectSortInc( 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_QuickSort3Inc_rec( pData, l, j );
Abc_QuickSort3Inc_rec( pData, i, r );
}
void Abc_QuickSort3Dec_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 )
{
Abc_SelectSortDec( 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_QuickSort3Dec_rec( pData, l, j );
Abc_QuickSort3Dec_rec( pData, i, r );
}
void Abc_QuickSort2( word * pData, int nSize, int fDecrease )
{
int i, fVerify = 0;
if ( fDecrease )
{
Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 );
if ( fVerify )
for ( i = 1; i < nSize; i++ )
assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
}
else
{
Abc_QuickSort2Inc_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 fDecrease )
{
int i, fVerify = 1;
if ( fDecrease )
{
Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 );
if ( fVerify )
for ( i = 1; i < nSize; i++ )
assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
}
else
{
Abc_QuickSort2Inc_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, int fDecrease, word * pData, int * pResult )
{
int i;
for ( i = 0; i < nSize; i++ )
pData[i] = ((word)i << 32) | pCosts[i];
Abc_QuickSort3( pData, nSize, fDecrease );
for ( i = 0; i < nSize; i++ )
pResult[i] = (int)(pData[i] >> 32);
}
int * Abc_QuickSortCost( int * pCosts, int nSize, int fDecrease )
{
word * pData = ABC_ALLOC( word, nSize );
int * pResult = ABC_ALLOC( int, nSize );
Abc_QuickSortCostData( pCosts, nSize, fDecrease, pData, pResult );
ABC_FREE( pData );
return pResult;
}
// extern void Abc_QuickSortTest();
// Abc_QuickSortTest();
/**Function*************************************************************
Synopsis []
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Abc_QuickSortTest()
{
int nSize = 1000000;
int fVerbose = 0;
word * pData1, * pData2;
int i;
abctime clk = Abc_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 ", Abc_Clock() - clk );
// perform sorting
clk = Abc_Clock();
Abc_QuickSort3( pData1, nSize, 1 );
Abc_PrintTime( 1, "Sort new", Abc_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 = Abc_Clock();
Abc_QuickSort1( pData2, nSize, 1 );
Abc_PrintTime( 1, "Sort old", Abc_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 );
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END