/* Same Fringe using threads
 * Using lwp SunOS library.
 * From Sun manual - with slight changes
 * Michael Elhadad - Jan 96
 * Compile as: gcc samefringe.c -o samefringe -llwp
 */

#include <lwp/lwp.h>
#include <lwp/stackdep.h>
#include <lwp/lwperror.h>

thread_t cmp, p1, p2;      /* Thread to compare, one for each tree    */
thread_t driver;           /* driver: set up threads and print result */
cv_t cv;                   /* condition variable for mutual exclusion */
mon_t mon;                 /* monitor - mutex on numdead variable     */
int numdead = 0;           /* num threads already completed           */

/* Tree data structure */
typedef struct tree_t {
  int val;
  struct tree_t *left, *right;
} tree_t;
#define TREENULL ((tree_t *) 0)

#define TRUE 1
#define FALSE 0

/* For thread scheduling */
#define MAXPRIO 10


/*               0-0
               /     \
           1-0        2-4
           /   \
       3-1     4-3
                 \
                  5-5

   FRINGE: 1-5-4
 */
tree_t t1[] = {
  {0, &t1[1], &t1[2]},       /* 0 */
  {0, &t1[3], &t1[4]},       /* 1 */
  {4, TREENULL, TREENULL},   /* 2 */
  {1, TREENULL, TREENULL},   /* 3 */
  {3, TREENULL, &t1[5]},     /* 4 */
  {5, TREENULL, TREENULL}    /* 5 */
};


/*                0-0
                /     \
             1-1      2-2
                     /   \
                  3-3     4-4

  FRINGE: 1-5-4
 */
tree_t t2[] = {
  {0, &t2[1], &t2[2]},       /* 0 */
  {1, TREENULL, TREENULL},   /* 1 */
  {2, &t2[3], &t2[4]},       /* 2 */
  {5, TREENULL, TREENULL},   /* 3 */
  {4, TREENULL, TREENULL}    /* 4 */
};



void compare();    /* Comparison function     */
void parsetree();  /* tree traversal function */

/* create a new thread - return thread into first param */
/* second param is the function of the thread.          */
void tfork(thread_t*, void (*adr)(), int arg);  

/* wait for up to count subthreads to terminate */
void join(int count);

/* Use this instead of lwp_destroy when using tfork and join */
void destroy(thread_t pid);

void main(int argc, char** argv) {
  int answer;

  pod_setmaxpri(MAXPRIO);    /* Set max prio for thread scheduling */
  lwp_setstkcache(10000, 5); /* Prepare stacks for 5 threads       */
  lwp_self(&driver);         /* main becomes thread driver         */

  /* Create threads */
  tfork(&cmp, compare, 0);
  tfork(&p1, parsetree, (int)t1);
  tfork(&p2, parsetree, (int)t2);

  /* Wait for any 2 threads to terminate */
  join(2);

  /* Get answer from comparator */
  msg_send(cmp, 0, 0, &answer, sizeof(answer));
  if (answer) 
    printf("Same fringe\n");
  else
    printf("Not same fringe\n");
  exit(0);
}

void compare() {
  int val1;
  thread_t next;
  thread_t sender;
  int samefringe = TRUE;
  int *resbuf;
  int ressize;
  int *argbuf;
  int argsize;
  int err;

  /* Comparator loop: receive answers from parser threads with leaf values
   * Compare them.  Resume each one in turn.
   * Act properly if one of the parser dies (arrives to end of tree).
   */
  for (;;) {

    /* Receive from any sender */
    err = MSG_RECVALL(&sender, &argbuf, &argsize, &resbuf, &ressize, INFINITY);
    if (err < 0) 
      lwp_perror("MSG_RECVALL");
    if (SAMETHREAD(sender, driver)) {
      *resbuf = samefringe;
      msg_reply(driver);
      return;
    }
    val1 = *argbuf;
    next = SAMETHREAD(sender, p1) ? p2 : p1;
    msg_reply(sender);

    /* Receive from next only */
    err = msg_recv(&next, &argbuf, &argsize, &resbuf, &ressize, INFINITY);
    if (err < 0) {
      /* next died */
      samefringe = FALSE;
      destroy(sender);
    } else {
      samefringe = (*argbuf == val1);
      if (! samefringe) {
	destroy(p1);
	destroy(p2);
      } else {
	msg_reply(next);
      }
    }
  }
}


void parsetree(tree_t* t)
{
  /* This kills the thread on end of tree */
  if (t == TREENULL)
    return;
  
  if ((t->left == TREENULL) && (t->right == TREENULL)) {
    /* leaf - send msg to comparator, don't need answer buffer */
    msg_send(cmp, &t->val, sizeof(int), 0, 0);
  } else {
    parsetree(t->left);
    parsetree(t->right);
  }
  /* end of recursion - thread dies */
}


/* Call when a thread started with tfork dies 
 * informs join by changing the value of shared variable numdead
 */
void die() {
  MONITOR(mon);    /* Gain access to monitor mon - release when exit        */
  numdead++;
  cv_notify(cv);   /* Notify all threads waiting on cv that numdead changed */
}


/* Exception handling in lwp: from the man page -
     exc_on_exit() specifies an exit procedure and argument to be
     passed  to the exit procedure, which is called when the pro-
     cedure which sets an exit handler using exc_on_exit() exits.
     The  exit  procedures  (more  than  one  may be set) will be
     called regardless if the setting procedure is exited using a
     return  or  an  exc_raise().   Because the exit procedure is
     called as if the handling procedure had returned, the  argu-
     ment  passed  to  it  should  not  contain  addresses on the
     handler's stack.  However, any value returned  by  the  pro-
     cedure  which established the exit procedure is preserved no
     matter what the exit procedure returns.  This  primitive  is
     used  in the MONITOR macro to enforce the monitor discipline
     on procedures.

     All in all: call proc and make sure that die() is called 
     whenever it returns - regardless of the way it returns.
*/
void prochelp(int (*proc)(), int arg) {
  exc_on_exit(die, 0);
  proc(arg);
}
  

/* Create a thread and make sure the monitor for join exists */
void tfork(thread_t* new, void (*adr)(), int arg) {
  static int init = 0;
  if (init == 0) {
    init = 1;
    mon_create(&mon);
    cv_create(&cv, mon);
  }
  lwp_create(new, prochelp, MINPRIO, 0, lwp_newstk(), 2, adr, arg);
}
  
void join(int cnt)
{
  MONITOR(mon);          /* Gain access to monitor - mutex on numdead */
  while (numdead < cnt)  
    cv_wait(cv);         /* while waiting, leave monitor - regain it after
                            each cv_notify */
  numdead -= cnt;
}


/* Use this instead of lwp_destroy when using tfork and join */
void destroy(thread_t pid) {
  die();
  lwp_destroy(pid);
}