/********************************************************************
*                                                                   *
* 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                     *
*                                                                   *
********************************************************************/
/*********************************************************************************
*                      Fichier: dprlin_R.c                                       *
*       version : 3.0                                                            *
*       date    : 19/03/92                                                       *
*********************************************************************************/
#include "dpr_R.h"
#include "util_R.h"

/**********************************************************************************
* widthalim
*  Calcul de la largeur d'une alim Verticale(direction NORTH or SOUTH.
**********************************************************************************/
 long  widthalim(ptcpos)
 chain_list *ptcpos;

 {
 /* incomplet si utilse pour tous les connecteurs*/
 return (((POSSIBILITY *)ptcpos->DATA)->WIDTH);
 }
 
/*********************************************************************************
* inserttrack                                                                    *
* insertion d'une liste de piste si necessaire, avec tri, dans le champ TRACK    *
* du gabarit.                                                                    *
*********************************************************************************/
 void  inserttrack(ptgabarit,ptcpos)
 GABARIT     *ptgabarit;
 chain_list  *ptcpos;
 
 {
 TRACK       *pttrack=NULL;
 TRACK       *pttrack_save=NULL; 
 POSSIBILITY *ptpos=NULL;
  
 for (;ptcpos;ptcpos=ptcpos->NEXT)
     {
     ptpos = (POSSIBILITY *)ptcpos->DATA;
     pttrack_save=NULL; 
     for (pttrack=ptgabarit->TRACK;pttrack;pttrack=pttrack->NEXT)
         {
         if (pttrack->Y==ptpos->Y)
            {
            pttrack_save = pttrack;
            break;
            }
         else
            if (pttrack->Y>ptpos->Y) 
               break;
            else
               pttrack_save = pttrack;
         }
     if (pttrack_save)
        {
        if (pttrack_save->Y != ptpos->Y)
            {
            ptgabarit->NBTRACK += 1;
            pttrack_save->NEXT = addtrack(pttrack_save->NEXT,ptpos->Y);
            }
        }
     else 
        {
        ptgabarit->NBTRACK += 1;
        ptgabarit->TRACK = addtrack(ptgabarit->TRACK,ptpos->Y);
        }
     }
 }

/*********************************************************************************
* con_in_gabarit
* recherche, avec parcours des possibilites du connecteur, s'il existe une
* possibilite hors gabarit retourne FAUX sinon VRAIS.
*********************************************************************************/
 int   con_in_gabarit(ptcon,ptgabarit) 
 CONNECTOR   *ptcon;
 GABARIT     *ptgabarit;
 
 {
 chain_list  *ptcpos=NULL;
 POSSIBILITY *ptpos=NULL;
 TRACK       *ptstrack=NULL;
 TRACK       *pttrack=NULL;
 
 if ((ptcon->MINPOS <= ptgabarit->TRACK->Y)||
     (ptcon->MAXPOS >= ptgabarit->TRACK->Y + ptgabarit->HEIGHT))
    return FALSE;
 for (ptcpos=ptcon->POS;ptcpos;ptcpos=ptcpos->NEXT)
     {
     ptpos = (POSSIBILITY *)ptcpos->DATA;
     ptstrack = NULL;
     /*if ((char)ptpos->LAYER==NWELL) continue;*/ /* pas necess */
     for (pttrack=ptgabarit->TRACK;pttrack;pttrack=pttrack->NEXT)
         {
         if (ptpos->Y==pttrack->Y)
            break;
         else
            if (pttrack->Y > ptpos->Y)
               break;
         }
     if (pttrack)
        {
        if (pttrack->Y != ptpos->Y)
           return FALSE;
        }
     else
        if ((ptgabarit->TRACK->Y + ptgabarit->HEIGHT)!=ptpos->Y)
           return FALSE;
     }
 return TRUE ;
 }

/*********************************************************************************
* valider_gabarit
* fonction de verification du gabarit extrait des transparences du circuit
* a l'aide d'une bibliotheque de gabarits permis . Resultat:OK/KO.
* le completer eventuellement quand gabcourant inclu dans gabmodel
*********************************************************************************/
 GABARIT *valider_gabarit(ptgabarit)
 GABARIT *ptgabarit;
 
 {
 /* a finir: provisoirement, on cable le bit slice 10 pistes */
 char *vdd=NULL,*vss=NULL;
 int i=0;
 long y=0;
 TRACK *pttrack=NULL;

 vdd = namealloc("vdd");
 vss = namealloc("vss");
 if (!strncmp(ptgabarit->ALIM1,vdd,3))
    {
    ptgabarit->NBTRACK = 11;
    ptgabarit->TRACK->NEXT = NULL;
    pttrack = ptgabarit->TRACK;
    y = pttrack->Y + 70;
    for (i=1;i<11;i++)
        {
        pttrack->NEXT = addtrack(NULL,y);
        pttrack = pttrack->NEXT;
        y = y + 50;
        }
    }
 else
    {
    if (!strncmp(ptgabarit->ALIM1,vss,3))
       {
       ptgabarit->NBTRACK = 11;
       ptgabarit->TRACK->NEXT = NULL;
       pttrack = ptgabarit->TRACK;
       y = pttrack->Y + 80;
       for (i=1;i<11;i++)
           {
           pttrack->NEXT = addtrack(NULL,y);
           pttrack = pttrack->NEXT;
           y = y + 50;
           }
       }
    else
       {
       printf("BUG: First slice Alim must be VDD* or VSS*\n");
       exit(7);
       }
    }
 return ptgabarit;
 }

/********************************************************************************
* initgabarit
*  creation et initialisation de la structure gabarit en parcourant la liste
*  des transparense, jusqu au connecteur de nom nextalim.
*  Detection d'une erreur si se dernier est inexistant.
********************************************************************************/
 GABARIT    *initgabarit (ptname,walim1,ylin,nextalim,ptcheadcon,ptcheadallow)
 char       *ptname;
 long        walim1;
 long        ylin;
 char       *nextalim;
 chain_list *ptcheadcon;
 chain_list *ptcheadallow;

 {
 chain_list *ptccon=NULL;
 chain_list *ptcallow=NULL;
 GABARIT    *ptgabarit=NULL;
 CONNECTOR  *ptcon=NULL;
 SEGMENT    *ptallow=NULL;
 TRACK      *pttrack=NULL;
 long        yalim2;
 
# ifdef DEBUG_ROUTER 
    if (DEBUG_ROUTER) fprintf(FOUT,"Entree de initgabarit :\n");
# endif
  
 ptgabarit = (GABARIT *)mbkalloc(sizeof(GABARIT));
 ptgabarit->ALIM1 = ptname;
 ptgabarit->WALIM1 = walim1;
 ptgabarit->NBTRACK = 1 ;
 ptgabarit->TRACK = addtrack(NULL,ylin);
  
 pttrack = ptgabarit->TRACK;
  
 for (ptccon=ptcheadcon;ptccon;ptccon=ptccon->NEXT)
     {
     ptcon = (CONNECTOR *)ptccon->DATA;
     if (!ptcon)
        {
        printf("Error: Unable to initialize the gabarit, not valid slice!\n");
        exit(7);
        }
     if (!strncmp(ptcon->NAME,nextalim,3))
        {
        yalim2 = ptcon->MAXPOS;
        ptgabarit->HEIGHT = ptcon->MAXPOS - ylin;
        ptgabarit->WALIM2 = widthalim(ptcon->POS);
        break ;
        }
     }
 if (!ptccon)
    {
    printf("Error: VDD and VSS alims must be available in all the instances\n");
    exit(1);
    }
  
/* creer les pistes horizontales du gabarit a partir des transparences */
 for (ptcallow=ptcheadallow;ptcallow;ptcallow=ptcallow->NEXT)
     {
     ptallow = (SEGMENT *)ptcallow->DATA;
     if ((ptallow)&&(ptallow->Y1>ylin)) break;
     }
 if (ptcallow)
    {
    for (;ptcallow->DATA;ptcallow=ptcallow->NEXT)
        {
        ptallow = (SEGMENT *)ptcallow->DATA;
        if (ptallow->Y1>yalim2)
           break;
        else 
           {
           if (pttrack->Y!=ptallow->Y1) /* pour eviter les redondances */
              {
              pttrack->NEXT = addtrack(NULL,ptallow->Y1);
              pttrack = pttrack->NEXT;
              ptgabarit->NBTRACK += 1;
              }
           }
        }
    }

/* rajouter la detection des pistes suplementaires du aux connecteurs fixes
*  d'orientation NORD SUD et de Layer ALU2  */

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

 return (ptgabarit);
 }

/*******************************************************************************
* addlin
*  Creation d'une structure colonne et ajout en tete de chaine.
*******************************************************************************/
 chain_list *addlin(ptchead,ylin,width,index,ptgab)
 chain_list *ptchead;
 long        ylin;
 long        width;
 long        index;
 GABARIT    *ptgab;

 {
 LINE    *ptlin=NULL;

 ptlin = (LINE *)mbkalloc(sizeof(LINE));
 ptlin->X = 0;
 ptlin->Y = ylin;
 ptlin->WIDTH = width;
 ptlin->HEIGHT = ptgab->HEIGHT;
 ptlin->INDEX = index;
 ptlin->GAB  = ptgab;
 ptlin->GRID = NULL;
 ptlin->SIG  = NULL;
 ptlin->CON  = NULL;
 ptlin->INS  = NULL;
 ptlin->N_WELL = NULL;
 ptlin->ALLOW = NULL;
 ptlin->USER = NULL;

 return addchain (ptchead,(void *)ptlin);
 }

/**********************************************************************************
* insertlin
*  
**********************************************************************************/
 chain_list   *insertlin(ptccon,ylin,width,indexlin)
 chain_list   *ptccon;
 long          ylin;
 long          width;
 long         indexlin;

 {
 chain_list  *ptclin=NULL;
 chain_list  *ptccol=NULL;
 chain_list  *ptcallow=NULL;
 chain_list  *ptccon_lin=NULL;
 chain_list  *ptccell_lin=NULL;
 chain_list  *ptcsig_lin=NULL;
 COLUMN      *ptcol=NULL;
 LINE        *ptlin=NULL;
 CONNECTOR   *ptcon=NULL;
 SIGNAL      *ptsig=NULL;
 GABARIT     *ptgabarit=NULL;
 char        *vdd=NULL,*vss=NULL,*nextalim=NULL;
 long          minlin;
 long          walim1;
 long          ynextalim;

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

 vdd = namealloc("vdd");
 vss = namealloc("vss");

 ptcon = (CONNECTOR *)ptccon->DATA;
 if (!strncmp(ptcon->NAME,vdd,3)) 
    nextalim = vss;
 else 
    if (!strncmp(ptcon->NAME,vss,3))
       nextalim = vdd;
    else 
       {
       printf("BUG: The instance must begin with an Alim terminal, %s\n",ptcon->NAME);
       exit(7);
       }
 walim1 = widthalim(ptcon->POS);
 ptcallow = ((INSTANCE *)ptcon->INS->DATA)->ALLOW;
 ptgabarit = initgabarit(ptcon->NAME,walim1,ylin,nextalim,ptccon,ptcallow);
 ptgabarit = valider_gabarit(ptgabarit);
 ptccell_lin = NULL;
 ptccon_lin = NULL;
 ptcsig_lin = NULL;
 ptclin = addlin(NULL,ylin,width,indexlin,ptgabarit);
 for (ptccol=ptcon->COL;ptccol->NEXT;ptccol=ptccol->NEXT->NEXT)
     {
     ptcol = (COLUMN *)ptccol->DATA;
     if (!ptcol->USER)
        continue;
     ptcon = (CONNECTOR *)ptcol->USER->DATA;
     if (ptcon->MINPOS == ylin)
        {
        if (!strncmp(ptcon->NAME,ptgabarit->ALIM1,3))
           {
           ptcol->USER = ptcol->USER->NEXT;
           ptccell_lin = addchain(ptccell_lin,(void *)ptcon->INS->DATA);
           }
        else
           {
           printf("Error: Bad alternance of the alim terminals!!\n");
           exit(7);
           }
        }
     else /* c.a.d ptcon->MINPOS > ylin */
        continue;
     for (;ptcol->USER;ptcol->USER=ptcol->USER->NEXT)
         {
         ptcon = (CONNECTOR *)ptcol->USER->DATA;
         if (!ptcon)
            {
            printf("Error: VDD and VSS alims must delimt all the slices!\n");
            exit(7);
            }
         if (!strncmp(ptcon->NAME,nextalim,3)) 
            { 
            ynextalim = ptcon->MAXPOS;
            if (!(ptcol->USER->NEXT->DATA))
               if ((ptcol->USER=ptcol->USER->NEXT->NEXT))
                  {
                  ptcon = (CONNECTOR *)ptcol->USER->DATA;
                  if ((strncmp(ptcon->NAME,nextalim,3))&&(ptcon->MINPOS==ynextalim))
                     {
                     printf("Error: Bad alternance of the alim terminals!\n");
                     exit(7);
                     }
                  }
            break;
            }
         if (!con_in_gabarit(ptcon,ptgabarit))
            {
            printf("Error: Terminal %s does not fit to the slice gabarit!!\n",ptcon->NAME);
            exit(7);
            }
         else
            {
            ptccon_lin = addchain(ptccon_lin,(void *)ptcon);
            ptcon->LIN = ptclin;
            ptsig = (SIGNAL *)ptcon->SIG->DATA;
            if (!existsig(ptcsig_lin,ptsig))
               {
               minlin = ptsig->MIN_LIN;
               ptsig->MIN_LIN = dpr_min(ptsig->MIN_LIN,indexlin);
               ptsig->HEIGHT =((minlin==MAXINT)?0:dpr_max(minlin+ptsig->HEIGHT,indexlin)
                                                   -ptsig->MIN_LIN);
               ptcsig_lin = addchain(ptcsig_lin,(void *)ptsig);
               ptsig->LIN = addchain(ptsig->LIN,(void *)ptclin->DATA);
               }
            }
         }
     }
 ptlin = (LINE *)ptclin->DATA;
 ptlin->CON = ptccon_lin;
 ptlin->SIG = ptcsig_lin;
 ptlin->INS = ptccell_lin;

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

 return (ptclin);
 }

/*********************************************************************************
* dprlin
*
*********************************************************************************/
 void dprlin(ptroot)
 FIGURE *ptroot;

 {
 chain_list  *ptclin=NULL;
 chain_list  *ptccol=NULL;
 chain_list  *ptccon=NULL;
 chain_list  *ptccon1=NULL;
 GABARIT     *ptgabarit;
 TRACK       *pttrack=NULL;
 CONNECTOR   *ptcon=NULL;
 CONNECTOR   *ptcon1=NULL;
 POSSIBILITY *ptpos=NULL;
 SIGNAL      *ptsig=NULL;
 LINE        *ptlin=NULL;
 COLUMN      *ptcol=NULL;
 long         ylin_pere;
 long         width=0;
 long         minlin=MAXINT;
 int          indexlin=1;
 int          detectlin=TRUE;
 chain_list  *ptcconbug=NULL;
 CONNECTOR   *ptconbug=NULL;
 chain_list  *ptcins=NULL;
 INSTANCE    *ptins=NULL;

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

 ptroot->LIN = addchain(ptroot->LIN,(void *)NULL);
 ptclin = ptroot->LIN;
 while (detectlin)
       {
       ptccon = NULL;
       ylin_pere = MAXLONG;
       for (ptccol=ptroot->COL->NEXT->NEXT;ptccol->NEXT;ptccol=ptccol->NEXT->NEXT)
           {
           ptcol = (COLUMN *)ptccol->DATA;
           /*for (ptcconbug=ptcol->USER;ptcconbug;ptcconbug=ptcconbug->NEXT)
               {
               ptconbug = (CONNECTOR *)ptcconbug->DATA;
               }
           for (ptcconbug=ptcol->DF_CON;ptcconbug;ptcconbug=ptcconbug->NEXT)
               {
               ptconbug = (CONNECTOR *)ptcconbug->DATA;
               }
           for (ptcconbug=ptcol->CT_CON;ptcconbug;ptcconbug=ptcconbug->NEXT)
               {
               ptconbug = (CONNECTOR *)ptcconbug->DATA;
               }
           for (ptcconbug=ptcol->ALIMS;ptcconbug;ptcconbug=ptcconbug->NEXT)
               {
               ptconbug = (CONNECTOR *)ptcconbug->DATA;
               }*/
           if (ptcol->USER)
              {
              ptcon = (CONNECTOR *)ptcol->USER->DATA;
              if ((ptcon->TYPE!=EXTERN)&&(ptcon->MINPOS<ylin_pere))
                 {
                 ylin_pere = ptcon->MINPOS;
                 ptccon = ptcol->USER;
                 }
              }
           }
       if (ptccon)
          {
          if ((ptlin=(LINE *)ptclin->DATA)) /* c.a.d une ligne detecte deja */
             if ((ptlin->Y+ptlin->HEIGHT)>ylin_pere)
                {
                printf("Error: Not valid slice overlapping\n");
                exit(7);
                }
             else;
                /*Avoir la hauteur du canal horizontal, si existe,
                et chercher le(s) gabarit(s) correspondant(s) */
          ptclin->NEXT = insertlin(ptccon,ylin_pere,width,indexlin);
          ptclin = ptclin->NEXT;
          ptlin = (LINE *)ptclin->DATA;
          ptgabarit = ptlin->GAB;

/* mettre les connecteurs DF place de la figure sur le gabarit de la ligne */
          for (ptccon1=ptroot->CON;ptccon1;ptccon1=ptccon1->NEXT)
              {
              ptcon1 = (CONNECTOR *)ptccon1->DATA;
/* dans sigconpere on cree un connecteur par possibilite: pas besoin de for  */
              ptpos = (POSSIBILITY *)ptcon1->POS->DATA;
              if ((ptcon1->COL)&&(!ptcon1->LIN)&&
                 ((ptpos->ACCES==EAST)||(ptpos->ACCES==WEST)))
                 {
                 if ((ptpos->Y>=ptlin->Y)&&(ptpos->Y<ptlin->Y+ptlin->HEIGHT))
                    {
                    if (!con_in_gabarit(ptcon1,ptgabarit)) /* c.a.d flottant */
                       {
                       pttrack = ptgabarit->TRACK->NEXT;
                       ptpos->Y = pttrack->Y;
                       ptcon1->MINPOS = dpr_min(ptcon1->MINPOS,pttrack->Y);
                       ptcon1->MAXPOS = dpr_max(ptcon1->MAXPOS,pttrack->Y);
                       for (pttrack=pttrack->NEXT;pttrack;pttrack=pttrack->NEXT)
                           {
                           ptcon1->POS->NEXT = addpos(ptcon1->POS->NEXT,ptpos->X,
                                                      pttrack->Y,ptpos->LAYER,
                                                      ptpos->ACCES,ptpos->TYPE,
                                                      ptpos->TRACK,ptpos->WIDTH,
                                                      ptcon1);
                           ptcon1->NBPOSS = ptcon1->NBPOSS + 1;
                           ptcon1->MINPOS = dpr_min(ptcon1->MINPOS,pttrack->Y);
                           ptcon1->MAXPOS = dpr_max(ptcon1->MAXPOS,pttrack->Y);
                           }
                       }
                    else /* c.a.d fixe */
                       {
                       ptcon1->MINPOS = ptpos->Y;
                       ptcon1->MAXPOS = ptpos->Y;
                       }
                    ptlin->CON = addchain(ptlin->CON,(void *)ptcon1);
                    ptcon1->LIN = ptclin;
                    ptsig = (SIGNAL *)ptcon1->SIG->DATA;
                    if (!existsig(ptlin->SIG,ptsig))
                       {
                       minlin = ptsig->MIN_LIN;
                       ptsig->MIN_LIN = dpr_min(ptsig->MIN_LIN,indexlin);
                       ptsig->HEIGHT = ((minlin==MAXINT)?0:
                                         dpr_max(minlin + ptsig->HEIGHT,
                                         indexlin) - ptsig->MIN_LIN);
                       ptlin->SIG = addchain(ptlin->SIG,(void *)ptsig);
                       ptsig->LIN = addchain(ptsig->LIN,(void *)ptlin);
                       }
                    }
                 }
              }
          indexlin++;
          }
       else
          detectlin = FALSE ;
       }
 ptclin = ptroot->LIN; /* pas necess */
 ptroot->LIN = ptroot->LIN->NEXT;

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

 }
