source: src/tests/concurrent/examples/quickSort.c@ 59073fd

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 59073fd was edb6f79, checked in by Peter A. Buhr <pabuhr@…>, 8 years ago

generic quicksort, not working
  • Property mode set to 100644
File size: 6.4 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 : Wed Dec 13 18:20:18 2017
12// Update Count : 138
13//
14
15#include <fstream>
16#include <stdlib>
17#include <kernel>
18#include <thread>
19#include <string.h> // strcmp
20
21forall( otype T | { T ?<?( T, T ); } )
22thread Quicksort {
23 T * values; // communication variables
24 int low, high, depth;
25};
26
27forall( otype T | { T ?<?( T, T ); } )
28void ?{}( Quicksort(T) & qs, T values[], int size, int depth ) {
29 qs.values = values; qs.low = 0; qs.high = size; qs.depth = depth;
30} // Quicksort
31
32forall( otype T | { T ?<?( T, T ); } )
33void main( Quicksort(T) & qs ) {
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 //sout << &uThisTask() << " " << depth << endl;
70 Quicksort(T) rqs = { values, low, right, depth }; // concurrently sort upper half
71 //Quicksort lqs( values, left, high, depth ); // concurrently sort lower half
72 sort( values, left, high, depth ); // concurrently sort lower half
73 } else {
74 sort( values, low, right, 0 ); // sequentially sort lower half
75 sort( values, left, high, 0 ); // sequentially sort upper half
76 } // if
77 } // if
78 } // sort
79
80 with( qs ) {
81 sort( values, low, high, depth );
82 } // with
83} // main
84
85
86bool convert( int & val, const char * nptr ) { // convert C string to integer
87 char * eptr;
88 int temp = strto( nptr, &eptr, 10 ); // do not change val on false
89 // true => entire string valid with no extra characters
90 return *nptr != '\0' && *eptr == '\0' ? val = temp, true : false;
91} // convert
92
93void usage( char * argv[] ) {
94 sout | "Usage:" | argv[0] | "( -s unsorted-file [ sorted-file ] | -t size (>= 0) [ depth (>= 0) ] )" | endl;
95 exit( EXIT_FAILURE ); // TERMINATE!
96} // usage
97
98
99#define ELEMTYPE int
100
101int main( int argc, char * argv[] ) {
102 ifstream & unsortedfile = sin;
103 ofstream & sortedfile = sout; // default value
104 int depth = 0, size;
105
106 if ( argc != 1 ) { // do not use defaults
107 if ( argc < 2 || argc > 4 ) usage( argv ); // wrong number of options
108 if ( strcmp( argv[1], "-s" ) == 0 ) {
109 choose ( argc ) {
110 case 4:
111 &sortedfile = new( (const char *)argv[3] ); // open the output file
112 if ( fail( sortedfile ) ) {
113 serr | "Error! Could not open sorted output file \"" | argv[3] | "\"" | endl;
114 usage( argv );
115 } // if
116 fallthrough;
117 case 3:
118 &unsortedfile = new( (const char *)argv[2] ); // open the input file
119 if ( fail( unsortedfile ) ) {
120 serr | "Error! Could not open unsorted input file \"" | argv[2] | "\"" | endl;
121 usage( argv );
122 } // if
123 } // choose
124 } else if ( strcmp( argv[1], "-t" ) == 0 ) {
125 unsortedfile = *(ifstream *)0; // no input
126 choose ( argc ) {
127 case 4:
128 if ( ! convert( depth, argv[3] ) || depth < 0 ) usage( argv );
129 fallthrough;
130 case 3:
131 if ( ! convert( size, argv[2] ) || size < 0 ) usage( argv );
132 } // choose
133 } else usage( argv ); // invalid flag
134 } // if
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 = anew( size ); // values to be sorted, too large to put on stack
143 for ( int counter = 0; counter < size; counter += 1 ) { // read unsorted numbers
144 unsortedfile | values[counter];
145 if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | endl | " ";
146 sortedfile | values[counter];
147 if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
148 } // for
149 sortedfile | endl;
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 ( int counter = 0; counter < size; counter += 1 ) { // print sorted list
154 if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | endl | " ";
155 sortedfile | values[counter];
156 if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
157 } // for
158 sortedfile | endl | endl;
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 = anew( size ); // values to be sorted, too large to put on stack
168 for ( int counter = 0; counter < size; counter += 1 ) { // 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 ( int counter = 0; counter < size - 1; counter += 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.c" //
186// End: //
Note: See TracBrowser for help on using the repository browser.