diff options
Diffstat (limited to 'src/misc/util')
-rw-r--r-- | src/misc/util/abc_global.h | 1 | ||||
-rw-r--r-- | src/misc/util/utilNam.c | 2 | ||||
-rw-r--r-- | src/misc/util/utilSort.c | 101 |
3 files changed, 103 insertions, 1 deletions
diff --git a/src/misc/util/abc_global.h b/src/misc/util/abc_global.h index 34bd5057..f6076399 100644 --- a/src/misc/util/abc_global.h +++ b/src/misc/util/abc_global.h @@ -515,6 +515,7 @@ static inline void Abc_ReverseOrder( int * pA, int nA ) // sorting extern void Abc_MergeSort( int * pInput, int nSize ); extern int * Abc_MergeSortCost( int * pCosts, int nSize ); +extern void Abc_MergeSortCost2( int * pInput, int nSize, int * pCost ); extern void Abc_QuickSort1( word * pData, int nSize, int fDecrease ); extern void Abc_QuickSort2( word * pData, int nSize, int fDecrease ); extern void Abc_QuickSort3( word * pData, int nSize, int fDecrease ); diff --git a/src/misc/util/utilNam.c b/src/misc/util/utilNam.c index b1d2702c..f6539f03 100644 --- a/src/misc/util/utilNam.c +++ b/src/misc/util/utilNam.c @@ -164,7 +164,7 @@ void Abc_NamSave( Abc_Nam_t * p, char * pFileName ) Abc_Nam_t * Abc_NamLoad( char * pFileName ) { Abc_Nam_t * p; - int fFound, NameId, nLineSize = 1 << 20; + int fFound, NameId = -1, nLineSize = 1 << 20; char * pBuffer = ABC_ALLOC( char, nLineSize+1 ); FILE * pFile = fopen( pFileName, "rb" ); if ( pFile == NULL ) { printf( "Count node open output file %s\n", pFileName ); return NULL; } diff --git a/src/misc/util/utilSort.c b/src/misc/util/utilSort.c index 31890503..679017ed 100644 --- a/src/misc/util/utilSort.c +++ b/src/misc/util/utilSort.c @@ -137,6 +137,107 @@ void Abc_MergeSort( int * pInput, int nSize ) } +/**Function************************************************************* + + Synopsis [Merging two lists of entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SortMergeCost2( 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_SortCost2_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_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 ); + } +} + +/**Function************************************************************* + + Synopsis [Returns the sorted array of integers.] + + Description [This procedure is about 10% faster than qsort().] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_MergeSortCost2( int * pInput, int nSize, int * pCost ) +{ + int * pOutput; + if ( nSize < 2 ) + return; + pOutput = (int *) malloc( sizeof(int) * nSize ); + Abc_SortCost2_rec( pInput, pInput + nSize, pOutput, pCost ); + free( pOutput ); +} + /**Function************************************************************* |