/*********************************************************************
* 
*  clocksync.c
*  Brad Topol 7/15/94
*  this program is a trace event postprocessor that performs
*  Lamport style physical clock synchronizations.
*  
*  Basically we follow the algorithm presented in Les Lamport's,
*  "Time, Clocks, and the Ordering of Events in a Distributed System"
*  Communications of the ACM, July 1978, pp 558-565.
*  The main difference here of course is we do it during 
*  postprocessing, not at execution time.
*********************************************************************/

#include <stdio.h>
#include "clocksync.h"
static TimeRec previous_time[NPROC];
static LineRec lineHead[NPROC];
static LineRec *sortptr[NPROC];
static FILE *ifd;
static FILE *ofd;
static int nproc=0;

static int compteur=0;
static int boucle=0;
static int stop=0;
static int cpt=1;

/**/
/* Forward declarations */
/**/
static void lamportMax(), diffTime(), addTime(), addMu();
static bllAppend();
static int bllDelete();

/*SD*/
int R;
/*SD*/


/**********************************************************************/
main(argc, argv)
     int argc;
     char** argv;
{
  TimeRec delta_t, temp_t;
  static TimeRec tzero = {0,0};
  int i,j,src,recv_found;
  int *sortptr_flags;
  LineRec *lp;
  int total_done = 0; 
  int curr_line;
  char temp_line[MAXLINE];
/**/
/* Open the input and output files */
/**/
  ifd = stdin;
  ofd = stdout;
  if(argc >= 2) {
    ifd = fopen (argv[1], "r");
    if (ifd==NULL)
      exit(0);
  }
  if(argc >=3) {
    ofd = fopen (argv[2], "w");
    if (ofd==NULL)
      exit(0);
  }
/**/
/* Initialize timing arrays; */
/**/
  for (src=0;src<NPROC;src++) {
    previous_time[src] = tzero;
	lineHead[src].next = lineHead[src].prev = &lineHead[src];
	lineHead[src].orig_time = tzero;
  }

/**/
/* Scan input and create lists  */
/**/
  lp = (LineRec*) malloc(sizeof(LineRec));
  if (lp == NULL) {
	  fprintf(stderr,"Clocksync: memory exhausted\n");
	  exit(1);
  }
  lp->mark = 0;
  while (fgets(temp_line, MAXLINE, ifd)) {
    sscanf(temp_line, "%d", &lp->event_type);
    if(isdigit(temp_line[0])){
      switch(lp->event_type) {

      case SEND:

	sscanf(temp_line, "%*d %d %d %d %d %d %d",&lp->adjust_time.sec, 
					  &lp->adjust_time.usec, &lp->node, &lp->DEST, 
					  &lp->MSG_TAG, &lp->MSG_LEN);
	lp->orig_time = lp->adjust_time;
	nproc=_MAX(nproc, lp->node+1);
	break;


      case RECV_WAKING:
      case RECV:

	sscanf(temp_line, "%*d %d %d %d %d %d %d",&lp->adjust_time.sec, 
					  &lp->adjust_time.usec, &lp->node, &lp->SRC, 
					  &lp->MSG_TAG, &lp->MSG_LEN);
	lp->orig_time = lp->adjust_time;
	nproc=_MAX(nproc, lp->node+1);
	break;
	
      case RECV_BLOCKING:
	sscanf(temp_line, "%*d %d %d %d %d ",&lp->adjust_time.sec, 
					  &lp->adjust_time.usec, &lp->node, &lp->MSG_TAG);
	lp->orig_time = lp->adjust_time;
	nproc=_MAX(nproc, lp->node+1);
	break;

      case TRACE_START:
	sscanf(temp_line, "%*d %d %d %d %d %d %d",&lp->adjust_time.sec, 
					  &lp->adjust_time.usec, &lp->node, &lp->p1, 
					  &lp->p2, &lp->p3);
	lp->orig_time = lp->adjust_time;
	nproc=_MAX(nproc, lp->node+1);
	break;

      case TRACE_END:
	sscanf(temp_line, "%*d %d %d %d %d",&lp->adjust_time.sec, 
					  &lp->adjust_time.usec, &lp->node, &lp->p1);
	lp->orig_time = lp->adjust_time;
	nproc=_MAX(nproc, lp->node+1);
	break;

      case COMPSTATS:
	sscanf(temp_line, "%*d %d %d %d %d %d",&lp->adjust_time.sec, 
					  &lp->adjust_time.usec, &lp->node, &lp->p1, 
					  &lp->p2);
	lp->orig_time = lp->adjust_time;
	nproc=_MAX(nproc, lp->node+1);
	break;

      case 23:
      case 24:
	  sscanf(temp_line, "%*d %d %d %d %d",&lp->adjust_time.sec,
		 &lp->adjust_time.usec, &lp->node,&lp->p1);
	  lp->orig_time = lp->adjust_time;
	  nproc=_MAX(nproc, lp->node+1);
	  break;

      default:
	  fprintf(stderr, "Warning: a default value was found\n");
	  sscanf(temp_line, "%*d %d %d %d",&lp->adjust_time.sec, 
		   &lp->adjust_time.usec, &lp->node);
	  lp->orig_time = lp->adjust_time;
	  lp->event_type = -1;
	  break;
      }
    }

    bllAppend(lp, &lineHead[lp->node]);
    lp = (LineRec*) malloc(sizeof(LineRec));
    if (lp == NULL) {
	    fprintf(stderr,"Clocksync: memory exhausted\n");
	    exit(1);
    }
	lp->mark = 0;
  }
  free(lp);

  /****************************************************************/

  /* Now the fun begins... topologically traverse and adjust times*/ 

  sortptr_flags = (int *) malloc(sizeof(int)*nproc);
  if (sortptr_flags == NULL)
      {
	  fprintf(stderr,"Clocksync: memory exhausted\n");
	  exit(1);
      }
  for (i=0;i<nproc;i++)
      {
	  sortptr_flags[i] = 0;
	  sortptr[i] = lineHead[i].next;
      }
  curr_line = 0; 
  total_done = 0;
  while (total_done < nproc) {
      boucle++;
      if (stop == 1)
	  {

	      sortptr[older_recv()]->mark = MATCHED;
	      sortptr[older_recv()] = (sortptr[older_recv()]->next);
	      stop=0;
	      compteur=0;
	  }/*****************************************************************/
      if (sortptr_flags[curr_line] == DONE) {
	  /* if this guy is done, let's try another */
	  curr_line++;
	  if (curr_line == nproc)
	      curr_line = 0; 
	  continue;
      }
      switch(sortptr[curr_line]->event_type) {

      case SEND:
compteur=0;/*****************************************************************/
	  /* if a send, make sure bigger than previous */
	  /* find matching receive, (if exists), mark it */
	  /* print, update prev and move sortptr */ 
R=curr_line;
diffTime(&sortptr[curr_line]->orig_time,
			 &sortptr[curr_line]->prev->orig_time,&delta_t);
    if (delta_t.sec == 0 && delta_t.usec == 0) delta_t.usec = 1;
    addTime(&delta_t,&previous_time[curr_line]
			,&previous_time[curr_line]);
    lamportMax(&sortptr[curr_line]->adjust_time,
			   &previous_time[curr_line],
			   &sortptr[curr_line]->adjust_time);
	previous_time[curr_line] = sortptr[curr_line]->adjust_time;
	/*find match, if exists, adjust timestamp if necessary*/ 
	/*if pointer is stuck there, BUMP IT, otherwise, mark node as*/
	/*already visited*/
	recv_found = 0;
	lp = lineHead[sortptr[curr_line]->DEST].next; 
	while (lp != &lineHead[sortptr[curr_line]->DEST]) {
           if (lp->event_type == RECV || lp->event_type== RECV_WAKING) {
               if((sortptr[curr_line]->node==lp->SRC) && 
				  (sortptr[curr_line]->DEST==lp->node) && 
				  (sortptr[curr_line]->MSG_TAG==lp->MSG_TAG)){
	               if (lp->mark == 0) {
					   recv_found = 1;
					   /* found a match, adjust timestamps if nec */
					   /* and update line */
					   lp->mark = MATCHED;
					   temp_t = sortptr[curr_line]->adjust_time;
					   addMu(&temp_t);
                       lamportMax(&lp->adjust_time,&temp_t,
								  &lp->adjust_time);
					   break;
                   }
               }
           }
		   lp = lp->next;
		   /* try next one */
	}
	/* here I could worry about nonmatching sends...*/
	/* let's let ParaGraph deal with it :-)         */

    /* print the send event*/	
	if (recv_found==0) {
		fprintf(stderr, "No matching recieve for  %d %d %d %d %d %d %d\n",
		    sortptr[curr_line]->event_type, 
		    sortptr[curr_line]->adjust_time.sec, 
		    sortptr[curr_line]->adjust_time.usec, 
		    sortptr[curr_line]->node, 
		    sortptr[curr_line]->DEST,
		    sortptr[curr_line]->MSG_TAG, 
		    sortptr[curr_line]->MSG_LEN);
     }


	fprintf(ofd, "%d %d %d %d %d %d %d\n",
		    sortptr[curr_line]->event_type, 
		    sortptr[curr_line]->adjust_time.sec, 
		    sortptr[curr_line]->adjust_time.usec, 
		    sortptr[curr_line]->node, 
		    sortptr[curr_line]->DEST,
		    sortptr[curr_line]->MSG_TAG, 
		    sortptr[curr_line]->MSG_LEN);

	sortptr[curr_line] = sortptr[curr_line]->next;

	/* if pointer reaches end, increment total_done and set   */
	/* sortptr flags to DONE                                  */
	if (sortptr[curr_line] == &lineHead[curr_line]) {
		sortptr_flags[curr_line] = DONE;
		total_done++;
    }
	break;
	
      case RECV_WAKING:
      case RECV:
    if (sortptr[curr_line]->mark == MATCHED)  {
compteur=0;/*****************************************************************************/
		/* if MATCHED, the send dependency has been taken care of */
		/* and we are free to continue from this point */
		/* otherwise, try the next guy (i.e. next current line */
        diffTime(&sortptr[curr_line]->orig_time,
			 &sortptr[curr_line]->prev->orig_time,&delta_t);
        if (delta_t.sec == 0 && delta_t.usec == 0) delta_t.usec = 1;
        addTime(&delta_t,&previous_time[curr_line]
			,&previous_time[curr_line]);
        lamportMax(&sortptr[curr_line]->adjust_time,
			   &previous_time[curr_line],
			   &sortptr[curr_line]->adjust_time);
	    previous_time[curr_line] = sortptr[curr_line]->adjust_time;
	    fprintf(ofd, "%d %d %d %d %d %d %d\n",
		    sortptr[curr_line]->event_type, 
		    sortptr[curr_line]->adjust_time.sec, 
		    sortptr[curr_line]->adjust_time.usec, 
		    sortptr[curr_line]->node, 
		    sortptr[curr_line]->SRC,
		    sortptr[curr_line]->MSG_TAG, 
		    sortptr[curr_line]->MSG_LEN);
	    sortptr[curr_line] = sortptr[curr_line]->next;

	    /* if pointer reaches end, increment total_done and set   */
	    /* sortptr flags to DONE                                  */
	    if (sortptr[curr_line] == &lineHead[curr_line]) {
	    	sortptr_flags[curr_line] = DONE;
	    	total_done++;
	    }
    }
     else {
         /* this guy is temporarily stuck, let's try another */
	      curr_line++;
	   	  if (curr_line == nproc)
		      curr_line = 0; 
if (compteur > nproc) 
    {
	stop=1;
    }
compteur++;/*****************************************************************************/
     }
	break;
      case RECV_BLOCKING:
compteur=0;/*****************************************************************************/
	
        diffTime(&sortptr[curr_line]->orig_time,
			 &sortptr[curr_line]->prev->orig_time,&delta_t);
        if (delta_t.sec == 0 && delta_t.usec == 0) delta_t.usec = 1;
        addTime(&delta_t,&previous_time[curr_line]
			,&previous_time[curr_line]);
        lamportMax(&sortptr[curr_line]->adjust_time,
			   &previous_time[curr_line],
			   &sortptr[curr_line]->adjust_time);
	    previous_time[curr_line] = sortptr[curr_line]->adjust_time;
	    fprintf(ofd, "%d %d %d %d %d\n",
		    sortptr[curr_line]->event_type, 
		    sortptr[curr_line]->adjust_time.sec, 
		    sortptr[curr_line]->adjust_time.usec, 
		    sortptr[curr_line]->node, 
		    sortptr[curr_line]->MSG_TAG);
	    sortptr[curr_line] = sortptr[curr_line]->next;

	/* if pointer reaches end, increment total_done and set   */
	/* sortptr flags to DONE                                  */
	if (sortptr[curr_line] == &lineHead[curr_line]) {
	  	sortptr_flags[curr_line] = DONE;
	   	total_done++;
        }
	break;
	
      case TRACE_START:
  diffTime(&sortptr[curr_line]->orig_time,
			 &sortptr[curr_line]->prev->orig_time,&delta_t);
        if (delta_t.sec == 0 && delta_t.usec == 0) delta_t.usec = 1;
        addTime(&delta_t,&previous_time[curr_line]
			,&previous_time[curr_line]);
        lamportMax(&sortptr[curr_line]->adjust_time,
			   &previous_time[curr_line],
			   &sortptr[curr_line]->adjust_time);
	    previous_time[curr_line] = sortptr[curr_line]->adjust_time;
	    fprintf(ofd, "%d %d %d %d %d %d %d\n",
		    sortptr[curr_line]->event_type, 
		    sortptr[curr_line]->adjust_time.sec, 
		    sortptr[curr_line]->adjust_time.usec, 
		    sortptr[curr_line]->node, 
		    sortptr[curr_line]->p1,
		    sortptr[curr_line]->p2, 
		    sortptr[curr_line]->p3);
	    sortptr[curr_line] = sortptr[curr_line]->next;
	/* if pointer reaches end, increment total_done and set   */
	/* sortptr flags to DONE                                  */
	if (sortptr[curr_line] == &lineHead[curr_line]) {
	  	sortptr_flags[curr_line] = DONE;
	   	total_done++;
        }
	break;
	
      case TRACE_END:
compteur=0;/*****************************************************************************/
        diffTime(&sortptr[curr_line]->orig_time,
			 &sortptr[curr_line]->prev->orig_time,&delta_t);
        if (delta_t.sec == 0 && delta_t.usec == 0) delta_t.usec = 1;
        addTime(&delta_t,&previous_time[curr_line]
			,&previous_time[curr_line]);
        lamportMax(&sortptr[curr_line]->adjust_time,
			   &previous_time[curr_line],
			   &sortptr[curr_line]->adjust_time);
	    previous_time[curr_line] = sortptr[curr_line]->adjust_time;
	    fprintf(ofd, "%d %d %d %d %d\n",
		    sortptr[curr_line]->event_type, 
		    sortptr[curr_line]->adjust_time.sec, 
		    sortptr[curr_line]->adjust_time.usec, 
		    sortptr[curr_line]->node, 
		    sortptr[curr_line]->p1);
	    sortptr[curr_line] = sortptr[curr_line]->next;
	/* if pointer reaches end, increment total_done and set   */
	/* sortptr flags to DONE                                  */
	if (sortptr[curr_line] == &lineHead[curr_line]) {
	  	sortptr_flags[curr_line] = DONE;
	   	total_done++;
        }
	break;
	 
      case COMPSTATS:
compteur=0;/*****************************************************************************/
        diffTime(&sortptr[curr_line]->orig_time,
			 &sortptr[curr_line]->prev->orig_time,&delta_t);
        if (delta_t.sec == 0 && delta_t.usec == 0) delta_t.usec = 1;
        addTime(&delta_t,&previous_time[curr_line]
			,&previous_time[curr_line]);
        lamportMax(&sortptr[curr_line]->adjust_time,
			   &previous_time[curr_line],
			   &sortptr[curr_line]->adjust_time);
	    previous_time[curr_line] = sortptr[curr_line]->adjust_time;
	    fprintf(ofd, "%d %d %d %d %d %d\n",
		    sortptr[curr_line]->event_type, 
		    sortptr[curr_line]->adjust_time.sec, 
		    sortptr[curr_line]->adjust_time.usec, 
		    sortptr[curr_line]->node, 
		    sortptr[curr_line]->p1,
		    sortptr[curr_line]->p2);
	    sortptr[curr_line] = sortptr[curr_line]->next;
	/* if pointer reaches end, increment total_done and set   */
	/* sortptr flags to DONE                                  */
	if (sortptr[curr_line] == &lineHead[curr_line]) {
	  	sortptr_flags[curr_line] = DONE;
	   	total_done++;
        }
	break;
	
      case 23:
	  compteur=0;
	  diffTime(&sortptr[curr_line]->orig_time,
		   &sortptr[curr_line]->prev->orig_time,&delta_t);
	  if (delta_t.sec == 0 && delta_t.usec == 0) delta_t.usec = 1;
	  addTime(&delta_t,&previous_time[curr_line]
		  ,&previous_time[curr_line]);
	  lamportMax(&sortptr[curr_line]->adjust_time,
		     &previous_time[curr_line],
		     &sortptr[curr_line]->adjust_time);
	  previous_time[curr_line] = sortptr[curr_line]->adjust_time;
	  fprintf(ofd, "-3 %d %d %d %d -1 0\n",
		  sortptr[curr_line]->adjust_time.sec,
		  sortptr[curr_line]->adjust_time.usec,
		  sortptr[curr_line]->node,
		  sortptr[curr_line]->p1);
	  sortptr[curr_line] = sortptr[curr_line]->next;
	  /* if pointer reaches end, increment total_done and set   */
	  /* sortptr flags to DONE                                  */
	  if (sortptr[curr_line] == &lineHead[curr_line]) {
	      sortptr_flags[curr_line] = DONE;
	      total_done++;
	  }
	  break;

      case 24:
	  compteur=0;
	  diffTime(&sortptr[curr_line]->orig_time,
		   &sortptr[curr_line]->prev->orig_time,&delta_t);
	  if (delta_t.sec == 0 && delta_t.usec == 0) delta_t.usec = 1;
	  addTime(&delta_t,&previous_time[curr_line]
		  ,&previous_time[curr_line]);
	  lamportMax(&sortptr[curr_line]->adjust_time,
		     &previous_time[curr_line],
		     &sortptr[curr_line]->adjust_time);
	  previous_time[curr_line] = sortptr[curr_line]->adjust_time;
	  fprintf(ofd, "-4 %d %d %d %d -1 0\n",
		  sortptr[curr_line]->adjust_time.sec,
		  sortptr[curr_line]->adjust_time.usec,
		  sortptr[curr_line]->node,
		  sortptr[curr_line]->p1);
	  sortptr[curr_line] = sortptr[curr_line]->next;
	  /* if pointer reaches end, increment total_done and set   */
	  /* sortptr flags to DONE                                  */
	  if (sortptr[curr_line] == &lineHead[curr_line]) {
	      sortptr_flags[curr_line] = DONE;
	      total_done++;	      
	  }
	  break;

default:
	fprintf(stderr,"Unrecognized line !!\n");
	exit(0);
	break;
      }
}
}
/**********************************************************************/
static void
lamportMax(t1, t2, t)
     TimeRec *t1, *t2, *t;
{
  TimeRec tx;
  /* returns the max of the two plus a little if nec :-) */
  double dt = (t1->sec - t2->sec)*1000000.0 + t1->usec - t2->usec;
  if (dt>0.0) {
    tx = *t1;
  }
  else {
	tx = *t2;
  }
  /*
  if ((t1->sec - t2->sec == 0) && (t1->usec - t2->usec == 0)) {
      if (tx.usec==1000000) {
	   	  tx.sec += 1;
		  tx.usec = 0;
      }
	  else {
		tx.usec += 1;
	  }

  }
  */
  *t = tx;
}
/*********************************************************************/

static void
diffTime(t1, t2, t)
     TimeRec *t1, *t2, *t;
{    
  TimeRec tx;
  if (((t1->sec)*1000000 + t1->usec) < ((t2->sec)*1000000+ t2->usec)) {
	  fprintf(stderr,"Error: diffTimes: t1 < t2\n");
	  fprintf(stderr,"t1 = %d , t2 = %d\n",(t1->sec*1000000 
		+ t1->usec),(t2->sec*1000000+ t2->usec));
 fprintf(stderr, "%d %d %d %d %d %d %d\n",
                      sortptr[R]->event_type,
                      sortptr[R]->adjust_time.sec,
                      sortptr[R]->adjust_time.usec,
			sortptr[R]->orig_time.sec,
			sortptr[R]->orig_time.usec,    
		sortptr[R]->node,
                      sortptr[R]->DEST,
                      sortptr[R]->MSG_TAG,
                      sortptr[R]->MSG_LEN);
	exit();
  }
  if (t1->usec >= t2->usec) {
	  tx.usec = t1->usec -t2->usec;
	  tx.sec = t1->sec -t2->sec;
  }
  else {
      /* borrow a second */
      tx.usec = (t1->usec+1000000) - t2->usec;
      tx.sec = (t1->sec-1)- t2->sec;
  }
  *t = tx;

}
/*********************************************************************/
static void
addTime(t1, t2, t)
     TimeRec *t1, *t2, *t;
{    
TimeRec tx;
tx.sec = 0;  
tx.usec = 0;

tx.usec = t1->usec + t2->usec;
if (tx.usec > 999999) {
	tx.usec -= 1000000;
	tx.sec += 1;
}
tx.sec += (t1->sec + t2->sec);

*t = tx;

}
/*********************************************************************/
static void
addMu(t)
     TimeRec *t;
{    
   t->usec += MU;
   if (t->usec > 999999) {
   	   t->usec -= 1000000;
   	   t->sec += 1;
   }

}
/********************************************************************/
static int
bllDelete (old_val , head)
    LineRec* old_val ;
    LineRec* head ;
{
	LineRec  *ov = old_val ;
	LineRec  *lh = head    ;
/**/
/* Return if bad arguments */
/**/
	if ( (old_val == NULL) || (head == NULL) ||
	    (old_val == head) || (lh->next == lh) )
		return (-1);
/**/
/* Make the deletion */
/**/
	ov->prev->next = ov->next ;
	ov->next->prev = ov->prev ;
	return (0) ;
}
/**********************************************************************/
static int
bllAppend (new_val , head)
    LineRec* new_val ;
    LineRec* head ;
{
	LineRec  *nv = new_val ;
	LineRec  *bf = head ;
/*	LineRec  *lh = head ;*/ /*SD*/
/**/
/* Exit on bad args */
/**/
	if ( (new_val == NULL) || (head == NULL) || (new_val == head) )
		return (-1);
/**/
/* Do the insertion */
/**/
	nv->prev       = bf->prev ;
	nv->next       = bf ;
	nv->prev->next = nv ;
	bf->prev       = nv ;
	return (0) ;
}
/***********************************************************************/
#ifdef __STDC__
int older_recv(void)
#else
int older_recv()
#endif

{
int i;
TimeRec  old;
old.sec=sortptr[0]->adjust_time.sec;
old.usec=sortptr[0]->adjust_time.usec;
for (i=1; i<nproc; i++)
    {
	if (old.sec > sortptr[i]->adjust_time.sec)
	    {
		old.sec = sortptr[i]->adjust_time.sec;
		old.usec = sortptr[i]->adjust_time.usec;
	    }
	if (old.sec = sortptr[i]->adjust_time.sec)
	    if (old.usec >= sortptr[i]->adjust_time.usec)
		    old.usec = sortptr[i]->adjust_time.usec;
    }
return(i-1);
}