#include <stdio.h>
#include <stdlib.h>

#include "mpi.h"





int main ( int argc, char *argv[] )

/******************************************************************************/
/*
  Purpose:

    MAIN is the main program for SEARCH.

  Discussion:

    SEARCH demonstrates the use of MPI routines to carry out a search

    An array of given size is to be searched for occurrences of a
    specific value.

    The search is done in parallel.  A master process generates the
    array and the target value, then distributes the information among
    a set of worker processes, and waits for them to communicate back
    the (global) index values at which occurrences of the target value
    were found.

    An interesting feature of this program is the use of allocatable
    arrays, which allows the master program to set aside just enough
    memory for the whole array, and for each worker program to set aside
    just enough memory for its own part of the array.

  Licensing:

    This code is distributed under the GNU LGPL license. 

  Modified:

    09 October 2002

  Author:

    John Burkardt

  Reference:

    William Gropp, Ewing Lusk, Anthony Skjellum,
    Using MPI: Portable Parallel Programming with the
    Message-Passing Interface,
    Second Edition,
    MIT Press, 1999,
    ISBN: 0262571323.
*/
{
  float factor;
  int *a, i, global, me, n, npart, np, start, target, source, tag;
  MPI_Status status;
  int tag_target = 1, tag_size = 2, tag_data = 3, tag_found = 4, tag_done = 5;
  int workers_done, x;

  MPI_Init ( &argc, &argv );
  MPI_Comm_rank ( MPI_COMM_WORLD, &me );
  MPI_Comm_size ( MPI_COMM_WORLD, &np );

  printf ( "np = %d, me = %d\n", np, me );
  /*
    Have the master process generate the target and data.  In a more 
    realistic application, the data might be in a file which the master 
    process would read.  Here, the master process decides.
  */
  if ( me == 0 )
  {
    /*
      Pick the number of data items per process, and set the total.
    */
    factor = ( float ) rand ( ) / ( float ) RAND_MAX;
    npart = 50 + ( int ) ( factor * 100.0E+00 );
    n = npart * np;

    printf ( "\n" );
    printf ( "  The number of data items per process is %d,\n", npart );
    printf ( "  The total number of data items is       %d.\n", n );
    /*
      Now allocate the master copy of A, fill it with values, and pick 
      a value for the target.
    */
    a = malloc ( n * sizeof ( int ) );
    factor = ( float ) n / 10.0E+00 ;
    for ( i = 0; i < n; i++ ) 
      a[i] = (int)(factor*(float)rand()/(float)RAND_MAX);
    target = a[n/2];

    printf ( "  The target value is %d.\n", target );
    /*
      The worker processes need to have the target value, the number of data items,
      and their individual chunk of the data vector.
    */
    for ( i = 1; i <= np-1; i++ )
    {
      MPI_Send ( &target, 1, MPI_INT, i, tag_target, MPI_COMM_WORLD );
      MPI_Send ( &npart, 1, MPI_INT, i, tag_size, MPI_COMM_WORLD );
      start = ( i - 1 ) * npart;
      MPI_Send ( a+start, npart, MPI_INT, i, tag_data, MPI_COMM_WORLD );
    }
    /*
      Now the master process simply waits for each worker process to report that 
      it is done.
    */
    workers_done = 0;
    while ( workers_done < np-1 )
    {
      MPI_Recv ( &x, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &status );
      source = status.MPI_SOURCE;
      tag = status.MPI_TAG;
      if ( tag == tag_done )
        workers_done = workers_done + 1;
      else if ( tag == tag_found )
        printf ( "Proc #%d %d %d\n", source, x, a[x] );
      else
        printf ( "  Master process received message with unknown tag = %d.\n", tag );
    }
  }
  /*
    Each worker process expects to receive the target value, the number of data
    items, and the data vector.
  */
  else 
  {
    MPI_Recv ( &target, 1, MPI_INT, 0, tag_target, MPI_COMM_WORLD, &status );
    MPI_Recv ( &npart, 1, MPI_INT, 0, tag_size, MPI_COMM_WORLD, &status );
    a = malloc ( npart * sizeof ( int ) );
    MPI_Recv ( a, npart, MPI_INT, 0, tag_data, MPI_COMM_WORLD, &status );
    /*
      The worker simply checks each entry to see if it is equal to the target
      value.
    */
    for ( i = 0; i < npart; i++ ) {
      if ( a[i] == target )
      {
        global = ( me - 1 ) * npart + i;
        MPI_Send ( &global, 1, MPI_INT, 0, tag_found, MPI_COMM_WORLD );
      }
    }
    /*
      When the worker is finished with the loop, it sends a dummy data value with
      the tag "TAG_DONE" indicating that it is done.
    */
    MPI_Send ( &target, 1, MPI_INT, 0, tag_done, MPI_COMM_WORLD );
    free ( a );
  }
  MPI_Finalize();
  return 0;
}