#include <stdio.h>
#include "mpi.h"

int bcast_linear_segment_size;

int bcast_linear(void *buf,int count, MPI_Datatype datatype, int root, MPI_Comm comm)
{
  int tag = 5000;
  MPI_Status status;
  MPI_Request req;
  int rank,phase,pipe_length;
  int i,j;
  int last_count;
  int send_size;
  int total_node;

  int *send_to;
  int *recv_from;
  int *sequence;

  MPI_Comm_rank(MPI_COMM_WORLD,&rank);
  MPI_Comm_size(MPI_COMM_WORLD,&total_node);
  // TOPOLOGY UNAWARE                                                                                                           
  send_to = (int *) malloc (total_node * sizeof (int));
  recv_from = (int *) malloc (total_node * sizeof (int));
  sequence = (int *) malloc (total_node * sizeof (int));

  for (i=0;i<total_node;i++)
    {
      send_to[i] = i+1;
      recv_from[i] = i-1;
      sequence[i] = i;
    }
  recv_from[0] = -1;
  send_to[total_node-1] = 0;

  // when a message is smaller than a block size 
  if (count <= bcast_linear_segment_size)
    {
      for (i=0;i<total_node-1;i++)
	{
	  if ((send_to[rank] != -1) && (sequence[rank] == i))
	    MPI_Send(buf,count,datatype,send_to[rank],tag,MPI_COMM_WORLD);

	  if ((recv_from[rank] != -1) && (sequence[rank] == i+1))
	    MPI_Recv(buf,count,datatype,recv_from[rank],tag,MPI_COMM_WORLD,&status);
	}
      free(send_to);
      free(recv_from);
      free(sequence);
      return 0;
    }

  pipe_length = (count-1)/bcast_linear_segment_size + 1;
  last_count = count%bcast_linear_segment_size;
  phase = pipe_length+total_node-2;

  // last message has the same size as all the rest
  if (last_count == 0)
    {
      for (i=0;i<phase;i++)
	{
	  if ((send_to[rank] != -1) && (i >= sequence[rank]) && (i < (pipe_length + sequence[rank])))
	    MPI_Send(buf+(bcast_linear_segment_size*(i-sequence[rank])),bcast_linear_segment_size,datatype,send_to[rank],tag,MPI_COMM_WORLD);

	  if ((recv_from[rank] != -1) && (i >= sequence[rank] -1) && (i <pipe_length + sequence[rank] -1 ))
	    MPI_Recv(buf+(bcast_linear_segment_size*(i-sequence[rank]+1)),bcast_linear_segment_size,datatype,recv_from[rank],tag,MPI_COMM_WORLD,&status);
	}
    }
  else
    {
      send_size = bcast_linear_segment_size;
      for (i=0;i<phase;i++)
	{
	  if ((send_to[rank] != -1) && (i >= sequence[rank]) && (i < (pipe_length + sequence[rank])))
	    {
	      if (i == (pipe_length + sequence[rank] - 1))
		send_size = last_count;
	      MPI_Send(buf+(bcast_linear_segment_size*(i-sequence[rank])),send_size,datatype,send_to[rank],tag,MPI_COMM_WORLD);
	    }
	  if ((recv_from[rank] != -1) && (i >= sequence[rank] -1) && (i <pipe_length + sequence[rank] -1 ))
	    {
	      if (i == (pipe_length + sequence[rank] - 2))
		  send_size = last_count;
	      MPI_Recv(buf+(bcast_linear_segment_size *(i-sequence[rank]+1)),send_size,datatype,recv_from[rank],tag,MPI_COMM_WORLD,&status);
	    }
	}
    }
  free(send_to);
  free(recv_from);
  free(sequence);
  return 0;
}