otree.c

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

#include "struct.h"

struct V guard, *current;
int codeI, codeJ;


/* create an OT, its values are copied from 'src' */
struct OT *otCopy(struct OT *src) {
  int i;
  struct OT *p;
  p=otCreate(src->dir);
  p->n=src->n;
  /* allocate memory if not empty */
  if (p->n) {
    p->code=(int *)calloc(2*p->n,sizeof(int));
    p->perm=(int *)calloc(p->n,sizeof(int));
    p->orient=(int *)calloc(p->n,sizeof(int));
    p->x=(int *)calloc(p->n,sizeof(int));
    p->y=(int *)calloc(p->n,sizeof(int));
  } else p->code=p->perm=p->orient=p->x=p->y=NULL;
  /* copy values from src */
  for (i=0;i<p->n*2;i++) p->code[i]=src->code[i];
  for (i=0;i<p->n;i++) {
    p->perm[i]=src->perm[i];
    p->orient[i]=src->orient[i];
    p->x[i]=src->x[i];
    p->y[i]=src->y[i];
  }
  return p;
}


void otDismiss(struct OT *p) {
  if (p->n) {
    if (p->code) free(p->code);
    if (p->perm) free(p->perm);
    if (p->orient) free(p->orient);
    if (p->x) free(p->x);
    if (p->y) free(p->y);
  }
  free(p);
}

void codeit(struct OT *ot, struct V *v) {
  ot->perm[codeI]=v-&ver[0];
  ot->orient[codeI]=v->orient;
  ot->x[codeI]=v->x;
  ot->y[codeI++]=v->y;
  ot->code[codeJ++]=0;
  if (v->ot_child) codeit(ot,v->ot_child);
  ot->code[codeJ++]=1;
  if (v->ot_sibling) codeit(ot,v->ot_sibling);
}




/*
void compute_area(struct OT *ot)
{
  int i, maxx=0, maxy=0;
  for (i=0;i<ot->n;i++) {
    int x,y,w,h;
    struct V *p=&ver[ot->perm[i]];
    if (ot->orient[i]%2) w=p->h, h=p->w;
    else w=p->w, h=p->h;
    x=ot->x[i]+w; y=ot->y[i]+h;
    if (x>maxx) maxx=x;
    if (y>maxy) maxy=y;
  }
  area=maxx*maxy;
}
*/

void changeOT(struct OT *ot)
{
int i;
for (i=0; i<ot->n; i++)
ver[ot->perm[i]].orient=ot->orient[i];

 if (ot->n>1){
codeI=codeJ=0;
codeit(ot, &ver[ot->perm[0]]);
}
ot->dir=1-ot->dir;


}

void delOt(struct OT *ot, int index) {
  int i, j, k, l, ii;
  for (i=0; i<ot->n && ot->perm[i]!=index; i++);
  for (j=k=1; j<ot->n*2 && k<=i; j++) if (ot->code[j]==0) k++;
  for (k=j, l=1; k<ot->n*2 && l>0 ; k++) l+=(ot->code[k]?-1:1);
// tprintf("i=%d j=%d k=%d\n",i,j,k);
  for (l=i; l<ot->n-1; l++) ot->perm[l]=ot->perm[l+1];
  for (l=i; l<ot->n-1; l++) ot->orient[l]=ot->orient[l+1];
  for (l=j; l<k-1; l++) {
    // tprintf("minus one (%d) : [",l);
    ot->code[l-1]=ot->code[l];
    // for (ii=0;ii<cell_count*2;ii++) tprintf("%d ",ot->code[ii]);
    // tprintf("]\n");
  }
  for (l=k; l<ot->n*2; l++) {
    // tprintf("minus two (%d) : [",l);
    ot->code[l-2]=ot->code[l];
    // for (ii=0;ii<cell_count*2;ii++) tprintf("%d ",ot->code[ii]);
    // tprintf("]\n");
  }
  ot->n=ot->n-1;
}

void freelist(struct snode *alist)
{
 if (alist) 
  {freelist(alist->next);
   free(alist);
  }
}

void Csibling(struct OT *ot)
{
int i;

struct snode head, *cpoint;
int index=0;

head.next=NULL;
head.prev=NULL;
cpoint=&head;
for (i=0; i<ot->n*2; i++)
{
  if (ot->code[i]==0)
  {
   struct snode *temp;
   temp=(struct snode *)malloc(sizeof(struct snode));
   temp->value=ot->perm[index];
  temp->prev=cpoint;
  temp->next=cpoint->next;
  cpoint->next=temp;
   index++;
   cpoint=temp;
  }
  else cpoint=cpoint->prev;
}

for (i=0; i<ot->n; i++)
{
  int temp=1-ot->code[2*ot->n-1-i];
  ot->code[2*ot->n-1-i]=1-ot->code[i];
  ot->code[i]=temp;
}

index=0;
cpoint=head.next;
while(cpoint)
{
  ot->perm[index]=cpoint->value;
  index++;
  cpoint=cpoint->next;
}

freelist(head.next);

}
  

int otCompact(struct OT *ot) {
  int i, j, changed=0;
  /* compact when #block > 1 */
  if (ot->n>1) {
    guard.contour_prev=guard.contour_next=NULL;
    current=&guard;
    for (i=j=0;i<2*ot->n;i++) {
      if (ot->code[i]==0) { /* put new block */
        int jj=ot->perm[j];
        struct V *pp=&ver[jj];
        pp->ot_child=pp->ot_sibling=pp->ot_tail=NULL;
        if (j==0) { /* first block */
          pp->contour_next=pp->contour_prev=&guard;
          guard.contour_next=guard.contour_prev=pp;
          guard.ot_child=guard.ot_tail=pp;
          pp->orient=ot->orient[j];
          pp->x=pp->y=ot->x[j]=ot->y[j]=0;
          current=pp;
        } else {
          struct V *p, *q, *vp=&guard;
          int maxx=0, maxy=0;
          pp->orient=ot->orient[j];
          p=q=current->contour_next;
          if (ot->dir==HOR) { /* horizontal */
            /* compute xpos */
            pp->x=ot->x[j]=(current==&guard)?0:current->x+(current->orient%2?current->h:current->w);
            /* compute ypos */
            maxx=pp->x+(pp->orient%2?pp->h:pp->w);
            while (p!=&guard && p->x<maxx ) {
              int cury=p->y+(p->orient%2?p->w:p->h);
              if (cury>maxy) maxy=cury, vp=p;
              if (p->x+(p->orient%2?p->h:p->w)<maxx) q=p->contour_next; /* upd
ate contour 1 */
              p=p->contour_next;
            }
            pp->y=ot->y[j]=maxy;
            /* verify changed */
            if (current!=&guard)
            if (current->y>pp->y+(pp->orient%2?pp->w:pp->h) || current->y+(current->orient%2?current->w:current->h)<pp->y) changed=1;
          } else { /* vertical */
            /* compute ypos */
           pp->y=ot->y[j]=(current==&guard)?0:current->y+(current->orient%2?current->w:current->h);
            /* compute xpos */
            maxy=pp->y+(pp->orient%2?pp->w:pp->h);
            while (p!=&guard && p->y<maxy ) {
             int curx=p->x+(p->orient%2?p->h:p->w);
              if (curx>maxx) maxx=curx, vp=p;
              if (p->y+(p->orient%2?p->w:p->h)<maxy) q=p->contour_next; /* update contour 1 */
              p=p->contour_next;
            }
            pp->x=ot->x[j]=maxx;
            /* verify changed */
            if (current!=&guard)
            if (current->x>pp->x+(pp->orient%2?pp->h:pp->w) || current->x+(current->orient%2?current->h:current->w)<pp->x) changed=1;
          }
          /* update contour 2 */
          pp->contour_next=q;
          pp->contour_prev=current;
          q->contour_prev=current->contour_next=pp;
          /* link parent */
          if (!vp->ot_child) vp->ot_child=pp;
          else vp->ot_tail->ot_sibling=pp;
          vp->ot_tail=pp;
          /* update current */
          current=pp;
        }
        j=j+1;
      } else { /* back one block */
        current=current->contour_prev;
      }
    }
    codeI=codeJ=0; codeit(ot,&ver[ot->perm[0]]);
  }
  ot->dir=1-ot->dir;
  return changed;
}