#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define	MAXLENGTH	50

/* Global variables for the tree structure */
#define	DEPTH		2
#define	BRANCHES	2
int	level=0;
int	pids[BRANCHES];

/* Global variables for the pipes communication */
#define R		0
#define W		1
struct descriptor {
	int	parent[2];
	int	child[2];
} 	fd[BRANCHES]; 
int	fdpw,fdpr;
char	lineage[20] = "0\0"; /* initalised to root id */

/* Global variables for the semaphore communication */
int	semid;

/* Global variables for the FIFO communication */
char    myfifo[9] = "./rw.fifo";
#define	MYFIFO	"./rw.fifo"	

void spawn(void);
void fifo_comm(void);
void pipe_comm(char *s);
void pipe_close(void);
void pass_lineage(void);
void read_lineage(void);
void write_parent(char s[]);
void read_children(char s[]);
void wait_kids(void);
void infantcide(void);
void pid_term(int process);
void itoa(int n, char s[] );
void reverse(char s[]);

main()
{
	int	i;
	char	s[100] = "\0";
	
	signal(SIGTERM,infantcide);

	/* The following section is used to define the global    */
	/*  semaphore, with ID stored in semid, and to initalise */
	/*  it's value to 1                                      */

	semid=semget(IPC_PRIVATE,1,IPC_CREAT|0600);
	if ( semid <  0 ) {
		printf("semget failed : semid %d\n",semid);
		exit(1);
	}
	else {
		printf("Success semget: semid %d\n",semid);
	}
	if((i=semctl(semid,0,SETVAL, 1)) == 0 ) {
   	  printf("Success semctl SETVAL: %d\n",semctl(semid,0,GETVAL,0));
	}
	else {
		printf("semctl failed :  %d\n",i);
		exit(1);
	}

	/* The next command simply creates a fifo                */
		
	if((i=mkfifo((char *)MYFIFO,00600))<0) {
		printf("mkfifo failed :  %d\n",i);
		exit(1);
	}
	else 
		printf("Success in mkfifo\n");

	fflush(stdout); /* clear buffer before recursion */

	/* spawn command creates a tree stucture of processes with    */
	/* level DEPTH and number of children per node BRANCHES.      */
	/* At each node two half-duples pipes are created between it  */
	/* and its parent and between it and each one if its children */

	spawn();
	
	/* The code executes the pipes communication component of this     */
	/* assignment. To demonstrate the comminication works, each node   */
	/* determines its lineage by reading a string from its parent, it  */
	/* then passes the string onto its children, adding and extra      */
	/* character describing the childs index number. To demonstrate    */
	/* the pipe communications in the other way, the leaves send back  */
	/* their lineage strings, with a comma attached for readability,and*/
	/* each node concatenates all its child lineage strings and passes */
	/* this string to its parent. In the end, the root node receives a */
	/* string with leaf lineages seperated by commas.                  */

	pipe_comm(s);  

	/* The code executes the fifo communication  and semaphore usage   */
	/* component of this assignment. The fifo has already been created.*/
	/* The the root and "left leaf" node ( defined to have all zeros   */
	/* in its lineage, ie. the first child of all nodes ) communicate  */
	/* in both directions through the same fifo, using a semaphore as  */
	/* a flag to control who has write access and who waits for read   */
	/* access. One process polls the semaphore for a predetermined value*/
	/* while the other process writes to the fifo. The writing process  */
	/* then resets the semaphore allowing the other process read access*/
	/* to the fifo. It then waits on a semaphore reset to know when it */
	/* should read the fifo. */

	fifo_comm(); 

	/* The semaphore is released upon completion of the fifo            */
	/* communication. */

	if(level==0)
		semctl(semid,0,IPC_RMID); /* root closes semaphore */

	/* The following code segement collapses the tree using signals */
	/* sent from the root process ( level == 0 ) */

	if ( level == 0 ) {
		infantcide();	
		wait_kids();
	}
	else if (level == DEPTH) {
		for (;;) 
			sleep(1);
	}
	else {
		wait_kids();
	}

	printf("Exiting from level %d\n",level) ;
        exit(0);
}


void fifo_comm(void)
{
	int	i,fifoid;
	char	lleaf[] = "\0",buf[80];

	/* Due to the variable size of the tree, we must reconstruct  */
	/* a copy of the left leaf's lineage to use as an identifier. */
	/* Stored as the string 'lleaf'                               */
	for(i=0;i<(DEPTH+1);i++)
		strcat(lleaf,(char *)"0");

	/* if the left leaf then enter...*/
	if( (level == DEPTH) && strcmp(lleaf,lineage) == 0 ) {
		/* open fifo with read+write access */
		fifoid=open((char *)MYFIFO,O_RDWR);
		if (fifoid>0)
			 printf("Leaf: fifo opened at %d\n",fifoid);
		else {
			printf("Leaf: Error in fifo open %d\n",fifoid);
			exit(1); 
		}
		
		/* wait on semaphore to read fifo */
		while(semctl(semid,0,GETVAL,0) == 1) 
			sleep(1);

		/* read fifo */
		if((i=read(fifoid,buf,sizeof(buf)))>0)
			printf("Leaf: Received- %s\n",buf);
		else {
			printf("Leaf: Read error %d\n",i);
			exit(1);
		}

		/* write to fifo */
		write(fifoid,"Hello Root!\n",11);

		/* Root is waiting on semaphore, reset so it can */
		/* read the fifo */
		semctl(semid,0,SETVAL,1);
		
		/* close the fifo */
		if(close(fifoid) == 0)
			printf("Leaf: fifo closed\n");	
		else
			printf("Leaf: Error in fifo close\n");
	}  
	/* if root node then enter...*/
	else if ( level == 0 ) {
		/* open fifo with read+write access */
		if ((fifoid=open((char *)MYFIFO,O_RDWR))>0)
			 printf("Root: fifo opened at %d\n",fifoid);
		else {
			printf("Root: Error in fifo open %d\n",fifoid);
			exit(1); 
		}


		/* write to fifo */
		write(fifoid,"Hello Leaf!\n",11);

		/* Leaf is waiting on semaphore, reset so it can */
		/* read the fifo */
		semctl(semid,0,SETVAL,0);

		/* wait on semaphore to read fifo */
		while(semctl(semid,0,GETVAL,0) == 0) 
			sleep(1);
		
		/* read fifo */
		if((i=read(fifoid,buf,sizeof(buf)))>0)
			printf("Root: Received- %s\n",buf);
		else {
			printf("Root: Read error %d\n",i);
			exit(1);
		}


		/* close the fifo */
		if(close(fifoid) == 0)
			printf("Root: fifo closed\n");	
		else
			printf("Root: Error in fifo close\n");
	}

	return;
}

void pipe_comm(char *s)
{
	int	i;

	if ( level == 0 ) {
		pass_lineage();
		read_children(s);
		printf("Root received %s\n",s);
	}
	else if (level == DEPTH) {
		read_lineage();
		strcpy(s,lineage);
		strcat(s,(char *)",");
		write_parent(s);
	}
	else {
		read_lineage();
		pass_lineage();
		read_children(s);
		printf("Lineage %s received %s\n",lineage,s);
		write_parent(s);
	}
	pipe_close();
	return;
}

void pipe_close(void)
{
	int	i;

	if ( level == 0 ) {
	  for(i=0;i DEPTH %d\n",level,DEPTH);
		exit(1);
	}
}

void wait_kids(void)
/* This routine simply loops until all children have died */
{
	int kids_exist = 0 ;
	int i,status;

	while( kids_exist == 0 ){
	    sleep(1);
            kids_exist = 1 ; 
	    for(i=0;i < BRANCHES; i++ ) {
	      if( waitpid(pids[i],&status,WNOHANG) == 0 ) {
	       kids_exist = 0 ; /* if any kids exist, sleep again */ 
              }
	    }
	}
}

void  infantcide(void)
/* If you are a leaf then just exit upon SIGTERM, else pass SIGTERM */
/* onto your kids and then return */
{
    int		i;

    switch (level) {
	case DEPTH:
	 printf("Leaf : pid %d , lineage %s : Received SIGTERM, exiting\n",
		getpid(),lineage); 
		exit(0);
	default:
	 for (i=0;i0   */
	i=0;
	do {		/*generate digits in reverse order */
		s[i++] = n % 10 + '0';	/* get next digit */
	} while ((n /= 10) > 0);		/* delete it */
	if (sign < 0 )
		s[i++] = '-';
	s[i] = '\0';
	reverse(s);
}

/* reverse: reverse string s in place. K&R p.62 */
void reverse(char s[])
{
	int c,i,j;
	for(i=0,j=strlen(s)-1; i < j; i++,j--) {
		c=s[i];
		s[i]=s[j];
		s[j]=c;
	}
}