home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume18 / treepar / part03 / par.c
Encoding:
C/C++ Source or Header  |  1989-03-12  |  25.5 KB  |  1,229 lines
  1. /* par.c - the actual placement and routine routines
  2.  *
  3.  * 12.Aug.87  jimmc  Initial definition - placement routines
  4.  * 14.Aug.87  jimmc  More placement, routing routines
  5.  *  3.Nov.87  jimmc  Add rowdir
  6.  *  6.Nov.87  jimmc  Use XCALLOC macro
  7.  * 18.Jan.88  jimmc  lint cleanup
  8.  * 27.Jan.88  jimmc  Add feedthrough stuff
  9.  * 29.Feb.88  jimmc  Improve robustness when doing partial place/routes
  10.  */
  11.  
  12. #include <ctype.h>
  13. #include "network.h"
  14. #include "xalloc.h"
  15.  
  16. #define SPLITCHAR '#'
  17.  
  18. extern Nnet *NFindNet(), *NCreateNet();
  19. extern Nbox *NFindBox(), *NCreateBox();
  20. extern Nconn *NCreateConn();
  21. extern NIFreeConn();
  22. extern NClearNetConns(), NClearBoxConns();
  23. extern NLinkConnNet();
  24.  
  25. extern char *index();
  26. extern char *strsav();
  27.  
  28. extern Nbase *NCurBase;
  29. extern char Tflag[];
  30.  
  31. #define HROW (NCurBase->rowdir=='H')
  32. #define vX cc[HROW?0:1]
  33. #define vY cc[HROW?1:0]
  34. /* if rows are horizontal, vX is X and vY is Y */
  35. #define NorE (HROW?N:E)
  36. #define SorW (HROW?S:W)
  37. #define NorEstr (HROW?"N":"E")
  38. #define SorWstr (HROW?"S":"W")
  39.  
  40. extern int NPosConn();
  41. extern Nbox *NFindBox();
  42.  
  43. static
  44. RUnmarkBox(box)
  45. Nbox *box;
  46. {
  47.     box->parflags = 0;
  48. }
  49.  
  50. int
  51. RIsFeedBox(box)
  52. Nbox *box;
  53. {
  54.     if (index(box->name,SPLITCHAR)) return 1;
  55.     return 0;
  56. }
  57.  
  58. static
  59. RUnSplitBox(box)
  60. Nbox *box;
  61. {
  62. extern int NUnLinkConnNet();
  63.  
  64.     if (!index(box->name,SPLITCHAR)) return;
  65.     NDoGroup(&(box->connlist),NUnLinkConnNet);
  66.     NFreeGroup(&(box->connlist),NIFreeConn);
  67. }
  68.  
  69. static
  70. RFreeSplitBox(box)
  71. Nbox *box;
  72. {
  73.     if (!index(box->name,SPLITCHAR)) return;
  74.     NIFreeBox(box);
  75. }
  76.  
  77. static
  78. RSelBox(box,rownum)
  79. Nbox *box;
  80. {
  81. int i;
  82.  
  83.     if (box->parflags & ROWSET) return;
  84.     box->rownum = rownum;
  85.     box->parflags |= ROWSET;
  86.     for (i=0; i<box->connlist.count; i++) {
  87.         RSelBConn(box->connlist.d.conn[i],rownum);
  88.     }
  89. }
  90.  
  91. static
  92. RSelectBox(box)        /* set the row number in a box */
  93. Nbox *box;
  94. {
  95.     RSelBox(box,0);        /* place this box in row 0 */
  96. }
  97.  
  98. static
  99. RUnsetrowBox(box)
  100. Nbox *box;
  101. {
  102.     box->row = 0;
  103. }
  104.  
  105. static
  106. RSetrowBox(box)        /* set a box into a row */
  107. Nbox *box;
  108. {
  109. Nrow *row, *RFindRow();
  110.  
  111.     if (box->row) return;    /* nop if already set */
  112.     row = RFindRow(NCurBase,box->rownum);
  113.     if (!row) {
  114.         printf("Can't find row %d for box %s\n",
  115.             box->rownum, box->name);
  116.         return;
  117.     }
  118.     box->row = row;
  119.     insertp(&(row->boxlist),(char *)box);
  120. }
  121.  
  122. static
  123. RSetrposBox(box)
  124. Nbox *box;
  125. {
  126.     if (!box->row) return;
  127.     box->origin.vY = box->row->pos;
  128. }
  129.  
  130. static
  131. RClearOrderBox(box)
  132. Nbox *box;
  133. {
  134.     box->parflags &= ~ORDERSET;
  135. }
  136.  
  137. static
  138. ROrderCBox(box,side,negdir)
  139. Nbox *box;
  140. int side;
  141. int negdir;
  142. {
  143. Ngroup clist;
  144. int i,j;
  145. Nnet *net;
  146. Nconn *cp;
  147. int RCmpConn();
  148.  
  149.     NClearGroup(&clist);
  150.     for (i=0; i<box->connlist.count; i++) {
  151.         /* collect all conns on the side of interest */
  152.         cp = box->connlist.d.conn[i];
  153.         if (cp->side==side && cp->net && cp->net->connlist.count>1) {
  154.             insertp(&clist,(char *)cp);
  155.         }
  156.     }
  157.     if (clist.count==0) return;
  158.     qsort((char *)clist.d.conn,clist.count,
  159.         sizeof(clist.d.conn[0]),RCmpConn);
  160.     for (i=0; i<clist.count; i++) {        /* see if any nets set yet */
  161.         net = clist.d.conn[i]->net;
  162.         if (net->parflags & ORDERSET) break;
  163.     }
  164.     if (i>=clist.count) {        /* no nets set yet */
  165.         if (negdir) i=clist.count;
  166.         else i=0;
  167.     }
  168.     for (j=i; j<clist.count; j++) {        /* count up from i */
  169.         ROrderNet(clist.d.conn[j]->net,0);
  170.     }
  171.     for (j=i-1; j>=0; j--) {        /* count down from i */
  172.         ROrderNet(clist.d.conn[j]->net,1);
  173.     }
  174.     if (clist.d.x) tfree((char *)clist.d.x);
  175. }
  176.  
  177. static
  178. ROrderBox(box,negdir)    /* sets orders in neighboring boxes */
  179. Nbox *box;
  180. int negdir;        /* if set, expand in negative direction */
  181. {
  182.     if (box->parflags & ORDERSET) return;
  183.     box->parflags |= ORDERSET;
  184.     if (negdir)
  185.         box->rowpos = --(box->row->rowposmin);
  186.     else
  187.         box->rowpos = (box->row->rowposmax)++;
  188.     ROrderCBox(box,NorE,negdir);    /* order the north or east boxes */
  189.     ROrderCBox(box,SorW,negdir);    /* order the south or west boxes */
  190. }
  191.  
  192. static int
  193. RCmpBox(b1,b2)
  194. Nbox **b1, **b2;
  195. {
  196.     return (*b1)->rowpos - (*b2)->rowpos;
  197. }
  198.  
  199. static
  200. RNetForceBox(box,side,pnforce,pncount)
  201. Nbox *box;
  202. int side;    /* use only connectors on this side */
  203. int *pnforce;    /* return value - total net force */
  204. int *pncount;    /* return value - count of nets */
  205. {
  206. Ngroup clist;
  207. int i;
  208. int nforce, ncount;
  209. int sumnforce, sumncount;
  210. Nconn *cp, *conn;
  211. Nnet *net;
  212.  
  213.     NClearGroup(&clist);
  214.     for (i=0; i<box->connlist.count; i++) {
  215.         /* collect all conns on the side of interest */
  216.         cp = box->connlist.d.conn[i];
  217.         if (cp->side==side && cp->net && cp->net->connlist.count>1) {
  218.             insertp(&clist,(char *)cp);
  219.         }
  220.     }
  221.     sumnforce = 0;
  222.     sumncount = 0;
  223.     for (i=0; i<clist.count; i++) {
  224.         conn = clist.d.conn[i];
  225.         net = conn->net;
  226.         RNetForceNet(net,conn,&nforce,&ncount);
  227.         sumnforce += nforce;
  228.         sumncount += ncount;
  229.     }
  230.     if (clist.d.x) tfree((char *)clist.d.x);
  231.     *pnforce = sumnforce;
  232.     *pncount = sumncount;
  233. }
  234.  
  235. static
  236. RUnmarkNet(net)
  237. Nnet *net;
  238. {
  239.     net->parflags = 0;        /* clear flag bits */
  240. }
  241.  
  242. static
  243. RSelNet(net,rownum)
  244. Nnet *net;
  245. int rownum;
  246. {
  247. int i;
  248.  
  249.     if (net->parflags & ROWSET) return;
  250.     net->rownum = rownum;
  251.     net->parflags |= ROWSET;
  252.     for (i=0; i<net->connlist.count; i++) {
  253.         RSelNConn(net->connlist.d.conn[i],rownum);
  254.     }
  255. }
  256.  
  257. static
  258. RUnsetrowNet(net)
  259. Nnet *net;
  260. {
  261.     net->row = 0;
  262. }
  263.  
  264. static
  265. RSetrowNet(net)        /* set a net into a row */
  266. Nnet *net;
  267. {
  268. Nrow *row, *RFindRow();
  269.  
  270.     if (net->row) return;    /* nop if already set */
  271.     row = RFindRow(NCurBase,net->rownum);
  272.     if (!row) {
  273.         printf("Can't find row %d for net %s\n",
  274.             net->rownum, net->name);
  275.         return;
  276.     }
  277.     net->row = row;
  278.     insertp(&(row->netlist),(char *)net);
  279. }
  280.  
  281. static
  282. RUnSplitNet(net)
  283. Nnet *net;
  284. {
  285. char *splitp;
  286. extern int RUnSplitConn();
  287.  
  288.     splitp = index(net->name,SPLITCHAR);
  289.     if (!splitp) return;        /* not a split net */
  290.     /* OK, it's one of ours, undo it */
  291.     NDoGroup(&(net->connlist),RUnSplitConn);
  292.     if (net->connlist.count!=0)
  293.         fatalerr("net count!=0 for net %s", net->name);
  294. }
  295.  
  296. static
  297. RFreeSplitNet(net)
  298. Nnet *net;
  299. {
  300.     if (!index(net->name,SPLITCHAR)) return;
  301.     NIFreeNet(net);
  302. }
  303.  
  304. static
  305. RSplitNet(net)
  306. Nnet *net;
  307. {
  308. Nconn *conn;
  309. int cboxrow;
  310. int connside, connrow;
  311. int i;
  312. int minrow,maxrow;
  313. char namebuf[516];
  314. char *namebufcpy;
  315. Nnet *newnet;
  316. char *thisname, *lastname;
  317. Nbox *newbox;
  318. Nconn *newconn;
  319.  
  320.     minrow=maxrow=0;
  321.     for (i=0; i<net->connlist.count; i++) {
  322.         conn = net->connlist.d.conn[i];
  323.         connside = conn->side;    /* NSEW */
  324.         cboxrow = conn->box->rownum;
  325.         connrow = cboxrow+((connside==N||connside==E)?1:-1);
  326.         if (i==0 || connrow<minrow) minrow=connrow;
  327.         if (i==0 || connrow>maxrow) maxrow=connrow;
  328.     }
  329.     if (minrow==maxrow) return;    /* all in one channel */
  330.     lastname = "";
  331.     for (i=minrow; i<=maxrow; i+=2) {
  332.         namebufcpy = 0;
  333.         sprintf(namebuf,"%s%c%s%d",net->name,SPLITCHAR,
  334.             ((i<0)?"m":""),((i<0)?-i:i));
  335.         newnet = NFindNet(NCurBase,namebuf);
  336.         if (!newnet) {
  337.             newnet = NCreateNet(strsav(namebuf),i);
  338.         }
  339.         thisname = newnet->name;
  340.         if (i>minrow) {
  341.             newbox = NFindBox(NCurBase,thisname);
  342.             if (newbox) {
  343.                 newbox->rownum = i-1;
  344.             } else {
  345.                 newbox = NCreateBox(strsav(namebuf),0,0,0,0,
  346.                     "",0,0,"",i-1,0);
  347.             }
  348.             newbox->parflags |= ROWSET;
  349.             NFreeGroup(&(newbox->connlist),NIFreeConn);
  350.             newconn = NCreateConn(strsav(newbox->name),
  351.                 strsav(thisname),
  352.                 0,0,strsav(NorEstr),strsav(thisname));
  353.             NLinkConnBox(newconn);
  354.             newconn = NCreateConn(strsav(newbox->name),
  355.                 strsav(lastname),
  356.                 0,0,strsav(SorWstr),strsav(lastname));
  357.             NLinkConnBox(newconn);
  358.         }
  359.         lastname = thisname;
  360.     }
  361.     for (i=0; i<net->connlist.count; i++) {
  362.         conn = net->connlist.d.conn[i];
  363.         connside = conn->side;    /* NSEW */
  364.         cboxrow = conn->box->rownum;
  365.         connrow = cboxrow+((connside==N||connside==E)?1:-1);
  366.         sprintf(namebuf,"%s%c%s%d",conn->netname,SPLITCHAR,
  367.             ((connrow<0)?"m":""),((connrow<0)?-connrow:connrow));
  368.         namebufcpy = XALLOC(char,strlen(namebuf)+1);
  369.         strcpy(namebufcpy,namebuf);
  370.         tfree(conn->netname);
  371.         conn->netname = namebufcpy;
  372.     }
  373. }
  374.  
  375. static
  376. RClearOrderNet(net)
  377. Nnet *net;
  378. {
  379.     net->parflags &= ~ORDERSET;
  380. }
  381.  
  382. static
  383. ROrderCNet(net,side,negdir)
  384. Nnet *net;
  385. int side;
  386. int negdir;
  387. {
  388. Ngroup clist;
  389. int i,j;
  390. Nbox *box;
  391. Nconn *cp;
  392.  
  393.     NClearGroup(&clist);
  394.     for (i=0; i<net->connlist.count; i++) {
  395.         /* collect all conns on the side of interest */
  396.         cp = net->connlist.d.conn[i];
  397.         if (cp->side==side && cp->box) {
  398.             insertp(&clist,(char *)cp);
  399.         }
  400.     }
  401.     if (clist.count==0) return;
  402.     qsort((char *)clist.d.conn,clist.count,
  403.         sizeof(clist.d.conn[0]),RCmpConn);
  404.     for (i=0; i<clist.count; i++) {        /* see if any boxes set yet */
  405.         box = clist.d.conn[i]->box;
  406.         if (box->parflags & ORDERSET) break;
  407.     }
  408.     if (i>=clist.count) {        /* no boxes set yet */
  409.         if (negdir) i=clist.count;
  410.         else i=0;
  411.     }
  412.     for (j=i; j<clist.count; j++) {        /* count up from i */
  413.         ROrderBox(clist.d.conn[j]->box,0);
  414.     }
  415.     for (j=i-1; j>=0; j--) {        /* count down from i */
  416.         ROrderBox(clist.d.conn[j]->box,1);
  417.     }
  418.     if (clist.d.x) tfree((char *)clist.d.x);
  419. }
  420.  
  421. static
  422. ROrderNet(net,negdir)    /* sets orders in neighboring boxes */
  423. Nnet *net;
  424. int negdir;        /* if set, expand in negative direction */
  425. {
  426.     if (net->parflags & ORDERSET) return;
  427.     net->parflags |= ORDERSET;
  428.     if (negdir)
  429.         net->rowpos = --(net->row->rowposmin);
  430.     else
  431.         net->rowpos = (net->row->rowposmax)++;
  432.     ROrderCNet(net,SorW,negdir); /* order the boxes to our south or west */
  433.     ROrderCNet(net,NorE,negdir); /* order the boxes to our north or east */
  434. }
  435.  
  436. static
  437. RSpanNet(net)    /* calculate the span for a net */
  438. Nnet *net;
  439. {
  440. int i;
  441. Nconn *conn;
  442. int max,min;
  443.  
  444.     max = min = 0;
  445.     for (i=0; i<net->connlist.count; i++) {
  446.         conn = net->connlist.d.conn[i];
  447.         if (i==0 || conn->apos.vX > max) max=conn->apos.vX;
  448.         if (i==0 || conn->apos.vX < min) min=conn->apos.vX;
  449.     }
  450.     net->maxpos = max;
  451.     net->minpos = min;
  452. }
  453.  
  454. static int
  455. RCmpNet(n1,n2)
  456. Nnet **n1, **n2;
  457. {
  458.     return (*n1)->minpos - (*n2)->minpos;
  459. }
  460.  
  461. static
  462. RNetForceNet(net,orgconn,pnforce,pncount)
  463. Nnet *net;
  464. Nconn *orgconn;    /* the source connector to calculate the force from */
  465. int *pnforce;    /* return value - total net force */
  466. int *pncount;    /* return value - count of net runs */
  467. {
  468. int i;
  469. Nconn *conn;
  470. int orgx;
  471. int nforce;
  472. int ncount;
  473.  
  474.     orgx = orgconn->apos.vX;
  475.     nforce = 0;
  476.     ncount = 0;
  477.     for (i=0; i<net->connlist.count; i++) {
  478.         conn = net->connlist.d.conn[i];
  479.         if (conn==orgconn) continue;
  480.         nforce += conn->apos.vX - orgx;
  481.         ncount++;
  482.     }
  483.     *pnforce = nforce;
  484.     *pncount = ncount;
  485. }
  486.  
  487. static
  488. RSetAngleNet(net)
  489. Nnet *net;
  490. {
  491. int i;
  492. Nconn *conn;
  493. int nconn, sconn, econn, wconn;
  494. int nsum, ssum, esum, wsum;
  495.  
  496.     if (net->connlist.count<=1) return;
  497.     nconn = sconn = econn = wconn = 0;
  498.     nsum = ssum = esum = wsum = 0;
  499.     net->track = 0;
  500.     for (i=0; i<net->connlist.count; i++) {
  501.         conn = net->connlist.d.conn[i];
  502.         switch (conn->side) {
  503.         case N:
  504.             nconn++;
  505.             nsum += conn->apos.X;
  506.             break;
  507.         case S:
  508.             sconn++;
  509.             ssum += conn->apos.X;
  510.             break;
  511.         case E:
  512.             econn++;
  513.             esum += conn->apos.Y;
  514.             break;
  515.         case W:
  516.             wconn++;
  517.             wsum += conn->apos.Y;
  518.             break;
  519.         default: break;
  520.         }
  521.     }
  522.     if      (nconn>sconn) net->angle = 'S';
  523.     else if (sconn>nconn) net->angle = 'N';
  524.     else if (econn>wconn) net->angle = 'W';
  525.     else if (wconn>econn) net->angle = 'E';
  526.     else if (esum>wsum) net->angle = 'L';    /* leans to the left */
  527.     else if (wsum>esum) net->angle = 'R';
  528.     else if (nsum>ssum) net->angle = 'L';
  529.     else if (ssum>nsum) net->angle = 'R';
  530.     else net->angle = 0;
  531. }
  532.  
  533. static
  534. RRouteNet(net)
  535. Nnet *net;
  536. {
  537. int i;
  538. Ntrack *track;
  539. Nconn *c1, *c2, *conn;
  540. int cpos;
  541. int NFreeGroupOnly();
  542.  
  543.     NFreeGroup(&(net->pathlist),NFreeGroupOnly);
  544.     if (net->connlist.count<=1) return;
  545.     track = net->track;
  546.     NSetNet(net);        /* so we can use NCeatePath below */
  547.     cpos = track->pos;
  548.     if (net->connlist.count==2) {    /* common special case */
  549.         c1 = net->connlist.d.conn[0];
  550.         c2 = net->connlist.d.conn[1];
  551.         if (net->minpos==net->maxpos) {        /* no bends! */
  552.             NCreatePath(c1->apos.X,c1->apos.Y);
  553.             NCreatePath(c2->apos.X,c2->apos.Y);
  554.         }
  555.         else {
  556.             NCreatePath(c1->apos.X,c1->apos.Y);
  557.             if (HROW) {
  558.                 NCreatePath(c1->apos.X,cpos);
  559.                 NCreatePath(c2->apos.X,cpos);
  560.             } else {
  561.                 NCreatePath(cpos,c1->apos.Y);
  562.                 NCreatePath(cpos,c2->apos.Y);
  563.             }
  564.             NCreatePath(c2->apos.X,c2->apos.Y);
  565.         }
  566.     }
  567.     else {        /* more than two points */
  568.         if (HROW) {
  569.             NCreate1Path(net->minpos,cpos,net->maxpos,cpos);
  570.             for (i=0; i<net->connlist.count; i++) {
  571.                 conn = net->connlist.d.conn[i];
  572.                 NCreate1Path(conn->apos.X,conn->apos.Y,
  573.                     conn->apos.X,cpos);
  574.             }
  575.         } else {
  576.             NCreate1Path(cpos,net->minpos,cpos,net->maxpos);
  577.             for (i=0; i<net->connlist.count; i++) {
  578.                 conn = net->connlist.d.conn[i];
  579.                 NCreate1Path(conn->apos.X,conn->apos.Y,
  580.                     cpos,conn->apos.Y);
  581.             }
  582.         }
  583.     }
  584. }
  585.  
  586. static
  587. RUnSplitConn(conn)
  588. Nconn *conn;
  589. {
  590. char *nnend;
  591.  
  592.     if (!conn->box)
  593.         NLinkConnBox(conn);
  594.     nnend = index(conn->netname,SPLITCHAR);
  595.     if (!nnend) return;
  596.     if (conn->net)
  597.         removep(&(conn->net->connlist),(char *)conn);
  598.             /* remove from old (split) net */
  599.     *nnend = 0;    /* strip tail off name */
  600.     if (!conn->box) return;
  601.     if (!index(conn->box->name,SPLITCHAR)) {
  602.         NLinkConnNet(conn);    /* relink the net pointer */
  603.     }
  604. }
  605.  
  606. static
  607. RSelBConn(conn,rownum)
  608. Nconn *conn;
  609. int rownum;
  610. {
  611.     if (!conn->net) return;
  612.     switch (conn->side) {
  613.     case E: case N:
  614.         RSelNet(conn->net,rownum+1);
  615.         break;
  616.     case W: case S:
  617.         RSelNet(conn->net,rownum-1);
  618.         break;
  619.     }
  620. }
  621.  
  622. static
  623. RSelNConn(conn,rownum)
  624. Nconn *conn;
  625. int rownum;
  626. {
  627.     if (!conn->box) return;
  628.     switch (conn->side) {
  629.     case E: case N:
  630.         RSelBox(conn->box,rownum-1);
  631.         break;
  632.     case W: case S:
  633.         RSelBox(conn->box,rownum+1);
  634.         break;
  635.     }
  636. }
  637.  
  638. static int
  639. RCmpConn(c1,c2)
  640. Nconn **c1, **c2;
  641. {
  642.     return (*c1)->pos.vX - (*c2)->pos.vX;
  643. }
  644.  
  645. static
  646. Nrow *
  647. RFindRow(base,num)
  648. Nbase *base;
  649. int num;
  650. {
  651. int i;
  652.  
  653.     for (i=0; i<base->rowlist.count; i++) {
  654.         if (base->rowlist.d.row[i]->rownum==num)
  655.             return base->rowlist.d.row[i];
  656.     }
  657.     return 0;
  658. }
  659.  
  660. static
  661. RSetflagRow(row)
  662. Nrow *row;
  663. {
  664.     if (row->boxlist.count)
  665.         row->parflags |= BOXROW;
  666.     else
  667.         row->parflags &= ~BOXROW;
  668. }
  669.  
  670. static int
  671. RSizeRow(row)
  672. Nrow *row;
  673. {
  674. int i;
  675. int smax,s;
  676.  
  677.     if (!(row->parflags & BOXROW)) return 0;    /* not a box row */
  678.     smax=0;
  679.     for (i=0; i<row->boxlist.count; i++) {
  680.         s = row->boxlist.d.box[i]->size.vY;
  681.         if (s>smax) smax=s;
  682.     }
  683.     row->size = smax;
  684.     return smax;
  685. }
  686.  
  687. static
  688. RClearOrderRow(row)
  689. Nrow *row;
  690. {
  691.     row->rowposmin = row->rowposmax = 0;
  692. }
  693.  
  694. static
  695. RSortRow(row)    /* sorts the boxes in a row */
  696. Nrow *row;
  697. {
  698.     if (!(row->parflags & BOXROW)) return;
  699.     qsort((char *)row->boxlist.d.box,row->boxlist.count,
  700.         sizeof(row->boxlist.d.box[0]),RCmpBox);
  701.             /* sort according to rowpos */
  702.     RNormalizeRow(row);
  703. }
  704.  
  705. static
  706. RNormalizeRow(row)
  707. Nrow *row;
  708. {
  709. Nbox *box;
  710. int i,t;
  711.  
  712.     t = 0;
  713.     for (i=0; i<row->boxlist.count; i++) {
  714.         box = row->boxlist.d.box[i];
  715.         box->origin.vX = t;
  716.         t += NCurBase->rowposspace + box->size.vX;
  717.     }
  718.     row->length = t-NCurBase->rowposspace;
  719. }
  720.  
  721. static
  722. RPositionRow(row,side)
  723. Nrow *row;
  724. int side;    /* position based on connectors on this side */
  725. {
  726.     if (!(row->parflags & BOXROW)) return;
  727.     RBalanceRow(row,side);
  728.     RSpreadRow(row,side);
  729. }
  730.  
  731. static
  732. RBalanceRow(row,side)    /* moves the row as a unit to a balanced position */
  733. Nrow *row;
  734. int side;    /* position based on connectors on this side */
  735. {
  736. int i;
  737. Nbox *box;
  738. int nforce, ncount;
  739. int sumnforce, sumncount;
  740. int dist;
  741.  
  742.     sumnforce = 0;
  743.     sumncount = 0;
  744.     for (i=0; i<row->boxlist.count; i++) {
  745.         box = row->boxlist.d.box[i];
  746.         RNetForceBox(box,side,&nforce,&ncount);
  747.         sumnforce += nforce;
  748.         sumncount += ncount;
  749.     }
  750.     if (sumncount==0) return;
  751.     dist = sumnforce/sumncount;
  752.     if (dist<0) return;
  753.     if (dist + row->length > NCurBase->maxrowlength)
  754.         dist = NCurBase->maxrowlength - row->length;
  755.     for (i=0; i<row->boxlist.count; i++) {
  756.         box = row->boxlist.d.box[i];
  757.         box->origin.vX += dist;
  758.         NDoGroup(&(box->connlist),NPosConn);
  759.         box->parflags &= ~POSITIONSET;
  760.     }
  761. }
  762.  
  763. static
  764. RSpreadRow(row,side)
  765. Nrow *row;
  766. int side;    /* position based on connectors on this side */
  767. {
  768. int i;
  769. Nbox *box;
  770. int floor, ceil;
  771. int nforce, ncount;
  772. int dist;
  773. int j;
  774. Nbox *boxj;
  775. int tfloor;
  776.  
  777.     floor = 0;
  778.     for (i=0; i<row->boxlist.count; i++) {
  779.         box = row->boxlist.d.box[i];
  780.         RNetForceBox(box,side,&nforce,&ncount);
  781.         if (ncount==0) {
  782.             floor += box->size.vX + NCurBase->rowposspace;
  783.                 /* raise floor, but place this box later */
  784.             continue;
  785.         }
  786.         dist = nforce/ncount;
  787.         if (dist>=0) break;
  788.         if (box->origin.vX + dist < floor)
  789.             box->origin.vX = floor;
  790.         else
  791.             box->origin.vX += dist;
  792.         NDoGroup(&(box->connlist),NPosConn);
  793.         floor = box->origin.vX + box->size.vX + NCurBase->rowposspace;
  794.         box->parflags |= POSITIONSET;
  795.         tfloor = box->origin.vX;
  796.         for (j=i-1; j>=0; j--) {
  797.             boxj = row->boxlist.d.box[j];
  798.             if (boxj->parflags & POSITIONSET) break;
  799.             tfloor -= boxj->size.vX + NCurBase->rowposspace;
  800.             boxj->origin.vX = tfloor;
  801.             boxj->parflags |= POSITIONSET;
  802.         }
  803.     }
  804.     ceil = NCurBase->maxrowlength;
  805.     for (i=row->boxlist.count-1; i>=0; i--) {
  806.         box = row->boxlist.d.box[i];
  807.         RNetForceBox(box,side,&nforce,&ncount);
  808.         if (ncount==0) {
  809.             ceil -= box->size.vX + NCurBase->rowposspace;
  810.             continue;
  811.         }
  812.         dist = nforce/ncount;
  813.         if (dist<=0) break;
  814.         if (box->origin.vX + box->size.vX + dist > ceil)
  815.             box->origin.vX = ceil - box->size.vX;
  816.         else
  817.             box->origin.vX += dist;
  818.         NDoGroup(&(box->connlist),NPosConn);
  819.         ceil = box->origin.vX - NCurBase->rowposspace;
  820.         box->parflags |= POSITIONSET;
  821.         tfloor = box->origin.vX + box->size.vX + NCurBase->rowposspace;
  822.         for (j=i+1; j<row->boxlist.count; j++) {
  823.             boxj = row->boxlist.d.box[j];
  824.             if (boxj->parflags & POSITIONSET) break;
  825.             boxj->origin.vX = tfloor;
  826.             tfloor += boxj->size.vX + NCurBase->rowposspace;
  827.             boxj->parflags |= POSITIONSET;
  828.         }
  829.     }
  830. }
  831.  
  832. /* track routines */
  833.  
  834. static Ntrack *
  835. RNewTrack(n)
  836. int n;
  837. {
  838. Ntrack *track;
  839.  
  840.     track = XCALLOC(Ntrack,1);
  841.     track->n = n;
  842.     track->netlist.count = track->netlist.alloc = 0;
  843.     track->netlist.d.net = 0;
  844.     return track;
  845. }
  846.  
  847. static
  848. RUseTrack(track,net)
  849. Ntrack *track;
  850. Nnet *net;
  851. {
  852.     track->parflags |= SPANSET;
  853.     insertp(&(track->netlist),(char *)net);
  854. }
  855.  
  856. static int    /* returns angle of the net which is in the way, 0 if open */
  857. RUnAvailTrack(track,min,max)
  858. Ntrack *track;
  859. int min,max;
  860. {
  861. Nnet *net;
  862. int i;
  863.  
  864.     if (!(track->parflags & SPANSET)) return 0;
  865.     for (i=0; i<track->netlist.count; i++) {
  866.         net = track->netlist.d.net[i];
  867.         if (min>=net->maxpos+NCurBase->trackspace) continue;
  868.         if (max<=net->minpos-NCurBase->trackspace) continue;
  869.         return net->angle;    /* this net is in the way */
  870.     }
  871.     return 0;
  872. }
  873.  
  874. static Ntrack *
  875. RFindTrack(row,min,max,netangle)
  876. Nrow *row;
  877. int min,max;
  878. int netangle;
  879. {
  880. int i;
  881. Ntrack *track, *lastavail;
  882. int trackangle;
  883.  
  884. /* find the last row in which the route DOES NOT fit, then return the
  885.  * next row after that! */
  886.     lastavail = 0;
  887.     for (i=row->tracklist.count-1; i>=0; i--) {
  888.         track = row->tracklist.d.track[i];
  889.         trackangle = RUnAvailTrack(track,min,max);
  890.         if (!trackangle)
  891.             lastavail = track;
  892.         else
  893.             if (trackangle==netangle) break;
  894.         /* if angles are different, continue looking */
  895.     }
  896.     if (lastavail) return lastavail;
  897.     return 0;
  898.  
  899. #if 0    /* greedy algorithm - doesn't do quite what we want */
  900.     for (i=0; i<row->tracklist.count; i++) {
  901.         track = row->tracklist.d.track[i];
  902.         if (!(RUnAvailTrack(track,min,max))) return track;
  903.     }
  904.     return 0;
  905. #endif
  906. }
  907.  
  908. static
  909. RClearTrack(track)
  910. Ntrack *track;
  911. {
  912.     NFreeGroupOnly(&(track->netlist));
  913.     track->parflags = 0;
  914. }
  915.  
  916. static
  917. RFreeTrack(track)
  918. Ntrack *track;
  919. {
  920.     NFreeGroupOnly(&(track->netlist));
  921.     tfree((char *)track);
  922. }
  923.  
  924. static
  925. RChanSizeRow(row)    /* calculate required number of tracks */
  926. Nrow *row;
  927. {
  928. int i;
  929. Nnet *net;
  930. Ntrack *track;
  931.  
  932.     if (row->parflags & BOXROW) return;
  933.     NFreeGroup(&(row->tracklist),RFreeTrack);
  934.     NDoGroup(&(row->netlist),RSpanNet);    /* find span of each net */
  935.     qsort((char *)row->netlist.d.net,row->netlist.count,
  936.         sizeof(row->netlist.d.net[0]),RCmpNet);
  937.     NDoGroup(&(row->netlist),RSetAngleNet);
  938.     for (i=row->netlist.count-1; i>=0; i--) {
  939.         net = row->netlist.d.net[i];
  940.         if (net->connlist.count<=1) continue;
  941.         switch (net->angle) {
  942.         case 'W': case 'R': case 'S':
  943.             break;
  944.         default:
  945.             continue;
  946.         }
  947.         track = RFindTrack(row,net->minpos,net->maxpos,net->angle);
  948.              /* see where it can fit */
  949.         if (!track) {        /* have to make a new track */
  950.             track = RNewTrack(row->tracklist.count);
  951.             insertp(&(row->tracklist),(char *)track);
  952.         }
  953.         net->track = track;
  954.         RUseTrack(track,net);
  955.     }
  956.     for (i=0; i<row->netlist.count; i++) {
  957.         net = row->netlist.d.net[i];
  958.         if (net->track || net->connlist.count<=1) continue;
  959.         track = RFindTrack(row,net->minpos,net->maxpos,net->angle);
  960.              /* see where it can fit */
  961.         if (!track) {        /* have to make a new track */
  962.             track = RNewTrack(row->tracklist.count);
  963.             insertp(&(row->tracklist),(char *)track);
  964.         }
  965.         net->track = track;
  966.         RUseTrack(track,net);
  967.     }
  968.     row->size = NCurBase->trackspace * (row->tracklist.count+1);
  969. }
  970.  
  971. static
  972. RRouteRow(row)
  973. Nrow *row;
  974. {
  975. int i;
  976. Ntrack *track;
  977.  
  978.     if (row->parflags & BOXROW) return;
  979.     for (i=0; i<row->tracklist.count; i++) {
  980.         track = row->tracklist.d.track[i];
  981.         track->pos = row->pos + NCurBase->trackspace*(1+i);
  982.     }
  983.     NDoGroup(&(row->tracklist),RClearTrack);    /* clear min/max */
  984.     NDoGroup(&(row->netlist),RRouteNet);    /* route all nets */
  985. }
  986.  
  987. int
  988. RSelect(boxname)    /* select rows for all boxes and nets */
  989. char *boxname;
  990. {
  991. Nbox *box;
  992.  
  993.     if (!NCurBase) {
  994.         printf("no data to place\n");
  995.         return 0;
  996.     }
  997.     NDoGroup(&(NCurBase->boxlist),RUnmarkBox);
  998.     NDoGroup(&(NCurBase->netlist),RUnmarkNet);
  999.  
  1000.     if (boxname) {    /* see if preferred root for placement */
  1001.         box = NFindBox(NCurBase,boxname);
  1002.         if (box) RSelectBox(box);
  1003.     }
  1004.     NDoGroup(&(NCurBase->boxlist),RSelectBox);    /* put in new row */
  1005.  
  1006.     return 1;
  1007. }
  1008.  
  1009. /* UnFeed removes any previously inserted feedthroughs */
  1010. int
  1011. RUnFeed()
  1012. {
  1013.     if (!NCurBase) {
  1014.         printf("no data to place\n");
  1015.         return 0;
  1016.     }
  1017.     NDoGroup(&(NCurBase->boxlist),RUnSplitBox);
  1018.     NRDoGroup(&(NCurBase->boxlist),RFreeSplitBox);
  1019.     NDoGroup(&(NCurBase->netlist),RUnSplitNet);
  1020.     NRDoGroup(&(NCurBase->netlist),RFreeSplitNet);
  1021.     return 1;
  1022. }
  1023.  
  1024. int
  1025. RFeed()        /* make feedthroughs */
  1026. {
  1027.  
  1028.     if (!NCurBase) {
  1029.         printf("no data to place\n");
  1030.         return 0;
  1031.     }
  1032.     NDoGroup(&(NCurBase->netlist),RSplitNet);
  1033.         /* divide nets up when spanning rows */
  1034.     NDoGroup(&(NCurBase->netlist),NClearNetConns);
  1035.     NDoGroup(&(NCurBase->connlist),NLinkConnNet);
  1036.     return 1;
  1037. }
  1038.  
  1039. int
  1040. RReFeed()    /* remove old feedthroughs and insert new */
  1041. {
  1042.     if (!RUnFeed()) return 0;
  1043.     if (!RFeed()) return 0;
  1044.     return 1;
  1045. }
  1046.  
  1047. int
  1048. RSpace()    /* set the spacing for the rows, set one coord in boxes */
  1049. {
  1050. extern int NFreeRow();
  1051. int rowmax=0;
  1052. int rowmin=0;
  1053. int r,rowcount;
  1054. int i;
  1055. int pos;
  1056. Nrow *row;
  1057.  
  1058.     if (!NCurBase) {
  1059.         printf("no data to place\n");
  1060.         return 0;
  1061.     }
  1062.     NSetBase(NCurBase);        /* so we can use NCreateRow */
  1063.     NFreeGroup(&(NCurBase->rowlist),NFreeRow);    /* dump all old rows */
  1064.     NDoGroup(&(NCurBase->boxlist),RUnsetrowBox);
  1065.     NDoGroup(&(NCurBase->netlist),RUnsetrowNet);
  1066.     for (i=0; i<NCurBase->boxlist.count; i++) {
  1067.         r = NCurBase->boxlist.d.box[i]->rownum;
  1068.         if (i==0 || r>rowmax) rowmax=r;
  1069.         if (i==0 || r<rowmin) rowmin=r;
  1070.     }
  1071.     for (i=0; i<NCurBase->netlist.count; i++) {
  1072.         r = NCurBase->netlist.d.net[i]->rownum;
  1073.         if (r>rowmax) rowmax=r;
  1074.         if (r<rowmin) rowmin=r;
  1075.     }
  1076.     rowcount = rowmax-rowmin+1;
  1077.     for (i=0; i<rowcount; i++) {
  1078.         NCreateRow(i+rowmin,0,0);    /* put in new rows */
  1079.     }
  1080.     NDoGroup(&(NCurBase->boxlist),RSetrowBox);
  1081.     NDoGroup(&(NCurBase->netlist),RSetrowNet);
  1082.         /* put all the boxes and nets into their rows */
  1083.     pos = 0;
  1084.     for (i=0; i<NCurBase->rowlist.count; i++) {
  1085.         row = NCurBase->rowlist.d.row[i];
  1086.         row->pos = pos;
  1087.         if (row->boxlist.count)
  1088.             row->parflags |= BOXROW;
  1089.         pos += NCurBase->interrowspace + RSizeRow(row);
  1090.     }
  1091.     NDoGroup(&(NCurBase->boxlist),RSetrposBox);
  1092.     NDoGroup(&(NCurBase->connlist),NPosConn);
  1093.     return 1;
  1094. }
  1095.  
  1096. static
  1097. RSetPtrs()    /* make sure pointers are set up (for incremental p/r) */
  1098. {
  1099.     /* make sure box and net pointers to row are in */
  1100.     NDoGroup(&(NCurBase->boxlist),RSetrowBox);
  1101.     NDoGroup(&(NCurBase->netlist),RSetrowNet);
  1102.     NDoGroup(&(NCurBase->rowlist),RSetflagRow);
  1103. }
  1104.  
  1105. int
  1106. ROrder(boxname)    /* order the boxes in each row */
  1107. char *boxname;
  1108. {
  1109. int i;
  1110. Nbox *box;
  1111.  
  1112.     if (!NCurBase) {
  1113.         printf("no data to place\n");
  1114.         return 0;
  1115.     }
  1116.  
  1117.     RSetPtrs();
  1118.  
  1119.     /* now start the ordering within each row */
  1120.     NDoGroup(&(NCurBase->boxlist),RClearOrderBox);
  1121.     NDoGroup(&(NCurBase->netlist),RClearOrderNet);
  1122.     NDoGroup(&(NCurBase->rowlist),RClearOrderRow);
  1123.         /* clear out any previous ordering info */
  1124.  
  1125.     if (boxname) {    /* see if preferred root for placement */
  1126.         box = NFindBox(NCurBase,boxname);
  1127.         if (box) ROrderBox(box,0);
  1128.     }
  1129.     for (i=0; i<NCurBase->boxlist.count; i++) {
  1130.         ROrderBox(NCurBase->boxlist.d.box[i],0);
  1131.     }
  1132.     NDoGroup(&(NCurBase->rowlist),RSortRow);
  1133.     NDoGroup(&(NCurBase->connlist),NPosConn);
  1134.     return 1;
  1135. }
  1136.  
  1137. int
  1138. RPosition()    /* position the boxes within each row */
  1139. {
  1140. int i;
  1141. Nrow *row;
  1142. int maxlength;
  1143. int rowi;
  1144.  
  1145.     if (!NCurBase) {
  1146.         printf("no data to place\n");
  1147.         return 0;
  1148.     }
  1149.  
  1150.     RSetPtrs();
  1151.  
  1152.     NDoGroup(&(NCurBase->rowlist),RNormalizeRow);
  1153.     maxlength = -1;
  1154.     for (i=0; i<NCurBase->rowlist.count; i++) {
  1155.         row = NCurBase->rowlist.d.row[i];
  1156.         if (!(row->parflags & BOXROW)) continue;
  1157.         if (row->length > maxlength) {
  1158.             maxlength = row->length;
  1159.             rowi = i;
  1160.         }
  1161.     }
  1162.     NCurBase->maxrowlength = maxlength;
  1163.     for (i=rowi-1; i>=0; i--) {
  1164.         RPositionRow(NCurBase->rowlist.d.row[i],NorE);
  1165.     }
  1166.     for (i=rowi+1; i<NCurBase->rowlist.count; i++) {
  1167.         RPositionRow(NCurBase->rowlist.d.row[i],SorW);
  1168.     }
  1169.     return 1;
  1170. }
  1171.  
  1172. int
  1173. RRoute()    /* do the channel route */
  1174. {
  1175. int i;
  1176. int t;
  1177. Nrow *row;
  1178.  
  1179.     if (!NCurBase) {
  1180.         printf("no data to place\n");
  1181.         return 0;
  1182.     }
  1183.  
  1184.     RSetPtrs();
  1185.  
  1186.     NDoGroup(&(NCurBase->connlist),NPosConn);
  1187.     NDoGroup(&(NCurBase->rowlist),RChanSizeRow);
  1188.         /* calculate the channel size for each row */
  1189.     t = 0;
  1190.     for (i=0; i<NCurBase->rowlist.count; i++) {
  1191.         row = NCurBase->rowlist.d.row[i];
  1192.         row->pos = t;
  1193.         t += row->size;
  1194.     }
  1195.     NDoGroup(&(NCurBase->boxlist),RSetrposBox);
  1196.     NDoGroup(&(NCurBase->connlist),NPosConn);
  1197.     NDoGroup(&(NCurBase->rowlist),RRouteRow);
  1198.         /* do the actual channel routing */
  1199.     return 1;
  1200. }
  1201.  
  1202. RSpacepar(boxname)    /* RSpace and the rest */
  1203. char *boxname;
  1204. {
  1205.     if (!RSpace()) return 0;
  1206.     if (!ROrder(boxname)) return 0;
  1207.     if (!RPosition()) return 0;
  1208.     if (!RRoute()) return 0;
  1209.     return 1;
  1210. }
  1211.  
  1212. RReFeedpar(boxname)    /* RFeed and the rest */
  1213. char *boxname;
  1214. {
  1215.     if (!RReFeed()) return 0;
  1216.     if (!RSpacepar(boxname)) return 0;
  1217.     return 1;
  1218. }
  1219.  
  1220. Rpar(boxname)        /* do it all */
  1221. char *boxname;
  1222. {
  1223.     if (!RSelect(boxname)) return 0;
  1224.     if (!RReFeedpar(boxname)) return 0;
  1225.     return 1;
  1226. }
  1227.  
  1228. /* end */
  1229.