source: tests/concurrent/examples/quickSort.cfa @ 2e457d8

aaron-thesisarm-ehcleanup-dtorsjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpersistent-indexer
Last change on this file since 2e457d8 was 2e457d8, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago

formatting

  • Property mode set to 100644
File size: 6.3 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 : Wed Feb 20 08:38:24 2019
14// Update Count     : 169
15//
16
17#include <fstream.hfa>
18#include <stdlib.hfa>
19#include <kernel.hfa>
20#include <thread.hfa>
21#include <string.h>                                                                             // strcmp
22
23thread Quicksort {
24        int * values;                                                                           // communication variables
25        int low, high, depth;
26};
27
28void ?{}( Quicksort & qs, int values[], int size, int depth ) {
29        qs.values = values;  qs.low = 0;  qs.high = size;  qs.depth = depth;
30} // Quicksort
31
32void main( Quicksort & qs ) {                                                   // thread starts here
33        // nested routines: information hiding
34
35        void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) {
36                qs.values = values;  qs.low = low;  qs.high = high;  qs.depth = depth;
37        } // Quicksort
38
39        void sort( int values[], int low, int high, int depth ) {
40                int left, right;                                                                // index to left/right-hand side of the values
41                int pivot;                                                                              // pivot value of values
42                int swap;                                                                               // temporary
43
44                //verify();                                                                             // check for stack overflow due to recursion
45
46                // partition while 2 or more elements in the array
47                if ( low < high ) {
48                        pivot = values[low + ( high - low ) / 2];
49                        left  = low;
50                        right = high;
51
52                        // partition: move values less < pivot before the pivot and values > pivot after the pivot
53                        do {
54                                while ( values[left] < pivot ) left += 1; // changed values[left] < pivot
55                                while ( pivot < values[right] ) right -= 1;
56                                if ( left <= right ) {
57                                        swap = values[left];                            // interchange values
58                                        values[left]  = values[right];
59                                        values[right] = swap;
60                                        left += 1;
61                                        right -= 1;
62                                } // if
63                        } while ( left <= right );
64
65                        // restrict number of tasks to slightly greater than number of processors
66                        if ( depth > 0 ) {
67                                depth -= 1;
68                                Quicksort rqs = { values, low, right, depth }; // concurrently sort upper half
69                                //Quicksort lqs( values, left, high, depth ); // concurrently sort lower half
70                                sort( values, left, high, depth );              // concurrently sort lower half
71                        } else {
72                                sort( values, low, right, 0 );                  // sequentially sort lower half
73                                sort( values, left, high, 0 );                  // sequentially sort upper half
74                        } // if
75                } // if
76        } // sort
77
78        with( qs ) {
79                sort( values, low, high, depth );
80        } // with
81} // main
82
83
84bool convert( int & val, const char * nptr ) {                  // convert C string to integer
85        char * eptr;
86        int temp = strto( nptr, &eptr, 10 );                            // do not change val on false
87        // true => entire string valid with no extra characters
88        return *nptr != '\0' && *eptr == '\0' ? val = temp, true : false;
89} // convert
90
91void usage( char * argv[] ) {
92        sout | "Usage:" | argv[0] | "( -s unsorted-file [ sorted-file ] | -t size (>= 0) [ depth (>= 0) ] )";
93        exit( EXIT_FAILURE );                                                           // TERMINATE!
94} // usage
95
96
97int main( int argc, char * argv[] ) {
98        ifstream & unsortedfile = sin;
99        ofstream & sortedfile = sout;                                           // default value
100        int depth = 0, size;
101
102        if ( argc != 1 ) {                                                                      // do not use defaults
103                if ( argc < 2 || argc > 4 ) usage( argv );              // wrong number of options
104                if ( strcmp( argv[1], "-t" ) == 0 ) {                   // timing ?
105                        &unsortedfile = (ifstream *)0;                          // no input
106                        choose ( argc ) {
107                          case 4:
108                                if ( ! convert( depth, argv[3] ) || depth < 0 ) usage( argv );
109                                fallthrough;
110                          case 3:
111                                if ( ! convert( size, argv[2] ) || size < 0 ) usage( argv );
112                        } // choose
113                } else {                                                                                // sort file
114                        choose ( argc ) {
115                          case 3:
116                                &sortedfile = new( (const char *)argv[2] ); // open the output file
117                                if ( fail( sortedfile ) ) {
118                                        serr | "Error! Could not open sorted output file \"" | argv[2] | "\"";
119                                        usage( argv );
120                                } // if
121                                fallthrough;
122                          case 2:
123                                &unsortedfile = new( (const char *)argv[1] ); // open the input file
124                                if ( fail( unsortedfile ) ) {
125                                        serr | "Error! Could not open unsorted input file \"" | argv[1] | "\"";
126                                        usage( argv );
127                                } // if
128                        } // choose
129                } // if
130        } // if
131        sortedfile | nlOff;                                                                     // turn off auto newline
132
133        enum { ValuesPerLine = 22 };                                            // number of values printed per line
134
135        if ( &unsortedfile ) {                                                          // generate output ?
136                for () {
137                        unsortedfile | size;                                            // read number of elements in the list
138                  if ( eof( unsortedfile ) ) break;
139                        int * values = alloc( size );                           // values to be sorted, too large to put on stack
140                        for ( int counter = 0; counter < size; counter += 1 ) { // read unsorted numbers
141                                unsortedfile | values[counter];
142                                if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | "  ";
143                                sortedfile | values[counter];
144                                if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
145                        } // for
146                        sortedfile | nl;
147                        if ( size > 0 ) {                                                       // values to sort ?
148                                Quicksort QS = { values, size - 1, 0 }; // sort values
149                        } // wait until sort tasks terminate
150                        for ( int counter = 0; counter < size; counter += 1 ) { // print sorted list
151                                if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | "  ";
152                                sortedfile | values[counter];
153                                if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
154                        } // for
155                        sortedfile | nl | nl;
156
157                        delete( values );
158                } // for
159                if ( &unsortedfile != &sin ) delete( &unsortedfile ); // close input/output files
160                if ( &sortedfile != &sout ) delete( &sortedfile );
161        } else {
162                processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads
163
164                int * values = alloc( size );                           // values to be sorted, too large to put on stack
165                for ( int counter = 0; counter < size; counter += 1 ) { // generate unsorted numbers
166                        values[counter] = size - counter;                       // descending values
167                } // for
168                {
169                        Quicksort QS = { values, size - 1, depth }; // sort values
170                } // wait until sort tasks terminate
171
172                // for ( int counter = 0; counter < size - 1; counter += 1 ) { // check sorting
173                //      if ( values[counter] > values[counter + 1] ) abort();
174                // } // for
175
176                delete( values );
177        } // if
178} // main
179
180// Local Variables: //
181// tab-width: 4 //
182// compile-command: "cfa quickSort.c" //
183// End: //
Note: See TracBrowser for help on using the repository browser.