diff options
Diffstat (limited to 'src/aig/gia/giaSort.c')
-rw-r--r-- | src/aig/gia/giaSort.c | 122 |
1 files changed, 122 insertions, 0 deletions
diff --git a/src/aig/gia/giaSort.c b/src/aig/gia/giaSort.c new file mode 100644 index 00000000..6986bc47 --- /dev/null +++ b/src/aig/gia/giaSort.c @@ -0,0 +1,122 @@ +/**CFile**************************************************************** + + FileName [gia.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Scalable AIG package.] + + Synopsis [] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: gia.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "gia.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [This is implementation of qsort in MiniSat.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static int num_cmp1( int * x, int * y) { return ((*x) < (*y)) ? -1 : (((*x) > (*y)) ? 1 : 0); } +static int num_cmp2( int * x, int * y) { return (*x) < (*y); } +static inline void selectionsort(int* array, int size, int(*comp)(const void *, const void *)) +{ + int i, j, best_i; + int tmp; + for (i = 0; i < size-1; i++){ + best_i = i; + for (j = i+1; j < size; j++){ + if (comp(array + j, array + best_i)) + best_i = j; + } + tmp = array[i]; array[i] = array[best_i]; array[best_i] = tmp; + } +} +static void sort_rec(int* array, int size, int(*comp)(const void *, const void *)) +{ + if (size <= 15) + selectionsort(array, size, comp); + else{ + int * pivot = array + size/2; + int tmp; + int i = -1; + int j = size; + for(;;){ + do i++; while(comp(array + i, pivot)); + do j--; while(comp(pivot, array + j)); + if (i >= j) break; + tmp = array[i]; array[i] = array[j]; array[j] = tmp; + } + sort_rec(array , i , comp); + sort_rec(&array[i], size-i, comp); + } +} +void minisat_sort(int* array, int size, int(*comp)(const void *, const void *)) +{ + sort_rec(array,size,comp); +} + + +int * Gia_SortGetTest( int nSize ) +{ + int i, * pArray; + srand( 0 ); + pArray = ABC_ALLOC( int, nSize ); + for ( i = 0; i < nSize; i++ ) + pArray[i] = rand(); + return pArray; +} +void Gia_SortVerifySorted( int * pArray, int nSize ) +{ + int i; + for ( i = 1; i < nSize; i++ ) + assert( pArray[i-1] <= pArray[i] ); +} +void Gia_SortTest() +{ + int nSize = 1000000; + int * pArray; + int clk = clock(); + + pArray = Gia_SortGetTest( nSize ); +clk = clock(); + qsort( pArray, nSize, 4, (int (*)(const void *, const void *)) num_cmp1 ); +ABC_PRT( "qsort ", clock() - clk ); + Gia_SortVerifySorted( pArray, nSize ); + ABC_FREE( pArray ); + + pArray = Gia_SortGetTest( nSize ); +clk = clock(); + minisat_sort( pArray, nSize, (int (*)(const void *, const void *)) num_cmp2 ); +ABC_PRT( "minisat", clock() - clk ); + Gia_SortVerifySorted( pArray, nSize ); + ABC_FREE( pArray ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |