source: tests/concurrent/examples/quickSort.generic.cfa @ 78e109f

arm-ehcleanup-dtorsjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-expr
Last change on this file since 78e109f was 78e109f, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago

generic quickSort that fails with thread thunk problem

  • Property mode set to 100644
File size: 6.4 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 Mar 15 14:52:41 2019
14// Update Count     : 147
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 ( int counter = 0; counter < size; counter += 1 ) { // 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 ( int counter = 0; counter < size; counter += 1 ) { // 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 ( 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.generic.cfa" //
186// End: //
Note: See TracBrowser for help on using the repository browser.