/********************************************************************
*                                                                   *
* Laboratoire MASI CAO-VLSI, UPMC, Copyright 1991 1992 1993 1994    *
*                                                                   *
* Software support Email : cao-vlsi@masi.ibp.fr                     *
*                                                                   *
* Authors : Zouina AKTOUF &                                         *
*           El Arabi RHOMARI &                                      *
*           Jose MARTINS DOS SANTOS                                 *
*                                                                   *
* Supervision & Modifications : Lotfi BEN AMMAR                     *
*                                                                   *
********************************************************************/
/***********************************************************************************
*                                                                                  *
*                              router_R .c                                         *
*                                                                                  *
* Version 3.0    28/03/92                                                          *
*                                                                                  *
***********************************************************************************/

#include "dpr_R.h"
#include "util_R.h"
 long total_acc=0l;
 long total_acc_col=0l;

/***********************************************************************************
* affdprpile                                                                       *
*                                                                                  *
***********************************************************************************/
 void affdprpile(fsortie,ptacces)
 FILE *fsortie;
 ACCESS *ptacces;
 
 {
 for (;ptacces;ptacces=ptacces->PREV)
     {
     if (ptacces->POS)
        fprintf(fsortie
                ,"|	|_(ORIENT,X,Y,POS.CON.NAME)  :( %c, %ld, %ld, %s) \n "
                ,ptacces->ORIENT
                ,ptacces->POS->X
                ,ptacces->POS->Y
                ,ptacces->POS->CON->NAME);
     else
        fprintf(fsortie
                ,"|	|_(ORIENT,X,Y,obstacle)  :( %c) \n "
                ,ptacces->ORIENT);
     }
 }

/***********************************************************************************
* affdprnoeud                                                                      *
*                                                                                  *
***********************************************************************************/
 void affdprnoeud(fsortie,ptheadnoeud)
 FILE  *fsortie;
 NODE *ptheadnoeud;

 {
 NODE *ptnoeud;
 static long   i=1;
 long   j=1;
  
 fprintf(fsortie,"|________Grille de la colonne %ld \n ",i++);
 for (;ptheadnoeud;ptheadnoeud=ptheadnoeud->NEXT)
     {
     fprintf(fsortie,"|________la ligne %ld \n ",j);
     j=j+2;
     fprintf(fsortie,"|\n ");
     for (ptnoeud=ptheadnoeud;ptnoeud;ptnoeud=ptnoeud->DPR_UP)
         {
         fprintf(fsortie,"|	|(Noeud = %ld, ",ptnoeud);
         if (ptnoeud->NEXT) fprintf(fsortie,"Next = %ld, ",ptnoeud->NEXT);
            else fprintf(fsortie,"Next = (Nil), ");
         if (ptnoeud->PREV) fprintf(fsortie,"Pred = %ld, ",ptnoeud->PREV);
            else fprintf(fsortie,"Pred = (Nil), ");
         if (ptnoeud->DPR_UP) fprintf(fsortie,"Up = %ld, ",ptnoeud->DPR_UP);
            else fprintf(fsortie,"Up = (Nil), ");
         if (ptnoeud->DPR_DWN) fprintf(fsortie,"Dwn = %ld)\n ",ptnoeud->DPR_DWN);
            else fprintf(fsortie,"Dwn = (Nil))\n ");
         fprintf(fsortie,"|	|__Pile du sommet RIGHT = %ld \n ",ptnoeud->DPR_RIGHT);
         if (ptnoeud->DPR_RIGHT) affdprpile(fsortie,ptnoeud->DPR_RIGHT);
            else fprintf(fsortie,"|	|______Pile Vide RIGHT = (Nil)\n ");
         fprintf(fsortie,"|	|_______________________________________\n ");
        /*
         if (ptnoeud->DPR_LEFT)
            {
            fprintf(fsortie,"|	|LEFT = %ld\n ",ptnoeud->DPR_LEFT);
            affdprpile(fsortie,ptnoeud->DPR_LEFT);
            }
         else fprintf(fsortie,"|	|LEFT = (Nil)\n ");
        */
         }
     }
 }

/*********************************************************************
**    fonction chain_pred() : retourne l'element dans le chainage   **
**    qui est juste avant l'element ptchain en donnee.              **
*********************************************************************/
 chain_list *chain_pred(ptchead,ptchain)
 chain_list *ptchead;
 chain_list *ptchain;

 {
 chain_list *ptccour=NULL;

 for (ptccour=ptchead;ptccour;ptccour=ptccour->NEXT)
     if (ptccour->NEXT==ptchain)
        return ptccour;

 return NULL;
 }
 
/********************************************************************
**  fonction seg_inclu() : retourne TRUE si l'un des deux segment  **
**  contient l'autre sinon FALSE.                                  **
********************************************************************/
 int seg_inclu(seg1_y1,seg1_y2,seg2_y1,seg2_y2)
 long seg1_y1;
 long seg1_y2;
 long seg2_y1;
 long seg2_y2;

 {
 if (seg1_y1<=seg2_y1)
    {
    if (seg1_y2<seg2_y1)
       {
       return FALSE;
             /*     +-+  */
             /*     |2|  */
             /*     +-+  */
             /* +-+      */
             /* |1|      */
             /* +-+      */
       }
    else
       {
       return TRUE;
             /*     +-+ |     +-+ | +-+ +-+ | +-+     */
             /*     |2| | +-+ |2| | | | |2| | | | +-+ */
             /* +-+ +-+ | |1| +-+ | |1| +-+ | |1| |2| */
             /* |1|     | | |     | | |     | | | +-+ */
             /* +-+     | +-+     | +-+     | +-+     */
       }
    }
 else
    {
    if (seg1_y1<=seg2_y2)
       {
       return TRUE; 
             /* +-+     | +-+     | +-+     | +-+     */
             /* |1|     | |1|     | | |     | | | +-+ */
             /* +-+ +-+ | | | +-+ | |1| +-+ | |1| |2| */
             /*     |2| | +-+ |2| | | | |2| | | | +-+ */
             /*     +-+ |     +-+ | +-+ +-+ | +-+     */
       }
    else
       {
       return FALSE;
             /* +-+      */
             /* |1|      */
             /* +-+      */
             /*     +-+  */
             /*     |2|  */
             /*     +-+  */
       }
    }
 }

/***********************************************************
**  fonction insertseg() :insertion d'un segment dans la  **
**  colonne. avec trie et unification des segments.       **
***********************************************************/
 void insertseg(ptcol,x1,y1,x2,y2,layer,width,name)
 COLUMN *ptcol;
 long x1,x2;
 long y1,y2;
 char layer;
 long width;
 char *name;

 {
 chain_list    *ptcseg_save=NULL;
 chain_list    *ptcseg=NULL;
 SEGMENT       *ptseg=NULL;
 int            inclu=0;

 for (ptcseg=ptcol->SEG;ptcseg;ptcseg=ptcseg->NEXT)
     {
     ptseg = (SEGMENT *)ptcseg->DATA;
     if (ptseg->Y1 > y1)
        break;
     else
        if (ptseg->Y1 == y1)
           if (inclu=seg_inclu(ptseg->X1,ptseg->X2,x1,x2))
              {
              ptcseg_save = ptcseg;
              break;
              }
           else
              ptcseg_save = ptcseg;
        else
           ptcseg_save = ptcseg;
     }
 if (ptcseg_save)
    {
    if (inclu)
       {
       ptseg->X1 = dpr_min(ptseg->X1,x1);
       ptseg->X2 = dpr_max(ptseg->X2,x2);
       }
    else  
       ptcseg_save->NEXT=addseg(ptcseg_save->NEXT,name,x1,y1,x2,y2,width,'H',layer);
    }
 else
    ptcol->SEG = addseg(ptcol->SEG,name,x1,y1,x2,y2,width,'H',layer);
 }

/*************************************************************
**   fonction durcir() : Pour le traitement d'un connecteur **
** multiacce : -ajout du via .                              **
**             -ajout du segment .                          **
**             -insertin du con-sig dans le canal.          **
*************************************************************/
 void        durcir(ptccolhead,ptacces)
 chain_list *ptccolhead;
 ACCESS     *ptacces;

 {
 chain_list    *ptccol_c=NULL;
 chain_list    *ptccol_o=NULL;
 chain_list    *ptcvia=NULL;
 chain_list    *ptcvia_save=NULL;
 COLUMN        *ptcol_o;
 COLUMN        *ptcol_c;
 SIGNAL        *ptsig=NULL;
 CHANNEL       *ptchannel;
 VIA           *ptvia=NULL;
 long           x=0, y=0, x1=0, x2=0;
 char           orient;
 char           type;

# ifdef DEBUG_ROUTER
    if (DEBUG_ROUTER) fprintf(FOUT,"Entrer dans durcir :\n ");
# endif

 ptccol_o = ptacces->POS->CON->COL;
 ptcol_o = (COLUMN *)ptccol_o->DATA;
 ptsig = ptacces->SIG;
 x = ptacces->POS->X;
 y = ptacces->POS->Y;
 orient = ptacces->ORIENT;
 type = ptacces->POS->TYPE;

 if (orient==EAST)
    {
    ptccol_c = ptccol_o->NEXT;
    ptcol_c = (COLUMN *)ptccol_c->DATA;
    x1 = x;
    x2 = ptcol_o->WIDTH;
    }
 else
    {
    ptccol_c = chain_pred(ptccolhead,ptccol_o);
    ptcol_c = (COLUMN *)ptccol_c->DATA;
    x1 = 0;
    x2 = x;
    }

 /* insertion et tri si necessaire selon y du via dans la colonne. */
 if (type==MULTIAX)
    {
    for (ptcvia=ptcol_o->VIA;ptcvia;ptcvia=ptcvia->NEXT)
        {
        ptvia = (VIA *)ptcvia->DATA;
        if (ptvia->Y > y)
           break;
        else 
           if ((ptvia->X==x)&&(ptvia->Y==y))
              {
              ptcvia_save = ptcvia;
              break;
              }
           else
              ptcvia_save = ptcvia;
        }
     if (ptcvia_save)
        {
        if ((ptvia->X!=x)||(ptvia->Y!=y))
           ptcvia_save->NEXT = addvia(ptcvia_save->NEXT,x,y,(char *)CONT_VIA);
        }
     else
        ptcol_o->VIA = addvia(ptcol_o->VIA,x,y,(char *)CONT_VIA);
     }

 /*insertion du segment si necessaire, par trie selon y, dans la colonne. */
 if (x1!=x2)
    {
    insertseg(ptcol_o,x1,y,x2,y,ALU2,WLAYER2,ptsig->NAME);
    }

 /*insertion du connecteur-signal dans le canal correspondant */
 ptchannel = (CHANNEL *)ptcol_c->DF_CON->DATA;
 (void *)insertcon_inchan(ptchannel,orient,ptsig->INDEX,y);

#ifdef DEBUG_ROUTER
   if (DEBUG_ROUTER) fprintf(FOUT,"Sortie de durcir :\n ");
#endif

 }

/*****************************************************
*  mkacces                                           *
*   Creation de la structure ACCESS                   *
*****************************************************/
 ACCESS *mkacces(acc_next,acc_prev,pos,orient,signal)
 ACCESS *acc_next;
 ACCESS *acc_prev;
 POSSIBILITY *pos;
 char orient;
 SIGNAL *signal;

 {
 ACCESS *ptacces;

 ptacces = (ACCESS *)mbkalloc(sizeof(ACCESS));

 ptacces->NEXT = acc_next;
 ptacces->PREV = acc_prev;
 ptacces->POS = pos;
 ptacces->ORIENT = orient;
 ptacces->SIG = signal;
 ptacces->LAST_POS = NULL;
 ptacces->LAST_ORIENT = (char)NULL;

 total_acc++;

 return(ptacces);
 }

/**********************************************************
* del_acces                                               *
*  suprime proprement une structure acces de la liste     *
**********************************************************/
 void    del_acces(noeud,acces)
 NODE   *noeud;
 ACCESS *acces;
 
 {

 /* transformation du chainage */
 if (acces->NEXT)
    acces->NEXT->PREV = acces->PREV;
 else
    noeud->DPR_RIGHT = acces->PREV;
 if (acces->PREV)
    acces->PREV->NEXT = acces->NEXT;
 else
    noeud->DPR_LEFT = acces->NEXT;

 total_acc--;

# ifdef DEBUG_ROUTER
    /*if (DEBUG_ROUTER) printf("Suppression d'acces sig:%s en (%ld,%ld)\n"
                          ,((SIGNAL *)(acces->POS->CON->SIG->DATA))->NAME
                          ,acces->POS->X
                          ,acces->POS->Y);*/
# endif

 }


/***********************************************************
* supress_acces                                            *
*  suprime tous les acces UP et DWN latteraux              *
***********************************************************/
 void supress_acces(noeud,acces)
 NODE *noeud;
 ACCESS *acces;

 {
 NODE      *noeud1=NULL;
 ACCESS    *acces1=NULL;
 CONNECTOR *con1=NULL;
 ACCESS    *acces2=NULL;
 char       orient1='X';

 /* verification de la coherence de l'appel */
 if (acces==NULL) return;
 if (acces->POS==NULL) return;
 if (noeud==NULL) return;
 for (acces1=noeud->DPR_LEFT;acces1;acces1=acces1->NEXT)
     if (acces1==acces) break;
 if (acces1==NULL) return;

 /* l'acces durcis devient obstacle */
 con1 = acces1->POS->CON;
 orient1 = acces1->ORIENT;
 acces1->POS = NULL; 
 acces1->ORIENT = ORIENTX;
 total_acc--;

 /* on suprime les autres acces du connecteur...*/
 if (noeud->DPR_DWN)
    for (noeud1=noeud;noeud1->DPR_DWN;noeud1=noeud1->DPR_DWN);
 else
    noeud1=noeud;
 for (;noeud1;noeud1=noeud1->DPR_UP)
     {
     for (acces2=noeud1->DPR_LEFT;acces2;acces2=acces2->NEXT)
         {
         if ((acces2)&&
             (acces2->POS)&&
             (acces2->POS->CON==con1)&&
             (acces2->ORIENT))
            {
            if (acces2->ORIENT==orient1)
               del_acces(noeud1,acces2);
            else
               {
               if ((orient1==EAST)&&
                   (((COLUMN *)con1->COL->DATA)->INDEX==acces1->SIG->MIN_COL))
                  del_acces(noeud1,acces2);
               else
                  if ((orient1==WEST)&&
                      (((COLUMN *)con1->COL->DATA)->INDEX==acces1->SIG->MIN_COL+
                                                           acces1->SIG->WIDTH))
                     del_acces(noeud1,acces2);
               }
            }
         } 
     }
 }

/********************************************************
* liber_noeud
********************************************************/
 void        liber_noeud(noeud,acces,ptccol)
 NODE       *noeud;
 ACCESS     *acces;
 chain_list *ptccol;

 {
 ACCESS *acces1=NULL;
 char    orient;

 orient = acces->ORIENT;
 if (orient==EAST) /* c.a.d durcir vers la droite */
    {
    /* on cherche l'acces le plus a gauche de meme SIG et meme ORIENT */
    for (acces1=acces;acces1;acces1=acces1->PREV)
        if ((acces1->ORIENT==orient)&&(acces1->SIG==acces->SIG))
           acces=acces1;
 
    /* on supprime (ou on durcis) ce qui est plus a droite */
    for (acces1=acces;acces1;acces1=acces1->NEXT)
        {
        if (acces1->ORIENT==orient)
           /* test si meme signal */
           if (acces1->SIG==acces->SIG)
              {
              /* meme ORIENT meme SIG: durcir */
              durcir(ptccol,acces1);
              supress_acces(noeud,acces1);
              }
           else
              {  
              /* meme ORIENT autre SIG:on detruit */
              acces1 = acces1->PREV;
              del_acces(noeud,acces1->NEXT);
              }
        else
           {
           if (acces1->ORIENT==WEST)
              if (acces1->SIG!=acces->SIG)
                 {
                 /* autre ORIENT autre SIG:on detruit */
                 acces1=acces1->PREV;
                 del_acces(noeud,acces1->NEXT);
                 }
                 /* autre ORIENT meme SIG:on garde */
           }
           /* ORIENT=='durci':on garde */
        }

    /* on supprime ce qui est plus a gauche */
    for (acces1=acces->PREV;acces1;acces1=acces1->PREV)
        {
        if (acces1->ORIENT==orient)
           /* test si meme signal sur un autre connecteur */
           if (acces1->SIG!=acces->SIG)
              {
              /* meme ORIENT autre SIG:on elimine */
              acces1=acces1->NEXT;
              del_acces(noeud,acces1->PREV);
              }
        /* autre ORIENT meme SIG:on laisse */
        /* autre ORIENT autre SIG:on laisse */
        /* ORIENT=='durci':on laisse */
        }
    }
 else /* c.a.d durcir vers la gauche */
    {
    /* on cherche l'acces le plus a droite de meme SIG et meme ORIENT */
    for (acces1=acces;acces1;acces1=acces1->NEXT)
        if ((acces1->ORIENT==orient)&&(acces1->SIG==acces->SIG))
           acces=acces1;
 
    /* on supprime (ou on durcis) ce qui est plus a gauche */
    for (acces1=acces;acces1;acces1=acces1->PREV)
        {
        if (acces1->ORIENT==orient)
           /* test si meme signal */
           if (acces1->SIG==acces->SIG)
              {
              /* meme ORIENT meme SIG: durcir */
              durcir(ptccol,acces1);
              supress_acces(noeud,acces1);
              }
           else
              {  
              /* meme ORIENT autre SIG:on detruit */
              acces1 = acces1->NEXT;
              del_acces(noeud,acces1->PREV);
              }
        else
           {
           if (acces1->ORIENT==EAST)
              if (acces1->SIG!=acces->SIG)
                 {
                 /* autre ORIENT autre SIG:on detruit */
                 acces1 = acces1->NEXT;
                 del_acces(noeud,acces1->PREV);
                 }
                 /* autre ORIENT meme SIG:on garde */
           }
           /* ORIENT=='durci':on garde */
        }

    /* on supprime ce qui est plus a droite */
    for (acces1=acces->NEXT;acces1;acces1=acces1->NEXT)
        {
        if (acces1->ORIENT==orient)
           /* test si meme signal sur un autre connecteur */
           if (acces1->SIG!=acces->SIG)
              {
              /* meme ORIENT autre SIG:on elimine */
              acces1 = acces1->PREV;
              del_acces(noeud,acces1->NEXT);
              }
        /* autre ORIENT meme SIG:on laisse */
        /* autre ORIENT autre SIG:on laisse */
        /* ORIENT=='durci':on laisse */
        }
    }
 }  
  
/****************************************************
* existence                                         *
*  permet de detecter et d'estimer le cout d,une    *
*  conection eventuelle d'un connecteur quelconque  *
*  pour le signal donne                             *
****************************************************/
 ACCESS *existence(ptnoeud,ptsig,orient,nbr_acces)
 NODE   *ptnoeud;
 SIGNAL *ptsig;
 char    orient;
 long   *nbr_acces;
 
 {
 ACCESS *ptacces=NULL;
 ACCESS *ptacces_save=NULL;
 
 *nbr_acces = 0;
 if (orient==EAST)
    {
    for (ptacces=ptnoeud->DPR_RIGHT;ptacces;ptacces=ptacces->PREV)
        if (ptacces->POS)
           if ((ptsig==ptacces->SIG)&&(ptacces->ORIENT==EAST))
              break;
           else 
              (*nbr_acces)++;
        else break;
    ptacces_save = ptacces;
    if (ptacces_save)
       if (ptacces->POS)
          {
          for (ptacces=ptacces->PREV;ptacces;ptacces=ptacces->PREV)
              if (ptacces->ORIENT==EAST) 
                 (*nbr_acces)++;
          return ptacces_save;
          }
       else
          return NULL;
    else
       return NULL;
    }
 else /*orient==WEST*/
    {
    for (ptacces=ptnoeud->DPR_LEFT;ptacces;ptacces=ptacces->NEXT)
        if (ptacces->POS)
           if ((ptsig==ptacces->SIG)&&(ptacces->ORIENT==WEST))
              break;
           else
              (*nbr_acces)++;
        else break;
    ptacces_save = ptacces;
    if (ptacces_save)
       if (ptacces->POS)
          {
          for (ptacces=ptacces->NEXT;ptacces;ptacces=ptacces->NEXT)
              if (ptacces->ORIENT==WEST)
                 (*nbr_acces)++;
          return ptacces_save;
          }
       else
          return NULL;
    else
       return NULL;
    }
 }

/***************************************************************
* put_obstacle                                                 *
*  met une structure obstacle dans un noeud                    *
***************************************************************/
 void  put_obstacle(noeud)
 NODE *noeud;
 
 {
 ACCESS *acces1;

 /* verification de la coherence de l'appel */
 if (noeud==NULL) return;
 
 /* destruction de tous les acces du noeud */
 if (noeud->DPR_LEFT)
    for (acces1=noeud->DPR_LEFT;acces1;acces1=acces1->NEXT)
        {
        del_acces(noeud,acces1);
        }

# ifdef DEBUG_ROUTER
    if (DEBUG_ROUTER) printf("Durcissement d'une transparence... \n");
# endif

 /* on place un unique obstacle dans le noeud */  
 acces1 = mkacces(NULL,NULL,NULL,ORIENTX,NULL);
 total_acc--;
 noeud->DPR_RIGHT=acces1;
 noeud->DPR_LEFT=acces1;
 }

/***************************************************************
* exist_con                                                    *
***************************************************************/
 int exist_con(ptcon,ptnoeud)
 CONNECTOR *ptcon;
 NODE      *ptnoeud;
 
 {
 NODE     *ptnoeud1=NULL;
 ACCESS   *ptacces1=NULL;
 
 /* recherche sur les noeuds verticaux */ 
 if (ptnoeud->DPR_DWN) 
    for (ptnoeud1=ptnoeud;ptnoeud1->DPR_DWN;ptnoeud1=ptnoeud1->DPR_DWN);
 else 
    ptnoeud1=ptnoeud;
 for (;ptnoeud1;ptnoeud1=ptnoeud1->DPR_UP)
     {
     if ((ptnoeud1!=ptnoeud)&&(ptnoeud1->DPR_LEFT))
        {
        for (ptacces1=ptnoeud1->DPR_LEFT;ptacces1;ptacces1=ptacces1->NEXT)
            {
            if ((ptacces1->POS)&&(ptacces1->POS->CON==ptcon))
               return(TRUE);
            }
        }
     }
 return FALSE;
 }

/*********************************************************
* uniqorient                                             *
*  Fonction booleenne permettant de detecter si une      *
*  possibilite d'acces est devenu unique dans            *
*  l'orientation (EAST ou WEST)                          *
*********************************************************/
 int uniqorient(noeud,acces)
 NODE *noeud;
 ACCESS *acces;
 {
 NODE      *noeud1=NULL;
 ACCESS    *acces1=NULL;
 CONNECTOR *con=NULL;
 char       orient;
 
 /* recherche sur les noeuds verticaux */
 
 orient = acces->ORIENT;
 con = acces->POS->CON;
 if (noeud->DPR_DWN)
    for (noeud1=noeud;noeud1->DPR_DWN;noeud1=noeud1->DPR_DWN);
 else
    noeud1=noeud;
 for (;noeud1;noeud1=noeud1->DPR_UP)
     {
     if ((noeud1!=noeud)&&(noeud1->DPR_LEFT))
        {
        for (acces1=noeud1->DPR_LEFT;acces1;acces1=acces1->NEXT)
            {
            if ((acces1->POS)&&(acces1->ORIENT==orient)&&(acces1->POS->CON==con))
               return(FALSE);
            }
        }
     }

 return(TRUE);
 }

/*********************************************************
* inhibuniq                                              *
*  Fonction booleenne permettant de detecter si une      *
*  eventuelle connexion inhibe un acces unique           *
*********************************************************/
 int inhibuniq(noeud,acces)
 NODE *noeud;
 ACCESS *acces;
 {
 NODE      *noeud1=NULL;
 ACCESS    *acces1=NULL;
 CONNECTOR *con=NULL;
 char       orient;
 
 if (acces->ORIENT==WEST)
    {
    for (acces1=acces->PREV;acces1;acces1=acces1->PREV)
        {
        if ((acces1->POS)&&(acces1->SIG!=acces->SIG)&&(uniqorient(noeud,acces1)))
           return TRUE;
        }
    for (acces1=acces->NEXT;acces1;acces1=acces1->NEXT)
        {
        if ((acces1->POS)&&(acces1->SIG!=acces->SIG)&&
            (acces1->ORIENT==acces->ORIENT)&&
            (acces1->SIG->MIN_COL!=((COLUMN *)acces1->POS->CON->COL->DATA)->INDEX)&&
            (uniqorient(noeud,acces1)))
           return TRUE;
        }
    }
 else
    {
    for (acces1=acces->NEXT;acces1;acces1=acces1->NEXT)
        {
        if ((acces1->POS)&&(acces1->SIG!=acces->SIG)&&(uniqorient(noeud,acces1)))
           return TRUE;
        }
    for (acces1=acces->PREV;acces1;acces1=acces1->PREV)
        {
        if ((acces1->POS)&&(acces1->SIG!=acces->SIG)&&
            (acces1->ORIENT==acces->ORIENT)&&
            ((acces1->SIG->MIN_COL+acces1->SIG->WIDTH)!=
             ((COLUMN *)acces1->POS->CON->COL->DATA)->INDEX)&&
            (uniqorient(noeud,acces1)))
           return TRUE;
        }
    }
 return FALSE;
 }

/***************************************************************
* test_allow                                                   *
***************************************************************/
 int test_allow(noeud,ptsig)
 NODE   *noeud;
 SIGNAL *ptsig;
 
 {
 NODE *noeud1=NULL;
 NODE *noeud2=NULL;
 CONNECTOR *con1=NULL;
 ACCESS    *acces=NULL;

 /* on refuse le passage s'il y a un obstacle*/
 for (acces=noeud->DPR_LEFT;acces;acces=acces->NEXT)
     if (!acces->POS)
        return FALSE;
  
 /* on refuse le passage si on detruit une possibilite unique */
 for (acces=noeud->DPR_LEFT;acces;acces=acces->NEXT)
     if (!exist_con(acces->POS->CON,noeud))
        return FALSE;
  
 /* on refuse le passage si on detruit une possibilite unique en orientation*/
 for (acces=noeud->DPR_LEFT;acces;acces=acces->NEXT)
     if (acces->ORIENT==WEST)
        {
        if ((uniqorient(noeud,acces))&&
            (acces->SIG->MIN_COL!=((COLUMN *)acces->POS->CON->COL->DATA)->INDEX))
           return FALSE;
        }
     else /*c.a.d acces->ORIENT==EAST*/
        {
        if ((uniqorient(noeud,acces))&&
            ((acces->SIG->MIN_COL+acces->SIG->WIDTH)!=
             ((COLUMN *)acces->POS->CON->COL->DATA)->INDEX))
           return FALSE;
        }
  
 /* on refuse le passage si le signal est present dans la case */
 noeud1=noeud;
 if (noeud1->DPR_DWN) 
    for (;noeud1->DPR_DWN;noeud1=noeud1->DPR_DWN);
 for (noeud2=noeud1;noeud2;noeud2=noeud2->DPR_UP)
     for (acces=noeud2->DPR_LEFT;acces;acces=acces->NEXT)
         if (acces->SIG==ptsig)
            return FALSE;

 /* on refuse le passage si on detruit une possibilite presque unique... */
 /* a finir si necessaire... */
      
 return TRUE;
 }
	
/***********************************
*  FONCTION UTILITAIRES DU scan1_1 *
***********************************/

/**********************************************
* free_dwn                                    *
*  recherche si un acces est libre vers SOUTH *
**********************************************/
 void free_dwn(noeud,acces)
 NODE *noeud;
 ACCESS **acces;

 {
 ACCESS *acces1;

 /* initialisation du resultat a FALSE */ 
 *acces = NULL;

 /* verification de la coherence de l'appel*/
 if (noeud==NULL) return;
 if (noeud->DPR_LEFT==NULL) return;
 if (noeud->DPR_LEFT->ORIENT!=SOUTH) return;

 for (acces1=noeud->DPR_LEFT->NEXT;acces1;acces1=acces1->NEXT)
     if (acces1->ORIENT==SOUTH) return;
     
 *acces=noeud->DPR_LEFT;
 }

/**********************************************
* free_up                                     *
*  recherche si un acces est libre vers NORTH *
**********************************************/
 void free_up(noeud,acces)
 NODE *noeud;
 ACCESS **acces;

 {
 ACCESS *acces1;

 /* initialisation du resultat a FALSE */ 
 *acces = NULL;

 /* verification de la coherence de l'appel*/
 if (noeud==NULL) return;
 if (noeud->DPR_RIGHT==NULL) return;
 if (noeud->DPR_RIGHT->ORIENT!=NORTH) return;

 for (acces1=noeud->DPR_RIGHT->PREV;acces1;acces1=acces1->PREV)
     if (acces1->ORIENT==NORTH) return;
     
 *acces=noeud->DPR_RIGHT;
 }

/**********************************************
* free_trans                                  *
*  recherche si la piste est totalement libre *
**********************************************/
 int free_trans(noeud) 
 NODE *noeud;

 {
 if (noeud==NULL) return(FALSE);
 if (noeud->NEXT==NULL) return(TRUE); 
 else return(FALSE);
 }

/**********************************************
* dur_up                                      *
*  recherche si la piste a un connecteur dur  *
*  d'orientation NORTH                        *
**********************************************/
 void dur_up(noeud,acces)
 NODE *noeud;
 ACCESS **acces;

 {
 *acces=NULL;
 if (noeud==NULL) return;
 if (noeud->NEXT!=NULL)
    if (noeud->DPR_RIGHT->ORIENT==NORTH)
       if (noeud->DPR_RIGHT->POS->TYPE==TYPEFIX)
          *acces=noeud->DPR_RIGHT;
 }

/**********************************************
* dur_dwn                                     *
*  recherche si la piste a un connecteur dur  *
*  d'orientation SOUTH                        *
**********************************************/
 void dur_dwn(noeud,acces)
 NODE *noeud;
 ACCESS **acces;

 {
 *acces=NULL;
 if (noeud==NULL) return;
 if (noeud->DPR_LEFT!=NULL)
    if (noeud->DPR_LEFT->ORIENT==SOUTH)
       if (noeud->DPR_LEFT->POS->TYPE==TYPEFIX)
          *acces=noeud->DPR_LEFT;
 }

/************************************************
* present_in_line                               *
*  recherche sur toute la largeur de la colonne *
*  si le signal existe                          *
************************************************/
 int present_in_line(noeud,ptcsig)
 NODE *noeud;
 chain_list *ptcsig;
 {
 NODE *noeud1=NULL,*noeud2=NULL;
 ACCESS *acces1=NULL;
 long  cout=0;

 /* verification de la coherence de l'appel */
 if (noeud==NULL) return FALSE;
 if (ptcsig==NULL) return FALSE;

 for (noeud1=noeud;noeud1->DPR_DWN;noeud1=noeud1->DPR_DWN);
 for (;noeud1;noeud1=noeud1->NEXT)
     {
     if (existence(noeud1,ptcsig,SOUTH,&cout)) return TRUE;
     if (existence(noeud1,ptcsig,NORTH,&cout)) return TRUE;
     }
 }

/***********************************************
* scan1_1                                      *
*  Premier parcours de la grille symbolyque    *
*  la plus haute priorite aux vis a vis libres *
*  eventuellement en passent par des tranp.    *
*  'vraies' .                                  *
***********************************************/
 void scan1_1(noeud,node_r,acces_r,node_l,acces_l)
 NODE *noeud;
 NODE **node_r;
 ACCESS **acces_r;
 NODE **node_l;
 ACCESS **acces_l;

 {
 NODE *noeud1=NULL, *noeud2=NULL, *noeud3=NULL;
 ACCESS *acces1=NULL, *acces2=NULL, *acces3=NULL;
 SIGNAL *sig1, *sig2;

 *node_r=NULL;
 *acces_r=NULL;
 *node_l=NULL;
 *acces_l=NULL;

 /* Parcours de bas en haut */
 for (noeud1=noeud; noeud1 ; noeud1=noeud1->DPR_UP)
     {
     /* Parcours de gauche a droite */
     for (noeud2=noeud1; noeud2; noeud2=noeud2->NEXT)
         {
         if (noeud2->DPR_UP==NULL) /*cad la ligne UP*/
            free_up(noeud2,acces_r);
         else
            free_dwn(noeud2,acces_r);
         if (*acces_r==NULL) 
            if (noeud2->DPR_UP==NULL) /*cad la ligne UP*/
               dur_up(noeud2,acces_r);
            else
               dur_dwn(noeud2,acces_r);
         if (*acces_r) 
            {
            /* On a trouve un acces up quandidat */
            sig1=(SIGNAL *)(*acces_r)->POS->CON->SIG->DATA;
            /* Parcours de haut (juste en dessous) en bas */
            for (noeud3=noeud2->DPR_DWN; noeud3->DPR_DWN;noeud3=noeud3->DPR_DWN)
                {
                /* On passe toutes les transparences libres */
                if (free_trans(noeud3)==FALSE) break;
                }
            /* Recherches sur l'autre extremite sud*/
            if (noeud3->DPR_DWN==NULL) /*cad la ligne DWN*/
               free_dwn(noeud3,acces_l);
            else
               free_up(noeud3,acces_l);
            if (*acces_l==NULL) 
               if (noeud3->DPR_DWN==NULL) /*cad la ligne DWN*/
               dur_dwn(noeud3,acces_l);
            else
               dur_up(noeud3,acces_l);
            if (*acces_l!=NULL) 
               {
               /* On a detecte une extremite adequate */
               sig2=(SIGNAL *)(*acces_l)->POS->CON->SIG->DATA;
               if (sig1==sig2)
                  {
                  /* GAGNE! */
                  *node_r=noeud2;
                  *node_l=noeud3;
                  }
               }
            }
         if (*acces_l) break;
         }
     if (*acces_l) break;
     }
 }


/*************************
* UTILITAIRES DE scan1_2 *
*************************/

/****************************************************
**    nbr_conincol() : retourne le nombre des      **
** connecteurs existants dans la colonne donnee en **
** second argument.                                **
****************************************************/
 long  nbr_conincol(ptcheadcon,ptccol)
 chain_list *ptcheadcon;
 chain_list *ptccol;
 {

 long nbr=0;

 for (;ptcheadcon;ptcheadcon=ptcheadcon->NEXT)
     if (ptcheadcon->DATA)
        if (((CONNECTOR *)ptcheadcon->DATA)->COL==ptccol)
           nbr++;

 return nbr ;
 }

/****************************************************
**    nbr_coninlin() : retourne le nombre des      **
** connecteurs d'un signal existant dans la ligne  **
** donnee en second argument.                      **
****************************************************/
 long  nbr_coninlin(ptcheadcon,ptclin)
 chain_list *ptcheadcon;
 chain_list *ptclin;

 {
 long       nbrcon=0;
 CONNECTOR *ptcon=NULL;

 for (;ptcheadcon;ptcheadcon=ptcheadcon->NEXT)
     {
     ptcon = (CONNECTOR *)ptcheadcon->DATA;
     if (ptcon->LIN==ptclin)
        nbrcon++;
     }

 return nbrcon;
 }

/***************************************************
** decroche() :renvoie TRUE si un signal  admet   **
** un connecteur unique dans la ligne             **
***************************************************/
 int         decroche(ptsig,ptclin)
 SIGNAL     *ptsig;
 chain_list *ptclin;
 
 {
 long nbrcon=0l;

 if (ptsig->WIDTH==0)
    return TRUE;
 if (ptsig->HEIGHT!=0)
    { 
    nbrcon = nbr_coninlin(ptsig->CON,ptclin);
    if (nbrcon==1)
       {
       return TRUE;
       }
    else
       return FALSE;
    }
 else
    return FALSE;
 }

/**************************************************************
* scan1_2                                                     *
*  Second parcours sur la grille symbolique; recherche        *
*  des connecteurs libres qui n'ont pas d'autre connecteurs   *
*  de meme signal dans la grille (donc qui devrons decrocher) *
*  on tiendra compte des informations sur la ligne MIN et MAX *
*  du signal                                                  *
**************************************************************/
 void scan1_2(noeud,noeud_d,acces_d)
 NODE *noeud;
 NODE **noeud_d;
 ACCESS **acces_d;

 {
 NODE *noeud1=NULL, *noeud2=NULL, *noeud3=NULL;
 ACCESS *acces1=NULL, *acces2=NULL, *acces3=NULL;
 SIGNAL *sig1, *sig2;
 chain_list *ptccon;
 LINE       *ptlin;
 CONNECTOR  *ptcon;


 /* Parcours de bas en haut */
 for (noeud1=noeud; noeud1 ; noeud1=noeud1->DPR_UP)
     {
     /* Parcours de gauche a droite */
     for (noeud2=noeud1; noeud2; noeud2=noeud2->NEXT)
         {
         free_dwn(noeud2,acces_d);
         if ((*acces_d)&&(decroche((SIGNAL *)(*acces_d)->POS->CON->SIG->DATA,(*acces_d)->POS->CON->COL)))
            {
            ptlin=(LINE *)(*acces_d)->POS->CON->LIN->DATA;
            sig1=(SIGNAL *)(*acces_d)->POS->CON->SIG->DATA;
            if (sig1->WIDTH==0)
               {
               for (ptccon=sig1->CON;ptccon;ptccon=ptccon->NEXT)
                   {
                   ptcon=(CONNECTOR *)ptccon->DATA;
                   if ((ptcon->TYPE=='E')&&(((LINE *)ptcon->LIN->DATA)->INDEX==ptlin->INDEX-1))
                      {
                      *noeud_d=noeud2;
                      /*printf("Pour le signal %s, je durcis vers le bas\n",sig1->NAME);*/
                      return;
                      }
                   }
               }
            }
         free_up(noeud2,acces_d);
         if ((*acces_d)&&(decroche((SIGNAL *)(*acces_d)->POS->CON->SIG->DATA,(*acces_d)->POS->CON->COL)))
            {
            ptlin=(LINE *)(*acces_d)->POS->CON->LIN->DATA;
            sig1=(SIGNAL *)(*acces_d)->POS->CON->SIG->DATA;
            if (sig1->WIDTH==0)
               {
               for (ptccon=sig1->CON;ptccon;ptccon=ptccon->NEXT)
                   {
                   ptcon=(CONNECTOR *)ptccon->DATA;
                   if ((ptcon->TYPE=='E')&&(((LINE *)ptcon->LIN->DATA)->INDEX==ptlin->INDEX+1))
                      {
                      *noeud_d=noeud2;
                      /*printf("Pour le signal %s, je durcis vers le haut\n",sig1->NAME);*/
                      return;
                      }
                   }
               }
            }
         }
     }
 /* initialisation du resultat a FALSE */
 *noeud_d=NULL;
 *acces_d=NULL;
 }


/***************************
* UTILITAIRES DE scan1_3   *
***************************/

/*********************************************************
* unique                                                 *
*  Fonction booleenne permettant de detecter si une      *
*  possibilite d'acces (et pas un connecteur dur)        *
*  est devenu l'unique possibilite pour un connecteur    *
*  Ceci pour l'un ET pour l'autre acces(UP/DWN)          *
*********************************************************/
 int unique(noeud,acces)
 NODE *noeud;
 ACCESS *acces;
 {
 NODE *noeud1=NULL,*noeud2=NULL;
 ACCESS *acces1=NULL,*acces2=NULL;
 CONNECTOR *con1=NULL;
 
 /* verifications de la coherence de l'appel */
 if (acces==NULL) return(FALSE);
 if (acces->POS==NULL) return(FALSE);
 if (noeud==NULL) return(FALSE);
 for (acces1=noeud->DPR_RIGHT;acces1;acces1=acces1->PREV)
     if (acces1==acces)break;
 if (acces1==NULL) return(FALSE);

 /* verification sur le type de connecteur */
 /*if (acces->POS->CON->TYPE=='E') return FALSE;*/
 
 /* recherche sur les noeuds lateraux */ 
 con1=acces->POS->CON;
 if (noeud->DPR_DWN)
    for (noeud1=noeud;noeud1->DPR_DWN;noeud1=noeud1->DPR_DWN);
 else noeud1=noeud;
 for (;noeud1;noeud1=noeud1->NEXT)
     {
     if ((noeud1!=noeud)&&(noeud1->DPR_RIGHT!=NULL))
        {
        for (acces1=noeud1->DPR_RIGHT;acces1;acces1=acces1->PREV)
            {
            if((acces1->POS)&& (acces1->POS->CON==con1)) return(FALSE);
            }
        }
     }

 /*Le connecteur n'existe sur aucune autre piste latterale */
 /*on cherche a savoir s'il est unique sur sa piste        */

 for (acces1=noeud->DPR_RIGHT;acces1;acces1=acces1->PREV)
     if ((acces1->POS)&&(acces1->POS->CON==con1)&&(acces1!=acces)) 
        return(FALSE);
 
 return(TRUE);
 }

/*********************************************************
* scan1_3                                                *
*  troisieme parcours de la grille symbolique; recherche *
*  des acces uniques (donc aussi de tous les connecteurs *
*  durs uniques).                                        *
*********************************************************/
 void scan1_3(noeud,node_r,acces_r)
 NODE *noeud;
 NODE **node_r;
 ACCESS **acces_r;

 {
 NODE *noeud1=NULL, *noeud2=NULL, *noeud3=NULL;
 ACCESS *acces1=NULL, *acces2=NULL, *acces3=NULL;

 /* initialisation du resultat a FALSE */
 *node_r=NULL;
 *acces_r=NULL;

 /* Parcours de bas en haut */
 for (noeud1=noeud; noeud1 ; noeud1=noeud1->DPR_UP)
     {
     /* Parcours de gauche a droite */
     for (noeud2=noeud1; noeud2; noeud2=noeud2->NEXT)
         {
         if (noeud2->DPR_RIGHT)
            /* parcours des acces de haut en bas */
            for (acces1=noeud2->DPR_RIGHT;acces1;acces1=acces1->PREV)
                {
                if (unique(noeud2,acces1))
                   {
                   /* GAGNE! */
                   *acces_r=acces1;
                   *node_r=noeud2;
                   }
                if (*acces_r) break;
                }
         if (*acces_r) break;
         }
     if (*acces_r) break;
     }
 }

/***************************************************
* heuristique_1                                    *
*  recherches de plus haute priorite  durant le    *
*  routage global.                                 *
***************************************************/
 void heuristique_1 (ptclin_head,noeud)
 chain_list *ptclin_head;
 NODE *noeud;

 {
 NODE *node_r=NULL,*node_l=NULL;
 ACCESS *acces_r=NULL,*acces_l=NULL;
 int non_fin=TRUE;
 chain_list *ptccol_c=NULL;
 LINE *ptcol_c=NULL,*ptcol_o;
 long x=0,index=0; 

# ifdef DEBUG_ROUTER
    /*if (DEBUG_ROUTER) printf("Entree heuristique1,nb total d'acces non traite %ld\n"
                             ,total_acc);*/
# endif

 while (non_fin)
       {
       while (non_fin)
             {
             while (non_fin)
                   {
                   non_fin=FALSE;
                   /* recherche de deux connecteurs libres et en vis a vis */

# ifdef DEBUG_ROUTER
    /*if (DEBUG_ROUTER) printf("h1 pre_scan1_1,nb total d'acces non traite %ld\n"
                             ,total_acc);*/
# endif

                   scan1_1(noeud->DPR_UP,&node_r,&acces_r,&node_l,&acces_l);
                   if (node_l)
                      {
                      ptccol_c=acces_l->POS->CON->LIN->NEXT;
                      durcir(ptclin_head,acces_l);
                      liber_noeud(node_l,acces_l,ptclin_head);

                      ptcol_c=(LINE*)ptccol_c->DATA;
                      x = acces_r->POS->X;
                      index = ((SIGNAL *)acces_r->POS->CON->SIG->DATA)->INDEX;
                      for (node_l=node_l->DPR_UP;node_l!=node_r;node_l=node_l->DPR_UP)
                          {
                          /* gestion du resultat physique */
                          ptcol_o=(LINE *)ptccol_c->NEXT->DATA;
                          insertseg(ptcol_o,x,0,ptcol_o->WIDTH,ALU2,2,NULL);
                          (void *)insertcon_inchan((CHANNEL *)ptcol_c->CON->DATA,SOUTH,index,x);
                          ptccol_c=ptccol_c->NEXT->NEXT;
                          ptcol_c=(LINE*)ptccol_c->DATA;
                          (void *)insertcon_inchan((CHANNEL *)ptcol_c->CON->DATA,NORTH,index,x); 
                          /* modification de la grille symbolique */
                          put_obstacle(node_l);
                          }
                      durcir(ptclin_head,acces_r);
                      liber_noeud(node_r,acces_r,ptclin_head);
                      non_fin=TRUE;
                      }

#ifdef DEBUG_ROUTER
   /*if (DEBUG_ROUTER) printf("h1 post_scan1_1,nb total d'acces non traite %ld\n"
                            ,total_acc);*/
#endif

                   }

# ifdef DEBUG_ROUTER
    /*if (DEBUG_ROUTER) printf("h1 pre_scan1_2,nb total d'acces non traite %ld\n"
                             ,total_acc);*/
# endif

             /* recherche d'un connecteur libre de haut nulle qui decroche vers ext*/
             scan1_2(noeud,&node_r,&acces_r);
             if (node_r)
                {
                durcir(ptclin_head,acces_r);
                liber_noeud(node_r,acces_r,ptclin_head);
                non_fin=TRUE;
                }

# ifdef DEBUG_ROUTER
    /*if (DEBUG_ROUTER) printf("h1 post_scan1_2,nb total d'acces non traite %ld\n"
                             ,total_acc);*/
# endif

             }

# ifdef DEBUG_ROUTER
    /*if (DEBUG_ROUTER) printf("h1 pre_scan1_3,nb total d'acces non traite %ld\n"
                             ,total_acc);*/
# endif

      /* recherche d'un connecteur unique*/
      scan1_3(noeud,&node_r,&acces_r);
      if (node_r)
         {
         durcir(ptclin_head,acces_r);
         /* sauvegarde des valeurs ORIENT et POS */
         acces_r->LAST_POS=acces_r->POS;
         acces_r->LAST_ORIENT=acces_r->ORIENT;
         liber_noeud(node_r,acces_r,ptclin_head);
         non_fin=TRUE;
         }

# ifdef DEBUG_ROUTER
    /*if (DEBUG_ROUTER) printf("h1 post_scan1_3,nb total d'acces non traite %ld\n"
                             ,total_acc);*/
# endif

      }

# ifdef DEBUG_ROUTER
    /*if (DEBUG_ROUTER) printf("Sortie heuristique1,nb total d'acces non traite %ld\n"
                             ,total_acc);*/
# endif

 }
/*********************************************************************************
*                      Fichier: heurist2.c                                       *
*       version : 2.2                                                            *
*       date    : 24/09/91                                                       *
*********************************************************************************/
/****************************************************
* HEURISTIQUE DE ROUTAGE GLOBAL NO 2                *
*  recherche du vis a vis de cout minimum           *
****************************************************/
/****************************************************
* donne l'etat du noeud                             *
****************************************************/
 ACCESS *node_state(ptnoeud,nbright,nbleft,nbobst)
 NODE   *ptnoeud;
 long   *nbright,*nbleft,*nbobst;
 
 {
 ACCESS  *ptacces=NULL;

 (*nbleft) = 0;
 (*nbright) = 0;
 (*nbobst)  = 0;
 if (ptnoeud)
    if (ptacces=ptnoeud->DPR_LEFT)
       {
       for (;ptacces;ptacces=ptacces->NEXT)
           if (ptacces->POS)
              if (ptacces->ORIENT==WEST)
                 (*nbleft) += 1;
              else 
                 (*nbright) += 1;
           else 
              (*nbobst) += 1;
       } 
    else
       return NULL;
 else
    return NULL;
 return ((*nbleft)?ptnoeud->DPR_LEFT:((*nbright)?ptnoeud->DPR_RIGHT:NULL));
 }

/*****************************************************
* scan2_1                                            *
*  premier (et unique) parcours pour l'heuristique 2 *
*  recherche du vis a vis de cout minimum            *
*****************************************************/
 void scan2_1(noeud,node_r,acces_r,node_l,acces_l,cout_final)
 NODE   *noeud;
 NODE   **node_r;
 ACCESS **acces_r;
 NODE   **node_l;
 ACCESS **acces_l;
 long   *cout_final;

 {
 NODE       *noeud1=NULL, *noeud2=NULL, *noeud3=NULL;
 ACCESS     *acces1=NULL, *acces2=NULL, *acces3=NULL;
 SIGNAL     *ptsig=NULL;
 long       nbright=0,nbleft=0,nbobst=0;
 long       cout=-1,cout_total=-1,cout_min=-1;

 /*initialisation des resultats a FALSE */
 (*node_r)=NULL;
 (*acces_r)=NULL;
 (*node_l)=NULL;
 (*acces_l)=NULL;

 /* Parcours de gauche a droite */
 for (noeud1=noeud;noeud1->NEXT;noeud1=noeud1->NEXT)
     {
     /* Parcours de bas en haut */
     for (noeud2=noeud1;noeud2;noeud2=noeud2->DPR_UP)
         {
         for (acces1=noeud2->DPR_RIGHT;acces1;acces1=acces1->PREV)
             {
             if ((acces1->ORIENT==EAST)&&(!inhibuniq(noeud2,acces1)))
                {
                /* On a trouve un acces par la droite quandidat */
                ptsig=acces1->SIG;
                (void) existence(noeud2,ptsig,EAST,&cout);
                cout_total=cout; /* cout de connection WEST */
                /* Parcours de droite (juste avant) a gauche */
                for (noeud3=noeud2->NEXT;noeud3;noeud3=noeud3->NEXT)
                    {
                    /* On passe toutes les transparences */
                    if (acces2=existence(noeud3,ptsig,WEST,&cout))
                       {
                       if (!inhibuniq(noeud3,acces2))
                          {
                          /* On a detecte une extremite adequate */
                          cout_total+=cout; /* +cout de sortie EAST */
                          break;
                          }
                       else /* c.a.d unique possibilite */
                          {
                          acces2 = NULL;
                          break;
                          }
                       }
                    if (!test_allow(noeud3,ptsig))
                       break; /* On bloque:echec */
                    /* On force la transparence */
                    (void) node_state(noeud3,&nbright,&nbleft,&nbobst);
                    cout_total += (nbright + nbleft); /* cout de passage */
                    }
                if (noeud3&&acces2) /* c.a.d on a trouve un vis a vis */
                   {
                   /* le vis a vis en cours est-il de cout min. */
                   if ((cout_min==-1)||(cout_total<cout_min))
                      {
                      (*node_r)=noeud3;
                      (*acces_r)=acces2;
                      (*node_l)=noeud2;
                      (*acces_l)=acces1;
                      cout_min=cout_total;
                      *cout_final=cout_min;
                      if (cout_min==0) /* on ne peut pas faire mieux */
                         break;
                      }
                   }
                }
             }
         if (cout_min==0) /* on ne peut pas faire mieux */
            break;
         }
     if (cout_min==0) /* on ne peut pas faire mieux */
        break;
     }
 }

/*****************************************************
* scan2o_1                                           *
*  premier (et unique) parcours pour l'heuristique 2o*
*  recherche du vis a vis                            *
*****************************************************/
 void scan2o_1(noeud,node_r,acces_r,node_l,acces_l,cout_final)
 NODE   *noeud;
 NODE   **node_r;
 ACCESS **acces_r;
 NODE   **node_l;
 ACCESS **acces_l;
 long   *cout_final;

 {
 NODE       *noeud1=NULL, *noeud2=NULL, *noeud3=NULL;
 ACCESS     *acces1=NULL, *acces2=NULL, *acces3=NULL;
 SIGNAL     *ptsig=NULL;
 long       nbright=0,nbleft=0,nbobst=0;
 long       cout=-1,cout_total=-1,cout_min=-1;

 /*initialisation des resultats a FALSE */
 (*node_r)=NULL;
 (*acces_r)=NULL;
 (*node_l)=NULL;
 (*acces_l)=NULL;

 /* Parcours de gauche a droite */
 for (noeud1=noeud;noeud1->NEXT;noeud1=noeud1->NEXT)
     {
     /* Parcours de bas en haut */
     for (noeud2=noeud1;noeud2;noeud2=noeud2->DPR_UP)
         {
         for (acces1=noeud2->DPR_LEFT;acces1;acces1=acces1->NEXT)
             {
             if ((acces1->ORIENT==EAST)&&(!inhibuniq(noeud2,acces1)))
                {
                /* On a trouve un acces par la droite quandidat */
                ptsig=acces1->SIG;
                (void) existence(noeud2,ptsig,EAST,&cout);
                cout_total=cout; /* cout de connection WEST */
                for (noeud3=noeud2->NEXT;noeud3;noeud3=noeud3->NEXT)
                    {
                    /* On passe toutes les transparences */
                    if (acces2=existence(noeud3,ptsig,WEST,&cout))
                       {
                       if (!inhibuniq(noeud3,acces2))
                          {
                          /* On a detecte une extremite adequate */
                          cout_total+=cout; /* +cout de sortie EAST */
                          break;
                          }
                       else /* c.a.d unique possibilite */
                          {
                          acces2 = NULL;
                          break;
                          }
                       }
                    if (!test_allow(noeud3,ptsig))
                       break; /* On bloque:echec */
                    /* On force la transparence */
                    (void) node_state(noeud3,&nbright,&nbleft,&nbobst);
                    cout_total += (nbright + nbleft); /* cout de passage */
                    }
                if (noeud3&&acces2) /* c.a.d on a trouve un vis a vis */
                   {
                   (*node_r)=noeud3;
                   (*acces_r)=acces2;
                   (*node_l)=noeud2;
                   (*acces_l)=acces1;
                   cout_min=cout_total;
                   *cout_final=cout_min;
                   return;
                   }
                }
             }
         }
     }
 }

/**********************************************************
* sig_crosscol                                            *
* cherche si un signal traverse une colonne OPERATOR      *
* pour cela cherche si signal existe dans canal a gauche: *
* cote EAST et dans canal a droite: cote WEST             *
**********************************************************/
 int sig_crosscol(ptccoll_c,index)
 chain_list *ptccoll_c;
 long        index;

 {
 COLUMN   *ptcoll_c=NULL;
 COLUMN   *ptcolr_c=NULL;
 CHANNEL  *ptchanl=NULL;
 CHANNEL  *ptchanr=NULL;
 ConnectorList *ptcon=NULL;

 ptcoll_c = (COLUMN *)ptccoll_c->DATA;
 ptcolr_c = (COLUMN *)ptccoll_c->NEXT->NEXT->DATA;
 ptchanl = (CHANNEL *)ptcoll_c->DF_CON->DATA;
 ptchanr = (CHANNEL *)ptcolr_c->DF_CON->DATA;
 
 /* canal a gauche cote EAST */
 for (ptcon=ptchanl->EASTCON;ptcon;ptcon=ptcon->NextCon)
     {
     if (ptcon->ConName==index)
        break;
     }
 if (!ptcon)
    return FALSE;
 
 /* canal a droite cote WEST */
 for (ptcon=ptchanl->WESTCON;ptcon;ptcon=ptcon->NextCon)
     {
     if (ptcon->ConName==index)
        break;
     }
 if (!ptcon)
    return FALSE;
 else
    return TRUE;
 }

/**********************************************************
* heuristique_2                                           *
*  recherche du vis a vis de cout minimum                 *
**********************************************************/
 int heuristique_2(ptccol_head,ptnoeud_head)
 chain_list *ptccol_head;
 NODE      *ptnoeud_head; 

 {
 NODE       *node_r=NULL;
 ACCESS     *acces_r=NULL;
 NODE       *node_l=NULL;
 ACCESS     *acces_l=NULL;
 long        cout=0;
 chain_list *ptccol_c=NULL;
 COLUMN     *ptcol_c=NULL;
 COLUMN     *ptcol_o=NULL;
 long        y=0,index=0;
 int         traverse=FALSE;

 scan2_1(ptnoeud_head,&node_r,&acces_r,&node_l,&acces_l,&cout);
 if (acces_l)
    {
    ptccol_c = acces_l->POS->CON->COL->NEXT;
    ptcol_c = (COLUMN *)ptccol_c->DATA;
    liber_noeud(node_l,acces_l,ptccol_head);

    /* gestion des durcissements intermediaires */
    y = acces_r->POS->Y;
    index = acces_r->SIG->INDEX;
    for (node_l=node_l->NEXT;node_l!=node_r;node_l=node_l->NEXT)
        {
        ptcol_o = (COLUMN *)ptccol_c->NEXT->DATA;
        traverse = sig_crosscol(ptccol_c,index);
        if (!traverse)
           {
           insertseg(ptcol_o,0,y,ptcol_o->WIDTH,y,ALU2,WLAYER2,acces_r->SIG->NAME);
           (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,WEST,index,y);
           }
        ptccol_c = ptccol_c->NEXT->NEXT;
        ptcol_c = (COLUMN *)ptccol_c->DATA;
        if (!traverse)
           {
           (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,EAST,index,y);
           /* modification de la grille symbolique */
           put_obstacle(node_l);
           }
        }

    liber_noeud(node_r,acces_r,ptccol_head);
    return (TRUE);
    }
 return (FALSE);
 }

/**********************************************************
* heuristique_2o                                          *
*  recherche du vis a vis                                 *
**********************************************************/
 int heuristique_2o(ptccol_head,ptnoeud_head)
 chain_list *ptccol_head;
 NODE      *ptnoeud_head; 

 {
 NODE       *node_r=NULL;
 ACCESS     *acces_r=NULL;
 NODE       *node_l=NULL;
 ACCESS     *acces_l=NULL;
 long        cout=0;
 chain_list *ptccol_c=NULL;
 COLUMN     *ptcol_c=NULL;
 COLUMN     *ptcol_o=NULL;
 long        y=0,index=0;
 int         traverse=FALSE;

 scan2o_1(ptnoeud_head,&node_r,&acces_r,&node_l,&acces_l,&cout);
 if (acces_l)
    {
    ptccol_c = acces_l->POS->CON->COL->NEXT;
    ptcol_c = (COLUMN *)ptccol_c->DATA;
    liber_noeud(node_l,acces_l,ptccol_head);

    /* gestion des durcissements intermediaires */
    y = acces_r->POS->Y;
    index = acces_r->SIG->INDEX;
    for (node_l=node_l->NEXT;node_l!=node_r;node_l=node_l->NEXT)
        {
        ptcol_o = (COLUMN *)ptccol_c->NEXT->DATA;
        traverse = sig_crosscol(ptccol_c,index);
        if (!traverse)
           {
           insertseg(ptcol_o,0,y,ptcol_o->WIDTH,y,ALU2,WLAYER2,acces_r->SIG->NAME);
           (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,WEST,index,y);
           }
        ptccol_c = ptccol_c->NEXT->NEXT;
        ptcol_c = (COLUMN *)ptccol_c->DATA;
        if (!traverse)
           {
           (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,EAST,index,y);
           /* modification de la grille symbolique */
           put_obstacle(node_l);
           }
        }

    liber_noeud(node_r,acces_r,ptccol_head);
    return (TRUE);
    }
 return (FALSE);
 }

/*********************************************************************************
*                      Fichier: heurist3.c                                       *
*       version : 2.2                                                            *
*       date    : 24/09/91                                                       *
*********************************************************************************/

/****************************************************
* scan3_1                                           *
*  Parcours de  la grille symbolique; recherche du  *
*  connecteur 'qui decroche' dont l'acces est de    *
*  cout minimum.                                    *
****************************************************/
 long    scan3_1(noeud,node,acces)
 NODE   *noeud;
 NODE   **node;
 ACCESS **acces;

 {
 NODE *noeud1=NULL, *noeud2=NULL, *noeud3=NULL;
 ACCESS *acces1=NULL, *acces2=NULL, *acces3=NULL;
 chain_list *ptcsig,*ptccon;
 long cout_min=-1,cout_east=0,cout_west=0;
 COLUMN  *ptcol;
 CONNECTOR *ptcon;
 SIGNAL *ptsig;

 /* initialisation du resultat a FALSE */
 *node = NULL;
 *acces = NULL;

 /* Parcours de gauche a droite */
 for (noeud1=noeud->NEXT;noeud1->NEXT;noeud1=noeud1->NEXT)
     {
     /* Parcours de bas en haut */
     for (noeud2=noeud1;noeud2;noeud2=noeud2->DPR_UP)
         {
         /* Parcours des acces du noeud */
         for (acces1=noeud2->DPR_LEFT;acces1;acces1=acces1->NEXT)
             {
             /* recherche d'un acces pour un connecteur qui decroche */
             if ((acces1->POS)&&(decroche(acces1->SIG,acces1->POS->CON->LIN))
                              &&(!inhibuniq(noeud2,acces1)))
                {
                ptsig = acces1->SIG;
                if (ptsig->WIDTH==0)
                   {
                   ptcol = (COLUMN *)acces1->POS->CON->COL->DATA;
                   acces2 = existence(noeud2,ptsig,WEST,&cout_west);
                   if (acces2)
                      {
                      for (ptccon=ptsig->CON;ptccon;ptccon=ptccon->NEXT)
                          {
                          ptcon = (CONNECTOR *)ptccon->DATA;
                          if ((ptcon->TYPE=='E')&&
                              (((COLUMN *)ptcon->COL->DATA)->INDEX==ptcol->INDEX-1))
                             {
                             if ((cout_west<cout_min)||(cout_min==-1))
                                {
                                cout_min = cout_west;
                                *node = noeud2;
                                *acces = acces2;
                                if (cout_min==0)
                                   break;
                                }
                             break;
                             }
                          }
                      }
                   acces2 = existence(noeud2,ptsig,EAST,&cout_east);
                   if (acces2)
                      {
                      for (ptccon=ptsig->CON;ptccon;ptccon=ptccon->NEXT)
                          {
                          ptcon = (CONNECTOR *)ptccon->DATA;
                          if ((ptcon->TYPE=='E')&&
                              (((COLUMN *)ptcon->COL->DATA)->INDEX==ptcol->INDEX+1))
                             {
                             if ((cout_east<cout_min)||(cout_min==-1))
                                {
                                cout_min = cout_east;
                                *node = noeud2;
                                *acces = acces2;
                                if (cout_min==0)
                                   break;
                                }
                             break;
                             }
                          }
                      }
                   }
                }
             if (cout_min==0)
                break;
             }
         if (cout_min==0)
            break;
         }
     if (cout_min==0)
        break;
     }
 return(cout_min);
 }

/***************************************************
* heuristique3                                     *
*  recherche du connecteur qui decroche de cout    *
*  minimum sur toute la grille symbolique.         *
***************************************************/
 int heuristique_3(ptccol_head,ptnoeud_head)
 chain_list *ptccol_head;
 NODE       *ptnoeud_head;
 
 {
 NODE   *node;
 ACCESS *acces;

 (void)scan3_1(ptnoeud_head,&node,&acces);
 if (acces)
    {
    liber_noeud(node,acces,ptccol_head);
    return(TRUE);
    }

 return(FALSE);
 }

/************************************************************
* info                                                      
*  utilitaire de DEBUG.                                                      
************************************************************/
 void info(ptcsig,node_l,pos_dwn,node_r,pos_up)
 chain_list   *ptcsig;
 NODE        *node_l;
 POSSIBILITY  *pos_dwn;
 NODE        *node_r;
 POSSIBILITY  *pos_up;
 {

#ifdef DEBUG_DIFF
  printf("On assure la continuite du SIGNAL %s,\n",((SIGNAL*)ptcsig->DATA)->NAME);
  printf("  entre la possibilite X=%ld en ligne %s,\n"
         ,pos_dwn->X
         ,((COLUMN *)pos_dwn->CON->COL->DATA)->NAME);
  printf("     et la possibilite X=%ld en ligne %s.\n"
         ,pos_up->X
         ,((COLUMN *)pos_up->CON->COL->DATA)->NAME);
#endif
  return;
 }
 
 
/************************************************************
* scan_ref                                                  *   
*  optimise l'acces RIGHT suivant la derniere transparence  *
************************************************************/
 NODE *scan_ref(ptnoeud,ptsig,ptacces)
 NODE      *ptnoeud;
 SIGNAL    *ptsig;
 ACCESS   **ptacces;
 
 {
 NODE *ptnoeud_up=NULL;
 NODE *ptnoeud_dwn=NULL;
 char   orient;
  
 /*printf("go in SCAN_REF\n");*/
 orient = (*ptacces)->ORIENT;
 ptnoeud_dwn = ptnoeud;
 ptnoeud_up = ptnoeud;
 while (ptnoeud_up||ptnoeud_dwn)
       {
       if (ptnoeud_dwn)
          {
          for ((*ptacces)=ptnoeud_dwn->DPR_LEFT;*ptacces;(*ptacces)=(*ptacces)->NEXT)
              {
              if (((*ptacces)->POS)&&((*ptacces)->SIG==ptsig))
                 if (((*ptacces)->ORIENT==orient)&&(!inhibuniq(ptnoeud_dwn,(*ptacces))))
                    return ptnoeud_dwn;
              }
          ptnoeud_dwn = ptnoeud_dwn->DPR_DWN; 
          }
       if (ptnoeud_up)
          {
          for ((*ptacces)=ptnoeud_up->DPR_LEFT;*ptacces;(*ptacces)=(*ptacces)->NEXT)
              {
              if (((*ptacces)->POS)&&((*ptacces)->SIG==ptsig))
                 if (((*ptacces)->ORIENT==orient)&&(!inhibuniq(ptnoeud_up,(*ptacces))))
                    return ptnoeud_up;
              }
          ptnoeud_up = ptnoeud_up->DPR_UP;
          }
       }
 return NULL;
 }

/************************************************************
* scan_allow                                                *
************************************************************/
 NODE       *scan_allow(ptnoeud,ptsig)
 NODE       *ptnoeud;
 chain_list *ptsig;
 
 {
 NODE *ptnoeud_up=NULL;
 NODE *ptnoeud_dwn=NULL;
  
 if (test_allow(ptnoeud,ptsig))
    return ptnoeud;
 ptnoeud_up = ptnoeud->DPR_UP;
 ptnoeud_dwn = ptnoeud->DPR_DWN;
 while (ptnoeud_up||ptnoeud_dwn)
       {
       if (ptnoeud_dwn)
          {
          if (test_allow(ptnoeud_dwn,ptsig))
             return ptnoeud_dwn;
          ptnoeud_dwn = ptnoeud_dwn->DPR_DWN; 
          }
       if ((ptnoeud_up))
          {
          if (test_allow(ptnoeud_up,ptsig))
             return ptnoeud_up;
          ptnoeud_up = ptnoeud_up->DPR_UP;
          }
       }
 return NULL;
 } 
        
/************************************************************
* diff_allows                                               *
************************************************************/
 NODE        *diff_allows(ptnode_l,ptccol_l,ptpos_l,ptccol_r,ptsig,pttrack_head)
 NODE        *ptnode_l;
 chain_list  *ptccol_l;
 POSSIBILITY *ptpos_l;
 chain_list  *ptccol_r;
 SIGNAL      *ptsig;
 TRACK       *pttrack_head;
 
 {
 GABARIT      *ptgab=NULL;
 NODE         *ptnoeud1=NULL;
 chain_list   *ptccol=NULL;
 COLUMN       *ptcol_o=NULL;
 NODE         *ptnoeud2=NULL;
 chain_list   *ptccol_c=NULL;
 NODE         *ptnoeud_sav=NULL;
 COLUMN       *ptcol_c=NULL;
 TRACK        *pttrack=NULL;
 int           traverse=FALSE;
 

 ptgab = ((LINE *)ptpos_l->CON->LIN->DATA)->GAB;

 ptnoeud1 = ptnode_l;
 ptccol_c = ptccol_l->NEXT;
 for (ptccol=ptccol_l->NEXT->NEXT;ptccol!=ptccol_r;ptccol=ptccol->NEXT->NEXT)
     {
     ptcol_c = (COLUMN *)ptccol_c->DATA;
     ptcol_o = (COLUMN *)ptccol->DATA;
     ptnoeud1 = ptnoeud1->NEXT;
     traverse = sig_crosscol(ptccol_c,ptsig->INDEX);
     if (!traverse)
        {
        ptnoeud2 = scan_allow(ptnoeud1,ptsig);
        if (!ptnoeud2)
           {
           printf("Warning: Can not go through column %s for signal %s\n",
                   ptcol_o->NAME,ptsig->NAME);
           ptccol_c = ptccol_c->NEXT->NEXT;
           continue;
           }
        ptnoeud_sav = ptnoeud2;
        /* extraction de y en fonction du gabarit et de ptnoeud2 */
        if (!pttrack_head) /* c.a.d appel pour traiter un bit-slice */
           for (pttrack=ptgab->TRACK;ptnoeud2;pttrack=pttrack->NEXT,
                                              ptnoeud2=ptnoeud2->DPR_DWN);
        else /* c.a.d appel pour traiter la figure */
           for (pttrack=pttrack_head;ptnoeud2;pttrack=pttrack->NEXT,
                                              ptnoeud2=ptnoeud2->DPR_DWN);
        /* gestion du resultat physique */
        insertseg(ptcol_o,0,pttrack->Y,ptcol_o->WIDTH,pttrack->Y,ALU2,WLAYER2,
                  ptsig->NAME);
        (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,
                                 WEST,
                                 ((SIGNAL *)ptpos_l->CON->SIG->DATA)->INDEX,
                                 pttrack->Y);
        }
     ptccol_c = ptccol_c->NEXT->NEXT;
     ptcol_c = (COLUMN *)ptccol_c->DATA;
     if (!traverse)
        {
        (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,
                                 EAST,
                                 ((SIGNAL *)ptpos_l->CON->SIG->DATA)->INDEX,
                                 pttrack->Y);
        /* modification de la grille symbolique */
        put_obstacle(ptnoeud_sav);
        ptnoeud1 = ptnoeud_sav;
        }
     }
 return ptnoeud1;
 }

/************************************************************
* chercher_right                                            *
************************************************************/
 void chercher_right(ptsig,node,node_r,acces_r)
 SIGNAL  *ptsig;
 NODE    *node;
 NODE   **node_r;
 ACCESS **acces_r;

 {
 NODE   *ptnoeud1=NULL;
 NODE   *ptnoeud2=NULL;
 ACCESS   *acces1=NULL; 
 long    nbr_acces=0;

 if (node->DPR_DWN)
    for (ptnoeud1=node;ptnoeud1->DPR_DWN;ptnoeud1=ptnoeud1->DPR_DWN);
 else
    ptnoeud1=node;

 for (ptnoeud1=ptnoeud1;ptnoeud1;ptnoeud1=ptnoeud1->NEXT)
     {
     for (ptnoeud2=ptnoeud1;ptnoeud2;ptnoeud2=ptnoeud2->DPR_UP)
         {
         acces1 = existence(ptnoeud2,ptsig,WEST,&nbr_acces);
         if ((acces1)&&(!inhibuniq(ptnoeud2,acces1)))
            {
            (*acces_r) = acces1;
            (*node_r) = ptnoeud2;
            return;
            }
         }
     }
 (*acces_r) = NULL;
 (*node_r) = NULL;
 }

/************************************************************
* diff_line                                                 *
*  diffusion des signaux (recherche de la continuite) sur   *
*  un slice unique; a ce stade il n'y a plus de vis a vis:  *
*  entre une extremite gauche et une autre droite           *
************************************************************/
 void        diff_line(ptccol_head,ptnoeud_head)
 chain_list *ptccol_head;
 NODE       *ptnoeud_head;
 
 {
 NODE   *ptnoeud1=NULL;
 NODE   *ptnoeud2=NULL;
 ACCESS *acces1=NULL;
 NODE   *node_r=NULL;
 ACCESS *acces_r=NULL;
 NODE   *ptnoeud3=NULL;
 
 for (ptnoeud1=ptnoeud_head;ptnoeud1->NEXT;ptnoeud1=ptnoeud1->NEXT)
     {
     for (ptnoeud2=ptnoeud1;ptnoeud2;ptnoeud2=ptnoeud2->DPR_UP)
         {
         for (acces1=ptnoeud2->DPR_RIGHT;acces1;acces1=acces1->PREV)
             {
             /* recherche du noeud de gauche */
             if ((acces1->POS)&&(!inhibuniq(ptnoeud2,acces1)))
                {
                if (acces1->ORIENT==EAST)
                   {
                   /* recherche du noeud de droite */
                   chercher_right(acces1->SIG,ptnoeud2->NEXT,&node_r,&acces_r);
                   if (acces_r)
                      {
                      /* on a trouve une diffusion a faire */
                      ptnoeud3 = diff_allows(ptnoeud2,
                                             acces1->POS->CON->COL,
                                             acces1->POS,
                                             acces_r->POS->CON->COL,
                                             acces_r->SIG,NULL);
                      liber_noeud(ptnoeud2,acces1,ptccol_head);
                      /* optimisation de l'acces right */
                      if (ptnoeud3)
                         node_r = scan_ref(ptnoeud3->NEXT,acces_r->SIG,&acces_r);
                      liber_noeud(node_r,acces_r,ptccol_head);
                      }
                   } 
                }
             }
         }
     }
 }

/*********************************************************************************
*                      Fichier: diff_all.c                                       *
*       version : 2.2                                                            *
*       date    : 24/09/91                                                       *
*********************************************************************************/

 /* REMARQUE PRELIMINAIRE */
 /* On parlera de SIGNAL LARGE pour un signal present dans plus d'une colonne */
 /* Au cours des etapes precedentes:
   -Les connecteurs du pere flottants dans la face N/S sont places dans
    la colonne lors de la diffusion_W0 si le signal est de largeur 1.
   -Les autres connecteurs du pere flottants N/S associes a un signal 
    large ne sont pas encore pris en compte.
   -On a interdit d'attribuer des transparences a un signal large.
   -Au cours de l'etape de diffusion_W0 les connecteurs ont ete ducis
    vers le bas, sauf pour la ligne MIN et si un acces des deux cotes
    etait possible le lieu etait code comme une 'transparence' propre 
    au signal, dans la liste des transparences de la figure DPR.      
   -Au cours de l'etape de diffusion_W0 les signaux de largeur 1 qui 
    n'on pas trouve de transparence pour traverser une ligne sont 
    mis dans une liste d'attente.*/
 /* premiere etape */
 /* verification que tous les signaux larges et qui ne
    sont presents que dans deux lignes CELL consecutives
    sont continus */
 /* seconde etape */
 /* boucle sur les signaux restants */
 /* initialisation */ 
 /* recherche du connecteur le plus bas */
 /* placement eventuel d'un connecteur flottant en ligne DWN */
 /* recherche du connecteur le plus haut */
 /* placement eventuel d'un connecteur flottant en ligne UP */
 /* choix des transparences a attribuer */
 /* boucle de la ligne MIN a la ligne MAX */ 
 /* recherche d'une transparence propre au signal sur la ligne CELL */
 /* attribution eventuelle d'une vrai transparence, UNIQUE sur la ligne CELL */
 /* troisieme etape */
 /* recherche des transparences hors colonne pour les signaux de largeur 1 
    qui n'ont pas trouve de passage dans leur colonne */

/******************************************************
* acces_commun: recherche et renvoie l'acces commun   *
* des connecteurs d'un meme signal                    *
* utilisee pour des signaux de hauteur nulle          *
******************************************************/
 char acces_commun(ptsig)
 SIGNAL *ptsig;
 
 {
 chain_list  *ptccon=NULL;
 CONNECTOR   *ptcon=NULL;
 chain_list  *ptcpos1=NULL;
 POSSIBILITY *ptpos1=NULL;
 chain_list  *ptcpos2=NULL;
 POSSIBILITY *ptpos2=NULL;
 char         comacces='I';
 char         posacces='O';

 for (ptccon=ptsig->CON;ptccon;ptccon=ptccon->NEXT)
     {
     ptcon = (CONNECTOR *)ptccon->DATA;
     posacces = 'O';
     ptcpos1 = ptcon->POS;
     ptpos1 = (POSSIBILITY *)ptcpos1->DATA;
     if (ptpos1->ACCES=='H')
        posacces = 'H';
     else
        if (ptpos1->ACCES==EAST)
           {
           for (ptcpos2=ptcpos1->NEXT;ptcpos2;ptcpos2=ptcpos2->NEXT)
               {
               ptpos2 = (POSSIBILITY *)ptcpos2->DATA;
               if ((ptpos2->ACCES=='H')||(ptpos2->ACCES==WEST))
                  {
                  posacces = 'H';
                  break;
                  }
               posacces = EAST;
               }
           }
        else /* c.a.d ptpos1->ACCES==WEST */
           {
           for (ptcpos2=ptcpos1->NEXT;ptcpos2;ptcpos2=ptcpos2->NEXT)
               {
               ptpos2 = (POSSIBILITY *)ptcpos2->DATA;
               if ((ptpos2->ACCES=='H')||(ptpos2->ACCES==EAST))
                  {
                  posacces = 'H';
                  break;
                  }
               posacces = WEST;
               }
           }

     if ((comacces=='H')||(comacces=='I'))
        {
        comacces = posacces;
        }
     else
        if (comacces==EAST)
           {
           if (posacces==WEST)
              {
              comacces = 'O';
              break;
              }
           else
              comacces = EAST;
           }
        else /* c.a.d comacces==WEST */
           {
           if (posacces==EAST)
              {
              comacces = 'O';
              break;
              }
           else
              comacces = WEST;
           }
     }
 return comacces;
 }

/******************************************************
* sig_inchan                                          *
* retourne TRUE si on trouve le signal dans le canal  *
* sinon FALSE                                         *
******************************************************/
 int sig_inchan(ptcol,ptsig)
 COLUMN *ptcol;
 SIGNAL *ptsig;
 {
 long index;
 CHANNEL *ptchannel=NULL;
 ConnectorList *ptcon_ch=NULL;

 index = ptsig->INDEX;
 ptchannel = (CHANNEL *)ptcol->DF_CON->DATA;

 for (ptcon_ch=ptchannel->NORTHCON;ptcon_ch;ptcon_ch=ptcon_ch->NextCon)
     if (ptcon_ch->ConName==index) return TRUE;
 
 for (ptcon_ch=ptchannel->SOUTHCON;ptcon_ch;ptcon_ch=ptcon_ch->NextCon)
     if (ptcon_ch->ConName==index) return TRUE;

 for (ptcon_ch=ptchannel->WESTCON;ptcon_ch;ptcon_ch=ptcon_ch->NextCon)
     if (ptcon_ch->ConName==index) return TRUE;
 
 for (ptcon_ch=ptchannel->EASTCON;ptcon_ch;ptcon_ch=ptcon_ch->NextCon)
     if (ptcon_ch->ConName==index) return TRUE;

 return FALSE;
 }

/******************************************************
* goto_chan                                           *
* ramene un signal jusqu'au premier canal de routage  *
* ou il existe                                        *
******************************************************/
 void        goto_chan(ptnoeud_deb,ptclin_deb,ptsig,pttrack_head)
 NODE       *ptnoeud_deb;
 chain_list *ptclin_deb;
 SIGNAL     *ptsig;
 TRACK      *pttrack_head;
 {
 chain_list *ptccol_c=NULL;
 COLUMN *ptcol_c=NULL;
 chain_list *ptccol_o=NULL;
 COLUMN *ptcol_o=NULL;
 NODE  *ptnoeud1=NULL;
 NODE  *ptnoeud2=NULL;
 NODE  *ptnoeud3=NULL;
 TRACK  *pttrack=NULL;

 ptnoeud1 = ptnoeud_deb->NEXT;
 for (ptccol_c=ptclin_deb->NEXT;ptccol_c->NEXT->NEXT;ptnoeud1=ptnoeud1->NEXT)
     {
     ptcol_c = (COLUMN *)ptccol_c->DATA;
     if (sig_inchan(ptcol_c,ptsig)) return;
     ptccol_o = ptccol_c->NEXT;
     ptcol_o = (COLUMN *)ptccol_o->DATA;
     if (!(ptnoeud2 = scan_allow(ptnoeud1,ptsig)))
        {
        Warning(2,"Can not route through column:\n",ptcol_o->NAME);
        ptccol_c = ptccol_c->NEXT->NEXT;
        continue;
        }
     put_obstacle(ptnoeud2);
     ptnoeud3 = ptnoeud2;
     /* extraction de l'ordonne du segment */
     for (pttrack=pttrack_head;ptnoeud2;pttrack=pttrack->NEXT,
          ptnoeud2=ptnoeud2->DPR_DWN);

     insertseg(ptcol_o,0,pttrack->Y,ptcol_o->WIDTH,pttrack->Y,ALU2,WTRAN,
               ptsig->NAME);
     (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,WEST,
                              ptsig->INDEX,pttrack->Y);
     ptccol_c = ptccol_c->NEXT->NEXT;
     ptcol_c = (COLUMN *)ptccol_c->DATA;
     (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,EAST,
                              ptsig->INDEX,pttrack->Y);
     ptnoeud1 = ptnoeud3;
     }
 }

/******************************************************
* back_chan                                           *
* ramene un signal jusqu'au premier canal de routage  *
* ou il existe                                        *
******************************************************/
 void        back_chan(ptnoeud_deb,ptclin_deb,ptsig,pttrack_head,ptccol_head)
 NODE       *ptnoeud_deb;
 chain_list *ptclin_deb;
 SIGNAL     *ptsig;
 TRACK      *pttrack_head;
 chain_list *ptccol_head;

 {
 chain_list *ptccol_c=NULL;
 COLUMN *ptcol_c=NULL;
 chain_list *ptccol_o=NULL;
 COLUMN *ptcol_o=NULL;
 NODE  *ptnoeud1=NULL;
 NODE  *ptnoeud2=NULL;
 NODE  *ptnoeud3=NULL;
 TRACK  *pttrack=NULL;

 ptnoeud1 = ptnoeud_deb->PREV;
 for (ptccol_c=chain_pred(ptccol_head,ptclin_deb);ptccol_c;ptnoeud1=ptnoeud1->PREV)
     {
     ptcol_c = (COLUMN *)ptccol_c->DATA;
     if (sig_inchan(ptcol_c,ptsig)) return;
     ptccol_o = chain_pred(ptccol_head,ptccol_c);
     ptcol_o = (COLUMN *)ptccol_o->DATA;
     if (!(ptnoeud2 = scan_allow(ptnoeud1,ptsig)))
        {
        Warning(2,"Can not route through column:\n",ptcol_o->NAME);
        ptccol_c = chain_pred(ptccol_head,chain_pred(ptccol_head,ptccol_c));
        continue;
        }
     put_obstacle(ptnoeud2);
     ptnoeud3 = ptnoeud2;
     /* extraction de l'abscisse du segment */
     for (pttrack=pttrack_head;ptnoeud2;pttrack=pttrack->NEXT,
          ptnoeud2=ptnoeud2->DPR_DWN);

     insertseg(ptcol_o,0,pttrack->Y,ptcol_o->WIDTH,pttrack->Y,ALU2,WTRAN,
               ptsig->NAME);
     (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,EAST,
                              ptsig->INDEX,pttrack->Y);
     ptccol_c = chain_pred(ptccol_head,chain_pred(ptccol_head,ptccol_c));
     if (ptccol_c)
        {
        ptcol_c = (COLUMN *)ptccol_c->DATA;
        (void *)insertcon_inchan((CHANNEL *)ptcol_c->DF_CON->DATA,WEST,
                              ptsig->INDEX,pttrack->Y);
        }
     ptnoeud1 = ptnoeud3;
     }
 }

/******************************************************
* diff_all                                            *
* finition du routage pour tous les connecteurs       *
* restants en travaillant sur la grille symbolique    *
* du chemin de donnees en entier                      *
******************************************************/
 TRACK    *diff_all(ptfig_dpr)
 FIGURE   *ptfig_dpr;

 {
 chain_list   *ptccolpos=NULL;
 COLUMN       *ptcolpos=NULL;
 chain_list   *ptclin1=NULL;
 chain_list   *ptclin2=NULL;
 LINE         *ptlin1=NULL;
 LINE         *ptlin2=NULL;
 NODE         *noeud2=NULL;
 NODE         *noeud1=NULL;
 NODE         *ptnoeud=NULL;
 NODE         *noeud_fin=NULL;
 chain_list   *ptcsig=NULL;
 ACCESS       *acces=NULL;
 char          comacces;
 SIGNAL       *ptsig=NULL;
 NODE         *node_r=NULL;
 ACCESS       *acces_r=NULL;
 GABARIT      *ptgab1=NULL;
 GABARIT      *ptgab2=NULL;
 TRACK        *pttrack1=NULL;
 TRACK        *pttrack2=NULL;
 TRACK        *pttrack_head=NULL;
 TRACK        *pttrack_cour=NULL;
 long          cout=-1;
 ACCESS       *acces2=NULL;
 NODE         *noeud3=NULL;

 /* creation du chainage des gabarits des differentes lignes */
 ptlin1 = (LINE *)(ptfig_dpr->LIN)->DATA;
 ptgab1 = ptlin1->GAB;
 pttrack_head = addtrack(NULL,ptgab1->TRACK->Y);
 pttrack_cour = pttrack_head;
 for (ptclin1=ptfig_dpr->LIN;ptclin1;ptclin1=ptclin1->NEXT)
     {
     ptlin1 = (LINE *)ptclin1->DATA;
     ptgab1 = ptlin1->GAB;
     for (pttrack1=ptgab1->TRACK->NEXT;pttrack1;pttrack1=pttrack1->NEXT)
         {
         pttrack_cour->NEXT = addtrack(pttrack_cour->NEXT,pttrack1->Y);
         pttrack_cour = pttrack_cour->NEXT;
         }
     }

 /* chainage des grilles des differentes lignes */
 ptclin1 = ptfig_dpr->LIN;
 for (ptclin2=ptclin1->NEXT;ptclin2;ptclin1=ptclin2,ptclin2=ptclin2->NEXT)
     {
     ptlin1 = (LINE *)ptclin1->DATA;
     ptlin2 = (LINE *)ptclin2->DATA;
     for (noeud1=ptlin1->GRID;noeud1->DPR_UP;noeud1=noeud1->DPR_UP);
     for (noeud2=ptlin2->GRID;noeud1;noeud1=noeud1->NEXT,noeud2=noeud2->NEXT)
         {
         noeud1->DPR_UP = noeud2;
         noeud2->DPR_DWN = noeud1;
         }
     }

 /* si total_acc==0 retourner pttrack_head juste apres avoir effectue les */
 /* chainages, sans faire du routage sur la grille globale */
 if (total_acc==0)
    return pttrack_head;

 printf(" * Multi-bit net symbolic routing *\n");
 /* parcours de la grille totale pour diffuser les signaux restants */
 ptclin1 = ptfig_dpr->LIN;
 ptlin1 = (LINE *)ptclin1->DATA;
 ptnoeud = ptlin1->GRID;
 for (noeud1=ptnoeud;noeud1;noeud1=noeud1->NEXT)
     for (noeud2=noeud1;noeud2;noeud2=noeud2->DPR_UP)
         for (acces=noeud2->DPR_RIGHT;acces;acces=acces->PREV)
             if ((acces->POS)&&(!inhibuniq(noeud2,acces)))
                {
                ptsig = acces->SIG;
                ptccolpos = acces->POS->CON->COL;
                ptcolpos = (COLUMN *)ptccolpos->DATA;
                if (!ptsig->WIDTH)
                   {
                   if (ptsig->TYPE=='I')
                      {
                      /* traitement d'un signal interne de largeur nulle*/
                      comacces = acces_commun(ptsig);
                      if (comacces!='O')
                         {
                         if (noeud2->DPR_UP) /* pour commencer par le haut */
                            for (noeud3=noeud2;noeud3->DPR_UP;noeud3=noeud3->DPR_UP);
                         else
                            noeud3 = noeud2;
                         for (noeud3=noeud3;noeud3;noeud3=noeud3->DPR_DWN)
                             {
                             if (comacces=='H')
                                {
                                acces2 = existence(noeud3,ptsig,EAST,&cout);
                                }
                             else
                                if (comacces==WEST)
                                   {
                                   acces2 = existence(noeud3,ptsig,WEST,&cout);
                                   }
                                else /* c.a.d comacces==EAST */
                                   {
                                   acces2 = existence(noeud3,ptsig,EAST,&cout);
                                   }
                             if ((acces2)&&(!inhibuniq(noeud3,acces2)))
                                /* durcir le connecteur du signal */
                                liber_noeud(noeud3,acces2,ptfig_dpr->COL);
                             }
                         }
                      else /* c.a.d pas d'acces commun */
                         {
                         printf("WARNING: %s not routed (not expected case)!!\n",
                                ptsig->NAME);
                         /* cas non prevu pour l'instant */
                         }
                      }
                   else
                      {
                      printf("BIZZ: External signal %s (width=0) not routed yet!!\n",
                              ptsig->NAME);
                      /*exit(20);*/
                      }
                   }
                else
                   {
                   /* traitement d'un signal de largeur non nulle*/
                   if (acces->ORIENT==EAST)
                      {
                      /* recherche du noeud de droite */
                      chercher_right(ptsig,noeud2->NEXT,&node_r,&acces_r);
                      if (acces_r)
                         {
                         /* on a trouve une diffusion a faire */
                         noeud3 = diff_allows(noeud2,
                                              ptccolpos,
                                              acces->POS,
                                              acces_r->POS->CON->COL,
                                              acces_r->SIG,
                                              pttrack_head);
                         liber_noeud(noeud2,acces,ptfig_dpr->COL);
                         /* optimisation de l'acces right si necessaire */
                         if (noeud3)
                            node_r = scan_ref(noeud3->NEXT,acces_r->SIG,&acces_r);
                         liber_noeud(node_r,acces_r,ptfig_dpr->COL);
                         }
                      else /* c.a.d acces unique */
                         {
                         if (ptcolpos->INDEX<(ptsig->MIN_COL+ptsig->WIDTH))
                            /* c.a.d pas colonne MAX */
                            {
                            /* go jusqu'au premier canal et durcir l'acces gauche */
                            goto_chan(noeud2,ptccolpos,ptsig,pttrack_head);
                            liber_noeud(noeud2,acces,ptfig_dpr->COL);
                            }
                         }
                      }
                   else /* c.a.d acces->ORIENT==WEST */
                      {
                      if (ptcolpos->INDEX==ptsig->MIN_COL+ptsig->WIDTH)
                         /* c.a.d colonne MAX */
                         {
                         /* revenir jusqu'au canal et durcir l'acces droit*/
                         back_chan(noeud2,ptccolpos,ptsig,pttrack_head,
                                   ptfig_dpr->COL);
                         liber_noeud(noeud2,acces,ptfig_dpr->COL);
                         }
                      }
                   }
                }
 return pttrack_head;
 }
/***********************************************************************************
* channel_rout                                                                     *
*                                                                                  *
***********************************************************************************/
 void channel_rout(x)
 long *x;
 {
 *x = 0;
 }

/***********************************************************************************
*  insertacces                                                                     *
*   Recherche s'il faut inserer une nouvelle                                       *
*   possibilite d'acces dans une case de la grille                                 *
*   symbolique                                                                     *
***********************************************************************************/
 void  insertacces(noeud,ptcon,ptpos,orient)
 NODE        *noeud;
 CONNECTOR   *ptcon;
 POSSIBILITY *ptpos;
 char orient;

 { 
 ACCESS *acc1=NULL, *acc2=NULL, *acc3=NULL;
  
 if (!noeud->DPR_RIGHT)
    {
    /* Cas du premier acces d'un noeud */
    acc3 = mkacces(NULL,NULL,ptpos,orient,ptcon->SIG->DATA);
    noeud->DPR_LEFT = acc3;
    noeud->DPR_RIGHT = acc3;
    }
 else
    { 
    /* Il existe au moins un acces dans le noeud: parcours de gauche a droite */
    for (acc1=noeud->DPR_LEFT,acc2=acc1;acc1;acc2=acc1,acc1=acc1->NEXT)
        {
        if (ptpos->X < acc1->POS->X) /* position d'insertion detectee */
           break;
        }
    /* Insertions */
    if (acc2==acc1) 
       {
       /* Insertion en debut de liste */
       acc3 = mkacces(acc1,NULL,ptpos,orient,ptcon->SIG->DATA);
       acc1->PREV = acc3;
       noeud->DPR_LEFT = acc3;
       }
    else
       { 
       if (acc1==NULL)
          {
          /* Insertion en fin de liste */
          acc3 = mkacces(NULL,acc2,ptpos,orient,ptcon->SIG->DATA);
          acc2->NEXT = acc3;
          noeud->DPR_RIGHT = acc3;
          }
       else
          {
          /* Insertion en milieu de liste */
          acc3 = mkacces(acc1,acc2,ptpos,orient,ptcon->SIG->DATA);
          acc1->PREV = acc3;
          acc2->NEXT = acc3;
          }
       } 
    }
 } 

/***********************************************************************************
* put_in_grid
*  Traduit pour une abscisse X donnee, toutes
*  possibilites (eventuelles) d'un connecteur
*  en structures ACCESS de la grille symbolique
*  en vue du routage global
*  Insere la possibilite minimum et la possibilite
*  maximum (selon y) pour le X recherche
***********************************************************************************/
 void  put_in_grid(noeud,y,ptcon)
 NODE      *noeud;
 long       y;
 CONNECTOR *ptcon;
 
 {
 POSSIBILITY *ptpos=NULL;
 POSSIBILITY *ptpos_min=NULL;
 POSSIBILITY *ptpos_max=NULL;
 chain_list  *ptcpos=NULL;
 
 for (ptcpos=ptcon->POS;ptcpos;ptcpos=ptcpos->NEXT)
     {
     ptpos = (POSSIBILITY *)ptcpos->DATA;
     if (ptpos->Y == y)
        {
        if ((ptpos->ACCES==WEST)||(ptpos->ACCES=='H'))
           {
           if (ptcon->TYPE=='E')
              {
              if ((ptpos_max==NULL)||(ptpos->X>ptpos_max->X)) 
                 ptpos_max=ptpos;
              }
           else
              {
              if ((ptpos_min==NULL)||(ptpos->X<ptpos_min->X)) 
                 ptpos_min = ptpos;
              }
           }
        if ((ptpos->ACCES==EAST)||(ptpos->ACCES=='H'))
           {
           if (ptcon->TYPE=='E')
              {
              if ((ptpos_min==NULL)||(ptpos->X<ptpos_min->X)) 
                 ptpos_min = ptpos;
              }
           else
              {
              if ((ptpos_max==NULL)||(ptpos->X>ptpos_max->X)) 
                 ptpos_max=ptpos;
              }
           }
        }
     }
 if (ptpos_min)
    insertacces(noeud,ptcon,ptpos_min,WEST);
 if (ptpos_max)
    insertacces(noeud,ptcon,ptpos_max,EAST);
 }

/***********************************************************************************
* getccon
* 
***********************************************************************************/
 chain_list *getccon(ptcheadcon,ptccol,ptclin)
 chain_list *ptcheadcon;
 chain_list *ptccol;
 chain_list *ptclin;
 {
 CONNECTOR *ptcon;
  
 for (;ptcheadcon;ptcheadcon=ptcheadcon->NEXT)
     {
     ptcon = (CONNECTOR *)ptcheadcon->DATA;
     if ((ptcon->COL==ptccol)&&(ptcon->LIN==ptclin))
        return ptcheadcon;
     }
 return NULL;
 }

/***********************************************************************************
* addnoeud
*
***********************************************************************************/
 NODE *addnoeud(pthead,nbr)
 NODE *pthead;
 long   nbr;

 {
 NODE *ptnoeud;
 NODE *ptnoeud_aux;
  
 ptnoeud = (NODE *)mbkalloc(sizeof(NODE));
 ptnoeud->NEXT  = NULL;
 ptnoeud->PREV  = NULL;
 ptnoeud->DPR_UP    = NULL;
 ptnoeud->DPR_DWN   = NULL;
 ptnoeud->DPR_RIGHT = NULL;
 ptnoeud->DPR_LEFT  = NULL;
  
 ptnoeud_aux = ptnoeud;
  
 for (nbr=nbr-1;nbr!=0;nbr--)
     {
     ptnoeud_aux->DPR_UP = (NODE *)mbkalloc(sizeof(NODE));
     ptnoeud_aux->DPR_UP->DPR_DWN = ptnoeud_aux;
     ptnoeud_aux        = ptnoeud_aux->DPR_UP;
     ptnoeud_aux->DPR_UP    = NULL ;
     ptnoeud_aux->NEXT  = NULL ;
     ptnoeud_aux->PREV  = NULL ;
     ptnoeud_aux->DPR_RIGHT = NULL ;
     ptnoeud_aux->DPR_LEFT  = NULL ;
     }
  
 for (ptnoeud_aux=ptnoeud;pthead;pthead=pthead->DPR_UP,ptnoeud_aux=ptnoeud_aux->DPR_UP)
     {
     pthead->NEXT = ptnoeud_aux;
     ptnoeud_aux->PREV = pthead;
     }
  
 return ptnoeud;
 }

/***********************************************************************************
* grille
*
***********************************************************************************/
 NODE  *grille(ptccol,ptclin)
 chain_list *ptccol;
 chain_list *ptclin;

 {
 chain_list *ptccon;
 LINE       *ptlin=NULL;
 GABARIT    *ptgab=NULL;
 NODE       *pthead=NULL;
 NODE       *ptfilnoeud=NULL;
 NODE       *ptnoeud=NULL;
 TRACK      *pttrack;
 
# ifdef DEBUG_ROUTER 
  if ( DEBUG_ROUTER ) fprintf(FOUT,"Entree de grille :\n");
# endif
  
 ptlin = (LINE *)ptclin->DATA;
 ptgab = ptlin->GAB;
  
/* creation de la structure NODE pour les connecteur de la colonne LEFT */
 pthead = addnoeud(pthead,ptgab->NBTRACK-1);
 ptfilnoeud = pthead;
 ptccon = getccon(ptlin->CON,ptccol,ptclin);
 for (;ptccon;ptccon=getccon(ptccon->NEXT,ptccol,ptclin))
     {
     pttrack = ptgab->TRACK->NEXT;
     for (ptnoeud=pthead;ptnoeud;ptnoeud=ptnoeud->DPR_UP,pttrack=pttrack->NEXT)
         put_in_grid(ptnoeud,pttrack->Y,(CONNECTOR *)ptccon->DATA);
     }
   
/* creation de la structure NODE pour les connecteur des colonnes OPERATOR */
 for (ptccol=ptccol->NEXT->NEXT;ptccol->NEXT;ptccol=ptccol->NEXT->NEXT)
     {
     pthead = addnoeud(pthead,ptgab->NBTRACK-1);
     ptccon = getccon(ptlin->CON,ptccol,ptclin);
     for (;ptccon;ptccon=getccon(ptccon->NEXT,ptccol,ptclin))
         {
         pttrack = ptgab->TRACK->NEXT;
         for (ptnoeud=pthead;ptnoeud;ptnoeud=ptnoeud->DPR_UP,pttrack=pttrack->NEXT)
             put_in_grid(ptnoeud,pttrack->Y,(CONNECTOR *)ptccon->DATA);
         }
     }
   
/* creation de la structure NODE pour les connecteur de la ligne RIGHT */
 pthead = addnoeud(pthead,ptgab->NBTRACK-1);
 ptccon = getccon(ptlin->CON,ptccol,ptclin);
 for (;ptccon;ptccon=getccon(ptccon->NEXT,ptccol,ptclin))
     {
     pttrack = ptgab->TRACK->NEXT;
     for (ptnoeud=pthead;ptnoeud;ptnoeud=ptnoeud->DPR_UP,pttrack=pttrack->NEXT)
         put_in_grid(ptnoeud,pttrack->Y,(CONNECTOR *)ptccon->DATA);
     }

# ifdef DEBUG_ROUTER
    if ( DEBUG_ROUTER ) fprintf(FOUT,"Sortie de grille :\n");
# endif

 return ptfilnoeud;
 }

/*******************************************************
* generobs
*        Generation des obstacles IMPLICITES de la grille
*  et verification de la coherence pour chaque noeud vide 
*  avec la liste des transparences de la ligne.
********************************************************/
 void   generobs(ptnoeud,ptccol_head,ptlin)
 NODE *ptnoeud;
 chain_list *ptccol_head;
 LINE *ptlin;
 
 {
 NODE *noeud1=NULL,*noeud2=NULL,*noeud3=NULL;
 int trouve_DWN=FALSE;
 ACCESS *acces1=NULL,*acces2=NULL,*acc_obs=NULL;
 long index=0,savindex=0,y=0,col=0,savcol=0;
 TRACK *pttrack=NULL;
 chain_list *ptcallow=NULL;
 SEGMENT    *ptallow=NULL;
 chain_list *ptccol=NULL;
 chain_list *ptcinscol=NULL;
 INSTANCE   *ptinscol=NULL;

 /* parcours de gauche a droite */
 for (noeud1=ptnoeud->NEXT;noeud1->NEXT;noeud1=noeud1->NEXT,col++)
     {
     index=0;
     /* parcours de bas en haut */
     for (noeud2=noeud1;noeud2;noeud2=noeud2->DPR_UP,index++)
         {
         if (noeud2->DPR_RIGHT)
            {
            /*la pile des acces est non vide */
            if (noeud2->DPR_RIGHT->ORIENT==EAST)
               {
               /* parcours des acces de droite a gauche */
               for (acces1=noeud2->DPR_RIGHT;acces1;acces1=acces1->PREV)
                   {
                   if (acces1->ORIENT==WEST)
                      {
                      break;
                      }
                   }
               if (acces1)  /* j'ai trouve un acces WEST */
                  {
                  if (acces1->POS->X!=acces1->NEXT->POS->X) /*deux ref !=*/
                     {
                     /*recherche de y de l'horizontale */
                     savindex = index;
                     for (pttrack=ptlin->GAB->TRACK->NEXT;index;
                          index--,pttrack=pttrack->NEXT);
                     index = savindex;
                     y = pttrack->Y;
                     /*recherche de la colonne */
                     savcol = col;
                     for (ptccol=ptccol_head->NEXT->NEXT;col;
                          col--,ptccol=ptccol->NEXT->NEXT);
                     col = savcol; 
                     for (ptcinscol=((COLUMN *)ptccol->DATA)->INS;ptcinscol;
                          ptcinscol=ptcinscol->NEXT)
                         {
                         ptinscol = (INSTANCE *)ptcinscol->DATA;
                         if ((ptinscol->Y<y)&&((ptinscol->Y+ptinscol->HEIGHT)>y))
                            {
                            /*recherche de la coherence par rapport a la liste*/
                            /*des transparences de l'instance*/
                            for (ptcallow=ptinscol->ALLOW;ptcallow->DATA;
                                 ptcallow=ptcallow->NEXT)
                                {
                                ptallow = (SEGMENT *)ptcallow->DATA;
                                if ((ptallow->Y1==y)&&
                                    (ptallow->X1<=ptinscol->X)&&
                                    (ptallow->X2>=ptinscol->X+ptinscol->WIDTH))
                                   break;
                                }
                            if (!ptcallow->DATA) /*c.a.d no transp traversante */
                               {
                               /*on trouve un obstacle au milieu,*/
                               /* juste a droite de acces1*/
                               /*printf("obstacle au milieu\n");*/
                               acc_obs = mkacces(acces1->NEXT,acces1,NULL,
                                                 ORIENTX,NULL);
                               acces1->NEXT->PREV = acc_obs;
                               acces1->NEXT = acc_obs;
                               total_acc--;
                               }
                            break;
                            }
                         if (ptinscol->Y>y)
                            {
                            printf("BUG: acces with no corresponding instance!!\n");
                            exit(27);
                            }
                         }
                     }
                  }
               else
                  {
                  /* on a trouve un obstacle a gauche de pile d'acces */
                  acc_obs = mkacces(noeud2->DPR_LEFT,NULL,NULL,ORIENTX,NULL);
                  noeud2->DPR_LEFT->PREV = acc_obs;
                  noeud2->DPR_LEFT = acc_obs;
                  total_acc--;
                  }
               }
            else /* c.a.d noeud2->RIGHT->ORIENT==WEST */
               {
               /* on a trouve un obstacle a droite de pile d'acces */
               acc_obs = mkacces(NULL,noeud2->DPR_RIGHT,NULL,ORIENTX,NULL);
               noeud2->DPR_RIGHT->NEXT = acc_obs;
               noeud2->DPR_RIGHT=acc_obs;
               total_acc--;
               }
            }
         else /* c.a.d pile des acces vide, vraie transparence?? */
            {
            /* verification de la coherence pour chaque noeud ayant une pile vide */
            /* avec la liste des transparences de sa colonne.        */
            /* on dispose de l'index on recherche l'ordonnee reelle  */

            /*recherche de y de l'horizontale */
            savindex = index;
            for (pttrack=ptlin->GAB->TRACK->NEXT;index;
                 index--,pttrack=pttrack->NEXT);
            index = savindex;
            y = pttrack->Y;
            /*printf("le y trouve de l'horizontale:%ld\n",y);*/
            /*recherche de la colonne*/
            savcol = col;
            for (ptccol=ptccol_head->NEXT->NEXT;col;
                 col--,ptccol=ptccol->NEXT->NEXT);
            col = savcol; 
            /*printf("la colonne trouve:%d\n",((COLUMN *)ptccol->DATA)->INDEX);*/
            /*recherche de l'instance*/
            for (ptcinscol=((COLUMN *)ptccol->DATA)->INS;ptcinscol;
                 ptcinscol=ptcinscol->NEXT)
                {
                ptinscol = (INSTANCE *)ptcinscol->DATA;
                if ((ptinscol->Y<y)&&((ptinscol->Y+ptinscol->HEIGHT)>y))
                   {
                   /*recherche de la coherence par rapport a la liste*/
                   /*des transparences de l'instance*/
                   for (ptcallow=ptinscol->ALLOW;((ptcallow)&&(ptcallow->DATA));
                        ptcallow=ptcallow->NEXT)
                       {
                       /*printf("y d'une transparence:%ld\n",
                                ((SEGMENT *)ptcallow->DATA)->Y1);*/
                       if (((SEGMENT *)ptcallow->DATA)->Y1==y)
                          break;
                       }
                   if ((!ptcallow)||(!ptcallow->DATA))
                      /*c.a.d on ne trouve pas de transparence*/
                      {
                      /* on a detecte un obstacle */
                      /*printf("fausse transparence!!\n");*/
                      acc_obs=mkacces(NULL,NULL,NULL,ORIENTX,NULL);
                      noeud2->DPR_RIGHT=acc_obs;
                      noeud2->DPR_LEFT=acc_obs;
                      total_acc--;
                      }
                   break;
                   }
                if (ptinscol->Y>y)
                   break;
                }
            }
         }
     }
 }

/***********************************************************************************
* dprrout
*  Corps du programme principal de routage global.
***********************************************************************************/
 void dprrout(ptfig,option_o)
 FIGURE *ptfig;
 int     option_o;

 {
 chain_list    *ptclin=NULL;
 chain_list    *ptclin1=NULL;
 chain_list    *ptclin2=NULL;
 int            bitslice=0;
 int            trouve=0;
 LINE          *ptlin=NULL;
 LINE          *ptlin1=NULL;
 LINE          *ptlin2=NULL;
 NODE          *ptnoeud=NULL;
 long           reste_total_acc=0l;
 int            non_fin=TRUE;
 NODE          *noeud1=NULL;
 NODE          *noeud2=NULL;
 NODE          *noeud3=NULL;
 NODE          *noeud4=NULL;
 ACCESS        *acces=NULL;
 ACCESS        *acces1=NULL;
 ACCESS        *acces2=NULL;
 POSSIBILITY   *ptpos1=NULL;
 long           i=0l,j=0l;
 TRACK         *pttrack_head=NULL;
 TRACK         *pttrack=NULL;

# ifdef DEBUG_ROUTER 
    if ( DEBUG_ROUTER ) fprintf(FOUT,"Entree de dprrout :\n");
# endif
 
/* creation de la grille symbolique de la figure pour eviter les */
/* connexions mono-connecteur (la grille est dupliquee et les    */
/* obstacles n'y sont pas representes!)                          */

/* creation des grilles pour chaque bit-slice */
 for (ptclin=ptfig->LIN;ptclin;ptclin=ptclin->NEXT)
     {
     ptlin = (LINE *)ptclin->DATA;
     ptlin->GRID = grille(ptfig->COL,ptclin);
     }

/* chainage des grilles des differentes lignes (ou slices) */
 ptclin1 = ptfig->LIN;
 for (ptclin2=ptclin1->NEXT;ptclin2;ptclin1=ptclin2,ptclin2=ptclin2->NEXT)
     {
     ptlin1 = (LINE *)ptclin1->DATA;
     ptlin2 = (LINE *)ptclin2->DATA;
     for (noeud1=ptlin1->GRID;noeud1->DPR_UP;noeud1=noeud1->DPR_UP);
     for (noeud2=ptlin2->GRID;noeud1;noeud1=noeud1->NEXT,noeud2=noeud2->NEXT)
         {
         noeud1->DPR_UP = noeud2;
         noeud2->DPR_DWN = noeud1;
         }
     }

/* positionnement de ptfig->GRID */
 ptclin = ptfig->LIN;
 ptlin = (LINE *)ptclin->DATA;
 ptfig->GRID = addchain(ptfig->GRID,(void *)ptlin->GRID);

/* enlever les acces "uniques" et INTERNE*/
 for (noeud1=(NODE *)ptfig->GRID->DATA;noeud1;noeud1=noeud1->NEXT)
     for (noeud2=noeud1;noeud2;noeud2=noeud2->DPR_UP)
         for (acces1=noeud2->DPR_LEFT;acces1;acces1=acces1->NEXT)
             {
             if (acces1->SIG->TYPE=='I')
                {
                trouve = 0;
                for (noeud3=(NODE *)ptfig->GRID->DATA;noeud3;noeud3=noeud3->NEXT)
                    {
                    for (noeud4=noeud3;noeud4;noeud4=noeud4->DPR_UP)
                        {
                        for (acces2=noeud4->DPR_LEFT;acces2;acces2=acces2->NEXT)
                            {
                            if ((acces1->SIG==acces2->SIG)&&(acces1!=acces2)&&
                                (acces1->POS->CON!=acces2->POS->CON))
                               {
                               trouve = 1;
                               break;
                               }
                            }
                        if (trouve==1)
                           break;
                        }
                    if (trouve==1)
                       break;
                    }
                if (trouve==0) /* c.a.d acces unique */
                   {
                   /*printf("DPR Warning: \n");*/
                   del_acces(noeud2,acces1);
                   }
                }
             }

/* pour voir les acces de la grille globale de la figure */
/* for (noeud1=(NODE *)ptfig->GRID->DATA,i=1;noeud1;noeud1=noeud1->NEXT,i++)
     for (noeud2=noeud1,j=1;noeud2;noeud2=noeud2->DPR_UP,j++)
         for (acces=noeud2->DPR_LEFT;acces;acces=acces->NEXT)
             if (acces->POS)
                ptpos1 = acces->POS;*/
     
/* dechainage de la grille globale pour obtenir N grilles */
 ptclin1 = ptfig->LIN;
 for (ptclin2=ptclin1->NEXT;ptclin2;ptclin1=ptclin2,ptclin2=ptclin2->NEXT)
     {
     ptlin1 = (LINE *)ptclin1->DATA;
     ptlin2 = (LINE *)ptclin2->DATA;
     for (noeud1=ptlin1->GRID;noeud1->DPR_UP!=ptlin2->GRID;noeud1=noeud1->DPR_UP);
     for (noeud2=ptlin2->GRID;noeud1;noeud1=noeud1->NEXT,noeud2=noeud2->NEXT)
         {
         noeud1->DPR_UP = NULL;
         noeud2->DPR_DWN = NULL;
         }
     }

/* routage sur grille symbolique ligne par ligne */ 
 for (ptclin=ptfig->LIN;ptclin;ptclin=ptclin->NEXT)
     {
     printf(" * Bit-slice %d symbolic routing *\n",bitslice);
     bitslice = bitslice + 1;
     ptlin = (LINE *)ptclin->DATA;
     /*ptnoeud = grille(ptfig->COL,ptclin);
     ptlin->GRID = ptnoeud;*/
     ptnoeud = ptlin->GRID;
     generobs(ptnoeud,ptfig->COL,ptlin);
     /*total_acc_col = total_acc - reste_total_acc;*/
     non_fin=TRUE;
     if (option_o)
        {
        while (non_fin)
              {
              non_fin = heuristique_2o(ptfig->COL,ptnoeud);
              }
        }
     else
        {
        while (non_fin)
              {
              non_fin = heuristique_2(ptfig->COL,ptnoeud);
              }
        }

     diff_line(ptfig->COL,ptnoeud);

     non_fin=TRUE;
     while (non_fin)
           {
           non_fin = heuristique_3(ptfig->COL,ptnoeud);
           }

     /* pour voir les acces qui restent dans chaque bit-slice */
     /*for (noeud1=ptnoeud,i=1;noeud1;noeud1=noeud1->NEXT,i++)
         for (noeud2=noeud1,j=1;noeud2;noeud2=noeud2->DPR_UP,j++)
             for (acces=noeud2->DPR_LEFT;acces;acces=acces->NEXT)
                 if (acces->POS)
                    ptpos1 = acces->POS;*/
     
     }

 /* chainage des grilles et routage multi-bit si necessaire */
 pttrack_head = diff_all(ptfig);

 /* pour voir les acces qui restent et enlever ceux qui sont attendus */
 if (total_acc)
    {
    for (noeud1=((LINE *)ptfig->LIN->DATA)->GRID,i=1;noeud1;noeud1=noeud1->NEXT,i++)
        for (noeud2=noeud1,j=1;noeud2;noeud2=noeud2->DPR_UP,j++)
            for (acces=noeud2->DPR_LEFT;acces;acces=acces->NEXT)
                if (acces->POS)
                   {
                   ptpos1 = acces->POS;
                   if ((acces->ORIENT==EAST)||
                       ((acces->SIG->MIN_COL+acces->SIG->WIDTH)==(2*i)-1))
                      printf("WARNING: Routing signal %s not finished (Cyclic case)!!\n",
                              acces->SIG->NAME);
                   else
                      del_acces(noeud2,acces);
                   }
    }

 /* parcours de la grille pour recuperer les transparences globales */
 for (noeud1=((LINE *)ptfig->LIN->DATA)->GRID;noeud1;noeud1=noeud1->DPR_UP)
     {
     for (noeud2=noeud1;noeud2;noeud2=noeud2->NEXT)
         if (noeud2->DPR_LEFT) /* c.a.d obstacle */
            break;
     if (!noeud2) /* c.a.d traverse la grille */
        {
        /* extraction de y de la transparence */
        noeud2 = noeud1;
        for (pttrack=pttrack_head;noeud2;pttrack=pttrack->NEXT,noeud2=noeud2->DPR_DWN);
        ptfig->ALLOW = addseg(ptfig->ALLOW,"",0,pttrack->Y,0,pttrack->Y,
                              WLAYER2,'H',TALU2);
        }
     }

# ifdef DEBUG_ROUTER
  if ( DEBUG_ROUTER ) fprintf(FOUT,"Sortie de dprrout :\n");
# endif

 }
