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

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 2fdbb3b was c1135eef, checked in by Peter A. Buhr <pabuhr@…>, 8 years ago

restore call to strcmp
  • 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 : Tue Jan 30 15:58:58 2018
12// Update Count : 162
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 ) { // 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) ] )" | endl;
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] | "\"" | 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: //
Note: See TracBrowser for help on using the repository browser.