/*
 * crossers.c: 
 *
 *          This program implements a solution to the river crossing problem,
 *          using a central coordinator.
 * 
 *          Before starting to cross the river, each crosser sends a two
 *          byte message to the coordinator consisting of the letter 'E'
 *          or 'W' (depending on the direction he wishes to go) followed by
 *          the crosser's id number.  The crosser then waits for a two
 *          byte message (the letters 'O' and 'K') before starting to cross.
 * 
 *          Upon finishing crossing, the crosser sends a two byte message
 *          to the coordinator, consisting of the letter 'F' followed by the
 *          the crosser's ID number.
 *
 *          The coordinator will allow any number of crossers to start crossing
 *          in a given direction, so long as there are no others waiting to go 
 *          the other way.  Once the direction of flow changes, the coordinator
 *          will let any crossers who were waiting to go in the new direction
 *          start.
 */

#include <stdio.h>
#include <unistd.h>
#include <math.h>
#include <sys/types.h>
#include <sys/socket.h>
#include "crossers_world.h"

/*
 * Report a fatal error and abort process.
 */

void fatal_error( char *s )
{
    perror( s );
    exit( 1 );
}

/*
 * Processes communicate with one another via socket pairs.  A crosser that
 * wants to send a message to the coordinator sends it on coordinator_socket[1]
 * and the coordinator receives it on coordinator_socket[0].  The coordinator
 * sends a message to crosser i on crosser_socket[i][1], who receives it
 * on crosser_socket[i][0].  Sockets are set up by the main process before
 * the crosser processes are forked.
 */

int coordinator_socket[2];
int crosser_socket[NUM_CROSSERS][2];

void crosser( int n )
/*
 * This code is executed by crosser n
 */
{
    /*
     * Keep track of which way I'm currently going.  Initially half the
     * crossers start out going each way.
     */
     
    char current_direction = ( n < NUM_CROSSERS / 2 ) ? 'E' : 'W';
     
    /* The random number generator will be used to control how much time
     * crossers spend wandering around enjoying the scenery.  Initialize this
     * to a different seed for each crosser.
     */
     
    srandom( 16 * (n + 1) );
     
    /* Loop forever alternating between crossing the river and wandering
     * around enjoying the beauty of the bank.
     */

    while ( 1 )
    { 
	char buffer[2];

	 /*
	  * Arrive at bank and get permission to cross
	  */
	arrive_at_bank( n, current_direction );
	 
        buffer[0] = current_direction;
	buffer[1] = n;
	 
	if ( send( coordinator_socket[1], buffer, 2, 0 ) != 2 )
	    fatal_error( "Crosser send request" );
	else if ( recv( crosser_socket[n][0], buffer, 2, 0 ) != 2 )
	    fatal_error( "Crosser receive" );
	else if ( buffer[0] != 'O' || buffer[1] != 'K' )
	    fatal_error( "Corrupted message received by crosser" );

	cross_river( n, current_direction );
	
	/*
	 * Check in with coordinator and enjoy the other shore
	 */
	buffer[0] = 'F'; 
	buffer[1] = n;
	 
	if ( send( coordinator_socket[1], buffer, 2, 0 ) != 2 )
	   fatal_error( "Crosser send finished" );
	 
	enjoy_scenery( n, current_direction );
	 
        /*
	 * Turn around and start over!
	 */
	current_direction = (current_direction == 'E') ? 'W' : 'E';
    }
}

void send_ok( int n )
/*
 * Send an "OK to cross" message to crosser n.
 */
{
    char buffer[2];
    buffer[0] = 'O';
    buffer[1] = 'K';
     
    if ( send( crosser_socket[n][1], buffer, 2, 0 ) != 2 )
	fatal_error( "Coordinator send OK" );
    usleep( 500000L ); /* Keep crossers from stepping on each other's heels */
}

void coordinator( void )
/*
 * This code is executed by the coordinator process.
 */
{
    /*
     * At any given time, crossers can only go in one direction.
     */
    char current_direction = ' '; /* Unspecified for now */

    /*
     * Keep count of number of crossers currently crossing and waiting to
     * go each way.
     */
    int num_crossing = 0;
    int east_waiting = 0;
    int west_waiting = 0;
     
    /*
     * Keep track of what message each crosser is waiting for a response to,
     * if any.
     */
    char waiting[NUM_CROSSERS];
    int i;
     
    for ( i = 0; i < NUM_CROSSERS; i++ ) waiting[i] = ' ';
     
    /*
     * Loop forever receiving a message and acting upon it
     */
         
    while ( 1 )
    {
	char buffer[2];
	if ( recv( coordinator_socket[0], buffer, 2, 0 ) != 2 )
	{
	     fatal_error( "Coordinator receive" );
	}
	else
	{ 
	    char message = buffer[0];
	    int sender = buffer[1];

	    switch ( message )
	    {
		case 'E':

		    /*
		     * Someone wants to go east.  Let him go if others are
		     * currently moving that way and no one is waiting to go
		     * the other way, or if no one is crossing at all.
		     */
		  
		    if ( current_direction == 'E' && west_waiting == 0 )
		    {
			send_ok( sender );
			num_crossing++;
		    }
		    else if ( num_crossing == 0 )
		    {
			current_direction = 'E';
			send_ok( sender );
			num_crossing++;
		    }
		    else
		    {
			waiting[sender] = 'E';
			east_waiting++;
		    }
		    break;
		 
		case 'W':
		 
		    /* 
		     * Someone wants to go west.  Let him go if others are
		     * currently moving that way and no one is waiting to go
		     * the other way, or if no one is crossing at all.
		     */
		  
		    if ( current_direction == 'W' && east_waiting == 0 )
		    {
			send_ok( sender );
			num_crossing++;
		    }
		    else if ( num_crossing == 0 )
		    {
			current_direction = 'W';
			send_ok( sender );
			num_crossing++;
		    }
		    else
		    {
			waiting[sender] = 'W';
			west_waiting++;
		    }
		    break;
		 
		case 'F':
		 
		    /*
		     * Someone has finished crossing.  If he was the last,
		     * then let people who are waiting to go the other way
		     * (if any) start.
		     */
		 
		    if ( --num_crossing == 0 )
		    {
			if ( current_direction == 'E' && west_waiting != 0 )
			{
			    current_direction = 'W';
			    for ( i = 0; i < NUM_CROSSERS; i++ )
			    {
				if ( waiting[i] == 'W' )
				{
				    waiting[i] = ' ';
				    send_ok(i);
				    num_crossing++;
				    west_waiting--;
				}
			    }
			}
			else if ( east_waiting != 0 )
		        {
			    current_direction = 'E';
			    for ( i = 0; i < NUM_CROSSERS; i++ )
			    {
				if ( waiting [i] == 'E' )
				{
				    waiting[i] = ' ';
				    send_ok(i);
				    num_crossing++;
				    east_waiting--;
				}
			    }
			}
			else
			{
			    current_direction = ' ';
			}
		    }
		    break;
		
		default:

		    fatal_error( "Corrupted message received by coordinator" );
	    }
	}
    }
}

int main( void )
{
    int i;
    
    create_world();
     
    /*
     * Create the necessary sockets
     */
     
    if ( socketpair( AF_UNIX, SOCK_STREAM, 0, coordinator_socket ) != 0 )
	fatal_error( "Creating coordinator socket" );

    for ( i = 0; i < NUM_CROSSERS; i++ )
    {
	if ( socketpair( AF_UNIX, SOCK_STREAM, 0, crosser_socket[i]) != 0 )
	    fatal_error( "Creating crosser socket" );
    }

    /*
     * Create the crosser processes.  A newly created crosser begins
     * execution at the return from the fork with a return value of 0, and
     * so goes off and "does his thing"; the parent process gets a non-zero
     * return value and keeps creating more crossers. 
     */
     
    for ( i = 0; i < NUM_CROSSERS; i++ )
    {
	if ( fork() == 0 )
	{
	    crosser(i);
	    exit( 0 );
	} /* Actually, we never get to the exit() */
    }
    
    /*
     * After creating all the crossers, the parent program becomes the
     * coordinator for its children - a not uncommon role for a parent!
     */
     
    coordinator();
}