asg/local_route.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 /*
  24  *      file local_route.c
  25  * As part of MS Thesis Work, S T Frezza, UPitt Engineering
  26  * February, 1990 - Major revision July, 1990 - Tuning for incremental route - Jan, 1991
  27  *
  28  * This file contains the global and local routing functions associated with the
  29  * SPAR schematics placer.  It is based on the data-structures created by the
  30  * parser (parse.c) and the placer (place.c), and is thus dependent upon:        */
  31
  32 #include <stdio.h>
  33 #include <time.h>       // For ctime()
  34 #include <stdlib.h>     // For getenv()
  35 #include "route.h"
  36
  37 /* It is expected that all modules have been placed, and that global routes have been
  38  * completed.  A global route consists of a list of completed trails, as set in
  39  * "terminate_expansion" in global_route.c, and are stored in the (common) trailist
  40  * ->connections in each of the expansions that are listed in the ->expns list
  41  * given in the net structure.
  42  *
  43  * Local Routing:
  44  * Once all nets have arcs assigned to them, (The result of the global routing process)
  45  * then the task remains to determine the corner points for jogs, angles, etc..  This
  46  * is a process of routing within boxes, where some items are constrained, others are
  47  * not, and some become constrained.  For example, a net that turns a corner within a
  48  * box is not completely constrained until the other corner of the net is reached.
  49  *
  50  * This is done by mapping each arc containing nets into a set of `constraints'.
  51  * These constraints are structures that represent where corners are to be placed.
  52  * They are linked by using common range structures, and are resolved when
  53  * the ranges are reduced to single points.  It is this resolution process that
  54  * determines how the nets are ordered within a given area.  Each constraint structure
  55  * is then complete, and is individually mapped into the segments that are printed on
  56  * the page.
  57  *
  58  * The constraint resolution process is not trivial, and is somewhat interesting in its
  59  * own right.  It is a heuristic process of seperating overlapping ranges such that the
  60  * corners and connections within each box are nicely placed.
  61  */
  62
  63
  64 /* ---- Local Variables ---------------------------------------------------------------*/
  65 #define TRIED -2
  66
  67 #define X_SHIFT -50
  68
  69 #define Y_SHIFT -50
  70
  71 extern char net_under_study[];
  72
  73 extern net *Net;                /* Used as a temporary global */
  74
  75 extern FILE *df, *vf, *hf;     /* Where to dump the global route trace/debug info */
  76
  77 extern int currentPage;         /* The current page on which insertions are being made */
  78
  79 static srange spanRange;
  80 /* static int idx = 0; */       /* Used for printing edge visitation order */
  81
  82 int *levelMap;                  /* Array used to trace the dependency depth of ranges */
  83 rnglist **reverseDepSets;       /* Array used to trace reverse dependency (break cyles)*/
  84
  85 ilist *congestion = NULL;       /* Indexed list of the tiles w/ worst congestion */
  86 ilist *crossovers = NULL;       /* Indexed list of the tiles w/ worst crossover */
  87
  88
  89 /* --- forward reference -------------------------------------------------------------:*/
  90 void write_local_route_to_file(FILE *f, nlist *nets);
  91 void xc_write_local_route(XCWindowData *areastruct, nlist *nets);
  92 void print_tile_spaces();
  93
  94 /*-------------------------------------------------------------------------------------*/
  95 /*-------------------------------------------------------------------------------------*/
  96 /*------------------------------------------------------------------------------------*/
  97 correct_overlap(a, aLen, b, bLen, beg, NewLen)  /* Not Used */
  98     int a, aLen, b, bLen, *beg, *NewLen;
  99 {
 100     int End;            /* Wouldn't compile with "end" - something about type problems */
 101
 102     /* Don't ask - takes two line segments, as determined by an axis point and length pair,
 103      * and resolves the overlap between the two of them [(a, aLen) and (b, bLen)]  */
 104     if ((a + aLen) >= (b + bLen)) End = b + bLen;
 105     else End = a + aLen;
 106
 107     if (a >= b) *beg = a;
 108     else *beg = b;
 109
 110     *NewLen = End - *beg;
 111 }
 112 /*------------------------------------------------------------------------------------*/
 113 /*------------------------------------------------------------------------------------*/
 114 /* Local Routing Stuff:                                                            */
 115 /*---------------------------------------------------------------------------------*/
 116 /*-------------------------------------------------------------------------------------*/
 117 int determine_entry_side(Parc, Carc, refX, refY)
 118     asg_arc *Parc, *Carc;
 119     int refX, refY;     /* Reference point in HORZ coordinates */
 120 {
 121     /* This determines the side of entry when moving from <Parc> to <Carc>. */
 122     int side;
 123
 124     if (Parc->page == VERT)
 125     {
 126         /* Check to see if the reference point is valid (contained in Parc): */
 127         if ((refX < Parc->t->y_pos) ||
 128             (refX > Parc->t->y_pos + Parc->t->y_len) ||
 129             (refY < Parc->t->x_pos) ||
 130             (refY > Parc->t->x_pos + Parc->t->x_len))
 131         {
 132             fprintf(stderr, "determine_entry_side : Bad reference point(%d, %d)\n",
 133                     refX, refY);
 134             return(FALSE);
 135         }
 136
 137         else if (Carc->page == VERT)
 138         {
 139             if (refX <= Carc->t->y_pos) return(LEFT);
 140             else return(RIGHT);
 141         }
 142
 143         else if (Carc->page == HORZ)
 144         {
 145             if (refY > Carc->t->y_pos) return(UP);
 146             else return(DOWN);
 147         }
 148     }
 149
 150     else /* Parc->page == HORZ */
 151     {
 152         /* Check to see if the reference point is valid (contained in Parc): */
 153         if ((refX < Parc->t->x_pos) ||
 154             (refX > Parc->t->x_pos + Parc->t->x_len) ||
 155             (refY < Parc->t->y_pos) ||
 156             (refY > Parc->t->y_pos + Parc->t->y_len))
 157         {
 158             fprintf(stderr, "determine_entry_side : Bad reference point(%d, %d)\n",
 159                     refX, refY);
 160             return(FALSE);
 161         }
 162
 163         else if (Carc->page == VERT)
 164         {
 165             if (refX <= Carc->t->y_pos) return(LEFT);
 166             else return(RIGHT);
 167         }
 168
 169         else if (Carc->page == HORZ) /* may want to look at y_pos + y_len... */
 170         {
 171             if (refY > Carc->t->y_pos) return(UP);
 172             else return(DOWN);
 173         }
 174     }
 175 }
 176 /*-------------------------------------------------------------------------------------*/
 177 int find_intersection(x1, x2, X1, X2, res1, res2)
 178     int x1, x2, X1, X2;
 179     int *res1, *res2;
 180 {
 181     /* this resolves the intersection between two ranges.  It does funny things
 182        if they are non-overlapping ranges. */
 183
 184     int xEndsFirst = (int)(x2 < X2);
 185     int xStartsFirst = (int)(x1 < X1);
 186
 187     if ((x2 < X1) || (x1 > X2))
 188     {
 189         fprintf(stderr, "find_intersection - NON-OVERLAPPING! (%d, %d) vs (%d, %d)\n",
 190             x1, x2, X1, X2);
 191         if (xEndsFirst && xStartsFirst)
 192         { *res1 = X1;   *res2 = x2; }
 193         else
 194         { *res1 = x1;   *res2 = X2; }
 195
 196         return(FALSE);
 197     }
 198     if (xEndsFirst) *res2 = x2;
 199     else            *res2 = X2;
 200
 201     if (xStartsFirst) *res1 = X1;
 202     else              *res1 = x1;
 203
 204     return(TRUE);
 205 }
 206 /*-------------------------------------------------------------------------------------*/
 207 range *create_range(srg, n)
 208     srange *srg;
 209     net *n;
 210 {
 211     /* This function serves the significant purpose of updating the tile/arc structure
 212        to include the <srg> and what side it occurs on.  This information is terribly
 213        useful  for figuring out how to resolve overlapping ranges. */
 214     range *r = (range *)calloc(1, sizeof(range));
 215     r->sr = srg;
 216     r->n = n;
 217     r->corners = NULL;
 218     r->use = r->flag = NULL;
 219
 220     return(r);
 221 }
 222 /*-------------------------------------------------------------------------------------*/
 223 range *quick_copy_range(oldR)
 224     range *oldR;
 225 {
 226     /* Make a new copy of <oldR> */
 227     range *r = (range *)calloc(1, sizeof(range));
 228     r->sr = oldR->sr;
 229     r->n = oldR->n;
 230     r->corners = oldR->corners;                 /* Not quite right, but...*/
 231     r->use = oldR->use;
 232     r->flag = oldR->flag;
 233
 234     return(r);
 235 }
 236 /*-------------------------------------------------------------------------------------*/
 237 range *copy_range(oldR)
 238     range *oldR;
 239 {
 240     /* Make a new copy of <oldR> */
 241     range *r = (range *)calloc(1, sizeof(range));
 242     r->sr = create_srange(oldR->sr->q1, oldR->sr->q2, oldR->sr->orient);
 243     r->n = oldR->n;
 244     r->corners = NULL;
 245     r->use = oldR->use;
 246     r->flag = oldR->flag;
 247
 248     return(r);
 249 }
 250 /*-------------------------------------------------------------------------------------*/
 251 int some_overlap_p(a1, a2, b1, b2)
 252     int a1, a2, b1, b2;
 253 {
 254     if ((a1 <= b2) && (a2 >= b1)) return(TRUE);
 255     else return(FALSE);
 256 }
 257 /*-------------------------------------------------------------------------------------*/
 258 int midpoint(range *rng)
 259 {
 260     return(  (rng->sr->q1 + rng->sr->q2 + 1) / 2 );
 261 }
 262 /* NOTE: The "+1" is a hack to insure that narrow tiles that are saught via some
 263    spanning range (See replace_corner_instance for an example) can be located
 264    (has to do with the fact that the left edge of a tile does not 'locate' it,
 265    whereas the right edge does - the SLIVER bug bites again!)   */
 266 /*-------------------------------------------------------------------------------------*/
 267 int corner_falls_in_arc_p(c, a)
 268     corner *c;
 269     asg_arc *a;
 270 {
 271     int b1 = a->t->y_pos, b2 = a->t->y_pos + a->t->y_len;
 272     int d1 = a->t->x_pos, d2 = a->t->x_pos + a->t->x_len;
 273
 274     if ((a->page == HORZ) &&
 275         ((some_overlap_p(b1, b2, c->cy->sr->q1,  c->cy->sr->q2) == FALSE) ||
 276          (d1 > c->cx->sr->q1) || (d2 < c->cx->sr->q2)))
 277     {
 278         return(FALSE);
 279     }
 280     else if ((a->page == VERT) &&
 281         ((some_overlap_p(b1, b2, c->cx->sr->q1,  c->cx->sr->q2) == FALSE) ||
 282          (d1 > c->cy->sr->q1) || (d2 < c->cy->sr->q2)))
 283     {
 284         return(FALSE);
 285     }
 286     else return (TRUE);
 287 }
 288
 289 /*-------------------------------------------------------------------------------------*/
 290 int add_corner_to_arc(c, a)
 291     corner *c;
 292     asg_arc *a;
 293 {
 294     int b1 = a->t->y_pos, b2 = a->t->y_pos + a->t->y_len;
 295     int d1 = a->t->x_pos, d2 = a->t->x_pos + a->t->x_len;
 296
 297     if ((corner_falls_in_arc_p(c,a) == FALSE) || (a->mod != NULL))
 298     {
 299         if (a->mod != NULL)
 300         {
 301             fprintf(stderr, "Attempt to add corner of net %s to module %s rejected!!\n",
 302                     c->cx->n->name, a->mod->name);
 303         }
 304         if ((a->page == HORZ) && (debug_level > 0))
 305         {
 306             fprintf(stderr, "([%d,%d],[%d,%d])Corner addition screwed...HORZ\n",
 307                     c->cx->sr->q1, c->cx->sr->q2, c->cy->sr->q1, c->cy->sr->q2);
 308         }
 309         else if ((a->page == VERT) && (debug_level > 0))
 310         {
 311             fprintf(stderr, "([%d,%d],[%d,%d])Corner addition screwed...VERT\n",
 312                     c->cx->sr->q1, c->cx->sr->q2, c->cy->sr->q1, c->cy->sr->q2);
 313         }
 314         return(FALSE);
 315     }
 316     else
 317     {
 318         pushnew(a, &c->al);
 319         pushnew(c, &a->corners);
 320         pushnew(c->cx->n, &a->nets);
 321         return(TRUE);
 322     }
 323 }
 324 /*-------------------------------------------------------------------------------------*/
 325 int pull_corner_from_arc(c, a)
 326     corner *c;
 327     asg_arc *a;
 328 {
 329     int b1 = a->t->y_pos, b2 = a->t->y_pos + a->t->y_len;
 330     int d1 = a->t->x_pos, d2 = a->t->x_pos + a->t->x_len;
 331
 332     if (corner_falls_in_arc_p(c,a) == TRUE)
 333     {
 334         if ((a->page == HORZ) && (debug_level > 0))
 335         {
 336             fprintf(stderr, "([%d,%d],[%d,%d])Corner removal screwed...HORZ\n",
 337                     c->cx->sr->q1, c->cx->sr->q2, c->cy->sr->q1, c->cy->sr->q2);
 338         }
 339         else if ((a->page == VERT) && (debug_level > 0))
 340         {
 341             fprintf(stderr, "([%d,%d],[%d,%d])Corner removal screwed...VERT\n",
 342                     c->cx->sr->q1, c->cx->sr->q2, c->cy->sr->q1, c->cy->sr->q2);
 343         }
 344         return(FALSE);
 345     }
 346     else
 347     {
 348         rem_item(a, &c->al);
 349         rem_item(c, &a->corners);
 350         rem_item(c->cx->n, &a->nets);
 351         return(TRUE);
 352     }
 353 }
 354 /*-------------------------------------------------------------------------------------*/
 355 corner *create_corner(rX, rY, a, ter)
 356     range *rX, *rY;
 357     asg_arc *a;
 358     term *ter;
 359 {
 360     tile *t;
 361
 362     corner *c = (corner *)calloc(1, sizeof(corner));
 363     c->cx = rX;
 364     c->cy = rY;
 365     c->vertOrder = c->horzOrder = 5000;
 366     c->al = NULL;
 367     c->t = ter;         /* Specialized use */
 368
 369     if (a != NULL) add_corner_to_arc(c, a);  /* Add to the arc we expect <c> to be in. */
 370
 371     pushnew(c, &rX->corners);
 372     pushnew(c, &rY->corners);
 373     return(c);
 374 }
 375 /*-------------------------------------------------------------------------------------*/
 376 corner *set_corner_point(n, curTile, prevTile, xlink, ylink, refX, refY)
 377     net *n;
 378     tile *curTile, *prevTile;
 379     range *xlink, *ylink;       /* Typically only one is set. */
 380     int refX, refY;
 381 {
 382     /* This procedure analyzes how <curTile> overlaps with <prevTile>, and sets up
 383        the ranges for the placement of the corner points (<cornerX>, <cornerY>).
 384        If either link is set, it is tied in. */
 385
 386     /* The X and Y designations are relative to the HORZ page set. */
 387
 388     range *cornerX, *cornerY;
 389     asg_arc *Carc = (asg_arc *)curTile->this, *Parc = (asg_arc *)prevTile->this;
 390     int Cpage = Carc->page, Ppage = Parc->page;
 391     int q1, q2, q3, q4, side;
 392
 393     side = determine_entry_side(Parc, Carc, refX, refY);
 394
 395     if (ylink != NULL)
 396     {
 397         if (xlink != NULL)
 398         {
 399             /* odd use... */
 400             cornerX = xlink;
 401             cornerY = ylink;
 402             return(create_corner(cornerX, cornerY, Carc, NULL));
 403         }
 404
 405         else /* Use the <ylink>, calculate the <cornerX>: */
 406         {
 407             if ((Cpage == HORZ) && (Ppage == VERT))
 408             {
 409                 find_intersection(curTile->x_pos, curTile->x_pos + curTile->x_len,
 410                                   prevTile->y_pos, prevTile->y_pos + prevTile->y_len,
 411                                   &q1, &q2);
 412             }
 413             else if ((Cpage == VERT) && (Ppage == HORZ))
 414             {
 415                 find_intersection(curTile->y_pos, curTile->y_pos + curTile->y_len,
 416                                   prevTile->x_pos, prevTile->x_pos + prevTile->x_len,
 417                                   &q1, &q2);
 418             }
 419             else if (Cpage == HORZ)
 420             {
 421                 find_intersection(curTile->x_pos, curTile->x_pos + curTile->x_len,
 422                                   prevTile->x_pos, prevTile->x_pos + prevTile->x_len,
 423                                   &q1, &q2);
 424             }
 425             else /* (Cpage == VERT) */
 426             {
 427                 find_intersection(curTile->y_pos, curTile->y_pos + curTile->y_len,
 428                                   prevTile->y_pos, prevTile->y_pos + prevTile->y_len,
 429                                   &q1, &q2);
 430             }
 431             cornerX = create_range(create_srange(q1,q2,Cpage), n);
 432             cornerY = ylink;
 433             return(create_corner(cornerX, cornerY, Carc, NULL));
 434         }
 435     }
 436
 437     else if (xlink != NULL)
 438     {
 439         /* Use the <xlink>, calculate the <cornerY>: */
 440         if ((Cpage == VERT) && (Ppage == HORZ))
 441         {
 442             find_intersection(curTile->x_pos, curTile->x_pos + curTile->x_len,
 443                               prevTile->y_pos, prevTile->y_pos + prevTile->y_len,
 444                               &q3, &q4);
 445         }
 446         else if ((Cpage == HORZ) && (Ppage == VERT))
 447         {
 448             find_intersection(curTile->y_pos, curTile->y_pos + curTile->y_len,
 449                               prevTile->x_pos, prevTile->x_pos + prevTile->x_len,
 450                               &q3, &q4);
 451         }
 452         else if (Cpage == VERT)
 453         {
 454             find_intersection(curTile->x_pos, curTile->x_pos + curTile->x_len,
 455                               prevTile->x_pos, prevTile->x_pos + prevTile->x_len,
 456                               &q3, &q4);
 457         }
 458         else
 459         {
 460             find_intersection(curTile->y_pos, curTile->y_pos + curTile->y_len,
 461                               prevTile->y_pos, prevTile->y_pos + prevTile->y_len,
 462                               &q3, &q4);
 463         }
 464         cornerY = create_range(create_srange(q3,q4,Cpage), n);
 465         cornerX = xlink;
 466         return(create_corner(cornerX, cornerY, Carc, NULL));
 467     }
 468
 469     else /* No links - create both corners... Also Strange usage...*/
 470     {
 471         if ((Cpage == HORZ) && (Ppage == VERT))
 472         {
 473             find_intersection(curTile->x_pos, curTile->x_pos + curTile->x_len,
 474                               prevTile->y_pos, prevTile->y_pos + prevTile->y_len,
 475                               &q1, &q2);
 476             find_intersection(curTile->y_pos, curTile->y_pos + curTile->y_len,
 477                               prevTile->x_pos, prevTile->x_pos + prevTile->x_len,
 478                               &q3, &q4);
 479         }
 480         else if ((Cpage == VERT) && (Ppage == HORZ))
 481         {
 482             find_intersection(curTile->y_pos, curTile->y_pos + curTile->y_len,
 483                               prevTile->x_pos, prevTile->x_pos + prevTile->x_len,
 484                               &q1, &q2);
 485             find_intersection(curTile->x_pos, curTile->x_pos + curTile->x_len,
 486                               prevTile->y_pos, prevTile->y_pos + prevTile->y_len,
 487                               &q3, &q4);
 488         }
 489         else if (Cpage == HORZ)
 490         {
 491             find_intersection(curTile->x_pos, curTile->x_pos + curTile->x_len,
 492                               prevTile->x_pos, prevTile->x_pos + prevTile->x_len,
 493                               &q1, &q2);
 494             find_intersection(curTile->y_pos, curTile->y_pos + curTile->y_len,
 495                               prevTile->y_pos, prevTile->y_pos + prevTile->y_len,
 496                               &q3, &q4);
 497         }
 498         else /* (Cpage == VERT) */
 499         {
 500             find_intersection(curTile->y_pos, curTile->y_pos + curTile->y_len,
 501                               prevTile->y_pos, prevTile->y_pos + prevTile->y_len,
 502                               &q1, &q2);
 503             find_intersection(curTile->x_pos, curTile->x_pos + curTile->x_len,
 504                               prevTile->x_pos, prevTile->x_pos + prevTile->x_len,
 505                               &q3, &q4);
 506         }
 507
 508 /* sides get screwed up badly.  ?? */
 509         cornerX = create_range(create_srange(q1,q2,Cpage), n);
 510         cornerY = create_range(create_srange(q3,q4,Cpage), n);
 511         return(create_corner(cornerX, cornerY, Carc, NULL));
 512     }
 513 }
 514 /*-------------------------------------------------------------------------------------*/
 515 /*-------------------------------------------------------------------------------------*/
 516 int map_net_into_constraint_sets(n)
 517     net *n;
 518 {
 519     /* This function walks along the global route assigned to the given net, assigning
 520      * constraints to the various corners detected.  This involves the creation of srange
 521      * structures that will be resolved into points.
 522
 523      * To determine which global route is to be used, check each expansion:
 524      * If the expansions belonging to the net have been properly terminated, then
 525      * there is a single (shared) list of trails that comprise the net.
 526
 527      * There is no guarantee that there is not any overlap abongst these trails */
 528
 529
 530      /* There are several conditions for these jointArcs that determine how the
 531         ranges should be set up and linked:  First, a jointArc may be shared by
 532         several (more than two) expansions (Rat's Nest condition);
 533         Secondly, a joint arc may occur as a non-joint tile in the middle of another
 534         path (T condition) and lastly a jointArc may be shared by two expansions
 535         (Simple Connection).
 536         */
 537
 538      expn *ex = (expn *)n->done->this;
 539      trail *besTrail;
 540      trlist *trl;
 541      tilist *temp, *tl, *tll;
 542      tile *lasTile, *thisTile;
 543      asg_arc *ar, *lar;
 544      range *xlink = NULL, *ylink = NULL;
 545      corner *c;
 546      int refX, refY;
 547
 548      for (trl = ex->connections; trl != NULL; trl = trl->next)
 549      {
 550          besTrail = trl->this;
 551          ex = besTrail->ex;
 552
 553          /* Walk along the trail, starting at the source terminal: */
 554          /* Need to maintain a reference point, and the link ranges <xlink> & <ylink> */
 555          /* Assume that the starting tile (<lasTile>) has HORZonatal orientation. */
 556          temp = (tilist *)rcopy_list(besTrail->tr);
 557          lasTile = temp->this;
 558          ar = (asg_arc *)lasTile->this;
 559          refX = ex->t->x_pos + ex->t->mod->x_pos;
 560          refY = ex->t->y_pos + ex->t->mod->y_pos;
 561          /* This is a terminal point, and should not be added to the VERT tile space.. */
 562          c = create_corner(create_range(create_srange(refX, refX, VERT), n),
 563                            create_range(create_srange(refY, refY, HORZ), n),
 564                            ar, ex->t);
 565          push(c, &besTrail->used);
 566          pushnew(lasTile, &n->route);
 567
 568          for (tl = temp->next; tl != NULL; tl = tl->next)
 569          {
 570              thisTile = tl->this;
 571              ar = (asg_arc *)thisTile->this;            lar = (asg_arc *)lasTile->this;
 572
 573              /* Standard Linkage control: */
 574              if ( ((asg_arc *)(thisTile->this))->page == VERT )
 575              {
 576                  ylink = c->cy; xlink = NULL;
 577              }
 578              else
 579              {
 580                  xlink = c->cx; ylink = NULL;
 581              }
 582
 583              /* At the intersection of <lasTile> & <thisTile>, set a corner point. */
 584              c = set_corner_point(n, thisTile, lasTile, xlink, ylink, refX, refY);
 585              refX = midpoint(c->cx);
 586              refY = midpoint(c->cy);
 587              add_corner_to_arc(c, lar);
 588              push(c, &besTrail->used);
 589              pushnew(thisTile, &n->route);
 590
 591              lasTile =  thisTile;       /* Advance the window... */
 592          }
 593          /* Now that the loop is done, <lasTile> should point to the the <joinTile>
 594             for this trail. */
 595          free_list(temp);
 596     }
 597 }
 598 /*------------------------------------------------------------------------------------*/
 599 int in_congestion_order(t1, t2)
 600     tile *t1, *t2;
 601 {
 602     asg_arc *a1 = (asg_arc *)t1->this, *a2= (asg_arc *)t2->this;
 603
 604     /* Return TRUE if <t1> has a higher congestion than <t2>. */
 605 /*     if (a1->congestion >= a2->congestion) return(TRUE);  */
 606     if (list_length(a1->corners) < list_length(a2->corners)) return(FALSE);
 607     else if (a1->congestion >= a2->congestion) return(TRUE);
 608     else return(TRUE);
 609 }
 610 /*------------------------------------------------------------------------------------*/
 611 int int_overlapped_p(min1, max1, min2, max2)
 612     int min1, max1, min2, max2;
 613 {
 614     /* This returns true if there is overlap between the ranges r1 & r2: */
 615     if (((max1 >= min2) && (min1 <= max2)) ||
 616          ((min1 <= max2) && (max1 >= min2))) return(TRUE);
 617     else return(FALSE);
 618 }
 619 /*------------------------------------------------------------------------------------*/
 620 int overlapped_p(r1, r2)
 621     srange *r1, *r2;
 622 {
 623     /* This returns true if there is overlap between the ranges r1 & r2: */
 624     if (r1->orient == r2->orient)
 625         return(int_overlapped_p(r1->q1, r1->q2, r2->q1, r2->q2));
 626     else return(FALSE);
 627 }
 628 /*------------------------------------------------------------------------------------*/
 629 corner *next_vert_corner(c)
 630     corner *c;
 631 {
 632     /* return the next corner in the vertical direction.  This is meant to be
 633        pumped for info;  If NULL is passed in, the last <c> given is used again.. */
 634     static crnlist *cl = NULL;
 635     static corner *oldC = NULL;
 636
 637     if ((int)c == VERT) return(oldC);
 638     else if (c != NULL)
 639     {
 640         cl = c->cx->corners;
 641         oldC = c;
 642     }
 643     else c = oldC;
 644
 645     for (; cl != NULL; cl = cl->next)
 646     {
 647         if (cl->this != c)
 648         {
 649             if(cl->this->cy->n  == c->cy->n)
 650             {
 651                 c = cl->this;
 652                 cl = cl->next;    /* Advance <cl> so we can restart where we left off */
 653                 return(c);
 654             }
 655         }
 656     }
 657     return(c);          /* Somethin's probably screwed... */
 658 }
 659 /*------------------------------------------------------------------------------------*/
 660 corner *next_horz_corner(c)
 661     corner *c;
 662 {
 663     /* return the next corner in the horizontal direction.This is meant to be
 664        pumped for info;  If NULL is passed in, the last <c> given is used again.. */
 665     static crnlist *cl = NULL;
 666     static corner *oldC = NULL;
 667
 668     if ((int)c == HORZ) return(oldC);   /* Special action */
 669     else if (c != NULL)
 670     {
 671         cl = c->cy->corners;
 672         oldC = c;
 673     }
 674     else c = oldC;
 675
 676     for (; cl != NULL; cl = cl->next)
 677     {
 678         if (cl->this != c)
 679         {
 680             if(cl->this->cx->n == c->cx->n)
 681             {
 682                 c = cl->this;
 683                 cl = cl->next;    /* Advance <cl> so we can restart where we left off */
 684                 return(c);
 685             }
 686         }
 687     }
 688     return(c);          /* Somethin's probably screwed... */
 689 }
 690 /*------------------------------------------------------------------------------------*/
 691 int in_x_order(c1, c2)
 692     corner *c1, *c2;
 693 {
 694     if (c1->cx->sr->q1 < c2->cx->sr->q1) return(TRUE);
 695     else return(FALSE);
 696 }
 697 /*------------------------------------------------------------------------------------*/
 698 int in_y_order(c1, c2)
 699     corner *c1, *c2;
 700 {
 701     if (c1->cy->sr->q1 < c2->cy->sr->q1) return(TRUE);
 702     else return(FALSE);
 703 }
 704 /*------------------------------------------------------------------------------------*/
 705 corner *most_vert_corner(c)
 706     corner *c;
 707 {
 708     /* return the next corner, that is highest in the vertical direction. */
 709     corner *largest = c;
 710     crnlist *cl = NULL;
 711
 712     if (c != NULL)
 713     {
 714         cl = c->cx->corners;
 715     }
 716     for (; cl != NULL; cl = cl->next)
 717     {
 718         if((cl->this->cy->n  == c->cy->n)  &&
 719            (cl->this->cy->sr->q2 > largest->cy->sr->q2))  largest = cl->this;
 720     }
 721     return(largest);
 722 }
 723 /*------------------------------------------------------------------------------------*/
 724 corner *least_vert_corner(c)
 725     corner *c;
 726 {
 727     /* return the next corner, that is lowest in the vertical direction. */
 728     corner *smallest = c;
 729     crnlist *cl = NULL;
 730
 731     if (c != NULL)
 732     {
 733         cl = c->cx->corners;
 734     }
 735     for (; cl != NULL; cl = cl->next)
 736     {
 737         if((cl->this->cy->n  == c->cy->n)  &&
 738            (cl->this->cy->sr->q1 < smallest->cy->sr->q1))  smallest = cl->this;
 739     }
 740     return(smallest);
 741 }
 742 /*------------------------------------------------------------------------------------*/
 743 corner *most_horz_corner(c)
 744     corner *c;
 745 {
 746     /* return the next corner, that is highest in the horizontal direction. */
 747     corner *largest = c;
 748     crnlist *cl = NULL;
 749
 750     if (c != NULL)
 751     {
 752         cl = c->cy->corners;
 753     }
 754     for (; cl != NULL; cl = cl->next)
 755     {
 756         if((cl->this->cx->n  == c->cx->n)  &&
 757            (cl->this->cx->sr->q2 > largest->cx->sr->q2))  largest = cl->this;
 758     }
 759     return(largest);
 760 }
 761 /*------------------------------------------------------------------------------------*/
 762 corner *least_horz_corner(c)
 763     corner *c;
 764 {
 765     /* return the next corner, that is lowest in the horizontal direction. */
 766     corner *smallest = c;
 767     crnlist *cl = NULL;
 768
 769     if (c != NULL)
 770     {
 771         cl = c->cy->corners;
 772     }
 773     for (; cl != NULL; cl = cl->next)
 774     {
 775         if((cl->this->cy->n  == c->cy->n)  &&
 776            (cl->this->cx->sr->q1 <  smallest->cx->sr->q1))  smallest = cl->this;
 777     }
 778     return(smallest);
 779 }
 780 /*------------------------------------------------------------------------------------*/
 781 /*------------------------------------------------------------------------------------*/
 782 int forms_T_p(c)
 783     corner *c;
 784 {
 785     crnlist *cl;
 786
 787     /* This returns VERT if <c> is the center of a vertical T, and HORZ if it is
 788        the center of a horizontal T.  Otherwise, it returns FALSE. */
 789
 790     /* If <c> has multiple (3 or more) points at the same y value, and <c> is more
 791        than just a single point: */
 792     if ((list_length(c->cy->corners) > 2) && (list_length(c->cx->corners) > 1))
 793     {
 794
 795         /* There is something worth looking at: */
 796         cl = (crnlist *)sort_list(c->cy->corners, in_x_order);
 797
 798         if (cl->next->this == c)
 799         {
 800             return(TRUE);
 801         }
 802
 803         for (cl = cl->next; ((cl != NULL) && (cl->this != c) && (cl->next != NULL));
 804              cl = cl->next)
 805         {
 806             if ((cl->next->this == c) && (cl->next->next != NULL))
 807             {
 808                 return(TRUE);
 809             }
 810         }
 811     }
 812
 813     /* Not this axis, so now check the Y axis: */
 814     /* If <c> has multiple (3 or more) points at the same x value, and <c> is more
 815        than just a single point: */
 816     if ((list_length(c->cx->corners) > 2) && (list_length(c->cy->corners) > 1))
 817     {
 818         /* There is something worth looking at: */
 819         cl = (crnlist *)sort_list(c->cx->corners, in_y_order);
 820
 821         if (cl->next->this == c)
 822         {
 823             return(TRUE);
 824         }
 825
 826         for (cl = cl->next; ((cl != NULL) && (cl->this != c) && (cl->next != NULL));
 827              cl = cl->next)
 828         {
 829             if ((cl->next->this == c) && (cl->next->next != NULL))
 830             {
 831                 return(TRUE);
 832             }
 833         }
 834     }
 835     return(FALSE);
 836 }
 837 /*------------------------------------------------------------------------------------*/
 838 int turns_up_p(c)
 839     corner *c;
 840 {
 841     /* Returns TRUE iff this corner represents an upward turn.  This is rather tricky,
 842      and is highly dependent on the vaguarities of the "next_vert_corner" function. */
 843     corner *nextY = next_vert_corner(c);
 844     range *r, *nextR;
 845
 846     if (c == NULL) c = next_vert_corner(VERT);   /* Get the old C for comparison */
 847     if (c == nextY)  return(FALSE);     /* (No turns) */
 848
 849     r = c->cy;
 850     nextR = nextY->cy;
 851
 852     /* if <r> is below <nextR> then return TRUE. */
 853     if ((r == NULL) || (nextR == NULL))
 854     {
 855         fprintf(stderr, "Major screwup 'in turns_up_p'\n");
 856         return(FALSE);
 857     }
 858     else if (r->sr->q2 < nextR->sr->q1) return(TRUE);
 859     else return(turns_up_p(NULL));                  /* Pump the "next_horz_corner" fn */
 860 }
 861 /*------------------------------------------------------------------------------------*/
 862 int turns_right_p(c)
 863     corner *c;
 864 {
 865     /* Returns TRUE iff this corner represents an right turn.  This is rather tricky,
 866      and is highly dependent on the vaguarities of the "next_horz_corner" function. */
 867     corner *nextX = next_horz_corner(c);
 868     range *r, *nextR;
 869
 870     if (c == NULL) c = next_horz_corner(HORZ);   /* Get the old C for comparison */
 871     if (c == nextX)  return(FALSE);     /* (No turns) */
 872
 873     r = c->cx;
 874     nextR = nextX->cx;
 875
 876     /* if <r> is below <nextR> then return TRUE. */
 877     if ((r == NULL) || (nextR == NULL))
 878     {
 879         fprintf(stderr, "Major screwup 'in turns_right_p'\n");
 880         return(FALSE);
 881     }
 882     else if (r->sr->q2 < nextR->sr->q1) return(TRUE);
 883     else return(turns_right_p(NULL));               /* Pump the "next_horz_corner" fn */
 884 }
 885 /*------------------------------------------------------------------------------------*/
 886 /*------------------------------------------------------------------------------------*/
 887 int form_vertical_ordering(c1, c2)
 888     corner *c1, *c2;
 889 {
 890     /* RULE 1:  bends gravitate toward the corner in the direction of the turn.
 891        RULE 2:  T's are placed on the side of the off-angle.
 892        RULE 3:  Throughs & jogs gravitate toward the center of the area.
 893      */
 894     /* Returns TRUE iff <c1> should be placed above <c2> in the same box.  This
 895        fact depends on the context in which <c1> occurs within it's net, and <c2>
 896        occurs within its net. */
 897
 898     range *r1, *r2;
 899     corner *nextC1, *nextC2;
 900     int hOrder;
 901     int c1LeftMost, c1RightMost, c2LeftMost, c2RightMost;
 902
 903     if (c1 == NULL) return (FALSE);
 904     else if (c2 == NULL) return (TRUE);
 905     else
 906     {
 907         r1 = c1->cy;
 908         r2 = c2->cy;
 909
 910         /* Ignore corners beloning to the same net */
 911         if (r1->n == r2->n) return(FALSE);
 912
 913         /* First, check the simple case that there is no overlapp to resolve: */
 914         if (overlapped_p(r1->sr, r2->sr) == FALSE)
 915         {
 916             if (r1->sr->q1 > r2->sr->q1) return(TRUE);
 917             else return(FALSE);
 918         }
 919
 920         /* OK, there is vertical overlap to deal with, so... */
 921         /* Check to see if they turn in opposite directions: */
 922         c1RightMost = turns_up_p(most_horz_corner(c1));
 923         c1LeftMost = turns_up_p(least_horz_corner(c1));
 924         c2RightMost = turns_up_p(most_horz_corner(c2));
 925         c2LeftMost = turns_up_p(least_horz_corner(c2));
 926
 927         if ((c1RightMost == TRUE) && (c2RightMost == FALSE)) return(TRUE);
 928         else if ((c1RightMost == FALSE) && (c2RightMost == TRUE)) return(FALSE);
 929         else if ((c1LeftMost == TRUE) && (c2LeftMost == FALSE)) return(TRUE);
 930         else if ((c1LeftMost == FALSE) && (c2LeftMost == TRUE)) return(FALSE);
 931         else    /* They both turn the same way */
 932         {
 933             /* special case for T's */
 934
 935             /* look again... */
 936             /* Look along the X Axis to see where the next corners are.  If the turn
 937                of the next corners is opposite, that is one turns up, while the other
 938                turns down, then the resolution is complete.  The net that turns up gets
 939                placed above the net that turns down. */
 940
 941             nextC1 = next_horz_corner(c1);
 942             nextC2 = next_horz_corner(c2);
 943
 944             if ((nextC1 == c1) && (nextC2 == c2))
 945             {
 946                 /* Terminal points;  look the other way */
 947                 nextC1 = next_vert_corner(c1);
 948                 nextC2 = next_vert_corner(c2);
 949
 950                 if ((nextC1 != c1) && (nextC2 != c2))
 951                 {
 952                     return(form_vertical_ordering(nextC1, nextC2));
 953                 }
 954                 else if (c1->cx->sr->q2 < c2->cx->sr->q1) return(FALSE);
 955                 else return(TRUE);
 956             }
 957             else
 958             {
 959                 /* Check to see if they turn in opposite directions: */
 960                 c1RightMost = turns_up_p(most_horz_corner(nextC1));
 961                 c1LeftMost = turns_up_p(least_horz_corner(nextC1));
 962                 c2RightMost = turns_up_p(most_horz_corner(nextC2));
 963                 c2LeftMost = turns_up_p(least_horz_corner(nextC2));
 964
 965                 if ((c1RightMost == TRUE) && (c2RightMost == FALSE)) return(TRUE);
 966                 else if ((c1RightMost == FALSE) && (c2RightMost == TRUE)) return(FALSE);
 967                 else if ((c1LeftMost == TRUE) && (c2LeftMost == FALSE)) return(TRUE);
 968                 else if ((c1LeftMost == FALSE) && (c2LeftMost == TRUE)) return(FALSE);
 969                 else
 970                 {
 971                     /* The next corners also both turn the same way */
 972                     if (debug_level > 2)
 973                     {
 974                         fprintf(stderr, "recursion in form_vertical_ordering ");
 975                         fprintf(stderr, "<%s>([%d, %d],[%d,%d]) and ", c1->cx->n->name,
 976                                 c1->cx->sr->q1, c1->cx->sr->q2,
 977                                 c1->cy->sr->q1, c1->cy->sr->q2);
 978
 979                         fprintf(stderr, "<%s>([%d, %d],[%d,%d])\n", r2->n->name,
 980                                 c2->cx->sr->q1, c2->cx->sr->q2,
 981                                 c2->cy->sr->q1, c2->cy->sr->q2);
 982                     }
 983                     hOrder = form_horizontal_ordering(nextC1, nextC2);
 984                     if (c1RightMost == TRUE) return( NOT(hOrder) );
 985                     else if (c1LeftMost == TRUE) return( NOT(hOrder) );
 986                     else return (hOrder);
 987                 }
 988             }
 989         }
 990     }
 991 }
 992 /*------------------------------------------------------------------------------------*/
 993 /*------------------------------------------------------------------------------------*/
 994 int form_horizontal_ordering(c1, c2)
 995     corner *c1, *c2;
 996 {
 997      /* RULE 1:  bends gravitate toward the corner in the direction of the turn.
 998         RULE 2:  T's are placed on the side of the off-angle.
 999         RULE 3:  Throughs & jogs gravitate toward the center of the area.
1000      */
1001
1002     /* Returns TRUE iff <c1> should be placed to the left of <c2> in the same box.  This
1003        fact depends on the context in which <c1> occurs within it's net, and <c2>
1004        occurs within its net. */
1005     range *r1, *r2;
1006     corner *nextC1, *nextC2;
1007     int vOrder;
1008     int c1TopMost, c1BotMost, c2TopMost, c2BotMost;
1009
1010     if (c1 == NULL) return (FALSE);
1011     else if (c2 == NULL) return (TRUE);
1012     else
1013     {
1014         r1 = c1->cx;
1015         r2 = c2->cx;
1016
1017         /* Ignore corners beloning to the same net */
1018         if (r1->n == r2->n) return(FALSE);
1019
1020         /* First, check the simple case that there is no overlapp to resolve: */
1021         if (overlapped_p(r1->sr, r2->sr) == FALSE)
1022         {
1023             if (r1->sr->q1 > r2->sr->q1) return(FALSE);
1024             else return(TRUE);
1025         }
1026
1027         /* OK, there is vertical overlap to deal with, so... */
1028         /* Check to see if they turn in opposite directions: */
1029         c1TopMost = turns_right_p(most_vert_corner(c1));
1030         c1BotMost = turns_right_p(least_vert_corner(c1));
1031         c2TopMost = turns_right_p(most_vert_corner(c2));
1032         c2BotMost = turns_right_p(least_vert_corner(c2));
1033
1034         if ((c1TopMost == TRUE) && (c2TopMost == FALSE)) return(TRUE);
1035         else if ((c1TopMost == FALSE) && (c2TopMost == TRUE)) return(FALSE);
1036         else if ((c1BotMost == TRUE) && (c2BotMost == FALSE)) return(TRUE);
1037         else if ((c1BotMost == FALSE) && (c2BotMost == TRUE)) return(FALSE);
1038         else    /* They both turn the same way */
1039         {
1040             /* special case for T's */
1041
1042             /* look again... */
1043             /* Look along the Y Axis to see where the next corners are.  If the turn
1044                of the next corners is opposite, that is one turns up, while the other
1045                turns down, then the resolution is complete.  The net that turns up gets
1046                placed above the net that turns down. */
1047
1048             nextC1 = next_vert_corner(c1);
1049             nextC2 = next_vert_corner(c2);
1050             if ((nextC1 == c1) && (nextC2 == c2))
1051             {
1052                 /* Terminal points;  look the other way */
1053                 nextC1 = next_horz_corner(c1);
1054                 nextC2 = next_horz_corner(c2);
1055
1056                 if ((nextC1 != c1) && (nextC2 != c2))
1057                 {
1058                     return(form_horizontal_ordering(nextC1, nextC2));
1059                 }
1060                 else if (c1->cy->sr->q2 < c2->cy->sr->q1) return(FALSE);
1061                 else return(TRUE);
1062
1063             }
1064             else
1065             {
1066                 /* Check to see if they turn in opposite directions: */
1067                 c1TopMost = turns_right_p(most_vert_corner(nextC1));
1068                 c1BotMost = turns_right_p(least_vert_corner(nextC1));
1069                 c2TopMost = turns_right_p(most_vert_corner(nextC2));
1070                 c2BotMost = turns_right_p(least_vert_corner(nextC2));
1071
1072                 if ((c1TopMost == TRUE) && (c2TopMost == FALSE)) return(TRUE);
1073                 else if ((c1TopMost == FALSE) && (c2TopMost == TRUE)) return(FALSE);
1074                 else if ((c1BotMost == TRUE) && (c2BotMost == FALSE)) return(TRUE);
1075                 else if ((c1BotMost == FALSE) && (c2BotMost == TRUE)) return(FALSE);
1076                 else
1077                 {
1078                     /* The next corners also turn the same way */
1079                     /* dangerous */
1080                     if (debug_level > 2)
1081                     {
1082                         fprintf(stderr, "recursion in form_horzontal_ordering ");
1083                         fprintf(stderr, "<%s>([%d, %d],[%d,%d]) and ", c1->cx->n->name,
1084                                 c1->cx->sr->q1, c1->cx->sr->q2,
1085                                 c1->cy->sr->q1, c1->cy->sr->q2);
1086
1087                         fprintf(stderr, "<%s>([%d, %d],[%d,%d])\n", r2->n->name,
1088                                 c2->cx->sr->q1, c2->cx->sr->q2,
1089                                 c2->cy->sr->q1, c2->cy->sr->q2);
1090                     }
1091                     vOrder = form_vertical_ordering(nextC1, nextC2);
1092                     if (c1TopMost == TRUE) return (vOrder);
1093                     else if (c1BotMost == TRUE) return (vOrder);
1094                     else return( NOT(vOrder) );
1095                 }
1096             }
1097         }
1098     }
1099 }
1100 /*------------------------------------------------------------------------------------*/
1101 /*------------------------------------------------------------------------------------*/
1102 int in_vert_order(c1, c2)
1103     corner *c1, *c2;
1104 {
1105     if (c1->vertOrder >= c2->vertOrder) return(TRUE);
1106     else return(FALSE);
1107 }
1108 /*------------------------------------------------------------------------------------*/
1109 int in_horz_order(c1, c2)
1110     corner *c1, *c2;
1111 {
1112     if (c1->horzOrder <= c2->horzOrder) return(TRUE);
1113     else return(FALSE);
1114 }
1115 /*------------------------------------------------------------------------------------*/
1116 int best_vert_order(cl)
1117     crnlist *cl;
1118 {
1119     crnlist *cll;
1120     int min = 5000;
1121     for (cll = cl; cll != NULL; cll = cll->next)
1122     {
1123         min = MIN(min, cll->this->vertOrder);
1124     }
1125     return(min);
1126 }
1127 /*------------------------------------------------------------------------------------*/
1128 int best_horz_order(cl)
1129     crnlist *cl;
1130 {
1131     crnlist *cll;
1132     int min = 5000;
1133     for (cll = cl; cll != NULL; cll = cll->next)
1134     {
1135         min = MIN(min, cll->this->horzOrder);
1136     }
1137     return(min);
1138 }
1139 /*------------------------------------------------------------------------------------*/
1140 int in_reasonable_vert_orderR(r1, r2)
1141     range *r1, *r2;
1142 {
1143     /* indicates <r1> belongs above <r2> */
1144     crnlist *cl1 = r1->corners, *cl2 = r2->corners;
1145     int o1 = best_vert_order(cl1);
1146     int o2 = best_vert_order(cl2);
1147
1148     if ((o1 >= o2) && (r2->sr->q2 > r1->sr->q1)) return(TRUE);
1149     else return(FALSE);
1150 }
1151 /*------------------------------------------------------------------------------------*/
1152 int in_reasonable_horz_orderR(r1, r2)
1153     range *r1, *r2;
1154 {
1155     /* indicates <r1> belongs to the left of <r2> */
1156     crnlist *cl1 = r1->corners, *cl2 = r2->corners;
1157     int o1 = best_horz_order(cl1);
1158     int o2 = best_horz_order(cl2);
1159
1160     if ((o1 <= o2) && (r2->sr->q2 > r1->sr->q1)) return(TRUE);
1161     else return(FALSE);
1162 }
1163 /*------------------------------------------------------------------------------------*/
1164 int merge_sranges(sr1, sr2)
1165     srange **sr1, **sr2;                /* sranges associated that overlap */
1166 {
1167     /* This resolves <sr1> and <sr2> to the (same) smallest subset of the two. */
1168
1169     int min1 = (*sr1)->q1, min2 = (*sr2)->q1;
1170     int max1 = (*sr1)->q2, max2 = (*sr2)->q2;
1171     int min = MAX(min1, min2),   max = MIN(max1, max2);
1172     srange *temp;
1173
1174     /* if there is overlap, then do something... */
1175     if (((min1 >= min2) && (min1 <= max2)) ||
1176         ((min2 >= min1) && (min2 <= max1)))
1177     {
1178         (*sr1)->q1 = min;
1179         (*sr1)->q2 = max;
1180         temp = *sr2;
1181         *sr2 = *sr1;
1182         my_free(temp);
1183         return(TRUE);
1184     }
1185     return(FALSE);
1186 }
1187 /*------------------------------------------------------------------------------------*/
1188 int divide_sranges(sr1, sr2)
1189     srange *sr1, *sr2;           /* sranges associated with each net that overlap */
1190 {
1191     /* This puts <sr1> to the right of <sr2> */
1192     int midPoint;
1193     int min1 = sr1->q1, min2 = sr2->q1;
1194     int max1 = sr1->q2, max2 = sr2->q2;
1195
1196     if (min1 == max1) /* Handle the point cases - these are the most common */
1197     {
1198         if ((min2 == max2) && (min1 != min2)) return(TRUE);
1199         else if ((min2 == max2) && (min1 == min2)) return(FALSE);    /* Real Problem! */
1200
1201         if (max2 > min1)
1202         {
1203             if (min2 >= min1)
1204             {
1205                 sr2->q1 = MAX(min1 + 1, min2);  /* Not good */
1206                 return(FALSE);
1207             }
1208             else sr2->q2 = min1 - 1;
1209         }
1210         else sr2->q2 = MIN(min1 - 1, max2);
1211         return(TRUE);
1212     }
1213     else if (min2 == max2)
1214     {
1215         if (max1 >= min2)
1216         {
1217             if (min1 <= min2) sr1->q1 = min2 + 1;
1218             return(TRUE);
1219         }
1220         return(FALSE);
1221     }
1222     else
1223     {
1224         /* Is there any overlap? */
1225         if ((max1 < min2) || (min1 == max2)) return(FALSE);
1226         else if ((min1 > max2) || (max1 == min2)) return(TRUE);
1227
1228         midPoint = (max1 + min2) / 2;
1229
1230         /* Set the beginning/end points of the sranges: */
1231         if (max1 < midPoint)
1232         {
1233             sr1->q1 = max1;
1234             sr2->q2 = max1 - 1;
1235         }
1236         else if (min2 > midPoint)
1237         {
1238             sr1->q1 = min2;
1239             sr2->q2 = min2 + 1;
1240         }
1241         else if ( ((midPoint - 1) < min2) || ((max1 - min1) >= (max2 -min2)) )
1242         {
1243             sr1->q1 = MAX(min1, midPoint + 1);
1244             sr2->q2 = MIN(midPoint, max2);
1245         }
1246         else
1247         {
1248             sr1->q1 = MAX(min1, midPoint);
1249             sr2->q2 = MIN(midPoint - 1, max2);
1250         }
1251         return(TRUE);
1252     }
1253 }
1254
1255 /*------------------------------------------------------------------------------------*/
1256 int ranged_overlap_p(r1a, r2a, r1b, r2b)
1257     srange *r1a, *r2a, *r1b, *r2b;
1258 {
1259     /* This returns true if there is overlap between the line from [r1a to r2a] and
1260        the line from [r1b to r2b]: */
1261     int a1 = MIN(r1a->q1, r2a->q1), a2 = MAX(r1a->q2, r2a->q2);
1262     int startA = MIN(a1, a2),     endA = MAX(a1, a2);
1263     int b1 = MIN(r1b->q1, r2b->q1), b2 = MAX(r1b->q2, r2b->q2);
1264     int startB = MIN(b1, b2),     endB = MAX(b1, b2);
1265
1266     if ((endA < startB) || (startA > endB)) return(FALSE);
1267     else return(TRUE);
1268 }
1269 /*-------------------------------------------------------------------------------------*/
1270 int segments_overlapped_p(c1, c2, orient)
1271     corner *c1, *c2;
1272     int orient;
1273 {
1274     /* check to see if these two corners overlap in the given direction.  If so,
1275        return TRUE. */
1276
1277     crnlist *cl = (orient == Y) ? c1->cx->corners : c1->cy->corners;
1278     crnlist *cll, *clll = (orient == Y) ? c2->cx->corners : c2->cy->corners;
1279     srange *srA1, *srA2, *srB1, *srB2;
1280
1281     if (orient == X)
1282     {
1283         srA1 = c1->cx->sr;      srB1 = c1->cx->sr;
1284         if (overlapped_p(srA1, srB1) == TRUE) return(TRUE);
1285     }
1286     else /* (orient == Y) */
1287     {
1288         srA1 = c1->cy->sr;      srB1 = c2->cy->sr;
1289         if (overlapped_p(srA1, srB1) == TRUE) return(TRUE);
1290     }
1291
1292     for(; cl != NULL; cl = cl->next)
1293     {
1294         srA2 = (orient == X) ? cl->this->cx->sr : cl->this->cy->sr;
1295         for(cll = clll; cll != NULL; cll = cll->next)
1296         {
1297             srB2 = (orient == X) ? cll->this->cx->sr : cll->this->cy->sr;
1298             if (ranged_overlap_p(srA1, srA2, srB1, srB2) == TRUE) return(TRUE);
1299         }
1300     }
1301     return(FALSE);
1302 }
1303 /*-------------------------------------------------------------------------------------*/
1304 /* Should check for function round() in configure. . .  */
1305
1306 /*
1307 int round(f)
1308     float f;
1309 {
1310     int d = (int)f;
1311     if (f - (float)d > 0.5) return(d + 1);
1312     else return(d);
1313 }
1314 */
1315
1316 /*-------------------------------------------------------------------------------------*/
1317 int set_step_size(orderedRanges, newStep)
1318     rnglist *orderedRanges;             /* These should be ordered l->r, or b->t */
1319     float *newStep;
1320 {
1321     /* Look through the entire set of <orderedRanges> to see if there is an
1322        uncoupleable condition (overlapped fixed points, start/end screwed up...)
1323        This also dynamically resizes the step size...
1324
1325        Want to find the minimum step size for the rangelist, assuming that the
1326        first element on the list is the one that will use the result.
1327        */
1328     int n = list_length(orderedRanges);
1329     range *last = (range *)nth(orderedRanges, n);
1330     rnglist *rl;
1331     float min = (float)orderedRanges->this->sr->q1, max = (float)last->sr->q2;
1332     float step = (max - min - (float)n + 1) / n;
1333
1334     n = 2;
1335     for (rl = orderedRanges->next; (rl != NULL); rl = rl->next)
1336     {
1337         max = (float)rl->this->sr->q2;
1338         if ((round(max) - round(min)) < (n - 1)) return(TRUE);
1339         step = MIN(MAX(((max - min - (float)n + 1) / n), 0.0), step);
1340         n += 1;
1341     }
1342     *newStep = step;
1343     return(FALSE);
1344 }
1345 /*-------------------------------------------------------------------------------------*/
1346 void decouple_ordered_ranges(orderedRanges)
1347         rnglist *orderedRanges;         /* These should be ordered l->r, or b->t */
1348 {
1349     int n = list_length(orderedRanges);
1350     range *r, *nextR, *last;
1351     rnglist *rl, *rll;
1352     float min, max, step, next;
1353
1354     if ((debug_level >= 2) && (n > 1))
1355     {
1356         fprintf(stderr, "Attempt to Decouple ");
1357         dump_ranges(orderedRanges);
1358     }
1359
1360     /* The first range should be limited to [min...min+step] or its current limit,
1361        whichever is smaller.  The process repeats until all ranges have been
1362        allotted non-overlapping slots. */
1363
1364     form_into_decoupleable_order(orderedRanges, list_length(orderedRanges));
1365
1366
1367     /* As the call to "form_into_decoupleable_order" may rearange <orderedRanges>,
1368        the following must be set after the call: */
1369
1370         last = (range *)nth(orderedRanges, n);
1371         min = (float)orderedRanges->this->sr->q1;
1372         max = (float)last->sr->q2;
1373         step = MAX(((max - min - (float)n + 1) / n), 1.0);
1374         next = min;
1375
1376
1377     if (n > 1)
1378     {
1379         for (rl = orderedRanges; rl != NULL; rl = rl->next)
1380         {
1381             r = rl->this;
1382             if (set_step_size(rl, &step) == TRUE)
1383             {
1384                 /* Serious problems */
1385                 fprintf(stderr, "Cannot decouple ranges ");
1386                 dump_ranges(rl);
1387                 break;
1388             }
1389
1390             /* Advance the <min> and <next> pointers... */
1391             min = (r->sr->q1 > round(next)) ? (float)r->sr->q1 : next;
1392             next = (round(min + step) > r->sr->q2) ? (float)r->sr->q2 : min + step;
1393
1394             if (rl->next != NULL)            /* Lookahead to avoid needless constraint */
1395             {
1396                 nextR = rl->next->this;
1397
1398                 if (r->n == nextR->n)
1399                 {
1400                     /* No need to constrain <r> as much. This allows <r> and <nextR>
1401                        to coincide.  */
1402                     next = (next < round(r->sr->q2)) ? next + step : (float)r->sr->q2;
1403                     nextR->sr->q1 = (round(min) > nextR->sr->q1) ? round(min) :
1404                     nextR->sr->q1;
1405                 }
1406
1407                 else  /* find the appropriate <next> point (where to end <r>) and set
1408                          the beginning point for <nextR>:                       */
1409                 {
1410                     if (round(next) < (nextR->sr->q1 - 1))
1411                     {
1412                         if ((nextR->sr->q1 - 1) <=  r->sr->q2)
1413                         next = (float)nextR->sr->q1 - 1.0;
1414                     }
1415                     else if (round(next) >= nextR->sr->q2)
1416                     {
1417                         /* Problem */
1418                         next = (float)nextR->sr->q2 - 1.0;
1419                         nextR->sr->q1 = nextR->sr->q2;
1420                     }
1421                     else if (round(next + step) >= nextR->sr->q2)
1422                     {
1423                         /* problem... Should reset (shrink) the step size */
1424                         step = MAX(((max - (float)nextR->sr->q1 - (float)n + 1.0)
1425                                     / (n - 1)), 1.0);
1426                         nextR->sr->q1 = round(next) + 1;
1427                     }
1428                     else
1429                     {
1430                         nextR->sr->q1 = round(next) + 1;
1431                     }
1432                 }
1433             }
1434             else
1435             {
1436                 next = max;
1437             }
1438             r->sr->q2 = round(next);
1439             n -= 1;
1440         }
1441
1442         if (debug_level >= 2)
1443         {
1444             fprintf(stderr, "       Resulted in  ");
1445             dump_ranges(orderedRanges);
1446         }
1447     }
1448     else if (debug_level >= 2)
1449     {
1450         r = orderedRanges->this;
1451         fprintf(stderr, "Skipping <%s>[%d,%d] \n", r->n->name, r->sr->q1, r->sr->q2);
1452     }
1453 }
1454 /*-------------------------------------------------------------------------------------*/
1455 void decouple_ranges(r1, r2)
1456         range *r1, *r2;
1457 {
1458     int flag;
1459     /* <r1> goes to the (bot/right) of <r2>: */
1460     flag = divide_sranges(r2->sr, r1->sr);
1461
1462     if ((flag == FALSE) && (debug_level >= 2))
1463     fprintf(stderr, "<%s> range [%d,%d] cannot go to left of <%s> range [%d,%d]\n",
1464             r1->n->name, r1->sr->q1, r1->sr->q2,
1465             r2->n->name, r2->sr->q1, r2->sr->q2);
1466 }
1467 /*-------------------------------------------------------------------------------------*/
1468 rnglist *old_rev_decoupleable_p(orderedRanges, stopAt)
1469     rnglist *orderedRanges;             /* These should be ordered l->r, or b->t */
1470     int stopAt;
1471 {
1472     /* Look through the entire set of <orderedRanges> to see if there is an
1473        uncoupleable condition (overlapped fixed points, start/end screwed up...)
1474
1475        The object is to return a list pointer to the range who's ordering screws
1476        up the range set. (Or return NULL)
1477
1478        This is the parallel to "decoupleable_p", in that it works by starting
1479        with the list and trims from the front to find the error. zb. The list now
1480        starts  1-2-3-4, 2-3-4, 3-4, 4 until the removal of a range fixes the problem.
1481        When the removal of a range fixes the problem, this is the list pointer
1482        to return.
1483      */
1484
1485     int n = stopAt + 1;
1486     range *last = (range *)nth(orderedRanges, stopAt);
1487     rnglist *rl, *rLast = orderedRanges;
1488     int min, max;
1489
1490     if (stopAt == 1) return(orderedRanges);
1491
1492     /* Step forward through the list [1-2-3-4, 2-3-4, 3-4, 4] */
1493     max = last->sr->q2;
1494     for (rl = orderedRanges; ((rl != NULL) && (n-- > 0)); rl = rl->next)
1495     {
1496         min = rl->this->sr->q1;
1497         if ((max - min) >= (n - 1))                     /* Someone's not fouled up */
1498         {
1499             return(rLast);
1500         }
1501         if (rl != orderedRanges) rLast = rLast->next;
1502     }
1503     return(NULL);
1504 }
1505 /*-------------------------------------------------------------------------------------*/
1506 rnglist *rev_decoupleable_p(orderedRanges, stopAt)
1507     rnglist *orderedRanges;             /* These should be ordered l->r, or b->t */
1508     int stopAt;
1509 {
1510     /* Look through the entire set of <orderedRanges> to see if there is an
1511        uncoupleable condition (overlapped fixed points, start/end screwed up...)
1512
1513        The object is to return a list pointer to the range who's ordering screws
1514        up the range set. (Or return NULL)
1515
1516        This is the parallel to "decoupleable_p", in that it works by starting
1517        with the list and trims from the front to find the error. zb. The list now
1518        starts  1-2-3-4, 2-3-4, 3-4, 4 until the removal of a range fixes the problem.
1519        When the removal of a range fixes the problem, this is the list pointer
1520        to return.
1521      */
1522
1523     /* There is a strange sub-problem that exists when one of the internal elements
1524        has a smaller <max> than the end of the list;  This breaks the problem into
1525        similar subproblems at that point;  The hard part is keeping the left-hand
1526        list pointers straight with the number of elements that must be fit between
1527        the <min> (defined by the LH list pointer) and the <max>, which may be
1528        in the middle of the list somewhere.
1529      */
1530
1531     int maxIndex, i1 = 0, i2 = 0, n, works = TRUE;
1532     range *last = (range*)nth(orderedRanges, stopAt);
1533     rnglist *rLast = orderedRanges;
1534     rnglist *RHs, *LHs = orderedRanges;
1535     int min = LHs->this->sr->q1, max = last->sr->q2;
1536
1537
1538     if (stopAt == 1) return(orderedRanges);
1539
1540     /* Set the <max> for the full list: (may not be at <last>) */
1541     for (RHs = orderedRanges; ((RHs != NULL) && (i1++ < stopAt)); RHs = RHs->next)
1542     {
1543         if (max < RHs->this->sr->q2)
1544         {
1545             max = RHs->this->sr->q2;
1546
1547             /* Step forward through the list [1-2-3-4, 2-3-4, 3-4, 4] */
1548             for (; ((LHs != NULL) && (i2++ <= i1)); LHs = LHs->next)
1549             {
1550                 min = MAX(min, LHs->this->sr->q1);
1551                 n = i1 - i2 + 1;                         /* Number of ranges to fit in */
1552
1553                 /* Found a problem already, and Someone's not fouled up */
1554                 if ((works == FALSE) && ((max - min) >= (n - 1))) return(rLast);
1555                 else if ((max - min) < (n - 1))
1556                 {
1557                     works = FALSE;      if (LHs != orderedRanges) rLast = rLast->next;
1558                 }
1559                 else if (LHs != orderedRanges) rLast = rLast->next;
1560             }
1561             /* At this point --> ((LHs == RHs) && (n == 0)) should be the TRUE. */
1562         }
1563     }
1564
1565     n = stopAt - i2 + 1;
1566     for (; ((LHs != NULL) && (n-- > 0)); LHs = LHs->next)
1567     {
1568         min = LHs->this->sr->q1;
1569
1570         /* Found a problem already, and Someone's not fouled up */
1571         if ((works == FALSE) && ((max - min) >= (n - 1))) return(rLast);
1572         else if ((works == TRUE) && ((max - min) < (n - 1)))
1573         {
1574             works = FALSE;      if (LHs != orderedRanges) rLast = rLast->next;
1575         }
1576         else if (LHs != orderedRanges) rLast = rLast->next;
1577     }
1578
1579     return(NULL);
1580 }
1581 /*-------------------------------------------------------------------------------------*/
1582 rnglist *decoupleable_p(orderedRanges, stopAt)
1583     rnglist *orderedRanges;             /* These should be ordered l->r, or b->t */
1584     int stopAt;
1585 {
1586     /* Look through the entire set of <orderedRanges> to see if there is an
1587        uncoupleable condition (overlapped fixed points, start/end screwed up...)
1588
1589        The object is to return a list pointer to the range who's ordering screws
1590        up the range set.
1591
1592        This works by starting at the beginning of the list and working
1593        forward through the list (1, 1-2, 1-2-3, 1-2-3-4, etc.) checking to see
1594        if the addition of any particular range destroys the decoupleability of the
1595        range set.  If no error is found, then NULL is returned.
1596
1597      */
1598
1599     int n = 1, idx = 1;
1600     range *last = (range *)nth(orderedRanges, stopAt);
1601     rnglist *rl, *fixup, *rLast = orderedRanges;
1602     int min, max;
1603
1604     if (stopAt == 1) return(NULL);
1605
1606     /* Search forward through the list [1, 1-2, 1-2-3, 1-2-3-4] */
1607     min = orderedRanges->this->sr->q1;
1608     for (rl = orderedRanges->next; ((rl != NULL) && (idx++ < stopAt)); rl = rl->next)
1609     {
1610         n++;
1611         max = rl->this->sr->q2;
1612
1613         if (rl->this->sr->q1 > min)             /* reset <min> if a more stringent */
1614         {                                       /* constraint is found */
1615
1616             /* Tough example: { [137..150], [137..150], [137..150], [138..150], etc..} */
1617
1618             if ((rl->this->sr->q2 - min) < (n - 1))
1619             {   /* Someone doesn't fit the new constraints... */
1620                 fixup = rev_decoupleable_p(orderedRanges, idx);
1621                 if ((fixup == NULL) || (fixup == orderedRanges))return(rLast);
1622                 else return(fixup);
1623             }
1624             else if ((rl->this->sr->q1 - min) < (n - 1))
1625             { /* Need to be careful how the min is reset */
1626                 min = rl->this->sr->q1 + (n - 1) - (rl->this->sr->q1 - min);
1627             }
1628             else /* Don't need to be careful how min is reset */
1629                 min = rl->this->sr->q1;
1630             n = 1;                              /* Everything fits; restart the count */
1631         }
1632
1633         if ((max - min) < (n - 1))                           /* Someone's fouled up */
1634         {
1635             fixup = rev_decoupleable_p(orderedRanges, idx);
1636             if (fixup == NULL) return(rLast);
1637             else return(fixup);
1638         }
1639         rLast = rLast->next;
1640     }
1641     return(NULL);
1642 }
1643 /*------------------------------------------------------------------------------------*/
1644 int form_into_decoupleable_order(orderedRanges, maxRecDepth)
1645     rnglist *orderedRanges;
1646     int maxRecDepth;
1647 {
1648     /* step through the given ordered set of ranges;  correct defaults by
1649        swapping.  keep track of the recursion depth to avoid serious problems.
1650        */
1651
1652     range *temp;
1653     rnglist *rl, *badSpot = NULL;
1654     int i, r;
1655
1656     if (maxRecDepth-- <= 0)
1657     {
1658         fprintf(stderr, "Cannot reform ");
1659         dump_ranges(orderedRanges);
1660         return(FALSE);
1661     }
1662
1663     for (i = 1; i <= list_length(orderedRanges); i++)
1664     {
1665         badSpot = decoupleable_p(orderedRanges, i);
1666         if (badSpot != NULL)
1667         {
1668             /* swap some elements, and try again */
1669             temp = badSpot->this;
1670             badSpot->this = badSpot->next->this;
1671             badSpot->next->this = temp;
1672
1673             break;
1674         }
1675     }
1676     if (badSpot != NULL) r = form_into_decoupleable_order(orderedRanges, maxRecDepth);
1677
1678     if ((debug_level >= 2) && (badSpot != NULL))
1679     {
1680         fprintf(stderr, "Reordered list into ");
1681         dump_ranges(orderedRanges);
1682     }
1683     return(TRUE);
1684 }
1685 /*------------------------------------------------------------------------------------*/
1686 int in_length_order(l, ll)
1687     list *l, *ll;
1688 {
1689     /* Return TRUE if <l> is longer than <ll>: */
1690     if (list_length(l) >= list_length(ll)) return(TRUE);
1691     else return(FALSE);
1692 }
1693 /*------------------------------------------------------------------------------------*/
1694 void perpendicular_expanse(r, min, max)
1695     range *r;
1696     int *min, *max;
1697 {
1698     /* This walks through all of the corners associated with <r>.
1699        The extent of the ranges seen among the corners associated with <r> is
1700        returned; */
1701
1702     crnlist *cl = r->corners;
1703     range *oppRange = (cl->this->cx == r) ? cl->this->cy : cl->this->cx;
1704
1705     *min = oppRange->sr->q1;
1706     *max = oppRange->sr->q2;
1707
1708
1709     for (; cl != NULL; cl = cl->next)
1710     {
1711         oppRange = (cl->this->cx == r) ? cl->this->cy : cl->this->cx;
1712         *min = MIN(oppRange->sr->q1, *min);
1713         *max = MAX(oppRange->sr->q2, *max);
1714     }
1715 }
1716 /*------------------------------------------------------------------------------------*/
1717 int check_sranges(sr, r)
1718     srange *sr;
1719     range *r;
1720 {
1721     if (r->sr == sr) return(TRUE);
1722     else return(FALSE);
1723 }
1724 /*------------------------------------------------------------------------------------*/
1725 /*------------------------------------------------------------------------------------*/
1726 int by_length(l1, l2)
1727     list *l1, *l2;
1728 {
1729     /* return TRUE if list_length(<l1>) > list_length(<l2>)     */
1730
1731     if (list_length(l1) > list_length(l2)) return (TRUE);
1732     else return(FALSE);
1733 }
1734 /*------------------------------------------------------------------------------------*/
1735 int subset_p(s, set)
1736     list *s, *set;
1737 {
1738     int i, len = list_length(s);
1739     list *l;
1740
1741     if (len > list_length(set)) return(FALSE);
1742     for (l = s; l != NULL; l = l->next)
1743     {
1744         if (member_p(l->this, set, identity) == FALSE) return(FALSE);
1745     }
1746     return(TRUE);
1747 }
1748 /*------------------------------------------------------------------------------------*/
1749 int subset_of_any_p(s, setOfSets)
1750     list *s, *setOfSets;                /* a list, and a list of lists */
1751 {
1752     list *l;
1753
1754     for (l = setOfSets; l != NULL; l = l->next)
1755     {
1756         if (subset_p(s, l->this) == TRUE) return(TRUE); /* <s> is subset of <l>->this */
1757     }
1758     return(FALSE);
1759 }
1760 /*------------------------------------------------------------------------------------*/
1761 int copy_of_list_p(l1, l2)
1762     list *l1, *l2;
1763 {
1764     int i, len = list_length(l1);
1765     list *lptr1 = l1, *lptr2 = l2;
1766
1767     if (len != list_length(l2)) return(FALSE);
1768     for (i = len; i >0; i--)
1769     {
1770         if (lptr1 == lptr2)
1771         {
1772             if (lptr1 == NULL) return(TRUE);
1773             lptr1 = lptr1->next;
1774             lptr2 = lptr2->next;
1775         }
1776         else if (lptr1->this != lptr2->this) return(FALSE);
1777     }
1778     return(TRUE);
1779 }
1780 /*------------------------------------------------------------------------------------*/
1781 int seen_by_others_p(range *r,rnglist *path)
1782
1783 {
1784     /* Return TRUE if this range <r> depends on any ranges that are yet unseen */
1785     /* The additional caveat is that for the unseen 'viewer' to qualify, it must be a
1786        part of the given <path> */
1787     rnglist *rl;
1788     for(rl = reverseDepSets[r->use]; rl != NULL; rl = rl->next)
1789     {
1790         if ((rl->this->flag == UNSEEN) &&
1791             (member_p(rl->this, path, identity) == TRUE)) return(TRUE);
1792     }
1793     return(FALSE);
1794 }
1795 /*------------------------------------------------------------------------------------*/
1796 int lowest_level_seen_at(pr, cr, dChains)
1797     range *pr, *cr;
1798     rnglist **dChains;
1799 {
1800     /* Return the lowest level at which the child range <cr> is used in the chain
1801        containing the given parent range <pr>. */
1802     int pi = pr->use, ci = cr->use, lowest, bottomNotReached = TRUE;
1803     range *r = pr;
1804     rnglist *rl;
1805
1806     if (member_p(cr, dChains[pi], identity) == TRUE)
1807     {
1808         lowest = levelMap[pi];
1809         while (bottomNotReached == TRUE)
1810         {
1811             for(rl = dChains[r->use]->next; rl != NULL; rl = rl->next)
1812             {
1813                 r = rl->this;
1814                 if (member_p(cr, dChains[r->use]->next, identity) == TRUE)
1815                 {
1816                     lowest = MIN(levelMap[r->use], lowest);
1817                 }
1818                 if ((r == cr) ||
1819                     (dChains[r->use]->next == NULL)) bottomNotReached = FALSE;
1820             }
1821         }
1822         return(lowest);
1823     }
1824
1825     /* The default case: */
1826     else return(levelMap[ci]);
1827
1828 }
1829 /*------------------------------------------------------------------------------------*/
1830 rnglist *enumerate_dependencies(parentRange, dChains, status, soFar)
1831     range *parentRange;
1832     rnglist **dChains;
1833     int *status;
1834     rnglist **soFar;
1835 {
1836     /* Depth-first traversal of the dependencies.   This just builds, and marks.
1837        It does not distinguish that a graph is redundant, saving that the status will
1838        never change to TRUE.
1839
1840        The graph is built up from the bottom of a recursion chain, and a graph
1841        will be built if somewhere in the chain a previously-unseen range is included. */
1842
1843     int i = parentRange->use, currentLevel, noneSeen = TRUE;
1844     range *nextParent;
1845     rnglist *rl, *growingChain = NULL;
1846
1847     /* simple-case: bad chain */
1848     if (dChains[i] == NULL) return(NULL);
1849
1850     /* No dependencies */
1851     else if (dChains[i]->next == NULL)
1852     {
1853         if ((parentRange->flag == UNSEEN) || (*status == TRUE))
1854         {
1855             /* Start building a chain - there's something worth building */
1856             if (parentRange->flag == UNSEEN) *status = TRUE;
1857             if (seen_by_others_p(parentRange, *soFar) == FALSE) parentRange->flag = SEEN;
1858             push(parentRange, &growingChain);
1859             return(growingChain);
1860         }
1861         else return(NULL);              /* There's nothing worth building */
1862     }
1863
1864     else /* There are Mulitple Dependencies... */
1865     {
1866         /* Note the status: */
1867         if (parentRange->flag == UNSEEN)
1868         {
1869             *status = TRUE;
1870             if (seen_by_others_p(parentRange, *soFar) == FALSE) parentRange->flag = SEEN;
1871         }
1872
1873         /* Check all of the dependents to see if they should be selected for
1874            branching.  To qualify, they can only branch on UNTRIED nodes */
1875         nextParent = dChains[i]->next->this;            /* default = Depth-first */
1876         currentLevel = levelMap[i];
1877         for (rl = dChains[i]->next; rl != NULL; rl = rl->next)
1878         {
1879             if ((rl->this->flag != TRIED) &&
1880                 (currentLevel == lowest_level_seen_at(parentRange, rl->this, dChains)))
1881             {
1882                 nextParent = rl->this;
1883                 push(nextParent, soFar);
1884
1885                 /* See if this was successful: */
1886                 growingChain = enumerate_dependencies(nextParent, dChains,
1887                                                       status, soFar);
1888                 if (growingChain != NULL)               /* It Worked */
1889                 {
1890                     push(parentRange, &growingChain);   /* Add to the chain */
1891                     return(growingChain);
1892                 }
1893                 else pop(soFar);                        /* It didn't */
1894             }
1895         }
1896         parentRange->flag = TRIED;  /* The possibilities have all failed */
1897         return(growingChain);
1898     }
1899 }
1900 /*------------------------------------------------------------------------------------*/
1901 int in_depth_order(r1, r2)
1902     range *r1, *r2;
1903 {
1904     if (levelMap[r1->use] < levelMap[r2->use]) return (TRUE);
1905     else if (r1->use < r2->use) return(TRUE);
1906     else return (FALSE);
1907 }
1908 /*------------------------------------------------------------------------------------*/
1909 int dependence_level(idx, dChains)
1910     int idx;
1911     rnglist **dChains;          /* Deeply recursive */
1912 {
1913     /* Find the maximum dependence level from this set of chains */
1914     rnglist *rl, *chain = dChains[idx];
1915     int lev = 0;
1916
1917     if (list_length(chain) <= 1) return(0);
1918
1919     for (rl = chain->next; rl != NULL; rl = rl->next)
1920     {
1921         lev = MAX(lev, dependence_level(rl->this->use, dChains));
1922     }
1923     return(1 + lev);
1924 }
1925 /*------------------------------------------------------------------------------------*/
1926 int help_setup_dependence_levels(idx, level, dChains)
1927     int idx, level;
1928     rnglist **dChains;          /* Deeply recursive */
1929 {
1930     /* Find the maximum dependence level from this set of chains */
1931     rnglist *rl, *chain = dChains[idx];
1932     int deepest = 0;
1933
1934     chain->this->flag = MAX(level, chain->this->flag);
1935
1936     for (rl = chain->next; rl != NULL; rl = rl->next)
1937     {
1938         if (rl->this->flag >= level + 1)
1939         {
1940             deepest = MAX(deepest, rl->this->flag);
1941         }
1942         else
1943         {
1944             rl->this->flag = level + 1;
1945             deepest = MAX(help_setup_dependence_levels(rl->this->use, level + 1, dChains),
1946                           deepest);
1947         }
1948     }
1949     return(MAX(deepest, chain->this->flag));
1950 }
1951 /*------------------------------------------------------------------------------------*/
1952 int setup_dependence_levels(count, dChains)
1953     int count;
1954     rnglist **dChains;          /* Deeply recursive */
1955 {
1956     /* Set the ->flag fields to contain the maximum depth of the
1957        given range in the graph set. */
1958
1959     rnglist *rl, *chain;
1960     int idx;
1961
1962     for (idx = 0; idx < count; idx++)
1963     {
1964         chain = dChains[idx];
1965         for (rl = chain->next; rl != NULL; rl = rl->next)
1966         {
1967             help_setup_dependence_levels(rl->this->use,
1968                                          MAX(1, rl->this->flag), dChains);
1969         }
1970     }
1971 }
1972 /*------------------------------------------------------------------------------------*/
1973 list *form_dependency_graph(orderedRanges)
1974     rnglist *orderedRanges;
1975 {
1976     /* This returns a list of range lists, such that each list is a subgraph of the
1977        dependency graph for the given ranges.  The ordering is the left->right/bottom->
1978        top ordering for the given set of ranges.
1979        This is not easy.  Start with an ordered list of ranges, ordered bottom->top.
1980        Then start with the bottom-most range, and sweep up the list;  The sweep front
1981        has the width of the last range encountered, and every range that overlaps the
1982        sweep-front is picked up.  This process continues until all the list has been
1983        checked once, and produes one dependency graph (stored in <temp>)
1984
1985        Next, start over, to see if there are more...       */
1986
1987     rnglist *rl, *rll, *graph, *temp = NULL, *scratch = NULL, **dependenceSets;
1988     list *nonOverlap = NULL;
1989     int i = 0, min, max, rMin, rMax, tot = list_length(orderedRanges);
1990     int maxLevel, maxIndex, notDone = TRUE, status = FALSE;
1991
1992     /* create an array to hold the dependency chains : */
1993     dependenceSets = (rnglist **)calloc(tot, sizeof(rnglist *));
1994
1995     /* Assign the global pointer to the depth map: */
1996     levelMap = (int *)calloc(tot, sizeof(int));
1997     reverseDepSets = (rnglist **)calloc(tot, sizeof(rnglist *));
1998
1999     /* Set up the chain of dependencies : */
2000     for (rl = orderedRanges; rl != NULL; rl = rl->next)
2001     {
2002         perpendicular_expanse(rl->this, &rMin, &rMax);    /* The parent extent */
2003         temp = NULL;
2004         for (rll = rl->next; rll != NULL; rll = rll->next)
2005         {
2006             perpendicular_expanse(rll->this, &min, &max); /* Wavefront  Extent */
2007             if (int_overlapped_p(min,max,rMin,rMax) == TRUE)      /* overlap */
2008             {
2009                 push(rll->this, &temp);         /* These are sorted later */
2010             }
2011         }
2012         push(rl->this, &temp);
2013         dependenceSets[i] = temp;
2014         rl->this->use = i++;                     /* Save the idx */
2015         rl->this->flag = 0;                      /* Assume everyone starts at level 0 */
2016     }
2017
2018     /* From the dependence set, create the level map: */
2019     maxIndex = tot - 1;
2020     maxLevel = 0;
2021
2022     setup_dependence_levels(tot, dependenceSets);
2023     for(i = tot - 1; i >= 0; i--)
2024     {
2025 /*      OLD->   levelMap[i] = dependence_level(i, dependenceSets); */
2026         levelMap[i] = dependenceSets[i]->this->flag;
2027         if (levelMap[i] > maxLevel)
2028         {
2029             maxIndex = i;
2030             maxLevel = levelMap[i];
2031         }
2032     }
2033
2034     for (rl = orderedRanges; rl != NULL; rl = rl->next)
2035     {
2036         rl->this->flag = UNSEEN;         /* Used to distinguish a unique graph */
2037
2038         /* sort the chains in dependency order */
2039         sort_list(dependenceSets[rl->this->use], in_depth_order);
2040
2041         /* Set up the reverse dependency lists */
2042         for (rll = dependenceSets[rl->this->use]->next; rll != NULL; rll = rll->next)
2043         {
2044             push(rl->this, &reverseDepSets[rll->this->use]);
2045         }
2046     }
2047
2048     /* From the dependence set and the level map, create the dependency graph: */
2049     for(rl = orderedRanges; rl != NULL; rl = rl->next)
2050     {
2051         if (rl->this->flag == UNSEEN)
2052         {
2053             notDone = TRUE;                             /* Start a new search */
2054
2055             /* enumerate into a set of complete graphs: */
2056             while (notDone == TRUE)
2057             {
2058                 /* Make the next dependency graph: */
2059                 graph = enumerate_dependencies(rl->this, dependenceSets,
2060                                                &status, &scratch);
2061                 scratch = (rnglist *)free_list(scratch);
2062                 if ((status == TRUE) && (graph != NULL))
2063                 {
2064                     push(graph, &nonOverlap);                   /* Keep it  */
2065                     status = FALSE;
2066                 }
2067                 else if (graph == NULL)
2068                 {
2069                     notDone = FALSE;                            /* Quit looking */
2070                     /* Clear the TRIED flags set */
2071                     for(rll = orderedRanges; rll != NULL; rll = rll->next)
2072                         if (rll->this->flag == TRIED) rll->this->flag = SEEN;
2073                 }
2074                 else free_list(graph);                          /* Scrap it */
2075             }
2076         }
2077     }
2078
2079     return(nonOverlap);
2080 }
2081 /*------------------------------------------------------------------------------------*/
2082 int range_exits_top(r, a)
2083     range *r;
2084     asg_arc *a;
2085 {
2086     /* This function returns TRUE if any of the corners along this range (assumed
2087        to be representative of a y-segment) are at or beyond the top of the given
2088        tile. */
2089     int y = (a->page == HORZ) ? a->t->y_pos + a->t->y_len :
2090                                 a->t->x_pos + a->t->x_len;
2091     corner *c;
2092     crnlist *cl;
2093
2094     for (cl = r->corners; cl != NULL; cl = cl->next)
2095     {
2096         for (c = next_vert_corner(cl->this);(c != cl->this); c = next_vert_corner(NULL))
2097         {
2098             if (cl->this->cy->sr->q1 >= y) return(TRUE);
2099         }
2100         if (cl->this->cy->sr->q1 >= y) return(TRUE);
2101     }
2102     return (FALSE);
2103 }
2104 /*------------------------------------------------------------------------------------*/
2105 int range_exits_bottom(r, a)
2106     range *r;
2107     asg_arc *a;
2108 {
2109     /* This function returns TRUE if any of the corners along this range (assumed
2110        to be representative of a y-segment) are at or beyond the bottom of the given
2111        tile. */
2112     int y = (a->page == HORZ) ? a->t->y_pos : a->t->x_pos;
2113     corner *c;
2114     crnlist *cl;
2115
2116     for (cl = r->corners; cl != NULL; cl = cl->next)
2117     {
2118         for (c = next_vert_corner(cl->this);(c != cl->this); c = next_vert_corner(NULL))
2119         {
2120             if (c->cy->sr->q2 <= y) return(TRUE);
2121         }
2122         if (c->cy->sr->q2 <= y) return(TRUE);
2123     }
2124     return (FALSE);
2125 }
2126 /*------------------------------------------------------------------------------------*/
2127 int range_exits_right(r, a)
2128     range *r;
2129     asg_arc *a;
2130 {
2131     /* This function returns TRUE if any of the corners along this range (assumed
2132        to be representative of an x-segment) are at or beyond the right side of the
2133        given tile. */
2134     int x = (a->page == HORZ) ? a->t->x_pos + a->t->x_len : a->t->y_pos + a->t->y_len;
2135     corner *c;
2136     crnlist *cl;
2137
2138     for (cl = r->corners; cl != NULL; cl = cl->next)
2139     {
2140         for (c = next_horz_corner(cl->this); (c != cl->this); c = next_horz_corner(NULL))
2141         {
2142             if (c->cx->sr->q1 >= x) return(TRUE);
2143         }
2144         if (c->cx->sr->q1 >= x) return(TRUE);
2145     }
2146     return (FALSE);
2147 }
2148 /*------------------------------------------------------------------------------------*/
2149 int range_exits_left(r, a)
2150     range *r;
2151     asg_arc *a;
2152 {
2153     /* This function returns TRUE if any of the corners along this range (assumed
2154        to be representative of an x-segment) are at or beyond the left side of the
2155        given tile. */
2156     int x = (a->page == HORZ) ? a->t->x_pos : a->t->y_pos;
2157     corner *c;
2158     crnlist *cl;
2159
2160     for (cl = r->corners; cl != NULL; cl = cl->next)
2161     {
2162         for (c = next_horz_corner(cl->this);(c != cl->this); c = next_horz_corner(NULL))
2163         {
2164             if (c->cx->sr->q2 <= x) return(TRUE);
2165         }
2166         if (c->cx->sr->q2 <= x) return(TRUE);
2167     }
2168     return (FALSE);
2169 }
2170 /*------------------------------------------------------------------------------------*/
2171 int natural_break_p(r1, r2)
2172     range *r1, *r2;
2173 {
2174     if ((r1->sr->q2 <= r2->sr->q1) ||
2175         (r2->sr->q2 <= r1->sr->q1)) return(TRUE);
2176     else return(FALSE);
2177 }
2178 /*------------------------------------------------------------------------------------*/
2179 int follow_natural_break(r1, r2)
2180     range *r1, *r2;
2181 {
2182     /* There is a 'natural' break, so return it */
2183     if (r1->sr->q2 <= r2->sr->q1) return(TRUE);
2184     else return(FALSE);
2185 }
2186 /*------------------------------------------------------------------------------------*/
2187 /*------------------------------------------------------------------------------------*/
2188 /*------------------------------------------------------------------------------------*/
2189 int exits_right_p(c)    /* Not very bulletproof. */
2190     corner *c;
2191 {
2192     corner *nextC = next_horz_corner(c);
2193     corner *otherNextC = next_horz_corner(NULL);
2194
2195     if (nextC->cx->sr->q1 >= c->cx->sr->q2) return(TRUE);
2196     else if ((otherNextC != c) &&
2197              (otherNextC->cx->sr->q1 >= c->cx->sr->q2)) return(TRUE);
2198     else return(FALSE);
2199 }
2200 /*------------------------------------------------------------------------------------*/
2201 int exits_top_p(c)
2202     corner *c;
2203 {
2204     corner *nextC = next_vert_corner(c);
2205     corner *otherNextC = next_vert_corner(NULL);
2206
2207     if (nextC->cy->sr->q1 >= c->cy->sr->q2) return(TRUE);
2208     else if ((otherNextC != c) &&
2209              (otherNextC->cy->sr->q1 >= c->cy->sr->q2)) return(TRUE);
2210     else return(FALSE);
2211 }
2212 /*------------------------------------------------------------------------------------*/
2213 int share_bound_p(r1, r2, boundC1, boundC2)
2214     range *r1, *r2;
2215     corner **boundC1, **boundC2;
2216 {
2217     /* This returns TRUE if any terminus of <r1> overlaps that of <r2> */
2218     /* As a useful side-effect, return the pointers to the corners from which the
2219        determiniation was concluded... */
2220     crnlist *cl, *cll;
2221     srange *t1, *t2;
2222     int orient = r1->sr->orient;
2223
2224     *boundC1 = r1->corners->this;
2225     *boundC2 = r2->corners->this;
2226
2227     for(cl = r1->corners; cl != NULL; cl = cl->next)
2228     {
2229         for(cll = r2->corners; cll != NULL; cll = cll->next)
2230         {
2231             if (orient == HORZ)
2232             {
2233                 t1 = cl->this->cx->sr;
2234                 t2 = cll->this->cx->sr;
2235             }
2236             else
2237             {
2238                 t1 = cl->this->cy->sr;
2239                 t2 = cll->this->cy->sr;
2240             }
2241             if ((overlapped_p(t1, t2) == TRUE) &&
2242                 (t1->q1 == t1->q2) && (t2->q1 == t2->q2))
2243             {
2244                 *boundC1 = cl->this;
2245                 *boundC2 = cll->this;
2246                 return(TRUE);
2247             }
2248         }
2249     }
2250     return(FALSE);
2251 }
2252 /*------------------------------------------------------------------------------------*/
2253 int share_lower_bound_p(r1, r2, minC1, minC2)
2254     range *r1, *r2;
2255     corner **minC1, **minC2;
2256 {
2257     /* This returns TRUE if the lesser terminus of <r1> overlaps that of <r2> */
2258     /* As a useful side-effect, return the pointers to the corners from which the
2259        determiniation was concluded... */
2260     crnlist *cl;
2261     srange *min1, *min2, *temp;
2262     int orient = r1->sr->orient;
2263
2264     min1 = (orient == HORZ) ? r1->corners->this->cx->sr : r1->corners->this->cy->sr;
2265     min2 = (orient == HORZ) ? r2->corners->this->cx->sr : r2->corners->this->cy->sr;
2266
2267     *minC1 = r1->corners->this;
2268     *minC2 = r2->corners->this;
2269
2270     for(cl = r1->corners; cl != NULL; cl = cl->next)
2271     {
2272         temp = (orient == HORZ) ? cl->this->cx->sr : cl->this->cy->sr;
2273         if (temp->q1 < min1->q1)
2274         {
2275             min1 = temp;
2276             *minC1 = cl->this;
2277         }
2278     }
2279     for(cl = r2->corners; cl != NULL; cl = cl->next)
2280     {
2281         temp = (orient == HORZ) ? cl->this->cx->sr : cl->this->cy->sr;
2282         if (temp->q1 < min2->q1)
2283         {
2284             min2 = temp;
2285             *minC2 = cl->this;
2286         }
2287     }
2288
2289     /* Now compare <min1> to <min2>: The lower bound is considered to be shared
2290        whenever the two overlapp, and are restrictive... */
2291     if ((overlapped_p(min1, min2) == TRUE) &&
2292         (min1->q1 == min1->q2) && (min2->q1 == min2->q2)) return(TRUE);
2293     else return(FALSE);
2294 }
2295 /*------------------------------------------------------------------------------------*/
2296 int find_lowest_exits(r1, r2, minC1, minC2)
2297     range *r1, *r2;
2298     corner **minC1, **minC2;
2299 {
2300     /* As a useful side-effect, return the pointers to the corners which exit the
2301        right/top side at the smallest (lowest/left-most)points.  */
2302     crnlist *cl;
2303     srange *min1, *min2, *temp;
2304     int orient = r1->sr->orient;
2305
2306     min1 = (orient == HORZ) ? r1->corners->this->cx->sr : r1->corners->this->cy->sr;
2307     min2 = (orient == HORZ) ? r2->corners->this->cx->sr : r2->corners->this->cy->sr;
2308
2309     *minC1 = r1->corners->this;
2310     *minC2 = r2->corners->this;
2311
2312     for(cl = r1->corners; cl != NULL; cl = cl->next)
2313     {
2314         temp = (orient == HORZ) ? cl->this->cx->sr : cl->this->cy->sr;
2315         if ((temp->q1 < min1->q1) ||
2316             ((orient == HORZ) && (exits_top_p(*minC1) == FALSE)) ||
2317             ((orient == VERT) && (exits_right_p(*minC1) == FALSE)))
2318         {
2319             min1 = temp;
2320             if (((orient == HORZ) && (exits_top_p(cl->this) == TRUE)) ||
2321                 ((orient == VERT) && (exits_right_p(cl->this) == TRUE)))
2322             *minC1 = cl->this;
2323         }
2324     }
2325     for(cl = r2->corners; cl != NULL; cl = cl->next)
2326     {
2327         temp = (orient == HORZ) ? cl->this->cx->sr : cl->this->cy->sr;
2328         if ((temp->q1 < min2->q1) ||
2329             ((orient == HORZ) && (exits_top_p(*minC2) == FALSE)) ||
2330             ((orient == VERT) && (exits_right_p(*minC2) == FALSE)))
2331         {
2332             min2 = temp;
2333             if (((orient == HORZ) && (exits_top_p(cl->this) == TRUE)) ||
2334                 ((orient == VERT) && (exits_right_p(cl->this) == TRUE)))
2335             *minC2 = cl->this;
2336         }
2337     }
2338     return(1);
2339 }
2340 /*------------------------------------------------------------------------------------*/
2341 int find_highest_exits(r1, r2, maxC1, maxC2)
2342     range *r1, *r2;
2343     corner **maxC1, **maxC2;            /* Untested */
2344 {
2345     /* As a useful side-effect, return the pointers to the corners which exit the
2346        right/top side at the largest (highest/right-most)points.  */
2347     crnlist *cl;
2348     srange *max1, *max2, *temp;
2349     int orient = r1->sr->orient;
2350
2351     max1 = (orient == HORZ) ? r1->corners->this->cx->sr : r1->corners->this->cy->sr;
2352     max2 = (orient == HORZ) ? r2->corners->this->cx->sr : r2->corners->this->cy->sr;
2353
2354     *maxC1 = r1->corners->this;
2355     *maxC2 = r2->corners->this;
2356
2357     for(cl = r1->corners; cl != NULL; cl = cl->next)
2358     {
2359         temp = (orient == HORZ) ? cl->this->cx->sr : cl->this->cy->sr;
2360         if ((temp->q1 > max1->q1) ||
2361             ((orient == HORZ) && (exits_top_p(*maxC1) == FALSE)) ||
2362             ((orient == VERT) && (exits_right_p(*maxC1) == FALSE)))
2363         {
2364             max1 = temp;
2365             if (((orient == HORZ) && (exits_top_p(cl->this) == TRUE)) ||
2366                 ((orient == VERT) && (exits_right_p(cl->this) == TRUE)))
2367             *maxC1 = cl->this;
2368         }
2369     }
2370     for(cl = r2->corners; cl != NULL; cl = cl->next)
2371     {
2372         temp = (orient == HORZ) ? cl->this->cx->sr : cl->this->cy->sr;
2373         if ((temp->q1 > max2->q1) ||
2374             ((orient == HORZ) && (exits_top_p(*maxC2) == FALSE)) ||
2375             ((orient == VERT) && (exits_right_p(*maxC2) == FALSE)))
2376         {
2377             max2 = temp;
2378             if (((orient == HORZ) && (exits_top_p(cl->this) == TRUE)) ||
2379                 ((orient == VERT) && (exits_right_p(cl->this) == TRUE)))
2380             *maxC2 = cl->this;
2381         }
2382     }
2383     return(1);
2384 }
2385 /*------------------------------------------------------------------------------------*/
2386 corner *greatest_corner(r)
2387     range *r;
2388 {
2389     /* Return TRUE if the given <r> has no connected corners lower/left of it */
2390
2391     corner *greatest = r->corners->this;
2392     crnlist *cl;
2393     int orient = r->sr->orient;
2394     int max, temp;
2395
2396     max = (orient == VERT) ? greatest->cy->sr->q2 : greatest->cx->sr->q2;
2397     for (cl = r->corners->next; cl != NULL; cl = cl->next)
2398     {
2399         temp = (orient == VERT) ? cl->this->cy->sr->q2 : cl->this->cx->sr->q2;
2400         if (temp > max) greatest = cl->this;
2401     }
2402     return(greatest);
2403 }
2404 /*------------------------------------------------------------------------------------*/
2405 /*------------------------------------------------------------------------------------*/
2406 corner *least_corner(r)
2407     range *r;
2408 {
2409     /* Return TRUE if the given <r> has no connected corners above/right of it */
2410
2411     corner *least = r->corners->this;
2412     crnlist *cl;
2413     int orient = r->sr->orient;
2414     int min, temp;
2415
2416     min = (orient == VERT) ? least->cy->sr->q1 : least->cx->sr->q1;
2417     for (cl = r->corners->next; cl != NULL; cl = cl->next)
2418     {
2419         temp = (orient == VERT) ? cl->this->cy->sr->q1 : cl->this->cx->sr->q1;
2420         if (temp < min) least = cl->this;
2421     }
2422     return(least);
2423 }
2424 /*------------------------------------------------------------------------------------*/
2425 /*------------------------------------------------------------------------------------*/
2426 int internal_horz_ordering(c1, c2)
2427     corner *c1, *c2;
2428 {
2429     range *r1 = c1->cx, *r2 = c2->cx;
2430     int min, max, r1Extent, r2Extent, temp;
2431     int result;
2432
2433     /* return TRUE if <r1> should be placed to the left of <r2>: */
2434
2435     if (natural_break_p(r1, r2) == TRUE) result = follow_natural_break(r1, r2);
2436
2437     else if ((r1->use == NULL) || (r2->use == NULL))
2438     {
2439         fprintf(stderr, "error in internal_horz_ordering; NULL ->use assignment\n");
2440         result = TRUE;
2441     }
2442
2443     else
2444     {
2445         switch(r1->use)
2446         {
2447             case UL_CORNER: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2448             if (r2->use != UL_CORNER) result = TRUE;
2449             else
2450             {
2451                 /* Ye who exits to the left uppermost is left-most */
2452                 result = form_vertical_ordering(c1, c2);
2453             }
2454             break;
2455
2456
2457             case LL_CORNER: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2458             if (r2->use == UL_CORNER) result = FALSE;
2459             else if (r2->use == LL_CORNER)
2460             {
2461                 /* Ye who exit to the left lower-most is left-most */
2462                 result = form_vertical_ordering(c2, c1);
2463             }
2464             else result = TRUE;
2465             break;
2466
2467
2468             case LEFT_U: /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2469             if ((r2->use == UL_CORNER) || (r2->use == LL_CORNER)) result = FALSE;
2470             else if (r2->use == LEFT_U)
2471             {
2472                 /* place the shortest vertical segment left-most */
2473                 perpendicular_expanse(c1->cx, &min, &max);
2474                 r1Extent = max - min;
2475                 perpendicular_expanse(c2->cx, &min, &max);
2476                 r2Extent = max - min;
2477
2478                 if (r1Extent >= r2Extent) result = FALSE;
2479                 else result = TRUE;
2480             }
2481             else result = TRUE;
2482             break;
2483
2484
2485             case VERT_LT: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2486             if ((r2->use == UL_CORNER) || (r2->use == LL_CORNER) ||
2487                 (r2->use == LEFT_U)) result = FALSE;
2488             else if (r2->use == VERT_LT)
2489             {
2490                 /* Ye who exits to the left uppermost is left-most */
2491                 temp = form_vertical_ordering(c1, c2);
2492                 result = temp;
2493             }
2494             else result = TRUE;
2495             break;
2496
2497
2498             case HORZ_JOG:
2499             case HORZ_UT:
2500             case HORZ_DT:
2501             case UPWARD_U:
2502             case DOWNWARD_U:/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2503             if ((r2->use == UL_CORNER) || (r2->use == LL_CORNER) ||
2504                 (r2->use == LEFT_U) || (r2->use == VERT_LT)) result = FALSE;
2505             else if ((r2->use == UR_CORNER) || (r2->use == LR_CORNER) ||
2506                      (r2->use == RIGHT_U) || (r2->use == VERT_RT)) result = TRUE;
2507             else if ((r2->use == X) || (r2->use == VERT_JOG)) result = TRUE;
2508             else
2509             {
2510                 /* These are a bit tricky: Follow the external restrictions; */
2511                 temp = form_horizontal_ordering(c1, c2);
2512                 result = temp;
2513             }
2514             break;
2515
2516             case X_CORNER:
2517             case VERT_JOG: /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2518             if ((r2->use == UL_CORNER) || (r2->use == LL_CORNER) ||
2519                 (r2->use == LEFT_U) || (r2->use == VERT_LT)) result = FALSE;
2520             else if ((r2->use == UR_CORNER) || (r2->use == LR_CORNER) ||
2521                      (r2->use == RIGHT_U) || (r2->use == VERT_RT)) result = TRUE;
2522             else if ((r2->use == HORZ_JOG) || (r2->use == HORZ_UT) ||
2523                      (r2->use == HORZ_DT) || (r2->use == UPWARD_U) ||
2524                      (r2->use == DOWNWARD_U)) result = FALSE;
2525             else
2526             {
2527                 /* ye who exits to the right the lowest is left-most, except where there
2528                    are restrictions on the y-segment overlaps...*/
2529                 if (share_bound_p(r1, r2, &c1, &c2) == TRUE)
2530                 temp = exits_right_p(c2);
2531                 else if ((find_lowest_exits(r1, r2, &c1, &c2)) &&
2532                          ((c1 == least_corner(r1)) || (c2 == least_corner(r2))))
2533                 {       /* True, if thing are generally turning downward */
2534                     temp = form_vertical_ordering(c2, c1);
2535                 }
2536                 else /* Things are turning generally upward */
2537                 {
2538                     find_highest_exits(r1, r2, &c1, &c2);
2539                     temp = form_vertical_ordering(c1, c2);
2540                 }
2541                 result = temp;
2542             }
2543             break;
2544
2545             case VERT_RT: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2546             if ((r2->use == UR_CORNER) || (r2->use == LR_CORNER) ||
2547                 (r2->use == RIGHT_U)) result = TRUE;
2548             else if (r2->use == VERT_RT)
2549             {
2550                 /* Ye who exit to the right lower-most is right-most */
2551                 temp = form_vertical_ordering(c1, c2);
2552                 result = temp;
2553             }
2554             else result = FALSE;
2555             break;
2556
2557             case RIGHT_U: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2558             if ((r2->use == UR_CORNER) || (r2->use == LR_CORNER)) result = TRUE;
2559             else if (r2->use == RIGHT_U)
2560             {
2561                 /* place the shortest vertical segment right-most */
2562                 perpendicular_expanse(c1->cx, &min, &max);
2563                 r1Extent = max - min;
2564                 perpendicular_expanse(c2->cx, &min, &max);
2565                 r2Extent = max - min;
2566
2567                 if (r1Extent >= r2Extent) result = TRUE;
2568                 else result = FALSE;
2569             }
2570             else result = FALSE;
2571             break;
2572
2573
2574             case UR_CORNER: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2575             if (r2->use == LR_CORNER) result = TRUE;
2576             else if (r2->use == UR_CORNER)
2577             {
2578                 /* Ye who exit to the right lower-most is right-most */
2579                 result = form_vertical_ordering(c1, c2);
2580             }
2581             else result = FALSE;
2582             break;
2583
2584
2585             case LR_CORNER: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2586             if (r2->use == LR_CORNER)
2587             {
2588                 /* Ye who exit to the right upper-most is right-most */
2589                 result = form_vertical_ordering(c2, c1);
2590             }
2591             else result = FALSE;
2592             break;
2593
2594
2595             default:  /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2596             fprintf(stderr, "error in internal_horz_ordering; unknown ->use assignment\n");
2597             result = TRUE;
2598             break;
2599         }
2600     }
2601
2602     /* Now check to see if there are any constraint problems: */
2603     if ((result == TRUE) && (constrained_in_x(r1, c2) == TRUE)) result = FALSE;
2604     else if ((result == FALSE) && (constrained_in_x(r2, c1) == TRUE)) result = TRUE;
2605
2606     return(result);
2607 }
2608 /*------------------------------------------------------------------------------------*/
2609 /*------------------------------------------------------------------------------------*/
2610 int internal_vert_ordering(c1, c2)
2611     corner *c1, *c2;
2612 {
2613     range *r1 = c1->cy, *r2 = c2->cy;
2614     int min, max, r1Extent, r2Extent, temp;
2615
2616     /* return TRUE if <r1> should be placed on top of <r2>: */
2617
2618     if (natural_break_p(r1, r2) == TRUE) return(follow_natural_break(r2, r1));
2619
2620     if ((r1->use == NULL) || (r2->use == NULL))
2621     {
2622         fprintf(stderr, "error in internal_vert_ordering; NULL ->use assignment\n");
2623         return(TRUE);
2624     }
2625
2626     switch(r1->use)
2627     {
2628         case UL_CORNER: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2629         if (r2->use != UL_CORNER) return(TRUE);
2630         else
2631         {
2632             /* Ye who exits to the left-most is upper-most */
2633             return(form_horizontal_ordering(c1, c2));
2634         }
2635         break;
2636
2637
2638         case UR_CORNER: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2639         if (r2->use == UL_CORNER) return(FALSE);
2640         else if (r2->use == UR_CORNER)
2641         {
2642             /* Ye who exit to the right-most is upper-most */
2643             return(form_horizontal_ordering(c2, c1));
2644         }
2645         else  return(TRUE);
2646         break;
2647
2648
2649         case UPWARD_U: /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2650         if ((r2->use == UL_CORNER) || (r2->use == UR_CORNER)) return (FALSE);
2651         else if (r2->use == UPWARD_U)
2652         {
2653             /* place the shortest horizontal segment upper-most */
2654             perpendicular_expanse(c1->cy, &min, &max);
2655             r1Extent = max - min;
2656             perpendicular_expanse(c2->cy, &min, &max);
2657             r2Extent = max - min;
2658
2659             if (r1Extent >= r2Extent) return(FALSE);
2660             else return(TRUE);
2661         }
2662         else return(TRUE);
2663         break;
2664
2665
2666         case HORZ_UT: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2667         if ((r2->use == UL_CORNER) || (r2->use == UR_CORNER) ||
2668             (r2->use == UPWARD_U)) return (FALSE);
2669         else if (r2->use == HORZ_UT)
2670         {
2671             /* Ye who exits to the left-most is upper-most */
2672             temp = form_horizontal_ordering(c1, c2);
2673             return(temp);
2674         }
2675         else return(TRUE);
2676         break;
2677
2678
2679         case VERT_JOG:
2680         case VERT_LT:
2681         case VERT_RT:
2682         case LEFT_U:
2683         case RIGHT_U:/*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2684         if ((r2->use == UL_CORNER) || (r2->use == UR_CORNER) ||
2685             (r2->use == UPWARD_U) || (r2->use == HORZ_UT)) return (FALSE);
2686         else if ((r2->use == LL_CORNER) || (r2->use == LR_CORNER) ||
2687                  (r2->use == DOWNWARD_U) || (r2->use == HORZ_DT)) return(TRUE);
2688         else if ((r2->use == X) || (r2->use == HORZ_JOG)) return (TRUE);
2689         else
2690         {
2691             /* These are a bit tricky: Follow the external restrictions; */
2692             temp = form_vertical_ordering(c1, c2);
2693             return(temp);
2694         }
2695         break;
2696
2697         case X_CORNER:
2698         case HORZ_JOG: /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2699         if ((r2->use == UL_CORNER) || (r2->use == UR_CORNER) ||
2700             (r2->use == UPWARD_U) || (r2->use == HORZ_UT)) return (FALSE);
2701         else if ((r2->use == LL_CORNER) || (r2->use == LR_CORNER) ||
2702                  (r2->use == DOWNWARD_U) || (r2->use == HORZ_DT)) return(TRUE);
2703         else if ((r2->use == VERT_JOG) || (r2->use == VERT_LT) ||
2704                  (r2->use == VERT_RT) || (r2->use == LEFT_U) ||
2705                  (r2->use == RIGHT_U)) return(FALSE);
2706         else
2707         {
2708             /* ye who enters the top right-most is lower-most.   This rule applies
2709                unless there is interference that may lead the router to step on itself.*/
2710             if (share_bound_p(r1, r2, &c1, &c2) == TRUE)
2711                 temp = exits_top_p(c2);
2712             else if ((find_lowest_exits(r1, r2, &c1, &c2)) &&
2713                      ((c1 == least_corner(r1)) || (c2 == least_corner(r2))))
2714             {   /* True, if thing are generally turning downward */
2715                 temp = form_horizontal_ordering(c2, c1);
2716             }
2717             else /* Things are turning generally upward */
2718             {
2719                 find_highest_exits(r1, r2, &c1, &c2);
2720                 temp = form_horizontal_ordering(c1, c2);
2721             }
2722             return(temp);
2723         }
2724         break;
2725
2726         case HORZ_DT: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2727         if ((r2->use == LL_CORNER) || (r2->use == LR_CORNER) ||
2728             (r2->use == DOWNWARD_U)) return(TRUE);
2729         else if (r2->use == HORZ_DT)
2730         {
2731             /* Ye who exit to the right-most is lower-most */
2732             temp = form_horizontal_ordering(c1, c2);
2733             return(temp);
2734         }
2735         else return(FALSE);
2736         break;
2737
2738         case DOWNWARD_U: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2739         if ((r2->use == LL_CORNER) || (r2->use == LR_CORNER)) return(TRUE);
2740         else if (r2->use == DOWNWARD_U)
2741         {
2742             /* place the shortest horizontal segment lower-most */
2743             perpendicular_expanse(c1->cy, &min, &max);
2744             r1Extent = max - min;
2745             perpendicular_expanse(c2->cy, &min, &max);
2746             r2Extent = max - min;
2747
2748             if (r1Extent >= r2Extent) return(TRUE);
2749             else return(FALSE);
2750         }
2751         else return(FALSE);
2752         break;
2753
2754
2755         case LL_CORNER: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2756         if (r2->use == LR_CORNER) return(FALSE);
2757         else if (r2->use == LL_CORNER)
2758         {
2759             /* Ye who exit to the left-most is lower-most */
2760             return(form_horizontal_ordering(c2, c1));
2761         }
2762         else return(TRUE);
2763         break;
2764
2765
2766         case LR_CORNER: /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2767         if (r2->use == LR_CORNER)
2768         {
2769             /* Ye who exit to the right-most is lower-most */
2770             return(form_horizontal_ordering(c1, c2));
2771         }
2772         else return(FALSE);
2773         break;
2774
2775
2776         default:  /*- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
2777         fprintf(stderr, "error in internal_vert_ordering; unknown ->use assignment\n");
2778         return(TRUE);
2779         break;
2780     }
2781 }
2782 /*------------------------------------------------------------------------------------*/
2783 /*------------------------------------------------------------------------------------*/
2784 /*------------------------------------------------------------------------------------*/
2785 void separate_corners_for_jog(c, middleC, nextC, a)
2786     corner *c;
2787     corner **middleC, **nextC;
2788     asg_arc *a;
2789 {
2790     /* This takes a corner belonging to a completely connected net, and breaks it,
2791        duplicating an X or Y range (HORZ or VERT arc).  All corners below <middleC>
2792        will be connected via the duplicate range, all those above by the original
2793        <linkRange>. */
2794     int i, len = 0;
2795     range *linkRange, *newLink;
2796     crnlist *cl, *newCornerList = NULL;
2797
2798     if (a->page == VERT)
2799     {
2800         linkRange = c->cx;
2801         sort_list(linkRange->corners, in_x_order);      /* left-right ordering */
2802     }
2803     else
2804     {
2805         linkRange = c->cy;
2806         sort_list(linkRange->corners, in_y_order);      /* bottom-top ordering */
2807     }
2808
2809     /* find the <middleC> */
2810     len = list_length(linkRange->corners);
2811     for (cl = linkRange->corners, i = 1; cl != NULL; cl = cl->next, i++)
2812     {
2813         /* Insure that <c> becomes either <middleC> or <nextC>: */
2814         if ( ((cl->this == c) && (i <= len/2)) ||       /* <c> -> <middleC> */
2815              (cl->next->this == c) )                    /* <c> -> <nextC>   */
2816         {
2817             *middleC = cl->this;
2818             *nextC = cl->next->this;
2819             newLink = copy_range(linkRange);      /* Make the new range */
2820             newLink->corners = newCornerList = cl->next;
2821             cl->next = NULL;                        /* Clip the old corner list */
2822             break;
2823         }
2824     }
2825     for (cl = newLink->corners, i = 1; cl != NULL; cl = cl->next, i++)
2826     {
2827         /* make the attachments for the remaining ranges: */
2828         if (a->page == VERT) cl->this->cx = newLink;
2829         else cl->this->cy = newLink;
2830     }
2831 }
2832 /*------------------------------------------------------------------------------------*/
2833 range *set_horz_constraints(c1, c2, a)
2834     corner *c1, *c2;
2835     asg_arc *a;
2836 {
2837     range *r1 = c1->cx, *r2 = c2->cx;
2838     range *newRange = NULL, *insert_jog();
2839     corner *leftJogC, *rightJogC;
2840     crnlist *cl, *cll;
2841
2842     /* This function assigns pointers to corners attached to <c1> and <c2>
2843        that constrain their placement in the horizontal direction, that is
2844        when <c1> MUST be placed to the right or left of <c2> and vv.. */
2845
2846     /* If such a condition exists, AND it causes a cycle, that is an overly-
2847        constrained placement problem, then an undesired (meaning otherwise
2848        unnecessary) jog MUST be introduced to enable the problem to be solved. */
2849
2850     /* Loop through all of the important corners of <r1>: */
2851     for (cl = r1->corners; cl != NULL; cl = cl->next)
2852     {
2853         /* Loop through all of the important corners of <r2>: */
2854         for (cll = r2->corners; cll != NULL; cll = cll->next)
2855         {
2856             if ((cl->this->cx->n != cll->this->cx->n) &&
2857                 (fixed_point_p(cl->this->cy) == TRUE) &&
2858                 (repeated_srange_p(cl->this->cy, cll->this->cy) == TRUE))
2859             {
2860                 if ((exits_right_p(cl->this) == TRUE) &&
2861                     (exits_right_p(cll->this) == FALSE))
2862                 {
2863                     /* There's a problem... */
2864                     pushnew(c2, &r1->dep);              /* Record the dependency */
2865
2866                     /* lookahead one step for the nasty 'completely constrained'
2867                        problem, which is recognized as a simple cycle in the
2868                        ->dep pointer-graph: */
2869                     if (member_p(c1, c2->cx->dep, identity) == TRUE)
2870                     {
2871                         /* BIG Problem - now the cycle needs to be broken, and a jog
2872                            arbitrarily inserted.  This will cause all sorts of problems.
2873                            */
2874                         rem_item(c1, &r2->dep); /* Break the cycle... */
2875                         if (debug_level > 0)
2876                         fprintf(stderr,"Nets %s and %s completely constrainted in X.\n",
2877                                 r1->n->name, r2->n->name);
2878                         separate_corners_for_jog(cl->this, &leftJogC, &rightJogC, a);
2879                         newRange = insert_jog(leftJogC, rightJogC, a, TRUE);
2880                     }
2881                 }
2882                 else if  ((exits_right_p(cl->this) == FALSE) &&
2883                           (exits_right_p(cll->this) == TRUE))
2884                 {
2885                     /* There is a known dependency, but things are ok. */
2886                     pushnew(c1, &r2->dep);
2887
2888                     /* lookahead one step for the nasty 'completely constrained'
2889                        problem, which is recognized as a simple cycle in the
2890                        ->dep pointer-graph: */
2891                     if (member_p(c2, c1->cx->dep, identity) == TRUE)
2892                     {
2893                         /* BIG Problem - now the cycle needs to be broken, and a jog
2894                            arbitrarily inserted.  This will cause all sorts of problems.
2895                            */
2896                         rem_item(c2, &r1->dep); /* Break the cycle... */
2897                         if (debug_level > 0)
2898                         fprintf(stderr,"Nets %s and %s completely constrainted in X.\n",
2899                                 r1->n->name, r2->n->name);
2900                         separate_corners_for_jog(cl->this, &leftJogC, &rightJogC, a);
2901                         newRange = insert_jog(leftJogC, rightJogC, a, TRUE);
2902                     }
2903                 }
2904             }
2905             /* Otherwise, we don't care. */
2906         }
2907     }
2908     return(newRange);
2909 }
2910
2911 /*------------------------------------------------------------------------------------*/
2912 /*------------------------------------------------------------------------------------*/
2913 range *set_vert_constraints(c1, c2, a)
2914     corner *c1, *c2;
2915     asg_arc *a;
2916 {
2917     range *r1 = c1->cy, *r2 = c2->cy;
2918     range *newRange = NULL, *insert_jog();
2919     corner *botJogC, *topJogC;
2920     crnlist *cl, *cll;
2921
2922     /* This function assigns pointers to corners attached to <c1> and <c2>
2923        that constrain their placement in the vertical direction, that is
2924        when <c1> MUST be placed to the right or left of <c2> and vv.. */
2925
2926     /* If such a condition exists, AND it causes a cycle, that is an overly-
2927        constrained placement problem, then an undesired (meaning otherwise
2928        unnecessary) jog MUST be introduced to enable the problem to be solved. */
2929
2930     /* Loop through all of the important corners of <r1>: */
2931     for (cl = r1->corners; cl != NULL; cl = cl->next)
2932     {
2933         /* Loop through all of the important corners of <r2>: */
2934         for (cll = r2->corners; cll != NULL; cll = cll->next)
2935         {
2936             if ((cl->this->cx->n != cll->this->cx->n) &&
2937                 (fixed_point_p(cl->this->cx) == TRUE) &&
2938                 (repeated_srange_p(cl->this->cx, cll->this->cx) == TRUE))
2939             {
2940                 if ((exits_top_p(cl->this) == FALSE) &&
2941                     (exits_top_p(cll->this) == TRUE))
2942                 {
2943                     /* There's a problem... */
2944                     pushnew(c2, &r1->dep);              /* Record the dependency */
2945
2946                     /* lookahead one step for the nasty 'completely constrained'
2947                        problem, which is recognized as a simple cycle in the ->dep
2948                        pointer-graph: */
2949                     if (member_p(c1, c2->cy->dep, identity) == TRUE)
2950                     {
2951                         /* BIG Problem - now the cycle needs to be broken, and a jog
2952                            arbitrarily inserted.  This will cause all sorts of problems.
2953                            */
2954                         rem_item(c1, &r2->dep);
2955                         if (debug_level > 0)
2956                         fprintf(stderr,"Nets %s and %s completely constrainted in Y.\n",
2957                                 r1->n->name, r2->n->name);
2958                         separate_corners_for_jog(cl->this, &botJogC, &topJogC, a);
2959                         newRange = insert_jog(botJogC, topJogC, a, TRUE);
2960                     }
2961                 }
2962                 else if ((exits_top_p(cl->this) == FALSE) &&
2963                          (exits_top_p(cll->this) == TRUE))
2964                 {
2965                     /* There is a known dependency, but things are ok. */
2966                     pushnew(c1, &r2->dep);              /* Record the dependency */
2967
2968                     /* lookahead one step for the nasty 'completely constrained'
2969                        problem, which is recognized as a simple cycle in the ->dep
2970                        pointer-graph: */
2971                     if (member_p(c2, c1->cy->dep, identity) == TRUE)
2972                     {
2973                         /* BIG Problem - now the cycle needs to be broken, and a jog
2974                            arbitrarily inserted.  This will cause all sorts of problems.
2975                            */
2976                         rem_item(c2, &r1->dep);
2977                         if (debug_level > 0)
2978                         fprintf(stderr,"Nets %s and %s completely constrainted in Y.\n",
2979                                 r2->n->name, r1->n->name);
2980                         separate_corners_for_jog(cl->this, &botJogC, &topJogC, a);
2981                         newRange = insert_jog(botJogC, topJogC, a, TRUE);
2982                     }
2983                 }
2984
2985             }
2986             /* Otherwise, we don't care. */
2987         }
2988     }
2989     return(newRange);
2990 }
2991
2992 /*------------------------------------------------------------------------------------*/
2993 int constrained_in_x(r, c)
2994     range *r;
2995     corner *c;
2996 {
2997     /* return TRUE if the corner <c> appears anywhere along the dependency chain
2998        of <r>. */
2999     /* This had better be an acyclic graph. */
3000     crnlist *cl;
3001
3002     for (cl = r->dep; cl != NULL; cl = cl->next)
3003     {
3004         if (cl->this == c) return(TRUE);
3005         if (constrained_in_x(cl->this->cx, c) != FALSE) return(TRUE);
3006     }
3007     return(FALSE);
3008 }
3009 /*------------------------------------------------------------------------------------*/
3010 int constrained_in_y(r, c)
3011     range *r;
3012     corner *c;
3013 {
3014     /* return TRUE if the corner <c> appears anywhere along the dependency chain
3015        of <r>. */
3016     /* This had better be an acyclic graph. */
3017     crnlist *cl;
3018
3019     for (cl = r->dep; cl != NULL; cl = cl->next)
3020     {
3021         if (cl->this == c) return(TRUE);
3022         if (constrained_in_y(cl->this->cy, c) != FALSE) return(TRUE);
3023     }
3024     return(FALSE);
3025 }
3026 /*------------------------------------------------------------------------------------*/
3027 /*------------------------------------------------------------------------------------*/
3028 /*------------------------------------------------------------------------------------*/
3029 void evaluate_corner_placement_constraints(cornersOfNote, a)
3030     crnlist **cornersOfNote;
3031     asg_arc *a;
3032 {
3033     range *r = NULL;
3034     rnglist *rl, *jogList = NULL;
3035     corner *c = (*cornersOfNote)->this;
3036     crnlist *cl, *cll;
3037
3038     r = (a->page == VERT) ? c->cx : c->cy;
3039
3040     /* Record the physical constraints on the ranges: */
3041
3042     for(cl = *cornersOfNote; cl != NULL; cl = cl->next)
3043     {
3044         if (cl->next != NULL)
3045         {
3046             for(cll = cl->next; cll != NULL; cll = cll->next)
3047             {
3048                 r = (a->page == VERT) ?
3049                     set_horz_constraints(cl->this, cll->this, a):
3050                     set_vert_constraints(cl->this, cll->this, a);
3051                 if (r != NULL)
3052                 {
3053                     /* Somehow add this range into the set being considered */
3054                     push(r, &jogList);
3055                 }
3056             }
3057         }
3058     }
3059     /* For each range located (there is one per jog introduced), add the
3060        corresponding corner to the <cornersOfNote> list: */
3061     for(rl = jogList; rl != NULL; rl = rl->next)
3062     {
3063         for(cl = rl->this->corners; cl != NULL; cl = cl->next)
3064         if (member_p(cl->this, *cornersOfNote, identity) != TRUE)
3065         {
3066             push(cl->this, cornersOfNote);
3067             break;
3068         }
3069     }
3070 }
3071
3072 /*------------------------------------------------------------------------------------*/
3073 void horz_decouple_corners(a)
3074     asg_arc *a;
3075 {
3076     /* This function decouples the given set of corners in the vertical
3077        dimension.  All of these corners are in the same arc and need decoupling.
3078        This function aims at decoupling all of the vertical segments in the
3079        given set of corners, which is the unique set of x ranges.
3080
3081        This is accomplished by forming a list of all horizontal ranges that exit on
3082        the left side of the box, and those that exit on the right.  These are ordered
3083        (bottom to top) based on their external connections.
3084
3085        Given this ordering, a given vertical segment can be ordered based on the
3086        following set of rules aimed at optimizing the internal characteristics of
3087        the box:
3088
3089        Looking from the right-side of the box:
3090        The segment that is part of a uturn with the shortest y extent is right most,
3091        followed in turn by all other uturns.  All segments that form an L (angle)
3092        through the top and right are ordered in order of their top-bottom ordering
3093        (top-most -> right-most).  Then the segments that form Z or bottom L turns are
3094        ordered left to right as per their top-bottom ordering (top-most -> left-most).
3095        The process is then repeated for the left-side.
3096
3097        NOTE: the only special case is with T formations, which are considered as
3098        Z arangements as opposed to their U or L arrangements.
3099        */
3100
3101     crnlist *cl, *cll, *temp, *cornersOfNote = NULL;
3102     range *r, *set_horz_constraints();
3103     rnglist *unique, *uniqueRanges = NULL;
3104     list *nonOverlap, *l;
3105     int horzIndex = 0, maxIndex = list_length(a->corners);
3106
3107     /* exit quickly if there's nothing to do... */
3108     if (a->corners == NULL) return;
3109
3110 /* Form the ordering that defines how the ranges are to be decoupled: */
3111     /* Start by characterizing the usage of the vertical segments in the tile: */
3112     for (cl = a->corners; cl != NULL; cl = cl->next)
3113     {
3114         /* Each unique x-range represents a segment that runs parallel to the
3115            Y-Axis, and probably two corners in the box (most formations are Z,
3116            rather than L arrangements).
3117            By the way, these are the segements that we need to decouple.*/
3118
3119         cl->this->horzOrder = maxIndex;     /* Need to insure that the ordering scheme
3120                                                used by "in_reasonable_horz_orderR"
3121                                                works */
3122         unique = (rnglist *) member(cl->this->cx->sr, uniqueRanges, check_sranges);
3123         if (unique == NULL)
3124         {
3125             r = cl->this->cx;
3126             r->use = 0;
3127
3128             push(cl->this, &cornersOfNote);
3129             push(r, &uniqueRanges);
3130             if (range_exits_bottom(r, a) == TRUE) r->use += BOT_EDGE;
3131             if (range_exits_top(r, a) == TRUE) r->use += TOP_EDGE;
3132             if (range_exits_left(cl->this->cy, a) == TRUE) r->use += LEFT_EDGE;
3133             if (range_exits_right(cl->this->cy, a) == TRUE) r->use += RIGHT_EDGE;
3134         }
3135         else /* treat Jog/ U combinations as U's: (gives better aesthetics) */
3136         {
3137             r = unique->this;
3138             if (range_exits_left(cl->this->cy, a) == TRUE)
3139             {
3140                 if (r->use == RIGHT_U)  r->use += LEFT_EDGE;
3141                 else if (r->use == LEFT_EDGE + RIGHT_EDGE) r->use -= RIGHT_EDGE;
3142             }
3143             else if (range_exits_right(cl->this->cy, a) == TRUE)
3144             {
3145                 if (r->use == LEFT_U) r->use += RIGHT_EDGE;
3146                 else if (r->use == LEFT_EDGE + RIGHT_EDGE) r->use -= LEFT_EDGE;
3147             }
3148         }
3149         if (r->use == NULL)
3150         {
3151             r->use = VERT_JOG;
3152         }
3153     }
3154
3155     /* Setup constraints, and add jogs as required: */
3156     evaluate_corner_placement_constraints(&cornersOfNote, a);
3157
3158
3159     /* Now each range of interest is listed in <uniqueRanges> and has been characterized
3160        for its usage within the given arc.  Given this arrangement, the ranges are
3161        ordered, first for aesthetics, and then for physical constraints.  */
3162     merge_sort_list(&cornersOfNote, internal_horz_ordering);
3163     uniqueRanges = (rnglist *)free_list(uniqueRanges);
3164
3165     /* Now map this corner list into the all-important range list: */
3166     for (cl = cornersOfNote; cl != NULL; cl = cl->next)
3167     {
3168         queue(cl->this->cx, &uniqueRanges);     /* Use queue to preserve order... */
3169         cl->this->horzOrder = horzIndex++;      /* Mark the ordering for the sorter */
3170     }
3171
3172
3173     /* There are several problems to be resolved - the first of which is the
3174        column reuse problem - If permitted, then there are subsets of ranges that
3175        do not interfere with each other.  To solve this, the ordered set of corners
3176        is broken into a set of ordered ranges;  The longest set of these (interfering)
3177        ranges is then decoupled, and then the next longest, until all ranges have
3178        been checked.  */
3179
3180     /* First - form sets of non-overlapping ranges:  That is, to be part of a set,
3181        the given corner must overlapp with ALL of the corners in the set;  From
3182        this set use the L->R ordering to form a dependency graph..      */
3183
3184     /* From this list of ranges, develop a dependency graph: */
3185     nonOverlap = form_dependency_graph(uniqueRanges);
3186
3187     /* OK - Now the dependency graph has been made - so use it... */
3188     for(l = sort_list(nonOverlap, in_length_order); l != NULL; l = l->next)
3189     {
3190         unique = (rnglist *)slow_sort_list(rcopy_list(l->this), in_reasonable_horz_orderR);
3191         decouple_ordered_ranges(unique);
3192         free_list(l->this);
3193         free_list(unique);
3194     }
3195
3196     free_list(uniqueRanges);
3197     free_list(nonOverlap);
3198 }
3199 /*------------------------------------------------------------------------------------*/
3200 void vert_decouple_corners(a)
3201     asg_arc *a;
3202 {
3203     /* This function decouples the given set of corners in the vertical
3204        dimension.  All of these corners are in the same asg_arc and need decoupling.
3205        This function aims at decoupling all of the vertical segments in the
3206        given set of corners, which is the unique set of x ranges.
3207
3208        This is accomplished by forming a list of all horizontal ranges that exit on
3209        the left side of the box, and those that exit on the right.  These are ordered
3210        (bottom to top) based on their external connections.
3211
3212        Given this ordering, a given vertical segment can be ordered based on the
3213        following set of rules aimed at optimizing the internal characteristics of
3214        the box:
3215
3216        Looking from the right-side of the box:
3217        The segment that is part of a uturn with the shortest y extent is right most,
3218        followed in turn by all other uturns.  All segments that form an L (angle)
3219        through the top and right are ordered in order of their top-bottom ordering
3220        (top-most -> right-most).  Then the segments that form Z or bottom L turns are
3221        ordered left to right as per their top-bottom ordering (top-most -> left-most).
3222        The process is then repeated for the left-side.
3223
3224        NOTE: the only special case is with T formations, which are considered as
3225        Z arangements as opposed to their U or L arrangements.
3226        */
3227
3228     crnlist *cl, *cll, *cornersOfNote = NULL;
3229     range *r, *set_vert_constraints();
3230     rnglist *unique, *uniqueRanges = NULL;
3231     list *nonOverlap, *l;
3232     int vertIndex = 0, maxIndex = list_length(a->corners);
3233
3234     /* exit quickly if there's nothing to do... */
3235     if (a->corners == NULL) return;
3236
3237 /* Form the ordering that defines how the ranges are to be decoupled: */
3238     /* Start by characterizing the usage of the vertical segments in the tile: */
3239     for (cl = a->corners; cl != NULL; cl = cl->next)
3240     {
3241         /* Each unique x-range represents a segment that runs parallel to the
3242            Y-Axis, and probably two corners in the box (most formations are Z,
3243            rather than L arrangements).
3244            By the way, these are the segements that we need to decouple.*/
3245
3246         cl->this->vertOrder = maxIndex;     /* Need to insure that the ordering scheme
3247                                                used by "in_reasonable_vert_orderR"
3248                                                works */
3249         unique = (rnglist *) member(cl->this->cy->sr, uniqueRanges, check_sranges);
3250         if (unique == NULL)
3251         {
3252             r = cl->this->cy;
3253             r->use = 0;
3254
3255             push(cl->this, &cornersOfNote);
3256             push(r, &uniqueRanges);
3257             if (range_exits_bottom(cl->this->cx, a) == TRUE) r->use += BOT_EDGE;
3258             if (range_exits_top(cl->this->cx, a) == TRUE) r->use += TOP_EDGE;
3259             if (range_exits_left(r, a) == TRUE) r->use += LEFT_EDGE;
3260             if (range_exits_right(r, a) == TRUE) r->use += RIGHT_EDGE;
3261         }
3262         else /* Classify Jog/U combinations as U's: (gives better aesthetics) */
3263         {
3264             r = unique->this;
3265             if (range_exits_bottom(cl->this->cx, a) == TRUE)
3266             {
3267                 if (r->use == UPWARD_U) r->use += BOT_EDGE;
3268                 else if (r->use == BOT_EDGE + TOP_EDGE) r->use -= TOP_EDGE;
3269             }
3270             else if (range_exits_top(cl->this->cx, a) == TRUE)
3271             {
3272                 if (r->use == DOWNWARD_U) r->use += TOP_EDGE;
3273                 else if (r->use == BOT_EDGE + TOP_EDGE) r->use -= BOT_EDGE;
3274             }
3275         }
3276         if (r->use == NULL)
3277         {
3278             r->use = HORZ_JOG;
3279         }
3280     }
3281
3282     /* Setup constraints, and add jogs as required: */
3283     evaluate_corner_placement_constraints(&cornersOfNote, a);
3284
3285
3286     /* Now each range of interest is listed in <uniqueRanges> and has been characterized
3287        for its usage within the given asg_arc.  Given this arrangement, the ranges are
3288        ordered, first for aesthetics, then for physical constraints.  */
3289     merge_sort_list(&cornersOfNote, internal_vert_ordering);
3290     uniqueRanges = (rnglist *)free_list(uniqueRanges);
3291
3292     /* Now map this corner list into the all-important range list: */
3293     for (cl = cornersOfNote; cl != NULL; cl = cl->next)
3294     {
3295         queue(cl->this->cy, &uniqueRanges);     /* Use queue to preserve order... */
3296         cl->this->vertOrder = vertIndex++;      /* Mark the ordering for the sorter */
3297     }
3298
3299
3300     /* There are several problems to be resolved - the first of which is the
3301        column reuse problem - If permitted, then there are subsets of ranges that
3302        do not interfere with each other.  To solve this, the ordered set of corners
3303        is broken into a set of ordered ranges;  The longest set of these (interfering)
3304        ranges is then decoupled, and then the next longest, until all ranges have
3305        been checked.  */
3306
3307     /* First - form sets of non-overlapping ranges:  That is, to be part of a set,
3308        the given corner must overlapp with ALL of the corners in the set;  From
3309        this set use the L->R ordering to form a dependency graph..      */
3310
3311     /* From this list of ranges, develop a dependency graph: */
3312     nonOverlap = form_dependency_graph(uniqueRanges);
3313
3314     /* OK - Now the dependency graph has been made - so use it... */
3315     for(l = sort_list(nonOverlap, in_length_order); l != NULL; l = l->next)
3316     {
3317         unique = (rnglist *)slow_sort_list(l->this, in_reasonable_vert_orderR);
3318         decouple_ordered_ranges(unique);
3319         free_list(l->this);
3320     }
3321
3322     free_list(uniqueRanges);
3323     free_list(nonOverlap);
3324 }
3325 /*------------------------------------------------------------------------------------*/
3326 /*------------------------------------------------------------------------------------*/
3327 void form_into_nonoverlapping_ranges(tl)
3328     tilist *tl;
3329 {
3330     tilist *tll;
3331     asg_arc *a;
3332     crnlist *cl;
3333
3334     int x1, y1, x2, y2;
3335
3336     for (tll = tl; tll != NULL; tll = tll->next)
3337     {
3338         /* Walk down this ordered list of asg_arcs, resolving the overlapped ranges */
3339         a = (asg_arc *)tll->this->this;
3340
3341         /* Divide the ranges listed in the corner structures into two lists, so they can
3342            be compared to each other: */
3343
3344         if (debug_level == 4)
3345         {
3346             if (a->page == VERT)
3347             {
3348                 x1 = tll->this->y_pos;          y1 = tll->this->x_pos;
3349                 x2 = x1 + tll->this->y_len;     y2 = y1 + tll->this->x_len;
3350             }
3351             else
3352             {
3353                 x1 = tll->this->x_pos;          y1 = tll->this->y_pos;
3354                 x2 = x1 + tll->this->x_len;     y2 = y1 + tll->this->y_len;
3355             }
3356
3357         fprintf(stderr, "\nExamining box at (%d, %d) to (%d, %d)[%s]\n",
3358                 x1, y1, x2, y2, (a->page == VERT) ? "v" : "h");
3359         }
3360
3361         if (a->page == VERT) horz_decouple_corners(a);
3362         else vert_decouple_corners(a);
3363     }
3364 }
3365 /*------------------------------------------------------------------------------------*/
3366 int link_value(r)
3367     range *r;
3368 {
3369     if (r != NULL) return (r->sr->q2 - r->sr->q1);
3370     else return (HASH_SIZE * 10);                       /* Some big number */
3371 }
3372 /*------------------------------------------------------------------------------------*/
3373 trail *locate_parent_trail(n, c)
3374     net *n;
3375     corner *c;
3376 {
3377     /* given a corner, and the net to which it belongs, locate the expansion that
3378        contains the corner (VERY SPECIAL -> depends on the trail->used pointers) */
3379
3380     expn *ex = (expn *)n->done->this;
3381     trlist *trl;
3382     crnlist *cl;
3383
3384     for (trl = ex->connections; trl != NULL; trl = trl->next)
3385     {
3386         for (cl = trl->this->used; cl != NULL; cl = cl->next)
3387         {
3388             if (cl->this == c) return(trl->this);
3389         }
3390     }
3391     return(NULL);
3392 }
3393
3394 /*------------------------------------------------------------------------------------*/
3395 tile *locate_for_corner(ts, x, y)
3396     tile * ts;
3397     int x, y;
3398 {
3399     /* Locate a tile in the tilespace dentoed by <ts> at the given point.
3400        Because this is used for locating a corner, the boundry conditions for
3401        location are modified from those given in "locate" as defined in cstitch.c. */
3402
3403     tile *t = locate(ts, x, y);
3404     asg_arc *a = (t != NULL) ? (asg_arc *)t->this : NULL;
3405
3406     if (a->mod != NULL)
3407     {
3408         if (t->x_pos + t->x_len == x) return(locate(t, ++x, y));
3409         if (t->x_pos == x) return(locate(t, --x, y));
3410         if (t->y_pos + t->y_len == y) return(locate(t, x, ++y));
3411         if (t->y_pos == y) return(locate(t, x, --y));
3412     }
3413     return(t);
3414 }
3415
3416 /*------------------------------------------------------------------------------------*/
3417 corner* create_linkage_between(c1, c2, linkRange, a, forcedJog)
3418     corner *c1, *c2;
3419     range *linkRange;
3420     asg_arc *a;
3421     int forcedJog;
3422 {
3423     int orient = a->page;
3424     corner *link1, *link2;
3425     tile *newTile1, *newTile2;
3426     asg_arc *newArc;
3427     arclist *al;
3428     net *n = c1->cx->n;
3429     trail *tr = locate_parent_trail(n, c1);
3430
3431     if (a->page == VERT)
3432     {
3433         link1 = create_corner(c1->cx, linkRange, c1->al->this, NULL);
3434         newTile1 = locate_for_corner(routingRoot[HORZ][0], midpoint(c1->cx),
3435                                      midpoint(linkRange));
3436         add_corner_to_arc(link1, newTile1->this);
3437         for (al = c1->al->next; al != NULL; al = al->next)
3438             add_corner_to_arc(link1, al->this);
3439
3440         link2 = create_corner(c2->cx, linkRange, c2->al->this, NULL);
3441         newTile2 = locate_for_corner(routingRoot[HORZ][0], midpoint(c2->cx),
3442                                      midpoint(linkRange));
3443         add_corner_to_arc(link2, newTile2->this);
3444         for (al = c2->al->next; al != NULL; al = al->next)
3445             add_corner_to_arc(link2, al->this);
3446     }
3447
3448     else  /* (a->Page == HORZ)  */
3449     {
3450         link1 = create_corner(linkRange, c1->cy, c1->al->this, NULL);
3451         newTile1 = locate_for_corner(routingRoot[VERT][0], midpoint(c1->cy),
3452                                      midpoint(linkRange));
3453         add_corner_to_arc(link1, newTile1->this);
3454         for (al = c1->al->next; al != NULL; al = al->next)
3455             add_corner_to_arc(link1, al->this);
3456
3457         link2 = create_corner(linkRange, c2->cy, c2->al->this, NULL);
3458         newTile2 = locate_for_corner(routingRoot[VERT][0], midpoint(c2->cy),
3459                                      midpoint(linkRange));
3460         add_corner_to_arc(link2, newTile2->this);
3461         for (al = c2->al->next; al != NULL; al = al->next)
3462             add_corner_to_arc(link2, al->this);
3463     }
3464     if (tr != NULL)     /* At a later stage of the local router (this is a hack) */
3465     {
3466         push(link1, &tr->used);
3467         pushnew(newTile1, &n->route);
3468         push(link2, &tr->used);
3469         pushnew(newTile2, &n->route);
3470     }
3471     else if (forcedJog == TRUE)         /* When the jog has been forced... */
3472     {
3473         push(link1, &n->route);
3474         push(link2, &n->route);
3475     }
3476
3477     if (debug_level > 0)
3478     if (tr != NULL)
3479     fprintf(stderr, "Adding jog to <%s>{%s %s} from ([%d,%d],[%d,%d]) to ([%d,%d],[%d,%d]) \n",
3480             n->name, tr->ex->t->name, tr->ex->t->mod->name,
3481             link1->cx->sr->q1, link1->cx->sr->q2, link1->cy->sr->q1, link1->cy->sr->q2,
3482             link2->cx->sr->q1, link2->cx->sr->q2, link2->cy->sr->q1, link2->cy->sr->q2);
3483     else
3484     fprintf(stderr, "Adding jog to <%s> from ([%d,%d],[%d,%d]) to ([%d,%d],[%d,%d]) \n",
3485             n->name,
3486             link1->cx->sr->q1, link1->cx->sr->q2, link1->cy->sr->q1, link1->cy->sr->q2,
3487             link2->cx->sr->q1, link2->cx->sr->q2, link2->cy->sr->q1, link2->cy->sr->q2);
3488
3489     return(link1);
3490 }
3491 /*------------------------------------------------------------------------------------*/
3492 range *insert_jog(c, linkC, a, forcedJog)
3493     corner *c, *linkC;
3494     asg_arc *a;
3495     int forcedJog;      /* Flag */
3496 {
3497     /* This adds the corners necessary to <a> (if any) to connect <c> to <c2>. */
3498
3499     /* There are two cases: either a contains a range that can be exploited to link the
3500        two, or it doesn't. */
3501
3502     corner *link = NULL;
3503     crnlist *cl;
3504     range *linkRange;
3505     int min, max;
3506
3507     for (cl = a->corners; ((cl != NULL) && (forcedJog == FALSE)); cl = cl->next)
3508     {
3509         if ((cl->this->cx->n == c->cx->n) &&            /* Only unique corners of */
3510             ((cl->this != c) && (cl->this != linkC)))   /* the same net qualify.  */
3511         {
3512             if (a->page == VERT)
3513             {
3514                 if ((overlapped_p(cl->this->cx->sr, c->cx->sr) == TRUE) &&
3515                     (overlapped_p(cl->this->cx->sr, linkC->cx->sr) == TRUE))
3516                 {
3517                     link = create_linkage_between(c, linkC, cl->this->cy, a, forcedJog);
3518                     break;
3519                 }
3520             }
3521             else /* (a->Page == HORZ)  */
3522             {
3523                 if ((overlapped_p(cl->this->cy->sr, c->cy->sr) == TRUE) &&
3524                     (overlapped_p(cl->this->cy->sr, linkC->cy->sr) == TRUE))
3525                 {
3526                     link = create_linkage_between(c, linkC, cl->this->cx, a, forcedJog);
3527                     break;
3528                 }
3529             }
3530         }
3531     }
3532
3533     /* OK - There's nothing to leverage from... */
3534     if (link == NULL)
3535     {
3536         if (a->page == VERT)
3537         {
3538             min = MIN(linkC->cy->sr->q1, c->cy->sr->q1);
3539             max = MAX(linkC->cy->sr->q2, c->cy->sr->q2);
3540
3541             if (min != max)
3542             {
3543                 linkRange = create_range(create_srange(min, max, HORZ), c->cx->n);
3544             }
3545             else
3546             {
3547                 /* There is the odd case of where a U needs to be formed, in which case
3548                    the link range min/max is determined by the tile that the corners
3549                    fall into. */
3550
3551                 if (a->t->x_pos == min)  /* Left-side U */
3552                 {
3553                     linkRange = create_range
3554                     (create_srange(min, a->t->x_pos + a->t->x_len, HORZ), c->cx->n);
3555                 }
3556                 else if (a->t->x_pos + a->t->x_len == max)  /* Right-side U */
3557                 {
3558                     linkRange = create_range
3559                     (create_srange(min, a->t->x_pos, HORZ), c->cx->n);
3560                 }
3561                 else /* NO CLUE! */
3562                 {
3563                     linkRange = create_range(create_srange(min, max, HORZ), c->cx->n);
3564                 }
3565             }
3566             create_linkage_between(c, linkC, linkRange, a, forcedJog);
3567         }
3568         else
3569         {
3570             min = MIN(linkC->cx->sr->q1, c->cx->sr->q1);
3571             max = MAX(linkC->cx->sr->q2, c->cx->sr->q2);
3572
3573             if (min != max)
3574             {
3575                 linkRange = create_range(create_srange(min, max, VERT), c->cx->n);
3576             }
3577             else
3578             {
3579                 /* There is the odd case of where a U needs to be formed */
3580                 if (a->t->x_pos == min)  /* Left-side U */
3581                 {
3582                     linkRange = create_range
3583                     (create_srange(min, a->t->x_pos + a->t->x_len, VERT), c->cx->n);
3584                 }
3585                 else if (a->t->x_pos + a->t->x_len == max)  /* Right-side U */
3586                 {
3587                     linkRange = create_range
3588                     (create_srange(min, a->t->x_pos, VERT), c->cx->n);
3589                 }
3590                 else /* NO CLUE! */
3591                 {
3592                     linkRange = create_range(create_srange(min, max, VERT), c->cx->n);
3593                 }
3594             }
3595             create_linkage_between(c, linkC, linkRange, a, forcedJog);
3596         }
3597     }
3598     return(linkRange);
3599 }
3600 /*------------------------------------------------------------------------------------*/
3601 corner *choose_best_link(n, a, setJogsP)
3602     net *n;
3603     asg_arc *a;
3604     int setJogsP;
3605 {
3606     /* find the best link in the given direction among the ranges given */
3607     /* This is done by running through the candidates for the best link, and
3608        counting the number of jogs that they require.  the one with the lowest
3609        count wins.  (This is still pretty arbitrary)
3610        */
3611
3612     /* There is a difficult problem to catch in the determination of the need for
3613        a jog - that is when there is a corner that two (or more) other corners
3614        can jog to, but if one jogs to it, the ensuing constraint does not
3615        permit the successive corners from being able to jog.
3616
3617        To avoid this problem, temp ranges are maintained and used to indicate
3618        where added jogs will be required due to dependencies among the
3619        links saught.
3620        */
3621
3622     crnlist *cl, *cll;
3623     corner *linkCorner = NULL;
3624     int orientation = a->page;
3625     range *bestLink = NULL, *testLink = NULL;
3626     range *testLinkCopy, *copy, *r;
3627     int count, bestCount = (HASH_SIZE * 50) - 1;                /* Some big number */
3628
3629     for (cl = a->corners; cl != NULL; cl = cl->next)
3630     {
3631         /* Try cl->this as the <testLink> corner: */
3632         /* Only pay attention to corners belonging to the given net: */
3633         if ((cl->this->cy != NULL) && (cl->this->cy->n == n))
3634         {
3635             count = 0;
3636             testLink = (orientation == VERT) ? cl->this->cx : cl->this->cy;
3637             testLinkCopy = quick_copy_range(testLink);
3638
3639             for (cll = a->corners; cll != NULL; cll = cll->next)
3640             {
3641                 /* Only pay attention to corners belonging to the given net: */
3642                 if ((cll != cl) &&
3643                     ((cll->this->cy != NULL) && (cll->this->cy->n == n)))
3644                 {
3645                     if (orientation == VERT)
3646                     {
3647                         r = cl->this->cx;               /* Used for debugging */
3648                         if (overlapped_p(cll->this->cx->sr, testLinkCopy->sr) != TRUE)
3649                         {
3650                             /* need to insert a jog of some sort.... */
3651                             count++;
3652                         }
3653                         else /* Restrict the <testLinkCopy> */
3654                         {
3655                             copy = quick_copy_range(cll->this->cx);
3656                             reduce_to_least_common_range(testLinkCopy->sr, copy->sr);
3657                             free(copy);
3658                         }
3659                     }
3660                     else
3661                     {
3662                         r = cl->this->cy;
3663                         if (overlapped_p(cll->this->cy->sr, testLinkCopy->sr) != TRUE)
3664                         {
3665                             /* time to insert a jog of some sort.... */
3666                             count++;
3667                         }
3668                         else /* Restrict the <testLinkCopy> */
3669                         {
3670                             copy = quick_copy_range(cll->this->cy);
3671                             reduce_to_least_common_range(testLinkCopy->sr, copy->sr);
3672                             free(copy);
3673                         }
3674                     }
3675                     if (count > bestCount) break;
3676                 }
3677             } /* end inner loop */
3678
3679
3680             /* Now check and conditionally update the bestLink...*/
3681             if ((count <= bestCount) &&
3682                 ((bestLink == NULL) ||(link_value(testLink) >= link_value(bestLink))))
3683             {
3684                 linkCorner = cl->this;
3685                 bestLink = quick_copy_range(testLinkCopy);
3686                 bestCount = count;
3687             }
3688
3689             free(testLinkCopy);         /* Collect Garbage... */
3690
3691         } /* end IF right net...*/
3692     } /* end outer loop */
3693
3694     /* Hopefully, the best link corner has now been discovered, so use it <linkCorner>.
3695        See if any jogs need to be calculated: */
3696
3697     if (setJogsP == TRUE)
3698     {
3699         /* cleanup requested, so do it... */
3700         for (cl = a->corners; cl != NULL; cl = cl->next)
3701         {
3702             /* Only pay attention to corners belonging to the given net: */
3703             if ((cl->this != linkCorner) &&
3704                 (cl->this->cx != NULL) && (cl->this->cx->n == n))
3705             {
3706                 if (orientation == VERT)
3707                 {
3708                     if (overlapped_p(cl->this->cx->sr, bestLink->sr) != TRUE)
3709                     {
3710                         insert_jog(cl->this, linkCorner, a, FALSE);
3711                     }
3712                 }
3713                 else
3714                 {
3715                     if (overlapped_p(cl->this->cy->sr, bestLink->sr) != TRUE)
3716                     {
3717                         insert_jog(cl->this, linkCorner, a, FALSE);
3718                     }
3719                 }
3720             }
3721         }
3722     }
3723     free(bestLink);     /* Garbage */
3724
3725     return(linkCorner);
3726 }
3727 /*------------------------------------------------------------------------------------*/
3728 corner *old_choose_best_link(n, a, setJogsP)
3729     net *n;
3730     asg_arc *a;
3731     int setJogsP;
3732 {
3733     /* find the best link in the given direction among the ranges given */
3734
3735     crnlist *cl, *cll;
3736     corner *linkCorner = NULL;
3737     int orientation = a->page;
3738     range *bestLink = NULL;
3739     int linkVal = (HASH_SIZE * 50) - 1;                 /* Some big number */;
3740
3741     for (cl = a->corners; cl != NULL; cl = cl->next)
3742     {
3743         /* Only pay attention to corners belonging to the given net: */
3744         if ((cl->this->cy != NULL) && (cl->this->cy->n == n))
3745         {
3746             if (orientation == VERT)
3747             {
3748                 if ((bestLink == NULL) ||
3749                     (link_value(cl->this->cx) <= linkVal))
3750                 {
3751                     if ((bestLink != NULL) && (setJogsP == TRUE) &&
3752                         (overlapped_p(cl->this->cx->sr, bestLink->sr) != TRUE))
3753                     {
3754                         /* time to insert a jog of some sort.... */
3755                         insert_jog(cl->this, linkCorner, a, FALSE);
3756                     }
3757                     linkCorner = cl->this;
3758                     bestLink = cl->this->cx;
3759                     linkVal = link_value(bestLink);  /* BUGG ??? */
3760                 }
3761             }
3762
3763             else
3764             {
3765                 if ((bestLink == NULL) ||
3766                     (link_value(cl->this->cy) <= linkVal))
3767                 {
3768                     if ((bestLink != NULL) && (setJogsP == TRUE) &&
3769                         (overlapped_p(cl->this->cy->sr, bestLink->sr) != TRUE))
3770                     {
3771                         /* time to insert a jog of some sort.... */
3772                         insert_jog(cl->this, linkCorner, a, FALSE);
3773                     }
3774                     linkCorner = cl->this;
3775                     bestLink = cl->this->cy;
3776                     linkVal = link_value(bestLink);
3777                 }
3778             }
3779         }
3780     }
3781     return(linkCorner);
3782 }
3783 /*------------------------------------------------------------------------------------*/
3784 /*------------------------------------------------------------------------------------*/
3785 int adjacent_p(t1, t2, axis)
3786     tile *t1, *t2;
3787     int axis;
3788 {
3789     if ((axis == X) &&
3790         ((t1->x_pos == t2->x_pos + t2->x_len) ||
3791          (t2->x_pos == t1->x_pos + t1->x_len))) return(TRUE);
3792     else if ((axis == Y) &&
3793              ((t1->y_pos == t2->y_pos + t2->y_len) ||
3794               (t2->y_pos == t1->y_pos + t1->y_len)))    return(TRUE);
3795     else return(FALSE);
3796 }
3797 /*------------------------------------------------------------------------*/
3798 int free_to_include_p(t)
3799     tile *t;
3800 {
3801     /* Returns TRUE if the tile is free for routing, and completly contains the
3802        spanRange (global)... */
3803
3804     asg_arc *a = (t != NULL) ? (asg_arc *)t->this : NULL;
3805     int x1, x2;
3806
3807     x1 = t->x_pos;      x2 = x1 + t->x_len;
3808
3809     if ((a != NULL) && (a->mod == NULL))
3810     {
3811         /* Look for overlap */
3812         if ((x1 <= spanRange.q1) && (x2 >= spanRange.q2)) return(TRUE);
3813     }
3814
3815     return(FALSE);
3816 }
3817 /*------------------------------------------------------------------------------------*/
3818 tilist *valid_slivers(root, x1, y1, x2, y2, min, max)
3819     tile *root;
3820     int x1, y1, x2, y2;
3821     int *min, *max;
3822 {
3823     int started = FALSE, foundRoot = FALSE;
3824     tile *t;
3825     tilist *tl, *temp = NULL, *valid = NULL;
3826
3827     spanRange.q1 = x1;
3828     spanRange.q2 = x2;
3829
3830     temp = area_enumerate(root, &temp, free_to_include_p, x1, y1, x2 - x1, y2 - y1);
3831
3832     /* Now evaluate for continuity, and set the *min, *max values: */
3833     for (tl = (tilist *)sort_list(temp, most_down); tl != NULL; tl = tl->next)
3834     {
3835         t = tl->this;
3836
3837         /* Should contain some of y, and all of x: */
3838         if ((t == root) ||
3839             ((t->x_pos <= x1) && (t->x_pos + t->x_len >= x2) &&
3840              (t->y_pos <= y2) && (t->y_pos + t->y_len >= y1)))
3841         {
3842             if (valid == NULL) push(t, &valid);
3843             /* Be sure to include <root> in the list... (Otherwise, start over...) */
3844             else if (adjacent_p(t, valid->this, Y) == TRUE) push(t, &valid);
3845             else if (foundRoot == FALSE)
3846             {
3847                 valid = (tilist *)free_list(valid);
3848                 push(t, &valid);
3849                 *min = MAX(y1, t->y_pos);
3850             }
3851             else break;
3852
3853             if (t == root) foundRoot = TRUE;
3854             if (started == FALSE)
3855             {
3856                 *min = MAX(y1, t->y_pos);
3857                 started = TRUE;
3858             }
3859         }
3860     }
3861
3862     *max = (valid != NULL) ? MIN(y2, valid->this->y_pos + valid->this->y_len) : FALSE;
3863
3864     free_list(temp);
3865     return(valid);
3866 }
3867 /*------------------------------------------------------------------------------------*/
3868 find_and_merge_slivers(a, n)
3869     asg_arc *a;
3870     net *n;
3871 {
3872     /* Look to see if there are other adjacent asg_arcs/tiles that can be used.
3873        If so, then modify the corner limits, and do the book keeping for the
3874        asg_arc/corner structures...*/
3875
3876     /* All such slivers located are added to the n->route list */
3877
3878     int contRangeMin, contRangeMax;
3879     int minX, minY, maxX, maxY;
3880     tilist *tl, *sliverSet;
3881     asg_arc *ar;
3882     srange *xSR, *ySR, *x1SR, *y1SR, *x2SR, *y2SR;
3883     corner *prev, *next;
3884     crnlist *cl, *cll;
3885
3886     for (cl = a->corners; cl != NULL; cl = cl->next)
3887     {
3888         /* Only look at corners belonging to this net: */
3889         if (((cl->this->cy != NULL) && (cl->this->cy->n == n)) ||
3890             ((cl->this->cx != NULL) && (cl->this->cx->n == n)))
3891         {
3892             ySR = cl->this->cy->sr;             xSR = cl->this->cx->sr;
3893
3894             if ((a->page == VERT) && (fixed_point_p(cl->this->cx) == FALSE))
3895             {
3896                 /* Find the corners of the legal routing space: (mega-tile) */
3897                 next = next_horz_corner(most_vert_corner(cl->this));
3898                 y1SR = next->cy->sr;            x1SR = next->cx->sr;
3899                 prev = next_horz_corner(least_vert_corner(cl->this));
3900                 y2SR = prev->cy->sr;            x2SR = prev->cx->sr;
3901
3902                 minX = MIN(xSR->q1, MIN(x1SR->q1, x2SR->q1));
3903                 minY = MIN(ySR->q1, MIN(y1SR->q1, y2SR->q1));
3904                 maxX = MAX(xSR->q2, MAX(x1SR->q2, x2SR->q2));
3905                 maxY = MAX(ySR->q2, MAX(y1SR->q2, y2SR->q2));
3906
3907                 /* Special case to detect vertical U's: */
3908                 if ((x1SR->q2 <= xSR->q1) && (x2SR->q2 <= xSR->q1))
3909                 {
3910                     /* left-pointing U */
3911                     maxX += WHITE_SPACE;
3912                     if (debug_level > 0) fprintf(stderr," left-pointing U for net %s\n", n->name);
3913                 }
3914
3915                 else if ((x1SR->q1 >= xSR->q2) && (x2SR->q2 >= xSR->q2))
3916                 {
3917                     /* right-pointing U */
3918                     minX -= WHITE_SPACE;
3919                     if (debug_level > 0) fprintf(stderr," right-pointing U for net %s\n", n->name);
3920                 }
3921
3922                 sliverSet = valid_slivers(a->t, minY, minX, maxY, maxX,
3923                                           &contRangeMin, &contRangeMax);
3924
3925                 if (member_p(a->t, sliverSet, identity) == FALSE)
3926                 {
3927                     /* Major Problem... */
3928                     fprintf(stderr, "(v) sliver detector screwed {(%d,%d) & (%d,%d)}\n",
3929                             minX, minY, maxX, maxY);
3930                     fprintf(stderr, "given %d tiles, couldn't find @(%d, %d) for net %s\n",
3931                             list_length(sliverSet), a->t->y_pos + (a->t->y_len/2),
3932                             a->t->x_pos + (a->t->x_len/2), n->name);
3933
3934                     return(NULL);
3935                 }
3936                 else
3937                 {
3938                     if ((cl->this->cx->sr->q1 > contRangeMin) ||
3939                         (cl->this->cx->sr->q2 < contRangeMax))
3940                     {
3941                         if ((debug_level >= 2) && (sliverSet->next != NULL))
3942                         {
3943                             fprintf(stderr, "<%s> expanding from x = [%d,%d] to [%d,%d] (%d slivers added)\n",
3944                                     cl->this->cx->n->name, cl->this->cx->sr->q1,
3945                                     cl->this->cx->sr->q2, contRangeMin, contRangeMax,
3946                                     list_length(sliverSet) - 1);
3947                         }
3948
3949                         /* Expand the range: */
3950                         cl->this->cx->sr->q1 = MIN(contRangeMin, cl->this->cx->sr->q1);
3951                         cl->this->cx->sr->q2 = MAX(contRangeMax, cl->this->cx->sr->q2);
3952
3953                         /* Add the expanded corners to all tiles that it uses. */
3954                         for(tl = sliverSet; tl != NULL; tl = tl->next)
3955                         {
3956                             ar = (asg_arc *)tl->this->this;
3957                             for(cll = cl->this->cx->corners;cll != NULL;cll = cll->next)
3958                             {
3959                                 if (corner_falls_in_arc_p(cll->this,ar) == TRUE)
3960                                 {
3961                                     add_corner_to_arc(cll->this, ar);
3962                                 }
3963                             }
3964                             pushnew(tl->this, &n->route);
3965                         }
3966                     }
3967                 }
3968             }
3969             else if ((a->page == HORZ) && (fixed_point_p(cl->this->cy) == FALSE))
3970             {
3971                 /* Find the corners of the legal routing space: (mega-tile) */
3972
3973                 next = next_vert_corner(most_horz_corner(cl->this));
3974                 y1SR = next->cy->sr;            x1SR = next->cx->sr;
3975                 prev = next_vert_corner(least_horz_corner(cl->this));
3976                 y2SR = prev->cy->sr;            x2SR = prev->cx->sr;
3977
3978                 minX = MIN(xSR->q1, MIN(x1SR->q1, x2SR->q1));
3979                 minY = MIN(ySR->q1, MIN(y1SR->q1, y2SR->q1));
3980                 maxX = MAX(xSR->q2, MAX(x1SR->q2, x2SR->q2));
3981                 maxY = MAX(ySR->q2, MAX(y1SR->q2, y2SR->q2));
3982
3983                 sliverSet = valid_slivers(a->t,  minX, minY, maxX, maxY,
3984                                           &contRangeMin, &contRangeMax);
3985
3986                 if (member_p(a->t, sliverSet, identity) == FALSE)
3987                 {
3988                     /* Major Problem... */
3989                     fprintf(stderr, "(h) sliver detector screwed {(%d,%d) & (%d,%d)}\n",
3990                             minX, minY, maxX, maxY);
3991                     fprintf(stderr, "given %d tiles, couldn't find @(%d, %d)for net %s\n",
3992                             list_length(sliverSet), a->t->x_pos + (a->t->x_len/2),
3993                             a->t->y_pos + (a->t->y_len/2), n->name);
3994
3995                     return(NULL);
3996                 }
3997                 else
3998                 {
3999                     if ((cl->this->cy->sr->q1 > contRangeMin) ||
4000                         (cl->this->cy->sr->q2 < contRangeMax))
4001                     {
4002                         if ((debug_level >= 2) && (sliverSet->next != NULL))
4003                         {
4004                             fprintf(stderr, "<%s> expanding from y = [%d,%d] to [%d,%d] (%d slivers added)\n",
4005                                     cl->this->cy->n->name, cl->this->cy->sr->q1,
4006                                     cl->this->cy->sr->q2, contRangeMin, contRangeMax,
4007                                     list_length(sliverSet) - 1);
4008                         }
4009
4010                         /* Expand the range: */
4011                         cl->this->cy->sr->q1 = MIN(contRangeMin, cl->this->cy->sr->q1);
4012                         cl->this->cy->sr->q2 = MAX(contRangeMax, cl->this->cy->sr->q2);
4013
4014                         /* Add the expanded corners to all tiles that it uses. */
4015                         for(tl = sliverSet; tl != NULL; tl = tl->next)
4016                         {
4017                             ar = (asg_arc *)tl->this->this;
4018                             for(cll = cl->this->cy->corners;cll != NULL;cll = cll->next)
4019                             {
4020                                 if (corner_falls_in_arc_p(cll->this,ar) == TRUE)
4021                                 {
4022                                     add_corner_to_arc(cll->this, ar);
4023                                 }
4024                             }
4025                             pushnew(tl->this, &n->route);
4026                         }
4027                     }
4028                 }
4029             }
4030         }
4031     }
4032 }
4033 /*------------------------------------------------------------------------------------*/
4034 expand_slivers(tilesUsed, n)
4035     tilist *tilesUsed;
4036     net *n;
4037 {
4038     tilist *tl;
4039     asg_arc *a;
4040
4041     for (tl = tilesUsed; tl != NULL; tl = tl->next)
4042     {
4043         a = (asg_arc *)tl->this->this;
4044
4045         /* Merge/expand slivered tiles for this net: */
4046         find_and_merge_slivers(a, n);
4047     }
4048 }
4049 /*------------------------------------------------------------------------------------*/
4050 o_complete_linkages(n, setJogsP)
4051     net *n;
4052     int setJogsP;
4053 {
4054     old_complete_linkages(n->route, n, setJogsP);
4055 }
4056 /*------------------------------------------------------------------------------------*/
4057 old_complete_linkages(usedTiles, n, setJogsP)
4058     tilist *usedTiles;
4059     net *n;
4060     int setJogsP;
4061 {
4062     /* This walks through the list of tiles, and completes the links among the
4063        corner structures for the given net. */
4064     /* This is very vicious - it introduces links at EVERY point where they can be
4065        made (common use of a tile by two pieces of the global route for the same
4066        net */
4067
4068     tilist *tl;
4069     asg_arc *a;
4070     corner *linkCorner;
4071     crnlist *cl, *cll;
4072     range *link;
4073
4074     for (tl = usedTiles; tl != NULL; tl = tl->next)
4075     {
4076         a = (asg_arc *)tl->this->this;
4077
4078         linkCorner = choose_best_link(n, a, setJogsP);
4079         if (linkCorner == NULL) break;
4080
4081         link = (a->page == VERT) ? linkCorner->cx : linkCorner->cy;
4082
4083         for (cl = a->corners; cl != NULL; cl = cl->next)
4084         {
4085             /* Only look at corners belonging to this net: */
4086             if (((cl->this->cy != NULL) && (cl->this->cy->n == n)) ||
4087                 ((cl->this->cx != NULL) && (cl->this->cx->n == n)))
4088             {
4089                 /* Set everybody's ylink to the same range */
4090                 if (a->page == VERT)
4091                 {
4092                     if (cl->this->cx != link)  /* Skip the link; it should be OK */
4093                     {
4094                         if (overlapped_p(cl->this->cx->sr, link->sr) == TRUE)
4095                         {
4096                             reduce_to_least_common_range(link->sr, cl->this->cx->sr);
4097                             replace_range_instance(cl->this, linkCorner, X);
4098                         }
4099                         else
4100                         {
4101                             a = a;
4102                         }
4103                     }
4104                 }
4105                 else    /* Horizontal Tile */
4106                 {
4107                     if (cl->this->cy != link)   /* Skip the link; it should be OK */
4108                     {
4109                         if (overlapped_p(cl->this->cy->sr, link->sr) == TRUE)
4110                         {
4111                             reduce_to_least_common_range(link->sr, cl->this->cy->sr);
4112                             replace_range_instance(cl->this, linkCorner, Y);
4113                         }
4114                         else
4115                         {
4116                             a = a;
4117                         }
4118                     }
4119                 }
4120             }
4121         }
4122     }
4123 }
4124 /*------------------------------------------------------------------------------------*/
4125 complete_linkages(n, setJogsP)
4126     net *n;
4127     int setJogsP;
4128 {
4129     /* This walks through the list of tiles, and completes the links among the
4130        corner structures for the given net. */
4131     /* This function is intended to do this linking only in the designated
4132        linkage tiles (where the global routes for two expansions meet).
4133        Albiet this is a rare case, probably some consideration needs to be made
4134        for global routes that overlap each other for more than one tile.  */
4135
4136     tilist *tl, *connectionTiles = NULL;
4137     expn *ex;
4138     trlist *trl;
4139     tile *first, *last;
4140
4141     ex = (expn *) n->done->this;
4142     for (trl = ex->connections; trl != NULL; trl = trl->next)
4143     {
4144         /* Find the <first> and <last> tiles for the set of expansions that
4145            makes up the global route for this net. */
4146
4147         last = trl->this->tr->this;
4148         for (tl = trl->this->tr; tl != NULL; tl = tl->next)
4149         {
4150             if (tl->next == NULL) first = tl->this;
4151         }
4152         pushnew(last, &connectionTiles);
4153         pushnew(first, &connectionTiles);
4154     }
4155
4156     old_complete_linkages(connectionTiles, n, setJogsP);
4157     free_list(connectionTiles);
4158 }
4159 /*------------------------------------------------------------------------------------*/
4160 center_range_on_single_point(sr)
4161     srange *sr;
4162 {
4163     /*This reduces the range of <sr> to a single point */
4164     int mid = (sr->q1 + sr->q2)/2;
4165     sr->q1 = mid;
4166     sr->q2 = mid;
4167 }
4168 /*------------------------------------------------------------------------------------*/
4169 void center_ranges_on_points(TilesToFix)
4170     tilist *TilesToFix;
4171 {
4172     /* this takes all ranges contained in all tiles on the route, and centers them. */
4173     /* This will screw-up royally if the overlap resolution is incomplete. */
4174
4175     tilist *tl;
4176     asg_arc *a;
4177     crnlist *cl;
4178
4179     for (tl = TilesToFix; tl != NULL; tl = tl->next)
4180     {   /* these should only consist of one range: */
4181         a = (asg_arc *)tl->this->this;
4182         for (cl = a->corners; cl != NULL; cl = cl->next)
4183         {
4184             center_range_on_single_point(cl->this->cy->sr);
4185             center_range_on_single_point(cl->this->cx->sr);
4186         }
4187     }
4188 }
4189 /*------------------------------------------------------------------------------------*/
4190 int reduce_to_least_common_range(target, other)
4191     srange *target, *other;
4192 {
4193     /* Reduce the <target> range to the least common overlapped range between
4194        <target> and <other> */
4195     int min, max;
4196
4197     find_intersection(target->q1, target->q2,
4198                       other->q1, other->q2,
4199                       &min, &max);
4200     target->q1 = min;
4201     target->q2 = max;
4202 }
4203
4204 /*------------------------------------------------------------------------------------*/
4205 /*------------------------------------------------------------------------------------*/
4206 int net_name_located_p(net_name, n)
4207     char *net_name;
4208     net *n;
4209 {
4210     if (!strcmp(net_name, n->name)) return(TRUE);
4211     return(FALSE);
4212 }
4213 /*------------------------------------------------------------------------------------*/
4214 void ps_dump_arc(f, t)
4215     FILE *f;
4216     tile *t;
4217 {
4218     /* This function prints the contents of the given tile in PostScript format t       file <f>. */
4219     asg_arc *a = (asg_arc *)t->this;
4220     float x1, y1, x2, y2;
4221
4222     if (a->mod == NULL)
4223     {
4224         if (a->page == HORZ)
4225         {
4226             x1 = (float)a->t->x_pos + GRAY_MARGIN;
4227             x2 = (float)a->t->x_pos + (float)a->t->x_len - GRAY_MARGIN;
4228             y1 = (float)a->t->y_pos + GRAY_MARGIN;
4229             y2 = (float)a->t->y_pos + (float)a->t->y_len - GRAY_MARGIN;
4230         }
4231         else
4232         {
4233             x1 = (float)a->t->y_pos + GRAY_MARGIN;
4234             x2 = (float)a->t->y_pos + (float)a->t->y_len - GRAY_MARGIN;
4235             y1 = (float)a->t->x_pos + GRAY_MARGIN;
4236             y2 = (float)a->t->x_pos + (float)a->t->x_len - GRAY_MARGIN;
4237         }
4238
4239         /* print the asg_arcs that contain the <net_under_study> */
4240
4241         if (debug_level == 1)
4242         {
4243             if (member_p(net_under_study, a->nets, net_name_located_p) == TRUE)
4244             {
4245                 /* Fill in the area with gray, shaded to show global route */
4246                 fprintf(f, "newpath %f %f moveto %f %f lineto ", x1, y1, x2, y1);
4247                 fprintf(f, "%f %f lineto %f %f lineto ", x2, y2, x1, y2);
4248                 fprintf(f, "closepath %.3f setgray fill 0 setgray\n", 0.7);
4249
4250                 /* ps_put_label(f, net_under_study, x1 + 0.9, y2 - 0.9); */
4251             }
4252         }
4253     }
4254
4255     else        /* Print out the module icon */
4256     {
4257         //ps_print_mod(f, a->mod);
4258     }
4259 }
4260 /*------------------------------------------------------------------------------------*/
4261 void ps_invert_arc(f, t)
4262     FILE *f;
4263     tile *t;
4264 {
4265     /* This function prints the contents of the given tile in PostScript format to
4266        file <f>. */
4267     asg_arc *a = (asg_arc *)t->this;
4268     float x1, y1, x2, y2;
4269
4270     if (a->mod == NULL)
4271     {
4272         /* print the arcs that contain the <net_under_study> */
4273
4274         if (member_p(net_under_study, a->nets, net_name_located_p) == TRUE)
4275         {
4276             if (a->page == HORZ)
4277             {
4278                 x1 = (float)a->t->x_pos + GRAY_MARGIN;
4279                 x2 = (float)a->t->x_pos + (float)a->t->x_len - GRAY_MARGIN;
4280                 y1 = (float)a->t->y_pos + GRAY_MARGIN;
4281                 y2 = (float)a->t->y_pos + (float)a->t->y_len - GRAY_MARGIN;
4282             }
4283             else
4284             {
4285                 x1 = (float)a->t->y_pos + GRAY_MARGIN;
4286                 x2 = (float)a->t->y_pos + (float)a->t->y_len - GRAY_MARGIN;
4287                 y1 = (float)a->t->x_pos + GRAY_MARGIN;
4288                 y2 = (float)a->t->x_pos + (float)a->t->x_len - GRAY_MARGIN;
4289             }
4290
4291             /* Fill in the area with gray, shaded to show global route */
4292             fprintf(f, "newpath %f %f moveto %f %f lineto ", x1, y1, x2, y1);
4293             fprintf(f, "%f %f lineto %f %f lineto ", x2, y2, x1, y2);
4294             fprintf(f, "closepath %.3f setgray fill 0 setgray\n", 0.9);
4295
4296             ps_put_label(f, net_under_study, x1 + 0.9, y2 - 0.9);
4297         }
4298     }
4299
4300     else        /* Don't print the module icon */
4301     {
4302 /*      ps_print_mod(f, a->mod);        */
4303     }
4304 }
4305 /*------------------------------------------------------------------------------------*/
4306 int solidp_for_printing(t)
4307     tile *t;
4308 {
4309     return(TRUE);
4310 }
4311 /*-------------------------------------------------------------------------------------*/
4312 replace_range(oldR, newR, axis)
4313     range *oldR, *newR;
4314     int axis;
4315 {
4316     asg_arc *a;
4317     arclist *al;
4318     crnlist *cll;
4319
4320     for (cll = oldR->corners; cll != NULL; cll = cll->next)
4321     {
4322         if (axis == X) cll->this->cx = newR;
4323         else cll->this->cy = newR;
4324
4325         push(cll->this, &newR->corners);
4326     }
4327     free_list(oldR->corners);
4328     my_free(oldR);
4329 }
4330 /*-------------------------------------------------------------------------------------*/
4331 restrict_corner_usage(c, axis)
4332     corner *c;
4333     int axis;
4334 {
4335     /* This function checks the corner <c> and all linked corners along the given
4336        axis for problems arising from incorrect tile inclusions (a->corners lists) */
4337     asg_arc *a;
4338     arclist *al;
4339     crnlist *cll;
4340     range *oldR = (axis == X) ? c->cx : c->cy;
4341
4342     for (cll = oldR->corners; cll != NULL; cll = cll->next)
4343     {
4344         for (al = cll->this->al; al != NULL; al = al->next)
4345         {
4346             if (corner_falls_in_arc_p(cll->this, al->this) == FALSE)
4347             {
4348                 a = al->this;
4349                 rem_item(cll->this, &a->corners);
4350                 rem_item(a, &cll->this->al);
4351
4352                 if (a->corners == NULL)
4353                 {
4354                     /* Got other problems, like cleaning up the usedTiles lists */
4355                 }
4356             }
4357         }
4358     }
4359 }
4360 /*-------------------------------------------------------------------------------------*/
4361 replace_range_instance(c, newC, axis)
4362     corner *c, *newC;
4363     int axis;
4364 {
4365     asg_arc *a;
4366     arclist *al, *atemp;
4367     crnlist *cll;
4368     range *oldR = (axis == X) ? c->cx : c->cy;
4369     range *newR = (axis == X) ? newC->cx : newC->cy;
4370
4371     for (cll = oldR->corners; cll != NULL; cll = cll->next)
4372     {
4373         if (axis == X) cll->this->cx = newR;
4374         else cll->this->cy = newR;
4375
4376         al = cll->this->al;
4377         while (al != NULL)
4378         {
4379             atemp = al->next;
4380             if (corner_falls_in_arc_p(cll->this, al->this) == FALSE)
4381             {
4382                 a = al->this;
4383                 rem_item(cll->this, &a->corners);
4384                 rem_item(a, &cll->this->al);
4385
4386                 if (a->corners == NULL)
4387                 {
4388                     /* Got other problems, like cleaning up the usedTiles lists */
4389                 }
4390             }
4391             al = atemp;
4392         }
4393
4394         push(cll->this, &newR->corners);
4395     }
4396     my_free(oldR->sr);
4397     free_list(oldR->corners);
4398     my_free(oldR);
4399 }
4400 /*-------------------------------------------------------------------------------------*/
4401 replace_corner_instance(c, newC)
4402     corner *c, *newC;
4403 {
4404     /* This function traces the usage of <c> and replaces all such occurances
4405        with <newC>.  If <newC> is already referenced, then <c> is simply deleted. */
4406     /* Hunt down the little bugger in the two tile spaces, and kill it: */
4407     /* Hunt down the little bugger in it's range connections, and kill it: */
4408
4409     tile *newTile;
4410     asg_arc *a;
4411     arclist *al;
4412     range *r;
4413     corner *e1 = NULL, *e2 = NULL, *e3 = NULL;
4414
4415     r = c->cx;
4416     e1 = (corner *)rem_item(c, &r->corners);
4417     pushnew(newC, &r->corners);
4418
4419     r = c->cy;
4420     e2 = (corner *)rem_item(c, &r->corners);
4421     pushnew(newC, &r->corners);
4422
4423     /* Now yank <c> from the all arc(s) where it is referenced:  */
4424     for (al = c->al; al != NULL; al = al->next)
4425     {
4426         a = al->this;
4427         e3 = (corner *)rem_item(c, &a->corners);
4428         if ((e3 == NULL) && (corner_falls_in_arc_p(c, a) == TRUE))
4429         {
4430             fprintf(stderr, "Screwedup corner deletion attempt...");
4431             /* exit(1); */
4432             return;
4433         }
4434         add_corner_to_arc(newC, a);
4435     }
4436     my_free(c);
4437 }
4438 /*-------------------------------------------------------------------------------------*/
4439 /*-------------------------------------------------------------------------------------*/
4440 remove_corner_from_used_lists(c, a)
4441     corner *c;
4442     asg_arc *a;
4443 {
4444     int i;
4445     trail *t;
4446     trailist *trl;
4447
4448     for (i=0; i<HASH_SIZE; i++)
4449     {
4450         for (trl = a->trails[i]; trl != NULL; trl = trl->next)
4451         {
4452             t = trl->this;
4453             if (t->used != NULL) rem_item(c, &t->used);
4454         }
4455     }
4456 }
4457 /*-------------------------------------------------------------------------------------*/
4458 delete_corner(c, deadRanges)
4459     corner *c;
4460     rnglist **deadRanges;
4461 {
4462     asg_arc *a;
4463     arclist *al;
4464     range *r;
4465
4466     r = c->cx;
4467     rem_item(c, &r->corners);
4468     pushnew(r, deadRanges);
4469
4470     r = c->cy;
4471     rem_item(c, &r->corners);
4472     pushnew(r, deadRanges);
4473
4474     for (al = c->al; al !=NULL; al = al->next)
4475     {
4476         a = al->this;
4477         rem_item(c, &a->corners);
4478         remove_corner_from_used_lists(c, a);
4479     }
4480     free_list(c->al);
4481     my_free(c);
4482 }
4483 /*-------------------------------------------------------------------------------------*/
4484 int border_condition(sr1, sr2)
4485     srange *sr1, *sr2;
4486 {
4487     if ((sr1->q1 == sr2->q2) || (sr1->q2 == sr2->q1)) return(TRUE);
4488     else return(FALSE);
4489 }
4490 /*-------------------------------------------------------------------------------------*/
4491 int fixed_point_p(r1)
4492     range *r1;
4493 {
4494     if (r1->sr->q1 != r1->sr->q2) return(FALSE);
4495     return(TRUE);
4496 }
4497 /*-------------------------------------------------------------------------------------*/
4498 int repeated_srange_p(r1, r2)
4499     range *r1, *r2;
4500 {
4501     /* This retuurns TRUE iff <r2> has the same underlying ranges as <r1>: */
4502     if ((r1->sr->q1 == r2->sr->q1) && (r1->sr->q2 == r2->sr->q2)) return (TRUE);
4503     else return(FALSE);
4504 }
4505 /*-------------------------------------------------------------------------------------*/
4506 int repeated_corner_p(c1, c2)
4507     corner *c1, *c2;
4508 {
4509     /* This returns TRUE iff <c2> has the same underlying ranges as <c1>: */
4510     if ((c1->cx->sr == c2->cx->sr) && (c1->cy->sr == c2->cy->sr)) return (TRUE);
4511     else return(FALSE);
4512 }
4513 /* ------------------------------------------------------------------------------------*/
4514 crnlist *delete_duplicate_corners(cl)
4515     crnlist **cl;
4516 {
4517     corner *targ;
4518     crnlist *p, *pp, *trash, *last;
4519
4520     if (*cl == NULL)
4521     {
4522         /* error: "delete_duplicate_corners passed null list" */
4523         return(NULL);
4524     }
4525
4526     for (p = *cl; ((p != NULL) && (p->next != NULL)); p = p->next)
4527     {
4528         targ = p->this;
4529         last = p;
4530         for (pp = p->next; pp != NULL;)
4531         {
4532             if (targ->cx->sr != pp->this->cx->sr)
4533             {
4534                 if ((repeated_srange_p(targ->cx, pp->this->cx) == TRUE)  &&
4535                     (repeated_srange_p(targ->cy, pp->this->cy) == TRUE))
4536                 {
4537                     /* Replace pp->this->cx with targ->cx */
4538                     replace_range_instance(pp->this, targ, X);
4539                 }
4540                 else if ((overlapped_p(targ->cx->sr, pp->this->cx->sr) == TRUE) &&
4541 /*                       ((fixed_point_p(targ->cx) == FALSE) &&
4542                           (fixed_point_p(pp->this->cx) == FALSE))  &&           */
4543                          (border_condition(targ->cx->sr, pp->this->cx->sr) == FALSE))
4544                 {
4545                     /* collapse these into one srange... */
4546                     merge_sranges(&targ->cx->sr, &pp->this->cx->sr);
4547                     /* Now check to see that the corners are in(ex)cluded in(from)
4548                        the right arcs... */
4549                     restrict_corner_usage(pp->this, X);
4550                     restrict_corner_usage(targ, X);
4551                 }
4552
4553                 /* Very specific, strange condition that occurs (BUG fix) */
4554                 else if((repeated_srange_p(targ->cy, pp->this->cy) == TRUE) &&
4555                         (list_length(pp->this->cx->corners) <= 1) &&
4556                         (pp->this->t == NULL) &&
4557                         (fixed_point_p(pp->this->cx) == FALSE))
4558                 {
4559                     /* delete the range pp->this->cx, and replace it with targ->cx */
4560                     merge_sranges(&targ->cx->sr, &pp->this->cx->sr);
4561                     replace_range(pp->this->cx, targ->cx, X);
4562                 }
4563
4564                 /* Very specific, strange condition that occurs (BUG fix continued) */
4565                 else if((repeated_srange_p(targ->cy, pp->this->cy) == TRUE) &&
4566                         (list_length(targ->cx->corners) <= 1) &&
4567                         (targ->t == NULL) &&
4568                         (fixed_point_p(targ->cx) == FALSE))
4569                 {
4570                     /* delete the range targ->cx, and replace it with pp->this->cx */
4571                     merge_sranges(&targ->cx->sr, &pp->this->cx->sr);
4572                     replace_range(targ->cx, pp->this->cx, X);
4573                 }
4574             }
4575             else if ((targ->cx != pp->this->cx) &&
4576                      (targ->cx->sr == pp->this->cx->sr))
4577             {
4578                 replace_range(pp->this->cx, targ->cx, X);
4579             }
4580
4581             if (targ->cy->sr != pp->this->cy->sr)
4582             {
4583                 if ((repeated_srange_p(targ->cy, pp->this->cy) == TRUE) &&
4584                     (repeated_srange_p(targ->cx, pp->this->cx) == TRUE))
4585                 {
4586                     /* Replace pp->this->cy with targ->cy */
4587                     replace_range_instance(pp->this, targ, Y);
4588                 }
4589                 else if ((overlapped_p(targ->cy->sr, pp->this->cy->sr) == TRUE) &&
4590                          ((fixed_point_p(targ->cy) == FALSE) &&
4591                           (fixed_point_p(pp->this->cy) == FALSE)) )/* &&
4592                          (border_condition(targ->cx->sr, pp->this->cx->sr) == FALSE)) */
4593                 {
4594                     /* collapse these into one srange... */
4595                     merge_sranges(&targ->cy->sr, &pp->this->cy->sr);
4596                     /* Now check to see that the corners are in(ex)cluded in(from)
4597                        the right arcs... BUT- Don't blow away ranges, because
4598                        this causes BIG problems... */
4599 /*                  restrict_corner_usage(pp->this, Y);
4600                     restrict_corner_usage(targ, Y);             */
4601                 }
4602
4603                 /* Very specific, strange condition that occurs (BUG fix) */
4604                 else if ((repeated_srange_p(targ->cx, pp->this->cx) == TRUE) &&
4605                           ((list_length(pp->this->cy->corners) <= 1) &&
4606                            (pp->this->t == NULL) &&
4607                            (fixed_point_p(pp->this->cy) == FALSE)))
4608                 {
4609                     /* delete the range pp->this->cy, and replace it with targ->cy */
4610                     merge_sranges(&targ->cy->sr, &pp->this->cy->sr);
4611                     replace_range(pp->this->cy, targ->cy, Y);
4612                 }
4613                 /* Bug Fix continued */
4614                 else if ((repeated_srange_p(targ->cx, pp->this->cx) == TRUE) &&
4615                           ((list_length(targ->cy->corners) <= 1) &&
4616                            (targ->t == NULL) &&
4617                            (fixed_point_p(targ->cy) == FALSE)))
4618                 {
4619                     /* delete the range targ->cy, and replace it with pp->this->cy */
4620                     merge_sranges(&targ->cy->sr, &pp->this->cy->sr);
4621                     replace_range(targ->cy, pp->this->cy, Y);
4622                 }
4623             }
4624             else if ((targ->cy != pp->this->cy) &&
4625                      (targ->cy->sr == pp->this->cy->sr))
4626             {
4627                 replace_range(pp->this->cy, targ->cy, Y);
4628             }
4629
4630             if (repeated_corner_p(targ, pp->this) == TRUE)
4631             {
4632                 replace_corner_instance(pp->this, targ);
4633                 last->next = pp->next;
4634                 trash = pp;
4635                 pp = pp->next;
4636                 my_free(trash);
4637             }
4638             else
4639             {
4640                 last = pp;
4641                 pp = pp->next;
4642             }
4643         }
4644     }
4645     return(*cl);
4646 }
4647 /*------------------------------------------------------------------------------------*/
4648 void delete_all_corners(deadCorners)
4649     crnlist *deadCorners;
4650 {
4651     rnglist *rangesToKill = NULL, *rl;
4652     crnlist *cl;
4653     for(cl = deadCorners; cl != NULL; cl = cl->next)
4654     {
4655         delete_corner(cl->this, &rangesToKill);
4656     }
4657
4658     for(rl = rangesToKill; rl != NULL; rl = rl->next)
4659     {
4660         my_free(rl->this->sr);
4661         my_free(rl->this);
4662     }
4663     free_list(rangesToKill);
4664 }
4665 /*------------------------------------------------------------------------------------*/
4666 void merge_global_subroutes(n)
4667     net *n;
4668 {
4669     /* This looks at the corners that have been saved in the global sub-routes
4670        that exist in the net (ex->connections);  These corner lists are merged,
4671        and all duplicates are removed.   The results are stored in n->route.  */
4672
4673     expn *ex = (expn *)n->done->this;
4674     trlist *trl;
4675
4676     n->route = free_list(n->route);
4677
4678     for (trl = ex->connections; trl != NULL; trl = trl->next)
4679     {
4680         /* Collect all of the corners used by this net: */
4681         n->route = append_list(n->route, trl->this->used);
4682         trl->this->used = NULL;
4683     }
4684     delete_duplicate_corners(&n->route);
4685 }
4686
4687 /*------------------------------------------------------------------------------------*/
4688 void reset_arc_costs(tilesToReset)
4689     tilist *tilesToReset;
4690 {
4691     /* This walks through the given set of tiles, and resets the congestion costs. */
4692
4693     crnlist *cl;
4694     tilist *tl;
4695     asg_arc *a;
4696
4697     for (tl = tilesToReset; tl != NULL; tl = tl->next)
4698     {
4699         /* Paint each arc with the usage - assume VERT tiles essentially have
4700            only the vertical tracks employed, and HORZ tiles the horizontal
4701            tracks. */
4702         a =(asg_arc *)tl->this->this;
4703
4704         for (cl = a->corners; cl != NULL; cl = cl->next)
4705         {
4706             pushnew(cl->this->cx->n, &a->nets);         /* Mark the route used */
4707         }
4708         (*set_congestion_value)(a);
4709     }
4710 }
4711 /*------------------------------------------------------------------------------------*/
4712 /*------------------------------------------------------------------------------------*/
4713 dump_ranges(rangesToSee)
4714     rnglist *rangesToSee;
4715 {
4716     rnglist *rl;
4717     /* Dump Corner List to the screen: */
4718     if (rangesToSee == NULL) fprintf (stderr, "NONE...");
4719     for (rl = rangesToSee; rl != NULL; rl = rl->next)
4720     {
4721         fprintf(stderr, "<%s> [%d,%d]...",
4722                 rl->this->n->name, rl->this->sr->q1, rl->this->sr->q2);
4723     }
4724     fprintf (stderr, "\n");
4725 }
4726 /*------------------------------------------------------------------------------------*/
4727 dump_corners(cornersToSee)
4728     crnlist *cornersToSee;
4729 {
4730     crnlist *cl;
4731     /* Dump Corner List to the screen: */
4732     if (cornersToSee == NULL) fprintf (stderr, "NONE...");
4733     for (cl = cornersToSee; cl != NULL; cl = cl->next)
4734     {
4735         fprintf(stderr, "([%d,%d],[%d,%d])...",
4736                 cl->this->cx->sr->q1, cl->this->cx->sr->q2,
4737                 cl->this->cy->sr->q1, cl->this->cy->sr->q2);
4738     }
4739     fprintf (stderr, "\n");
4740 }
4741 /*------------------------------------------------------------------------------------*/
4742 dump_corner_names(cornersToSee)
4743     crnlist *cornersToSee;
4744 {
4745     crnlist *cl;
4746     /* Dump Corner List to the screen: */
4747     if (cornersToSee == NULL) fprintf (stderr, "NONE...");
4748     for (cl = cornersToSee; cl != NULL; cl = cl->next)
4749     {
4750         fprintf(stderr, "%s...", cl->this->cx->n->name);
4751     }
4752     fprintf (stderr, "\n");
4753 }
4754 /*------------------------------------------------------------------------------------*/
4755 void local_route(nl, page, printFlag)
4756     nlist *nl;
4757     int page, printFlag;
4758 {
4759     /* Perform the local routing tasks, now that "global_route" is complete.
4760        The global route that is used consists of the collection of the 'Best Trails'
4761        contained in each of the expansions.  (One expansion per terminal)  */
4762
4763     nlist *nll, *temp = NULL;
4764     tilist *tl, *TilesUsed = NULL;
4765     corner *corn;
4766     crnlist *cl;
4767     trlist *trl;
4768     expn *ex;
4769     int setupFlag = TRUE;
4770
4771     /* Create the corner and srange structures from the best trails for each
4772        expansion of each net: */
4773     for (nll = nl; ((nll != NULL) && (setupFlag != FALSE)); nll = nll->next)
4774     {
4775         if (list_length(nll->this->done) > 1)   /* If there's something to local route */
4776         {
4777             map_net_into_constraint_sets(nll->this);
4778             /* This creates all of the corner and srange structures, and appropriately
4779                paints the tiles used with the corners that occur within them. */
4780             /* Here also, the usage of the list pointer n->route is converted from
4781                saving all of the tiles visited, to the corners that comprise the local
4782                route for the net */
4783
4784             complete_linkages(nll->this, TRUE);
4785
4786             if (useSlivering == TRUE)
4787             {
4788                 expand_slivers(nll->this->route, nll->this);
4789                 o_complete_linkages(nll->this, FALSE);
4790             }
4791
4792             for (tl = (tilist *)nll->this->route; tl != NULL; tl = tl->next)
4793             {
4794                 pushnew(tl->this, &TilesUsed);
4795             }
4796
4797             /* At this point, the global routes, which have been calculated, need to be
4798                combined and duplicates removed.  The global router is very prone to give
4799                results where (to insure completion) tiles are repeated in two or more
4800                global sub-routes. [This sets up n->route as a corner list]  */
4801             merge_global_subroutes(nll->this);
4802         }
4803     }
4804
4805     if (debug_level == 4)
4806     {
4807         fprintf(stderr, "\nGlobal Routes are as follows:\n");
4808         for (nll = nl; nll != NULL; nll = nll->next)
4809         {
4810             /* Dump the local routes to the screen: */
4811             fprintf(stderr, "<%s>\t", nll->this->name);
4812             dump_corners(nll->this->route);
4813         }
4814         fprintf (stderr, "\n\n");
4815     }
4816
4817     /* As the nets have now been expanded to fill the available (legal) spaces
4818        (Sliver nonsense), the congestion is now inappropriate: */
4819     reset_arc_costs(TilesUsed);
4820
4821     /* Resolve sranges */
4822     /* This is a two-step procecess - firstly, the nets have their (currently) overlapped
4823        sranges resolved into non-overlapping ranges.  Secondly, these non-overlapping
4824        sranges are resolved into points so that wires can be drawn. */
4825
4826     TilesUsed = (tilist *)sort_list(TilesUsed, in_congestion_order);
4827     form_into_nonoverlapping_ranges(TilesUsed);
4828
4829     if (debug_level >= 2)
4830     {
4831         fprintf(stderr, "\nLocal Routes are as follows:\n");
4832         for (nll = nl; nll != NULL; nll = nll->next)
4833         {
4834             /* Dump the local routes to the screen: */
4835             fprintf(stderr, "<%s>\t", nll->this->name);
4836             dump_corners(nll->this->route);
4837         }
4838         fprintf (stderr, "\n\n");
4839     }
4840
4841     center_ranges_on_points(TilesUsed);
4842
4843     /* Ready for printing, mein Herr */
4844
4845     if (printFlag == TRUE)
4846     {
4847         /* finish the dump file(s) */
4848         if (debug_level == 1)
4849         {
4850             solidp = solidp_for_printing;
4851             ps_print_tile_space(routingRoot[VERT][page], df, ps_invert_arc, FALSE);
4852             ps_print_tile_space(routingRoot[HORZ][page], df, ps_dump_arc, TRUE);
4853         }
4854
4855         if (debug_level == 10) print_tile_spaces(hf, vf);
4856         else if (debug_level == 11) print_tile_spaces(hf, vf);
4857     }
4858 }
4859 /*------------------------------------------------------------------------------------*/
4860 /*-------------------------------------------------------------------------------------*/
4861 int printed_p(m)
4862     module *m;
4863 {
4864     if (m->placed == TRUE)return(TRUE);
4865     else return(FALSE);
4866 }
4867 /*-------------------------------------------------------------------------------------*/
4868 int mark_as_printed(m)
4869     module *m;
4870 {
4871     m->placed = TRUE;
4872 }
4873 /*-------------------------------------------------------------------------------------*/
4874 int manhattan_p(c1, c2)
4875     corner *c1, *c2;
4876 {
4877     /* Returns TRUE iff the two corners do not form a manhattan-oriented segment. */
4878     int x1 = c1->cx->sr->q1, x2 = c2->cx->sr->q1;
4879     int y1 = c1->cy->sr->q1, y2 = c2->cy->sr->q1;
4880
4881     if ((x1 == x2) || (y1 == y2)) return(TRUE);
4882     else return(FALSE);
4883 }
4884 /*-------------------------------------------------------------------------------------*/
4885 int not_on_Net(r)
4886     range *r;
4887 {
4888     if ((r->n == Net) && r->n != NULL) return(FALSE);
4889     return(FALSE);
4890 }
4891 /*-------------------------------------------------------------------------------------*/
4892 /*-------------------------------------------------------------------------------------*/
4893 /*-------------------------------------------------------------------------------------*/
4894 //ASG Code
4895 list *xc_extract_corner_list(cd,n)
4896     XCWindowData *cd;
4897     net *n;
4898 {
4899     /* This loops through the corners from <n>->route, and builds a
4900        list of point lists (corners) that are to be exported to XCircuit.
4901         The <cd> argument allows wire intersections to be printed as they are discovered.*/
4902
4903     crnlist *allCorners = (crnlist *)n->route;
4904     crnlist *cl, *cll, *temp;
4905     list *l, *results = NULL;
4906     int x1, y1;
4907
4908     if (debug_level == 4)
4909     {
4910         fprintf(stderr, "given corners for <%s>@ ", n->name);
4911     }
4912
4913     /* This works by copying the main segments to the (ordered) <temp>list, and then
4914        picking each corner, and adding the segments needed to fill out the lists.
4915        It is critical that points be liad in a connected (manhattan_p) order */
4916
4917     for (cl = allCorners; cl != NULL; cl = cl->next)
4918     {
4919         temp = NULL;
4920
4921         /* look along the Y Axis: */
4922         for (cll = cl->this->cx->corners; cll != NULL; cll = cll->next)
4923         {
4924             if (cll->this != cl->this) push(cll->this, &temp);
4925         }
4926
4927         /* Now add the point */
4928         push(cl->this, &temp);
4929
4930         /* look along the X axis: */
4931         for (cll = cl->this->cy->corners; cll != NULL; cll = cll->next)
4932         {
4933             if (cll->this != cl->this) push(cll->this, &temp);
4934         }
4935
4936         /* If this corner is a T, then print out the dot to <cd>: */
4937         if (forms_T_p(cl->this) != FALSE)
4938         {
4939             x1 = cl->this->cx->sr->q1;
4940             y1 = cl->this->cy->sr->q1;
4941             // ps_print_contact(f, (float)x1, (float)y1); // Dump the "DOT" to XC at the location
4942
4943             if (debug_level == 4) fprintf(stderr, "*");
4944         }
4945
4946         if (debug_level == 4)
4947         fprintf(stderr, "(%d,%d)...", cl->this->cx->sr->q1, cl->this->cy->sr->q1);
4948
4949         if (temp != NULL) push(temp, &results);
4950     }
4951
4952     if (debug_level == 4)
4953     {
4954         fprintf(stderr, "\n printing corners for <%s> @ ",n->name);
4955         for (l =results; l != NULL; l = l->next)
4956         {
4957             fprintf(stderr, " [");
4958             for (cl = (crnlist *)l->this; cl != NULL; cl = cl->next)
4959             {
4960                 fprintf(stderr, "(%d,%d)...", cl->this->cx->sr->q1, cl->this->cy->sr->q1);
4961             }
4962             fprintf(stderr, "] ");
4963         }
4964         fprintf (stderr, "\n");
4965     }
4966     return(results);
4967 }
4968 /*-------------------------------------------------------------------------------------*/
4969 list *extract_corner_list(f, n)
4970     FILE *f;
4971     net *n;
4972 {
4973     /* This loops through the corners from <n>->route, and builds a
4974        list of point lists (corners) that are to be printed. The <f> argument allows
4975         wire intersections to be printed as they are discovered. */
4976
4977     crnlist *allCorners = (crnlist *)n->route;
4978     crnlist *cl, *cll, *temp;
4979     list *l, *results = NULL;
4980     int x1, y1;
4981
4982     if (debug_level == 4)
4983     {
4984         fprintf(stderr, "given corners for <%s>@ ", n->name);
4985     }
4986
4987     /* This works by copying the main segments to the (ordered) <temp>list, and then
4988        picking each corner, and adding the segments needed to fill out the lists.
4989        It is critical that points be liad in a connected (manhattan_p) order */
4990
4991     for (cl = allCorners; cl != NULL; cl = cl->next)
4992     {
4993         temp = NULL;
4994
4995         /* look along the Y Axis: */
4996         for (cll = cl->this->cx->corners; cll != NULL; cll = cll->next)
4997         {
4998             if (cll->this != cl->this) push(cll->this, &temp);
4999         }
5000
5001         /* Now add the point */
5002         push(cl->this, &temp);
5003
5004         /* look along the X axis: */
5005         for (cll = cl->this->cy->corners; cll != NULL; cll = cll->next)
5006         {
5007             if (cll->this != cl->this) push(cll->this, &temp);
5008         }
5009
5010         /* If this corner is a T, then print out the dot to <f>: */
5011         if (forms_T_p(cl->this) != FALSE)
5012         {
5013             x1 = cl->this->cx->sr->q1;
5014             y1 = cl->this->cy->sr->q1;
5015             ps_print_contact(f, (float)x1, (float)y1);
5016
5017             if (debug_level == 4) fprintf(stderr, "*");
5018         }
5019
5020         if (debug_level == 4)
5021         fprintf(stderr, "(%d,%d)...", cl->this->cx->sr->q1, cl->this->cy->sr->q1);
5022
5023         if (temp != NULL) push(temp, &results);
5024     }
5025
5026     if (debug_level == 4)
5027     {
5028         fprintf(stderr, "\n printing corners for <%s> @ ",n->name);
5029         for (l =results; l != NULL; l = l->next)
5030         {
5031             fprintf(stderr, " [");
5032             for (cl = (crnlist *)l->this; cl != NULL; cl = cl->next)
5033             {
5034                 fprintf(stderr, "(%d,%d)...", cl->this->cx->sr->q1, cl->this->cy->sr->q1);
5035             }
5036             fprintf(stderr, "] ");
5037         }
5038         fprintf (stderr, "\n");
5039     }
5040     return(results);
5041 }
5042 /*-------------------------------------------------------------------------------------*/
5043 void write_local_route_to_file(f, nets)
5044     FILE *f;
5045     nlist *nets;
5046 {
5047     net *n;
5048     nlist *nl;
5049     expn *ex;
5050     trlist *trl;
5051     crnlist *cl;
5052     list *l, *ll;
5053     int x1, y1, x2, y2;
5054
5055
5056     for (nl = nets; nl != NULL; nl = nl->next)
5057     {
5058         n = nl->this;
5059         if (n->expns != NULL)
5060         {
5061             ex = (expn *)n->expns->this;
5062
5063             fprintf(f, "\n%%%% postscript code for modules associated with net <%s> %%%%\n", n->name);
5064
5065             /* Print as much of each net as possible: */
5066             for (trl = ex->connections; trl != NULL; trl = trl->next)
5067             {
5068                 /* If it has been routed, print it: */
5069                 if (printed_p(trl->this->ex->t->mod) == FALSE)
5070                 {
5071                     ps_print_mod(f, trl->this->ex->t->mod);
5072                     mark_as_printed(trl->this->ex->t->mod);
5073                 }
5074             }
5075
5076            fprintf(f, "\n%%%% postscript code for net <%s> %%%%\n", n->name);
5077
5078            /* Arrange the corners for this expansion in printing order: */
5079            l = extract_corner_list(f, n);       /* Locates and prints contacts */
5080
5081            for (ll = l; ll != NULL; ll = ll->next)
5082             {
5083                 fprintf(f,"newpath ");
5084                 for (cl = (crnlist *)ll->this; cl != NULL; cl = cl->next)
5085                 {
5086                     if ((cl->next != NULL) &&
5087                         (manhattan_p(cl->this, cl->next->this) == TRUE))
5088                     {
5089                         x1 = cl->this->cx->sr->q1;
5090                         y1 = cl->this->cy->sr->q1;
5091                         x2 = cl->next->this->cx->sr->q1;
5092                         y2 = cl->next->this->cy->sr->q1;
5093                         fprintf(f, "%d %d moveto %d %d lineto \n", x1, y1, x2, y2);
5094                     }
5095                 }
5096                 fprintf(f, "closepath stroke [] 0 setdash\n");
5097                 ll->this = (int *)free_list(ll->this);
5098             }
5099             free_list(l);
5100         }
5101     }
5102 }
5103
5104 /*-------------------------------------------------------------------------------------*/
5105 void xc_write_local_route(areastruct, nets)
5106     XCWindowData *areastruct;
5107     nlist *nets;
5108 {
5109     net *n;
5110     nlist *nl;
5111     expn *ex;
5112     trlist *trl;
5113     crnlist *cl;
5114     list *l, *ll;
5115     float scale;
5116
5117     for (nl = nets; nl != NULL; nl = nl->next)
5118     {
5119         n = nl->this;
5120         if (n->expns != NULL)
5121         {
5122             ex = (expn *)n->expns->this;
5123
5124             /* Print as much of each net as possible: */
5125             for (trl = ex->connections; trl != NULL; trl = trl->next)
5126             {
5127                 /* If it has been routed, print it: */
5128                 if (printed_p(trl->this->ex->t->mod) == FALSE)
5129                 {
5130                     scale = (float)(trl->this->ex->t->mod->x_size)
5131                                 / (float)(ICON_SIZE * ICON_SIZE / 2);
5132                     xc_print_asg_module(areastruct, trl->this->ex->t->mod);
5133                     mark_as_printed(trl->this->ex->t->mod);
5134                 }
5135             }
5136             /* Arrange the corners for this expansion in printing order: */
5137             l = xc_extract_corner_list(areastruct, n);  /* Locates and prints contacts */
5138
5139             for (ll = l; ll != NULL; ll = ll->next)
5140             {
5141                 int *x, *y;
5142                 int num_points = 0;
5143
5144                 for (cl = (crnlist *)ll->this; cl != NULL; cl = cl->next)
5145                    num_points++;
5146                 x = (int *)malloc(num_points * sizeof(int));
5147                 y = (int *)malloc(num_points * sizeof(int));
5148
5149                 num_points = 0;
5150                 for (cl = (crnlist *)ll->this; cl != NULL; cl = cl->next)
5151                 {
5152                     /* x[num_points] = 15 * cl->this->cx->sr->q1 + X_SHIFT; */
5153                     /* y[num_points] = 15 * cl->this->cy->sr->q1 + Y_SHIFT; */
5154                     x[num_points] = cl->this->cx->sr->q1;
5155                     y[num_points] = cl->this->cy->sr->q1;
5156                     num_points++;
5157                 }
5158
5159                 asg_make_polygon(areastruct, num_points, x, y);
5160                 free(x);
5161                 free(y);
5162
5163                 ll->this = (int *)free_list(ll->this);
5164             }
5165             free_list(l);
5166
5167             calcbbox(areastruct->topinstance);
5168             centerview(areastruct->topinstance);
5169         }
5170     }
5171 }
5172
5173 /*-------------------------------------------------------------------------------------*/
5174
5175 void xc_print_local_route(areastruct, nets)
5176     XCWindowData *areastruct;
5177     nlist *nets;
5178 {
5179     FILE *hfile, *fopen ();
5180     nlist *netToPrint, *nl;     /* For debug == 1 stuff... */
5181     int c;
5182
5183     /* Insert code to put useful comments on XC diagram */
5184
5185     /* Write the local route now: */
5186     xc_write_local_route(areastruct, nets);
5187
5188     if (debug_level == 1)
5189     {
5190         /* Write the local route now: */
5191         for (nl = nets; ((nl != NULL) && (strcmp(nl->this->name, net_under_study)));
5192              nl = nl->next);
5193         if (nl != NULL)
5194         {
5195             push(nl->this, &netToPrint);
5196             xc_write_local_route(areastruct, netToPrint);
5197         }
5198     }
5199 }
5200
5201 /*-------------------------------------------------------------------------------------*/
5202 void print_local_route(f, nets)
5203     FILE *f;
5204     nlist *nets;
5205 {
5206     FILE *hfile, *fopen ();
5207     nlist *netToPrint, *nl;     /* For debug == 1 stuff... */
5208     int c;
5209
5210     /* for date and time */
5211     long time_loc;
5212     extern long int time();
5213
5214     /* now dump the result */
5215     time_loc = time(0L);
5216
5217     if (latex != TRUE) /* Not in latex mode */
5218     {
5219         ps_print_standard_header(f);
5220         fprintf(f,"(N2A %s %s ?? %s)\n",
5221                 getenv("USER"), ctime(&time_loc),
5222                 (stopAtFirstCut == TRUE) ? "(first cut only)" : "with rip-up");
5223
5224         fprintf(f,"\n(with flags-> rule #%d s:%d c:%d part:%d dir:%d)\n",
5225                 partition_rule, max_partition_size, max_partition_conn,
5226                 partition_count, matrix_type);
5227
5228         fprintf(f, "%d %d %d %d init\n", xfloor, yfloor, x_sizes[0], y_sizes[0]);
5229
5230         fprintf(f,"\n(N2A %s %s input:?? s:%d c:%d r:%-5.3f rule #%d part:%d dir:%d) %d %d %d %d init\n",
5231         getenv("USER"), ctime(&time_loc), max_partition_size,
5232         max_partition_conn, partition_ratio, partition_rule,
5233         partition_count, matrix_type, xfloor, yfloor, x_sizes[0], y_sizes[0]);
5234
5235     }
5236     else /* This stuff replaces the init for latex mode */
5237     {
5238         ps_print_standard_header(f);
5239         fprintf(f,"%%%%BoundingBox: %d %d %d %d\n",
5240                 xfloor - CHANNEL_LENGTH, yfloor - CHANNEL_HEIGHT,
5241                 x_sizes[0] + CHANNEL_LENGTH, y_sizes[0] + CHANNEL_HEIGHT);
5242         fprintf(f, "swidth setlinewidth\n/Courier findfont fwidth scalefont setfont\n");
5243     }
5244
5245     /* Write the local route now: */
5246     write_local_route_to_file(f, nets);
5247
5248     if (latex != TRUE) fprintf(f, "showpage\n");
5249
5250
5251     if (debug_level == 1)
5252     {
5253         /* Write the local route now: */
5254         for (nl = nets; ((nl != NULL) && (strcmp(nl->this->name, net_under_study)));
5255              nl = nl->next);
5256         if (nl != NULL)
5257         {
5258             push(nl->this, &netToPrint);
5259             write_local_route_to_file(df, netToPrint);
5260         }
5261         if (latex != TRUE) fprintf(df, "showpage\n");
5262     }
5263 }
5264 /*------------------------------------------------------------------------------------*/
5265 int ignore_contents(t)
5266     tile *t;
5267 {
5268     return(FALSE);
5269 }
5270 /*-------------------------------------------------------------------------------------*/
5271 void ps_ignore_arc(f, t)
5272     FILE *f;
5273     tile *t;
5274 {
5275     /* This function prints the statistical info for the given tile in PostScript
5276        to the file <f>. */
5277     asg_arc *a = (asg_arc *)t->this;
5278     float x1, y1, x2, y2;
5279
5280     if (a->mod == NULL)
5281     {
5282         x1 = (float)a->t->x_pos + GRAY_MARGIN;
5283         x2 = (float)a->t->x_pos + (float)a->t->x_len - GRAY_MARGIN;
5284         y1 = (float)a->t->y_pos + GRAY_MARGIN;
5285         y2 = (float)a->t->y_pos + (float)a->t->y_len - GRAY_MARGIN;
5286
5287         if (member_p(net_under_study, a->nets, net_name_located_p) == TRUE)
5288         {
5289         /* print fancy stuff in the arcs that contain the <net_under_study> */
5290             if (a->page == VERT)
5291             {
5292                 x1 = (float)a->t->y_pos + GRAY_MARGIN;
5293                 x2 = (float)a->t->y_pos + (float)a->t->y_len - GRAY_MARGIN;
5294                 y1 = (float)a->t->x_pos + GRAY_MARGIN;
5295                 y2 = (float)a->t->x_pos + (float)a->t->x_len - GRAY_MARGIN;
5296             }
5297
5298             /* Fill in the area with gray, shaded to show global route */
5299             fprintf(f, "newpath %f %f moveto %f %f lineto ", x1, y1, x2, y1);
5300             fprintf(f, "%f %f lineto %f %f lineto ", x2, y2, x1, y2);
5301             fprintf(f, "closepath %.3f setgray fill 0 setgray\n", 0.9);
5302
5303             ps_put_int(f, a->local, x1, y2);
5304             ps_put_label(f, net_under_study, x1 + 2.0, y2);
5305         }
5306         else
5307         {
5308             ps_put_int(f, a->local, x1, y2);
5309         }
5310     }
5311 }
5312 /*-------------------------------------------------------------------------------------*/
5313 void print_tile_spaces(f1, f2)
5314     FILE *f1, *f2;
5315 {
5316     long time_loc;
5317     extern long int time();
5318
5319    /* Define the bounding box for the post-script code: */
5320     fprintf(f1,"%%%%BoundingBox: %d %d %d %d\n",
5321             xfloor - CHANNEL_LENGTH, yfloor - CHANNEL_HEIGHT,
5322             x_sizes[0] + CHANNEL_LENGTH, y_sizes[0] + CHANNEL_HEIGHT);
5323     fprintf(f2,"%%%%BoundingBox: %d %d %d %d\n",
5324             yfloor - CHANNEL_HEIGHT, xfloor - CHANNEL_LENGTH,
5325             y_sizes[0] + CHANNEL_HEIGHT, x_sizes[0] + CHANNEL_LENGTH);
5326
5327     /* now dump the result */
5328     time_loc = time(0L);
5329
5330     if (latex != TRUE) /* Not in latex mode */
5331     {
5332         ps_print_standard_header(f1);
5333         fprintf(f1,
5334                 "\n(Horizontal Tilespace for N2A %s %s input:?? s:%d rule #%d part:%d dir:%d) %d %d %d %d init\n",
5335                 getenv("USER"), ctime(&time_loc),
5336                 max_partition_size, partition_rule,
5337                 partition_count, matrix_type,
5338                 xfloor, yfloor, x_sizes[0], y_sizes[0]);
5339
5340         ps_print_standard_header(f2);
5341         fprintf(f2,
5342                 "\n(Vertical Tilespace for N2A %s %s input:?? s:%d rule #%d part:%d dir:%d) %d %d %d %d init\n",
5343                 getenv("USER"), ctime(&time_loc),
5344                 max_partition_size, partition_rule,
5345                 partition_count, matrix_type,
5346                 xfloor, yfloor, x_sizes[0], y_sizes[0]);
5347
5348         /* Special stuff for the vertical tile space: */
5349         fprintf(f2, "%% Flip the figure, as x's and y's are reversed: %%\n");
5350         fprintf(f2, "    -1 1 scale %d neg %d translate\n",
5351                 y_sizes[0] + CHANNEL_HEIGHT, xfloor - CHANNEL_LENGTH);
5352         fprintf(f2, "    180 rotate %d neg %d neg translate \n",
5353                 xfloor - CHANNEL_LENGTH, y_sizes[0] + CHANNEL_HEIGHT);
5354     }
5355     else /* This stuff replaces the init for latex mode */
5356     {
5357         ps_print_standard_header(f1);
5358         fprintf(f1, "swidth setlinewidth\n/Courier findfont fwidth scalefont setfont\n");
5359         fprintf(f1,"%%%%BoundingBox: %d %d %d %d\n",
5360                 xfloor - CHANNEL_LENGTH, yfloor - CHANNEL_HEIGHT,
5361                 x_sizes[0] + CHANNEL_LENGTH, y_sizes[0] + CHANNEL_HEIGHT);
5362
5363         ps_print_standard_header(f2);
5364         fprintf(f2, "swidth setlinewidth\n/Courier findfont fwidth scalefont setfont\n");
5365         fprintf(f2,"%%%%BoundingBox: %d %d %d %d\n",
5366                 yfloor - CHANNEL_HEIGHT, xfloor - CHANNEL_LENGTH,
5367                 y_sizes[0] + CHANNEL_HEIGHT, x_sizes[0] + CHANNEL_LENGTH);
5368
5369         /* Special stuff for the vertical tile space: */
5370         fprintf(f2,"%% Flip the figure, as x's and y's are reversed: %%\n");
5371         fprintf(f2,"    -1 1 scale %d neg 0 translate\n", y_sizes[0] + CHANNEL_HEIGHT);
5372         fprintf(f2,"    90 rotate 0 %d neg translate\n", y_sizes[0] + CHANNEL_HEIGHT);
5373     }
5374
5375
5376     /* Write the tile spaces now: */
5377     solidp = (debug_level != 11) ? ignore_contents : solidp_for_printing;
5378     ps_print_tile_space(routingRoot[HORZ][0], f1, ps_ignore_arc, TRUE);
5379     ps_print_tile_space(routingRoot[VERT][0], f2, ps_ignore_arc, TRUE);
5380
5381 /*    write_local_route_to_file(f, nets); */
5382
5383     if (latex != TRUE)
5384     {
5385         fprintf(f1, "showpage\n");
5386         fprintf(f2, "showpage\n");
5387     }
5388 }
5389 /*------------------------------------------------------------------------------------*/
5390 /* --------------------------------------------------------------
5391  * quality_statistics
5392  * This function provides statistics on how well the routing was
5393  * done:  Statistics are # modules, # nets, # terminals, #cc @ level <l>...
5394  * # cc @ level 1, # foul-ups.
5395  * A signal flow foulup is defined as any non-cc module who's child is not
5396  * in an x-position greater-than its parent.
5397  * Other useful info is the filename, date, and all of the (specified?)
5398  * command-line args.  All information is printed to a file "quality_stats"
5399  *---------------------------------------------------------------
5400  */
5401 void quality_statistics()
5402 {
5403     int cc_count[10];
5404     int xfouls = 0, yfouls = 0, term_count = 0, lev;
5405     int out_x, in_x, out_y, in_y, possibly_screwed, also_unscrewed;
5406
5407     mlist *ml;
5408     module *m, *last_m, *cc_m, *top_cc_mod, *bot_cc_mod;
5409     tlist *t, *tt;
5410
5411     FILE *f = fopen("quality_stats", "a");
5412
5413     for (lev=0; lev < cc_search_level; lev++) cc_count[lev] = 0;
5414
5415     last_m = modules->this;
5416     last_m->placed = UNPLACED;  /* for cross_coupled_p to work properly */
5417
5418     term_count = list_length(last_m->terms);
5419
5420
5421     for(ml = modules->next; ml != NULL; ml = ml->next)
5422     {
5423         m = cc_m = ml->this;
5424         term_count += list_length(m->terms);
5425
5426         /* Set up all the strangeness for cross-coupled modules: */
5427         for (lev = 1; (lev <= cc_search_level) && (cc_m != NULL); lev++)
5428         {
5429             cc_m->placed = UNPLACED;
5430
5431             if (cross_coupled_p(last_m, cc_m, lev) != FALSE)
5432             {
5433                 top_cc_mod = last_m;
5434                 bot_cc_mod = cc_m;
5435                 cc_count[lev-1] += 1;
5436                 break;
5437             }
5438             cc_m = (ml->next != NULL) ? ml->next->this : NULL;
5439         }
5440
5441         for (t = last_m->terms; t != NULL; t = t->next)
5442         {
5443             if ((t->this->type == OUT) || (t->this->type == INOUT))
5444             {
5445                 possibly_screwed = FALSE;
5446                 also_unscrewed = FALSE;
5447
5448                 for (tt = t->this->nt->terms; tt != NULL; tt = tt->next)
5449                 {
5450                     if ((tt->this->type == IN) || (tt->this->type == INOUT))
5451                     {
5452                         out_x = t->this->mod->x_pos + t->this->x_pos;
5453                         in_x = tt->this->mod->x_pos + tt->this->x_pos;
5454                         out_y = t->this->mod->y_pos + t->this->y_pos;
5455                         in_y = tt->this->mod->y_pos + tt->this->y_pos;
5456
5457                         if (((t->this->mod == top_cc_mod)&&(tt->this->mod == bot_cc_mod)) ||
5458                             ((t->this->mod == bot_cc_mod)&&(tt->this->mod == top_cc_mod)))
5459                         {  /* Skip cc modules */
5460                             also_unscrewed = TRUE;
5461                         }
5462
5463                         else if (out_x > in_x)
5464                         { xfouls += 1; }
5465
5466                         else if (out_y < in_y)
5467                         { possibly_screwed = TRUE; }
5468
5469                         else
5470                         { also_unscrewed = TRUE; }
5471
5472                     }
5473                 }
5474                 if ((possibly_screwed == TRUE) && (also_unscrewed == FALSE)) yfouls += 1;
5475             }
5476         }
5477         /* for next iteration: */
5478         last_m = m;
5479         last_m->placed = UNPLACED;
5480
5481     }
5482
5483     /* Done gathering statistics! */
5484     terminal_count = term_count;                /* Save this quantity in the golbal */
5485
5486     fprintf(f,"------------------------------------------------------------------------------\n");
5487
5488     fprintf(f,"| ?? -p%d -s%d -c%d -r%-4.2f -m%d \t ||",
5489             partition_rule, max_partition_size, max_partition_conn,
5490             partition_ratio, matrix_type);
5491
5492     fprintf(f, "\t %d \t %d \t %d \t %dx%d = %d",
5493             xfouls, yfouls, xfouls+yfouls, x_sizes[0], y_sizes[0], x_sizes[0] * y_sizes[0]);
5494
5495     fprintf(f," |\n");
5496     fclose(f);
5497
5498 }
5499
5500 /*------------------------------------------------------------------------------------*/
5501 int falls_in_tile_p(t, c)
5502     tile *t;
5503     corner *c;
5504 {
5505     /* returns TRUE iff corner <c> falls in tile <t> */
5506     return(corner_falls_in_arc_p(c, t->this));
5507 }
5508 /*------------------------------------------------------------------------------------*/
5509 int crossover_count(t)
5510     tile *t;
5511 {
5512     /* Count the number of crossovers within this tile */
5513     int crossoverCount = 0;
5514     asg_arc *pa, *a = (asg_arc *)t->this;
5515     tilist *tl, *tileSet = NULL;
5516     nlist *nl, *nll;
5517     corner *inCorn, *outCorn;
5518     crnlist *cl;
5519     int minXi, maxXi, minYi, maxYi;
5520     int minXo, maxXo, minYo, maxYo;
5521
5522     /* get the set of perpendicular tiles that cross this tile */
5523     tileSet = (tilist*)collect_tiles(t, routingRoot[toggle_direction(a->page)][0]);
5524
5525     for(tl = tileSet; tl != NULL; tl = tl->next)
5526     {
5527         pa = (asg_arc *)tl->this->this;
5528
5529         for (nll = pa->nets; nll != NULL; nll = nll->next)
5530         {
5531             cl = (crnlist *)member(tl->this, nll->this->route, falls_in_tile_p);
5532             if (cl == NULL) break;
5533             outCorn = cl->this;
5534
5535             for (nl = a->nets; nl != NULL; nl = nl->next)
5536             {
5537                 cl = (crnlist *)member(t, nl->this->route, falls_in_tile_p);
5538                 if (cl == NULL) break;
5539                 inCorn = cl->this;
5540
5541                 /* NOTE: if <inCorn> and <outCorn> share a similar range,
5542                    ignore them */
5543                 if ((inCorn->cx != outCorn->cx) && (inCorn->cy != outCorn->cy))
5544                 {
5545                     /* Skip it */
5546                 }
5547                 else if (a->page == VERT)
5548                 {
5549                     /* Find the max vertical extent and lowest position for the
5550                        segment associated with <inCorn>, and compare it to the max
5551                        horizontal extent and position for the segment associated
5552                        with <outCorn>.  If these two segments cross, count 'em. */
5553                     perpendicular_expanse(inCorn->cx, &minYi, &maxYi);
5554                     minXi = maxXi = inCorn->cx->sr->q1;
5555                     perpendicular_expanse(outCorn->cy, &minXo, &maxXo);
5556                     minYo = maxYo = outCorn->cy->sr->q1;
5557
5558                     if ((int_overlapped_p(minXi, maxXi, minXo, maxXo) == TRUE) &&
5559                         (int_overlapped_p(minYi, maxYi, minYo, maxYo) == TRUE))
5560                     {
5561                         /* There is a crossover, so count it: */
5562                         crossoverCount += 1;
5563                     }
5564                 }
5565                 else /* (a->page == HORZ) */
5566                 {
5567                     /* Find the max horizontal extent and lowest position for the
5568                        segment associated with <inCorn>, and compare it to the max
5569                        vertical extent and position for the segment associated
5570                        with <outCorn>.  If these two segments cross, count 'em. */
5571                     perpendicular_expanse(outCorn->cx, &minYo, &maxYo);
5572                     minXo = maxXo = outCorn->cx->sr->q1;
5573                     perpendicular_expanse(inCorn->cy, &minXi, &maxXi);
5574                     minYi = maxYi = inCorn->cy->sr->q1;
5575
5576                     if ((int_overlapped_p(minXi, maxXi, minXo, maxXo) == TRUE) &&
5577                         (int_overlapped_p(minYi, maxYi, minYo, maxYo) == TRUE))
5578                     {
5579                         /* There is a crossover, so count it: */
5580                         crossoverCount += 1;
5581                     }
5582                 }
5583             }
5584         }
5585     }
5586     return(crossoverCount);
5587 }
5588 /*------------------------------------------------------------------------------------*/
5589 float crossover_value(t)
5590     tile *t;
5591 {
5592     static int max = 0;
5593     int count, area;
5594     asg_arc *a;
5595
5596     if (t == NULL) return ((float)max);
5597
5598     a = (asg_arc*)t->this;
5599     count = crossover_count(t);
5600     max = MAX(max, count);
5601     area = t->x_len * t->y_len;
5602
5603     ordered_ilist_insert(t, count, &crossovers);
5604     a->local = area;
5605
5606     return((float)count/(float)area);
5607 }
5608 /*------------------------------------------------------------------------------------*/
5609 float congestion_value(t)
5610     tile *t;
5611 {
5612 /* NOTE: This definition differs from that used in the global routing
5613    routines.  See "congestion_cost" in file global_route.c      */
5614
5615     asg_arc *a = (asg_arc*)t->this;
5616     int count = list_length(a->corners);
5617     int area = t->x_len * t->y_len;
5618
5619     ordered_ilist_insert(t, count, &congestion);
5620     a->local = area;
5621
5622     return((float)count/(float)area);
5623 }
5624 /*------------------------------------------------------------------------------------*/
5625 reset_tile_congestion(t)
5626     tile *t;
5627 {
5628     asg_arc *a = (asg_arc *)t->this;
5629     crnlist *cl;
5630
5631     free_list(a->nets);         /* Scrap the old ->nets list */
5632     a->nets = NULL;
5633
5634     for (cl = a->corners; cl != NULL; cl = cl->next)    /* Build a new ->nets list */
5635     {
5636         pushnew(cl->this->cx->n, &a->nets);             /* Mark the route used */
5637     }
5638     (*set_congestion_value)(a);
5639 }
5640 /*------------------------------------------------------------------------------------*/
5641 void ps_print_tile_border(f, a)
5642     FILE *f;            /* Where to write things */
5643     asg_arc *a;         /* The asg_arc to be printed */
5644 {
5645     /* This function prints a dotted line that corresponds to the border of the
5646        tile in question. */
5647     tile *t = a->t;             /* The tile to be printed */
5648     int x1, y1, x2, y2;
5649
5650     if (t != NULL)
5651     {
5652         if (a->page == HORZ)    /* Get the orientation straight */
5653         {
5654             x1 = t->x_pos;              y1 = t->y_pos;
5655             x2 = x1 + t->x_len;         y2 = y1 + t->y_len;
5656         }
5657         else
5658         {
5659             y1 = t->x_pos;              x1 = t->y_pos;
5660             y2 = y1 + t->x_len;         x2 = x1 + t->y_len;
5661         }
5662
5663         fprintf(f,"%%%% Tile border for %x LLHC(%d,%d), URHC=(%d,%d) %%%%\n",
5664                 t, x1, y1, x2, y2);
5665         fprintf(f,"[1 2] 0.2 setdash\n");
5666         fprintf(f, "newpath %d %d moveto %d %d lineto ", x1, y1, x1, y2); /* left edge */
5667         fprintf(f, "%d %d lineto %d %d lineto ", x2, y2, x2, y1); /* top & right edges */
5668         fprintf(f, "%d %d lineto stroke\n", x1, y1);                    /* bottom edge */
5669         fprintf(f, "[] 0 setdash\n");
5670     }
5671 }
5672 /*------------------------------------------------------------------------------------*/
5673 float quality_ranking(manPWS,congDenAve,congCount, termCount)
5674     float manPWS,congDenAve;
5675     int congCount, termCount;
5676 {
5677     /* This returns the appropriate scaling for the relative ranking of
5678        this diagram.  Ideally, among a set of diagrams, the one with the
5679        lowest value is "the best" diagram, etc.. */
5680
5681     float PWS_const = 4.0;
5682     float CD_const = 12.0;
5683     float CC_const = 4.0;
5684     float sum;
5685
5686     sum = (PWS_const/manPWS) + (CD_const * congDenAve) +
5687           ((float)congCount/(float)termCount/CC_const);
5688     return(sum);
5689 }
5690 /*------------------------------------------------------------------------------------*/
5691 void collect_congestion_stats(page)
5692     int page;
5693 {
5694     /* This function evaluates the route for congestion statistics information */
5695     /* The desired values are the average congestion-per-tile, the standard deviation
5696        of the congestion-per-tile, and the tile that is most congested. */
5697
5698     tile *vRoot = routingRoot[VERT][page], *hRoot = routingRoot[HORZ][page], *t;
5699     tilist *vRoutingTiles = NULL, *hRoutingTiles = NULL, *tl;
5700     asg_arc *a, *worstCong, *worstCross;
5701     ilist *il, *ill;
5702     int area, i, congCount = 0, crossCount = 0, conge=0, cros=0;
5703     float congSum = 0.0, congSumSquared = 0.0, count = 0.0, cong;
5704     float crosSum = 0.0, crosSumSquared = 0.0, cross;
5705     float vCongSum, vCongSumSquared, vCrosSum, vCrosSumSquared, vnum;
5706     float hCongSum, hCongSumSquared, hCrosSum, hCrosSumSquared, hnum;
5707
5708     float vCongStandardDeviation, vCongAverage, hCongStandardDeviation, hCongAverage;
5709     float vCrosStandardDeviation, vCrossAverage, hCrosStandardDeviation, hCrossAverage;
5710     float congDeviation, congAverage, crossDeviation, crossAverage;
5711
5712     FILE *qsf = fopen("qual_stats", "a");
5713
5714     fprintf (stderr, "Collecting Routing statistics in file qual_stats.\n");
5715
5716     freespace(vRoot, &vRoutingTiles);
5717     freespace(hRoot, &hRoutingTiles);
5718
5719     /* Collect congestion and crossover stats for the vertical tiles: */
5720     for (tl = vRoutingTiles; tl != NULL; tl = tl->next)
5721     {
5722         reset_tile_congestion(tl->this);
5723         cong = congestion_value(tl->this);      cross = crossover_value(tl->this);
5724         congSum += cong;                        crosSum += cross;
5725         congSumSquared += cong * cong;          crosSumSquared += cross * cross;
5726         count += 1.0;
5727     }
5728
5729     vnum = count;
5730     vCongSum = congSum;                 vCrosSum = crosSum;
5731     vCongSumSquared = congSumSquared;   vCrosSumSquared = crosSumSquared;
5732
5733     vCongAverage = vCongSum/vnum;
5734     vCongStandardDeviation = sqrt(vCongSumSquared/vnum - vCongAverage * vCongAverage);
5735
5736     vCrossAverage = vCrosSum/vnum;
5737     vCrosStandardDeviation = sqrt(vCrosSumSquared/vnum - vCrossAverage * vCrossAverage);
5738
5739     /* Collect congestion and crossover stats for the horizontal tiles: */
5740     for (tl = hRoutingTiles; tl != NULL; tl = tl->next)
5741     {
5742         reset_tile_congestion(tl->this);
5743         cong = congestion_value(tl->this);      cross = crossover_value(tl->this);
5744         congSum += cong;                        crosSum += cross;
5745         congSumSquared += cong * cong;          crosSumSquared += cross * cross;
5746         count += 1.0;
5747     }
5748
5749     hnum = count - vnum;
5750     hCongSum = congSum - vCongSum;              hCrosSum = crosSum - vCrosSum;
5751     hCongSumSquared = congSumSquared - vCongSumSquared;
5752     hCrosSumSquared = crosSumSquared - vCrosSumSquared;
5753
5754     hCongAverage = (float)hCongSum/(float)hnum;
5755     hCongStandardDeviation = sqrt((float)hCongSumSquared/(float)hnum -
5756                                   hCongAverage * hCongAverage);
5757
5758     hCrossAverage = (float)hCrosSum/(float)hnum;
5759     hCrosStandardDeviation = sqrt((float)hCrosSumSquared/(float)hnum -
5760                                   hCrossAverage * hCrossAverage);
5761
5762     /* Now do funny things to only do statistics on the worst 10% of the tiles */
5763     congSum = 0.0;      crosSum = 0.0;
5764     count = (float)(int)((ilist_length(congestion) * 0.100) + 0.5);
5765
5766     ill = reverse_copy_ilist(congestion);
5767     for (il = ill; ((il != NULL) && (il->index > 0)); il = il->next)
5768     {
5769         t = (tile*)il->this;
5770         a = (asg_arc*)t->this;
5771         area = a->local;
5772         congSum += (float)il->index/(float)area;
5773         congCount += 1;
5774         conge += il->index;                     /* Total congestion */
5775         if (il == ill)
5776         {
5777             worstCong = (asg_arc*)t->this;
5778             worstCong->congestion = ill->index;
5779             ps_print_tile_border(stdout, worstCong);
5780         }
5781     }
5782     free_ilist(ill);
5783     ill = reverse_copy_ilist(crossovers);
5784     for (il = ill; ((il != NULL) && (il->index > 0)); il = il->next)
5785     {
5786         t = (tile*)il->this;
5787         a = (asg_arc*)t->this;
5788         area = a->local;
5789         crosSum += (float)il->index/(float)area;
5790         crossCount += 1;
5791         cros += il->index;                      /* Total Crossovers */
5792         if (il == ill)
5793         {
5794             worstCross = (asg_arc*)t->this;
5795             worstCross->count = ill->index;
5796         }
5797     }
5798     free_ilist(congestion);     free_ilist(crossovers);
5799
5800     congAverage = (float)congSum/(float)congCount;
5801     congDeviation = sqrt((float)congSumSquared/(float)congCount -
5802                          congAverage * congAverage);
5803
5804     crossAverage = (float)crosSum/(float)crossCount;
5805     crossDeviation = sqrt((float)crosSumSquared/(float)crossCount -
5806                           crossAverage * crossAverage);
5807
5808     /* Now that the calculations have been done, print out the line with the info: */
5809     fprintf(qsf,"------------------------------------------------------------------------------\n");
5810
5811     fprintf(qsf,"?? -p%d -s%d -c%d -r%-4.2f %s %s %s\t ||",
5812             partition_rule, max_partition_size, max_partition_conn,
5813             partition_ratio, (stopAtFirstCut == TRUE) ? "-f" : "--",
5814             (useSlivering == FALSE) ? "-v" : "--", (useAveraging == TRUE) ? "-w" : "--");
5815
5816     fprintf(qsf, "\t %-6.4f \t ", congAverage);
5817
5818     fprintf(qsf, "%d \t %d  |", conge, worstCong->congestion);
5819
5820     fprintf(qsf, "\t %-6.4f \t", crossAverage);
5821
5822     fprintf(qsf, "%d \t %d  |", cros, worstCross->count);
5823
5824     fprintf(qsf, "\t| %-6.4f |", quality_ranking(manhattan_PWS(), congAverage,
5825                                                  conge, terminal_count));
5826
5827     fprintf(qsf,"\n");
5828     fclose(qsf);
5829
5830     /* Now print the outline of the worst congested tile: */
5831 }
5832
5833 /*------------------------------------------------------------------------------------*/
5834 /*------------------------------------------------------------------------------------*/
5835 /*------------------------------------------------------------------------------------*/
5836
5837 /* END OF FILE "local_route.c" */