source: tests/concurrent/examples/quickSort.c @ 2112663f

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprno_listpersistent-indexerpthread-emulationqualifiedEnum
Last change on this file since 2112663f was adb6b30f, checked in by Peter A. Buhr <pabuhr@…>, 6 years ago

more forctrl changes

  • Property mode set to 100644
File size: 6.2 KB
RevLine 
[764b4b2]1//
[90449e4]2// The contents of this file are covered under the licence agreement in the
3// file "LICENCE" distributed with Cforall.
[764b4b2]4//
[90449e4]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.
[764b4b2]7//
[90449e4]8// Author           : Peter A. Buhr
9// Created On       : Wed Dec  6 12:15:52 2017
10// Last Modified By : Peter A. Buhr
[adb6b30f]11// Last Modified On : Thu Aug 16 08:17:41 2018
12// Update Count     : 163
[764b4b2]13//
[90449e4]14
[73abe95]15#include <fstream.hfa>
16#include <stdlib.hfa>
17#include <kernel.hfa>
18#include <thread.hfa>
[90449e4]19#include <string.h>                                                                             // strcmp
20
21thread Quicksort {
[f0322e20]22        int * values;                                                                           // communication variables
[90449e4]23        int low, high, depth;
24};
25
[f0322e20]26void ?{}( Quicksort & qs, int values[], int size, int depth ) {
[90449e4]27        qs.values = values;  qs.low = 0;  qs.high = size;  qs.depth = depth;
28} // Quicksort
29
[f0322e20]30void main( Quicksort & qs ) {                                                   // thread starts here
[90449e4]31        // nested routines: information hiding
32
[f0322e20]33        void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) {
[90449e4]34                qs.values = values;  qs.low = low;  qs.high = high;  qs.depth = depth;
35        } // Quicksort
36
[f0322e20]37        void sort( int values[], int low, int high, int depth ) {
[90449e4]38                int left, right;                                                                // index to left/right-hand side of the values
[f0322e20]39                int pivot;                                                                              // pivot value of values
40                int swap;                                                                               // temporary
[90449e4]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;
[f0322e20]66                                Quicksort rqs = { values, low, right, depth }; // concurrently sort upper half
[90449e4]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
[edb6f79]94
[90449e4]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
[c1135eef]102                if ( strcmp( argv[1], "-t" ) == 0 ) {                   // timing ?
[f0322e20]103                        &unsortedfile = (ifstream *)0;                          // no input
[90449e4]104                        choose ( argc ) {
105                          case 4:
[f0322e20]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
[90449e4]115                                if ( fail( sortedfile ) ) {
[f0322e20]116                                        serr | "Error! Could not open sorted output file \"" | argv[2] | "\"" | endl;
[90449e4]117                                        usage( argv );
118                                } // if
119                                fallthrough;
[f0322e20]120                          case 2:
121                                &unsortedfile = new( (const char *)argv[1] ); // open the input file
[90449e4]122                                if ( fail( unsortedfile ) ) {
[f0322e20]123                                        serr | "Error! Could not open unsorted input file \"" | argv[1] | "\"" | endl;
[90449e4]124                                        usage( argv );
125                                } // if
126                        } // choose
[f0322e20]127                } // if
[90449e4]128        } // if
129
130        enum { ValuesPerLine = 22 };                                            // number of values printed per line
131
132        if ( &unsortedfile ) {                                                          // generate output ?
[adb6b30f]133                for () {
[90449e4]134                        unsortedfile | size;                                            // read number of elements in the list
135                  if ( eof( unsortedfile ) ) break;
[f0322e20]136                        int * values = alloc( size );                           // values to be sorted, too large to put on stack
[90449e4]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 ?
[f0322e20]145                                Quicksort QS = { values, size - 1, 0 }; // sort values
[90449e4]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
[f0322e20]161                int * values = alloc( size );                           // values to be sorted, too large to put on stack
[90449e4]162                for ( int counter = 0; counter < size; counter += 1 ) { // generate unsorted numbers
163                        values[counter] = size - counter;                       // descending values
164                } // for
165                {
[f0322e20]166                        Quicksort QS = { values, size - 1, depth }; // sort values
[90449e4]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.