source: src/tests/concurrent/examples/quickSort.c @ b8a4f47

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since b8a4f47 was fe4840a, checked in by Peter A. Buhr <pabuhr@…>, 7 years ago

fix bugs in quickSort, still not working because thunk problem
  • Property mode set to 100644
File size: 6.7 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 : Thu Dec 14 11:20:40 2017
12// Update Count     : 142
13//
14
15#include <fstream>
16#include <stdlib>
17#include <kernel>
18#include <thread>
19#include <string.h>                                                                             // strcmp
20
21forall( otype T | { int ?<?( T, T ); } )
22thread Quicksort {
23        T * values;                                                                                     // communication variables
24        int low, high, depth;
25};
26
27forall( otype T | { int ?<?( 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 | { int ?<?( 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                        ELEMTYPE * values = alloc( size );                      // values to be sorted, too large to put on stack
144//                      ELEMTYPE * values = (ELEMTYPE *)malloc( sizeof(ELEMTYPE) * size );
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 ?
153                                Quicksort(ELEMTYPE) QS = { values, size - 1, 0 }; // sort values
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
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
171                for ( int counter = 0; counter < size; counter += 1 ) { // generate unsorted numbers
172                        values[counter] = size - counter;                       // descending values
173                } // for
174                {
175                        Quicksort(ELEMTYPE) QS = { values, size - 1, depth }; // sort values
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.