abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
giaSort.c File Reference
#include "gia.h"

Go to the source code of this file.

Functions

static ABC_NAMESPACE_IMPL_START int num_cmp1 (int *x, int *y)
 DECLARATIONS ///. More...
 
static int num_cmp2 (int *x, int *y)
 
static void selectionsort (int *array, int size, int(*comp)(const void *, const void *))
 
static void sort_rec (int *array, int size, int(*comp)(const void *, const void *))
 
void minisat_sort (int *array, int size, int(*comp)(const void *, const void *))
 
static void selectionsort2 (int *array, int size)
 
static void sort_rec2 (int *array, int size)
 
void minisat_sort2 (int *array, int size)
 
int * Gia_SortGetTest (int nSize)
 
void Gia_SortVerifySorted (int *pArray, int nSize)
 
void Gia_SortTest ()
 
static void selectionsort3 (float *array, int *perm, int size)
 
static void sort_rec3 (float *array, int *perm, int size)
 
void minisat_sort3 (float *array, int *perm, int size)
 
int * Gia_SortFloats (float *pArray, int *pPerm, int nSize)
 

Function Documentation

int* Gia_SortFloats ( float *  pArray,
int *  pPerm,
int  nSize 
)

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

Synopsis [Sorts the array of floating point numbers.]

Description []

SideEffects []

SeeAlso []

Definition at line 251 of file giaSort.c.

252 {
253  int i;
254  if ( pPerm == NULL )
255  {
256  pPerm = ABC_ALLOC( int, nSize );
257  for ( i = 0; i < nSize; i++ )
258  pPerm[i] = i;
259  }
260  minisat_sort3( pArray, pPerm, nSize );
261 // for ( i = 1; i < nSize; i++ )
262 // assert( pArray[i-1] <= pArray[i] );
263  return pPerm;
264 }
minisat_sort3
void minisat_sort3(float *array, int *perm, int size)
Definition: giaSort.c:235
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
pPerm
static int pPerm[13719]
Definition: rwrTemp.c:32
int* Gia_SortGetTest ( int  nSize)

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

Synopsis [This is implementation of qsort in MiniSat.]

Description []

SideEffects []

SeeAlso []

Definition at line 144 of file giaSort.c.

145 {
146  int i, * pArray;
147  srand( 0 );
148  pArray = ABC_ALLOC( int, nSize );
149  for ( i = 0; i < nSize; i++ )
150  pArray[i] = rand();
151  return pArray;
152 }
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
void Gia_SortTest ( )

Definition at line 159 of file giaSort.c.

160 {
161  int nSize = 100000000;
162  int * pArray;
163  abctime clk = Abc_Clock();
164 
165  printf( "Sorting %d integers\n", nSize );
166  pArray = Gia_SortGetTest( nSize );
167 clk = Abc_Clock();
168  qsort( pArray, nSize, 4, (int (*)(const void *, const void *)) num_cmp1 );
169 ABC_PRT( "qsort ", Abc_Clock() - clk );
170  Gia_SortVerifySorted( pArray, nSize );
171  ABC_FREE( pArray );
172 
173  pArray = Gia_SortGetTest( nSize );
174 clk = Abc_Clock();
175  minisat_sort( pArray, nSize, (int (*)(const void *, const void *)) num_cmp2 );
176 ABC_PRT( "minisat", Abc_Clock() - clk );
177  Gia_SortVerifySorted( pArray, nSize );
178  ABC_FREE( pArray );
179 
180  pArray = Gia_SortGetTest( nSize );
181 clk = Abc_Clock();
182  minisat_sort2( pArray, nSize );
183 ABC_PRT( "minisat with inlined comparison", Abc_Clock() - clk );
184  Gia_SortVerifySorted( pArray, nSize );
185  ABC_FREE( pArray );
186 }
minisat_sort
void minisat_sort(int *array, int size, int(*comp)(const void *, const void *))
Definition: giaSort.c:79
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Gia_SortGetTest
int * Gia_SortGetTest(int nSize)
Definition: giaSort.c:144
Gia_SortVerifySorted
void Gia_SortVerifySorted(int *pArray, int nSize)
Definition: giaSort.c:153
minisat_sort2
void minisat_sort2(int *array, int size)
Definition: giaSort.c:128
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
ABC_PRT
#define ABC_PRT(a, t)
Definition: abc_global.h:220
num_cmp2
static int num_cmp2(int *x, int *y)
Definition: giaSort.c:46
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
num_cmp1
static ABC_NAMESPACE_IMPL_START int num_cmp1(int *x, int *y)
DECLARATIONS ///.
Definition: giaSort.c:45
void Gia_SortVerifySorted ( int *  pArray,
int  nSize 
)

Definition at line 153 of file giaSort.c.

154 {
155  int i;
156  for ( i = 1; i < nSize; i++ )
157  assert( pArray[i-1] <= pArray[i] );
158 }
assert
#define assert(ex)
Definition: util_old.h:213
void minisat_sort ( int *  array,
int  size,
int(*)(const void *, const void *)  comp 
)

Definition at line 79 of file giaSort.c.

80 {
81  sort_rec(array,size,comp);
82 }
size
static int size
Definition: cuddSign.c:86
sort_rec
static void sort_rec(int *array, int size, int(*comp)(const void *, const void *))
Definition: giaSort.c:60
void minisat_sort2 ( int *  array,
int  size 
)

Definition at line 128 of file giaSort.c.

129 {
130  sort_rec2(array,size);
131 }
size
static int size
Definition: cuddSign.c:86
sort_rec2
static void sort_rec2(int *array, int size)
Definition: giaSort.c:109
void minisat_sort3 ( float *  array,
int *  perm,
int  size 
)

Definition at line 235 of file giaSort.c.

236 {
237  sort_rec3(array, perm, size);
238 }
size
static int size
Definition: cuddSign.c:86
sort_rec3
static void sort_rec3(float *array, int *perm, int size)
Definition: giaSort.c:214
static ABC_NAMESPACE_IMPL_START int num_cmp1 ( int *  x,
int *  y 
)
static

DECLARATIONS ///.

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

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

Synopsis [This is implementation of qsort in MiniSat.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file giaSort.c.

45 { return ((*x) < (*y)) ? -1 : (((*x) > (*y)) ? 1 : 0); }
static int num_cmp2 ( int *  x,
int *  y 
)
static

Definition at line 46 of file giaSort.c.

46 { return (*x) < (*y); }
static void selectionsort ( int *  array,
int  size,
int(*)(const void *, const void *)  comp 
)
inlinestatic

Definition at line 47 of file giaSort.c.

48 {
49  int i, j, best_i;
50  int tmp;
51  for (i = 0; i < size-1; i++){
52  best_i = i;
53  for (j = i+1; j < size; j++){
54  if (comp(array + j, array + best_i))
55  best_i = j;
56  }
57  tmp = array[i]; array[i] = array[best_i]; array[best_i] = tmp;
58  }
59 }
size
static int size
Definition: cuddSign.c:86
static void selectionsort2 ( int *  array,
int  size 
)
inlinestatic

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

Synopsis [This is implementation of qsort in MiniSat.]

Description []

SideEffects []

SeeAlso []

Definition at line 96 of file giaSort.c.

97 {
98  int i, j, best_i;
99  int tmp;
100  for (i = 0; i < size-1; i++){
101  best_i = i;
102  for (j = i+1; j < size; j++){
103  if (array[j] < array[best_i])
104  best_i = j;
105  }
106  tmp = array[i]; array[i] = array[best_i]; array[best_i] = tmp;
107  }
108 }
size
static int size
Definition: cuddSign.c:86
static void selectionsort3 ( float *  array,
int *  perm,
int  size 
)
inlinestatic

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

Synopsis [This is implementation of qsort in MiniSat.]

Description []

SideEffects []

SeeAlso []

Definition at line 199 of file giaSort.c.

200 {
201  float tmpf;
202  int tmpi;
203  int i, j, best_i;
204  for (i = 0; i < size-1; i++){
205  best_i = i;
206  for (j = i+1; j < size; j++){
207  if (array[j] < array[best_i])
208  best_i = j;
209  }
210  tmpf = array[i]; array[i] = array[best_i]; array[best_i] = tmpf;
211  tmpi = perm[i]; perm[i] = perm[best_i]; perm[best_i] = tmpi;
212  }
213 }
size
static int size
Definition: cuddSign.c:86
static void sort_rec ( int *  array,
int  size,
int(*)(const void *, const void *)  comp 
)
static

Definition at line 60 of file giaSort.c.

61 {
62  if (size <= 15)
63  selectionsort(array, size, comp);
64  else{
65  int pivot = array[size/2];
66  int tmp;
67  int i = -1;
68  int j = size;
69  for(;;){
70  do i++; while(comp(array + i, &pivot));
71  do j--; while(comp(&pivot, array + j));
72  if (i >= j) break;
73  tmp = array[i]; array[i] = array[j]; array[j] = tmp;
74  }
75  sort_rec(array , i , comp);
76  sort_rec(&array[i], size-i, comp);
77  }
78 }
selectionsort
static void selectionsort(int *array, int size, int(*comp)(const void *, const void *))
Definition: giaSort.c:47
size
static int size
Definition: cuddSign.c:86
sort_rec
static void sort_rec(int *array, int size, int(*comp)(const void *, const void *))
Definition: giaSort.c:60
static void sort_rec2 ( int *  array,
int  size 
)
static

Definition at line 109 of file giaSort.c.

110 {
111  if (size <= 15)
112  selectionsort2(array, size);
113  else{
114  int pivot = array[size/2];
115  int tmp;
116  int i = -1;
117  int j = size;
118  for(;;){
119  do i++; while(array[i] < pivot);
120  do j--; while(pivot < array[j]);
121  if (i >= j) break;
122  tmp = array[i]; array[i] = array[j]; array[j] = tmp;
123  }
124  sort_rec2(array , i );
125  sort_rec2(&array[i], size-i);
126  }
127 }
size
static int size
Definition: cuddSign.c:86
selectionsort2
static void selectionsort2(int *array, int size)
Definition: giaSort.c:96
sort_rec2
static void sort_rec2(int *array, int size)
Definition: giaSort.c:109
static void sort_rec3 ( float *  array,
int *  perm,
int  size 
)
static

Definition at line 214 of file giaSort.c.

215 {
216  if (size <= 15)
217  selectionsort3(array, perm, size);
218  else{
219  float pivot = array[size/2];
220  float tmpf;
221  int tmpi;
222  int i = -1;
223  int j = size;
224  for(;;){
225  do i++; while(array[i] < pivot);
226  do j--; while(pivot < array[j]);
227  if (i >= j) break;
228  tmpf = array[i]; array[i] = array[j]; array[j] = tmpf;
229  tmpi = perm[i]; perm[i] = perm[j]; perm[j] = tmpi;
230  }
231  sort_rec3(array , perm, i );
232  sort_rec3(&array[i], &perm[i], size-i);
233  }
234 }
selectionsort3
static void selectionsort3(float *array, int *perm, int size)
Definition: giaSort.c:199
size
static int size
Definition: cuddSign.c:86
sort_rec3
static void sort_rec3(float *array, int *perm, int size)
Definition: giaSort.c:214