abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
giaSort.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [gia.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Scalable AIG package.]
8 
9  Synopsis []
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: gia.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "gia.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33 
34 /**Function*************************************************************
35 
36  Synopsis [This is implementation of qsort in MiniSat.]
37 
38  Description []
39 
40  SideEffects []
41 
42  SeeAlso []
43 
44 ***********************************************************************/
45 static int num_cmp1( int * x, int * y) { return ((*x) < (*y)) ? -1 : (((*x) > (*y)) ? 1 : 0); }
46 static int num_cmp2( int * x, int * y) { return (*x) < (*y); }
47 static inline void selectionsort(int* array, int size, int(*comp)(const void *, const void *))
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 }
60 static void sort_rec(int* array, int size, int(*comp)(const void *, const void *))
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 }
79 void minisat_sort(int* array, int size, int(*comp)(const void *, const void *))
80 {
81  sort_rec(array,size,comp);
82 }
83 
84 
85 /**Function*************************************************************
86 
87  Synopsis [This is implementation of qsort in MiniSat.]
88 
89  Description []
90 
91  SideEffects []
92 
93  SeeAlso []
94 
95 ***********************************************************************/
96 static inline void selectionsort2(int* array, int size)
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 }
109 static void sort_rec2(int* array, int size)
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 }
128 void minisat_sort2(int* array, int size)
129 {
130  sort_rec2(array,size);
131 }
132 
133 /**Function*************************************************************
134 
135  Synopsis [This is implementation of qsort in MiniSat.]
136 
137  Description []
138 
139  SideEffects []
140 
141  SeeAlso []
142 
143 ***********************************************************************/
144 int * Gia_SortGetTest( int nSize )
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 }
153 void Gia_SortVerifySorted( int * pArray, int nSize )
154 {
155  int i;
156  for ( i = 1; i < nSize; i++ )
157  assert( pArray[i-1] <= pArray[i] );
158 }
159 void Gia_SortTest()
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 }
187 
188 /**Function*************************************************************
189 
190  Synopsis [This is implementation of qsort in MiniSat.]
191 
192  Description []
193 
194  SideEffects []
195 
196  SeeAlso []
197 
198 ***********************************************************************/
199 static inline void selectionsort3(float* array, int* perm, int size)
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 }
214 static void sort_rec3(float* array, int* perm, int size)
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 }
235 void minisat_sort3(float* array, int* perm, int size)
236 {
237  sort_rec3(array, perm, size);
238 }
239 
240 /**Function*************************************************************
241 
242  Synopsis [Sorts the array of floating point numbers.]
243 
244  Description []
245 
246  SideEffects []
247 
248  SeeAlso []
249 
250 ***********************************************************************/
251 int * Gia_SortFloats( float * pArray, int * pPerm, int nSize )
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 }
265 
266 
267 ////////////////////////////////////////////////////////////////////////
268 /// END OF FILE ///
269 ////////////////////////////////////////////////////////////////////////
270 
271 
272 ABC_NAMESPACE_IMPL_END
273 
Gia_SortTest
void Gia_SortTest()
Definition: giaSort.c:159
selectionsort3
static void selectionsort3(float *array, int *perm, int size)
Definition: giaSort.c:199
selectionsort
static void selectionsort(int *array, int size, int(*comp)(const void *, const void *))
Definition: giaSort.c:47
minisat_sort
void minisat_sort(int *array, int size, int(*comp)(const void *, const void *))
Definition: giaSort.c:79
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
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
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
size
static int size
Definition: cuddSign.c:86
pPerm
static int pPerm[13719]
Definition: rwrTemp.c:32
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Gia_SortFloats
int * Gia_SortFloats(float *pArray, int *pPerm, int nSize)
Definition: giaSort.c:251
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
selectionsort2
static void selectionsort2(int *array, int size)
Definition: giaSort.c:96
num_cmp2
static int num_cmp2(int *x, int *y)
Definition: giaSort.c:46
sort_rec3
static void sort_rec3(float *array, int *perm, int size)
Definition: giaSort.c:214
assert
#define assert(ex)
Definition: util_old.h:213
sort_rec
static void sort_rec(int *array, int size, int(*comp)(const void *, const void *))
Definition: giaSort.c:60
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278
sort_rec2
static void sort_rec2(int *array, int size)
Definition: giaSort.c:109
num_cmp1
static ABC_NAMESPACE_IMPL_START int num_cmp1(int *x, int *y)
DECLARATIONS ///.
Definition: giaSort.c:45