place.c

用C实现的基于O-tree的ic设计布图布线工具源代码,有相关文档

#include "struct.h"

//local function

 

struct V Vfloor;
void child(struct OT *ot, int index, int diff);
int between(struct OT *ot, int a, int b);
int Otfeasible(struct OT *ot);
int decedent(struct OT *ot, int a, int b);




void placeX(ot)
struct OT *ot;
{
 int i, j, *sstack, w;
 int sindex=-1;
 int width;

Width=0;
sstack=(int *)calloc(sizeof(int), ot->n);
  for (i=j=0; i<2*ot->n; i++)
   {
     if (ot->code[i]==0)
      {
        int jj=ot->perm[j];
         if (sindex==-1)
         ver[jj].x=ot->x[j]=0;
         else
         { w=ot->orient[sstack[sindex]]%2?ver[ot->perm[sstack[sindex]]].h:ver[ot->perm[sstack[sindex]]].w;
         ver[jj].x=ot->x[j]=ot->x[sstack[sindex]]+w;
         }
         sindex++;
         sstack[sindex]=j;
         width=ot->x[j]+(ot->orient[j]%2?ver[jj].h:ver[jj].w);
//printf(" ot ->x %d , width %d \n", ot->x[j], width);
      j++;
     if (Width < width) Width=width; 
     }
     else
      sindex--;
}
free(sstack);


}


int BellmanFord(struct OT *ot)
{
int i,k, parent,w, child;

 int *myindex=(int *)malloc(ot->n*sizeof(int));

 for ( i=0; i<ot->n; i++)
  {
  ot->x[i]=ver[ot->perm[i]].x=MAXfloat;
  ver[ot->perm[i]].orient=ot->orient[i];
  }



 for ( k=1; k<=ot->n-1; k++)
  {
   parent=0;
   myindex[parent]=-1;
   child=-1;
    for (i=0; i<2*ot->n; i++)
     {
      if (ot->code[i]==0)
     {
      child++;
      if (myindex[parent]==-1)
     { if (ver[ot->perm[child]].x >0.0)
       ot->x[child]=ver[ot->perm[child]].x=0;}
      else
{
      w=ot->orient[child]%2?ver[ot->perm[myindex[parent]]].h:ver[ot->perm[myindex[parent]]].w;
    if (ver[ot->perm[child]].x >ver[ot->perm[myindex[parent]]].x-w)
     ot->x[child]=ver[ot->perm[child]].x=ver[ot->perm[myindex[parent]]].x-w ;
   }
      parent++;
      myindex[parent]=child;
    }
   else
    parent--;
    }
   for (i=0; i<LL_count; i++)
   {
    if (ver[LL[i].a].type[2]=='R')
     {
     if (ver[LL[i].a].type[1]=='L')
      {
     if (ver[LL[i].a].x >ver[LL[i].b].x)
      ver[LL[i].a].x=ver[LL[i].b].x;
     if (ver[LL[i].b].x > ver[LL[i].a].x)
      ver[LL[i].b].x=ver[LL[i].a].x;
      }
     else
     {
      int w1=ver[LL[i].a].orient%2?ver[LL[i].a].h:ver[LL[i].a].w;
      int w2=ver[LL[i].b].orient%2?ver[LL[i].b].h:ver[LL[i].b].w;
       if (ver[LL[i].a].x -w1>ver[LL[i].b].x-w2)
      ver[LL[i].a].x=ver[LL[i].b].x-w2+w1;
     if (ver[LL[i].b].x -w2> ver[LL[i].a].x-w1)
      ver[LL[i].b].x=ver[LL[i].a].x-w1+w2;
     }
   }
}
  
  }

for (i=0; i<ot->n; i++)
ot->x[i]=ver[ot->perm[i]].x;
parent=0;
   myindex[parent]=-1;
   child=-1;
    for (i=0; i<2*ot->n; i++)
     {
      if (ot->code[i]==0)
    {
      child++;
      if (myindex[parent]==-1)
       { if (ver[ot->perm[child]].x > 0.0)
         return 0;}
      else
{
    w=ot->orient[child]%2?ver[ot->perm[myindex[parent]]].h:ver[ot->perm[myindex[parent]]].w;
if (ver[ot->perm[child]].x >ver[ot->perm[myindex[parent]]].x-w)
       return 0;
  }
      parent++;
      myindex[parent]=child;
}
   else
    parent--;
    }

   for (i=0; i<LL_count; i++)
   {
    if (ver[LL[i].a].type[2]=='R')
     {
     if (ver[LL[i].a].type[1]=='L')
      {
     if (ver[LL[i].a].x >ver[LL[i].b].x) return 0;
     if (ver[LL[i].b].x > ver[LL[i].a].x) return 0;
      }
     else
     {
      int w1=ver[LL[i].a].orient%2?ver[LL[i].a].h:ver[LL[i].a].w;
      int w2=ver[LL[i].b].orient%2?ver[LL[i].b].h:ver[LL[i].b].w;
       if (ver[LL[i].a].x -w1>ver[LL[i].b].x-w2)
        return 0;
     if (ver[LL[i].b].x -w2> ver[LL[i].a].x-w1)
        return 0;
     }
   }

}

for (i=0; i<ot->n; i++)
{
ot->x[i]=ver[ot->perm[i]].x=-ver[ot->perm[i]].x;
printf("%d ", ot->x[i]);
}
printf(" Bellmanford x \n");
return 1;


}




int Otfeasible(struct OT *ot)
{ int i, diff;
  for (i=0; i< LR_count; i++)
{ if (ver[LR[i].a].x+ver[LR[i].a].w < ver[LR[i].b].x+ver[LR[i].b].w)
    {
    diff=ver[LR[i].b].x+ver[LR[i].b].w-ver[LR[i].a].w-ver[LR[i].a].x;
    ver[LR[i].a].x=ver[LR[i].b].x+ver[LR[i].b].w-ver[LR[i].a].w;
    child(ot, LR[i].a, diff);
    Width+=diff;
    }
  else{
    diff=ver[LR[i].a].x+ver[LR[i].a].w-ver[LR[i].b].w-ver[LR[i].b].x;
    ver[LR[i].b].x=ver[LR[i].a].x+ver[LR[i].a].w-ver[LR[i].b].w;
    child(ot, LR[i].b, diff);
    Width+=diff;
    }
}



  for (i=0; i<LR_count; i++)
   if (between(ot, LR[i].a, LR[i].b)) return 0;


return 1;

}

void child(struct OT *ot, int index, int diff)
{
  int i,j,k;
  for (i=0; i<ot->n && ot->perm[i]!=index; i++);
  for (j=k=1; j<ot->n*2 && k<i+1; j++) if (ot->code[j]==0) k++;
//  printf(" in child j %d  \n", j);
  if (ot->code[j]==1) return ;
  else 
    {

       int kindex=1;
       while (kindex >0)
       {
//printf(" j is %d \n", j);
         if (ot->code[j]==1) kindex--;
         else 
           { i++;
             kindex++;
              ver[ot->perm[i]].x+=diff;}
         j++;
       }
    }
}

int between(struct OT *ot, int a, int b)
{
 int i, bindex;
 int width, maxx;

 for (i=0; i<ot->n && ot->perm[i]!=a && ot->perm[i]!=b; i++);
 if (ot->perm[i]==a) bindex=b;
 else  bindex=a;
 width=ver[a].x+ver[a].w;
 maxx=(ver[a].x >ver[b].x)?ver[a].x: ver[b].x;
 for (i=i+1; i<ot->n && ot->perm[i]!=bindex; i++)
  {
if ((ver[ot->perm[i]].x+ver[ot->perm[i]].w<=maxx) || (ver[ot->perm[i]].x >=width));
 else return 1;
  }
 return 0;
}


void createVfloor()
{
 Vfloor.x=0;
 Vfloor.y=0;
 Vfloor.w=xybound;
 Vfloor.h=0;
 Vfloor.type="R";
 Vfloor.orient=0;
 Vfloor.ot_child=Vfloor.ot_tail=NULL;
}



struct NodeList * Inivfloor()
{
 struct NodeList *t;
 t=(struct NodeList *)calloc(sizeof(struct NodeList),1);
 t->block=&Vfloor;
 t->next=NULL;
 t->prev=NULL;
 t->parent=NULL;
 t->child=NULL;
 t->x=0;
 t->y=0;
 t->h=0;
 t->w=Vfloor.w;
 return t;
}


int place(struct OT *ot)
{
struct NodeList *nPtr, *nPtr2;
int i,j, changed=0;
createVfloor();
HeadFloor=Inivfloor();
HeadFloor->parent=&froot;
fcurrent=&froot;
fcurrent->next=HeadFloor;
HeadFloor->prev=&froot;

//BellmanFord(ot);
placeX(ot);
  for (i=j=0; i<2*ot->n; i++)
   {
     if (ot->code[i]==0)
      {
      if (placeCell(ot, j)) changed=1;
//printf(" changed %d \n", changed);
      j++;
     }
     else
     fcurrent=fcurrent->parent;

}
//printf(" in place 2 \n");

//printf(" in the end of the place \n");

/* free the node list */
nPtr = HeadFloor;
while ( nPtr != NULL )
{
    nPtr2 = nPtr->next;
    //free(nPtr);
    nPtr = nPtr2;
}

/* free the node list */
nPtr = fcurrent;
while ( nPtr != NULL )
{
    nPtr2 = nPtr->next;
    //free(nPtr);
    nPtr = nPtr2;
}

/* free the node list */
nPtr = froot.next;
while ( nPtr != NULL )
{
    nPtr2 = nPtr->next;
    //free(nPtr);
    nPtr = nPtr2;
}

return changed;

}

  
    

int placeCell(struct OT *ot, int j)
{
 int maxx, maxy, changed=0;
 struct NodeList *p, *q;
 struct NodeList *vp=(struct NodeList *)calloc(sizeof(struct NodeList),1);
 int jj=ot->perm[j];
 struct V *pp=&ver[jj];
 struct NodeList *pq=fcurrent, *hvp;
 int fmax;

 vp->block=pp;
 vp->block->ot_child=vp->block->ot_tail=NULL;
 vp->block->ot_sibling=NULL;
     vp->x=ver[jj].x;
     ot->x[j]=ver[jj].x;
      vp->w=ot->orient[j]%2?ver[jj].h:ver[jj].w;
      vp->h=ot->orient[j]%2?ver[jj].w:ver[jj].h;
  maxx=vp->x+vp->w;
  maxy=0;
 while (fcurrent->x+fcurrent->w <= vp->x)
         fcurrent=fcurrent->next;
          p=fcurrent;
hvp=fcurrent;
            while (p!=NULL && (p->x < maxx))
            { int cury=p->block->y+p->h;
              if (cury > maxy) {maxy=cury; hvp=p;}
             q=p;
              p=p->next;
             }
            vp->y=ot->y[j]=ver[jj].y=maxy;
            fmax=q->x+q->w;
            if (pq->y>pp->y+(pp->orient%2?pp->w:pp->h) || pq->y
+(ot->orient[j]%2?pq->w:pq->h)<pp->y) changed=0;


         if (q==fcurrent) 
{ if (fcurrent->x<vp->x && fmax > maxx)
   {
   struct NodeList *temp1=(struct NodeList *)calloc(sizeof(struct NodeList),1);

           temp1->block=fcurrent->block;
           temp1->x=maxx;
           temp1->w=fmax-temp1->x;
           vp->next=temp1;
           temp1->child=fcurrent->child;
           temp1->parent=fcurrent->parent;
           temp1->next=fcurrent->next;
          if (fcurrent->next) fcurrent->next->prev=temp1;
           temp1->prev=vp;
           fcurrent->w=vp->x-fcurrent->x;
           fcurrent->next=vp;
           vp->prev=fcurrent;
         }
  else{ if (fcurrent->x==vp->x && fmax==maxx)
   {
     vp->prev=fcurrent->prev;
     if (fcurrent->prev) fcurrent->prev->next=vp;
     else {HeadFloor=vp; }
     vp->next=fcurrent->next;
     if (fcurrent->next) fcurrent->next->prev=vp;
   }
   else{
      if (fcurrent->x ==vp->x)
        { 
          vp->prev=fcurrent->prev;
          if (fcurrent->prev) fcurrent->prev->next=vp;
          else {HeadFloor=vp;}
          vp->next=fcurrent;
          fcurrent->prev=vp;
 fcurrent->w=fmax-maxx;
          fcurrent->x=maxx;
         }
       else {
         vp->next=fcurrent->next;
         if (fcurrent->next) fcurrent->next->prev=vp;
         fcurrent->next=vp;
         vp->prev=fcurrent;
         fcurrent->w=vp->x-fcurrent->x;
         }
      }
    }
  }
else {
   if (vp->x==fcurrent->x)
    {
     vp->prev=fcurrent->prev;
     if (fcurrent->prev) fcurrent->prev->next=vp;
 //    else { HeadFloor=vp;}
     vp->child=fcurrent;
    }
  else {
    vp->child=fcurrent->next;
    vp->prev=fcurrent;
    fcurrent->next=vp;
    fcurrent->w=vp->x-fcurrent->x;
     }
   if (fmax==maxx)
    {
      vp->next=q->next;
      if (q->next) q->next->prev=vp;
    }
   else{
      vp->next=q;
      q->prev=vp;
      q->w=fmax-maxx;
      q->x=maxx;
        }
   }

 vp->parent=pq;
   fcurrent=vp;


if (hvp->block->ot_child==NULL)  hvp->block->ot_child=vp->block;
else 
hvp->block->ot_tail->ot_sibling=vp->block;
hvp->block->ot_tail=vp->block;


/* 
printf(" this is %d , fcurrent.h %d   y is %d \n", jj,  fcurrent->h, vp->y);

q=HeadFloor;
while(q)
{
printf(" parent.h %d q.h %d \n", q->parent->h, q->h);
q=q->next;}
 */

return changed;

}