1 | // |
---|
2 | // The contents of this file are covered under the licence agreement in the |
---|
3 | // file "LICENCE" distributed with Cforall. |
---|
4 | // |
---|
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. |
---|
7 | // |
---|
8 | // Author : Peter A. Buhr |
---|
9 | // Created On : Wed Dec 6 12:15:52 2017 |
---|
10 | // Last Modified By : Peter A. Buhr |
---|
11 | // Last Modified On : Tue Jan 30 15:58:58 2018 |
---|
12 | // Update Count : 162 |
---|
13 | // |
---|
14 | |
---|
15 | #include <fstream.hfa> |
---|
16 | #include <stdlib.hfa> |
---|
17 | #include <kernel.hfa> |
---|
18 | #include <thread.hfa> |
---|
19 | #include <string.h> // strcmp |
---|
20 | |
---|
21 | thread Quicksort { |
---|
22 | int * values; // communication variables |
---|
23 | int low, high, depth; |
---|
24 | }; |
---|
25 | |
---|
26 | void ?{}( Quicksort & qs, int values[], int size, int depth ) { |
---|
27 | qs.values = values; qs.low = 0; qs.high = size; qs.depth = depth; |
---|
28 | } // Quicksort |
---|
29 | |
---|
30 | void main( Quicksort & qs ) { // thread starts here |
---|
31 | // nested routines: information hiding |
---|
32 | |
---|
33 | void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) { |
---|
34 | qs.values = values; qs.low = low; qs.high = high; qs.depth = depth; |
---|
35 | } // Quicksort |
---|
36 | |
---|
37 | void sort( int values[], int low, int high, int depth ) { |
---|
38 | int left, right; // index to left/right-hand side of the values |
---|
39 | int pivot; // pivot value of values |
---|
40 | int swap; // temporary |
---|
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; |
---|
66 | Quicksort rqs = { values, low, right, depth }; // concurrently sort upper half |
---|
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 | |
---|
94 | |
---|
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 |
---|
102 | if ( strcmp( argv[1], "-t" ) == 0 ) { // timing ? |
---|
103 | &unsortedfile = (ifstream *)0; // no input |
---|
104 | choose ( argc ) { |
---|
105 | case 4: |
---|
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 |
---|
115 | if ( fail( sortedfile ) ) { |
---|
116 | serr | "Error! Could not open sorted output file \"" | argv[2] | "\"" | endl; |
---|
117 | usage( argv ); |
---|
118 | } // if |
---|
119 | fallthrough; |
---|
120 | case 2: |
---|
121 | &unsortedfile = new( (const char *)argv[1] ); // open the input file |
---|
122 | if ( fail( unsortedfile ) ) { |
---|
123 | serr | "Error! Could not open unsorted input file \"" | argv[1] | "\"" | endl; |
---|
124 | usage( argv ); |
---|
125 | } // if |
---|
126 | } // choose |
---|
127 | } // if |
---|
128 | } // if |
---|
129 | |
---|
130 | enum { ValuesPerLine = 22 }; // number of values printed per line |
---|
131 | |
---|
132 | if ( &unsortedfile ) { // generate output ? |
---|
133 | for ( ;; ) { |
---|
134 | unsortedfile | size; // read number of elements in the list |
---|
135 | if ( eof( unsortedfile ) ) break; |
---|
136 | int * values = alloc( size ); // values to be sorted, too large to put on stack |
---|
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 ? |
---|
145 | Quicksort QS = { values, size - 1, 0 }; // sort values |
---|
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 | |
---|
161 | int * values = alloc( size ); // values to be sorted, too large to put on stack |
---|
162 | for ( int counter = 0; counter < size; counter += 1 ) { // generate unsorted numbers |
---|
163 | values[counter] = size - counter; // descending values |
---|
164 | } // for |
---|
165 | { |
---|
166 | Quicksort QS = { values, size - 1, depth }; // sort values |
---|
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: // |
---|