/**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" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// 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); } /**Function************************************************************* Synopsis [This is implementation of qsort in MiniSat.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void selectionsort2(int* array, int size) { 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 (array[j] < array[best_i]) best_i = j; } tmp = array[i]; array[i] = array[best_i]; array[best_i] = tmp; } } static void sort_rec2(int* array, int size) { if (size <= 15) selectionsort2(array, size); else{ int pivot = array[size/2]; int tmp; int i = -1; int j = size; for(;;){ do i++; while(array[i] < pivot); do j--; while(pivot < array[j]); if (i >= j) break; tmp = array[i]; array[i] = array[j]; array[j] = tmp; } sort_rec2(array , i ); sort_rec2(&array[i], size-i); } } void minisat_sort2(int* array, int size) { sort_rec2(array,size); } /**Function************************************************************* Synopsis [This is implementation of qsort in MiniSat.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ 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 = 100000000; int * pArray; abctime clk = Abc_Clock(); printf( "Sorting %d integers\n", nSize ); pArray = Gia_SortGetTest( nSize ); clk = Abc_Clock(); qsort( pArray, nSize, 4, (int (*)(const void *, const void *)) num_cmp1 ); ABC_PRT( "qsort ", Abc_Clock() - clk ); Gia_SortVerifySorted( pArray, nSize ); ABC_FREE( pArray ); pArray = Gia_SortGetTest( nSize ); clk = Abc_Clock(); minisat_sort( pArray, nSize, (int (*)(const void *, const void *)) num_cmp2 ); ABC_PRT( "minisat", Abc_Clock() - clk ); Gia_SortVerifySorted( pArray, nSize ); ABC_FREE( pArray ); pArray = Gia_SortGetTest( nSize ); clk = Abc_Clock(); minisat_sort2( pArray, nSize ); ABC_PRT( "minisat with inlined comparison", Abc_Clock() - clk ); Gia_SortVerifySorted( pArray, nSize ); ABC_FREE( pArray ); } /**Function************************************************************* Synopsis [This is implementation of qsort in MiniSat.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void selectionsort3(float* array, int* perm, int size) { float tmpf; int tmpi; int i, j, best_i; for (i = 0; i < size-1; i++){ best_i = i; for (j = i+1; j < size; j++){ if (array[j] < array[best_i]) best_i = j; } tmpf = array[i]; array[i] = array[best_i]; array[best_i] = tmpf; tmpi = perm[i]; perm[i] = perm[best_i]; perm[best_i] = tmpi; } } static void sort_rec3(float* array, int* perm, int size) { if (size <= 15) selectionsort3(array, perm, size); else{ float pivot = array[size/2]; float tmpf; int tmpi; int i = -1; int j = size; for(;;){ do i++; while(array[i] < pivot); do j--; while(pivot < array[j]); if (i >= j) break; tmpf = array[i]; array[i] = array[j]; array[j] = tmpf; tmpi = perm[i]; perm[i] = perm[j]; perm[j] = tmpi; } sort_rec3(array , perm, i ); sort_rec3(&array[i], &perm[i], size-i); } } void minisat_sort3(float* array, int* perm, int size) { sort_rec3(array, perm, size); } /**Function************************************************************* Synopsis [Sorts the array of floating point numbers.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int * Gia_SortFloats( float * pArray, int * pPerm, int nSize ) { int i; if ( pPerm == NULL ) { pPerm = ABC_ALLOC( int, nSize ); for ( i = 0; i < nSize; i++ ) pPerm[i] = i; } minisat_sort3( pArray, pPerm, nSize ); // for ( i = 1; i < nSize; i++ ) // assert( pArray[i-1] <= pArray[i] ); return pPerm; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END