source: tests/concurrent/examples/quickSort.generic.cfa@ 9bb9545b

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 9bb9545b was 3aa1d22, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

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