/* ---------------------------------------------------------------------------- */
/*  This code implements Chandy & Misras' algorithm  for the dining philosopers */
/*  problem.                                                                    */ 
/*  Response time      O(n)                                                     */
/*  Message Complexity O(delta)                                                 */
/*  Failure Locality   n                                                        */
/*    n  = number of nodes in graph                                             */
/* delta = degree of conflict graph                                             */
/* ---------------------------------------------------------------------------- */
#include "maisie.h"
#include <stdlib.h>
#include <sys/time.h>

#define numproc 25
#define thinking 0
#define hungry 1
#define eating 2
#define AveDegree 5.0
#define EATDELAY  5 
#define THINKDELAY 1
#define MXCLOCK "1000"

extern entity basic_stats{}; 

/*  Given an array of integers and a key integer, this function returns */
/*  the index of the key                                                */
int getindex(key,array,size)
int key;
int array[];
int size;
{
  int i,found; 
  for(i=0;i<size;i++)
    if (array[i] == key) found = i;
  return found;
}

/*  This function creates an adjacancy matrix for a graph with numproc */
/*  nodes and an average degrre of AVEDEGREE                           */
void makegraph(adj,size)
int adj[numproc][numproc];
int size;
{
  int i,j; 
  unsigned int seed;
  float tmp,tmp2;

  printf("Enter seed : ");
  seed = getchar();
  seed = seed * seed;

  tmp2 = AveDegree / size;

  for(i=0;i<size;i++) 
    for (j=0;j<(i+1);j++)
      adj[i][j] = 0;

  for (i=0;i<size;i++) {
    for (j=(i+1);j<size;j++) {
      tmp = rand_r(&seed);
      tmp = tmp / 32767;
      adj[i][j] = (tmp<tmp2);        
      adj[j][i] = (tmp<tmp2);
    }
  }
}


entity driver{}
{ ename philosophers[numproc];
  ename tmpproc[numproc];
  int tmpnum[numproc];
  int i,j,n;
  int adj[numproc][numproc];
  ename Mstat,Tstat,Wstat;	

  maxclock(MXCLOCK);
  makegraph(adj,numproc);


  Mstat = new basic_stats{"Number of Messages"}; 
  Tstat = new basic_stats{"Number of Transitions"}; 
  Wstat = new basic_stats{"Time waiting hungry"};  

  for (i=0; i<numproc; i++) {
     print("Creating philosopher %d",i);
     philosophers[i] = new philosopher{i,Mstat,Tstat,Wstat} at i;
    }
  for(i=0; i<numproc; i++) {
    n = 0;
    for(j=0;j<numproc;j++) {
      if (adj[i][j]) {
       tmpproc[n] = philosophers[j];
       tmpnum[n] = j; 
       n++;
      }
    } 
    print("Setting up philosopher %d, degree %d",i,n);
    invoke philosophers[i] with msetup {&tmpproc[0]::numproc*sizeof(ename),
                                        &tmpnum[0]::numproc*sizeof(int),
                                        n};
  }
}


entity philosopher{myid,Mstat,Tstat,Wstat}
 int myid;
 ename Mstat,Tstat,Wstat;
{ 
  message msetup {ename adj[numproc]; int adjname[numproc]; int n;} setupvar;
  message fork {int id;} forkvar;
  message request {int id;} requestvar;
  
  /* Variables to keep track of neighbors  */
  int numneighbors;
  ename neighbors[numproc];
  int intneighbors[numproc];

  /* Variables to keep track of state information */
  int state;
  int fork[numproc];
  int reqf[numproc];
  int dirty[numproc];

  /* Aux variables needed to execute C code  */
  int Last;
  float waittime;
  int i;

  state = thinking;
  wait until mtype(msetup) {
     numneighbors = msg.msetup.n;
     print("Philosopher %d receives setup message",myid);
     for (i=0;i<numneighbors;i++) {
        neighbors[i] = msg.msetup.adj[i];
        intneighbors[i] = msg.msetup.adjname[i];
        fork[i] = (myid < intneighbors[i]);
      	reqf[i] = 1 - fork[i];
     }
  }
  
  Last = cti(sclock());
  for(;;) {
    wait 1 until 
      { mtype(fork) {
        	fork[getindex(msg.fork.id,intneighbors,numneighbors)] = 1;
                dirty[getindex(msg.fork.id,intneighbors,numneighbors)] = 0;
                    }           
       or mtype(request) {
                reqf[getindex(msg.request.id,intneighbors,numneighbors)] = 1;
                       }
       or mtype(timeout);
     }

     if (state == hungry) {
       for(i=0;i<numneighbors;i++) {
         if (reqf[i] && (fork[i] == 0)) {
           invoke neighbors[i] with request { myid }; 
           invoke Mstat with value{1.0}; 
	   reqf[i] = 0;
         }
       }
     }
     if (state != eating) {
       for(i=0;i<numneighbors;i++) {
         if (reqf[i] && fork[i] && dirty[i]) {
           fork[i] = 0;
           dirty[i] = 0;
           invoke neighbors[i] with fork { myid };
           invoke Mstat with value{1.0};
         }  
       }
     }
     if (state == eating) {
         if (cti(sclock()) > (Last + EATDELAY)) {
           state = thinking;
/*           print("Philosopher #%d is Now Thinking",myid); */
	   Last = cti(sclock());
         }
    }
    if (state == thinking) {
         if (cti(sclock()) > (Last + THINKDELAY)) {
           state = hungry;
/*           print("Philosopher #%d is Now Hungry",myid); */
           Last = cti(sclock());
         }
    }
     if (state == hungry) {
       state = eating;
       for(i=0; i<numneighbors;i++) {
         if (fork[i]==0) state = hungry;
       }
       if (state == eating) {
         for(i=0; i<numneighbors;i++) {
           dirty[i] = 1;
         }
/*         print("Philosopher #%d is Now Eating",myid); */
         invoke Tstat with value{1.0}; 
         waittime = cti(sclock()) - Last;
         invoke Wstat with value{waittime};
         Last = cti(sclock());
       }
     }      
 }
}