asg/terminals.c

   1 /************************************************************
   2 **
   3 **       COPYRIGHT (C) 1993 UNIVERSITY OF PITTSBURGH
   4 **       COPYRIGHT (C) 1996 GANNON UNIVERSITY
   5 **                  ALL RIGHTS RESERVED
   6 **
   7 **        This software is distributed on an as-is basis
   8 **        with no warranty implied or intended.  No author
   9 **        or distributor takes responsibility to anyone
  10 **        regarding its use of or suitability.
  11 **
  12 **        The software may be distributed and modified
  13 **        freely for academic and other non-commercial
  14 **        use but may NOT be utilized or included in whole
  15 **        or part within any commercial product.
  16 **
  17 **        This copyright notice must remain on all copies
  18 **        and modified versions of this software.
  19 **
  20 ************************************************************/
  21
  22
  23 /* file terminals.c */
  24 /* ------------------------------------------------------------------------
  25  * Terminal Placement routines                         stf 1/91
  26  * Implemented as part of the incremental routing solution for SPAR
  27  * MS Thesis work, UPittsburgh School of Engineering.
  28  * ------------------------------------------------------------------------
  29  */
  30 #include "terminals.h"  /* The conn structures, used to link modules to net fragments */
  31 #include "psfigs.h"
  32
  33 /*---------------------------------------------------------------
  34  * Forward Declarations
  35  *---------------------------------------------------------------
  36  */
  37
  38 static int startX, endX;        /* globals , of sorts */
  39 /*===================================================================================*/
  40 int srange_width(sr)
  41     srange *sr;
  42 {
  43     return(sr->q2 - sr->q1);
  44 }
  45 /*===================================================================================*/
  46 int spans_range_p(t)
  47     tile *t;
  48 {
  49     /* Return TRUE if the given tile spans the x-range specified by the variables
  50        <startX> and <endX>, and has an empty arc (no module contained). */
  51
  52     if ((t->x_pos <= startX) &&
  53         (t->x_pos + t->x_len >= endX) &&
  54         (emptyp_for_arcs(t) == TRUE))           return(TRUE);
  55     else                                        return (FALSE);
  56 }
  57 /*===================================================================================*/
  58 connect *create_connect(m, sr, crl)
  59     module *m;
  60     srange *sr;
  61     crnlist *crl;
  62 {
  63     term *t = m->terms->this;
  64
  65     connect *cn = (connect *)calloc(1, sizeof(connect));
  66     cn->exit = sr;                                      /* Fill in later */
  67     cn->up = m->y_size - t->y_pos;
  68     cn->down = t->y_pos;
  69     cn->mod = m;
  70     cn->corners = crl;
  71
  72     return(cn);
  73 }
  74 /*===================================================================================*/
  75 int spans_overlapped_p(s1, s2)
  76     connect *s1, *s2;
  77 {
  78     /* Returns TRUE if the two spans overlapp in the least. */
  79     srange *r1 = s1->exit, *r2 = s2->exit;
  80     if ((r1->q2 + s1->up >= r2->q1 - s2->down) &&
  81          (r1->q1 - s1->down <= r2->q1 + s2->up))  return(TRUE);
  82     else return(FALSE);
  83 }
  84 /*------------------------------------------------------------------------------------*/
  85 paint_corners(m)
  86     module *m;
  87 {
  88     /* Paint all of the corners that are fixed in the y dimension to terminals to
  89        be painted with the terminal to whom they are fixed. */
  90     term *t;
  91     crnlist *cl, *cll;
  92     range *fixedRange;
  93     net *n;
  94
  95     n = m->terms->this->nt;
  96     for(cl = (crnlist *)n->route; cl != NULL; cl = cl->next)
  97     {
  98         if (cl->this->t != NULL)
  99         {
 100             t = cl->this->t;
 101             fixedRange = cl->this->cy;
 102             for (cll = (crnlist *)n->route; cll != NULL; cll = cll->next)
 103             {
 104                 if (cll->this->cy == fixedRange) cll->this->t = t;
 105             }
 106         }
 107     }
 108 }
 109 /*------------------------------------------------------------------------------------*/
 110 int terminal_point_to_save(sr, corners)
 111     srange *sr;
 112     crnlist *corners;
 113 {
 114     crnlist *cl;
 115     int cy = TILE_SPACE_Y_POS;                          /* big negative number */
 116
 117     for (cl = corners; cl != NULL; cl = cl->next)
 118     {
 119         if (cl->this->t != NULL)
 120         {
 121             sr->orient = cl->this->cy->sr->orient;
 122             if ((overlapped_p(cl->this->cy->sr, sr) == TRUE) &&
 123                 (cl->this->cy->sr->q1 > cy))
 124             {
 125                 cy = cl->this->cy->sr->q1;      /* Get the highest corner in the range */
 126             }
 127         }
 128     }
 129     return(cy);
 130 }
 131 /*------------------------------------------------------------------------------------*/
 132 int insert_gap_between_sranges(sr1, sr2, gap, crl1, crl2)
 133     srange *sr1, *sr2;          /* sranges associated with each net that overlap */
 134     int gap;                    /* How much of a gap goes between the two */
 135     crnlist *crl1, *crl2;       /* The corners that produced these ranges */
 136 {
 137     /* This puts <sr1> to the right of (above) <sr2> by <gap> */
 138     int midPoint, c1, c2, c;
 139     int min1 = sr1->q1, min2 = sr2->q1;
 140     int max1 = sr1->q2, max2 = sr2->q2;
 141
 142     if (min2 == max2) /* Handle the point cases - these are the most common */
 143     {
 144         if (min1 >= min2 + gap) return(TRUE);           /* <sr2> to right of <sr1> */
 145         else if (max1 <= min2 - gap) return(TRUE);      /* <sr1> to right of <sr2> */
 146         else if (min1 <= min2 - gap)                /* fit <sr1> to right of <sr2> */
 147         {
 148             sr1->q2 = min2 - gap;
 149             return(TRUE);
 150         }
 151         else if (max1 >= max2 + gap)                 /* fit <sr1> to left of <sr2> */
 152         {
 153             sr1->q1 = max2 + gap;
 154             return(TRUE);
 155         }
 156         else  return(FALSE);                            /* <sr1> doesn't fit!!! */
 157     }
 158
 159     if (min1 == max1) /* Handle the point cases - these are the most common */
 160     {
 161         if (min2 >= min1 + gap) return(TRUE);           /* <sr1> to right of <sr2> */
 162         else if (max2 <= min1 - gap) return(TRUE);      /* <sr2> to right of <sr1> */
 163         else if (min2 <= min1 - gap)                /* fit <sr2> to right of <sr1> */
 164         {
 165             sr2->q2 = min1 - gap;
 166             return(TRUE);
 167         }
 168         else if (max2 >= max1 + gap)                 /* fit <sr2> to left of <sr1> */
 169         {
 170             sr2->q1 = max1 + gap;
 171             return(TRUE);
 172         }
 173         else  return(FALSE);                            /* <sr1> doesn't fit!!! */
 174     }
 175     else
 176     {
 177         /* Is there any overlap? */
 178         if ((max1 + gap < min2) || (max2 + gap < min1)) return(TRUE);  /* Fits already */
 179         else if (min2 + max1 < gap + 2) return(FALSE);                 /* Can't fit */
 180
 181         midPoint = (max2 + min1) / 2;
 182
 183         /* Set the beginning/end points of the sranges: */
 184         if (max1 < midPoint) min1 = sr1->q1 = sr1->q2 = min1;
 185         else if (min2 > midPoint) max2 = sr2->q1 = sr2->q2 = min2;
 186
 187         else if ( (midPoint >= min2) || ((max1 - min1) >= (max2 - min2)) )
 188         {       /* <sr1> goes to the right of <sr2> */
 189             sr1->q1 = MIN(MAX(min1, midPoint), max1);
 190             sr2->q2 = MAX(MIN(midPoint, max2), min2);
 191         }
 192         else
 193         {   /* <sr2> goes to the right of <sr1> */
 194             sr2->q1 = MIN(MAX(min1, midPoint), max2);
 195             sr1->q2 = MAX(MIN(midPoint, max2), min1);
 196         }
 197         /* now figure out how to fit the <gap> in: (It should fit) */
 198         min1 = sr1->q1;         min2 = sr2->q1;
 199         max1 = sr1->q2;         max2 = sr2->q2;
 200
 201         c1 = terminal_point_to_save(sr1, crl1); /* maintain corners whenever possible */
 202         c2 = terminal_point_to_save(sr2, crl2);
 203
 204         if (((c1 == TILE_SPACE_Y_POS) && (c2 == TILE_SPACE_Y_POS)) ||
 205             ((c1 != TILE_SPACE_Y_POS) && (c2 != TILE_SPACE_Y_POS) &&
 206              (MAX(c1, c2) - MIN(c1, c2) <= gap)) )
 207         {
 208             /* Ignore corner inclusion: */
 209             /* put <sr1> to left of <sr2> with the gap midway between them */
 210             if (min1 <= min2)
 211             {
 212                 if ((min1 <= midPoint - gap/2) && (max2 >= midPoint + gap/2))
 213                 {
 214                     sr1->q2 = midPoint - gap/2;
 215                     sr2->q1 = midPoint + gap/2;
 216                 }
 217                 else if (max2 >= min2 + gap)    sr2->q1 += gap;   /* clip 2 */
 218                 else if (min1 <= max1 - gap)    sr1->q2 -= gap;   /* clip 1 */
 219                 else
 220                 {
 221                     gap -= (max2 - min2);
 222                     sr2->q1 = max2;
 223                     sr1->q2 -= gap;
 224                 }
 225                 return(TRUE);
 226             }
 227             else  /* put <sr2> to left of <sr1> with the gap midway between them */
 228             {
 229                 if (min1 >= midPoint - gap/2)
 230                 {
 231                     sr2->q2 = midPoint - gap/2;
 232                     sr1->q1 = midPoint + gap/2;
 233                 }
 234                 else if (min2 <= max2 - gap)    sr2->q2 -= gap;   /* clip 2 */
 235                 else if (max1 >= min1 + gap)    sr1->q1 += gap;   /* clip 1 */
 236                 else /* Stuff it */
 237                 {
 238                     sr2->q1 = max2 - (max2 - gap - min1)/2;
 239                     sr1->q2 = min1 + (max2 - gap - min1)/2;
 240                 }
 241                 return(TRUE);
 242             }
 243         }
 244         else if ((c1 != TILE_SPACE_Y_POS) && (c2 != TILE_SPACE_Y_POS))
 245         {
 246             /* Deal with both corners */
 247             /* put <sr1> to left of <sr2> with the gap midway between them */
 248             if ((min1 <= midPoint - gap/2) && (max2 >= midPoint + gap/2))
 249
 250             {
 251                 if ((c1 <= midPoint - gap/2) && (c2 >= midPoint + gap/2))
 252                 {
 253                     sr1->q2 = midPoint - gap/2;
 254                     sr2->q1 = midPoint + gap/2;
 255                 }
 256                 else return(FALSE);
 257             }
 258             /* put <sr2> to left of <sr1> with the gap midway between them */
 259             else if (min1 >= midPoint - gap/2)  /* Can't trim sr1 */
 260             {
 261                 if (c2 - gap >= max1)    sr2->q1 = sr2->q2 = c2;
 262
 263                 else if ((c1 <= min1 + (max2 - min1 - gap)/2) &&
 264                     ((c2 >= max2 - (max2 - min1 - gap)/2)))
 265                 {
 266                     sr1->q2 = min1 + (max2 - min1 - gap)/2;
 267                     sr2->q1 = max2 - (max2 - min1 - gap)/2;
 268                 }
 269                 else return(FALSE);
 270             }
 271             else if (max2 <= midPoint + gap/2)  /* Can't trim sr2 */
 272             {
 273                 if (c1 + gap <= min2) sr1->q1 = sr1->q2 = c1;
 274
 275                 else return(FALSE);
 276             }
 277
 278             /* See if they both work: */
 279             else if ((c1 < c2) && (c1 + gap <= c2))
 280             {
 281                 sr1->q1 = sr1->q2 = c1;
 282                 sr1->q2 = sr1->q2 = c2;
 283             }
 284
 285             else return(FALSE);
 286
 287             return(TRUE);
 288         }
 289         else    /* deal with one corner or less */
 290         {
 291             if ((c1 != TILE_SPACE_Y_POS) && (c1 - gap > min2))
 292             {   /* Put <sr1> to the right of <sr2>, fixing <sr1> at point <c1>: */
 293                 sr1->q1 = sr1->q2 = c1;
 294                 sr2->q2 = MAX(min2, MIN(c1 - gap, max2));
 295             }
 296             else if ((c2 != TILE_SPACE_Y_POS) && (c2 - gap < max1))
 297             {   /* put <sr1> to the right of <sr2>, fixing <sr2> at point <c2>: */
 298                 sr2->q1 = sr2->q2 = c2;
 299                 sr1->q1 = MIN(max1, MAX(c2 + gap, min1));
 300             }
 301
 302             /* Bag it */
 303             /* put <sr1> to left of <sr2> with the gap midway between them */
 304             else if ((min1 <= midPoint - gap/2) && (max2 >= midPoint + gap/2))
 305             {
 306                 sr1->q2 = midPoint - gap/2;
 307                 sr2->q1 = midPoint + gap/2;
 308             }
 309             /* put <sr2> to left of <sr1> with the gap midway between them */
 310             else if (min1 >= midPoint - gap/2)
 311             {
 312                 sr1->q2 = midPoint + gap/2;
 313                 sr2->q1 = midPoint - gap/2;
 314             }
 315             else /* Stuff it */
 316             {
 317                 sr2->q1 = max2 - (max2 - gap - min1)/2;
 318                 sr1->q1 = min1 + (max2 - gap - min1)/2;
 319             }
 320             return(TRUE);
 321         }
 322     }
 323 }
 324 /*===================================================================================*/
 325 int separate_spans(s1, s2)
 326     connect *s1, *s2;
 327 {
 328     /* return TRUE and modify the two spans if some legal selections of <s1>->exit
 329        and <s2>->exit can be chosen so as to avoid overlap between the two:
 330      */
 331     srange *r1 = s1->exit, *r2 = s2->exit;
 332
 333     if (((r1->q2 + s1->up > r2->q1 - s2->down) &&
 334          (r1->q1 - s1->down < r2->q1 + s2->up)) ||
 335         ((r1->q2 + s1->up < r2->q1 - s2->down) &&
 336          (r1->q1 - s1->down > r2->q1 + s2->up)))
 337
 338     {
 339         if ((r1->q1 < r2->q1) ||                         /* Put <r1> below <r2> */
 340             ((r1->q1 == r2->q1) && (r1->q2 < r2->q2)))
 341         {
 342             if (srange_width(r1) == 0)
 343             {
 344                 if (r2->q2 >= r1->q2 + s1->up + s2->down)       /* Close shave */
 345                 {
 346                     r2->q1 = r1->q2 + s1->up;
 347                 }
 348                 else return(FALSE);     /* No Go */
 349             }
 350             else if (r1->q1 + r2->q2 <= s1->up + s2->down + 2)
 351             {
 352                 return(FALSE);          /* No Go */
 353             }
 354             else /* Normal Case */
 355             {
 356                 return(insert_gap_between_sranges(r2, r1, s2->up + s1->down,
 357                                                   s1->corners, s2->corners));
 358             }
 359         }
 360         else                    /* Put <r2> below <r1> */
 361         {
 362             if (srange_width(r1) == 0)
 363             {
 364                 if (r1->q2 >= r2->q2 + s2->up + s1->down)       /* Close shave */
 365                 {
 366                     r1->q1 = r2->q2 + s2->up;
 367                 }
 368                 else
 369                 {
 370                     return(FALSE);      /* No Go */
 371                 }
 372             }
 373             else if (r2->q1 + r1->q2 <= s2->up + s1->down + 2)
 374             {
 375                 return(FALSE);          /* No Go */
 376             }
 377             else
 378             {
 379                 return(insert_gap_between_sranges(r1, r2, s1->up + s2->down,
 380                                                   s1->corners, s2->corners));
 381             }
 382         }
 383
 384         if((srange_width(r2) < 0) || (srange_width(r1) < 0))
 385         {
 386             return(FALSE);                      /* Somethin's screwed */
 387         }
 388         else return(TRUE);      /* No overlap problems. */
 389     }
 390     else return(TRUE);  /* No overlap problems. */
 391 }
 392 /*===================================================================================*/
 393 int descending_order(sp1, sp2)
 394     connect *sp1, *sp2;
 395 {
 396     /* Return TRUE iff sp1 is less than sp2 */
 397     if (sp1->exit->q2 <= sp2->exit->q1) return(TRUE);
 398     else return(FALSE);
 399 }
 400 /*===================================================================================*/
 401 int ascending_order(sp1, sp2)
 402     connect *sp1, *sp2;
 403 {
 404     /* Return TRUE iff sp1 is less than sp2 */
 405     if (sp1->exit->q2 <= sp2->exit->q1) return(FALSE);
 406     else return(TRUE);
 407 }
 408 /*===================================================================================*/
 409 int check_spanset_p(span, spanSet)
 410     connect *span;
 411     connlist *spanSet;
 412 {
 413     /* Return TRUE iff the given <span> fits in the <spanset>   Make no alterations. */
 414     connlist *srl;
 415     int min1 = span->exit->q1, min2, max1 = span->exit->q2, max2;
 416
 417     if (spanSet == NULL) return(TRUE);
 418
 419     sort_list(spanSet, descending_order);
 420     for (srl = spanSet; srl != NULL; srl = srl->next) /* <spanSet> is sorted */
 421     {
 422         min2 = srl->this->exit->q1;
 423         max2 = srl->this->exit->q2;
 424         if (separate_spans(span, srl->this) != TRUE)
 425         {
 426             /* restore values */
 427             span->exit->q1 = min1;      srl->this->exit->q1 = min2;
 428             span->exit->q2 = max1;      srl->this->exit->q2 = max2;
 429             return(FALSE);
 430         }
 431         else
 432         {   /* Repair side effects */
 433             srl->this->exit->q1 = min2;         srl->this->exit->q2 = max2;
 434         }
 435     }
 436     /* restore values */
 437     span->exit->q1 = min1;      span->exit->q2 = max1;
 438     return(TRUE);
 439 }
 440 /*===================================================================================*/
 441 int fits_in_spanset_p(span, spanSet)
 442     connect *span;
 443     connlist *spanSet;
 444 {
 445     /* Return TRUE iff the given <span> fits in the <spanset>   Make no alterations. */
 446     connlist *srl;
 447     int min1 = span->exit->q1, min2, max1 = span->exit->q2, max2;
 448
 449     if (spanSet == NULL) return(TRUE);
 450
 451     sort_list(spanSet, descending_order);
 452     for (srl = spanSet; srl != NULL; srl = srl->next) /* <spanSet> is sorted */
 453     {
 454         min2 = srl->this->exit->q1;
 455         max2 = srl->this->exit->q2;
 456         if (separate_spans(span, srl->this) != TRUE)
 457         {
 458             /* restore values */
 459             span->exit->q1 = min1;      srl->this->exit->q1 = min2;
 460             span->exit->q2 = max1;      srl->this->exit->q2 = max2;
 461             return(FALSE);
 462         }
 463         if (span->exit->q2 < min2) break;
 464     }
 465     return(TRUE);
 466 }
 467 /*===================================================================================*/
 468 int unobstructed_p(vertSRange, horzSRange, span, usedSpans, exitSide)
 469     srange *vertSRange, *horzSRange;
 470     connect *span;
 471     connlist *usedSpans;
 472     int exitSide;
 473
 474 {
 475     /* Return TRUE if the some of the given <vertSRange> casn be traced from <horzSRange>
 476        to the given <exitSide> of the page.  If it can, correct the <vertSRange> to the
 477        part of the range that will connect. */
 478
 479     int yExtent = srange_width(vertSRange), xExtent;
 480     connect vSpan;
 481     srange vSRange;
 482     tile *corn, *lasTile = NULL;
 483     tilist *tl, *marker, *goodTiles = NULL;
 484
 485     /* Set up the local span variables.  These are used to verify the usefulness
 486        of a located <horzSRange> so that a good one is returned, if one exists.  */
 487     vSRange.orient = VERT;
 488     vSpan.exit = &vSRange;
 489     vSpan.up = span->up;
 490     vSpan.down = span->down;
 491     vSpan.mod = span->mod;
 492     vSpan.corners = span->corners;
 493
 494     /* The <vertSRange>, <horzSRange> and the <exitSide> determine a rectangle that can
 495        be searched to see if there is anything that spans the distance:
 496      */
 497
 498     if (exitSide == RIGHT)
 499     {
 500         corn = find_LRHC(routingRoot[0][HORZ]);
 501         xExtent = corn->x_pos + corn->x_len - horzSRange->q1;
 502     }
 503     else
 504     {
 505         corn = find_ULHC(routingRoot[0][HORZ]);
 506         xExtent = corn->x_pos - horzSRange->q2;
 507     }
 508
 509     /* Set the span range for the filter function: */
 510     startX = MIN(horzSRange->q1, horzSRange->q1 + xExtent);
 511     endX = MAX(horzSRange->q1, horzSRange->q1 + xExtent);
 512
 513     area_enumerate(corn, &goodTiles, spans_range_p,
 514                    horzSRange->q1, vertSRange->q1 ,xExtent, yExtent);
 515
 516     /* Something to deal with - form the real continuous span from this info: */
 517     if (exitSide == LEFT)
 518         sort_list(goodTiles, most_up); /* Start placing outputs to LL */
 519     else
 520         sort_list(goodTiles, most_down);   /* Start placing inputs to UR */
 521
 522     /* Set up the loop stuff: */
 523     marker = goodTiles;
 524     while(marker != NULL)
 525     {
 526         lasTile = marker->this;
 527         vSRange.q1 = lasTile->y_pos;
 528         vSRange.q2 = lasTile->y_pos + lasTile->y_len;
 529         tl = marker->next;
 530
 531         /* Setup the next contiunous, unobstructed vertical srange:     */
 532         while ((tl != NULL) && (adjacent_tiles_p(tl->this, lasTile) == TRUE))
 533         {
 534             /* Now find the maximum y-span available. (Best-First) */
 535             vSRange.q1 = MIN(vSRange.q1, tl->this->y_pos);
 536             vSRange.q2 = MAX(vSRange.q2, tl->this->y_pos + tl->this->y_len);
 537             lasTile = tl->this; /* Advance the loop index */
 538             tl = tl->next;
 539         }
 540         marker = tl;    /* Update the marker */
 541
 542         /* Check to see if this unobstructed range will work: */
 543         if (fits_in_spanset_p(&vSpan, usedSpans) == TRUE)
 544         {
 545             /* Reset the range to that which is unobstructed */
 546             vertSRange->q1 = vSRange.q1;
 547             vertSRange->q2 = vSRange.q2;
 548             free_list(goodTiles);
 549             return(TRUE);
 550         }
 551         /* Otherwise, Loop again to see if there is another one that will work */
 552     }
 553     free_list(goodTiles);
 554     return(FALSE);
 555 }
 556 /*===================================================================================*/
 557 crnlist *find_next_closest_range(vertSRange, horzSRange, orderedCorners)
 558     srange *vertSRange, **horzSRange;
 559     crnlist **orderedCorners;
 560 {
 561     /* Given the list of <orderedCorners> to chose from, pop the next set of corners
 562        that shares the same <horzSRange>.  From this set of corners, fill in the superset
 563        of xpositions into the <vertSRange> slots.  Stuff the corner(s) used to create
 564        this range into a list and return it.
 565
 566        LOTS OF SIDE EFFECTS!!!
 567      */
 568
 569     crnlist *cl, *used = NULL;
 570     range *xR;
 571     if (*orderedCorners != NULL)
 572     {
 573         xR = (*orderedCorners)->this->cx;
 574         vertSRange->q1 = (*orderedCorners)->this->cy->sr->q1;
 575         vertSRange->q2 = (*orderedCorners)->this->cy->sr->q2;
 576
 577         for(cl = *orderedCorners; ((cl != NULL) && (cl->this->cx == xR));
 578             cl = *orderedCorners)
 579         {
 580             /* Shorten <orderedCorners>, lengthen <used> & update the <vertSRange> : */
 581             trans_item(cl->this, orderedCorners, &used);
 582             vertSRange->q1 = MIN(vertSRange->q1, cl->this->cy->sr->q1);
 583             vertSRange->q2 = MAX(vertSRange->q2, cl->this->cy->sr->q2);
 584         }
 585         *horzSRange = xR->sr;
 586         return(used);
 587
 588     }
 589     else /* Given nothing to work with */
 590     {
 591         *horzSRange = NULL;
 592         vertSRange->q1 = 0;
 593         vertSRange->q2 = 0;
 594         return(NULL);
 595     }
 596 }
 597 /*===================================================================================*/
 598 term *select_non_systerm(terms, side)
 599     tlist *terms;
 600     int side;
 601 {
 602     /* Return the first non-system terminal. */
 603     module *m;
 604     tile *corn;
 605     term *closest = NULL;
 606     tlist *tl;
 607     int mType, base, smallestDist;
 608
 609     if (side == RIGHT) corn = find_LRHC(routingRoot[0][HORZ]);
 610     else corn = find_ULHC(routingRoot[0][HORZ]);
 611     base = (side == LEFT) ? corn->x_pos : corn->x_pos + corn->x_len;
 612     smallestDist = -1;
 613
 614     for (tl = terms; tl != NULL; tl = tl->next)
 615     {
 616         mType = validate(tl->this->mod->type);
 617         if ((mType != INPUT_SYM) && (mType != OUTPUT_SYM) &&
 618             (mType != INOUT_SYM))
 619         {
 620             m = tl->this->mod;
 621             if ((abs(base - m->x_pos - tl->this->x_pos) <= smallestDist) ||
 622                 (smallestDist == -1));
 623             {
 624                 closest = tl->this;
 625                 smallestDist = abs(base - m->x_pos - closest->x_pos);
 626             }
 627         }
 628     }
 629     if (closest == NULL)
 630         fprintf(stderr, "error in select_non_systerm --> no terminal found!\n");
 631     return(closest);
 632 }
 633
 634 /*===================================================================================*/
 635
 636 srange *locate_best_placement_range_for_systerm(span, fromSide, usedSpans)
 637     connect *span;              /* The Span being built */
 638     int fromSide;               /* LEFT or RIGHT */
 639     connlist *usedSpans;
 640 {
 641     /* This is a best-first algorithm;  Other (collective) limitations are not
 642        included (yet).  Probably a running list of available ranges should be maintained
 643        and checked against in the "unobstructed_p" function.
 644      */
 645     module *systerm = span->mod;
 646     srange *dummyVRange, *dummyHRange;
 647     net *n = systerm->terms->this->nt;
 648     corner *c;
 649     crnlist *cl, *AllCorners, *used;
 650     term *t;
 651     int refX, refY;
 652
 653     if (fromSide == RIGHT)
 654     {
 655         AllCorners = (crnlist *)rcopy_list(sort_list(n->route, in_x_order));
 656     }
 657     else
 658     {
 659         AllCorners = (crnlist *)copy_list(sort_list(n->route, in_x_order));
 660     }
 661
 662     if (AllCorners == NULL) /* There is only one terminal connected, so fake it : */
 663     {
 664         t = select_non_systerm(n->terms, fromSide);
 665         refX = t->x_pos + t->mod->x_pos;
 666         refY = t->y_pos + t->mod->y_pos;
 667         c = create_corner(create_range(create_srange(refX, refX, VERT), n),
 668                           create_range(create_srange(refY, refY, HORZ), n), NULL, t);
 669         push(c, &AllCorners);
 670     }
 671     for (cl = AllCorners; cl != NULL; cl = cl->next)
 672     {
 673         /* Walk through the corner list, and find the left/right-most unobstructed
 674            range to use: */
 675         /* First, create the dummy range to fill: */
 676         dummyVRange = create_srange(0, 0, VERT);
 677
 678         /* Next fill the range: */
 679         used = find_next_closest_range(dummyVRange, &dummyHRange, &AllCorners);
 680
 681         while((AllCorners != NULL) && (srange_width(dummyHRange) > 0))
 682         {
 683             span->corners = used;
 684             if (unobstructed_p(dummyVRange, dummyHRange, span, usedSpans, fromSide)
 685                 == TRUE)
 686             {
 687                 span->exit = dummyHRange;
 688                 if (fits_in_spanset_p(span, usedSpans) == TRUE)
 689                 {
 690                     /* If there is a corner in this span, pick the highest one and
 691                        fix the location to it: */
 692                     refY = terminal_point_to_save(dummyVRange, span->corners);
 693                     if (refY != TILE_SPACE_Y_POS)
 694                     {
 695                         dummyVRange->q1 = dummyVRange->q2 = refY;
 696                     }
 697                     span->exit = dummyVRange;
 698                     return(dummyVRange);
 699                 }
 700             }
 701             else
 702                 used = find_next_closest_range(dummyVRange, &dummyHRange, &AllCorners);
 703         }
 704
 705         span->corners = used;
 706         if (unobstructed_p(dummyVRange, dummyHRange, span, usedSpans, fromSide) == TRUE)
 707         {
 708             span->exit = dummyVRange;
 709             if (fits_in_spanset_p(span, usedSpans) == TRUE)
 710             {
 711                 refY = terminal_point_to_save(dummyVRange, span->corners);
 712                 if (refY != TILE_SPACE_Y_POS)
 713                 {
 714                     dummyVRange->q1 = dummyVRange->q2 = refY;
 715                 }
 716                 span->exit = dummyVRange;
 717                 return(dummyVRange);
 718             }
 719         }
 720     }
 721     span->exit = dummyVRange;           /* Give it something to work with */
 722     return(NULL);                       /* Notify that this range doesn't fit */
 723 }
 724 /*===================================================================================*/
 725 int falls_in_srange_p(x, sr)
 726     int x;
 727     srange *sr;
 728 {
 729     if ((sr->q1 <= x) && (x <= sr->q2)) return(TRUE);
 730     else return(FALSE);
 731 }
 732 /*===================================================================================*/
 733 int fits_in_before(sp, fixedSpan, side, usedSpans)
 734     connect *sp, *fixedSpan;
 735     int side;
 736     connlist *usedSpans;
 737 {
 738     int p = sp->exit->q1;
 739     term *closesTerm;
 740     srange dummyXRange, dummyYRange;
 741
 742     /* First see if a range can be found between <p> and <fixedSpan>->exit in which
 743        to locate <sp> */
 744     if (p > fixedSpan->exit->q1)
 745     {
 746         dummyYRange.q1 = fixedSpan->exit->q2;           dummyYRange.q2 = p;
 747     }
 748     else
 749     {
 750         dummyYRange.q1 = p;             dummyYRange.q2 = fixedSpan->exit->q1;
 751     }
 752
 753     /* find the nearest (horizontally) terminal to line up on. */
 754     closesTerm = select_non_systerm(sp->mod->terms->this->nt->terms, side);
 755     dummyXRange.q1 = dummyXRange.q2 = closesTerm->mod->x_pos + closesTerm->x_pos;
 756
 757     if (unobstructed_p(&dummyYRange, &dummyXRange, sp, usedSpans, side) == TRUE)
 758     {
 759         sp->exit->q1 = dummyYRange.q1;
 760         sp->exit->q2 = dummyYRange.q2;
 761         if (fits_in_spanset_p(sp, usedSpans) == TRUE) return(TRUE);
 762     }
 763
 764     /* Otherwise try fitting <sp> immediately before <fixedSpan> */
 765     sp->exit->q2 = fixedSpan->exit->q1 - sp->up - fixedSpan->down;
 766     sp->exit->q1 = sp->exit->q2;
 767     return (fits_in_spanset_p(sp, usedSpans));
 768 }
 769 /*===================================================================================*/
 770 int fits_in_after(sp, fixedSpan, side, usedSpans)
 771     connect *sp, *fixedSpan;
 772     int side;
 773     connlist *usedSpans;
 774 {
 775     int p = sp->exit->q1;
 776     term *closesTerm;
 777     srange dummyXRange, dummyYRange;
 778
 779     /* First see if a range can be found between <p> and <fixedSpan>->exit in which
 780        to locate <sp> */
 781     if (p > fixedSpan->exit->q1)
 782     {
 783         dummyYRange.q1 = fixedSpan->exit->q2;           dummyYRange.q2 = p;
 784     }
 785     else
 786     {
 787         dummyYRange.q1 = p;             dummyYRange.q2 = fixedSpan->exit->q1;
 788     }
 789
 790     /* find the nearest (horizontally) terminal to line up on. */
 791     closesTerm = select_non_systerm(sp->mod->terms->this->nt->terms, side);
 792     dummyXRange.q1 = dummyXRange.q2 = closesTerm->mod->x_pos + closesTerm->x_pos;
 793
 794     if (unobstructed_p(&dummyYRange, &dummyXRange, sp, usedSpans, side) == TRUE)
 795     {
 796         sp->exit->q1 = dummyYRange.q1;
 797         sp->exit->q2 = dummyYRange.q2;
 798         if (fits_in_spanset_p(sp, usedSpans) == TRUE) return(TRUE);
 799     }
 800
 801     /*  Otherwise, try fitting <sp> immediately after <fixedSpan> */
 802     sp->exit->q1 = fixedSpan->exit->q2 + sp->down + fixedSpan->up;
 803     sp->exit->q2 = sp->exit->q1;
 804     return(fits_in_spanset_p(sp, usedSpans));
 805 }
 806 /*===================================================================================*/
 807 fit_into_available_space(sp, side, usedSpans)
 808     connect *sp;
 809     int side;
 810     connlist **usedSpans;
 811 {
 812     /* find something near sp->exit that will accomodate <sp> in <usedSpans> */
 813     srange *yRng;
 814     int p;
 815     connlist *before = NULL, *after = NULL;
 816     connlist *cnl, *bl, *al;
 817
 818     center_range_on_single_point(sp->exit);
 819     p = sp->exit->q1;
 820     sort_list(*usedSpans, descending_order);
 821
 822     /* Create a list of spans that occur <before> and <after> <sp>.  The break occurs
 823        before the span near where <sp> wants to fall: */
 824     for (cnl = *usedSpans; cnl != NULL; cnl = cnl->next)
 825     {
 826         if ((falls_in_srange_p(p, cnl->this->exit) == TRUE) ||
 827             (p < cnl->this->exit->q1))
 828         {
 829             after = cnl;
 830             break;
 831         }
 832         else
 833         {
 834             push(cnl->this, &before);
 835         }
 836     }
 837
 838     /* (useAveraging == TRUE)??   Something to try later... */
 839
 840     if ((after != NULL) && (before != NULL))
 841     {
 842         /* Which is closer? */
 843         if ((after->this->exit->q1 - p) < (p - before->this->exit->q2))
 844         {
 845             /* after->this is, so try next to there first: */
 846             if (fits_in_before(sp, after->this, side, *usedSpans) == TRUE)
 847             {
 848                 push(sp, usedSpans);
 849                 return(TRUE);
 850             }
 851         }
 852         else
 853         {
 854             if (fits_in_after(sp, before->this, side, *usedSpans) == TRUE)
 855             {
 856                 push(sp, usedSpans);
 857                 return(TRUE);
 858             }
 859
 860         }
 861     }
 862
 863     /* Toggle back and forth between the before & after lists looking for a
 864        legal place to insert <sp>: */
 865     bl = before;
 866     al = after;
 867     while ((al != NULL) && (bl != NULL))
 868     {
 869         if ((bl == NULL) ||                             /* No before list left... */
 870             (((al != NULL) && (bl != NULL)) &&          /* the <al> entry is closer */
 871               ((al->this->exit->q1 - p) < (p - bl->this->exit->q2))))
 872         {
 873             if ((fits_in_before(sp, al->this, side, *usedSpans) == TRUE) ||
 874                 (fits_in_after(sp, al->this, side, *usedSpans) == TRUE))
 875             {
 876                 push(sp, usedSpans);
 877                 return(TRUE);
 878             }
 879             else al = al->next;
 880         }
 881
 882         if ((al == NULL) ||                             /* no after list left... */
 883             ((al != NULL) && (bl != NULL)))             /* the <bl> entry is closer */
 884         {
 885             if ((fits_in_after(sp, bl->this, side, *usedSpans) == TRUE) ||
 886                 (fits_in_before(sp, bl->this, side, *usedSpans) == TRUE))
 887             {
 888                 push(sp, usedSpans);
 889                 return(TRUE);
 890             }
 891             else bl = bl->next;
 892         }
 893     }
 894
 895     /* If you get this far, <sp> could not be fit into the middle of <usedSpans> */
 896     /* Force it on the end somewhere */
 897
 898     bl = *usedSpans;
 899     for (cnl = after; ((cnl != NULL) && (cnl->next != NULL)); cnl = cnl->next);
 900
 901     if ((cnl != NULL) &&
 902         ((cnl->this->exit->q1 - p) < (p - bl->this->exit->q2)))
 903     {
 904         /* if closer to the top of the page: */
 905         sp->exit->q1 = cnl->this->exit->q2 + sp->down + cnl->this->up;
 906         sp->exit->q2 = sp->exit->q1;
 907     }
 908     else
 909     {
 910         /* force it to the begining of <usedSpans>: */
 911         sp->exit->q2 = bl->this->exit->q1 - sp->up - bl->this->down;
 912         sp->exit->q1 = sp->exit->q2;
 913     }
 914     push(sp, usedSpans);        /* It Better Fit!!  BB Problems??? */
 915
 916     return(FALSE);
 917 }
 918 /*===================================================================================*/
 919 repair_failed_spans(failedSpans, side, goodSpans)
 920     connlist *failedSpans;
 921     int side;
 922     connlist **goodSpans;
 923 {
 924     srange *yRng;
 925     connect *span;
 926     connlist *cnl;
 927
 928     sort_list(failedSpans, ascending_order);
 929     for (cnl = failedSpans; cnl != NULL; cnl = cnl->next)
 930     {
 931         span = cnl->this;
 932         if (*goodSpans == NULL) push(span, goodSpans);
 933         else fit_into_available_space(span, side, goodSpans);
 934     }
 935 }
 936 /*===================================================================================*/
 937 verify_all_spans(goodSpans, side, spanStillScrewed)
 938     connlist **goodSpans;
 939     int side;
 940     connlist **spanStillScrewed;
 941 {
 942     srange *yRng;
 943     connect *span;
 944     connlist *master = NULL, *cnl;
 945
 946     master = (connlist *)copy_list(sort_list(*goodSpans, ascending_order));
 947     for (cnl = master; cnl != NULL; cnl = cnl->next)
 948     {
 949         span = (connect *)rem_item(cnl->this, goodSpans);
 950         if (fits_in_spanset_p(span, *goodSpans) == TRUE) push(span, goodSpans);
 951         else
 952         {
 953             fit_into_available_space(span, side, goodSpans);
 954             push(span, spanStillScrewed);
 955         }
 956     }
 957     free_list(master);
 958 }
 959 /*===================================================================================*/
 960 int locate_systerm(span, x_pos)
 961     connect *span;
 962     int x_pos;
 963 {
 964     /* Finds and sets the best Y location for this module: use the given span info
 965      RULES:
 966         (1) Pick a corner. Highest corner is prefered for inputs, lowest for outputs
 967         (2) Pick the center of the range spanned by the corners chosen
 968         (3) Pick the center of the available exit range
 969      */
 970
 971     int min, max, cornerY;
 972     module *systerm;
 973     crnlist *cl;
 974     srange *exit;
 975
 976     if ((span == NULL) || (span->exit == NULL)) return(FALSE);
 977
 978     exit = span->exit;
 979     systerm = span->mod;
 980     min = span->exit->q1;
 981     max = span->exit->q2;
 982
 983     /* Rule (0) -- Use terminal poins */
 984     cornerY = terminal_point_to_save(exit, span->corners);
 985     if (cornerY != TILE_SPACE_Y_POS)
 986     {
 987         systerm->y_pos = cornerY - span->down;
 988         systerm->x_pos = x_pos;
 989         exit->q1 = exit->q2 = cornerY;
 990         return(TRUE);
 991     }
 992
 993     /* Rule (1) */
 994     for (cl = span->corners; cl != NULL; cl = cl->next)
 995     {
 996         cornerY = cl->this->cy->sr->q1;
 997
 998         /* If there is a corner that connects inside the  exit range, use it: */
 999         if (falls_in_srange_p(cornerY, exit) == TRUE)
1000         {
1001             /* Found One! */
1002             systerm->y_pos = cornerY - span->down;
1003             systerm->x_pos = x_pos;
1004             exit->q1 = exit->q2 = cornerY;
1005             return(TRUE);
1006         }
1007         min = MIN(cornerY, min);        /* Expand the range that the term can fall in */
1008         max = MAX(cornerY, max);
1009     }
1010     /* Rule (2) */
1011     if (falls_in_srange_p((min+max)/2, exit) == TRUE)
1012     {
1013         systerm->y_pos = (min+max)/2 - span->down;
1014         systerm->x_pos = x_pos;
1015         exit->q1 = exit->q2 = (min+max)/2;
1016         return(TRUE);
1017     }
1018     else if (falls_in_srange_p((min+max+1)/2, exit) == TRUE)
1019     {
1020         systerm->y_pos = (min+max+1)/2 - span->down;
1021         systerm->x_pos = x_pos;
1022         exit->q1 = exit->q2 = (min+max+1)/2;
1023         return(TRUE);
1024     }
1025     else
1026     {
1027         /* Rule (3) */
1028         center_range_on_single_point(exit);                   /* see "local_route.c" */
1029         systerm->y_pos = exit->q1 - span->down;
1030         systerm->x_pos = x_pos;
1031         return(TRUE);
1032     }
1033 }
1034 /*===================================================================================*/
1035 set_spans(spans, x_pos, leftovers, base, height)
1036     connlist *spans;
1037     int x_pos;
1038     mlist **leftovers;          /* Things not dealt with that should have been */
1039     int *base, *height;
1040 {
1041     connlist *col;
1042     module *m;
1043
1044     /* Now that valid ranges have been set up, localize the ranges */
1045     for (col = spans; col != NULL; col = col->next)
1046     {
1047         /* Now use this information to place the modules.  Any terminal with an entry
1048            sould be placed directly.  Anything with a NULL ->exit field needs to be
1049            handled seperately. */
1050         m = col->this->mod;
1051         locate_systerm(col->this, x_pos);
1052         if (col->this->exit == NULL)
1053         {
1054             push(m, leftovers);
1055             m->placed = UNPLACED;
1056         }
1057         else
1058         {
1059             /* Create the fuzzy (delayed-evaluation) position...  (not quite right) */
1060             m->fx->item1 = create_int_varStruct(&m->x_pos);
1061             m->fy->item1 = create_int_varStruct(&m->y_pos);
1062
1063             /* record the base & height values (for BB calculation) */
1064             *base = MIN(*base, col->this->exit->q1 - col->this->down - CHANNEL_HEIGHT);
1065             *height = MAX(*height, col->this->exit->q2 + col->this->up -
1066                                    *base + CHANNEL_HEIGHT);
1067         }
1068     }
1069 }
1070
1071 /*===================================================================================*/
1072 /*---------------------------------------------------------------
1073  * place_systerm_partitions(part, x_pos)        (Level 2)
1074  * place the modules in the given partition, given that all those in
1075  * partitions[0] have been placed AND ROUTED (See "local_route.c")
1076  *
1077  * This is supposed to use the routing and terminal locations available to
1078  * place the given terminals on the edge of the page (The x position given)
1079
1080  *  So here is the plan:
1081     Find the list of terminals to be placed, and then see if there are nets associated
1082     with them extant in the (routed) partition[0].  There will either be a wire (corner
1083     list) or at least a terminal.
1084
1085     now the trick is to align as many terminals as possible on _unobstructed_ corners.
1086     So, what is an _unobstructed_ corner?  It is one in which no bends are required
1087     to connect to it.  Properly done, this process should result in a set of modules
1088     and a (vertical) range to tie them to.  Based on these range, place the modules.
1089     Anything without a placement range still needs to be placed as well, and there is
1090     the problem of insuring that the various ranges do not force the modules to
1091     overlap vertically.
1092  *
1093  *---------------------------------------------------------------
1094  */
1095 place_systerm_partitions(part, x_pos, bb_base, bb_height)
1096     int part, x_pos;
1097     int *bb_base, *bb_height;
1098 {
1099     int side;
1100     module *m;
1101     mlist *ml, *mml, *leftovers = NULL;
1102     srange *sr;
1103     connect *newSpan;
1104     connlist *col, *screwedSpans = NULL, *bestSpans = NULL;
1105
1106     /* The partition number indexes either the input system terminals, or the
1107        output system terminals.  (see "place.c") */
1108     for (ml = partitions[part]; ml != NULL; ml = ml->next)
1109     {
1110         /* Reset the terminal information within the net structures: */
1111         add_terms_to_nets(ml->this);
1112         paint_corners(ml->this);
1113
1114         newSpan = create_connect(ml->this, NULL, NULL);
1115
1116         /* Find the best unobstructed range in which to place this module,
1117            and push it onto the <bestRanges> list */
1118         if (part == partition_count + 1) side = RIGHT;
1119         else side = LEFT;
1120
1121         sr = locate_best_placement_range_for_systerm(newSpan, side, bestSpans);
1122
1123         if (sr != NULL)
1124         {
1125             newSpan->exit = sr;
1126             queue(newSpan, &bestSpans);
1127         }
1128         else
1129         {
1130             if (debug_level > 0)
1131             fprintf(stderr, "Placement will be irregular for system terminal <%s>.\n",
1132                     ml->this->name);
1133             /* Now mark the span, so it can be fitted later: */
1134             push(newSpan, &screwedSpans);
1135         }
1136     }
1137
1138     /* Now fix those that we are happy with: */
1139     set_spans(bestSpans, x_pos, &leftovers, bb_base, bb_height);
1140
1141     /* Now find a way to adjust the failed spans so they will fit: */
1142     repair_failed_spans(screwedSpans, side, &bestSpans);
1143     set_spans(screwedSpans, x_pos, &leftovers, bb_base, bb_height);
1144
1145     screwedSpans = (connlist *)free_list(screwedSpans);
1146     verify_all_spans(&bestSpans, side, &screwedSpans);
1147     set_spans(screwedSpans, x_pos, &leftovers, bb_base, bb_height);
1148
1149     if (leftovers != NULL)
1150     {
1151         fprintf(stderr, "WARNING:  System Terminals on the %s side may overlap.\n",
1152                 SSIDE(side));
1153     }
1154
1155 /* Cleanup: */
1156     for (ml = partitions[part]; ml != NULL; ml = ml->next)
1157     {
1158         /* move the partition to partition 0 */
1159         partitions[0] = (mlist *)concat_list(ml->this, partitions[0]);
1160
1161         /* and mark it as placed */
1162         ml->this->placed = PLACED;
1163     }
1164     free_list(screwedSpans);
1165     free_list(leftovers);
1166     free_list(bestSpans);
1167 }
1168 /*===================================================================================*/
1169 /*---------------------------------------------------------------
1170  * fine_systerm_placement (Level 1)
1171  * Put all the partitions into one bounding box in partition 0,
1172  * based on picking the largest number of connections off the diagonal
1173  * of the connection matrix; (which has been built to match the
1174  * partitions, seen as clusters)
1175  *---------------------------------------------------------------
1176  */
1177 mlist *fine_systerm_placement(x1, y1, x2, y2)
1178     int *x1, *y1, *x2, *y2;                     /* The current Bounding Box */
1179 {
1180 /* Now there are three partitions:  0, pc+1, & pc+2, which contain the (now placed)
1181  * internal modules, the output only system terminals, and the remaining systerms.
1182  * These remaining two sets of unplaced modules are placed using the information found by
1183  * examining the placement of the internal modules.  NOTE:  The systerms have been
1184  * 'placed' by the boxing routines, so the information within the mod structures must
1185  * be ignored.
1186  *
1187  */
1188     int outputColumn = *x2 - CHANNEL_LENGTH - SYSTERM_SIZE;
1189     int inputColumn = *x1 + CHANNEL_LENGTH;
1190     int yP = *y1, yL = *y2 - *y1;
1191
1192 /* Reset the placement information within the module structures: */
1193
1194 /* place the systerm modules within their partitions: */
1195     place_systerm_partitions(partition_count + 2, inputColumn, &yP, &yL);
1196     place_systerm_partitions(partition_count + 1, outputColumn, &yP, &yL);
1197
1198 /* cleanup the bounding box (ganz wigtig! very important!) */
1199     if(*y1 != yP)
1200     {
1201         /*      if (debug_level != 0)  */
1202         fprintf(stderr, "Adjusting Bounding Box base from (%d,%d) to (%d,%d)\n",
1203                 *x1, *y1, *x1, yP - CHANNEL_HEIGHT);
1204         *y1 = yP - CHANNEL_HEIGHT;
1205         *y2 += CHANNEL_HEIGHT;
1206     }
1207     if (*y2 - *y1 != yL)
1208     {
1209         /*      if (debug_level != 0)  */
1210         fprintf(stderr, "Adjusting Bounding Box top from (%d,%d) to (%d,%d)\n",
1211                 *x2, *y2, *x2, yL - yP);
1212         *y2 = yL - *y1 + CHANNEL_HEIGHT;
1213     }
1214
1215 /* build the return list: */
1216     return((mlist *)append_list(rcopy_list(partitions[partition_count+2]),
1217                                 rcopy_list(partitions[partition_count+1])));
1218 }
1219
1220 /*===================================================================================*/
1221
1222 mlist *make_room_for_systerm_placement(systermNets, x1, y1, x2, y2)
1223     nlist **systermNets;
1224     int *x1, *y1, *x2, *y2;
1225 {
1226     /* Use the old systerm placement routine, so as to allow enough room for the
1227        system terminals.  The main purpose is to set xfloor, yfloor, etc. for
1228        partition 0;  Also assigns X columns for systerm placement.
1229        */
1230
1231     mlist *ml, *systerms = NULL;
1232     systerms = (mlist *)append_list(rcopy_list(partitions[partition_count+2]),
1233                                     rcopy_list(partitions[partition_count+1]));
1234     expand_bounding_box_for_systerms(x1, y1, x2, y2);
1235     for (ml = systerms; ml != NULL; ml = ml->next)
1236     {
1237         push(ml->this->terms->this->nt, systermNets);
1238     }
1239     return(systerms);
1240 }
1241
1242 /*===================================================================================*/
1243
1244 expand_bounding_box_for_systerms(x1, y1, x2, y2)
1245     int *x1, *y1, *x2, *y2;
1246 {
1247     /* Determine the new bounding box llhc and urhc: */
1248     mlist *ml;
1249     int bestX, max_wid = 0, max_height = 0;
1250     int left = partition_count + 2, right = partition_count + 1;
1251     int noInputs, noOutputs, maxCount;
1252
1253     noInputs = list_length(partitions[left]);
1254     noOutputs = list_length(partitions[right]);
1255     maxCount = MAX(noInputs, noOutputs);
1256
1257     *y1 = yfloor - CHANNEL_HEIGHT; /* - (SYSTERM_SIZE) * maxCount; */
1258     *y2 = *y1 + y_sizes[0] + CHANNEL_HEIGHT;
1259 /*          2 * (CHANNEL_HEIGHT + (SYSTERM_SIZE) * maxCount); */
1260
1261     *x1 = xfloor - CHANNEL_LENGTH - noInputs - SYSTERM_SIZE;
1262     *x2 = *x1 + x_sizes[0] + 2 * (CHANNEL_LENGTH + noInputs + SYSTERM_SIZE);
1263 }
1264
1265 /*===================================================================================*/
1266
1267 /*---------------------------------------------------------------
1268  * gross_systerm_placement (Level 1)
1269  * Put all the partitions into one bounding box in partition 0,
1270  * based on picking the largest number of connections off the diagonal
1271  * of the connection matrix; (which has been built to match the
1272  * partitions, seen as clusters)
1273  *---------------------------------------------------------------
1274  */
1275 mlist *gross_systerm_placement(x1, y1, x2, y2)
1276     int *x1, *y1, *x2, *y2;
1277 {
1278 /* Now there are three partitions:  0, pc+1, & pc+2, which contain the (now placed)
1279  * internal modules, the output only system terminals, and the remaining systerms.
1280  * These remaining two sets of unplaced modules are placed using the information found by
1281  * examining the placement of the internal modules.  NOTE:  The systerms have been
1282  * 'placed' by the boxing routines, so the information within the mod structures must
1283  * be ignored.
1284  */
1285
1286 /* Reset the placement information within the module structures:
1287    This is the OLD placement algorithm.  It is not good, but it will complete, and serve
1288    well as a space-holder function.  These results will need to be overwritten later.
1289 */
1290
1291     /* place the systerm modules within their partitions: */
1292     old_place_systerm_partitions(partition_count + 2, xfloor);     /* input terminals */
1293     old_place_systerm_partitions(partition_count + 1, x_sizes[0]); /* output terminals */
1294
1295     /* cleanup */
1296     if((xfloor < 0)||(yfloor < 0))
1297     {
1298         reset_borders(xfloor,yfloor);
1299
1300         /* put the lower left corner of the box back at 0,0 */
1301         fixup_partition(0, xfloor, yfloor);
1302     }
1303
1304 /* build the return list: */
1305     return((mlist *)append_list(rcopy_list(partitions[partition_count+2]),
1306                                 rcopy_list(partitions[partition_count+1])));
1307 }
1308 /*===================================================================================*/
1309 /*---------------------------------------------------------------
1310  * old_place_systerm_partitions(part, x_pos)    (Level 2)
1311  * place the modules in p1, given that all those in <p2> have already been
1312  * put down.  TOO MESSY TO DESCRIBE!
1313  *---------------------------------------------------------------
1314  */
1315 old_place_systerm_partitions(part, x_pos)
1316     int part, x_pos;
1317 {
1318     mlist *ml, *mml;
1319     int ysum, count, y_pos, y_max = 0, x_max = 0;
1320     int temp, max_wid = 0, max_height = 0, placement_ok = FALSE;
1321     int left_side = partition_count + 2, right_side = partition_count + 1;
1322     tlist *tl, *ttl;
1323
1324     int systermX, systermY, lineupX, placement_set, bestX;
1325
1326     for (ml = partitions[part]; ml != NULL; ml = ml->next)
1327     {
1328         /* Reset the terminal information within the net structures: */
1329         add_terms_to_nets(ml->this);
1330
1331         /* walk through the list of modules in this partition, and find their ideal
1332            vertical location wrt partition 0, the set of already-placed partitions.  */
1333
1334         bestX = x_sizes[0] - xfloor;   /* used to choose the best term to line up on */
1335         placement_set = FALSE;
1336         max_wid = MAX(ml->this->x_size, max_wid);
1337         max_height = MAX(ml->this->y_size, max_height);
1338
1339         for (tl = ml->this->terms;  tl != NULL; tl = tl->next)
1340                                                         /* typically there's only one */
1341         {
1342 /* Average the position amongst the terminal positions on the net */
1343             count = ysum = 0;
1344
1345             for (ttl = tl->this->nt->terms; ttl != NULL; ttl = ttl->next)
1346             {
1347                 if ((ttl->this->mod != tl->this->mod) &&
1348                     (((part == left_side)  && (ttl->this->type != OUT)) ||
1349                      ((part == right_side) && (ttl->this->type == OUT))))
1350                 {
1351                     ysum += ttl->this->mod->y_pos + ttl->this->y_pos;
1352                     count += 1;
1353                     /* Try lining up on the first source (desination) terminal*/;
1354                     y_pos = ttl->this->mod->y_pos + ttl->this->y_pos - tl->this->y_pos;
1355
1356                     /* save the distance to this module, as we want the closest one.*/
1357                     lineupX = ttl->this->mod->x_pos;
1358
1359                     /* save it's position (if it's ok, we'll keep it) */
1360                     systermY = y_pos;                         /* (int)(ysum / count); */
1361                     systermX = (part == right_side) ?
1362                         x_pos + (WHITE_SPACE * count_terms_part(part, LEFT)) :
1363                         x_pos - ml->this->x_size -
1364                             (WHITE_SPACE * count_terms_part(part, RIGHT));
1365
1366                     /* Look for conflicts amongst the already-placed systerm modules: */
1367                     for (mml = partitions[part]; (mml != NULL);)
1368                     {
1369                         if (((mml->this != ml->this) && (mml->this->placed == PLACED))
1370                             &&
1371                             (!((mml->this->y_pos >=
1372                                 systermY + ml->this->y_size) ||
1373                                (mml->this->y_pos + mml->this->y_size <=
1374                                 systermY))))
1375                         {
1376                             /* there's a problem, so fix it. */
1377                             placement_ok = FALSE;
1378                             break;
1379                         }
1380                         else
1381                         {
1382                             placement_ok = TRUE;   /* keep checking */
1383                             mml = mml->next;
1384                         }
1385                     }
1386                     if (placement_ok == TRUE)  /* got a good one, so save whilst ahead */
1387                     {
1388                         if(abs(lineupX - x_pos) <= bestX)
1389                         {
1390                             bestX = abs(lineupX - x_pos);
1391                             y_max = MAX(y_max, systermY);
1392                             x_max = MAX(x_max, systermX);
1393                             ml->this->x_pos = systermX;
1394                             ml->this->y_pos = systermY;
1395                             placement_set = TRUE;
1396
1397                             /* Create the fuzzy (delayed-evaluation) position...
1398                                (not quite right) */
1399                             ml->this->fx->item1 = create_int_varStruct(&ml->this->x_pos);
1400                             ml->this->fy->item1 = create_int_varStruct(&ml->this->y_pos);
1401
1402                             /*   now keep looking (see if there is a closer one)   */
1403                         }
1404                     }
1405                 }
1406             }
1407         }
1408
1409         if (placement_set == FALSE)
1410         {
1411             ml->this->x_pos = systermX;
1412             ml->this->y_pos = systermY;
1413
1414             /* Create the fuzzy (delayed-evaluation) position...  (not quite right) */
1415             ml->this->fx->item1 = create_int_varStruct(&ml->this->x_pos);
1416             ml->this->fy->item1 = create_int_varStruct(&ml->this->y_pos);
1417
1418         /*     The module in question <ml->this> has now been placed in a (hopefully)
1419                legal position amongst its brother systerms.  This should be a lineup on
1420                the closest terminal that will yield a known legal position.  This may
1421                not have worked, so the following code is to insure that a legal position
1422                is found: */
1423
1424             /* Check again for conflicts amongst the already-placed systerm modules: */
1425             for (mml = partitions[part]; (mml != NULL);)
1426             {
1427                 if (((mml->this != ml->this) && (mml->this->placed == PLACED))
1428                     &&
1429                     (!((mml->this->y_pos >
1430                         ml->this->y_pos + ml->this->y_size) ||
1431                        (mml->this->y_pos + mml->this->y_size <
1432                         ml->this->y_pos))))
1433                 {
1434                     /* there's a problem, so fix it. (brutal) */
1435                     ml->this->y_pos = CHANNEL_HEIGHT + mml->this->y_size +
1436                     MAX(mml->this->y_pos, ml->this->y_pos);
1437
1438                     mml = partitions[part]; /* restart the loop, to see if this worked.*/
1439                 }
1440                 else mml = mml->next;
1441             }
1442         }
1443
1444         /* move the partition to partition 0 */
1445         partitions[0] = (mlist *)concat_list(ml->this, partitions[0]);
1446
1447         /* and mark it as placed */
1448         ml->this->placed = PLACED;
1449
1450         /* Readjust the bounding box: */
1451         if (y_sizes[0] <= ml->this->y_pos + ml->this->y_size)
1452         {
1453             y_sizes[0] = ml->this->y_pos + ml->this->y_size +
1454                          CHANNEL_HEIGHT + max_height;
1455         }
1456         if (x_sizes[0] <= ml->this->x_pos + ml->this->x_size)
1457         {
1458            x_sizes[0] = ml->this->x_pos + ml->this->x_size +
1459                         (WHITE_SPACE * count_terms_part(part, LEFT)) + max_wid;
1460         }
1461         if (yfloor >= ml->this->y_pos)
1462         {
1463             yfloor = ml->this->y_pos - ((WHITE_SPACE + CHANNEL_HEIGHT) + max_height);
1464         }
1465         if (xfloor >= ml->this->x_pos)
1466         {
1467             xfloor = ml->this->x_pos - (WHITE_SPACE * count_terms_part(part, RIGHT)) -
1468                      max_wid - CHANNEL_LENGTH;
1469         }
1470     }
1471 }
1472 /*===================================================================================*/
1473 /* end of file "terminals.c" */