/***********************************
  (C) Copyright 1992-1993; dit/upm
   Distributed under the conditions stated in the
   TOPO General Public License (see file LICENSE)
 ***********************************
 $Log: tree.c,v $
 * Revision 2.7  1994/11/14  18:46:14  lotos
 * fixed a minor error during offer insertion in ready queue
 *
 * Revision 2.6  1993/09/30  19:14:27  lotos
 * fix minor bug in tree drawing
 *
 * Revision 2.5  1993/06/23  15:44:45  lotos
 * remove undesired traces (level 2)
 *
 * Revision 2.4  1993/01/18  18:25:53  lotos
 * distribution issues
 *
 * Revision 2.3  1993/01/12  14:28:39  lotos
 * fix bug in tree drawing
 *
 * Revision 2.2  1992/11/17  17:27:06  lotos
 * var -> rav
 * success -> xto
 * distinguish kdatum / udatum
 *
 * Revision 2.1  1992/10/20  17:49:56  lotos
 * new KT evaluation algorithm
 * new Lbeta interface
 * cleaning, code optimization, space saving, bugs, ...
 *
 * Revision 1.10  1992/09/11  16:54:31  lotos
 * fix tree re-evaluation to take care of priorities
 *
 * Revision 1.9  1992/09/02  17:38:31  lotos
 * full remake w.r.t. News Queue
 *
 * Revision 1.8  1992/05/06  18:54:38  lotos
 * send traces to stderr
 * send traces to stderr
 * make min-delay functionality upward compatible
 *
 * Revision 1.7  92/03/05  17:37:09  lotos
 * just a few more bugs went to the hell
 * 
 * Revision 1.6  92/03/04  14:52:51  lotos
 * 100 minor bugettes
 * 
 * Revision 1.5  92/03/03  19:55:21  lotos
 * minor bug fixing
 * 
 * Revision 1.4  92/02/29  13:26:10  lotos
 * miscellaneous bug fixing
 * 
 * Revision 1.3  92/02/12  18:47:47  lotos
 * ni idea, era una version que andaba por ahi ...
 * 
 * Revision 1.2  92/01/15  12:41:05  lotos
 * a bug in frames
 * change success and values
 * 
 * Revision 1.1  92/01/14  19:25:54  lotos
 * Initial revision
 * 
 ***********************************/

#ifndef lint
static char rcsid[]= "$Id: tree.c,v 2.7 1994/11/14 18:46:14 lotos Exp $";
#endif

#include "swbus.h"
/* LINTLIBRARY */

PRIVATE void    insert_stops ();
PRIVATE void    simp_st      ();
PRIVATE rq_elem newrqe       ();

  /*------------------------------------------------
    ------------------------------------------------
    --           OBJECT MANAGEMENT                --
    ------------------------------------------------
    ------------------------------------------------*/

rq_elem  Ready_queue ;
 board   Leaves_queue;


  /*------------------------------------------------
  --------------------------------------------------
  -- function for putting information on the tree --
  --------------------------------------------------
  ------------------------------------------------*/


  
void 
eval_tree ()
{
  gate gte;
  offert  off = NULL;
  offert  offa = NULL;
  offert  off2;
  board  b;
  board  l;
  board  bth;
  board  fth;
  offert aux;  
  /* initial stuff */
  
  clean (Kt);
  reset_mmg ();
  
  for (l = get_f_leave(); l != NULL; l =  get_n_leave(l)) {
    
    if (get_type(l) == b_ii  ||
	get_type(l) == b_dl  ||
	get_type(l) == b_wt) {
      assert (l->offer->next == NULL);
      insert_rq(a_cpoff(l->offer),0);
      off = NULL;
    }      
    else  {
      gte     = l->offer->adg;
      b       = l;
      off = a_cpoff (l->offer);
    } 

    while  (off != NULL) {
      bth = brother(b); 
      fth = father(b);  
      
      switch (get_type(fth)){
      case b_hd :
	if (fth->gte[gte]) {
	  
	   offa = off;
	   while (offa != NULL) {
	     off = offa->next;
	     offa->next = NULL;
	     insert_rq (offa,fth->but);
             offa = off;
	  }

	  off = NULL;
	} else 
	  or_off (fth,off);
	break;
      case b_en :
	if (gte == EXITG) {
	  off2=off;
	  while (off2 != NULL) {
	    off2->enable    = fth;
	    off2 = off2->next;
	  }
	  offa = off;
	  while (offa != NULL) {
	     off = offa->next;
	     offa->next = NULL;
	     insert_rq (offa,fth->but);
             offa = off;
	   }
	  
	  off       = NULL;
	}  else
	  or_off (fth,off);
	break;
      case b_ds :
      case b_ch :
	or_off (fth,off);
	break;
      case b_pi :
	if  (gte == EXITG) 
	  off =  and_off (off,bth->offer);
	or_off (fth,off);
	break;
      case b_pe :
	if  (fth->gte[gte] ||  gte == EXITG) 
	  off =  and_off (off,bth->offer);
	or_off (fth,off);
	break;
      case b_ps :
	off =  and_off (off,bth->offer);
	or_off (fth,off);
	break;
      case b_re :
	if (gte != EXITG) {
	  gte  =  fth->gte_r[gte];
	  for (aux=off; aux!= NULL; aux= aux->next)
	    aux->adg= gte;
	} 
	or_off (fth,off);
	break;
      case b_kt :
	/* comprobar lo de la exitg */
	offa = off;
	while (offa != NULL) {
	  off = offa->next;
	  offa->next = NULL;
	  insert_rq (offa,fth->but);
	  offa = off;
	}
	
	off = NULL;
	break;
      default :
	  dumpcore ("strage KT while eval_treeing");
      }
      
      b    = fth;    /* go on climbing */
    }
  }
}



  /*----------------------------------------------------------
  ------------------------------------------------------------
  --  function that activates the actions that synchronize  --
  ------------------------------------------------------------
  ----------------------------------------------------------*/


  

void  
ad_gl (off)
offert off;
{  
 board brd;  
 register  int i;
 int  ot;
  
 if (konfig.trace != 0 && g_flag) {
   (void) fprintf (stderr,"%s:%s\n",
		  TSprocesses[off->but],
		  TSgates[off->but][off->adg]);
 for (i= 0; i < TSsizes[off->sort_id]; i++) 
     (void) fprintf (stderr,"\t! %s\n", 
                  draw (TSsbes[off->sort_id][i], xto[i])); 
 }
 valvar (off);
 ot = off->sort_id;
 for (i=0; i < off->actn; i ++) {
   brd= off->act[i];
   if (konfig.trace > 1 && g_flag) {
     (void) fprintf(stderr," ->%s: ",TSprocesses[brd->frm->but]);
     draw_node (brd);
     }
   remove_lq (brd);
   simp_synch (brd);
 }
 for (i=0; i < TSsizes[ot]; i ++) {
     ud_free(TSsbes[ot][i],xto[i]);
     xto[i] = NULL;
   }
   if (konfig.trace > 1 && g_flag) 
     fprintf (stderr,"\n");
}

  

void  
ex_gl (off)
offert off;
{  
 board brd;  
 int i;

 if (konfig.trace != 0 && g_flag) {
   (void) fprintf (stderr,"%s:exit ",TSprocesses[off->but]);
   for (i=0; i< TSsizes[off->sort_id]; i++) 
	  (void) fprintf (stderr, " ! %s", 
		   draw (TSsbes[off->sort_id][i],off->exp[i]->val)); 
   (void) fprintf (stderr,"\n");
 }
 if (konfig.trace > 1 && g_flag) {
   for (i=0; i < off->actn; i ++) {
     brd= off->act[i];
     (void) fprintf(stderr," ->%s: ",TSprocesses[brd->frm->but]);
     draw_node (brd);
     }
   (void) fprintf (stderr,"\n");
 }
 brd = off->enable;   
 if (brd != NULL) {
   value_en_passing(brd);
   cut (fson(brd));
   brd->sons = NULL;
   simp_synch (brd);
 } else {
   cut (Kt);
 }
}

void  
i_gl (off)
offert off;
{  
 board brd;  

 brd= off->act[0];
 if (konfig.trace != 0)
   draw_node(brd);
 remove_lq  (brd);
 simp_synch (brd);
}

  /*----------------------------------------------
  -            SIMPLIFY  TREE                   --
  ----------------------------------------------*/
      /* B1    [> synch -> synch */
      /* B1    [] synch -> synch */
      /* synch [] B     -> synch */


void   
simp_synch (brd)
board brd;

{
  register  board  bfa; 
  register  board  baux;
  register  board  ch = brd->frm->ch;
  register  board  dis = brd->frm->dis;

  if (ch != NULL || dis != NULL) {
    
    bfa   = father(brd);
    baux  = brd;
    while (bfa != NULL && get_type(bfa) != b_kt 
	   && (ch != NULL || dis != NULL)) { 
      if(bfa == brd->frm->ch )
	ch = NULL;
      if (bfa ==brd->frm->dis )
	dis = NULL;
      
      if (get_type(bfa) == b_ch  
	  || (get_type(bfa) == b_ds && fson(bfa) != baux ))  {
	sustitute_brd (bfa,baux);
	bfa = father(baux);
      } else {
	baux = bfa;
	bfa = father(baux);
      }
    }
  }
  brd->frm->ch  = NULL;
  brd->frm->dis = NULL;
  brd->btype    = b_us;
  bctbl (brd);
}



PUBLIC void
  simp_stop ()
{

  board l;

  Leaves_queue = NULL;
  insert_stops (Kt);  
  
  for (l = Leaves_queue; l != NULL; l =  l->r_leaf) {
    if (l->btype != b_fr)
      simp_st(l);
  }
}


PRIVATE void
  insert_stops (b)
    board b;
{
  if(b == NULL)
    return;
  if(b->btype == b_st)
    insert_lq(b);
  insert_stops(b->sons);
  insert_stops(b->bth);
  
}


PRIVATE void
simp_st (brd)
board brd;
{
  board    bfa;

  for(;;) {
    bfa=father(brd);
    switch (bfa->btype){
    case b_kt:
      return;
    case b_re:
    case b_hd:	/* hide STOP -> STOP */
    case b_en:	/* STOP >> B -> STOP */
      bfa->btype = b_st;
      bfa->sons  = NULL;
      freeboard(brd);
      brd=bfa;
      break;
    case b_ch:	/* B1 [] STOP [] B2 -> B1 [] B2 */
    case b_ds:
      sustitute_brd(bfa,brother(brd));
      return;
      /* STOP || STOP  -> STOP */
    case b_ps:
    case b_pe:
    case b_pi:
      if(brother(brd)->btype == b_st)
	sustitute_brd (bfa, brd);
      else
	return;
      break;
      default:
      brd=bfa;
      break;
    }
  }
}
  

   /*************** tree leaves queue management **********************/


PUBLIC  void 
  insert_lq (brd)
board brd;
{

  brd->r_leaf = Leaves_queue;
  brd->l_leaf = NULL;
  if (Leaves_queue != NULL) 
    Leaves_queue->l_leaf = brd;
  Leaves_queue = brd;

}


PUBLIC void 
  remove_lq (brd)
board brd;
{
  frame f;

  if (brd->l_leaf != NULL)  {
    brd->l_leaf->r_leaf = brd->r_leaf;
    if (brd->r_leaf != NULL) 
      brd->r_leaf->l_leaf = brd->l_leaf;
  } else  {
    if (brd->r_leaf != NULL )
      brd->r_leaf->l_leaf = NULL;
    Leaves_queue=brd->r_leaf;
  }
  brd->r_leaf = NULL;
  brd->l_leaf = NULL;
  brd->offer  = NULL;
  f =  brd->frm;

  freeoff(f->off);
  f->off = NULL;
  
}

PUBLIC  board
get_f_leave ()
{
  if (Leaves_queue !=  NULL) {
    Leaves_queue->offer  = Leaves_queue->frm->off;
  }
  return Leaves_queue;
}

PUBLIC  board
get_n_leave (brd)
board brd;
{
  board  brd2 = brd->r_leaf;

  if (brd2 != NULL) {
    brd2->offer  = brd2->frm->off;
    assert (brd2->offer->act[0] == brd2);
    assert (brd2->offer->next   == NULL);
  }

  return brd2 ;
}



 /*************** tree ready queue management ************/



PUBLIC void
  insert_rq (o,b)
offert  o;
bh_unit b;
{
  rq_elem  elem;
  rq_elem  old;
  rq_elem  temp;
  int      priority;
  int      n_elem = 1;
  offert   aux;

  elem = Ready_queue;
  old  = Ready_queue;
  priority = o->prior;
  o->but = b;

  if (elem == NULL || elem->prior < priority) {
    elem = newrqe ();
    elem->prior = priority;
    elem->next  = Ready_queue;
    Ready_queue = elem;
  } else {
    if (elem->prior != priority) {
      while (elem != NULL && priority < elem->prior) {
	old  = elem;
	elem = old->next;
      } if (elem == NULL  || elem->prior < priority) {
	temp = newrqe ();
	temp->prior = priority;
	old->next = temp;
	temp->next = elem;
	elem = temp;
      } 
    }
  }

  aux = o;
  while (aux->next != NULL) {
    n_elem ++;
    aux = aux->next;
  }
  aux->next = elem->off;
  elem->off = o;
  elem->n   += n_elem;
}


PUBLIC offert 
  get_rq ()
{
  rq_elem next;
  int     elem;
  int     e;
  offert  off;
  offert  old;

  next = Ready_queue;
  if (konfig.random != NULL && next->n != 1) {
    elem = (int)konfig.random() % (next->n);
  } else {
    elem = 0;
  }

  off = next->off;

  if (elem == 0) {
    next->off = off->next;      
    off->next = NULL;
  } else {
    for (e= elem; e > 0; e --){
      old = off;
      off = off->next;
    }
    old->next = off->next;
    off->next = NULL;
  }
  next->n --;

  if (next->n == 0) {
    Ready_queue = next->next;
  }
  return off;
}
    

PUBLIC boolean
  eof_rq()
{
  return (Ready_queue == NULL);
}

PUBLIC int
  min_delay ()
{
  board b = Leaves_queue;
  long dl = 0;
  boolean d_flag = FALSE;
  
  while(b != NULL) {
    if (b->btype == b_dl){
      d_flag = TRUE;
      if (dl == 0)
	dl = b->stime;
      else
	if (b->stime < dl)
	  dl = b->stime;
    }
    b=b->r_leaf;
  }
  if (dl != 0)
    return (int) (dl-time(NULL));
  else {
    if(d_flag)
      return 0;
    else
      return -1;
  }
}


/************** MMG ************/

PRIVATE rq_elem free_rq_elem = NULL;
PRIVATE rq_elem nowf_rq_elem = NULL;

#define RQ_BUCK 300

       /*  --         CREATE        -- */
PRIVATE rq_elem
newrqe()
{
  static   unsigned buck_size= sizeof(st_rq_elem) * RQ_BUCK;
  register rq_elem  b;
  register int    i;
  
  if (nowf_rq_elem == NULL) {
    if (free_rq_elem != NULL) {
      for (nowf_rq_elem = free_rq_elem;nowf_rq_elem->next != NULL;
	   nowf_rq_elem= nowf_rq_elem->next)
	;
      b= (rq_elem) my_malloc (buck_size);
      nowf_rq_elem->next = b;
      for (i= 0; i < (RQ_BUCK -1); i++)
	b[i].mmg= &b[i+1];
      b[RQ_BUCK -1].mmg= NULL;
    } else {
      b= (rq_elem) my_malloc (buck_size);
      free_rq_elem = b;
      nowf_rq_elem = b;
      for (i= 0; i < (RQ_BUCK -1); i++)
	b[i].mmg= &b[i+1];
      b[RQ_BUCK -1].mmg= NULL;
    }
  }
  b= nowf_rq_elem;
  nowf_rq_elem = b->mmg;
  
  b->prior    = 0;
  b->n        = 0;
  b->off      = NULL;  
  b->next     = NULL;  

  return b;
 }

       /*  --         DESTROY       -- */
PUBLIC void 
reset_freerqe ()
{
  nowf_rq_elem = free_rq_elem;
  Ready_queue  = NULL;
} 


void 
mem_init ()
{ 
  register int i;

  if (xto == NULL) {
    xto= (value_list) malloc (max_exp * sizeof(value));
    for(i= 0; i < max_exp; i++)
      xto[i]= NULL;
    suc_n= 0;
  }
}
  
  /*------------------------------------------------
    --                    DRAW                    --
    ------------------------------------------------*/

PRIVATE  void  it_tree ();
PRIVATE int doff_flag = FALSE;

void  
  dumpcore (msg)
char * msg;
{
  FILE* fopen   ();
  FILE*  core;

  if ((core= fopen ("topocore", "w")) == NULL)
    core= stderr;
  else {
    /* KJT 28/08/00: warning omitted if NDEBUG macro defined */
    #ifndef NDEBUG
      (void) fprintf (stderr, "%s\n", msg);
      (void) fprintf (stderr, "topo dumping core\n");
    #endif
  }
  (void) fprintf (core, "%s\n", msg);
  (void) fprintf (core, "-----  Kt: kernel tree  -----\n");
  dump_tree (core, Kt);
  (void) fprintf (core, "-----  Rq: Ready  queue  -----\n");
  dump_ready (core);
} 



void  
  dump_tree (fp, tree)
FILE * fp;
board  tree;
{
  it_tree (fp, 0, tree,1);
}


void   
  draw_tree (b)
board b;
{
  dump_tree (stderr,b);
}


   
PRIVATE  void  
it_tree (fp, indent,  tree,t)
FILE * fp;
 int  indent;
board tree;
int t;

{
  
int i;

  if ( tree != NULL) {
    
    switch (t){
    case 1 :		/* tree */
      if (tree->sons != NULL) {
	if (tree->sons->bth != NULL) {
	  it_tree (fp, (indent +1), tree->sons    , 1);
	  for (i=0; i< indent; i++) 
		(void) fprintf (fp, "  ");
	  dump_node (fp, tree);
	  if (doff_flag)
	    dump_off  (fp, tree->offer);
	  
	  it_tree (fp, (indent +1), tree->sons->bth, 1);
	} else {
	  for (i=0; i< indent; i++) 
	    (void) fprintf (fp, "  ");
	  dump_node (fp, tree);
	  if (doff_flag)
	    dump_off  (fp, tree->offer);
	  it_tree (fp, (indent +1), tree->sons    , 1);
	}
      } else {
	for (i=0; i< indent; i++) 
	  (void) fprintf (fp, "  ");
	dump_node (fp, tree);
	if (doff_flag)
	  dump_off  (fp, tree->offer);
      }
     break;
    case 2 :		/* queue */
      for (i=0; i< indent; i++) 
	(void) fprintf (fp, "  ");
      dump_node (fp, tree);
      it_tree (fp,   indent   , tree->r_leaf , 2); 
    } 
  } 
  
}
  



void   
  dump_leaves (fp)
FILE * fp;
{
  it_tree(fp, 0, Leaves_queue, 2);
}

void   
draw_leaves ()
{
  dump_leaves (stderr);
}

void   
  dump_ready  (fp)
FILE * fp;
{
  rq_elem aux = Ready_queue;
  
  while (aux != NULL) {
    dump_off (fp,aux->off);
    aux = aux->next;
  }
}

void  
  draw_ready ()
{
  dump_ready (stderr);
}



void 
  dt ()
{ 
  draw_tree(Kt);
}



