utilSort.c File Reference

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include "abc_global.h"

Include dependency graph for utilSort.c:

Go to the source code of this file.

Macros
#define	NUMBER1   3716960521u
#define	NUMBER2   2174103536u

Functions
ABC_NAMESPACE_IMPL_START void	Abc_SortMerge (int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut)
	DECLARATIONS ///.
void	Abc_Sort_rec (int *pInBeg, int *pInEnd, int *pOutBeg)
void	Abc_MergeSort (int *pInput, int nSize)
void	Abc_SortMergeCost2 (int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut, int *pCost)
void	Abc_SortCost2_rec (int *pInBeg, int *pInEnd, int *pOutBeg, int *pCost)
void	Abc_MergeSortCost2 (int *pInput, int nSize, int *pCost)
void	Abc_SortMergeCost2Reverse (int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut, int *pCost)
void	Abc_SortCost2Reverse_rec (int *pInBeg, int *pInEnd, int *pOutBeg, int *pCost)
void	Abc_MergeSortCost2Reverse (int *pInput, int nSize, int *pCost)
void	Abc_MergeSortCostMerge (int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut)
void	Abc_MergeSortCost_rec (int *pInBeg, int *pInEnd, int *pOutBeg)
int *	Abc_MergeSortCost (int *pCosts, int nSize)
int	Abc_SortNumCompare (int *pNum1, int *pNum2)
void	Abc_SortTest ()
int	Abc_QuickSort1CompareInc (word *p1, word *p2)
int	Abc_QuickSort1CompareDec (word *p1, word *p2)
void	Abc_QuickSort1 (word *pData, int nSize, int fDecrease)
void	Abc_QuickSort2Inc_rec (word *pData, int l, int r)
void	Abc_QuickSort2Dec_rec (word *pData, int l, int r)
void	Abc_QuickSort3Inc_rec (word *pData, int l, int r)
void	Abc_QuickSort3Dec_rec (word *pData, int l, int r)
void	Abc_QuickSort2 (word *pData, int nSize, int fDecrease)
void	Abc_QuickSort3 (word *pData, int nSize, int fDecrease)
void	Abc_QuickSortCostData (int *pCosts, int nSize, int fDecrease, word *pData, int *pResult)
int *	Abc_QuickSortCost (int *pCosts, int nSize, int fDecrease)
void	Abc_QuickSortTest ()
unsigned	Abc_Random (int fReset)
word	Abc_RandomW (int fReset)

Macro Definition Documentation

NUMBER1

#define NUMBER1   3716960521u

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 1001 of file utilSort.c.

NUMBER2

#define NUMBER2   2174103536u

Definition at line 1002 of file utilSort.c.

Function Documentation

Abc_MergeSort()

void Abc_MergeSort	(	int *	pInput,
		int	nSize )

Function*************************************************************

Synopsis [Returns the sorted array of integers.]

Description [This procedure is about 10% faster than qsort().]

SideEffects []

SeeAlso []

Definition at line 129 of file utilSort.c.

{
    int * pOutput;
    if ( nSize < 2 )
        return;
    pOutput = (int *) malloc( sizeof(int) * nSize );
    Abc_Sort_rec( pInput, pInput + nSize, pOutput );
    free( pOutput );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_MergeSortCost()

int * Abc_MergeSortCost	(	int *	pCosts,
		int	nSize )

Function*************************************************************

Synopsis [Sorting procedure.]

Description [Returns permutation for the non-decreasing order of costs.]

SideEffects []

SeeAlso []

Definition at line 442 of file utilSort.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_MergeSortCost2()

void Abc_MergeSortCost2	(	int *	pInput,
		int	nSize,
		int *	pCost )

Function*************************************************************

Synopsis [Returns the sorted array of integers.]

Description [This procedure is about 10% faster than qsort().]

SideEffects []

SeeAlso []

Definition at line 231 of file utilSort.c.

{
    int * pOutput;
    if ( nSize < 2 )
        return;
    pOutput = (int *) malloc( sizeof(int) * nSize );
    Abc_SortCost2_rec( pInput, pInput + nSize, pOutput, pCost );
    free( pOutput );
}

Here is the call graph for this function:

Abc_MergeSortCost2Reverse()

void Abc_MergeSortCost2Reverse	(	int *	pInput,
		int	nSize,
		int *	pCost )

Function*************************************************************

Synopsis [Returns the sorted array of integers.]

Description [This procedure is about 10% faster than qsort().]

SideEffects []

SeeAlso []

Definition at line 333 of file utilSort.c.

{
    int * pOutput;
    if ( nSize < 2 )
        return;
    pOutput = (int *) malloc( sizeof(int) * nSize );
    Abc_SortCost2Reverse_rec( pInput, pInput + nSize, pOutput, pCost );
    free( pOutput );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_MergeSortCost_rec()

void Abc_MergeSortCost_rec	(	int *	pInBeg,
		int *	pInEnd,
		int *	pOutBeg )

Function*************************************************************

Synopsis [Recursive sorting.]

Description []

SideEffects []

SeeAlso []

Definition at line 387 of file utilSort.c.

{
    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 );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_MergeSortCostMerge()

void Abc_MergeSortCostMerge	(	int *	p1Beg,
		int *	p1End,
		int *	p2Beg,
		int *	p2End,
		int *	pOut )

Function*************************************************************

Synopsis [Merging two lists of entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 356 of file utilSort.c.

{
    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 );
}

Here is the caller graph for this function:

Abc_QuickSort1()

void Abc_QuickSort1	(	word *	pData,
		int	nSize,
		int	fDecrease )

Definition at line 681 of file utilSort.c.

{
    int i, fVerify = 0;
    if ( fDecrease )
    {
        qsort( (void *)pData, (size_t)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, (size_t)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] );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_QuickSort1CompareDec()

int Abc_QuickSort1CompareDec	(	word *	p1,
		word *	p2 )

Definition at line 673 of file utilSort.c.

{
    if ( (unsigned)(*p1) > (unsigned)(*p2) )
        return -1;
    if ( (unsigned)(*p1) < (unsigned)(*p2) )
        return 1;
    return 0;
}

Here is the caller graph for this function:

Abc_QuickSort1CompareInc()

int Abc_QuickSort1CompareInc	(	word *	p1,
		word *	p2 )

Function*************************************************************

Synopsis [QuickSort algorithm as implemented by qsort().]

Description []

SideEffects []

SeeAlso []

Definition at line 665 of file utilSort.c.

{
    if ( (unsigned)(*p1) < (unsigned)(*p2) )
        return -1;
    if ( (unsigned)(*p1) > (unsigned)(*p2) )
        return 1;
    return 0;
}

Here is the caller graph for this function:

Abc_QuickSort2()

void Abc_QuickSort2	(	word *	pData,
		int	nSize,
		int	fDecrease )

Definition at line 866 of file utilSort.c.

{
    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] );
    }
}

Here is the call graph for this function:

Abc_QuickSort2Dec_rec()

void Abc_QuickSort2Dec_rec	(	word *	pData,
		int	l,
		int	r )

Definition at line 768 of file utilSort.c.

{
    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 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_QuickSort2Inc_rec()

void Abc_QuickSort2Inc_rec	(	word *	pData,
		int	l,
		int	r )

Definition at line 742 of file utilSort.c.

{
    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 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_QuickSort3()

void Abc_QuickSort3	(	word *	pData,
		int	nSize,
		int	fDecrease )

Definition at line 884 of file utilSort.c.

{
    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] );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_QuickSort3Dec_rec()

void Abc_QuickSort3Dec_rec	(	word *	pData,
		int	l,
		int	r )

Definition at line 830 of file utilSort.c.

{
    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 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_QuickSort3Inc_rec()

void Abc_QuickSort3Inc_rec	(	word *	pData,
		int	l,
		int	r )

Definition at line 795 of file utilSort.c.

{
    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 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_QuickSortCost()

int * Abc_QuickSortCost	(	int *	pCosts,
		int	nSize,
		int	fDecrease )

Definition at line 923 of file utilSort.c.

{
    word * pData = ABC_ALLOC( word, nSize );
    int * pResult = ABC_ALLOC( int, nSize );
    Abc_QuickSortCostData( pCosts, nSize, fDecrease, pData, pResult );
    ABC_FREE( pData );
    return pResult;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_QuickSortCostData()

void Abc_QuickSortCostData	(	int *	pCosts,
		int	nSize,
		int	fDecrease,
		word *	pData,
		int *	pResult )

Function*************************************************************

Synopsis [Wrapper around QuickSort to sort entries based on cost.]

Description []

SideEffects []

SeeAlso []

Definition at line 914 of file utilSort.c.

{
    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);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_QuickSortTest()

void Abc_QuickSortTest

(

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 946 of file utilSort.c.

{
    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 );
}

Here is the call graph for this function:

Abc_Random()

unsigned Abc_Random

(

int

fReset

)

Definition at line 1004 of file utilSort.c.

{
#ifdef _MSC_VER
    static unsigned int m_z = NUMBER1;
    static unsigned int m_w = NUMBER2;
#else
    static __thread unsigned int m_z = NUMBER1;
    static __thread unsigned int m_w = NUMBER2;
#endif    
    if ( fReset )
    {
        m_z = NUMBER1;
        m_w = NUMBER2;
    }
    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);
    return (m_z << 16) + m_w;
}

Abc_RandomW()

word Abc_RandomW

(

int

fReset

)

Definition at line 1022 of file utilSort.c.

{
    return ((word)Abc_Random(fReset) << 32) | ((word)Abc_Random(fReset) << 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_Sort_rec()

void Abc_Sort_rec	(	int *	pInBeg,
		int *	pInEnd,
		int *	pOutBeg )

Function*************************************************************

Synopsis [Recursive sorting.]

Description []

SideEffects []

SeeAlso []

Definition at line 80 of file utilSort.c.

{
    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 );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_SortCost2_rec()

void Abc_SortCost2_rec	(	int *	pInBeg,
		int *	pInEnd,
		int *	pOutBeg,
		int *	pCost )

Function*************************************************************

Synopsis [Recursive sorting.]

Description []

SideEffects []

SeeAlso []

Definition at line 182 of file utilSort.c.

{
    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_SortCost2_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost );
        Abc_SortCost2_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost );
        Abc_SortMergeCost2( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost );
        memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_SortCost2Reverse_rec()

void Abc_SortCost2Reverse_rec	(	int *	pInBeg,
		int *	pInEnd,
		int *	pOutBeg,
		int *	pCost )

Function*************************************************************

Synopsis [Recursive sorting.]

Description []

SideEffects []

SeeAlso []

Definition at line 284 of file utilSort.c.

{
    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_SortCost2Reverse_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost );
        Abc_SortCost2Reverse_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost );
        Abc_SortMergeCost2Reverse( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost );
        memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_SortMerge()

ABC_NAMESPACE_IMPL_START void Abc_SortMerge	(	int *	p1Beg,
		int *	p1End,
		int *	p2Beg,
		int *	p2End,
		int *	pOut )

DECLARATIONS ///.

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

] FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Merging two lists of entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 49 of file utilSort.c.

{
    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 );
}

Here is the caller graph for this function:

Abc_SortMergeCost2()

void Abc_SortMergeCost2	(	int *	p1Beg,
		int *	p1End,
		int *	p2Beg,
		int *	p2End,
		int *	pOut,
		int *	pCost )

Function*************************************************************

Synopsis [Merging two lists of entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 151 of file utilSort.c.

{
    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 );
}

Here is the caller graph for this function:

Abc_SortMergeCost2Reverse()

void Abc_SortMergeCost2Reverse	(	int *	p1Beg,
		int *	p1End,
		int *	p2Beg,
		int *	p2End,
		int *	pOut,
		int *	pCost )

Function*************************************************************

Synopsis [Merging two lists of entries.]

Description []

SideEffects []

SeeAlso []

Definition at line 253 of file utilSort.c.

{
    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 );
}

Here is the caller graph for this function:

Abc_SortNumCompare()

int Abc_SortNumCompare	(	int *	pNum1,
		int *	pNum2 )

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 586 of file utilSort.c.

{
    return *pNum1 - *pNum2;
}

Here is the caller graph for this function:

Abc_SortTest()

void Abc_SortTest

(

)

Function*************************************************************

Synopsis [Testing the sorting procedure.]

Description []

SideEffects []

SeeAlso []

Definition at line 602 of file utilSort.c.

{
    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, (size_t)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 );
}

Here is the call graph for this function: