abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
utilSort.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [utilSort.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Merge sort with user-specified cost.]
8 
9  Synopsis [Merge sort with user-specified cost.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - Feburary 13, 2011.]
16 
17  Revision [$Id: utilSort.c,v 1.00 2011/02/11 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include <stdio.h>
22 #include <string.h>
23 #include <stdlib.h>
24 #include <assert.h>
25 
26 #include "abc_global.h"
27 
28 ABC_NAMESPACE_IMPL_START
29 
30 ////////////////////////////////////////////////////////////////////////
31 /// DECLARATIONS ///
32 ////////////////////////////////////////////////////////////////////////
33 
34 ////////////////////////////////////////////////////////////////////////
35 /// FUNCTION DEFINITIONS ///
36 ////////////////////////////////////////////////////////////////////////
37 
38 /**Function*************************************************************
39 
40  Synopsis [Merging two lists of entries.]
41 
42  Description []
43 
44  SideEffects []
45 
46  SeeAlso []
47 
48 ***********************************************************************/
49 void Abc_SortMerge( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut )
50 {
51  int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
52  int * pOutBeg = pOut;
53  while ( p1Beg < p1End && p2Beg < p2End )
54  {
55  if ( *p1Beg == *p2Beg )
56  *pOut++ = *p1Beg++, *pOut++ = *p2Beg++;
57  else if ( *p1Beg < *p2Beg )
58  *pOut++ = *p1Beg++;
59  else // if ( *p1Beg > *p2Beg )
60  *pOut++ = *p2Beg++;
61  }
62  while ( p1Beg < p1End )
63  *pOut++ = *p1Beg++;
64  while ( p2Beg < p2End )
65  *pOut++ = *p2Beg++;
66  assert( pOut - pOutBeg == nEntries );
67 }
68 
69 /**Function*************************************************************
70 
71  Synopsis [Recursive sorting.]
72 
73  Description []
74 
75  SideEffects []
76 
77  SeeAlso []
78 
79 ***********************************************************************/
80 void Abc_Sort_rec( int * pInBeg, int * pInEnd, int * pOutBeg )
81 {
82  int nSize = pInEnd - pInBeg;
83  assert( nSize > 0 );
84  if ( nSize == 1 )
85  return;
86  if ( nSize == 2 )
87  {
88  if ( pInBeg[0] > pInBeg[1] )
89  {
90  pInBeg[0] ^= pInBeg[1];
91  pInBeg[1] ^= pInBeg[0];
92  pInBeg[0] ^= pInBeg[1];
93  }
94  }
95  else if ( nSize < 8 )
96  {
97  int temp, i, j, best_i;
98  for ( i = 0; i < nSize-1; i++ )
99  {
100  best_i = i;
101  for ( j = i+1; j < nSize; j++ )
102  if ( pInBeg[j] < pInBeg[best_i] )
103  best_i = j;
104  temp = pInBeg[i];
105  pInBeg[i] = pInBeg[best_i];
106  pInBeg[best_i] = temp;
107  }
108  }
109  else
110  {
111  Abc_Sort_rec( pInBeg, pInBeg + nSize/2, pOutBeg );
112  Abc_Sort_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2 );
113  Abc_SortMerge( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg );
114  memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
115  }
116 }
117 
118 /**Function*************************************************************
119 
120  Synopsis [Returns the sorted array of integers.]
121 
122  Description [This procedure is about 10% faster than qsort().]
123 
124  SideEffects []
125 
126  SeeAlso []
127 
128 ***********************************************************************/
129 void Abc_MergeSort( int * pInput, int nSize )
130 {
131  int * pOutput;
132  if ( nSize < 2 )
133  return;
134  pOutput = (int *) malloc( sizeof(int) * nSize );
135  Abc_Sort_rec( pInput, pInput + nSize, pOutput );
136  free( pOutput );
137 }
138 
139 
140 
141 /**Function*************************************************************
142 
143  Synopsis [Merging two lists of entries.]
144 
145  Description []
146 
147  SideEffects []
148 
149  SeeAlso []
150 
151 ***********************************************************************/
152 void Abc_MergeSortCostMerge( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut )
153 {
154  int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
155  int * pOutBeg = pOut;
156  while ( p1Beg < p1End && p2Beg < p2End )
157  {
158  if ( p1Beg[1] == p2Beg[1] )
159  *pOut++ = *p1Beg++, *pOut++ = *p1Beg++, *pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
160  else if ( p1Beg[1] < p2Beg[1] )
161  *pOut++ = *p1Beg++, *pOut++ = *p1Beg++;
162  else // if ( p1Beg[1] > p2Beg[1] )
163  *pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
164  }
165  while ( p1Beg < p1End )
166  *pOut++ = *p1Beg++, *pOut++ = *p1Beg++;
167  while ( p2Beg < p2End )
168  *pOut++ = *p2Beg++, *pOut++ = *p2Beg++;
169  assert( pOut - pOutBeg == nEntries );
170 }
171 
172 /**Function*************************************************************
173 
174  Synopsis [Recursive sorting.]
175 
176  Description []
177 
178  SideEffects []
179 
180  SeeAlso []
181 
182 ***********************************************************************/
183 void Abc_MergeSortCost_rec( int * pInBeg, int * pInEnd, int * pOutBeg )
184 {
185  int nSize = (pInEnd - pInBeg)/2;
186  assert( nSize > 0 );
187  if ( nSize == 1 )
188  return;
189  if ( nSize == 2 )
190  {
191  if ( pInBeg[1] > pInBeg[3] )
192  {
193  pInBeg[1] ^= pInBeg[3];
194  pInBeg[3] ^= pInBeg[1];
195  pInBeg[1] ^= pInBeg[3];
196  pInBeg[0] ^= pInBeg[2];
197  pInBeg[2] ^= pInBeg[0];
198  pInBeg[0] ^= pInBeg[2];
199  }
200  }
201  else if ( nSize < 8 )
202  {
203  int temp, i, j, best_i;
204  for ( i = 0; i < nSize-1; i++ )
205  {
206  best_i = i;
207  for ( j = i+1; j < nSize; j++ )
208  if ( pInBeg[2*j+1] < pInBeg[2*best_i+1] )
209  best_i = j;
210  temp = pInBeg[2*i];
211  pInBeg[2*i] = pInBeg[2*best_i];
212  pInBeg[2*best_i] = temp;
213  temp = pInBeg[2*i+1];
214  pInBeg[2*i+1] = pInBeg[2*best_i+1];
215  pInBeg[2*best_i+1] = temp;
216  }
217  }
218  else
219  {
220  Abc_MergeSortCost_rec( pInBeg, pInBeg + 2*(nSize/2), pOutBeg );
221  Abc_MergeSortCost_rec( pInBeg + 2*(nSize/2), pInEnd, pOutBeg + 2*(nSize/2) );
222  Abc_MergeSortCostMerge( pInBeg, pInBeg + 2*(nSize/2), pInBeg + 2*(nSize/2), pInEnd, pOutBeg );
223  memcpy( pInBeg, pOutBeg, sizeof(int) * 2 * nSize );
224  }
225 }
226 
227 /**Function*************************************************************
228 
229  Synopsis [Sorting procedure.]
230 
231  Description [Returns permutation for the non-decreasing order of costs.]
232 
233  SideEffects []
234 
235  SeeAlso []
236 
237 ***********************************************************************/
238 int * Abc_MergeSortCost( int * pCosts, int nSize )
239 {
240  int i, * pResult, * pInput, * pOutput;
241  pResult = (int *) calloc( sizeof(int), nSize );
242  if ( nSize < 2 )
243  return pResult;
244  pInput = (int *) malloc( sizeof(int) * 2 * nSize );
245  pOutput = (int *) malloc( sizeof(int) * 2 * nSize );
246  for ( i = 0; i < nSize; i++ )
247  pInput[2*i] = i, pInput[2*i+1] = pCosts[i];
248  Abc_MergeSortCost_rec( pInput, pInput + 2*nSize, pOutput );
249  for ( i = 0; i < nSize; i++ )
250  pResult[i] = pInput[2*i];
251  free( pOutput );
252  free( pInput );
253  return pResult;
254 }
255 
256 
257 // this implementation uses 3x less memory but is 30% slower due to cache misses
258 
259 #if 0
260 
261 /**Function*************************************************************
262 
263  Synopsis [Merging two lists of entries.]
264 
265  Description []
266 
267  SideEffects []
268 
269  SeeAlso []
270 
271 ***********************************************************************/
272 void Abc_MergeSortCostMerge( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut, int * pCost )
273 {
274  int nEntries = (p1End - p1Beg) + (p2End - p2Beg);
275  int * pOutBeg = pOut;
276  while ( p1Beg < p1End && p2Beg < p2End )
277  {
278  if ( pCost[*p1Beg] == pCost[*p2Beg] )
279  *pOut++ = *p1Beg++, *pOut++ = *p2Beg++;
280  else if ( pCost[*p1Beg] < pCost[*p2Beg] )
281  *pOut++ = *p1Beg++;
282  else // if ( pCost[*p1Beg] > pCost[*p2Beg] )
283  *pOut++ = *p2Beg++;
284  }
285  while ( p1Beg < p1End )
286  *pOut++ = *p1Beg++;
287  while ( p2Beg < p2End )
288  *pOut++ = *p2Beg++;
289  assert( pOut - pOutBeg == nEntries );
290 }
291 
292 /**Function*************************************************************
293 
294  Synopsis [Recursive sorting.]
295 
296  Description []
297 
298  SideEffects []
299 
300  SeeAlso []
301 
302 ***********************************************************************/
303 void Abc_MergeSortCost_rec( int * pInBeg, int * pInEnd, int * pOutBeg, int * pCost )
304 {
305  int nSize = pInEnd - pInBeg;
306  assert( nSize > 0 );
307  if ( nSize == 1 )
308  return;
309  if ( nSize == 2 )
310  {
311  if ( pCost[pInBeg[0]] > pCost[pInBeg[1]] )
312  {
313  pInBeg[0] ^= pInBeg[1];
314  pInBeg[1] ^= pInBeg[0];
315  pInBeg[0] ^= pInBeg[1];
316  }
317  }
318  else if ( nSize < 8 )
319  {
320  int temp, i, j, best_i;
321  for ( i = 0; i < nSize-1; i++ )
322  {
323  best_i = i;
324  for ( j = i+1; j < nSize; j++ )
325  if ( pCost[pInBeg[j]] < pCost[pInBeg[best_i]] )
326  best_i = j;
327  temp = pInBeg[i];
328  pInBeg[i] = pInBeg[best_i];
329  pInBeg[best_i] = temp;
330  }
331  }
332  else
333  {
334  Abc_MergeSortCost_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost );
335  Abc_MergeSortCost_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost );
336  Abc_MergeSortCostMerge( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost );
337  memcpy( pInBeg, pOutBeg, sizeof(int) * nSize );
338  }
339 }
340 
341 /**Function*************************************************************
342 
343  Synopsis [Sorting procedure.]
344 
345  Description [Returns permutation for the non-decreasing order of costs.]
346 
347  SideEffects []
348 
349  SeeAlso []
350 
351 ***********************************************************************/
352 int * Abc_MergeSortCost( int * pCosts, int nSize )
353 {
354  int i, * pInput, * pOutput;
355  pInput = (int *) malloc( sizeof(int) * nSize );
356  for ( i = 0; i < nSize; i++ )
357  pInput[i] = i;
358  if ( nSize < 2 )
359  return pInput;
360  pOutput = (int *) malloc( sizeof(int) * nSize );
361  Abc_MergeSortCost_rec( pInput, pInput + nSize, pOutput, pCosts );
362  free( pOutput );
363  return pInput;
364 }
365 
366 #endif
367 
368 
369 
370 
371 /**Function*************************************************************
372 
373  Synopsis []
374 
375  Description []
376 
377  SideEffects []
378 
379  SeeAlso []
380 
381 ***********************************************************************/
382 int Abc_SortNumCompare( int * pNum1, int * pNum2 )
383 {
384  return *pNum1 - *pNum2;
385 }
386 
387 /**Function*************************************************************
388 
389  Synopsis [Testing the sorting procedure.]
390 
391  Description []
392 
393  SideEffects []
394 
395  SeeAlso []
396 
397 ***********************************************************************/
398 void Abc_SortTest()
399 {
400  int fUseNew = 0;
401  int i, nSize = 50000000;
402  int * pArray = (int *)malloc( sizeof(int) * nSize );
403  int * pPerm;
404  abctime clk;
405  // generate numbers
406  srand( 1000 );
407  for ( i = 0; i < nSize; i++ )
408  pArray[i] = rand();
409 
410  // try sorting
411  if ( fUseNew )
412  {
413  int fUseCost = 1;
414  if ( fUseCost )
415  {
416  clk = Abc_Clock();
417  pPerm = Abc_MergeSortCost( pArray, nSize );
418  Abc_PrintTime( 1, "New sort", Abc_Clock() - clk );
419  // check
420  for ( i = 1; i < nSize; i++ )
421  assert( pArray[pPerm[i-1]] <= pArray[pPerm[i]] );
422  free( pPerm );
423  }
424  else
425  {
426  clk = Abc_Clock();
427  Abc_MergeSort( pArray, nSize );
428  Abc_PrintTime( 1, "New sort", Abc_Clock() - clk );
429  // check
430  for ( i = 1; i < nSize; i++ )
431  assert( pArray[i-1] <= pArray[i] );
432  }
433  }
434  else
435  {
436  clk = Abc_Clock();
437  qsort( (void *)pArray, nSize, sizeof(int), (int (*)(const void *, const void *)) Abc_SortNumCompare );
438  Abc_PrintTime( 1, "Old sort", Abc_Clock() - clk );
439  // check
440  for ( i = 1; i < nSize; i++ )
441  assert( pArray[i-1] <= pArray[i] );
442  }
443 
444  free( pArray );
445 }
446 
447 
448 
449 
450 /**Function*************************************************************
451 
452  Synopsis [QuickSort algorithm as implemented by qsort().]
453 
454  Description []
455 
456  SideEffects []
457 
458  SeeAlso []
459 
460 ***********************************************************************/
461 int Abc_QuickSort1CompareInc( word * p1, word * p2 )
462 {
463  if ( (unsigned)(*p1) < (unsigned)(*p2) )
464  return -1;
465  if ( (unsigned)(*p1) > (unsigned)(*p2) )
466  return 1;
467  return 0;
468 }
469 int Abc_QuickSort1CompareDec( word * p1, word * p2 )
470 {
471  if ( (unsigned)(*p1) > (unsigned)(*p2) )
472  return -1;
473  if ( (unsigned)(*p1) < (unsigned)(*p2) )
474  return 1;
475  return 0;
476 }
477 void Abc_QuickSort1( word * pData, int nSize, int fDecrease )
478 {
479  int i, fVerify = 0;
480  if ( fDecrease )
481  {
482  qsort( (void *)pData, nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSort1CompareDec );
483  if ( fVerify )
484  for ( i = 1; i < nSize; i++ )
485  assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
486  }
487  else
488  {
489  qsort( (void *)pData, nSize, sizeof(word), (int (*)(const void *, const void *))Abc_QuickSort1CompareInc );
490  if ( fVerify )
491  for ( i = 1; i < nSize; i++ )
492  assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
493  }
494 }
495 
496 /**Function*************************************************************
497 
498  Synopsis [QuickSort algorithm based on 2/3-way partitioning.]
499 
500  Description [This code is based on the online presentation
501  "QuickSort is Optimal" by Robert Sedgewick and Jon Bentley.
502  http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf
503 
504  The first 32-bits of the input data contain values to be compared.
505  The last 32-bits contain the user's data. When sorting is finished,
506  the 64-bit words are ordered in the increasing order of their value ]
507 
508  SideEffects []
509 
510  SeeAlso []
511 
512 ***********************************************************************/
513 static inline void Abc_SelectSortInc( word * pData, int nSize )
514 {
515  int i, j, best_i;
516  for ( i = 0; i < nSize-1; i++ )
517  {
518  best_i = i;
519  for ( j = i+1; j < nSize; j++ )
520  if ( (unsigned)pData[j] < (unsigned)pData[best_i] )
521  best_i = j;
522  ABC_SWAP( word, pData[i], pData[best_i] );
523  }
524 }
525 static inline void Abc_SelectSortDec( word * pData, int nSize )
526 {
527  int i, j, best_i;
528  for ( i = 0; i < nSize-1; i++ )
529  {
530  best_i = i;
531  for ( j = i+1; j < nSize; j++ )
532  if ( (unsigned)pData[j] > (unsigned)pData[best_i] )
533  best_i = j;
534  ABC_SWAP( word, pData[i], pData[best_i] );
535  }
536 }
537 
538 void Abc_QuickSort2Inc_rec( word * pData, int l, int r )
539 {
540  word v = pData[r];
541  int i = l-1, j = r;
542  if ( l >= r )
543  return;
544  assert( l < r );
545  if ( r - l < 10 )
546  {
547  Abc_SelectSortInc( pData + l, r - l + 1 );
548  return;
549  }
550  while ( 1 )
551  {
552  while ( (unsigned)pData[++i] < (unsigned)v );
553  while ( (unsigned)v < (unsigned)pData[--j] )
554  if ( j == l )
555  break;
556  if ( i >= j )
557  break;
558  ABC_SWAP( word, pData[i], pData[j] );
559  }
560  ABC_SWAP( word, pData[i], pData[r] );
561  Abc_QuickSort2Inc_rec( pData, l, i-1 );
562  Abc_QuickSort2Inc_rec( pData, i+1, r );
563 }
564 void Abc_QuickSort2Dec_rec( word * pData, int l, int r )
565 {
566  word v = pData[r];
567  int i = l-1, j = r;
568  if ( l >= r )
569  return;
570  assert( l < r );
571  if ( r - l < 10 )
572  {
573  Abc_SelectSortDec( pData + l, r - l + 1 );
574  return;
575  }
576  while ( 1 )
577  {
578  while ( (unsigned)pData[++i] > (unsigned)v );
579  while ( (unsigned)v > (unsigned)pData[--j] )
580  if ( j == l )
581  break;
582  if ( i >= j )
583  break;
584  ABC_SWAP( word, pData[i], pData[j] );
585  }
586  ABC_SWAP( word, pData[i], pData[r] );
587  Abc_QuickSort2Dec_rec( pData, l, i-1 );
588  Abc_QuickSort2Dec_rec( pData, i+1, r );
589 }
590 
591 void Abc_QuickSort3Inc_rec( word * pData, int l, int r )
592 {
593  word v = pData[r];
594  int k, i = l-1, j = r, p = l-1, q = r;
595  if ( l >= r )
596  return;
597  assert( l < r );
598  if ( r - l < 10 )
599  {
600  Abc_SelectSortInc( pData + l, r - l + 1 );
601  return;
602  }
603  while ( 1 )
604  {
605  while ( (unsigned)pData[++i] < (unsigned)v );
606  while ( (unsigned)v < (unsigned)pData[--j] )
607  if ( j == l )
608  break;
609  if ( i >= j )
610  break;
611  ABC_SWAP( word, pData[i], pData[j] );
612  if ( (unsigned)pData[i] == (unsigned)v )
613  { p++; ABC_SWAP( word, pData[p], pData[i] ); }
614  if ( (unsigned)v == (unsigned)pData[j] )
615  { q--; ABC_SWAP( word, pData[j], pData[q] ); }
616  }
617  ABC_SWAP( word, pData[i], pData[r] );
618  j = i-1; i = i+1;
619  for ( k = l; k < p; k++, j-- )
620  ABC_SWAP( word, pData[k], pData[j] );
621  for ( k = r-1; k > q; k--, i++ )
622  ABC_SWAP( word, pData[i], pData[k] );
623  Abc_QuickSort3Inc_rec( pData, l, j );
624  Abc_QuickSort3Inc_rec( pData, i, r );
625 }
626 void Abc_QuickSort3Dec_rec( word * pData, int l, int r )
627 {
628  word v = pData[r];
629  int k, i = l-1, j = r, p = l-1, q = r;
630  if ( l >= r )
631  return;
632  assert( l < r );
633  if ( r - l < 10 )
634  {
635  Abc_SelectSortDec( pData + l, r - l + 1 );
636  return;
637  }
638  while ( 1 )
639  {
640  while ( (unsigned)pData[++i] > (unsigned)v );
641  while ( (unsigned)v > (unsigned)pData[--j] )
642  if ( j == l )
643  break;
644  if ( i >= j )
645  break;
646  ABC_SWAP( word, pData[i], pData[j] );
647  if ( (unsigned)pData[i] == (unsigned)v )
648  { p++; ABC_SWAP( word, pData[p], pData[i] ); }
649  if ( (unsigned)v == (unsigned)pData[j] )
650  { q--; ABC_SWAP( word, pData[j], pData[q] ); }
651  }
652  ABC_SWAP( word, pData[i], pData[r] );
653  j = i-1; i = i+1;
654  for ( k = l; k < p; k++, j-- )
655  ABC_SWAP( word, pData[k], pData[j] );
656  for ( k = r-1; k > q; k--, i++ )
657  ABC_SWAP( word, pData[i], pData[k] );
658  Abc_QuickSort3Dec_rec( pData, l, j );
659  Abc_QuickSort3Dec_rec( pData, i, r );
660 }
661 
662 void Abc_QuickSort2( word * pData, int nSize, int fDecrease )
663 {
664  int i, fVerify = 0;
665  if ( fDecrease )
666  {
667  Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 );
668  if ( fVerify )
669  for ( i = 1; i < nSize; i++ )
670  assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
671  }
672  else
673  {
674  Abc_QuickSort2Inc_rec( pData, 0, nSize - 1 );
675  if ( fVerify )
676  for ( i = 1; i < nSize; i++ )
677  assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
678  }
679 }
680 void Abc_QuickSort3( word * pData, int nSize, int fDecrease )
681 {
682  int i, fVerify = 1;
683  if ( fDecrease )
684  {
685  Abc_QuickSort2Dec_rec( pData, 0, nSize - 1 );
686  if ( fVerify )
687  for ( i = 1; i < nSize; i++ )
688  assert( (unsigned)pData[i-1] >= (unsigned)pData[i] );
689  }
690  else
691  {
692  Abc_QuickSort2Inc_rec( pData, 0, nSize - 1 );
693  if ( fVerify )
694  for ( i = 1; i < nSize; i++ )
695  assert( (unsigned)pData[i-1] <= (unsigned)pData[i] );
696  }
697 }
698 
699 /**Function*************************************************************
700 
701  Synopsis [Wrapper around QuickSort to sort entries based on cost.]
702 
703  Description []
704 
705  SideEffects []
706 
707  SeeAlso []
708 
709 ***********************************************************************/
710 void Abc_QuickSortCostData( int * pCosts, int nSize, int fDecrease, word * pData, int * pResult )
711 {
712  int i;
713  for ( i = 0; i < nSize; i++ )
714  pData[i] = ((word)i << 32) | pCosts[i];
715  Abc_QuickSort3( pData, nSize, fDecrease );
716  for ( i = 0; i < nSize; i++ )
717  pResult[i] = (int)(pData[i] >> 32);
718 }
719 int * Abc_QuickSortCost( int * pCosts, int nSize, int fDecrease )
720 {
721  word * pData = ABC_ALLOC( word, nSize );
722  int * pResult = ABC_ALLOC( int, nSize );
723  Abc_QuickSortCostData( pCosts, nSize, fDecrease, pData, pResult );
724  ABC_FREE( pData );
725  return pResult;
726 }
727 
728 // extern void Abc_QuickSortTest();
729 // Abc_QuickSortTest();
730 
731 /**Function*************************************************************
732 
733  Synopsis []
734 
735  Description []
736 
737  SideEffects []
738 
739  SeeAlso []
740 
741 ***********************************************************************/
742 void Abc_QuickSortTest()
743 {
744  int nSize = 1000000;
745  int fVerbose = 0;
746  word * pData1, * pData2;
747  int i;
748  abctime clk = Abc_Clock();
749  // generate numbers
750  pData1 = ABC_ALLOC( word, nSize );
751  pData2 = ABC_ALLOC( word, nSize );
752  srand( 1111 );
753  for ( i = 0; i < nSize; i++ )
754  pData2[i] = pData1[i] = ((word)i << 32) | rand();
755  Abc_PrintTime( 1, "Prepare ", Abc_Clock() - clk );
756  // perform sorting
757  clk = Abc_Clock();
758  Abc_QuickSort3( pData1, nSize, 1 );
759  Abc_PrintTime( 1, "Sort new", Abc_Clock() - clk );
760  // print the result
761  if ( fVerbose )
762  {
763  for ( i = 0; i < nSize; i++ )
764  printf( "(%d,%d) ", (int)(pData1[i] >> 32), (int)pData1[i] );
765  printf( "\n" );
766  }
767  // create new numbers
768  clk = Abc_Clock();
769  Abc_QuickSort1( pData2, nSize, 1 );
770  Abc_PrintTime( 1, "Sort old", Abc_Clock() - clk );
771  // print the result
772  if ( fVerbose )
773  {
774  for ( i = 0; i < nSize; i++ )
775  printf( "(%d,%d) ", (int)(pData2[i] >> 32), (int)pData2[i] );
776  printf( "\n" );
777  }
778  ABC_FREE( pData1 );
779  ABC_FREE( pData2 );
780 }
781 
782 
783 ////////////////////////////////////////////////////////////////////////
784 /// END OF FILE ///
785 ////////////////////////////////////////////////////////////////////////
786 
787 
788 ABC_NAMESPACE_IMPL_END
789 
malloc
char * malloc()
Abc_QuickSortCostData
void Abc_QuickSortCostData(int *pCosts, int nSize, int fDecrease, word *pData, int *pResult)
Definition: utilSort.c:710
free
VOID_HACK free()
Abc_SelectSortDec
static void Abc_SelectSortDec(word *pData, int nSize)
Definition: utilSort.c:525
Abc_QuickSortCost
int * Abc_QuickSortCost(int *pCosts, int nSize, int fDecrease)
Definition: utilSort.c:719
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Abc_Sort_rec
void Abc_Sort_rec(int *pInBeg, int *pInEnd, int *pOutBeg)
Definition: utilSort.c:80
Abc_QuickSort3Dec_rec
void Abc_QuickSort3Dec_rec(word *pData, int l, int r)
Definition: utilSort.c:626
Abc_MergeSortCost_rec
void Abc_MergeSortCost_rec(int *pInBeg, int *pInEnd, int *pOutBeg)
Definition: utilSort.c:183
Abc_QuickSort2Inc_rec
void Abc_QuickSort2Inc_rec(word *pData, int l, int r)
Definition: utilSort.c:538
Abc_MergeSortCostMerge
void Abc_MergeSortCostMerge(int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut)
Definition: utilSort.c:152
Abc_MergeSort
void Abc_MergeSort(int *pInput, int nSize)
Definition: utilSort.c:129
Abc_SortNumCompare
int Abc_SortNumCompare(int *pNum1, int *pNum2)
Definition: utilSort.c:382
memcpy
char * memcpy()
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Abc_Clock
static abctime Abc_Clock()
Definition: abc_global.h:279
Abc_SortTest
void Abc_SortTest()
Definition: utilSort.c:398
Abc_QuickSort1CompareInc
int Abc_QuickSort1CompareInc(word *p1, word *p2)
Definition: utilSort.c:461
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
Abc_SelectSortInc
static void Abc_SelectSortInc(word *pData, int nSize)
Definition: utilSort.c:513
Abc_PrintTime
static void Abc_PrintTime(int level, const char *pStr, abctime time)
Definition: abc_global.h:367
Abc_MergeSortCost
int * Abc_MergeSortCost(int *pCosts, int nSize)
Definition: utilSort.c:238
Abc_SortMerge
ABC_NAMESPACE_IMPL_START void Abc_SortMerge(int *p1Beg, int *p1End, int *p2Beg, int *p2End, int *pOut)
DECLARATIONS ///.
Definition: utilSort.c:49
Abc_QuickSort2Dec_rec
void Abc_QuickSort2Dec_rec(word *pData, int l, int r)
Definition: utilSort.c:564
Abc_QuickSort1CompareDec
int Abc_QuickSort1CompareDec(word *p1, word *p2)
Definition: utilSort.c:469
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Abc_QuickSort3Inc_rec
void Abc_QuickSort3Inc_rec(word *pData, int l, int r)
Definition: utilSort.c:591
pPerm
static int pPerm[13719]
Definition: rwrTemp.c:32
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
abc_global.h
calloc
char * calloc()
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
Abc_QuickSort2
void Abc_QuickSort2(word *pData, int nSize, int fDecrease)
Definition: utilSort.c:662
Abc_QuickSort3
void Abc_QuickSort3(word *pData, int nSize, int fDecrease)
Definition: utilSort.c:680
Abc_QuickSortTest
void Abc_QuickSortTest()
Definition: utilSort.c:742
assert
#define assert(ex)
Definition: util_old.h:213
Abc_QuickSort1
void Abc_QuickSort1(word *pData, int nSize, int fDecrease)
Definition: utilSort.c:477
abctime
ABC_INT64_T abctime
Definition: abc_global.h:278