benchmarks/qsort/qsort_main.c

   1 //**************************************************************************
   2 // Quicksort benchmark
   3 //--------------------------------------------------------------------------
   4 //
   5 // This benchmark uses quicksort to sort an array of integers. The
   6 // implementation is largely adapted from Numerical Recipes for C. The
   7 // input data (and reference data) should be generated using the
   8 // qsort_gendata.pl perl script and dumped to a file named
   9 // dataset1.h The smips-gcc toolchain does not support system calls
  10 // so printf's can only be used on a host system, not on the smips
  11 // processor simulator itself. You should not change anything except
  12 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
  13
  14 #include "util.h"
  15
  16 // The INSERTION_THRESHOLD is the size of the subarray when the
  17 // algorithm switches to using an insertion sort instead of
  18 // quick sort.
  19
  20 #define INSERTION_THRESHOLD 7
  21
  22 // NSTACK is the required auxiliary storage.
  23 // It must be at least 2*lg(DATA_SIZE)
  24
  25 #define NSTACK 50
  26
  27 // Swap macro for swapping two values.
  28
  29 #define SWAP(a,b) temp=(a);(a)=(b);(b)=temp;
  30
  31 //--------------------------------------------------------------------------
  32 // Input/Reference Data
  33
  34 #include "dataset1.h"
  35
  36 //--------------------------------------------------------------------------
  37 // Quicksort function
  38
  39 void sort( int n, int arr[] )
  40 {
  41   int i,j,k;
  42   int ir = n;
  43   int l = 1;
  44   int jstack = 0;
  45   int a, temp;
  46
  47   int istack[NSTACK];
  48
  49   for (;;) {
  50
  51 #if HOST_DEBUG
  52     printArray( "", n, arr );
  53 #endif
  54
  55     // Insertion sort when subarray small enough.
  56     if ( ir-l < INSERTION_THRESHOLD ) {
  57
  58       for ( j = l+1; j <= ir; j++ ) {
  59         a = arr[j-1];
  60         for ( i = j-1; i >= l; i-- ) {
  61           if ( arr[i-1] <= a ) break;
  62           arr[i] = arr[i-1];
  63         }
  64         arr[i] = a;
  65       }
  66
  67       if ( jstack == 0 ) break;
  68
  69       // Pop stack and begin a new round of partitioning.
  70       ir = istack[jstack--];
  71       l = istack[jstack--];
  72
  73     }
  74     else {
  75
  76       // Choose median of left, center, and right elements as
  77       // partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
  78
  79       k = (l+ir) >> 1;
  80       SWAP(arr[k-1],arr[l])
  81       if ( arr[l-1] > arr[ir-1] ) {
  82         SWAP(arr[l-1],arr[ir-1])
  83       }
  84       if ( arr[l] > arr[ir-1] ) {
  85         SWAP(arr[l],arr[ir-1])
  86       }
  87       if ( arr[l-1] > arr[l] ) {
  88         SWAP(arr[l-1],arr[l])
  89       }
  90
  91       // Initialize pointers for partitioning.
  92       i = l+1;
  93       j = ir;
  94
  95       // Partitioning element.
  96       a = arr[l];
  97
  98       for (;;) {                       // Beginning of innermost loop.
  99         do i++; while (arr[i-1] < a);  // Scan up to find element > a.
 100         do j--; while (arr[j-1] > a);  // Scan down to find element < a.
 101         if (j < i) break;              // Pointers crossed. Partitioning complete.
 102         SWAP(arr[i-1],arr[j-1]);       // Exchange elements.
 103       }                                // End of innermost loop.
 104
 105       // Insert partitioning element.
 106       arr[l] = arr[j-1];
 107       arr[j-1] = a;
 108       jstack += 2;
 109
 110       // Push pointers to larger subarray on stack,
 111       // process smaller subarray immediately.
 112
 113 #if HOST_DEBUG
 114       if ( jstack > NSTACK ) { printf("NSTACK too small in sort.\n"); exit(1); }
 115 #endif
 116
 117       if ( ir-i+1 >= j-l ) {
 118         istack[jstack]   = ir;
 119         istack[jstack-1] = i;
 120         ir = j-1;
 121       }
 122       else {
 123         istack[jstack]   = j-1;
 124         istack[jstack-1] = l;
 125         l = i;
 126       }
 127     }
 128
 129   }
 130
 131 }
 132
 133 //--------------------------------------------------------------------------
 134 // Main
 135
 136 int main( int argc, char* argv[] )
 137 {
 138   // Output the input array
 139   printArray( "input", DATA_SIZE, input_data );
 140   printArray( "verify", DATA_SIZE, verify_data );
 141
 142 #if PREALLOCATE
 143   // If needed we preallocate everything in the caches
 144   sort( DATA_SIZE, input_data );
 145 #endif
 146
 147   // Do the sort
 148   setStats(1);
 149   sort( DATA_SIZE, input_data );
 150   setStats(0);
 151
 152   // Print out the results
 153   printArray( "test", DATA_SIZE, input_data );
 154
 155   // Check the results
 156   return verify( DATA_SIZE, input_data, verify_data );
 157 }