// CRCW Quicksort algorithm by Chlebus and Vrto. JPDC, 1991
// Implementation in Fork by Christoph Kessler 10/1999.

#include <fork.h>
#include <io.h>
#include <stdlib.h>

#define N 16
sh int key[N]; // array to be sorted

// auxiliary global data structures:
sh int lchild[N], rchild[N],
       root,
       lnum[N], rnum[N], order[N];
pr int myParent,
       IAmALeftChild;

#define SHOWTREE 0

async void showTree( int depth, int subtree )
 // print the tree in sequential
{
 int i;
 if (lchild[subtree]<N) showTree( depth+1, lchild[subtree] );
 for (i=0; i<depth; i++) printf("-------");
 printf("+-- %d\n", key[subtree]);
 if (rchild[subtree]<N) showTree( depth+1, rchild[subtree] );
}

sync void buildTree( void )  // assumes #==N procs.
{
 pr int c, w = -1;
 root = $;     // concurrent write, proc.(#-1) wins 
 myParent = root;               // on priority CRCW PRAM
 lchild[$] = rchild[$] = N;
 if ($!=root) {
   while (w!=$) {
     farm // evaluate condition separately:
       c = (key[$]<key[myParent]
           || (key[$]==key[myParent] && $<myParent) );
     if ( c )
     { // I must go to the left of myParent:
       lchild[myParent] = $;  // (arbitrary) conc. write
       IAmALeftChild = 1;
       w = lchild[myParent];  // read what has been written
       if (w!=$)         // someone else (w) was successful:
          myParent = w;  // w becomes my new parent node
       // else I am the new parent node: I am done
     }
     else { // I must go to the right of myParent:
       rchild[myParent] = $; // select one processor arbitrarily
       IAmALeftChild = 0;
       w = rchild[myParent];
       if (w!=$)
          myParent = w;
     }
   } // while ($!=w);
 }
#if SHOWTREE
 seq showTree( 0, root );
#endif
}


sync void countDescendants( void )  // parallel sweep upwards
{
 pr int y;
 lnum[$] = rnum[$] = y = 0;
 farm {
  if ($!=root) {
    if (lchild[$]==N) {
       if (rchild[$]==N) // $ is a leaf
         y = 1; 
       else { // $ has only a right child
         while (rnum[$]==0) ; // wait until rnum[$] computed
         y = rnum[$] + 1;
       }
     }
     else { // $ has a left child
       if (rchild[$]==N) { // and no right child
         while (lnum[$]==0) ; // wait until lnum[$] computed
         y = lnum[$] + 1;
       }
       else { // $ has two children
         while (lnum[$]==0 || rnum[$]==0) ; // wait for both
         y = lnum[$] + rnum[$] + 1;
       }
     }
     // now y holds the number of descendants of $ (incl. $)
     if (IAmALeftChild)
       lnum[myParent] = y;
     else
       rnum[myParent] = y;
   }
 }
}


sync void findOrder( void )     // parallel sweep downwards
{
 int z;
 order[$] = -1;
 farm 
   if ($ == root)
     order[$] = lnum[$];
   else {
     do { z = order[myParent]; }
     while (z == -1);  // wait until it's my turn
     if (IAmALeftChild)
        order[$] = z - rnum[$] - 1;
     else
        order[$] = z + lnum[$] + 1;
   }
}


void main( void )
{
 int i;
 start {  // enter synchronous region, set $
initTracing(100000);
   // 0. test whether N processors are available:
   if (#<N) {
     seq
       printf("You need %d processors! Try again\n", N);
     exit(1);
   }
   if ($<N) { // if more than N procs, use only N
     // 1. initialize the array to be sorted:
     farm {
       srand( 17*$*$*$ ); // seed the random number generator
       key[$] = rand()&((1<<20)-1); // to produce individual values
     }
     seq {
       for (i=0; i<N; i++) {
         printf(" %d", key[i]);
         if (i%8==7) printf("\n");
       }
       printf("\nSorting...\n");
     }
 i = getct();
     // 2. build the tree (myParent, lchild, rchild):
startTracing();
     buildTree();
stopTracing();
 i = getct() - i;
 seq printf("Time: %3.2f msecs\n", i*0.004 );  // 1 PRAM step = 4 usec
writeTraceFile("buildTree.trv","buildTree");
     // 3. count the descendants in the tree (lnum, rnum):
     countDescendants();
     // 4. find the right order among them (order):
     findOrder();
     // 5. permute the array according to order:
     key[order[$]] = key[$];
     // 6. print the result:
     seq
       for (i=0; i<N; i++) {
         printf(" %d", key[i]);
         if (i%8==7) printf("\n");
       }
   }
 }
}