update.c

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

#include "struct.h"

struct V Vceiling;


//local function

/*
void pushCeil(int cj, int cverin);
void putCeil(int j, struct OT *ot);
*/
 

 
void createVceiling()
{
 Vceiling.x=0;
 Vceiling.y=xybound;
 Vceiling.w=xybound;
 Vceiling.h=0;
 Vceiling.type="R";
 Vceiling.orient=HOR;
}


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

void pushCeil(struct OT *ot)
{
int i,j;
createVceiling();
HeadCeil=InivCeil();
HeadCeil->parent=HeadCeil;
ccurrent=HeadCeil;
Gap=xybound;
//printf(" Gap %d \n", Gap);
placeX(ot);
//BellmanFord(ot);
for (i=0; i<ot->n; i++)
putCeil(ot->n-1-i, ot);
//printf(" Headceil.y %d \n", HeadCeil->y);

}


void putCeil(int j, struct OT *ot)
{
int maxx, miny;
int jj=ot->perm[j];
int fmax;
struct V *pp=&ver[jj];
struct NodeList *p, *q;
struct NodeList *vp=(struct NodeList *)calloc(sizeof(struct NodeList),1);
vp->block=pp;
   ot->x[j]=vp->x=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;
miny=xybound;
  while(ccurrent!=NULL && ccurrent->x >vp->x)
     ccurrent=ccurrent->prev;
    while(ccurrent->x+ccurrent->w <=vp->x)
      ccurrent=ccurrent->next;
     p=ccurrent;
q=p;
while(p!=NULL && (p->x <maxx))
  { int cury=p->block->y;
    if (cury <miny) miny=cury;
//printf(" cury.y %d ", cury);
    q=p;
    p=p->next;
   }
  vp->y=miny=miny-vp->h;
//printf(" vp y %d \n", vp->y);
  pp->y=vp->y;
 if (Gap >miny) Gap=miny;
 fmax=q->x+q->w;

  if (q==ccurrent)
{
  if (ccurrent->x <vp->x && fmax >maxx)
    {
   struct NodeList *temp1=(struct NodeList *)calloc(sizeof(struct NodeList),1);
          temp1->block=ccurrent->block;
          temp1->x=maxx;
          temp1->w=fmax-temp1->x;
          vp->next=temp1;
          temp1->next=ccurrent->next;
       if (ccurrent->next) ccurrent->next->prev=temp1;
        temp1->prev=vp;
        ccurrent->w=vp->x-ccurrent->x;
        ccurrent->next=vp;
        vp->prev=ccurrent;
        vp->child=ccurrent;
        vp->tail=temp1;
     }
  else { if (ccurrent->x==vp->x && fmax==maxx)
    {
      vp->prev=ccurrent->prev;
      if (ccurrent->prev) ccurrent->prev->next=vp;
      else HeadCeil=vp;
      vp->next=ccurrent->next;
      if (ccurrent->next) ccurrent->next->prev=vp;
       }
    else {
         if (ccurrent->x==vp->x)
          {
            vp->prev=ccurrent->prev;
            if (ccurrent->prev) ccurrent->prev->next=vp;
            else HeadCeil=vp;
            vp->next=ccurrent;
            ccurrent->prev=vp;
            ccurrent->w=fmax-maxx;
            ccurrent->x=maxx;
          }
        else{
         vp->next=ccurrent->next;
         if (ccurrent->next) ccurrent->next->prev=vp;
         ccurrent->next=vp;
         vp->prev=ccurrent;
         ccurrent->w=vp->x-ccurrent->x;
         }
      }
     vp->child=vp->tail=ccurrent;
     }
}
else {
  if (vp->x==ccurrent->x)
   {
       vp->prev=ccurrent->prev;
      if (ccurrent->prev) ccurrent->prev->next=vp;
      else HeadCeil=vp;
       vp->child=ccurrent;
   }
  else {
     vp->child=ccurrent->next;
     vp->prev=ccurrent;
     ccurrent->next=vp;
     ccurrent->w=vp->x-ccurrent->x;
       }
   if (fmax==maxx)
    { 
      vp->next=q->next;
      if (q->next) q->next->prev=vp;
      vp->tail=q;
    }
   else{
    vp->tail=q->prev;
    vp->next=q;
     q->prev=vp;
     q->w=fmax-maxx;
     q->x=maxx;
       }
   }
 ccurrent=vp;
}
    
  




void ceilDismiss(struct NodeList *List)
{
  if (List)
  { if (List->next) ceilDismiss(List->next);
     free(List);
  }
}




void peelCeil(int jj, struct OT *ot)
{
struct NodeList *point, *p,*q;
point=HeadCeil;
while( point && point->block!= & ver[ot->perm[jj]])
point=point->next;
if (!point) exit(0);

  
if (point->child->w+point->child->x == point->x && point->tail->x== point->x+point->w)
  { 
    point->child->w=point->child->w+point->w+point->tail->w;
    point->child->next=point->tail->next;
    if (point->tail->next) point->tail->next->prev=point->child;
    free(point->tail);
    free(point);
  }
else {
  if ( point->child->x==point->x && point->tail->x+point->tail->w==point->x+point->w)
   {
     if (point->prev) point->prev->next=point->child;
     else HeadCeil=point->child;
     if (point->next) point->next->prev=point->tail;
   }
  else{

   if (point->prev && point->prev==point->child)
     {
       point->prev->next=point->next;
       if (point->next) point->next->prev=point->prev;
       point->prev->w+=point->w;
     }
   else{
     if ( point->next && point->next==point->tail)
         {
           if (point->prev) point->prev->next=point->tail;
           else HeadCeil=point->tail;
           point->tail->prev=point->prev;
           point->tail->x=point->x;
           point->tail->w+=point->w;
          }
     else{
           if (point->next==point->child)
              {
  int mytrue;
 mytrue=point->child->block->y<=point->tail->block->y;
   if (mytrue)
                 {
          point->child->w+=point->child->x-point->child->block->x;
                  point->child->x=point->child->block->x;
           point->tail->w=point->child->x-point->tail->x;
                 }
                else
                 {
              point->child->w+=point->child->x;
                 point->child->x=point->tail->block->x+(point->tail->block->orient%2?point->tail->block->h:point->tail->block->w);
             point->child->w-=point->child->x;
             point->tail->w=point->child->x-point->tail->x;
                 }
              }
           else{
             if (point->prev)
             point->prev->w=point->child->x-point->prev->x;
             else HeadCeil=point->child;
             if (point->next)
             {
              point->next->w+=point->next->x;
             point->next->x=point->tail->x+point->tail->w;
             point->next->w=point->next->w-point->next->x;
              }
             }
           
       if (point->prev) point->prev->next=point->child;
       if (point->next) point->next->prev=point->tail;
        } 
          }
}
      free(point);
      }
}