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

#define TAG_BCAST 123

void my_broadcast(int rank, int size, double *message);

int main(int argc, char *argv[])
{
	int rank, size;
	double message;

	MPI_Init(&argc, &argv);
	MPI_Comm_rank(MPI_COMM_WORLD, &rank);
	MPI_Comm_size(MPI_COMM_WORLD, &size);

	/* an arbitrary message */
	message = 0.0;
	if (rank == 0)
		message = 5.6789;

	/* local broadcast */
	my_broadcast(rank, size, &message);

	/* check that nodes received message */
	printf("after broadcast -- node %d -- message %f\n", rank, message);

	/* end of code */
	MPI_Finalize();
	return EXIT_SUCCESS;
}

void my_broadcast(int rank, int size, double *message)
{
	int level, maxlevel;
	int shift_ip, n_target;
	int *target_process;
	int from_process, target;
	MPI_Status recv_status;

	/* build transmission tree */

	/* size of binary tree */
	maxlevel = 0;
	while (1 << maxlevel + 1 < size)
		maxlevel++;
	/* '<<' is a bitwise shift left, so  1 << b == pow(2, b) */

	/* make space for local branch of tree */
	target_process = (int *)malloc((unsigned)(size * sizeof(int)));

	/* build the branches */
	n_target = 0;
	from_process = -1;
	n_target = 0;
	for (level = 0; level <= maxlevel; level++) {
		shift_ip = 1 << level;
		if (rank >= shift_ip)
			from_process = rank - shift_ip;
		if (rank < shift_ip) {
			target = rank + shift_ip;
			if (target < size) {
				target_process[n_target] = target;
				n_target++;
			}
		}
	}

	/* debugging output */
	fprintf(stderr, "process %d -- from_process %d -- %d targets\n",
		rank, from_process, n_target);
	if (n_target > 0) {
		for (target = 0; target < n_target; target++)
			fprintf(stderr, "process %d -- target %d\n",
				rank, target_process[target]);
	}

	/* message transmission */

	/* receive message */
	if (rank > 0) {
		fprintf(stderr, "--- receiving %d %d \n", rank, from_process);
		fflush(stderr);
		MPI_Recv(message, 1, MPI_DOUBLE, from_process, TAG_BCAST,
			 MPI_COMM_WORLD, &recv_status);
	}

	/* send message to all target processes */
	if (n_target > 0) {
		fprintf(stderr, "--- sending %d %d \n", rank, n_target);
		for (target = 0; target < n_target; target++)
			MPI_Ssend(message, 1, MPI_DOUBLE,
				  target_process[target], TAG_BCAST,
				  MPI_COMM_WORLD);
	}

	/* free up space */
	free(target_process);
}