source: tests/concurrency/examples/quickSort.cfa @ 6f47834

//
// Cforall Version 1.0.0 Copyright (C) 2017 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// quickSort.c -- In-place concurrent quick-sort: threads are created to partition to a specific depth, then sequential
//              recursive-calls are use to sort each partition.
//
// Author           : Peter A. Buhr
// Created On       : Wed Dec  6 12:15:52 2017
// Last Modified By : Peter A. Buhr
// Last Modified On : Mon Jan  1 12:07:59 2024
// Update Count     : 188
//

#include <fstream.hfa>                                                                  // sin/sout
#include <stdlib.hfa>                                                                   // convert
#include <thread.hfa>
#include <math.hfa>                                                                             // sqrt
#include <string.h>                                                                             // strcmp

thread Quicksort {
        int * values;                                                                           // communication variables
        int low, high, depth;
};

void ?{}( Quicksort & qs, int values[], int size, int depth ) {
        qs.[values, low, high, depth] = [values, 0, size, depth];
} // Quicksort

void main( Quicksort & qs ) {                                                   // thread starts here
        // nested routines: information hiding

        void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) {
                qs.values = values;  qs.low = low;  qs.high = high;  qs.depth = depth;
        } // Quicksort

        void sort( int values[], int low, int high, int depth ) {
                int left, right;                                                                // index to left/right-hand side of the values
                int pivot;                                                                              // pivot value of values
                int swap;                                                                               // temporary

                //verify();                                                                             // check for stack overflow due to recursion

                // partition while 2 or more elements in the array
                if ( low < high ) {
                        pivot = values[low + ( high - low ) / 2];
                        left  = low;
                        right = high;

                        // partition: move values less < pivot before the pivot and values > pivot after the pivot
                        do {
                                while ( values[left] < pivot ) left += 1; // changed values[left] < pivot
                                while ( pivot < values[right] ) right -= 1;
                                if ( left <= right ) {
                                        swap = values[left];                            // interchange values
                                        values[left]  = values[right];
                                        values[right] = swap;
                                        left += 1;
                                        right -= 1;
                                } // if
                        } while ( left <= right );

                        // restrict number of tasks to slightly greater than number of processors
                        if ( depth > 0 ) {
                                depth -= 1;
                                Quicksort lqs = { values, low, right, depth }; // concurrently sort lower half
                                Quicksort rqs = { values, left, high, depth }; // concurrently sort upper half
                                // Quicksort lqs = { values, low, right, depth }; // concurrently sort lower half
                                // sort( values, left, high, depth );           // concurrently sort upper half
                        } else {
                                sort( values, low, right, 0 );                  // sequentially sort lower half
                                sort( values, left, high, 0 );                  // sequentially sort upper half
                        } // if
                } // if
        } // sort

        with( qs ) {
                sort( values, low, high, depth );
        } // with
} // main

// convert(...) throws out_of_range or invalid_argument
ExceptionDecl( cmd_error );

int main( int argc, char * argv[] ) {
        ifstream unsortedfile = sin;                                            // default values
        ofstream sortedfile = sout;
        // Must be signed because of the conversion routine.
        intmax_t depth = 0;
        intmax_t size = -1;                                                                     // -1 means time mode not activated

        try {
                if ( 1 < argc && strcmp( argv[1], "-t" ) == 0 ) { // time mode ?
                        choose ( argc ) {
                          case 4:
                                depth = convert( argv[3] );                             // invalid integer ?
                                if ( depth < 0 ) throw ExceptionInst( cmd_error );
                                fallthrough;
                          case 3:
                                size = convert( argv[2] );                              // invalid integer ?
                                if ( size < 0 ) throw ExceptionInst( cmd_error );
                          default:                                                                      // wrong number of options
                                throw ExceptionInst( cmd_error );
                        } // choose
                } else {                                                                                // sort file
                        choose ( argc ) {
                          case 4:
                                depth = convert( argv[3] );                             // invalid integer ?
                                if ( depth < 0 ) throw ExceptionInst( cmd_error );
                                fallthrough;
                          case 3: case 2:
                                if ( strcmp( argv[1], "d" ) != 0 ) {
                                        try {                                                           // open input file first as output creates file
                                                open( unsortedfile, argv[1] );
                                        } catch( open_failure * ) {                     // open failed ?
                                                serr | "Error! Could not open unsorted input file \"" | argv[1] | "\"";
                                                throw ExceptionInst( cmd_error );
                                        } // try
                                } // if
                                if ( argc > 2 && strcmp( argv[2], "d" ) != 0 ) {
                                        try {
                                                open( sortedfile, argv[2] );
                                        } catch( open_failure * ) {                     // open failed ?
                                                serr | "Error! Could not open sorted output file \"" | argv[2] | "\"";
                                                throw ExceptionInst( cmd_error );
                                        } // try
                                } // if
                                fallthrough;
                          case 1: ;                                                                     // defaults
                          default:                                                                      // wrong number of options
                                throw ExceptionInst( cmd_error );
                        } // choose
                } // if
        } catch( exception_t * ) {                                                      // catch any
                exit | "Usage: " | argv[0] |                                    // TERMINATE
                        " ( [ unsorted-file | 'd' [ sorted-file | 'd' [ depth (>= 0) ] ] ]"
                        " | -t size (>= 0) [ depth (>= 0) ] )";
        } //  try

        enum { ValuesPerLine = 22 };                                            // number of values printed per line

        sortedfile | nlOff;                                                                     // turn off auto newline

        if ( size == -1 ) {                                                                     // generate output ?
                for () {
                        unsortedfile | size;                                            // read number of elements in the list
                  if ( eof( unsortedfile ) ) break;

                        int * values = aalloc( size );                          // values to be sorted, too large to put on stack
                        for ( counter; size ) {                                         // read unsorted numbers
                                unsortedfile | values[counter];
                                if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | "  ";
                                sortedfile | values[counter];
                                if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
                        } // for
                        sortedfile | nl;

                        if ( size > 0 ) {                                                       // values to sort ?
                                Quicksort QS = { values, size - 1, 0 }; // sort values
                        } // wait until sort tasks terminate
                        for ( counter; size ) {                                         // print sorted list
                                if ( counter != 0 && counter % ValuesPerLine == 0 ) sortedfile | nl | "  ";
                                sortedfile | values[counter];
                                if ( counter < size - 1 && (counter + 1) % ValuesPerLine != 0 ) sortedfile | ' ';
                        } // for
                        sortedfile | nl | nl;

                        delete( values );
                } // for
        } else {                                                                                        // timing
                PRNG prng;                                                                              
                processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads
                int * values = aalloc( size );                                  // values to be sorted, too large to put on stack

                for ( counter; size ) {                                                 // generate unsorted numbers
                        values[counter] = size - counter;                       // descending values
                } // for

                unsigned int times = sqrt( size );
                for ( unsigned int counter = 0; counter < times; counter += 1 ) {
                        swap( values[0], values[prng(size)] );          // randomize unsorted numbers
                } // for
                {
                        Quicksort QS = { values, size - 1, depth }; // sort values
                } // wait until sort tasks terminate

                // for ( counter; size - 1 ) {                          // check sorting
                //      if ( values[counter] > values[counter + 1] ) abort();
                // } // for

                delete( values );
        } // if
} // main

// for depth in 0 1 2 3 4 5 ; do echo "sort 500000000 values with ${depth} depth" ; time -f "%Uu %Ss %E %Mkb" a.out -t 500000000 ${depth} ; done

// Local Variables: //
// tab-width: 4 //
// compile-command: "cfa quickSort.cfa" //
// End: //