source: src/tests/concurrent/examples/quickSort.c@ 5b51f5e

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 5b51f5e was fe4840a, checked in by Peter A. Buhr <pabuhr@…>, 8 years ago

fix bugs in quickSort, still not working because thunk problem
  • Property mode set to 100644
File size: 6.7 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
[fe4840a]11// Last Modified On : Thu Dec 14 11:20:40 2017
12// Update Count : 142
[90449e4]13//
14
15#include <fstream>
16#include <stdlib>
17#include <kernel>
18#include <thread>
19#include <string.h> // strcmp
20
[fe4840a]21forall( otype T | { int ?<?( T, T ); } )
[90449e4]22thread Quicksort {
[edb6f79]23 T * values; // communication variables
[90449e4]24 int low, high, depth;
25};
26
[fe4840a]27forall( otype T | { int ?<?( T, T ); } )
[edb6f79]28void ?{}( Quicksort(T) & qs, T values[], int size, int depth ) {
[90449e4]29 qs.values = values; qs.low = 0; qs.high = size; qs.depth = depth;
30} // Quicksort
31
[fe4840a]32forall( otype T | { int ?<?( T, T ); } )
[edb6f79]33void main( Quicksort(T) & qs ) {
[90449e4]34 // nested routines: information hiding
35
[edb6f79]36 void ?{}( Quicksort(T) & qs, T values[], int low, int high, int depth ) {
[90449e4]37 qs.values = values; qs.low = low; qs.high = high; qs.depth = depth;
38 } // Quicksort
39
[edb6f79]40 void sort( T values[], int low, int high, int depth ) {
[90449e4]41 int left, right; // index to left/right-hand side of the values
[edb6f79]42 T pivot; // pivot value of values
43 T swap; // temporary
[90449e4]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;
[edb6f79]70 Quicksort(T) rqs = { values, low, right, depth }; // concurrently sort upper half
[90449e4]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
[edb6f79]98
99#define ELEMTYPE int
100
[90449e4]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;
[fe4840a]142// ELEMTYPE * values = anew( size ); // values to be sorted, too large to put on stack
143 ELEMTYPE * values = alloc( size ); // values to be sorted, too large to put on stack
144// ELEMTYPE * values = (ELEMTYPE *)malloc( sizeof(ELEMTYPE) * size );
[90449e4]145 for ( int counter = 0; counter < size; counter += 1 ) { // read unsorted numbers
146 unsortedfile | values[counter];
147 if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | endl | " ";
148 sortedfile | values[counter];
149 if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
150 } // for
151 sortedfile | endl;
152 if ( size > 0 ) { // values to sort ?
[edb6f79]153 Quicksort(ELEMTYPE) QS = { values, size - 1, 0 }; // sort values
[90449e4]154 } // wait until sort tasks terminate
155 for ( int counter = 0; counter < size; counter += 1 ) { // print sorted list
156 if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | endl | " ";
157 sortedfile | values[counter];
158 if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
159 } // for
160 sortedfile | endl | endl;
161
162 delete( values );
163 } // for
164 if ( &unsortedfile != &sin ) delete( &unsortedfile ); // close input/output files
165 if ( &sortedfile != &sout ) delete( &sortedfile );
166 } else {
167 processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads
168
[fe4840a]169// ELEMTYPE * values = anew( size ); // values to be sorted, too large to put on stack
170 ELEMTYPE * values = alloc( size ); // values to be sorted, too large to put on stack
[90449e4]171 for ( int counter = 0; counter < size; counter += 1 ) { // generate unsorted numbers
172 values[counter] = size - counter; // descending values
173 } // for
174 {
[edb6f79]175 Quicksort(ELEMTYPE) QS = { values, size - 1, depth }; // sort values
[90449e4]176 } // wait until sort tasks terminate
177
178 // for ( int counter = 0; counter < size - 1; counter += 1 ) { // check sorting
179 // if ( values[counter] > values[counter + 1] ) abort();
180 // } // for
181
182 delete( values );
183 } // if
184} // main
185
186// Local Variables: //
187// tab-width: 4 //
188// compile-command: "cfa quickSort.c" //
189// End: //
Note: See TracBrowser for help on using the repository browser.