source: src/tests/concurrent/examples/quickSort.c@ 2db79e5

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since 2db79e5 was 90449e4, checked in by Peter A. Buhr <pabuhr@…>, 8 years ago

add concurrent quick-sort example
  • Property mode set to 100644
File size: 6.3 KB
RevLine 
[90449e4]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 : Mon Dec 11 17:00:25 2017
12// Update Count : 126
13//
14
15#include <fstream>
16#include <stdlib>
17#include <kernel>
18#include <thread>
19#include <string.h> // strcmp
20
21thread Quicksort {
22 int * values; // communication variables
23 int low, high, depth;
24};
25
26void ?{}( Quicksort & qs, int values[], int size, int depth ) {
27 qs.values = values; qs.low = 0; qs.high = size; qs.depth = depth;
28} // Quicksort
29
30void main( Quicksort & qs ) {
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 //sout << &uThisTask() << " " << depth << endl;
67 Quicksort rqs = { values, low, right, depth }; // concurrently sort upper half
68 //Quicksort lqs( values, left, high, depth ); // concurrently sort lower half
69 sort( values, left, high, depth ); // concurrently sort lower half
70 } else {
71 sort( values, low, right, 0 ); // sequentially sort lower half
72 sort( values, left, high, 0 ); // sequentially sort upper half
73 } // if
74 } // if
75 } // sort
76
77 with( qs ) {
78 sort( values, low, high, depth );
79 } // with
80} // main
81
82
83bool convert( int & val, const char * nptr ) { // convert C string to integer
84 char * eptr;
85 int temp = strto( nptr, &eptr, 10 ); // do not change val on false
86 // true => entire string valid with no extra characters
87 return *nptr != '\0' && *eptr == '\0' ? val = temp, true : false;
88} // convert
89
90void usage( char * argv[] ) {
91 sout | "Usage:" | argv[0] | "( -s unsorted-file [ sorted-file ] | -t size (>= 0) [ depth (>= 0) ] )" | endl;
92 exit( EXIT_FAILURE ); // TERMINATE!
93} // usage
94
95int 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], "-s" ) == 0 ) {
103 choose ( argc ) {
104 case 4:
105 &sortedfile = new( (const char *)argv[3] ); // open the output file
106 if ( fail( sortedfile ) ) {
107 serr | "Error! Could not open sorted output file \"" | argv[3] | "\"" | endl;
108 usage( argv );
109 } // if
110 fallthrough;
111 case 3:
112 &unsortedfile = new( (const char *)argv[2] ); // open the input file
113 if ( fail( unsortedfile ) ) {
114 serr | "Error! Could not open unsorted input file \"" | argv[2] | "\"" | endl;
115 usage( argv );
116 } // if
117 } // choose
118 } else if ( strcmp( argv[1], "-t" ) == 0 ) {
119 unsortedfile = *(ifstream *)0; // no input
120 choose ( argc ) {
121 case 4:
122 if ( ! convert( depth, argv[3] ) || depth < 0 ) usage( argv );
123 fallthrough;
124 case 3:
125 if ( ! convert( size, argv[2] ) || size < 0 ) usage( argv );
126 } // choose
127 } else usage( argv ); // invalid flag
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 = anew( 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 = anew( 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: //
Note: See TracBrowser for help on using the repository browser.