/*
  Alex Safonov, Jon Herlocker, and Brian Bailey.

  This module parallelizes the generation of prime numbers using a pipeline.
  The idea is as follows:

    First, submit 2 as a prime number.
    Generate odd numbers starting with 3, up to a maximum limit, which
    for this assignment will be the square root of 2^16. 

    Each processor tries to divide the number by its entire list of
    primes.  If the number divides evenly, then it is not a prime number
    and is discarded.  If the number is not divisible, then the number
    ALONG with the highest current prime existing at the local process.

    When the next process receives the number, it checks the highest prime
    sent with the message against its own local highest prime.  If the
    sent prime is larger, then the number is a NEW prime and should be
    added to the local list, and we stop. If not, then repeat the process.

*/




#include "mpi.h"
#include <stdio.h>
#include <stdlib.h> /* For malloc */

#ifdef DEBUG
#include "pr_tbl.c"
#endif

/* define an element on the prime queue */
typedef struct prime_element {
    unsigned int prime;
    struct prime_element *next;
} PrimeElement;


/* define the prime queue data structure which contains the prime queue
   along with some bookkeeping information.
*/
typedef struct prime_q {
    PrimeElement *queue_h;       /* head of the queue */
    PrimeElement *queue_t;       /* tail of the queue */
    unsigned int largest_prime;  /* the largest prime seen so far */
} PrimeQ;


typedef struct factorRecord {
    unsigned int original ;      /* Original number to be factored */
    unsigned int factor ;        /* factor */
    unsigned int power ;         /* Number of times the factor divdes */
    struct factorRecord *next ;
} FactorRecord ;

typedef struct factorQ {
    FactorRecord *head ;
    FactorRecord *tail ;
    unsigned count;
} FactorQ ;
    
/* each process needs their own queue */
static PrimeQ *primeQ;
static FactorQ *factorQ ;

/* external variables */
extern int numprocessors ;

/* local functions */
static void PrimeInsert(int prime);
static PrimeElement *PrimeElement_New(int prime);
static FactorRecord *FactorRecord_New(unsigned int, unsigned int, 
				       unsigned int) ;
static void Initialize(int id);
static void InitializeMaster() ;
static int Divide(unsigned int);
static unsigned int Factor(unsigned int, unsigned int) ;
static void PrintPrimes(int) ;
static void PrintFactors(int) ;
static void FactorInsert(unsigned int, unsigned int, unsigned int) ;

/* specify the largest number to be 2^16 */
#define LARGESTNUMBER 0x10000
/*#define LARGESTNUMBER 20*/

#define MAX_FACTORS  4096

/* define which process is the master */
#define MASTER 0


/* define the tags we will use for this part of the program */
#define STAGE1 1    /* sieving primes */
#define STAGE2 2    /* factoring */
#define STAGE3 3    /* collecting results */

/* 
 * These are  secondary tags for STAGE1.
 * They must be bigger than the possible number of processes
 */
#define GOTOSTAGE2 10000
#define POSSIBLE_PRIME 10001
#define ENDSTAGE1 10002

/*
 * Secondary tages for STAGE2
 * Note that these are possible because nobody will try to factor 0 or 1
 * The master should check for this.
 */
#define GOTOSTAGE3 0
#define ENDSTAGE2 1

/*
 * Secondary tages for STAGE3
 * Note that these are possible because nobody will try to factor 0
 * The master should check for this.
 */
#define ALLDONE    0


void primegeneratemaster(int id, unsigned numbers[], unsigned len)
{
   int nextid = 0;
   int previd = 0;
   MPI_Status status;
   unsigned int *data;
   unsigned int number;
   int msgWaiting ;
   int done ;
   int numnumbers ;
   int i, j, k ;
   int r ; 
   static unsigned factors[MAX_FACTORS*2];
   static unsigned prfactors[MAX_FACTORS*2];
   unsigned nfactors, totfactors;
   double start2, end2;

   /* 
    * Largest prime sent out
    */
   unsigned int largestPrime = 0 ;
   
   /*
    * Next process who should receive a prime
    */
   int nextProcess = 1 ;

   if (id != MASTER)
	fprintf(stderr, "process running the master code is NOT the master\n");
   else
	fprintf(stderr, "The master is ready\n");


   /*
    * allocate space for the prime factor queue
    */
   InitializeMaster() ;

   data = (unsigned int *) malloc(sizeof(unsigned int) * 2);

   nextid = (MASTER + 1) % numprocessors;
   previd = MASTER - 1 ;
   /*
    * the MOD command (%) will return negative values, so you can't
    * use it on a subtraction.
    */
   if (previd < 0) {
       previd = numprocessors - 1 ;
   }

   /***
   **** STAGE1
   ****
   **** The master generates all possible odd numbers (and 2)
   **** and pushes them through the pipeline.
   **** At the same time, the master continuously checks for new
   **** messages. The only message that it should receive is a prime
   **** that has completed the loop.
   ****     When it receives a prime, the master sends the prime out
   **** to the process with the least number of accumulated primes.
   **** The master tracks who is next to get a prime. Primes are sent 
   **** through the loop instead of direct to take advantage of message
   **** ordering provided by MPI
   **** The master also remembers the largest prime that it has sent out,
   **** and will not send out any number n unless all primes less than
   **** (n/2) have been send.  (n/2 is always greater than sqrt(n) for 
   **** n > 4).
   ****/
   
   /* 
    * Initially send 2, then send all odds.
    */
   *data = POSSIBLE_PRIME ;
   *(data + 1) = 2 ;
   MPI_Send(data, 2, MPI_UNSIGNED, nextid,
	    STAGE1, MPI_COMM_WORLD);

   /* 
    * Start with 3 and send all odds
    */
   number = 3 ;

   /*
    * Main loop.
    * We alternate between processing the receive queue and
    * generating new possible primes.
    */
   
   done = 0 ;
   while (!done) {
       /*
	* First check the receive queue
	*/
       MPI_Iprobe(previd, STAGE1, MPI_COMM_WORLD, &msgWaiting, &status) ;
       if (msgWaiting) {
	   /*
	    * We have a new prime!
	    */
	    
	    
	   MPI_Recv(data, 2, MPI_UNSIGNED, previd, STAGE1,
		    MPI_COMM_WORLD, &status); 
/* 	   printf("master received %d %d from %d\n", *data, *(data+1), previd) ; */
	   largestPrime = *(data + 1) ;
	   
	   /* 
	    * Send this prime off to a process that will use it
	    * to factor numbers 
	    */
	   *data = nextProcess ;
	   nextProcess = (nextProcess + 1) % numprocessors ;
	   if (nextProcess == 0) {
	       nextProcess++ ;
	   }
	   MPI_Send(data, 2, MPI_UNSIGNED, nextid,  
		    STAGE1, MPI_COMM_WORLD); 
       }

       /*
	* Only send a new number n into the loop if all primes up to n/2
	* have been found.
	*/
       if (largestPrime < (number / 2)) {
	   continue ;
       }
       
       *data = POSSIBLE_PRIME ;
       *(data + 1) = number ;
       
       number += 2 ;

  
       r = MPI_Send(data, 2, MPI_UNSIGNED, nextid,
	   STAGE1, MPI_COMM_WORLD);

       if (number > LARGESTNUMBER ) {
	   done = 1;
       }
   }

   /*
    * We have sent all the possible primes into the loop.
    * We now send the ENDSTAGE1 token into the loop.
    * when we receive this token we know that all the possible primes
    * are done processing.
    */ 
   
   *data = ENDSTAGE1 ;
   MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE1, MPI_COMM_WORLD) ;
   
   done = 0 ;
   while (!done) {
       MPI_Recv(data, 2, MPI_UNSIGNED, previd, STAGE1,
		MPI_COMM_WORLD, &status); 
	
       if (*data != ENDSTAGE1) {
	   largestPrime = *(data + 1) ;
	   
	   /* 
	    * Send this prime off to a process that will use it
	    * to factor numbers 
	    */
	   *data = nextProcess ;
	   nextProcess = (nextProcess + 1) % numprocessors ;
	   if (nextProcess == 0) {
	       nextProcess++ ;
	   }
/* 	   printf("Sending %d %d to %d\n", *data, *(data+1), nextid) ; */
	   MPI_Send(data, 2, MPI_UNSIGNED, nextid,
		    STAGE1, MPI_COMM_WORLD);
       } else {
	      /* Done! Move to stage 2. */
	      done = 1 ;
       }
   }

   
   /*
    * Now we are sure that we have received and processed all 
    * new primes. So we tell everybody to move to the next stage
    */

   *data = GOTOSTAGE2 ;
   MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE1, MPI_COMM_WORLD) ;

   fprintf(stderr, "Master done with stage 1\n") ;
   /*** 
   **** STAGE 2.
   ****
   **** Start the factorization process.
   **** In this process, the master just feeds the loop
   **** with the specified numbers.
   **** However, any prime factors of a number that are greater than 
   **** 2^16 (which is the largest prime that we generate)
   **** will make a complete circuit through the loop.
   **** So we listen for those messages and store them in a 
   **** FactorRecord queue just like the slaves.
   ****
   ***/

   start2 = MPI_Wtime();

   numnumbers = len;
   
   for (i=0; i< numnumbers; i++) {
       /*
	* First check the receive queue
	*/
       MPI_Iprobe(previd, STAGE2, MPI_COMM_WORLD, &msgWaiting, &status) ;
       if (msgWaiting) {
	   /*
	    * We have a prime factor that is greater than
	    * 2^16.
	    */
	   
	   MPI_Recv(data, 2, MPI_UNSIGNED, previd, STAGE2,
		    MPI_COMM_WORLD, &status); 
	   /* 	   printf("master received %d %d from %d\n", *data, *(data+1), previd) ; */
	   
	   /*
	    * Store this prime factor record in the master process
	    */
	   FactorInsert(*data, *(data+1), 1) ;
	   
       }
       

       /*
	* First number is original, second is what's left to factor 
	*/
       *data = numbers[i] ;
       *(data + 1) = numbers[i] ;
       
       MPI_Send(data, 2, MPI_UNSIGNED, nextid,  
		STAGE2, MPI_COMM_WORLD); 
   }
   
   /*
    * Again we have to send a message token around to make sure that
    * we have processed all primes.
    */
   *data = ENDSTAGE2 ;
   *(data + 1) = 0 ;
   MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE2, MPI_COMM_WORLD) ;

   done = 0 ;
   while (!done) {
       MPI_Recv(data, 2, MPI_UNSIGNED, previd, STAGE2, MPI_COMM_WORLD, 
		&status);
       
       if (*data == ENDSTAGE2) {
	   done = 1 ;
       } else {
	   FactorInsert(*data, *(data+1), 1) ;
       }
   }

   end2 = MPI_Wtime();
   printf("Factoring %d numbers on %d CPUs took %lf\n", 
	  len, numprocessors - 1, end2 - start2);

/*    PrintFactors(0) ; */
   
   *data = GOTOSTAGE3 ;
   *(data + 1) = 0 ;
   MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE2, MPI_COMM_WORLD) ;
   MPI_Recv(data, 2, MPI_UNSIGNED, previd, STAGE2, MPI_COMM_WORLD, &status); 

   fprintf(stderr, "Master done with stage 2\n") ;

   /*** 
   **** STAGE 3.
   ****
   **** Collect the factorization results from slave processes.
   ****
   **** For each number that was factored, master queries each slave process
   **** for its list of (factor, power) pairs for this number. When the 
   **** slave process receives a request from master for a list of pairs,
   **** it first counts how many factors it has for this number, sends
   **** this information to the master in one message,  and then sends
   **** the actual list in the next message.
   ****
   **** After receiving a list of (factor, power) pairs for a number
   **** from a slave, the master inserts each of these pairs in the
   **** appropriate place of the list of ALL factors for this number.
   ****
   ***/

   /* loop through all factored numbers */
   for (i=0; i<numnumbers; i++) {
     FactorRecord *element;


     /* totfactors stores 2*number of currently accumulated factors 
      * for the current number, numbers[i] */
     totfactors = 0;

     /* query each slave process */
     for (j=1; j<numprocessors; j++) {
       *data = numbers[i] ;
       *(data + 1) = numbers[i] ;

       /* send slave 'j' the number that was factored */
       MPI_Ssend(data, 2, MPI_UNSIGNED, j,  
		STAGE3, MPI_COMM_WORLD); 

       /* receive from slave 'j' how many factors it has for this number */
       MPI_Recv(data, 2, MPI_UNSIGNED, j, 
		STAGE3,	MPI_COMM_WORLD, &status); 
       nfactors = data[0];
       number = data[1];

       if (nfactors > 0) {
	 /* receive from slave 'j' the list of (factor, power) pairs */
	 MPI_Recv(factors, 2*nfactors, MPI_UNSIGNED, j, 
		  STAGE3, MPI_COMM_WORLD, &status); 
	 
	 /* add factors supplied by slave 'j' to list of factors
	  * for the current number, maintaining the ascending sorting order */
	 for (k = 0; k < nfactors; k++) {
	   int cur, ind;

	   /* find the smallest factor found so far 
	    * at is larger than the new one */
	   for (cur = 0; cur < totfactors; cur += 2) {
	     if (prfactors[cur] > factors[2*k])
	       break;
	   }
	   /* shift data up if needed */
	   for (ind = totfactors; ind > cur; ind -= 2) {
	     prfactors[ind] = prfactors[ind-2];
	     prfactors[ind+1] = prfactors[ind-1];
	   }
	   /* insert new factor at the right place */
	   prfactors[cur] = factors[2*k];
	   prfactors[cur+1] = factors[2*k+1];
/* 	   printf("inserting factor %d at %d, total %dd\n ",  */
/* 		  factors[2*k], cur, totfactors); */
	   totfactors += 2;
	 }
       }
     }

     element = factorQ->head ;
     /* count how many factors master has for the requested number,
      * (it can have at most one)
      * and put (factor, power) pair, if found in the 'prfactors' buffer
      */
     while (element != NULL) {
       if (element->original == numbers[i]) {
	 prfactors[totfactors]   = element->factor;
	 prfactors[totfactors+1] = element->power;
	 totfactors += 2;
       }
       element = element->next;
     }

     printf("factors of %6d: ", numbers[i]);
     for (k = 0; k < totfactors-2; k += 2) {
       printf("%d^%d * ", prfactors[k], prfactors[k+1]);
     }
     printf("%d^%d", prfactors[k], prfactors[k+1]);
     printf("\n");
     fflush(stdout);
   }
   
   /* tell all slave processes we are done */
   *data = ALLDONE ;
   *(data + 1) = 0 ;
   for (j=1; j<numprocessors; j++) {

     MPI_Ssend(data, 2, MPI_UNSIGNED, j,  
	       STAGE3, MPI_COMM_WORLD); 

     MPI_Recv(data, 2, MPI_UNSIGNED, j, 
	      STAGE3,	MPI_COMM_WORLD, &status); 
   }

   fprintf(stderr, "Master done with stage 3\n") ;

   free(data);
}





/* Each slave will enter this function parameterized by its own id */
void primegenerateslave(int id)
{
  int previd = 0;
  int nextid = 0;
  MPI_Status status;
  unsigned int *data ;
  int done = 0;
  static unsigned factors[MAX_FACTORS*2]; /* buffer to send to master */
  unsigned nfactors;                      /* number of (factor, power) pairs */
                                          /* in the 'factors' buffer */

  double stage2Start, countStart, countEnd, totalTime ;
  double msgRecvTime = 0, msgSendTime = 0, computeTime = 0 ;
  data  = (unsigned int *) malloc(sizeof(unsigned int) * 2);

  /* compute the prev and next machines in the ring relative to me */
  previd = (id - 1) % numprocessors;

  nextid = (id + 1) % numprocessors;

  /* ask this process to initialize itself */
  Initialize(id);

  /*** 
  **** STAGE 1
  **** 
  **** In this stage, there are two three kinds of messages that
  **** can arrive. 
  **** 1. A possible prime
  ****      See if it is evenly divided by one of the primes in this 
  ****      processes' prime queue. If so, drop it.  Otherwise pass it on.
  **** 2. A prime destined for this process.
  ****      Add it to the prime queue.
  **** 3. A prime destined for another process.
  ****      Pass it on.
  **** 4. A token marking the end of all possible primes.
  ****      Pass it on.
  **** 5. A message telling everyone to go to stage 2.
  ****      Move to stage 2. 
  ****
  **** Messages are differentiated by an unsigned integer field that preceeds
  **** the data of every message.
  ****/


  /* begin to receive prime numbers until they are done (signified by a -1)*/
  while (!done) 
  {
      MPI_Recv(data, 2, MPI_UNSIGNED, previd, STAGE1, 
	   MPI_COMM_WORLD, &status);
      
/*       printf("%d: S1 : %f : Received %d %d\n", id, MPI_Wtime(),  */
/* 	     *data, *(data + 1)) ; */

      /* 
       * First unsigned int is a tag identifying the type of message 
       */
      if (*data == POSSIBLE_PRIME) {
	  /* 
	   * We received a potential prime, so we need to test it. 
	   * First, see if any of the numbers maintained by this process 
	   * will divide the number
	   * If so, then get ride of the number (do not send it any further) 
	   */

	  if (primeQ->largest_prime == 0) {
	      /*
	       * Initial condition
	       * Just pass it on.
	       */
	      MPI_Send(data, 2, MPI_UNSIGNED, nextid,
                        STAGE1, MPI_COMM_WORLD) ;
/* 	      printf("%d: S1 : %f : Sending %d to %d\n", id, MPI_Wtime(), */
/* 		     *(data+1), nextid) ; */
	      
	  } else if (Divide( *(data+1) ) == 0) {   
	      /* 
	       * did not divide the prime 
	       * Pass it on so others can check it.
	       */
	      MPI_Send(data, 2, MPI_UNSIGNED, nextid, 
			STAGE1, MPI_COMM_WORLD) ;
/* 	      printf("%d: S1 : %f : Sending %d to %d\n", id, MPI_Wtime(), */
/* 		     *(data+1), nextid) ; */
	  } else {
	      /* 
	       * Drop it.
	       */
/* 	      printf("%d : S1 : %f : Divided %d\n", id, MPI_Wtime(), */
/* 		     *(data+1)) ; */
	  }
      } else if (*data == id) {
	  /*
	   * Message is a new prime destined for this process
	   * Add it to our prime list
	   */
	  PrimeInsert(*(data+1)) ;
      } else if (*data < numprocessors) {
	  /*
	   * Message is a new prime destined for another process.
	   * Pass it on.
	   */
	  MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE1, 
		    MPI_COMM_WORLD) ;
/* 	  printf("%d: S1 : %f : Sending %d to %d\n", id, MPI_Wtime(), */
/* 		 *(data+1), nextid) ; */
	  
      } else if (*data == ENDSTAGE1) {
	  /*
	   * This token marks the end of the possible prime stream
	   */
	  MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE1, 
		   MPI_COMM_WORLD) ;
      } else if (*data == GOTOSTAGE2) {
	  /*
	   * All primes have been generated, move to stage 2
	   * where numbers will be factored
	   */
	  MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE1, 
		   MPI_COMM_WORLD) ;
	  done = 1 ;
      } 
  }

  
  /***
  **** STAGE 2
  ****
  **** This is the factoring stage. The master passes numbers to be
  **** factored around the loop. Each process tries to factor the number,
  **** attempting to divide the number by every prime it has.
  **** The process will store a record of how many times each prime evenly
  **** divided the number. Then it will pass on the remaining part of the
  **** number that it could not factor to the next process.
  ****
  **** There are only two kinds of messages a process can receive in this
  **** stage:
  ****
  **** 1. A number to factor. Actually, it is two numbers. The first number
  ****    is the original number (to be used as an identifier), and he
  ****    second value is the actual number to be factored.
  **** 2. A message telling the process to move to stage three, since all
  ****    the necessary numbers have been factored.
  ****
  ****/

  stage2Start = MPI_Wtime() ;

/*   fprintf(stderr, "%d: moving to stage 2\n", id) ; */
  done = 0;
  while (!done) {
      countStart = MPI_Wtime() ;
      MPI_Recv(data, 2, MPI_UNSIGNED, previd, STAGE2, 
	       MPI_COMM_WORLD, &status);
      countEnd = MPI_Wtime() ;
      msgRecvTime += (countEnd - countStart) ;

/*       printf("%d: S2 : %f : Received %d %d\n", id, MPI_Wtime(),   */
/* 	     *data, *(data + 1)) ;  */

      if (*data > 1 ) {
	  /*
	   * We have a number to factor!
	   */
	  unsigned int number ;
	  
	  countStart =  MPI_Wtime() ;
	  number = Factor(*data, *(data + 1)) ;
	  countEnd = MPI_Wtime() ;
	  computeTime += (countEnd - countStart) ;

	  if (number > 1) {
	      /* 
	       * Still data left to factor. Pass it on to the next
	       * process.
	       */
	      *(data + 1) = number ;

	      countStart = MPI_Wtime() ;
	      MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE2, 
			MPI_COMM_WORLD) ;
	      countEnd = MPI_Wtime() ;
	      msgSendTime += (countEnd - countStart) ;

	  }
      } else if (*data == ENDSTAGE2) {
	  countStart = MPI_Wtime() ;
	  MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE2, 
		   MPI_COMM_WORLD) ;
	  countEnd = MPI_Wtime() ;
	  msgSendTime += (countEnd - countStart) ;
      } else if (*data == GOTOSTAGE3) {
	  countStart = MPI_Wtime() ;
	  MPI_Send(data, 2, MPI_UNSIGNED, nextid, STAGE2, 
		   MPI_COMM_WORLD) ;
	  countEnd = MPI_Wtime() ;
	  msgSendTime += (countEnd - countStart) ;
	  done = 1 ;
      }
  }

  
  totalTime = MPI_Wtime() - stage2Start ;
  printf("%d: Total time in stage 2: %f\n", id, totalTime) ;
  printf("%d: Compute time         : %f\n", id, computeTime) ;
  printf("%d: MPI_Recv time        : %f\n", id, msgRecvTime) ;
  printf("%d: MPI_Send time        : %f\n", id, msgSendTime) ;
/*   fprintf(stderr, "%d: Moving to stage 3\n", id) ; */
  
/*   PrintFactors(id) ; */
/*   fflush(stdout); */

  /***
  **** STAGE3
  ****
  **** Now all the factorizations are collected by the master process.
  **** For each number that was factored, it queries each slave process
  **** for its list of (factor, power) pairs for this number. When the 
  **** slave process receives a request from master for a list of pairs,
  **** it first counts how many factors it has for this number, sends
  **** this information to the master in one message,  and then sends
  **** the actual list in the next message.
  ***/

  done = 0;
  while (!done) {
      MPI_Recv(data, 2, MPI_UNSIGNED, MASTER, STAGE3, 
	       MPI_COMM_WORLD, &status);
      
/*        printf("%d: S3 : %f : Received %d %d\n", id, MPI_Wtime(),  */
/*  	     *data, *(data + 1)) ;  */
/*        fflush(stdout); */

      if (*data > 1 ) {
	  /*
	   * We have a number to send factors for!
	   */
	FactorRecord *element;
	unsigned int number ;


	number = *(data + 1) ;

	element = factorQ->head ;
	nfactors = 0;
	/* count how many factors this slave has for the requested number,
	 * and put (factor, power) pairs in the 'factors' buffer
	 */
	while (element != NULL) {
	  if (element->original == number) {
	    factors[2*nfactors]   = element->factor;
	    factors[2*nfactors+1] = element->power;
	    nfactors++;
	  }
	  element = element->next;
	}

	/* Send message back to the master telling him how many
	 * factors we have */
	data[0] = nfactors;
	data[1] = number;
	MPI_Send(data, 2, MPI_UNSIGNED, MASTER,  
		 STAGE3, MPI_COMM_WORLD); 

	/* If we found some factors for the specified number, 
	 * send the list of (factor, power) pairs to the master */
	if (nfactors > 0) {
	  MPI_Send(factors, 2*nfactors, MPI_UNSIGNED, MASTER,  
		   STAGE3, MPI_COMM_WORLD); 
	}
      } else if (*data == ALLDONE) {
	/* master told us everything is done; acknowledge it and break out
	 * (is ack really needed here?) */
	MPI_Send(data, 2, MPI_UNSIGNED, MASTER, STAGE3, 
		 MPI_COMM_WORLD) ;
	done = 1 ;
      }
  }

  free (data);
}




static void Initialize(int id)
{

  primeQ = (PrimeQ *) malloc (sizeof(PrimeQ));  
  primeQ->largest_prime = 0;
  primeQ->queue_h = NULL;
  primeQ->queue_t = NULL;

  factorQ = (FactorQ *) malloc (sizeof(FactorQ)) ;
  factorQ->head = NULL ;
  factorQ->tail = NULL ;
  factorQ->count = 0 ;
}

static void InitializeMaster()
{

  factorQ = (FactorQ *) malloc (sizeof(FactorQ)) ;
  factorQ->head = NULL ;
  factorQ->tail = NULL ;
  factorQ->count = 0 ;
}



/* insert a prime number into the local prime number list */
static void PrimeInsert(int prime)
{
   PrimeElement *new_element = PrimeElement_New(prime);
   
/*    printf("%f: Inserting new prime %d\n", MPI_Wtime(), prime) ; */
   /* if queue is empty, then make this the first one */
   if (primeQ->queue_h == NULL) {
     primeQ->queue_h = new_element;
     primeQ->queue_t = new_element;
   }
   else {
     primeQ->queue_t->next = new_element;
     primeQ->queue_t = new_element;
   }

   /* numbers are always increasing, so every new number placed will always be the highest */
   /* we explicitly keep an extra copy for fast retrieval */
   primeQ->largest_prime = prime;
}





/* create a new prime element for the list */
static PrimeElement *PrimeElement_New(int prime)
{
    PrimeElement *element = (PrimeElement *) malloc(sizeof(PrimeElement));
    if (element == NULL) {
      printf("OUT OF MEMORY - OH NO !!!\n");
    }
    else {
       element->prime = prime;
       element->next = NULL;
    }
    return element;
}

/* insert a factor record into the local prime number list */
static void FactorInsert(unsigned int orig, unsigned int factor, 
			 unsigned int power)
{
   FactorRecord *new_element = FactorRecord_New(orig, factor, power);
   
   factorQ->count++;
   /* if queue is empty, then make this the first one */
   if (factorQ->head == NULL) {
     factorQ->head = new_element;
     factorQ->tail = new_element;
   }
   else {
     factorQ->tail->next = new_element;
     factorQ->tail = new_element;
   }
}



/* create a new prime element for the list */
static FactorRecord *FactorRecord_New(unsigned int orig, unsigned int factor,
				      unsigned int power)
{
    FactorRecord *element = (FactorRecord *) malloc(sizeof(FactorRecord));

    if (element == NULL) {
      printf("OUT OF MEMORY - OH NO !!!\n");
    }
    else {
       element->original = orig ;
       element->factor = factor ;
       element->power = power ;
       element->next = NULL;
    }
    return element;
}



/* 
 * Test if any of the numbers maintained locally divide this potential
 * prime number.
 *
 * Return 1 if it can be divided; 0 otherwise 
 */
static int Divide(unsigned int number)
{
   PrimeElement *current = primeQ->queue_h;
   unsigned halfnumber = number / 2;

   /* loop through each of the prime numbers */
   while (current != NULL) {
       if (current->prime > halfnumber) {
	   break ;
       }
      /* if it is divisible */
      if ( (number % current->prime) == 0)
	return 1;

      current = current->next;  /* go to the next one */
   }

   return 0;
}


/* 
 * Try and factor the given number with all the primes we have
 *
 * Returns: 0 if the number can be fully factored, otherwise returns
 *          the component of the number it could not factor.
 */

static unsigned int Factor(unsigned int original, unsigned int number )
{
    unsigned int power ;

    PrimeElement *current = primeQ->queue_h;

    /* loop through each of the prime numbers */
    while (current != NULL) {
	power = 0 ;

	while ( (number % current->prime) == 0) {
	    power++ ;
	    number /= current->prime ;
	}
	if (power > 0) {
	    /*
	     * We have a factor!
	     */
	    FactorInsert(original, current->prime, power) ;
	}
	
	if ( number == 1 ) {
	    /*
	     * There are no more factors
	     */
	    return 0 ;
	}

      current = current->next;  /* go to the next one */
   }

   return number ;
}



void PrintFactors(int id)
{
   FactorRecord *element;

   element = factorQ->head ;
   while (element != NULL) {

     printf("Process %d contains a factor of %d: (%d ^ %d)\n", 
	    id, element->original, element->factor, element->power);
     element = element->next;
   }
}

void PrintPrimes(int id)
{
   PrimeElement *element;

   element = primeQ->queue_h;
   while (element != NULL) {

     printf("Process %d contains prime %d\n", id, element->prime);
     element = element->next;
   }
}