// Adsmith sample program; NOT INTENDED TO BE EFFICIENT as a prime
// finder, either in algorithm or implementation 
//
// finds and reports the number of primes less than or equal to N

// each node works on a range of Chunk numbers at a time, testing
// them for primeness by straight division; if a potential divisor
// has already been found to be composite (i.e. nonprime), then we
// skip it

// necessary includes
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include "adsm.h"
#include "adsmutil.h"
#include "adsmtime.h"

// the following variables are shared in the Adsmith sense; note that
// we typically access them via pointers, which are returned to us by
// calls to adsm_malloc() and adsm_malloc_array()
int **Composite; // array of pointers to composites found so 
                 // far, code 1 for composite, 0 otherwise 
int *NPtr, // check primes from 2 to N 
    *ChunkPtr, // how many numbers to check at one time 
    *NNodesPtr; // number of nodes in computation

// the following variables are not shared in the Adsmith sense, though
// they will have the same (unchanging) values at every node
int N,Chunk,NNodes;

// the following variable is not shared in the Adsmith sense, and in
// fact has different values at each node
int Me;  // number of this node

// declare an instance of Adsmith's built-in barrier class, AdsmBarrier
AdsmBarrier PrintBarr("printbar");

// declare an instance of Adsmith's built-in mutex (lock) class,
// AdsmMutex
AdsmMutex CompCountMtx("ccmutex");

int IsComposite(int K)  // returns 1 if K is found to be composite 

{  int J;

   for (J = 2; J*J <= K; J++)  {
      // if J is known to be composite, don't bother dividing by it 
      adsm_refresh(Composite[J]);  // get latest value 
      if (*Composite[J] == 0)  
         if (K % J == 0) return 1;
   }
   return 0;
}

Worker()

{  int First,Last,Iter,NIters,I,Block,MyComposites = 0;

   Block = NNodes * Chunk;

   First = 1 + Me * Chunk;
   Last = First + Chunk - 1;
   NIters = N / Block;

   for (Iter = 0; Iter < NIters; Iter++)  {
      for (I = First; I <= Last; I++)  
         if (IsComposite(I))  {
	    *Composite[I] = 1;
	    // update the other nodes
	    adsm_flush(Composite[I]);
	    MyComposites++;
	 }
      First += Block;  Last += Block;
   }
   
   PrintBarr.barrier(NNodes);
   CompCountMtx.lock();  // need atomic access to *Composite[0] 
   adsm_refresh(Composite[0]);  // get latest count value
   *Composite[0] += MyComposites;
   adsm_flush(Composite[0]);  // update the other nodes
   CompCountMtx.unlock(); // end of critical section
}

int main(int argc, char **argv)

{  int I;

   Me = get_seqno();  // Adsmith library function, like MPI_Comm_rank()

   if (Me == 0)  {

      // pick up the command-line arguments
      N = atoi(argv[1]);
      Chunk = atoi(argv[2]);
      NNodes = atoi(argv[3]);

      // since the other nodes don't have access to argv, we need to
      // make these Adsmith shared variables, even though they will 
      // never change  values after the beginning of the program
      //
      // so, the following call with have Adsmith set up a space in
      // its own shared memory pool, and set up a buffer for us to
      // reference that variable in, returning a pointer to the buffer;
      // the initial value in the pool and in that buffer will be drawn
      // from N; the spot in the pool will be named "n"
      NPtr = (int *) adsm_malloc("n",sizeof(int),&N);
      ChunkPtr = (int *) adsm_malloc("chunk",sizeof(int),&Chunk);
      NNodesPtr = (int *) adsm_malloc("number of nodes",sizeof(int),&NNodes);
      // no calls to adsm_flush() are needed above, since it is done by
      // the call to adsm_malloc()
   }
   else  {
      // call adsm_malloc() here too, but without initial values,
      // getting them from node 0's call to adsm_malloc()
      NPtr = (int *) adsm_malloc("n",sizeof(int));
      // get the latest value
      adsm_refresh(NPtr);
      N = *NPtr;
      ChunkPtr = (int *) adsm_malloc("chunk",sizeof(int));
      adsm_refresh(ChunkPtr);
      Chunk = *ChunkPtr;
      NNodesPtr = (int *) adsm_malloc("number of nodes",sizeof(int));
      adsm_refresh(NNodesPtr);
      NNodes = *NNodesPtr;
   }

   Composite = (int **) malloc((N+1)*sizeof(int *));

   if (N % (NNodes*Chunk) > 0)  {
      printf("N must be an even multiple of NNodes*Chunk\n");
      exit(1);
   }

   char SegName[100]; int Zero = 0;
   for (I = 0; I < N+1; I++)  {
      sprintf(SegName,"composite[%d]",I);
      if (Me == 0) Composite[I] = 
              (int *) adsm_malloc(SegName,sizeof(int),&Zero);
      else  {
         Composite[I] = (int *) adsm_malloc(SegName,sizeof(int));
         adsm_refresh(Composite[I]); 
      }
   }

   // spawn at other nodes
   if (Me == 0)  {
      int NSpawned = adsm_spawn(execname(argv[0]),NNodes-1);
      cout<<"number spawned = "<<NSpawned<<endl;
   }

   Worker();

   // need to make sure everyone is done before printing 
   // out the results 
   PrintBarr.barrier(NNodes);

   if (Me == 0)  {
      adsm_refresh(Composite[0]); 
      printf("number of primes = %d\n",N-*Composite[0]-1);
   }
}