[764b4b2] | 1 | // |
---|
[90449e4] | 2 | // The contents of this file are covered under the licence agreement in the |
---|
| 3 | // file "LICENCE" distributed with Cforall. |
---|
[764b4b2] | 4 | // |
---|
[90449e4] | 5 | // quickSort.c -- In-place concurrent quick-sort: threads are created to partition to a specific depth, then sequential |
---|
| 6 | // recursive-calls are use to sort each partition. |
---|
[764b4b2] | 7 | // |
---|
[90449e4] | 8 | // Author : Peter A. Buhr |
---|
| 9 | // Created On : Wed Dec 6 12:15:52 2017 |
---|
| 10 | // Last Modified By : Peter A. Buhr |
---|
[adb6b30f] | 11 | // Last Modified On : Thu Aug 16 08:17:41 2018 |
---|
| 12 | // Update Count : 163 |
---|
[764b4b2] | 13 | // |
---|
[90449e4] | 14 | |
---|
[73abe95] | 15 | #include <fstream.hfa> |
---|
| 16 | #include <stdlib.hfa> |
---|
| 17 | #include <kernel.hfa> |
---|
| 18 | #include <thread.hfa> |
---|
[90449e4] | 19 | #include <string.h> // strcmp |
---|
| 20 | |
---|
| 21 | thread Quicksort { |
---|
[f0322e20] | 22 | int * values; // communication variables |
---|
[90449e4] | 23 | int low, high, depth; |
---|
| 24 | }; |
---|
| 25 | |
---|
[f0322e20] | 26 | void ?{}( Quicksort & qs, int values[], int size, int depth ) { |
---|
[90449e4] | 27 | qs.values = values; qs.low = 0; qs.high = size; qs.depth = depth; |
---|
| 28 | } // Quicksort |
---|
| 29 | |
---|
[f0322e20] | 30 | void main( Quicksort & qs ) { // thread starts here |
---|
[90449e4] | 31 | // nested routines: information hiding |
---|
| 32 | |
---|
[f0322e20] | 33 | void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) { |
---|
[90449e4] | 34 | qs.values = values; qs.low = low; qs.high = high; qs.depth = depth; |
---|
| 35 | } // Quicksort |
---|
| 36 | |
---|
[f0322e20] | 37 | void sort( int values[], int low, int high, int depth ) { |
---|
[90449e4] | 38 | int left, right; // index to left/right-hand side of the values |
---|
[f0322e20] | 39 | int pivot; // pivot value of values |
---|
| 40 | int swap; // temporary |
---|
[90449e4] | 41 | |
---|
| 42 | //verify(); // check for stack overflow due to recursion |
---|
| 43 | |
---|
| 44 | // partition while 2 or more elements in the array |
---|
| 45 | if ( low < high ) { |
---|
| 46 | pivot = values[low + ( high - low ) / 2]; |
---|
| 47 | left = low; |
---|
| 48 | right = high; |
---|
| 49 | |
---|
| 50 | // partition: move values less < pivot before the pivot and values > pivot after the pivot |
---|
| 51 | do { |
---|
| 52 | while ( values[left] < pivot ) left += 1; // changed values[left] < pivot |
---|
| 53 | while ( pivot < values[right] ) right -= 1; |
---|
| 54 | if ( left <= right ) { |
---|
| 55 | swap = values[left]; // interchange values |
---|
| 56 | values[left] = values[right]; |
---|
| 57 | values[right] = swap; |
---|
| 58 | left += 1; |
---|
| 59 | right -= 1; |
---|
| 60 | } // if |
---|
| 61 | } while ( left <= right ); |
---|
| 62 | |
---|
| 63 | // restrict number of tasks to slightly greater than number of processors |
---|
| 64 | if ( depth > 0 ) { |
---|
| 65 | depth -= 1; |
---|
[f0322e20] | 66 | Quicksort rqs = { values, low, right, depth }; // concurrently sort upper half |
---|
[90449e4] | 67 | //Quicksort lqs( values, left, high, depth ); // concurrently sort lower half |
---|
| 68 | sort( values, left, high, depth ); // concurrently sort lower half |
---|
| 69 | } else { |
---|
| 70 | sort( values, low, right, 0 ); // sequentially sort lower half |
---|
| 71 | sort( values, left, high, 0 ); // sequentially sort upper half |
---|
| 72 | } // if |
---|
| 73 | } // if |
---|
| 74 | } // sort |
---|
| 75 | |
---|
| 76 | with( qs ) { |
---|
| 77 | sort( values, low, high, depth ); |
---|
| 78 | } // with |
---|
| 79 | } // main |
---|
| 80 | |
---|
| 81 | |
---|
| 82 | bool convert( int & val, const char * nptr ) { // convert C string to integer |
---|
| 83 | char * eptr; |
---|
| 84 | int temp = strto( nptr, &eptr, 10 ); // do not change val on false |
---|
| 85 | // true => entire string valid with no extra characters |
---|
| 86 | return *nptr != '\0' && *eptr == '\0' ? val = temp, true : false; |
---|
| 87 | } // convert |
---|
| 88 | |
---|
| 89 | void usage( char * argv[] ) { |
---|
| 90 | sout | "Usage:" | argv[0] | "( -s unsorted-file [ sorted-file ] | -t size (>= 0) [ depth (>= 0) ] )" | endl; |
---|
| 91 | exit( EXIT_FAILURE ); // TERMINATE! |
---|
| 92 | } // usage |
---|
| 93 | |
---|
[edb6f79] | 94 | |
---|
[90449e4] | 95 | int main( int argc, char * argv[] ) { |
---|
| 96 | ifstream & unsortedfile = sin; |
---|
| 97 | ofstream & sortedfile = sout; // default value |
---|
| 98 | int depth = 0, size; |
---|
| 99 | |
---|
| 100 | if ( argc != 1 ) { // do not use defaults |
---|
| 101 | if ( argc < 2 || argc > 4 ) usage( argv ); // wrong number of options |
---|
[c1135eef] | 102 | if ( strcmp( argv[1], "-t" ) == 0 ) { // timing ? |
---|
[f0322e20] | 103 | &unsortedfile = (ifstream *)0; // no input |
---|
[90449e4] | 104 | choose ( argc ) { |
---|
| 105 | case 4: |
---|
[f0322e20] | 106 | if ( ! convert( depth, argv[3] ) || depth < 0 ) usage( argv ); |
---|
| 107 | fallthrough; |
---|
| 108 | case 3: |
---|
| 109 | if ( ! convert( size, argv[2] ) || size < 0 ) usage( argv ); |
---|
| 110 | } // choose |
---|
| 111 | } else { // sort file |
---|
| 112 | choose ( argc ) { |
---|
| 113 | case 3: |
---|
| 114 | &sortedfile = new( (const char *)argv[2] ); // open the output file |
---|
[90449e4] | 115 | if ( fail( sortedfile ) ) { |
---|
[f0322e20] | 116 | serr | "Error! Could not open sorted output file \"" | argv[2] | "\"" | endl; |
---|
[90449e4] | 117 | usage( argv ); |
---|
| 118 | } // if |
---|
| 119 | fallthrough; |
---|
[f0322e20] | 120 | case 2: |
---|
| 121 | &unsortedfile = new( (const char *)argv[1] ); // open the input file |
---|
[90449e4] | 122 | if ( fail( unsortedfile ) ) { |
---|
[f0322e20] | 123 | serr | "Error! Could not open unsorted input file \"" | argv[1] | "\"" | endl; |
---|
[90449e4] | 124 | usage( argv ); |
---|
| 125 | } // if |
---|
| 126 | } // choose |
---|
[f0322e20] | 127 | } // if |
---|
[90449e4] | 128 | } // if |
---|
| 129 | |
---|
| 130 | enum { ValuesPerLine = 22 }; // number of values printed per line |
---|
| 131 | |
---|
| 132 | if ( &unsortedfile ) { // generate output ? |
---|
[adb6b30f] | 133 | for () { |
---|
[90449e4] | 134 | unsortedfile | size; // read number of elements in the list |
---|
| 135 | if ( eof( unsortedfile ) ) break; |
---|
[f0322e20] | 136 | int * values = alloc( size ); // values to be sorted, too large to put on stack |
---|
[90449e4] | 137 | for ( int counter = 0; counter < size; counter += 1 ) { // read unsorted numbers |
---|
| 138 | unsortedfile | values[counter]; |
---|
| 139 | if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | endl | " "; |
---|
| 140 | sortedfile | values[counter]; |
---|
| 141 | if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' '; |
---|
| 142 | } // for |
---|
| 143 | sortedfile | endl; |
---|
| 144 | if ( size > 0 ) { // values to sort ? |
---|
[f0322e20] | 145 | Quicksort QS = { values, size - 1, 0 }; // sort values |
---|
[90449e4] | 146 | } // wait until sort tasks terminate |
---|
| 147 | for ( int counter = 0; counter < size; counter += 1 ) { // print sorted list |
---|
| 148 | if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | endl | " "; |
---|
| 149 | sortedfile | values[counter]; |
---|
| 150 | if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' '; |
---|
| 151 | } // for |
---|
| 152 | sortedfile | endl | endl; |
---|
| 153 | |
---|
| 154 | delete( values ); |
---|
| 155 | } // for |
---|
| 156 | if ( &unsortedfile != &sin ) delete( &unsortedfile ); // close input/output files |
---|
| 157 | if ( &sortedfile != &sout ) delete( &sortedfile ); |
---|
| 158 | } else { |
---|
| 159 | processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads |
---|
| 160 | |
---|
[f0322e20] | 161 | int * values = alloc( size ); // values to be sorted, too large to put on stack |
---|
[90449e4] | 162 | for ( int counter = 0; counter < size; counter += 1 ) { // generate unsorted numbers |
---|
| 163 | values[counter] = size - counter; // descending values |
---|
| 164 | } // for |
---|
| 165 | { |
---|
[f0322e20] | 166 | Quicksort QS = { values, size - 1, depth }; // sort values |
---|
[90449e4] | 167 | } // wait until sort tasks terminate |
---|
| 168 | |
---|
| 169 | // for ( int counter = 0; counter < size - 1; counter += 1 ) { // check sorting |
---|
| 170 | // if ( values[counter] > values[counter + 1] ) abort(); |
---|
| 171 | // } // for |
---|
| 172 | |
---|
| 173 | delete( values ); |
---|
| 174 | } // if |
---|
| 175 | } // main |
---|
| 176 | |
---|
| 177 | // Local Variables: // |
---|
| 178 | // tab-width: 4 // |
---|
| 179 | // compile-command: "cfa quickSort.c" // |
---|
| 180 | // End: // |
---|