Changeset f0322e20


Ignore:
Timestamp:
Jan 29, 2018, 9:18:16 AM (7 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
ff39851
Parents:
604e76d
Message:

add quicksort test

Location:
src/tests/concurrent/examples
Files:
1 added
1 edited

Legend:

Unmodified
Added
Removed
  • src/tests/concurrent/examples/quickSort.c

    r604e76d rf0322e20  
    99// Created On       : Wed Dec  6 12:15:52 2017
    1010// Last Modified By : Peter A. Buhr
    11 // Last Modified On : Thu Dec 14 11:20:40 2017
    12 // Update Count     : 142
     11// Last Modified On : Mon Jan 29 08:41:37 2018
     12// Update Count     : 155
    1313//
    1414
     
    1919#include <string.h>                                                                             // strcmp
    2020
    21 forall( otype T | { int ?<?( T, T ); } )
    2221thread Quicksort {
    23         T * values;                                                                                     // communication variables
     22        int * values;                                                                           // communication variables
    2423        int low, high, depth;
    2524};
    2625
    27 forall( otype T | { int ?<?( T, T ); } )
    28 void ?{}( Quicksort(T) & qs, T values[], int size, int depth ) {
     26void ?{}( Quicksort & qs, int values[], int size, int depth ) {
    2927        qs.values = values;  qs.low = 0;  qs.high = size;  qs.depth = depth;
    3028} // Quicksort
    3129
    32 forall( otype T | { int ?<?( T, T ); } )
    33 void main( Quicksort(T) & qs ) {
     30void main( Quicksort & qs ) {                                                   // thread starts here
    3431        // nested routines: information hiding
    3532
    36         void ?{}( Quicksort(T) & qs, T values[], int low, int high, int depth ) {
     33        void ?{}( Quicksort & qs, int values[], int low, int high, int depth ) {
    3734                qs.values = values;  qs.low = low;  qs.high = high;  qs.depth = depth;
    3835        } // Quicksort
    3936
    40         void sort( T values[], int low, int high, int depth ) {
     37        void sort( int values[], int low, int high, int depth ) {
    4138                int left, right;                                                                // index to left/right-hand side of the values
    42                 T pivot;                                                                                // pivot value of values
    43                 T swap;                                                                                 // temporary
     39                int pivot;                                                                              // pivot value of values
     40                int swap;                                                                               // temporary
    4441
    4542                //verify();                                                                             // check for stack overflow due to recursion
     
    6764                        if ( depth > 0 ) {
    6865                                depth -= 1;
    69                                 //sout << &uThisTask() << " " << depth << endl;
    70                                 Quicksort(T) rqs = { values, low, right, depth }; // concurrently sort upper half
     66                                Quicksort rqs = { values, low, right, depth }; // concurrently sort upper half
    7167                                //Quicksort lqs( values, left, high, depth ); // concurrently sort lower half
    7268                                sort( values, left, high, depth );              // concurrently sort lower half
     
    9793
    9894
    99 #define ELEMTYPE int
    100 
    10195int main( int argc, char * argv[] ) {
    10296        ifstream & unsortedfile = sin;
     
    106100        if ( argc != 1 ) {                                                                      // do not use defaults
    107101                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
     102//              if ( strcmp( argv[1], "-t" ) == 0 ) {                   // timing ?
     103                if ( argv[1][0] == '-' && argv[1][1] == 't' ) { // timing ?
     104                        &unsortedfile = (ifstream *)0;                          // no input
    126105                        choose ( argc ) {
    127106                          case 4:
     
    131110                                if ( ! convert( size, argv[2] ) || size < 0 ) usage( argv );
    132111                        } // choose
    133                 } else usage( argv );                                                   // invalid flag
     112                } else {                                                                                // sort file
     113                        choose ( argc ) {
     114                          case 3:
     115                                &sortedfile = new( (const char *)argv[2] ); // open the output file
     116                                if ( fail( sortedfile ) ) {
     117                                        serr | "Error! Could not open sorted output file \"" | argv[2] | "\"" | endl;
     118                                        usage( argv );
     119                                } // if
     120                                fallthrough;
     121                          case 2:
     122                                &unsortedfile = new( (const char *)argv[1] ); // open the input file
     123                                if ( fail( unsortedfile ) ) {
     124                                        serr | "Error! Could not open unsorted input file \"" | argv[1] | "\"" | endl;
     125                                        usage( argv );
     126                                } // if
     127                        } // choose
     128                } // if
    134129        } // if
    135130
     
    140135                        unsortedfile | size;                                            // read number of elements in the list
    141136                  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 );
     137                        int * values = alloc( size );                           // values to be sorted, too large to put on stack
    145138                        for ( int counter = 0; counter < size; counter += 1 ) { // read unsorted numbers
    146139                                unsortedfile | values[counter];
     
    151144                        sortedfile | endl;
    152145                        if ( size > 0 ) {                                                       // values to sort ?
    153                                 Quicksort(ELEMTYPE) QS = { values, size - 1, 0 }; // sort values
     146                                Quicksort QS = { values, size - 1, 0 }; // sort values
    154147                        } // wait until sort tasks terminate
    155148                        for ( int counter = 0; counter < size; counter += 1 ) { // print sorted list
     
    167160                processor processors[ (1 << depth) - 1 ] __attribute__(( unused )); // create 2^depth-1 kernel threads
    168161
    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
     162                int * values = alloc( size );                           // values to be sorted, too large to put on stack
    171163                for ( int counter = 0; counter < size; counter += 1 ) { // generate unsorted numbers
    172164                        values[counter] = size - counter;                       // descending values
    173165                } // for
    174166                {
    175                         Quicksort(ELEMTYPE) QS = { values, size - 1, depth }; // sort values
     167                        Quicksort QS = { values, size - 1, depth }; // sort values
    176168                } // wait until sort tasks terminate
    177169
Note: See TracChangeset for help on using the changeset viewer.