source: tests/concurrent/examples/quickSort.cfa@ c802eb88

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr no_list persistent-indexer pthread-emulation qualifiedEnum
Last change on this file since c802eb88 was 25cdca5, checked in by Thierry Delisle <tdelisle@…>, 7 years ago

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc
  • Property mode set to 100644
File size: 6.2 KB
Line 
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 : Sat Dec 22 08:44:27 2018
12// Update Count : 168
13//
14
15#include <fstream.hfa>
16#include <stdlib.hfa>
17#include <kernel.hfa>
18#include <thread.hfa>
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 ) { // 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
82bool 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
89void usage( char * argv[] ) {
90 sout | "Usage:" | argv[0] | "( -s unsorted-file [ sorted-file ] | -t size (>= 0) [ depth (>= 0) ] )";
91 exit( EXIT_FAILURE ); // TERMINATE!
92} // usage
93
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], "-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] | "\"";
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] | "\"";
124 usage( argv );
125 } // if
126 } // choose
127 } // if
128 } // if
129 sortedfile | nlOff; // turn off auto newline
130
131 enum { ValuesPerLine = 22 }; // number of values printed per line
132
133 if ( &unsortedfile ) { // generate output ?
134 for () {
135 unsortedfile | size; // read number of elements in the list
136 if ( eof( unsortedfile ) ) break;
137 int * values = alloc( size ); // values to be sorted, too large to put on stack
138 for ( int counter = 0; counter < size; counter += 1 ) { // read unsorted numbers
139 unsortedfile | values[counter];
140 if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " ";
141 sortedfile | values[counter];
142 if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
143 } // for
144 sortedfile | nl;
145 if ( size > 0 ) { // values to sort ?
146 Quicksort QS = { values, size - 1, 0 }; // sort values
147 } // wait until sort tasks terminate
148 for ( int counter = 0; counter < size; counter += 1 ) { // print sorted list
149 if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | " ";
150 sortedfile | values[counter];
151 if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
152 } // for
153 sortedfile | nl | nl;
154
155 delete( values );
156 } // for
157 if ( &unsortedfile != &sin ) delete( &unsortedfile ); // close input/output files
158 if ( &sortedfile != &sout ) delete( &sortedfile );
159 } else {
160 processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads
161
162 int * values = alloc( size ); // values to be sorted, too large to put on stack
163 for ( int counter = 0; counter < size; counter += 1 ) { // generate unsorted numbers
164 values[counter] = size - counter; // descending values
165 } // for
166 {
167 Quicksort QS = { values, size - 1, depth }; // sort values
168 } // wait until sort tasks terminate
169
170 // for ( int counter = 0; counter < size - 1; counter += 1 ) { // check sorting
171 // if ( values[counter] > values[counter + 1] ) abort();
172 // } // for
173
174 delete( values );
175 } // if
176} // main
177
178// Local Variables: //
179// tab-width: 4 //
180// compile-command: "cfa quickSort.c" //
181// End: //
Note: See TracBrowser for help on using the repository browser.