asg/global_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  *      file global_route.c
  24  * As part of MS Thesis Work, S T Frezza, UPitt Engineering
  25  * February, 1990 - Major revision July, 1990 - Incremental GR January, 1991
  26  *
  27  * This file contains the global and local routing functions associated with the
  28  * SPAR schematics placer.  It is based on the data-structures created by the
  29  * parser (parse.c) and the placer (place.c), and is thus dependent upon:        */
  30
  31 #include <stdio.h>
  32 #include "route.h"
  33 #include "psfigs.h"
  34
  35 /* It is expected that all modules have been placed.
  36  *
  37  * The routing algorithm breaks the process into two stages, global and then local
  38  * routing.  To arrange for the channels used these two schemes, the modules are
  39  * indidvidually inserted into a tile space (see cstitch.c) and the set of empty tile
  40  * constitutes the available routing area.
  41  *
  42  * Global Routing:
  43  * This process determines the tiles through which each net will pass.  It is an
  44  * expansion process, where the nodes that are expanded into are edges of tiles.  The
  45  * general gist is to do a first route, and then apply rip-up-&-reroute techniques to
  46  * the most expensive of the routes, using cost-based expansion techniques. (Kern-like
  47  * expansions).
  48  *   This is done such that every net is ripped up at least once.  Nets are selected for
  49  * rip-up if they happen to be in using the most congested asg_arc on along a net that is
  50  * scheduled for rip-up.
  51  *
  52  * NEW ADDITIONS:
  53  * The global router will be a modified Korn [DAC '82]algorithm, somewhat similar to
  54  * that used in the PI Place and Route system from MIT.  The similarity is in the
  55  * creation of routing channels (via the use of two parallel, 90 deg rotated corner-
  56  * stitching structures).  The differences lie in the handling of multi-terminal nets.
  57  * These will be managed by drawing connecting lines to all points on the net, and
  58  * collecting the set of cells through which they pass.  All cells not on this list
  59  * will be be given a higher cost,  so as to speed the router up.  These lines will
  60  * extend from the target tiles that lay behind each of the terminals in question.
  61  *
  62  * Local Routing: see "local_route.c"
  63  *
  64  */
  65
  66
  67 /* ---- Global Variables -------------------------------------------------------------*/
  68
  69 char net_under_study[32] = "not in use";
  70 char dfname[40] = "temp";
  71
  72 net *Net = NULL;        /* Used as a temporary global */
  73
  74 FILE *df, *vf, *hf;     /* Where to dump the global route trace/debug info */
  75
  76 int currentPage;        /* The current page on which insertions are being made */
  77
  78 int (*set_congestion_value)();           /* The congestion function being used */
  79
  80
  81 /* --- forward reference -------------------------------------------------------------:*/
  82 void write_local_route_to_file();
  83 expnlist *list_completed_subnetsA();
  84 void prepare_tile_spaces();
  85 void delete_trail();
  86 void replace_trail();
  87 trail *copy_trail();
  88 void add_trail_copy();
  89 trailist *remove_trailA();
  90 trailist *remove_trailE();
  91 tile *initial_move();
  92 tile *locate_first_tile();
  93
  94 /*-------------------------------------------------------------------------------------
  95  * Setup stuff - This creates the tile/arc data structures, and the expansion
  96  *               elements for a given placement.
  97  *-------------------------------------------------------------------------------------
  98  */
  99
 100 /*-------------------------------------------------------------------------------------*/
 101
 102 void do_nothing()
 103 {
 104     ;
 105 }
 106
 107 /*-------------------------------------------------------------------------------------*/
 108
 109 int contents_equivalentp_for_arcs(t1, t2)
 110     tile *t1, *t2;
 111 {
 112     asg_arc *a1 = (asg_arc *)t1->this, *a2 = (asg_arc *)t2->this;
 113     if (a1->mod == a2->mod) return(TRUE);
 114     else return(FALSE);
 115 }
 116
 117 /*-------------------------------------------------------------------------------------*/
 118 /* return TRUE iff tile t is used. */
 119 /*-------------------------------------------------------------------------------------*/
 120
 121 int solidp_for_arcs(t)
 122     tile *t;
 123 {
 124     asg_arc *a = (asg_arc *)t->this;
 125
 126     return((a->mod != NULL) ? TRUE : FALSE);
 127 }
 128
 129 /*-------------------------------------------------------------------------------------*/
 130
 131 int emptyp_for_arcs(t)
 132     tile *t;
 133 {
 134     asg_arc *a = (asg_arc *)t->this;
 135
 136     return((a->mod != NULL) ? FALSE : TRUE);
 137 }
 138
 139 /*-------------------------------------------------------------------------------------*/
 140
 141 asg_arc *create_arc(t, page, modFlag)
 142     tile *t;
 143     int page, modFlag;
 144 {
 145     /* create a new arc structure, initialize it, and return it. */
 146     asg_arc *tarc;
 147     int i;
 148
 149     /* Modifies the tile space by replacing the contents field with an arc struct. */
 150     tarc = (asg_arc *)calloc(1, sizeof(asg_arc));
 151     tarc->congestion = 0;
 152     tarc->page = page;
 153     tarc->corners = NULL;
 154     tarc->nets = NULL;                  /* Where the 'whos used me' information goes */
 155     tarc->t = t;                        /* Store the tile pointer ( back pointer ) */
 156     /* if this is a blank tile being transformed, save the module pointer. */
 157     tarc->mod = (modFlag == TRUE) ? (module *)t->this : NULL;
 158     tarc->vcap = (page == VERT) ? t->x_len : t->y_len;
 159     tarc->hcap = (page == HORZ) ? t->x_len : t->y_len;
 160     tarc->local = tarc->count = 0;
 161
 162     for (i=0; i<HASH_SIZE; i++) tarc->trails[i] = NULL;
 163
 164     t->this = (int *)tarc;              /* Replace the tile contents with the arc str. */
 165
 166     return (tarc);
 167 }
 168
 169 /*------------------------------------------------------------------------------------*/
 170
 171 delete_arc(a)
 172     asg_arc *a;
 173 {
 174     /* Delete the contents and allocation for this arc: */
 175     a->nets = (nlist *)free_list(a->nets);
 176     a->corners = (crnlist *)free_list(a->corners);
 177     kill_hashA(a);
 178     my_free(a);
 179 }
 180
 181 /*------------------------------------------------------------------------------------*/
 182
 183 assign_tile_dimensions(m, xPos, yPos, xLen, yLen)
 184     module *m;
 185     int *xPos, *yPos, *xLen, *yLen;
 186 {
 187     switch(validate(m->type))
 188     {
 189         case BUFFER :
 190         case NOT_  :
 191         case AND  :
 192         case NAND :
 193         case OR   :
 194         case NOR  :
 195         case XOR  :
 196         case XNOR : *xPos = m->x_pos - TERM_MARGIN;
 197                     *yPos = m->y_pos;
 198                     *xLen = m->x_size + 2 * TERM_MARGIN;
 199                     *yLen = m->y_size;
 200                     break;
 201         case INPUT_SYM : *xPos = m->x_pos;
 202                          *yPos = m->y_pos;
 203                          *xLen = m->x_size + TERM_MARGIN;
 204                          *yLen = m->y_size;
 205                          break;
 206         case OUTPUT_SYM : *xPos = m->x_pos - TERM_MARGIN;
 207                           *yPos = m->y_pos;
 208                           *xLen = m->x_size;
 209                           *yLen = m->y_size;
 210                           break;
 211         case BLOCK :
 212         default :
 213                      *xPos = m->x_pos - TERM_MARGIN;
 214                      *yPos = m->y_pos - TERM_MARGIN;
 215                      *xLen = m->x_size + 2 * TERM_MARGIN;
 216                      *yLen = m->y_size + 2 * TERM_MARGIN;
 217                      break;
 218    }
 219 }
 220
 221 /*------------------------------------------------------------------------------------*/
 222
 223 insert_all_modules(hroot, vroot, ml)
 224     tile *hroot, *vroot;
 225     mlist *ml;
 226 {
 227     /* This function inserts each listed tile into the tile space containing <hroot>. */
 228     /* The tile is also inserted into the vertically-oriented space by reversing the
 229        x,y ordiering */
 230
 231     mlist *mll;
 232     tile *t;
 233     int xPos, yPos, xLen, yLen;
 234
 235     /* Reset the content-manging stuff for this round of tile dealings: */
 236     solidp = std_solidp;
 237     contents_equivalentp = std_contents_equivalentp;
 238     insert_contents = std_insert_contents;
 239     manage_contents__hmerge = manage_contents__vmerge = null;
 240     manage_contents__hsplit= manage_contents__vsplit = null;
 241     manage_contents__dead_tile = null;
 242
 243     for (mll = ml; mll != NULL; mll = mll->next)
 244     {
 245         mll->this->htile = mll->this->vtile = NULL;     /* Zero out the tile pointers */
 246
 247         assign_tile_dimensions(mll->this, &xPos, &yPos, &xLen, &yLen);
 248
 249         /* Include a buffer around the modules for the terminals */
 250         t = insert_tile(hroot, xPos, yPos, xLen, yLen, mll->this);
 251         mll->this->htile = t;                   /* save the horiz tile pointer
 252                                                    for cross-reference */
 253         if (t == NULL)
 254         {
 255             fprintf(stderr, "ERROR: %s module %s did not insert into horz tilespace\n",
 256                     mll->this->type, mll->this->name, mll->this);
 257             exit(-1);
 258         }
 259
 260         t = insert_tile(vroot, yPos, xPos, yLen, xLen, mll->this);
 261         mll->this->vtile = t;                   /* save the vert tile pointer for
 262                                                    cross-reference */
 263         if (t == NULL)
 264         {
 265             fprintf(stderr, "ERROR: %s module %s did not insert into vert tilespace\n",
 266                     mll->this->type, mll->this->name, mll->this);
 267             exit(-1);
 268         }
 269
 270         mll->this->placed = FALSE;      /* Reuse of flag, now used for printing */
 271     }
 272 }       /* No error checking */
 273
 274 /*------------------------------------------------------------------------------------*/
 275
 276 distribute_corner_list(owner, partner)
 277     asg_arc *owner, *partner;   /* <owner> contains <corners>, <partner>s ->corners
 278                                    should be NULL. */
 279 {
 280     /* Redistribute the corners contained in <corners> amongst the two tiles such that
 281        the range limitations of the various points are observed.  Correct the
 282        tile/arc pointers within the corner structures themselves.  */
 283
 284     crnlist *cl, *corners = (crnlist *)rcopy_list(owner->corners);
 285
 286     for (cl = corners; cl != NULL; cl = cl->next)
 287     {
 288         if (corner_falls_in_arc_p(cl->this, owner) == FALSE)
 289         {
 290             pull_corner_from_arc(cl->this, owner);
 291         }
 292         if ((partner != NULL) && (corner_falls_in_arc_p(cl->this, partner) == TRUE))
 293         {
 294             add_corner_to_arc(cl->this, partner);
 295         }
 296     }
 297     free_list(corners);
 298 }
 299
 300 /*------------------------------------------------------------------------------------*/
 301
 302 consolodate_corner_list(taker, giver)
 303     asg_arc *taker, *giver;
 304 {
 305     /* Redistribute the corners contained in <giver> into <taker>.
 306        The range limitations of the various points are observed.  Correct the
 307        tile/arc pointers within the corner structures themselves.  */
 308
 309     crnlist *cl;
 310
 311     for (cl = giver->corners; cl != NULL; cl = cl->next)
 312     {
 313         if (corner_falls_in_arc_p(cl->this, taker) == TRUE)
 314         {
 315             add_corner_to_arc(cl->this, taker);
 316         }
 317         pull_corner_from_arc(cl->this, taker);
 318     }
 319 }
 320
 321 /*------------------------------------------------------------------------------------*/
 322
 323 int definite_overlap_p(a1, a2, b1, b2)
 324     int a1, a2, b1, b2;
 325 {
 326     if ((a1 < b2) && (a2 > b1)) return(TRUE);
 327     else return(FALSE);
 328 }
 329
 330 /*------------------------------------------------------------------------------------*/
 331
 332 int tile_contacts_tile_p(t1, t2)
 333     tile *t1, *t2;
 334 {
 335     /* Returns TRUE iff <t1> intersects <t2>.  It is assumed that the two tiles
 336        are from opposite page orientations. */
 337
 338     if ((definite_overlap_p(t1->x_pos, t1->x_pos + t1->x_len,
 339                         t2->y_pos, t2->y_pos + t2->y_len) == TRUE) &&
 340         (definite_overlap_p(t2->x_pos, t2->x_pos + t2->x_len,
 341                         t1->y_pos, t1->y_pos + t1->y_len) == TRUE))
 342     {
 343         return(TRUE);
 344     }
 345     else return(FALSE);
 346 }
 347
 348 /*------------------------------------------------------------------------------------*/
 349
 350 int valid_trail_p(tr)
 351     trail *tr;
 352 {
 353     /* Check the given trail <tr> for consitency. */
 354     tile *termTile;
 355     tilist *tl;
 356     int tx, ty;
 357     term *t;
 358
 359     for (tl = tr->tr; tl != NULL; tl = tl->next)
 360     {
 361         if ((tl == tr->tr) &&            /* First tile on list && */
 362             (tr->jEx != NULL))           /* It's a completed trail */
 363         {
 364             termTile = initial_move(tr->jEx, HORZ);
 365             if (termTile != tl->this)
 366             {
 367                 return (FALSE);
 368             }
 369         }
 370
 371         if (tl->next != NULL)
 372         {
 373             if (tile_contacts_tile_p(tl->this, tl->next->this) == FALSE)
 374             {
 375                 return(FALSE);
 376             }
 377         }
 378         else    /* At the beginning of the trail, so check to see that it touches
 379                    the terminial listed for tr->ex->t */
 380         {
 381             termTile = initial_move(tr->ex, HORZ);
 382             if (termTile != tl->this)
 383             {
 384                 return (FALSE);
 385             }
 386         }
 387     }
 388     return(TRUE);
 389 }
 390
 391 /*------------------------------------------------------------------------------------*/
 392
 393 int check_trail_p(tr, org, rep)
 394     trail *tr;
 395     tile *org, *rep;
 396 {
 397     /* Check the given trail <tr> for the tile <org>.  For the instance of <org>,
 398        replace it with <rep> and check to see that the trail is still valid, that
 399        is that the (two) neighbor(s) of <org> can legally reach <rep>. */
 400     /* This simply insures that the trail works up to the point where the
 401        replacement occurs. */
 402
 403     tile *termTile;
 404     tilist *tl;
 405     term *t;
 406     int tx, ty, foundIt = FALSE, damnThingFits = 0;
 407
 408     if (tr->tr->this == org) damnThingFits = 1;      /* <org> is at head of list */
 409
 410     for (tl = tr->tr; tl != NULL; tl = tl->next)
 411     {   /* This first check is a validation check */
 412         if ((tl == tr->tr) &&            /* First tile on list && */
 413             (tr->jEx != NULL))           /* It's a completed trail */
 414         {
 415             termTile = initial_move(tr->jEx, HORZ);
 416             if (((tl->this == org) && (rep != termTile)) ||
 417                 ((tl->this != org) && (termTile != tl->this)))
 418             {
 419                 return (FALSE);
 420             }
 421         }
 422
 423         if (tl->next != NULL)
 424         {
 425             if ((tl->next->this == org) &&
 426                 (tile_contacts_tile_p(tl->this, rep) == TRUE)) damnThingFits +=1;
 427             else if (tl->this == org)
 428             {
 429                 foundIt = TRUE;
 430                 if (tile_contacts_tile_p(tl->next->this, rep) == TRUE)
 431                     damnThingFits += 1;
 432             }
 433             else if (tile_contacts_tile_p(tl->this, tl->next->this) == FALSE)
 434             {
 435                 return(FALSE);
 436             }
 437         }
 438         else
 439         {
 440             termTile = initial_move(tr->ex, HORZ);
 441             if (tl->this == org)
 442             {   /* <org> is at tail end of list */
 443                 foundIt = TRUE;
 444                 if (termTile == rep) damnThingFits += 1;
 445             }
 446             else if (termTile != tl->this)
 447             {
 448                 return (FALSE);
 449             }
 450         }
 451     }
 452     if (foundIt != TRUE)
 453     {
 454         fprintf(stderr, "Tile 0x%x got lost (wrt trail 0x%x)\n", org, tr);
 455     }
 456     return (((foundIt == TRUE) && (damnThingFits >= 2)) ? TRUE : FALSE);
 457 }
 458
 459 /*------------------------------------------------------------------------------------*/
 460 /*------------------------------------------------------------------------------------*/
 461
 462 trail *enumerate_trail(pTrail, org, rep)
 463     trail *pTrail;
 464     tile *org, *rep;
 465 {
 466     /* Replicate the given trail with the <org> tile replaced with the <rep> tile.
 467        Do no error checking or costing */
 468     trail *t = copy_trail(pTrail);
 469     repl_item(org, rep, t->tr);
 470     return(t);
 471 }
 472
 473 /*------------------------------------------------------------------------------------*/
 474
 475 void manage_trails_for_merge(amoeba, food)
 476     asg_arc *amoeba, *food;
 477 {
 478     /* This is to merge/validate/correct the trails collected in the <amoeba> arc;
 479        The appropriate trails are swiped from the <food> arc.  The 'food' arc
 480        is about to be swallowed up... */
 481
 482     /* Also builds the ->nets list for the <amoeba> arc, deleting that for the <food>
 483        arc.  The congestion values are appropriately set.*/
 484     int i;
 485     trail *t;
 486     trailist *trl, *temp;
 487
 488     if (amoeba == NULL)
 489     {
 490         if (food != NULL)
 491         {
 492             manage_trails_for_merge(food, amoeba);
 493             return;
 494         }
 495         else return;                            /* Bad call... */
 496     }
 497     else if (food == NULL) return;              /* Trivial Case */
 498
 499     amoeba->nets = (nlist *)free_list(amoeba->nets);
 500
 501     /* Walk through the table in <food>, copying whatever is of use, and destroying
 502        the rest.  When completed, <food>'s hash table should get nuked. */
 503     for (i=0; i<HASH_SIZE; i++)
 504     {
 505         temp = (trailist *)rcopy_ilist(food->trails[i]);
 506         for (trl = temp; trl != NULL; trl = trl->next)
 507         {
 508             if (check_trail_p(trl->this, food->t, amoeba->t) == TRUE)
 509             {
 510                 repl_item(food->t, amoeba->t, t->tr);
 511                 insert_trailA(trl->this, food);
 512                 pushnew(t->ex->n, &food->nets);
 513             }
 514             remove_trailA(trl->this, food);
 515         }
 516         temp = (trailist *)free_ilist(temp);
 517         food->trails[i] = (trailist *)free_ilist(food->trails[i]);
 518     }
 519 }
 520
 521 /*------------------------------------------------------------------------------------*/
 522
 523 trlist *manage_trails_for_split(parent, sibling, pFlag)
 524     asg_arc *parent, *sibling;
 525     int pFlag;                  /* If TRUE, then modify <parent> */
 526 {
 527     /* This is to validate/correct the trails collected in the <parent> arc;
 528        The appropriate trails are then recreated for the <sibling> arc. */
 529
 530     /* Also rebuilds the ->nets list for each of the arcs, and resets the congestion
 531        value. */
 532
 533     /* The <pFlag> acts as a delayer;  The clean-up for the <parent> arc is only
 534        evaluated if the flag is set. */
 535     int i;
 536     tile *p, *s;
 537     trail *t;
 538     trailist *temp, *trash, *trl;
 539     trlist *valid = NULL;
 540
 541     if (parent == NULL)
 542     {
 543         if (sibling != NULL)
 544         {
 545             valid = manage_trails_for_split(sibling, parent, pFlag);
 546             return(valid);
 547         }
 548         else return;                            /* Bad call... */
 549     }
 550
 551     p = parent->t;
 552     parent->nets = (nlist *)free_list(parent->nets);
 553
 554     if ((sibling == NULL) && (pFlag == TRUE))
 555     {
 556         /* Any trail that connects <p> validly (ie, now that p has been changed)
 557            is still valid, and should remain in the table to be rehashed.
 558            Any trail that does not connect should be nuked.
 559
 560            This is a selective rehash of the arc.  */
 561         for (i=0; i<HASH_SIZE; i++)
 562         {
 563             temp = (trailist *)rcopy_ilist(parent->trails[i]);
 564
 565             for (trl = temp; trl != NULL; trl = trl->next)
 566             {
 567                 if (check_trail_p(trl->this, p, p) == TRUE)
 568                 {
 569                     t = trl->this;
 570                     t->cost = trail_cost(t);
 571                     replace_trail(t, t);
 572                     pushnew(t->ex->n, &parent->nets);
 573                     if (valid_trail_p(t) == TRUE) push(t, &valid);;
 574                 }
 575                 else if (pFlag == TRUE)
 576                 {
 577                     delete_trail(trl->this);
 578                 }
 579             }
 580             temp = (trailist *)free_ilist(temp);
 581         }
 582     }
 583     else
 584     {
 585         /* Any trail that connects <s> validly (when <p> usage is replaced with <s>)
 586            is still valid, and should be added to <sibling>'s table.
 587            Any trail that does not connect should be ignored. */
 588
 589         s = sibling->t;
 590         sibling->nets = (nlist *)free_list(sibling->nets);
 591
 592         for (i=0; i<HASH_SIZE; i++)
 593         {
 594             temp = (trailist *)rcopy_ilist(parent->trails[i]);
 595
 596             for (trl = temp; trl != NULL; trl = trl->next)
 597             {
 598                 if ((check_trail_p(trl->this, p, p) == TRUE) &&
 599                     (pFlag == TRUE))
 600                 {
 601                     t = trl->this;
 602                     t->cost = trail_cost(t);
 603                     replace_trail(t, t);
 604                     pushnew(t->ex->n, &parent->nets);
 605                     if (valid_trail_p(t) == TRUE) push(t, &valid);;
 606
 607                     if (check_trail_p(trl->this, p, s) == TRUE)
 608                     {
 609                         t = enumerate_trail(trl->this, p, s);
 610                         t->cost = trail_cost(t);
 611                         add_trail_copy(t);
 612                         if (valid_trail_p(t) == TRUE) push(t, &valid);;
 613                     }
 614                 }
 615                 else    /* Blow the trail away.  It is now been proven invalid. */
 616                 {
 617                     if (check_trail_p(trl->this, p, s) == TRUE)
 618                     {
 619                         t = enumerate_trail(trl->this, p, s);
 620                         t->cost = trail_cost(t); /* can't break ties if <trl->this> is */
 621                         if (pFlag == TRUE) delete_trail(trl->this);
 622                         add_trail_copy(t);       /* addition */
 623                         if (valid_trail_p(t) == TRUE) push(t, &valid);;
 624                     }
 625                     else if (pFlag == TRUE)
 626                     {
 627                         delete_trail(trl->this);
 628                     }
 629                 }
 630             }
 631             temp = (trailist *)free_ilist(temp);
 632         }
 633     }
 634     return(valid);
 635 }
 636
 637 /*------------------------------------------------------------------------------------*/
 638 /*------------------------------------------------------------------------------------*/
 639
 640 void manage_arc_during_hmerge(left, right)
 641     tile *left, *right;
 642 {
 643     /* <left> will remain, while <right> is destroyed.  All pertinent info from <right>
 644        needs to be copied into <left>.
 645      */
 646     asg_arc *lArc, *rArc;
 647
 648     if (left == NULL)
 649     {
 650         fprintf(stderr, "manage_arc_during_hmerge called with NULL arg...\n");
 651         return;                 /* probably very bad... */
 652     }
 653     else if (right != NULL)
 654     {
 655         return; /* Problem ??  Hard to say.  */
 656     }
 657     if (solidp_for_arcs(left) == TRUE)
 658     {
 659         fprintf(stderr, "problem in manage_arc_during_hmerge\n");
 660         lArc->mod = NULL;
 661     }
 662
 663     lArc = (asg_arc *)left->this;
 664     rArc = (asg_arc *)right->this;
 665
 666     lArc->hcap = (currentPage == HORZ) ? left->x_len : left->y_len;
 667     lArc->vcap = (currentPage == VERT) ? left->x_len : left->y_len;
 668     lArc->local += rArc->local;
 669     lArc->count += rArc->count;
 670
 671     consolodate_corner_list(lArc, rArc);
 672     manage_trails_for_merge(lArc, rArc);
 673 }
 674
 675 /*------------------------------------------------------------------------------------*/
 676
 677 void manage_arc_during_vmerge(bottom, top)
 678     tile *bottom, *top;
 679 {
 680     asg_arc *bArc, *tArc;
 681
 682     if (bottom == NULL)
 683     {
 684         fprintf(stderr, "manage_arc_during_hmerge called with NULL arg...\n");
 685         return;                         /* probably very bad... */
 686     }
 687     else if (top != NULL)
 688     {
 689         return;                         /* Problem ??  Hard to say.  */
 690     }
 691     if (solidp_for_arcs(bottom) == TRUE)
 692     {
 693         fprintf(stderr, "problem in manage_arc_during_vmerge\n");
 694         bArc->mod = NULL;
 695     }
 696
 697     bArc = (asg_arc *)bottom->this;
 698     tArc = (asg_arc *)top->this;
 699
 700     bArc->hcap = (currentPage == HORZ) ? bottom->x_len : bottom->y_len;
 701     bArc->vcap = (currentPage == VERT) ? bottom->x_len : bottom->y_len;
 702     bArc->local += tArc->local;
 703     bArc->count += tArc->count;
 704
 705     consolodate_corner_list(bArc, tArc);
 706     manage_trails_for_merge(bArc, tArc);
 707 }
 708
 709 /*------------------------------------------------------------------------------------*/
 710
 711 void manage_arc_during_hsplit(left, right)
 712     tile *left, *right;
 713 {
 714     asg_arc *a, *cArc, *pArc;
 715     trail *tr;
 716     trlist *collectedTrails = NULL;
 717
 718     /* Create the arc for the <child> arc and tie it in: */
 719     pArc = (asg_arc *)left->this;
 720     cArc = create_arc(right, currentPage, FALSE);
 721     pArc->hcap = (currentPage == HORZ) ? left->x_len : left->y_len;
 722     pArc->vcap = (currentPage == VERT) ? left->x_len : left->y_len;
 723     cArc->local = pArc->local;
 724     cArc->count = pArc->count;
 725
 726     distribute_corner_list(pArc, cArc);
 727     collectedTrails = manage_trails_for_split(pArc, cArc, TRUE);
 728
 729     if ((debug_level == 4) && (collectedTrails != NULL))
 730     {
 731         fprintf(stderr, "\narc for tiles [%x]c ", right);
 732         dump_tile(right);
 733         fprintf(stderr, " & [%x]p ", left);
 734         dump_tile(left);
 735         fprintf(stderr," contains %d trails: \n", list_length(collectedTrails));
 736         dump_trails(collectedTrails);
 737     }
 738 }
 739
 740 /*------------------------------------------------------------------------------------*/
 741
 742 void manage_arc_during_vsplit(top, bot)
 743     tile *top, *bot;
 744 {
 745     asg_arc *a, *cArc, *pArc;
 746     trail *tr;
 747     trlist *collectedTrails = NULL;
 748
 749     /* Create the arc for the <child> arc and tie it in: */
 750     pArc = (asg_arc *)top->this;
 751     cArc = create_arc(bot, currentPage, FALSE);
 752     pArc->hcap = (currentPage == HORZ) ? top->x_len : top->y_len;
 753     pArc->vcap = (currentPage == VERT) ? top->x_len : top->y_len;
 754     cArc->local = pArc->local;
 755     cArc->count = pArc->count;
 756
 757     distribute_corner_list(pArc, cArc);
 758     collectedTrails = manage_trails_for_split(pArc, cArc, TRUE);
 759
 760     if ((debug_level == 4) && (collectedTrails != NULL))
 761     {
 762         fprintf(stderr, "\nasg_arc for tiles [%x] ", bot);
 763         dump_tile(bot);
 764         fprintf(stderr, " & [%x] ", top);
 765         dump_tile(top);
 766         fprintf(stderr," contains %d trails: \n", list_length(collectedTrails));
 767         dump_trails(collectedTrails);
 768     }
 769 }
 770
 771 /*------------------------------------------------------------------------------------*/
 772
 773 void manage_arcs_for_modified_tiles(tilePairList)
 774     list *tilePairList;
 775 {
 776     /* Given a list of tilists in the form (child, parent), correct the arcs in
 777        each.  This essentially means checking all trails contained in each of the
 778        <parent> tiles, and then checking each trail for all combinations of variations.
 779        this is a lot of checking, but typically not a lot of work.  Typical trails
 780        will have only one affected tile, and the rare trail will have two.
 781
 782        given the lists (a,b), (c,d),(e,a), (f,d), the following arrangement should
 783        be made:  (in order!!)
 784            All occurances of <b> map into two lists, ...a... and ...b...
 785            All occurances of <d> map into two lists, ...d... and ...c...
 786            All occurances of <a> map into two lists, ...a... and ...e...
 787            All occurances of <d> map into two lists, ...d... and ...f...
 788        Note that this implies that the <d>'s actually form many more combinations.    */
 789
 790     list *l;
 791     tile *parent, *child;
 792     tilist *tl, *pr, *tilesTouched = NULL;
 793     asg_arc *a, *cArc, *pArc, *oldArc;
 794     trail *tr;
 795     trlist *trl, *enumTrails = NULL, *collectedTrails = NULL;
 796     trlist *remove_all_trails_from_arc();
 797
 798     /* Basic Method:
 799        (1) Collect all the trails from the parent arc (Remove them from the arcs)...
 800        (1a)Create arcs for the child tiles.
 801        (2) Then enumerate the trails, as per the <tilePairList> ordering...
 802        (3) Given this (enumerated) list of trails, validate each trail...
 803        (4) reinsert each trail into the arcspace...
 804        (5) Clean up list pointers.
 805        */
 806
 807     /* Generate the enuimerated trlist:  (Items (1) & (2) */
 808     for(l = tilePairList; l != NULL; l = l->next)
 809     {
 810         pr = (tilist *)l->this;
 811         parent = pr->next->this;        child = pr->this;
 812
 813         /* Create the arc for the <child> arc and tie it in: */
 814         pArc = (asg_arc *)parent->this;
 815         oldArc = (asg_arc *)child->this;
 816         cArc = create_arc(child, currentPage, FALSE);
 817         cArc->local = oldArc->local;
 818         cArc->count = oldArc->count;
 819         distribute_corner_list(oldArc, cArc);
 820         distribute_corner_list(pArc, cArc);
 821
 822         collectedTrails = remove_all_trails_from_arc(parent->this);
 823
 824         /* Comb through the trails that have already been enumerated; <parent> may
 825            or may not be a part of these trails */
 826         for (trl = enumTrails; trl != NULL; trl = trl->next)
 827         {
 828             if (member_p(parent, trl->this->tr, identity) == TRUE)
 829             {
 830                 tr = enumerate_trail(trl->this, parent, child);
 831                 push(tr, &enumTrails);
 832             }
 833         }
 834
 835         /* enumerate all of the <collectedTrails>, as <parent> is a member of each of
 836            these. */
 837         for (trl = collectedTrails; trl != NULL; trl = trl->next)
 838         {
 839             tr = enumerate_trail(trl->this, parent, child);
 840             push(tr, &enumTrails);
 841         }
 842
 843         /* Combine to form the complete enumeration list. */
 844         enumTrails = (trlist *)append_list(enumTrails, collectedTrails);
 845
 846         pushnew(parent, &tilesTouched);         pushnew(child, &tilesTouched);
 847     }
 848
 849     /* Validate these trails, deleting the bad ones, and inserting the
 850        good ones. (Items 3 & 4)  */
 851     for (trl = enumTrails; trl != NULL; trl = trl->next)
 852     {
 853         tr = trl->this;
 854         if (valid_trail_p(tr) == TRUE)
 855         {
 856             tr->cost = trail_cost(tr);
 857             add_trail_copy(tr);
 858         }
 859         else
 860         {
 861             delete_trail(tr);
 862         }
 863     }
 864
 865     /* finally, (5) Cleanup the list pointers... */
 866     free_list(enumTrails);
 867     free_list(tilesTouched);
 868 }
 869
 870 /*------------------------------------------------------------------------------------*/
 871 /*------------------------------------------------------------------------------------*/
 872
 873 void manage_arc_for_new_tile(new)
 874     tile *new;
 875 {       /* This tile was just created... */
 876     asg_arc *q = create_arc(new, currentPage, TRUE);
 877 }
 878
 879 /*------------------------------------------------------------------------------------*/
 880
 881 void manage_arc_for_dead_tile(old)
 882     tile *old;
 883 {       /* This tile is about to go away... */
 884     /* Check to see that it is not something important like a root tile... */
 885     asg_arc *a = (asg_arc *)old->this;
 886
 887     if(routingRoot[a->page][currentPage] == old)
 888     {
 889         if (old->rt != NULL) routingRoot[a->page][currentPage] = old->rt;
 890         else if (old->tr != NULL) routingRoot[a->page][currentPage] = old->tr;
 891         else if (old->lb != NULL) routingRoot[a->page][currentPage] = old->lb;
 892         else if (old->bl != NULL) routingRoot[a->page][currentPage] = old->bl;
 893         else
 894         {
 895             fprintf(stderr, "dying tile about to blow away rootTile[%d][%d]...\n",
 896                     a->page, currentPage);
 897         }
 898     }
 899     /* Trash everything in the arc: */
 900     delete_arc(a);
 901 }
 902
 903 /*------------------------------------------------------------------------------------*/
 904
 905 void manage_arc_for_copied_tile(child, parent)
 906     tile *child, *parent;
 907 {
 908     /* <new>->this points to the arc for the tile this was copied from, so be careful */
 909     asg_arc *cArc, *pArc = (asg_arc *)parent->this, *oldArc = (asg_arc *)child->this;
 910     tile *oldTile = oldArc->t;
 911     trlist *q;
 912
 913     cArc = create_arc(child, currentPage, FALSE);
 914     cArc->local = oldArc->local;
 915     cArc->count = oldArc->count;
 916     distribute_corner_list(oldArc, cArc);
 917     distribute_corner_list(pArc, cArc);
 918
 919     /* To handle the trails, probably need to assume that the corner stitches for
 920        <top> and <bottom> are correct, which is not a safe assumption, I THINK.
 921        This could be a very critical problem. */
 922
 923         q = manage_trails_for_split(oldArc, cArc, FALSE);
 924
 925     if ((debug_level == 4) && (q != NULL))
 926     {
 927         fprintf(stderr, "\narc for tiles [%x] ", child);
 928         dump_tile(child);
 929         fprintf(stderr, " & [%x] ", oldTile);
 930         dump_tile(oldTile);
 931         fprintf(stderr," contains %d trails: \n", list_length(q));
 932         dump_trails(q);
 933     }
 934 }
 935
 936 /*------------------------------------------------------------------------------------*/
 937
 938 void manage_arc_for_clipped_tile(copy)
 939     tile *copy;
 940 {
 941     /* This tile has been modified, and is now stable.  Correct the contents to
 942        reflect this change.  */
 943     asg_arc *qArc = (asg_arc *)copy->this;
 944     trlist *q;
 945
 946     distribute_corner_list(qArc, NULL);
 947     q = manage_trails_for_split(qArc, NULL, TRUE);
 948     if ((debug_level == 4) && (q != NULL))
 949     {
 950         fprintf(stderr, "arc for tile [%x] ", copy);
 951         dump_tile(copy);
 952         fprintf(stderr, " contains %d trails: \n", list_length(q));
 953         dump_trails(q);
 954     }
 955 }
 956
 957 /*------------------------------------------------------------------------------------*/
 958
 959 void insert_contents_for_arc(t, m)
 960     tile *t;
 961     module *m;
 962 {
 963     /* Given the tile <t> that is part of the modified tile space, insert <m> into
 964        the arc structure, and return said structure;
 965        */
 966     asg_arc *a = (arc *)t->this;
 967     a->mod = m;
 968 }
 969
 970 /*------------------------------------------------------------------------------------*/
 971
 972 add_modules(ml, p)
 973     mlist *ml;          /* List of modules being added */
 974     int p;              /* the page being dealt with */
 975 {
 976     /* Designed for use on modified tile spaces. */
 977     /* This function inserts each listed tile a->trails[index]
 978        into the tile space containing routingRoot[HORZ][p]. */
 979     /* The tile is also inserted into the vertically-oriented space by reversing
 980        the x,y ordering and inserting into the space containing tile
 981        routingRoot[VERT][p].
 982
 983        These two globals must be used, as they can be changed as modifications occur
 984        within the tile spaces during the calls to "insert_tile." */
 985
 986     mlist *mll;
 987     asg_arc * a, *temp;
 988     tile *t;
 989     int xPos, yPos, xLen, yLen;
 990
 991     /* Setup all of the specialized functions for handling complex colors in
 992        the tile space: */
 993     /* See "cstitch.h" and "cstitch.c" for the specs and usage of thes functions. */
 994     manage_contents__hmerge = manage_arc_during_hmerge;
 995     manage_contents__vmerge = manage_arc_during_vmerge;
 996     manage_contents__hsplit = manage_arc_during_hsplit;
 997     manage_contents__vsplit = manage_arc_during_vsplit;
 998     manage_contents__dead_tile = manage_arc_for_dead_tile;
 999
1000     solidp = solidp_for_arcs;
1001     contents_equivalentp = contents_equivalentp_for_arcs;
1002     insert_contents = insert_contents_for_arc;
1003
1004     for (mll = ml; mll != NULL; mll = mll->next)
1005     {
1006         if (debug_level == 4)
1007         {
1008             fprintf(stderr, "module %s being added to the Horizontal Page:\n",
1009                     mll->this->name);
1010         }
1011
1012         currentPage = HORZ;
1013         /* Include a buffer around the modules for the terminals */
1014         assign_tile_dimensions(mll->this, &xPos, &yPos, &xLen, &yLen);
1015
1016         t = insert_tile(routingRoot[HORZ][p], xPos, yPos, xLen, yLen, mll->this);
1017         mll->this->htile = t;                   /* save the horiz tile pointer
1018                                                    for cross-reference */
1019         if (t == NULL)
1020         {
1021             fprintf(stderr, "ERROR: %s module %s did not insert into horz tilespace\n",
1022                     mll->this->type, mll->this->name, mll->this);
1023             exit(-1);
1024         }
1025         if (debug_level == 4)
1026         {
1027             fprintf(stderr, "inserted @ %x...", t);
1028             dump_tile(t);
1029             fprintf(stderr, "\nmodule <%s> being added to the Vertical Page:\n",
1030                     mll->this->name);
1031         }
1032
1033         currentPage = VERT;
1034         t = insert_tile(routingRoot[VERT][p], yPos, xPos, yLen, xLen, mll->this);
1035         mll->this->vtile = t;                   /* save the vert tile pointer for
1036                                                    cross-reference */
1037         if (t == NULL)
1038         {
1039             fprintf(stderr, "ERROR: %s module %s did not insert into vert tilespace\n",
1040                     mll->this->type, mll->this->name, mll->this);
1041             exit(-1);
1042         }
1043
1044         mll->this->placed = FALSE;      /* Reuse of flag, now used for printing */
1045         if (debug_level == 4)
1046         {
1047             fprintf(stderr, "inserted @ %x...", t);
1048             dump_tile(t);
1049             fprintf(stderr,"\n");
1050         }
1051     }
1052 }       /* No error checking */
1053
1054 /*-------------------------------------------------------------------------------------*/
1055
1056 reform_tile_space(Tlist, page)
1057     tilist *Tlist;
1058     int page;           /* orientation of the tile-space */
1059 {
1060     /* Reform the tile space such that the tile contents point to arcs, and the
1061        arc->t slots point to the original tile contents (either NULL or a Module
1062        pointer). */
1063
1064     tilist *tl;
1065     asg_arc *tarc;
1066
1067     for (tl = Tlist; tl != NULL; tl = tl->next)
1068     {
1069         /* Save the module pointer from the communist (unreformed) tile */
1070         tarc = create_arc(tl->this, page, TRUE);
1071     }
1072 }
1073
1074 /*-------------------------------------------------------------------------------------*/
1075 /*-------------------------------------------------------------------------------------*/
1076
1077 int not_source_p(ex)
1078     expn *ex;
1079 {
1080     /* Return TRUE if the given expansion is associated with a source terminal */
1081     if (ex->t->type == IN) return(TRUE);
1082     else return(FALSE);
1083 }
1084
1085 /*------------------------------------------------------------------------*/
1086
1087 int identity(exp1, exp2)
1088     expn *exp1, *exp2;
1089 {
1090     return ((int)exp1 == (int)exp2);
1091 }
1092
1093 /*---------------------------------------------------------------------------------*/
1094 /* TRAIL MANIPULATION FUNCTIONS -                                                  */
1095 /*---------------------------------------------------------------------------------*/
1096
1097 /*------- Manage the Hash table in the expn structure: ----------------------------*/
1098
1099 unsigned hashE(tr)
1100     trail *tr;
1101 {
1102     /* Given a trail, hash your way to it */
1103
1104     unsigned hashval = (unsigned)(((int)tr->ex + ((int)tr->ex % 3)) % HASH_SIZE);
1105
1106     return (hashval);
1107 }
1108
1109 /*------------------------------------------------------------------------------------*/
1110
1111 trailist *lookup_trailE(tr, ex)
1112     trail *tr;
1113     expn *ex;
1114 {
1115     /* This function returns a pointer to the trailist structure where the given
1116        trail <tr>  should be stored. */
1117     trailist *trl =      ex->queue[ hashE(tr) ];
1118
1119     if (find_indexed_element(tr->cost, trl) != NULL) return(trl);
1120     else return(NULL);
1121 }
1122
1123 /*------------------------------------------------------------------------------------*/
1124
1125 int note_tiles_added(trailToCheck, ex)
1126     trail *trailToCheck;
1127     expn *ex;
1128 {
1129     /* This is to maintain the ->seen list in <ex> */
1130
1131     tile *lastTileAdded;        /* Used to check if an addition has been made... */
1132     tilist *tilesToCheck = trailToCheck->tr;
1133     tilist *tl;
1134
1135     if (trailToCheck->ex == ex)
1136     {
1137         for (tl = tilesToCheck; tl != NULL; tl = tl->next)
1138         {
1139             pushnew(tl->this, &ex->seen);
1140             lastTileAdded = ex->seen->this;
1141             if (tl->this != lastTileAdded) /* If this tile has been 'seen'already,     */
1142             {                              /* assume the rest of the tiles on the list */
1143                 break;                     /* have been as well. .   This works on the */
1144             }                              /* assumtion that the last tile in the list */
1145         }                                  /* is a source tile for <ex>.               */
1146     }
1147     else                                   /* Otherwise, who knows?  Check 'em all...  */
1148     {
1149         for (tl = tilesToCheck; tl != NULL; tl = tl->next) pushnew(tl->this, &ex->seen);
1150     }
1151 }
1152
1153 /*------------------------------------------------------------------------------------*/
1154
1155 int insert_trailE(tr, ex)
1156     trail *tr;
1157     expn *ex;
1158 {
1159     /* This installs <tr> into the hashtable in <ex> */
1160     int q, hashval = hashE(tr);
1161
1162     if ((ex->queue[ hashval ] != NULL) &&
1163         (ex->queue[ hashval ]->this->cost == tr->cost))
1164     {
1165         /* Deal with the race condition: */
1166         if (break_cost_tie(ex->queue[hashval]->this, tr) == TRUE) tr->cost += 1;
1167         else ex->queue[hashval]->this->cost += 1;
1168     }
1169     q = ordered_ilist_insert(tr, tr->cost, &ex->queue[ hashE(tr) ]);
1170
1171     note_tiles_added(tr, ex);                   /* Record that this tile has been seen */
1172     return(q);
1173 }
1174
1175 /*------------------------------------------------------------------------------------*/
1176
1177 trailist *remove_trailE(tr, ex)
1178     trail *tr;
1179     expn *ex;
1180 {
1181     /* This removes the given trail from the hash table in <ex>. */
1182     int index = hashE(tr);
1183     expn *tempEx;
1184     expnlist *exl, *newSibList, *oldSibList = NULL;
1185     trlist *trl, *newConnList;
1186     trail *q = (trail *)irem_item(tr, &ex->queue[index], NULL);
1187
1188     /* Maintain the ->siblings and ->connections lists: */
1189     for (trl = ex->connections; trl != NULL; trl = trl->next)
1190     {
1191         if (trl->this == tr)
1192         {
1193             rem_item(tr, &ex->connections);
1194             rem_item(ex, &ex->siblings);
1195             newSibList = ex->siblings;
1196             newConnList = ex->connections;
1197             push(ex, &oldSibList);
1198
1199             for (exl = newSibList; exl != NULL; exl = exl->next)
1200             {
1201                 exl->this->siblings = newSibList;              /* may not have changed */
1202                 exl->this->connections = newConnList;
1203             }
1204             ex->siblings = oldSibList;
1205         }
1206     }
1207     return(ex->queue[index]);
1208 }
1209
1210 /*------------------------------------------------------------------------------------*/
1211
1212 trail *best_trailE(ex)
1213     expn *ex;
1214 {
1215     /* This pops the best trail off of the hash table in <ex>: */
1216     int i, bestIndex = FALSE;
1217     int bestVal = FALSE;
1218     for (i=0; i<HASH_SIZE; i++)
1219     {
1220         if ((ex->queue[i] != NULL) &&
1221             ((bestVal == FALSE) || (ex->queue[i]->index <= bestVal)))
1222         {
1223             bestIndex = i;
1224             bestVal = ex->queue[i]->index;
1225         }
1226     }
1227     if (bestIndex == FALSE) return(NULL);
1228     else return((trail *)ipop(&ex->queue[bestIndex]));
1229 }
1230
1231 /*------------------------------------------------------------------------------------*/
1232
1233 trail *examine_best_trailE(ex)
1234     expn *ex;
1235 {
1236     /* simply returns the pointer to the best_trail for examination */
1237     int i, bestIndex = FALSE;
1238     int bestVal = FALSE;
1239
1240     for (i=0; i<HASH_SIZE; i++)
1241     {
1242         if ((ex->queue[i] != NULL) &&
1243             ((bestVal == FALSE) || (ex->queue[i]->this->cost <= bestVal)))
1244         {
1245             bestIndex = i;
1246             bestVal = ex->queue[i]->this->cost;
1247         }
1248     }
1249     if (bestIndex == FALSE) return(NULL);
1250     else return((trail *)(ex->queue[bestIndex]->this));
1251 }
1252
1253 /*------------------------------------------------------------------------------------*/
1254
1255 void pull_trail_from_all_arcs(t)
1256     trail *t;
1257 {
1258     /* Nuke the little commie: */
1259     tilist *tl;
1260     for (tl = t->tr; tl != NULL; tl = tl->next)
1261     {
1262         remove_trailA(t, (asg_arc *)tl->this->this);   /* Pull from arc hash table */
1263     }
1264     free_list(t->used);
1265 }
1266
1267 /*------------------------------------------------------------------------------------*/
1268
1269 void delete_trail(t)
1270     trail *t;
1271 {
1272     /* Nuke the little commie: */
1273     pull_trail_from_all_arcs(t);                /* Pull from arc hash tables */
1274     remove_trailE(t, t->ex);                    /* Pull from expn hash table */
1275     my_free(t);
1276 }
1277
1278 /*------------------------------------------------------------------------------------*/
1279 /*------------------------------------------------------------------------------------*/
1280
1281 trail *remove_trail(t)
1282     trail *t;
1283 {
1284     /* Pull the little commie out for interrogation: */
1285     expn *ex = t->ex;
1286     tilist *tl;
1287
1288     for (tl = t->tr; tl != NULL; tl = tl->next)
1289     {
1290         remove_trailA(t, (asg_arc *)tl->this->this);   /* Pull from arc hash table */
1291     }
1292     remove_trailE(t, ex);                          /* Pull from expn hash table*/
1293
1294     return(t);
1295 }
1296
1297 /*------------------------------------------------------------------------------------*/
1298
1299 void replace_trail(tOld, tNew)
1300     trail *tOld, *tNew;
1301 {
1302     /* Nuke the little commie: */
1303     expn *ex = tOld->ex;
1304     tilist *tl;
1305
1306     for (tl = tOld->tr; tl != NULL; tl = tl->next)
1307     {
1308         remove_trailA(tOld, (asg_arc *)tl->this->this);   /* Pull from arc hash table */
1309         insert_trailA(tNew, (asg_arc *)tl->this->this);
1310     }
1311     remove_trailE(tOld, ex);                       /* Pull from expn hash table*/
1312     insert_trailE(tNew, ex);
1313     if (tOld != tNew)
1314     {
1315         free_list(tOld->used);
1316         my_free(tOld);
1317     }
1318 }
1319
1320 /*------------------------------------------------------------------------------------*/
1321
1322 void add_trail_copy(copy)
1323     trail *copy;
1324 {
1325     /* add <copy> where ever it belongs */
1326     expn *ex = copy->ex;
1327     asg_arc *a;
1328     tilist *tl;
1329
1330     for (tl = copy->tr; tl != NULL; tl = tl->next)
1331     {
1332         a = (asg_arc *)tl->this->this;
1333         insert_trailA(copy, a);
1334         pushnew(copy->ex->n, &a->nets);
1335     }
1336     insert_trailE(copy, ex);
1337 }
1338
1339 /*------------------------------------------------------------------------------------*/
1340
1341 void kill_hashE(ex)
1342     expn *ex;
1343 {
1344     /* This goes through all of the trails listed in ex->queue[] and
1345        deletes them, destroying the table. */
1346     int i;
1347     trail *t;
1348     trailist *trash, *temp, *trl;
1349
1350     for (i=0; i<HASH_SIZE; i++)
1351     {
1352         trl = ex->queue[i];
1353         while (trl != NULL)
1354         {
1355             temp = trl->next;
1356             t = trl->this;
1357             delete_trail(t);
1358             trl = temp;
1359         }
1360         ex->queue[i] = (trailist *)free_ilist(ex->queue[i]);
1361     }
1362 }
1363
1364 /*------------------------------------------------------------------------------------*/
1365
1366 void rehashE(ex)
1367     expn *ex;
1368 {
1369     /* This goes through all of the trails listed in ex->queue[] and
1370        recomputes the costs, reordering the table. */
1371     int i;
1372     trail *t;
1373     trailist *temp, *trash, *trl;
1374
1375     ex->seen = (tilist *)free_list(ex->seen);   /* necessary for yanking dead tiles */
1376
1377     for (i=0; i<HASH_SIZE; i++)
1378     {
1379         temp = NULL;
1380
1381         for (trl = ex->queue[i]; trl != NULL; trl = trl->next)
1382         {
1383             t = trl->this;
1384             if (valid_trail_p(t) == TRUE)
1385             {
1386                 t->cost = trail_cost(t);
1387                 ordered_ilist_insert(t, t->cost, &temp);
1388                 note_tiles_added(t, ex);
1389             }
1390             else
1391             {
1392                 delete_trail(t);
1393             }
1394         }
1395
1396         trash = ex->queue[i];
1397         ex->queue[i] = temp;
1398         free_ilist(trash);
1399     }
1400 }
1401
1402 /*------- Manage the Hash table in the arc structure: ----------------------------*/
1403
1404 unsigned hashA(ex)
1405     expn *ex;
1406 {
1407     /* Given an expansion, hash your way to it */
1408     unsigned hashval = (unsigned)(((int)ex + ((int)ex % 5)) % HASH_SIZE);
1409
1410     return (hashval);
1411 }
1412
1413 /*------------------------------------------------------------------------------------*/
1414
1415 trailist *lookup_trailA(tr, a)
1416     trail *tr;
1417     asg_arc *a;
1418 {
1419     /* This function returns a pointer to the trailist structure where the given
1420        trail <a>  should be stored. */
1421     int index = hashA(tr->ex);
1422     if (find_indexed_element(tr->cost, a->trails[index]) != NULL)
1423         return(a->trails[index]);
1424     else return(NULL);
1425 }
1426
1427 /*------------------------------------------------------------------------------------*/
1428
1429 int insert_trailA(tr, a)
1430     trail *tr;
1431     asg_arc *a;
1432 {
1433     /* This installs <tr> into the hashtable in <a> */
1434     int q = NULL, hashval = hashA(tr->ex);
1435
1436     if (valid_trail_p(tr) == TRUE)
1437     {
1438         if ((a->trails[ hashval ] != NULL) &&
1439             (a->trails[ hashval ]->this->cost == tr->cost))
1440         {
1441             /* Deal with the race condition: */
1442             if (break_cost_tie(a->trails[hashval]->this, tr) == TRUE) tr->cost += 1;
1443             else a->trails[hashval]->this->cost += 1;
1444         }
1445         q = ordered_ilist_insert(tr, tr->cost, &a->trails[ hashval ]);
1446     }
1447
1448     return(q);
1449 }
1450
1451 /*------------------------------------------------------------------------------------*/
1452
1453 trailist *remove_trailA(tr, a)
1454     trail *tr;
1455     asg_arc *a;
1456 {
1457     /* This removes the given trail from the hash table in <a>. */
1458     int index = hashA(tr->ex);
1459     trail *q = (trail *)irem_item(tr, &a->trails[index], NULL);
1460     return(a->trails[index]);
1461 }
1462
1463 /*------------------------------------------------------------------------------------*/
1464
1465 trail *best_trailA(a, ex)
1466     asg_arc *a;
1467     expn *ex;
1468 {
1469     /* This examines  the best trail in the hash table in <a>: that belongs to the
1470        given expansion <ex>.  Faked to be non-destructive.  */
1471
1472     trailist *temp = NULL;
1473     int index = hashA(ex), bestIndex = 0;
1474     trail *besTrail;
1475
1476     /* Check to make sure that <ex> did not collide with another expansion in the
1477        hash table: */
1478     besTrail = (trail *)ipop(&a->trails[index]);  /* Get the best trail on this list */
1479
1480     /* If <besTrail> belongs to this expansion <ex>, we're done;
1481         Otherwise, save this entry on <temp> and keep looking */
1482     for (; ((besTrail->ex != ex) && (a->trails[index] != NULL));
1483          besTrail = (trail *)ipop(&a->trails[index]) )
1484         ipush(besTrail, &temp);
1485
1486     /* Cleanup everything that has been pushed onto <temp>:
1487        (This should correct the destructive ipop)       */
1488     for(; temp != NULL; temp = temp->next)
1489     {
1490         /* Push everything back onto <a->trails[index]> */
1491         ordered_ilist_insert(temp->this, temp->index, &a->trails[index]);
1492     }
1493
1494     /* Achtung! wichtig! return the <besTrail> to the table: */
1495     ordered_ilist_insert(besTrail, besTrail->cost, &a->trails[index]);
1496
1497     return( (besTrail->ex == ex) ? besTrail : NULL );
1498
1499 }
1500
1501 /* This could be written better.... */
1502
1503 /*------------------------------------------------------------------------------------*/
1504 /*------------------------------------------------------------------------------------*/
1505
1506 trail *any_trailA(a)
1507     asg_arc *a;
1508 {
1509     /* This examines  the best trail in the hash table in <a>:
1510        Faked to be non-destructive.  */
1511
1512     int i;
1513     trail *nexTrail;
1514
1515     for (i=0; i<HASH_SIZE; i++)
1516     {
1517         if (a->trails[i] != NULL)
1518         {
1519             nexTrail = (trail *)ipop(&a->trails[i]);
1520             ordered_ilist_insert(nexTrail, nexTrail->cost, &a->trails[i]);
1521             return(nexTrail);
1522         }
1523     }
1524     return( NULL );
1525 }
1526
1527 /*------------------------------------------------------------------------------------*/
1528
1529 kill_hashA(a)
1530     asg_arc *a;
1531 {
1532     /* This goes through all of the trails listed in a->trails[] and
1533        deletes them, destroying the table. */
1534     int i;
1535     trail *t;
1536     trailist *temp, *trash, *trl;
1537
1538     for (i=0; i<HASH_SIZE; i++)
1539     {
1540         temp = NULL;
1541
1542         for (trl = a->trails[i]; trl != NULL; trl = trl->next)
1543         {
1544             t = trl->this;
1545             delete_trail(t);
1546         }
1547         a->trails[i] = (trailist *)free_ilist(a->trails[i]);
1548     }
1549 }
1550
1551 /*------------------------------------------------------------------------------------*/
1552
1553 void full_rehashA(a)
1554     asg_arc *a;
1555 {
1556     /* This goes through all of the trails listed in a->trails[]
1557        and recomputes the costs, reordering the table. */
1558     int i;
1559     expn *ex;
1560     trail *t;
1561     trailist *temp, *trash, *trl;
1562
1563     for (i = 0; i < HASH_SIZE; i++)
1564     {
1565         temp = NULL;
1566
1567         for (trl = a->trails[i]; trl != NULL; trl = trl->next)
1568         {
1569             t = trl->this;
1570             t->cost = trail_cost(t);
1571             ordered_ilist_insert(t, t->cost, &temp);
1572         }
1573
1574         trash = a->trails[i];
1575         a->trails[i] = temp;
1576         free_ilist(trash);
1577     }
1578 }
1579
1580 /*------------------------------------------------------------------------------------*/
1581
1582 void rehashA(a, ex)
1583     asg_arc *a;
1584     expn *ex;
1585 {
1586     /* This goes through all of the trails listed in a->trails[] that are associated
1587        with <ex> and recomputes the costs, reordering the table. */
1588     int i;
1589     trail *t;
1590     trailist *temp, *trash, *trl;
1591
1592     i = hashA(ex);
1593
1594     temp = NULL;
1595
1596     for (trl = a->trails[i]; trl != NULL; trl = trl->next)
1597     {
1598         t = trl->this;
1599
1600         t->cost = trail_cost(t);
1601         ordered_ilist_insert(t, t->cost, &temp);
1602     }
1603
1604     trash = a->trails[i];
1605     a->trails[i] = temp;
1606     free_ilist(trash);
1607 }
1608
1609 /*------------------------------------------------------------------------------------*/
1610
1611 trail *create_trail(ti, ex, p, dir)
1612     tile *ti;
1613     expn *ex;
1614     int p, dir;   /* array index to the root tile of the next page to be searched. */
1615 {
1616     /* create a tile structure from scratch : */
1617     trail *tr = (trail *)calloc(1, sizeof(trail));
1618     asg_arc *a;
1619
1620     tr->cost = 0;
1621     tr->ex = ex;
1622     tr->used = NULL;
1623     tr->tr = NULL;
1624     tr->page = p;
1625     tr->direction = dir;
1626     if (ti != NULL)
1627     {
1628         push(ti, &tr->tr);      /* Add the tile to the list maintained by the trail */
1629         pushnew(ti, &ex->seen); /* Add the tile to the list of tiles seen */
1630         a = (asg_arc *) ti->this;
1631     }
1632     /* insert_trailA(tr, a);  Don't add the trail to the initial tile just yet */
1633     /* insert_trailE(tr, ex); Don't add the trail to the expansion structure, just yet */
1634
1635     return(tr);
1636 }
1637
1638 /*------------------------------------------------------------------------------------*/
1639 /*------------------------------------------------------------------------------------*/
1640
1641 trail *create_subtrail(newTiles, ex, p, dir)
1642     tilist *newTiles;
1643     expn *ex;
1644     int p, dir;   /* array index to the root tile of the next page to be searched. */
1645 {
1646     /* create a tile structure from scratch : */
1647     trail *tr = (trail *)calloc(1, sizeof(trail));
1648     asg_arc *a;
1649     tilist *tl;
1650
1651     tr->cost = trail_cost_est(newTiles, ex, p);
1652     tr->ex = ex;
1653     tr->used = NULL;
1654     tr->tr = NULL;
1655     tr->page = p;
1656     tr->direction = dir;
1657     tr->tr = (tilist *)copy_list(newTiles);
1658
1659     /* Inform the arcs on the list of the new trail being established: */
1660     for (tl = newTiles; tl != NULL; tl = tl->next)
1661     {
1662         a = (asg_arc *)tl->this->this;
1663         insert_trailA(tr, a);
1664     }
1665
1666     /* Clean up the expansion structure: */
1667     insert_trailE(tr, ex);
1668
1669     return(tr);
1670 }
1671
1672 /*------------------------------------------------------------------------------------*/
1673
1674 trail *copy_trail(t)
1675     trail *t;
1676 {
1677     trail *new = create_trail(NULL, t->ex, t->page, t->direction);
1678
1679     new->cost = t->cost;
1680     new->tr = (tilist *)copy_list(t->tr);
1681     new->jEx = t->jEx;
1682     new->used = t->used;
1683
1684     /* Don't forget to update the expansion. (insert_trailE()....) */
1685     /* Don't forget to update the tile. (insert_trailA()....) */
1686     return(new);
1687 }
1688
1689 /*------------------------------------------------------------------------------------*/
1690
1691 trlist *remove_all_trails_from_arc(a)
1692     asg_arc *a;
1693 {
1694     /* Remove all trails from the given arc.  Compile them into a list, and return
1695        the list. */
1696
1697     trail *temp = NULL;
1698     trlist *collectedTrails = NULL;
1699
1700     do {
1701         temp = any_trailA(a);
1702         if (temp != NULL)
1703         {
1704             push(temp, &collectedTrails);
1705             remove_trail(temp);
1706         }
1707     } while (temp != NULL);
1708
1709     a->nets = (nlist *)free_list(a->nets);
1710     a->congestion = 0;
1711
1712     return(collectedTrails);
1713 }
1714
1715 /*------------------------------------------------------------------------------------*/
1716
1717 trail *add_to_trail(tr, ti)
1718     trail *tr;          /* Trail being added to */
1719     tile *ti;           /* Tile being added to the list */
1720 {
1721     /* Add this tile to the existing trail <tr>:   Does all of the book keeping for
1722        the arc/tile structures.  */
1723     asg_arc *a;
1724     tilist *tl;
1725
1726     tr->direction = toggle_direction(tr->direction);
1727     /* Since you're modifyinging the trail, the previous joint may not be valid.*/
1728     tr->jEx = NULL;   /* Done so as not to confuse the "valid_trial_p" function ????? */
1729
1730     if (ti != NULL)
1731     {
1732         push(ti, &tr->tr);   /* Add the tile to the tile list maintained by the trail */
1733         tr->cost = trail_cost(tr);
1734
1735         /* Add this trail to all of the arcs along the path... */
1736         for (tl = tr->tr; tl != NULL; tl = tl->next)
1737         {
1738             a = (asg_arc *)tl->this->this;
1739             remove_trailA(tr, a);       /* The ordering may have changed... */
1740             insert_trailA(tr, a);
1741         }
1742
1743         a = (asg_arc *)ti->this;
1744
1745         if ((debug_level == 11) && (!strcmp(net_under_study, tr->ex->n->name))
1746             && (a->local == 0))
1747         {
1748             a->local = tr->cost;
1749         }
1750     }
1751     return(tr);
1752 }
1753
1754 /*------------------------------------------------------------------------------------*/
1755
1756 void trim_trails_at(ex, ti)
1757     expn *ex;
1758     tile *ti;
1759 {
1760     /* find all trails belonging to <ex> in <ti> and clip them at <ti>.  This involves
1761        removing all tiles on the trail->tr lists that are in front of <ti>, and
1762        then recosting the whole trail.  Later, the set of trails affected needs to be
1763        checked for duplicate trails.  */
1764     asg_arc *a = (asg_arc *)ti->this;
1765     tilist *tl;
1766     trail *t;
1767     trailist *trl, *temp = NULL;
1768     trlist *trll, *trailSeen = NULL, *uniqueTrails = NULL;
1769
1770     /* get the trails belonging to <ex> that pass through <a>: */
1771     temp = (trailist *)copy_ilist(a->trails[hashA(ex)]);
1772
1773     for (trl = temp; trl != NULL; trl = trl->next)
1774     {
1775         if (trl->this->ex == ex)        /* Only look at trails belonging to <ex> */
1776         {
1777             t = trl->this;
1778             remove_trailE(t, ex);                          /* Pull from expn hash table*/
1779
1780             /* Remove all tiles from the list up to (but not including) <ti>: */
1781             for (tl = t->tr; ((tl != NULL) && (tl->this != ti));
1782                  tl = tl->next)
1783             {
1784                 remove_trailA(t, (asg_arc *)tl->this->this ); /* Pull from asg_arc hash table */
1785                 pop(&t->tr);                           /* Yank this (extraneous) tile.*/
1786             }
1787
1788             /* Now remove <ti>: */
1789             if (tl != NULL)
1790             {   /* Now remove <ti>: */
1791                 remove_trailA(t, (asg_arc *)tl->this->this );
1792                 pop(&t->tr);                    /* Yank <ti>, then reinsert later... */
1793
1794                 /* Now reconstruct the trails, adding the tile back again, and
1795                    recomputing it's cost: */
1796        /* NOTE: This will screw up a->trails[...], hence the "copy_ilist" call */
1797                 add_to_trail(t, ti);            /* Does bookeeping (costs, etc.) */
1798                 insert_trailE(t, ex);           /* Add back to expn hash table */
1799                 push(t, &trailSeen);            /* Save for posterity */
1800             }
1801         }
1802     }
1803     free_ilist(temp);
1804
1805     /* Look for, and remove duplicate trails: */
1806     for (trll  = trailSeen; trll != NULL; trll = trll->next)
1807     {
1808         t = trll->this;
1809         if (unique_trail(t, &uniqueTrails) == FALSE)
1810         {
1811             delete_trail(trll->this);
1812         }
1813     }
1814     free_list(trailSeen);
1815 }
1816
1817 /*------------------------------------------------------------------------------------*/
1818 /*------------------------------------------------------------------------------------*/
1819
1820 int opposite_side(dir)
1821     int dir;
1822 {
1823     switch(dir)
1824     {
1825         case LEFT: return(RIGHT);
1826         case UP:   return(DOWN);
1827         case RIGHT:return(LEFT);
1828         case DOWN: return(UP);
1829     }
1830     return(dir);
1831 }
1832
1833 /*------------------------------------------------------------------------------------*/
1834
1835 int toggle_direction(lastOrientation)
1836     int lastOrientation;
1837 {
1838     /* This toggles the direction that the expansion set is saught from;  That is,
1839        if the last set of expansions came from the routingRoot[HORZ][p] plane, then
1840        the next set should come from the routingRoot[VERT][p] plane & vv. */
1841
1842     if (lastOrientation == HORZ) return(VERT);
1843     else return(HORZ);
1844 }
1845
1846 /*------------------------------------------------------------------------------------*/
1847
1848 expn *create_expansion(t)
1849     term *t;
1850 {
1851     /* create an expansion node for this terminal */
1852     expn *ex = (expn *)calloc(1, sizeof(expn));
1853     int i;
1854     ex->n = t->nt;
1855     ex->t = t;
1856     ex->siblings = NULL;        ex->connections = NULL;
1857     ex->seen = NULL;
1858     for (i=0; i<HASH_SIZE; i++) ex->queue[i] = NULL;
1859     push(ex, &t->nt->expns);    /* Tie the expansion into the net structure */
1860     push(ex, &ex->siblings);
1861     return(ex);
1862 }
1863
1864 /*-----------------------------------------------------------------------------------*/
1865
1866 int length_to_next_corner(t1, t2, orgX, orgY, useOrg, x, y)
1867     tile *t1, *t2;
1868     int orgX, orgY, useOrg;
1869     int *x, *y;
1870 {
1871     /* This returns the length in <t1> up to <t2>, correctly handling the
1872        null conditions.  It's side effect is to produce the appropriate
1873        coordinates for the point of intersection between <t1> & <t2> */
1874     asg_arc *a1, *a2;
1875     int q1 = 0, q2 = 0, midpnt = 0;
1876
1877     if (t1 == NULL)
1878     {
1879         if (t2 == NULL) return (0);
1880         else
1881         {
1882             a2 = (asg_arc *)t2->this;
1883             *x = t2->x_pos + (t2->x_len / 2);
1884             *y = t2->y_pos + (t2->y_len / 2);
1885             if (useOrg == FALSE) return(t2->x_len/2);
1886             else return( (int)abs(orgX - (t2->x_pos + t2->x_len)) );
1887         }
1888     }
1889
1890     a1 = (asg_arc *)t1->this;
1891
1892     if (t2 == NULL)
1893     {
1894         *x = t1->x_pos + (t1->x_len / 2);
1895         *y = t1->y_pos + (t1->y_len / 2);
1896         if (useOrg == FALSE) return(t1->x_len/2);
1897         else return( (int)abs(orgX - (t1->x_pos + t1->x_len)) );
1898     }
1899
1900
1901     else        /* Given both tiles, determine the length of t2 that is available
1902                    after the intersection point of the two tiles. */
1903     {
1904         a2 = (asg_arc *)t2->this;
1905         if ((a1->page == VERT) && (a2->page == HORZ))
1906         {
1907             find_intersection(t1->x_pos, t1->x_pos + t1->x_len,
1908                               t2->y_pos, t2->y_pos + t2->y_len, &q1, &q2);
1909             midpnt = (q1 + q2) / 2;
1910             *y = midpnt;
1911             *x = t1->y_pos + (t1->y_len / 2);
1912             return((useOrg == FALSE) ? t1->x_len / 2 : (int) abs(orgY - midpnt));
1913         }
1914         else if ((a1->page == HORZ) && (a2->page == VERT))
1915         {
1916             find_intersection(t2->y_pos, t2->y_pos + t2->y_len,
1917                               t1->x_pos, t1->x_pos + t1->x_len, &q1, &q2);
1918             midpnt = (q1 + q2) / 2;
1919             *x = midpnt;
1920             *y = t1->y_pos + (t1->y_len / 2);
1921             return((useOrg == FALSE) ? t1->x_len / 2 : (int) abs(orgX - midpnt));
1922         }
1923         else    /* Adjacent tiles, how odd... */
1924         {
1925             *x = t2->x_pos + (t2->x_len / 2);
1926             *y = t2->y_pos + (t2->y_len / 2);
1927             if(a2->page == HORZ)
1928                 return( (useOrg == FALSE) ? (t2->y_len + t1->y_len) / 2 :
1929                                             (int)abs (orgY - *y));
1930             else return( (useOrg == FALSE) ? (t2->x_len + t1->x_len) / 2 :
1931                                              (int) abs(orgX - *x));
1932         }
1933     }
1934 }
1935
1936 /*-----------------------------------------------------------------------------------*/
1937
1938 int distance_to_go(ex, x, y, closestEx)
1939     expn *ex;
1940     int x, y;
1941     expn **closestEx;
1942 {
1943     /* Given the (x, y) position of this particular piece of <ex>, find the minimum
1944        manhattan distance to a legal terminus of <ex>.  The set of legal terminii
1945        is the terminals corresponding to the expansions that are part of <ex>->n, but
1946        are not siblings of <ex>.   */
1947
1948     expnlist *exl;
1949     term *t;
1950     int tempX, tempY, dist, minDist = FALSE;
1951
1952     for (exl = (expnlist *)ex->n->expns; exl != NULL; exl = exl->next)
1953     {
1954         if (member_p(exl->this, ex->siblings, identity) == FALSE)
1955         {
1956             t = exl->this->t;
1957             tempX = t->x_pos + t->mod->x_pos + 2 * terminal_spacer(t, X);
1958             tempY = t->y_pos + t->mod->y_pos + 2 * terminal_spacer(t, Y);
1959             dist = (int)abs(tempX - x) + (int)abs(tempY - y) +
1960                    EXPECTED_CORNERS * CORNER_COST;
1961             if ((minDist == FALSE) || (dist <= minDist))
1962             {
1963                 minDist = dist;
1964                 *closestEx = exl->this;
1965             }
1966         }
1967     }
1968
1969     if (minDist != FALSE) return ((int)(minDist * FORWARD_EST_MULTIPLIER));
1970     else return(0);                             /* Problem */
1971 }
1972
1973 /*-----------------------------------------------------------------------------------*/
1974
1975 int trail_cost(tr)
1976     trail *tr;
1977 {
1978     /* Estimate the cost to use this trail.  */
1979     int a, b, c, d;
1980     return(trail_cost_est(tr->tr, tr->ex, tr->page, &a, &b, &c, &d));
1981 }
1982
1983 /*-----------------------------------------------------------------------------------*/
1984
1985 int trail_cost_est(tiles, ex, page, trailLength, trailEst, tileCount, trailCong)
1986     tilist *tiles;
1987     expn *ex;
1988     int page, *trailLength, *trailEst, *tileCount, *trailCong;
1989
1990 {
1991     /* Estimate the cost for the given expansion to use this string of tiles.  */
1992
1993     int lookaheadEstimate, length = 0, cornerCount = 1;
1994     int congestionCost = 0;
1995     int tx, ty, cornX, cornY;
1996     term *t;
1997     asg_arc *a;
1998     expn *nearestEx = NULL;
1999     tile *termTile;
2000     tile *lasTile= (tiles != NULL) ? tiles->this : NULL;
2001     tile *curTile = ((lasTile != NULL) && (tiles->next != NULL)) ?
2002                       tiles->next->this : NULL;
2003     tile *nexTile = ((curTile != NULL) && (tiles->next->next != NULL)) ?
2004                       tiles->next->next->this : NULL;
2005     tilist *tl;
2006
2007     /* What should be be returning in this case (where something has    */
2008     /* gone badly wrong)?                                               */
2009     if (lasTile == NULL) {
2010         error("trail_cost_est: passed a NULL tile", "");
2011         return 0;
2012     }
2013
2014     /* Handle the first tile on the trail: */
2015     a = (asg_arc *)lasTile->this;
2016
2017     congestionCost = congestion_cost(a);
2018
2019     /* Set up the corner point, but ignore the length estimate (no corner to base
2020        from yet)  */
2021     length_to_next_corner(lasTile, curTile, cornX, cornY, FALSE, &cornX, &cornY);
2022
2023     /* If this is a complete trail, that is it connects to the closest expansion
2024        not in <ex>'s expansion group, then measure the distance from (<cornX>,<cornY>)
2025        to <nearestEx>'s terminal.  Otherwise, use the <lookaheadEstimate>. */
2026
2027     lookaheadEstimate = distance_to_go(ex, cornX, cornY, &nearestEx);
2028     if (nearestEx != NULL)
2029     {
2030         termTile = initial_move(nearestEx, page);
2031         if (termTile == lasTile)
2032         {
2033             tx = nearestEx->t->mod->x_pos + nearestEx->t->x_pos;
2034             ty = nearestEx->t->mod->y_pos + nearestEx->t->y_pos;
2035             length += (int)abs(cornX - tx);
2036             length += (int)abs(cornY - ty);
2037         }
2038         else length = lookaheadEstimate;
2039     }
2040
2041
2042     /* Set up to evaluate the second tile: */
2043     lasTile = curTile;
2044     curTile = nexTile;
2045     nexTile = ((nexTile != NULL) && (tiles->next->next->next != NULL)) ?
2046                 tiles->next->next->next->this : NULL;
2047
2048     /* There are three or more tiles on the trail: */
2049     for (tl = (nexTile != NULL) ? tiles->next->next->next->next : NULL;
2050          (lasTile != NULL);
2051          tl = (tl != NULL) ? tl = tl->next : NULL)
2052     {
2053         a = (asg_arc *)lasTile->this;
2054         congestionCost += congestion_cost(a);
2055         if (curTile != NULL)
2056         {
2057             length += length_to_next_corner(lasTile, curTile, cornX, cornY,
2058                                             TRUE, &cornX, &cornY);
2059             cornerCount += 1;
2060         }
2061         else
2062         {
2063             length += (int)abs(cornX - (ex->t->x_pos + ex->t->mod->x_pos));
2064             length += (int)abs(cornY - (ex->t->y_pos + ex->t->mod->y_pos));
2065         }
2066
2067         /* Set up to evaluate the next tile: */
2068         lasTile = curTile;
2069         curTile = nexTile;
2070         nexTile = (tl != NULL) ? tl->this : NULL;
2071     }
2072
2073     *trailLength = length;
2074     *trailEst = lookaheadEstimate;
2075     *tileCount = cornerCount;
2076     *trailCong = congestionCost;
2077
2078     return(length * LENGTH_WEIGHT +  cornerCount * CORNER_COST +  congestionCost );
2079 }
2080
2081 /*-------------------------------------------------------------------------------------*/
2082
2083 int break_cost_tie(tr1, tr2)
2084     trail *tr1, *tr2;
2085 {
2086     /* return TRUE iff the cost of <tr1> is preferred to that of <tr2>: */
2087
2088     int length1, length2, moveCount1, moveCount2;
2089     int forwardEst1, forwardEst2;
2090     int congestion1, congestion2, totalCost1, totalCost2;
2091
2092     if (valid_trail_p(tr1) == FALSE)
2093     {
2094         return(FALSE);
2095     }
2096     if (valid_trail_p(tr2) == FALSE)
2097     {
2098         return(TRUE);
2099     }
2100
2101     totalCost1 = trail_cost_est(tr1->tr, tr1->ex, tr1->page, &length1,
2102                                 &forwardEst1, &moveCount1, &congestion1);
2103
2104     totalCost2 = trail_cost_est(tr2->tr, tr2->ex, tr2->page, &length2,
2105                                 &forwardEst2, &moveCount2, &congestion2);
2106
2107
2108     if (totalCost1 < totalCost2) return (TRUE);
2109     else if (totalCost1 > totalCost2) return(FALSE);
2110     else
2111     {
2112         if (congestion1 < congestion2) return(TRUE);
2113         else if (congestion1 > congestion2) return(FALSE);
2114         else
2115         {
2116             if (moveCount1 < moveCount2) return(TRUE);
2117             else if (moveCount1 > moveCount2) return(FALSE);
2118             else
2119             {
2120                 if (length1 > length2) return(FALSE);
2121                 else if (length1 < length2) return(TRUE);
2122                 else
2123                 {
2124                     if (forwardEst1 < forwardEst2) return(TRUE);
2125                     else if (forwardEst1 > forwardEst2) return(FALSE);
2126                     else
2127                     {
2128                         if (tr1->jEx != NULL)return(TRUE);
2129                         else if (tr2->jEx != NULL) return(FALSE);
2130                         else return(TRUE);
2131                     }
2132                 }
2133             }
2134         }
2135     }
2136 }
2137
2138 /*------------------------------------------------------------------------------------*/
2139
2140 int lower_cost(t1, t2)
2141     trail *t1, *t2;
2142 {
2143     /* This compares the cost of <t1> & <t2>.  If <t1> is less expensive than <t2>,
2144        TRUE is returned. */
2145
2146     if (t1->cost < t2->cost) return(TRUE);
2147     else return(FALSE);
2148 }
2149
2150 /*------------------------------------------------------------------------------------*/
2151
2152 int set_congestion1(a)
2153     asg_arc *a;
2154 {
2155     /* Congestion defaults to corner count.  See `congestion_cost' */
2156     a->congestion = 0;
2157 }
2158
2159 /*------------------------------------------------------------------------------------*/
2160
2161 int set_congestion2(a)
2162     asg_arc *a;
2163 {
2164     int crossoverCount = 0, cornerCount = 0;
2165     tilist *temp = NULL, *tl;
2166     asg_arc *perpA;
2167     nlist *nl;
2168
2169     /* Count the corners in this tile: */
2170     for(nl = a->nets; nl != NULL; nl = nl->next) cornerCount++;
2171
2172     /* Examine each tile that crosses this tile... */
2173     temp = collect_tiles(a->t, routingRoot[toggle_direction(a->page)][currentPartition]);
2174     for (tl = temp; tl != NULL; tl = tl->next)
2175     {
2176         /* Count the number of nets that are in the perpendicular tile: */
2177         perpA = (asg_arc *)tl->this->this;
2178         for(nl = perpA->nets; nl != NULL; nl = nl-> next) crossoverCount++;
2179     }
2180     free_list(temp);
2181     a->congestion = cornerCount * crossoverCount + cornerCount;
2182     return (a->congestion);
2183
2184 }
2185
2186 /*------------------------------------------------------------------------------------*/
2187
2188 select_congestion_rule(congestionRule)
2189     int congestionRule;
2190 {
2191     switch(congestionRule)
2192     {
2193         case 1 : set_congestion_value = (int (*)())set_congestion1; break;
2194         case 2 : set_congestion_value = (int (*)())set_congestion2; break;
2195         default: error("select_congestion_rule - bad rule choice ", "");
2196                  break;
2197     }
2198 }
2199
2200 /*------------------------------------------------------------------------------------*/
2201
2202 int congestion_cost(a)
2203     asg_arc *a;         /* asg_arc to be used... */
2204 {
2205     /* This is an estimate of what it costs to use the given asg_arc.  This should be
2206        refined as a real rout becomes a local route... */
2207
2208     /* The cost of congestion = 2x corner count + crossover count + penalty(if any)
2209        (See `set_congestion2 this function to verify this comment) */
2210
2211     float cost, TracksAvail, TracksUsed;
2212
2213     TracksUsed = (float)list_length(a->nets);
2214     TracksAvail = (a->page == VERT) ? (float)a->hcap : (float)a->vcap;
2215
2216     cost = (TracksUsed / TracksAvail) * TRACK_WEIGHT +      /* Corner-only component */
2217            a->congestion / TracksAvail;                     /* Crossover component */
2218
2219     /* Severely penalize overusage: */
2220     if (TracksUsed >= (int)TracksAvail-1)
2221     {
2222         cost = 5 * cost + 40;
2223     }
2224     return( (int)(cost) );
2225 }
2226
2227 /*------------------------------------------------------------------------------------*/
2228 /*------------------------------------------------------------------------------------*/
2229
2230 /*-------------------------------------------------------------------------
2231  * Algorithmic stuff
2232  * given static costs built into the routing space, route all nets:
2233  *-------------------------------------------------------------------------
2234  */
2235
2236 /*------------------------------------------------------------------------*/
2237
2238 int on_same_net(exp1, exp2)
2239     expn *exp1, *exp2;
2240 {
2241     return (((int)exp1->n == (int)exp2->n) && ((int)exp1 != (int)exp2));
2242 }
2243
2244 /*------------------------------------------------------------------------*/
2245
2246 int free_to_route_in_p(t)
2247     tile *t;
2248 {
2249     /* Returns TRUE if the tile is free for routing.... */
2250     asg_arc *a = (t != NULL) ? (asg_arc *)t->this : NULL;
2251     if ((a != NULL) && (a->mod == NULL)) return(TRUE);
2252     else return(FALSE);
2253 }
2254
2255 /*------------------------------------------------------------------------------------*/
2256 /*------------------------------------------------------------------------------------*/
2257
2258 nlist *list_nets_represented(expns, temp)
2259     expnlist *expns;
2260     nlist **temp;
2261 {
2262     /* Given a list of expansions, create a list of the nets represented */
2263     expnlist *exl;
2264     for (exl = expns; exl != NULL; exl = exl->next)
2265     {
2266         pushnew(exl->this->n, temp);
2267     }
2268     return(*temp);
2269 }
2270
2271 /*------------------------------------------------------------------------------------*/
2272 /*------------------------------------------------------------------------------------*/
2273
2274 expn *locate_fellow_expansion(exlist, ex_already_found)
2275     expnlist *exlist;
2276     expn *ex_already_found;
2277 {
2278     /* Return the expansion from <exl> that is on the same net as <ex_already_found> */
2279
2280     expnlist *exl;
2281
2282     for (exl = exlist; exl != NULL; exl = exl->next)
2283     {
2284         if (on_same_net(ex_already_found, exl->this) == TRUE) return(exl->this);
2285     }
2286     return(NULL);
2287 }
2288
2289 /*------------------------------------------------------------------------------------*/
2290
2291 tilist *collect_tiles(starTile, Root)
2292     tile *starTile, *Root;
2293 {
2294     /* given an area-of-interest (AOI) based on the dimensions of <startTile>, find
2295        the list of tiles from <Root> that are contained.  It is assumed that <starTile>
2296        is not in the same tile-space as <Root>, so  the x/y values are inverted.*/
2297     tilist *temp = NULL;
2298
2299     if (debug_level == 5)
2300         fprintf(stderr, "Collecting tiles from Root tilespace 0x%x\n", Root);
2301
2302     temp = area_enumerate(Root, &temp, free_to_route_in_p,
2303                           starTile->y_pos, starTile->x_pos,
2304                           starTile->y_len,  starTile->x_len );
2305
2306     /* Added by Tim 2/5/05:  If no tiles were found, but the boundary   */
2307     /* of Root borders on the space of interest, then expand Root by    */
2308     /* one unit and try again.                                          */
2309
2310 /*
2311     if (temp == NULL) {
2312        if (debug_level == 5)
2313           fprintf(stderr, "temp = NULL in given area\n");
2314        temp = area_enumerate(Root, &temp, free_to_route_in_p,
2315                           starTile->y_pos, starTile->x_pos,
2316                           starTile->y_len + 1,  starTile->x_len + 1);
2317        if (debug_level == 5) {
2318           if (temp != NULL)
2319              fprintf(stderr, "temp = 0x%x in expanded area\n", temp);
2320           else
2321              fprintf(stderr, "temp = NULL in expanded area\n");
2322        }
2323     }
2324 */
2325
2326     /* end of test code. . . ---Tim */
2327
2328     return(temp);
2329 }
2330
2331 /*------------------------------------------------------------------------------------*/
2332
2333 trlist *list_trails_using_A(ex, A)
2334     expn *ex;
2335     asg_arc *A;
2336 {
2337     trailist *tl;
2338     trlist *temp = NULL;
2339
2340     for(tl = A->trails[hashA(ex)]; tl!= NULL; tl = tl->next)
2341     {
2342         if (tl->this->ex == ex) push(tl->this, &temp);
2343     }
2344     return(temp);
2345 }
2346
2347 /*------------------------------------------------------------------------------------*/
2348 /*------------------------------------------------------------------------------------*/
2349
2350 tilist *remove_tiles_on_circular_trail(ex, besTrail, completeList)
2351     expn *ex;                   /* Expansion (group) that is being extended */
2352     trail *besTrail;            /* Trail that got me here... */
2353     tilist **completeList;      /* What tiles are expansion candidates */
2354 {
2355     /* This function returns a list without any tiles that would create a circular
2356        trail.   */
2357
2358 /* Need to insure that the 'NewPathDominates' only applys to tiles on the 'wavefront.' */
2359
2360     tilist *tl, *copy;
2361     tile *newTile;
2362     expnlist *exl;
2363
2364
2365     copy = (tilist *)rcopy_list(*completeList);
2366
2367     for (tl = copy; tl != NULL; tl = tl->next)
2368     {
2369         newTile = tl->this;
2370         if (member_p (newTile, besTrail->tr, identity) == TRUE)         /* No duplicate tiles */
2371             rem_item(newTile, completeList);
2372
2373         else
2374         {
2375             for (exl = ex->siblings; exl != NULL; exl = exl->next)
2376             {
2377                 ex = exl->this;
2378                 if (member_p (newTile, ex->seen, identity) == TRUE)
2379                 {
2380                     /* Visited this tile before... */
2381                     rem_item(newTile, completeList);
2382                 }
2383                 /* else - <ex> hasn't visited this guy, so keep checking in the group */
2384             }
2385         }
2386     }
2387     free_list(copy);
2388     return (*completeList);
2389 }
2390
2391 /*------------------------------------------------------------------------------------*/
2392 /*------------------------------------------------------------------------------------*/
2393
2394 trail *flip_trail(t)
2395     trail *t;
2396 {
2397     trail *newTrail;
2398     trlist *trl, *temp, *newConnList = NULL;
2399     expn *ex = t->ex;
2400     expnlist *exl;
2401
2402     /* create a new trail for t->jEx:   The old one gets trashed. */
2403     newTrail = create_trail(NULL, t->jEx, t->page, VERT);
2404     newTrail->jEx = t->ex;
2405     newTrail->tr = (tilist *)rcopy_list(t->tr);
2406     newTrail->cost = trail_cost(newTrail);
2407
2408     add_trail_copy(newTrail);                           /* Add to all asg_arc hash tables */
2409     remove_trailE(newTrail, newTrail->ex);              /* Pull from expn hash table */
2410
2411     queue(newTrail, &ex->connections);  /* gs Risky Business... */
2412     pull_trail_from_all_arcs(t);        /* Perhaps it should be returned to the expn
2413                                            hash table, but then it would compete... */
2414     /* Explicity maintain the ->connections lists: */
2415     trl = ex->connections;
2416     while (trl != NULL)
2417     {
2418         temp = trl->next;
2419         if (trl->this == t)
2420         {
2421             rem_item(t, &ex->connections);
2422             newConnList = ex->connections;
2423
2424             for (exl = ex->siblings; exl != NULL; exl = exl->next)
2425             {
2426                 exl->this->connections = newConnList;
2427             }
2428         }
2429         trl = temp;
2430     }
2431     my_free(t);                       /* BOOM ! */
2432     return(newTrail);
2433 }
2434
2435 /*------------------------------------------------------------------------------------*/
2436
2437 adjust_trailset(expnToSet, expnToFlip)
2438     expn *expnToSet, *expnToFlip;
2439 {
2440     trail *newTrail = NULL;
2441     trlist *trl;
2442
2443     /* Fix the expnToFlip->connections so that <expnToSet> is represented:  To be
2444        represented, an expansion must have a single trail that contains the given
2445        expansion in the ->ex field.
2446
2447        This gets interesting, because <expnToSet> is the expansion known to be unique,
2448        ie: desirous of a trail;  The routine is designed to set up the trail for
2449        <expnToFlip>, so if <expnToFlip> has already terminated, then some existing
2450        trail needs to be 'flipped,' making it now representative of its ->jEx
2451        expansion;  This 'flip' may require other trails to be flipped, as long
2452        as the <expnToSet> winds up with a trail.
2453        */
2454
2455     /* find the <expnToSet> and do so: */
2456     for (trl=expnToFlip->connections;
2457          ((trl != NULL) && (trl->this->jEx != expnToSet)); trl=trl->next);
2458
2459     if (trl != NULL)
2460     {
2461         newTrail = flip_trail(trl->this);
2462
2463         if ((newTrail != NULL) && (newTrail->jEx != expnToFlip))
2464             adjust_trailset(newTrail->jEx, expnToFlip);
2465     }
2466 }
2467
2468 /*------------------------------------------------------------------------------------*/
2469
2470 void terminate_expansion(ex, jEx, jArc, besTrail, ActiveExpns)
2471     expn *ex, *jEx;
2472     asg_arc *jArc;
2473     trail *besTrail;
2474     expnlist **ActiveExpns;
2475 {
2476     /* Record the termination position (asg_arc) of the expansion, notify the net that
2477        the expn is done, and clip it from the <ActiveExpn> list. */
2478     int q, xAv, yAv, xPos, yPos;
2479     int startCost = besTrail->cost;
2480     net *n = ex->n;
2481     term *t;
2482     trail *sibTrail;
2483     tile *firsTile;
2484     tilist *tl, *completionList;
2485     expn *newJex = NULL, *whoStopped = NULL;
2486     expnlist *exl;
2487
2488     for (exl = ex->siblings; ((exl != NULL) && (whoStopped == NULL)); exl = exl->next)
2489     {
2490         /* Make sure somebody we care about stops  */
2491         whoStopped = (expn *)rem_item(exl->this, ActiveExpns);
2492     }
2493
2494     if (whoStopped != NULL)
2495     {
2496         push(whoStopped, &n->done);
2497         if (whoStopped != ex)           /* Indirection! */
2498         {
2499             /* The end object is to arrange that at the end of the termination process,
2500                the global route needs to consist of a set of trails where each trail
2501                represents a unique terminal.  */
2502
2503             adjust_trailset(whoStopped, ex);
2504
2505         }
2506         jEx->siblings = (expnlist *)append_list(jEx->siblings, ex->siblings);
2507
2508         /* Now create the trail that comprises the complete path from <ex> to <jEx>: */
2509         sibTrail = best_trailA(jArc, jEx);
2510         for (tl = sibTrail->tr; ((tl != NULL) && (tl->this != jArc->t)); tl = tl->next);
2511         completionList = tl;
2512         for (tl = completionList->next; tl != NULL; tl = tl->next)
2513         {
2514             add_to_trail(besTrail, tl->this);
2515         }
2516
2517         besTrail->jEx = jEx;
2518         push(besTrail, &ex->connections);
2519         jEx->connections = (trlist *)append_list(jEx->connections, ex->connections);
2520
2521         if (debug_level >= 4)
2522         {
2523             /* print out something useful... */
2524             q = list_length(ex->n->done);
2525             xAv = (jArc->t->x_pos + jArc->t->x_len)/ 2;
2526             yAv = (jArc->t->y_pos + jArc->t->y_len)/ 2;
2527             if (jArc->page == VERT)
2528             {
2529                 yAv = xAv;
2530                 xAv = (jArc->t->y_pos + jArc->t->y_len)/ 2;
2531             }
2532
2533             if (whoStopped != ex)
2534             {
2535                 fprintf(stderr,
2536       "****<%s>\t{%s %s} terminated via <%s>{%s %s} near (%d, %d)%s after %d visits\n",
2537                     whoStopped->n->name, whoStopped->t->name, whoStopped->t->mod->name,
2538                         ex->n->name, ex->t->name, ex->t->mod->name,
2539                         xAv, yAv, (jArc->page == VERT) ? "v" : "h", ex->eCount);
2540             }
2541             else
2542             {
2543                 fprintf(stderr,
2544       "****<%s>\t{%s %s} terminated near (%d, %d)%s after %d visits[%d/%d]\n",
2545                         ex->n->name, ex->t->name, ex->t->mod->name,
2546                         xAv, yAv, (jArc->page == VERT) ? "v" : "h",
2547                         ex->eCount, startCost, besTrail->cost);
2548             }
2549             fprintf(stderr, "****<%s> \t{%s %s} merged with <%s> {%s %s}\n",
2550                     ex->n->name, ex->t->name, ex->t->mod->name,
2551                     jEx->n->name, jEx->t->name, jEx->t->mod->name);
2552         }
2553
2554         if (list_length(n->done) + 1 == list_length(n->expns))
2555         {
2556             if (member_p(jEx, *ActiveExpns, identity) == TRUE)
2557             {
2558                 /* Explicitly terminate <jEx>:  */
2559                 completionList = (tilist *)rcopy_list(sibTrail->tr);
2560                 firsTile = completionList->this;
2561                 free_list(completionList);
2562                 sibTrail = create_trail(firsTile, jEx, sibTrail->page, VERT);
2563                 insert_trailA(sibTrail, sibTrail->tr->this->this);
2564                 sibTrail->jEx = jEx;    /* This is a terminated trail, so set ->jEx... */
2565                 newJex = jEx;
2566             }
2567
2568             else
2569             {
2570                 /* Need to explicitly terminiate the remaining active expansion that
2571                    <jEx> belongs to, so first find it... */
2572                 exl = (expnlist *)member(jEx, *ActiveExpns, on_same_net);
2573                 newJex = exl->this;
2574
2575                 /* Then set up a trail with only the first move on it... */
2576
2577                 t = newJex->t;
2578                 xPos = t->x_pos + t->mod->x_pos + terminal_spacer(t, X);
2579                 yPos = t->y_pos + t->mod->y_pos + terminal_spacer(t, Y);
2580
2581                 firsTile = locate_first_tile(t->side, xPos, yPos, sibTrail->page);
2582                 sibTrail = create_trail(firsTile, newJex, sibTrail->page, VERT);
2583                 sibTrail->jEx = newJex; /* This is a terminated trail, so set ->jEx... */
2584                 insert_trailA(sibTrail, sibTrail->tr->this->this);
2585             }
2586
2587             /* Wrap up the <newJx> as well: */
2588             if (firsTile == (tile *)nth(besTrail->tr, list_length(besTrail->tr)))
2589                 sibTrail->jEx = besTrail->ex;
2590             push(sibTrail, &jEx->connections);
2591             push(newJex, &n->done);
2592             rem_item(newJex, ActiveExpns);
2593
2594             if (debug_level >= 4)
2595             {
2596                 /* print out something useful... */
2597                 fprintf(stderr, "****<%s>\t{%s %s} completes the GR for <%s>.\n",
2598                         newJex->n->name, newJex->t->name, newJex->t->mod->name,
2599                         ex->n->name);
2600             }
2601         }
2602         /* Complete the merger of the two expansions: */
2603         for (exl = jEx->siblings; exl != NULL; exl = exl->next)
2604         {
2605             exl->this->connections = jEx->connections;
2606             exl->this->siblings = jEx->siblings;
2607             /* The merger changes the "distance_to_go" measure, so recalculate the
2608                trail costs */
2609             rehashE(exl->this);         /* if (newJex == NULL) rehashE(exl->this); */
2610         }
2611     }
2612 }
2613
2614 /*------------------------------------------------------------------------------------*/
2615
2616 int meets_termination_conditions_p(tr, parentEx, besTrail)
2617     trail *tr;                  /* Trail being checked */
2618     expn *parentEx;             /* Expansion that is being checked for termination */
2619     trail *besTrail;            /* Best trail so far in the given asg_arc */
2620 {
2621     if ((tr->ex->n == parentEx->n) &&         /* IF it belongs to the same net */
2622
2623         (member_p(tr->ex, parentEx->siblings,
2624                   identity) == FALSE) &&      /* AND is not part of <parent>'s
2625                                                  group */
2626
2627         ((besTrail == NULL) ||               /* AND is the best trail so far */
2628          (tr->cost < besTrail->cost) ||
2629          ((besTrail->jEx != NULL) && (tr->cost == besTrail->cost))))
2630     {
2631         return(TRUE);
2632     }
2633     else
2634     {
2635         return(FALSE);
2636     }
2637 }
2638
2639 /*------------------------------------------------------------------------------------*/
2640
2641 int check_for_AND_terminate_expn(t, expnsStillActive)
2642     trail *t;
2643     expnlist **expnsStillActive;
2644 {
2645     /*  This seasg_arches through the list of trails that have been hashed into the
2646         proposed jointArc <a>.  Within this list of trails, each is checked to see
2647         if it completes a subnet of the <parent> expansion.
2648
2649         IF it so happens that a subnet that is a <besTrail> is discovered (and can
2650         be legally terminated), it is - <expnsStillActive> is decremented, and TRUE
2651         is returned.
2652      */
2653
2654     expn *parentEx = t->ex;
2655     asg_arc *a = (asg_arc *)t->tr->this->this;            /* Proposed joint arc for <parent> */
2656     trail *besTrail = NULL, *temp;
2657     trailist *trll;
2658
2659     int i;
2660
2661     for (i=0; i<HASH_SIZE; i++)
2662     {
2663         for (trll = a->trails[i]; trll != NULL; trll = trll->next)
2664         {
2665             /* the arc lists all trails that cross it.  Find all that are on the same
2666                net, but not the same expansion.  If any are found, then this expansion
2667                may terminate.  Do it.*/
2668
2669             temp = trll->this;
2670
2671             if (meets_termination_conditions_p(temp, parentEx, besTrail) == TRUE)
2672             {
2673                 besTrail = temp;
2674             }
2675         }
2676     }
2677     if (besTrail != NULL)
2678     {
2679         terminate_expansion(parentEx, besTrail->ex, a, t, expnsStillActive);
2680         return(TRUE);
2681     }
2682     else return(FALSE);
2683 }
2684
2685 /*------------------------------------------------------------------------------------*/
2686
2687 expnlist *check_for_termination(t)
2688     trail *t;
2689 {
2690     /*  This searches through the list of trails that have been hashed into the
2691         proposed jointArc <a>.  Within this list of trails, each is checked to see
2692         if it completes a subnet of the <parent> expansion.
2693
2694         IF it so happens that a subnet that is a <besTrail> is discovered (and can
2695         be legally terminated), the pointer the expansion that caused the best terminus
2696         is returned.
2697
2698         NOTE:  There may be more than one of these.
2699      */
2700
2701     asg_arc *a;
2702
2703     if (t == NULL) {
2704         error("check_for_termination:  trail is NULL", "");
2705         return NULL;
2706     }
2707     else if (t->tr == NULL) {
2708         error("check_for_termination:  trail component tr is NULL", "");
2709         return NULL;
2710     }
2711
2712     a = (asg_arc *) t->tr->this->this;  /* Proposed joint arc for <parent> */
2713
2714     expn *parent = t->ex;
2715     expnlist *terminationCandidateList = NULL;
2716     trail *temp, *besTrail = NULL;
2717     trailist *trll;
2718
2719     int i;
2720
2721     for (i=0; i<HASH_SIZE; i++)
2722     {
2723         for (trll = a->trails[i]; trll != NULL; trll = trll->next)
2724         {
2725             /* the asg_arc lists all trails that cross it.  Find all that are on the same
2726                net, but not the same expansion.  If any are found, then this expansion
2727                may terminate. */
2728
2729             temp = trll->this;
2730
2731             if ((temp != besTrail) &&
2732                 (meets_termination_conditions_p(temp, parent, besTrail) == TRUE))
2733             {
2734                 besTrail = temp;
2735                 pushnew(temp->ex, &terminationCandidateList);
2736             }
2737         }
2738     }
2739     if (terminationCandidateList != NULL)
2740     {
2741         return(terminationCandidateList);
2742     }
2743     else return(NULL);
2744 }
2745
2746 /*------------------------------------------------------------------------------------*/
2747
2748 trail *examine_best_trail_in_expn_group(ex)
2749     expn *ex;
2750 {       /* Generalized form of "examine_best_trailE" */
2751     expnlist *exl;
2752     trail *t = NULL, *tempTrail;
2753
2754     /* Get the cell to move from-- This is the best trail for the given expansion: */
2755     for (exl = ex->siblings; exl != NULL; exl = exl->next)
2756     {
2757         /* Check <ex> and all of <ex>'s siblings for the best trail... */
2758         tempTrail = examine_best_trailE(exl->this);
2759         if ((t == NULL) ||
2760             ((tempTrail != NULL) && (tempTrail->cost <= t->cost))) t = tempTrail;
2761     }
2762     return(t);
2763 }
2764
2765 /*------------------------------------------------------------------------------------*/
2766
2767 trail *extract_best_trail_in_expn_group(ex)
2768     expn *ex;
2769 {       /* Generalized form of "best_trailE" */
2770     trail *t = NULL;
2771     t = examine_best_trail_in_expn_group(ex);
2772     remove_trailE(t, t->ex);
2773     return(t);
2774 }
2775
2776 /*------------------------------------------------------------------------------------*/
2777
2778 trail *restart_expansion(ex)
2779     expn *ex;                   /* expansion being restarted */
2780 {
2781     /* Delete all discovered trails for this expansion, and start over. */
2782
2783     static expn *lastEx;
2784     tile *ti;
2785     trail *t, *make_startup_trail();
2786     asg_arc *a;
2787
2788     if (lastEx == ex) return(NULL);
2789     else lastEx = ex;
2790
2791     kill_hashE(ex);
2792     ex->connections = NULL;                                /* Should be NULL already */
2793     ex->seen = (tilist*) free_list(ex->seen);
2794
2795     t = make_startup_trail(ex, initial_move(ex, 0), 0);
2796     if (t->tr == NULL) {
2797         error("restart_expansion: trail has NULL component", "");
2798         return NULL;    /* Something has gone wrong. . . */
2799     }
2800     a = (asg_arc *)t->tr->this->this;
2801     insert_trailA(t, a);
2802     insert_trailE(t, ex);            /* Will be the only trail in the expansion group */
2803
2804     return(t);
2805 }
2806
2807 /*------------------------------------------------------------------------------------*/
2808
2809 int make_next_best_move(ex, trailsCompleted)
2810     expn *ex;
2811     trlist **trailsCompleted;
2812 {
2813     /* make the next best move for this expansion.  This involves removing the best trail
2814      * from the priority queue, expanding from the end of that trail,  */
2815     tile *lasTile, *starTile, *nexTile;
2816     asg_arc *a;
2817     int done_count, undone_count, expnsToGo;
2818     tilist *tl, *tileSet = NULL;
2819     trail *tempTrail, *t = NULL, *trailToUse;
2820     trlist *activeTrails = NULL;
2821     expn *nextEx, *tempEx;
2822     expnlist *possibleTerminations = NULL, *secondaryTerminations, *exl;
2823
2824
2825     /* Get the cell to move from-- This is the best trail for the given expansion: */
2826     t = examine_best_trail_in_expn_group(ex);
2827
2828     if ((t == NULL) &&
2829         ((ex->connections == NULL) ||
2830          (list_length(ex->n->expns) - list_length(ex->n->done) < 2)))
2831     {
2832         t = restart_expansion(ex);
2833         if (t == NULL)
2834         {
2835             fprintf(stderr, "ERROR:  <%s> \t{%s %s} CANCELLED - no more paths!!! \n",
2836                     ex->n->name, ex->t->name, ex->t->mod->name);
2837             /* exit(1); */
2838             return -1;
2839         }
2840         else
2841         {
2842             fprintf(stderr, "WARNING: <%s> \t{%s %s} LOST - being restarted!!! \n",
2843                     ex->n->name, ex->t->name, ex->t->mod->name);
2844             /* Treat this as an error condition and abort */
2845             /* (previously, routine continued, but is in infinite loop at this point) */
2846             return -1;
2847         }
2848     }
2849
2850     else if (t != NULL)
2851     {
2852         ex = t->ex;
2853         t = extract_best_trail_in_expn_group(ex);
2854
2855         ex->eCount += 1;
2856         starTile = t->tr->this;
2857         lasTile = (t->tr->next != NULL) ? t->tr->next->this : t->tr->this;
2858         a = (asg_arc *)starTile->this;
2859
2860         /* Check to insure that this trail is not already 'Completed' : */
2861         possibleTerminations = check_for_termination(t);
2862
2863         if (possibleTerminations == NULL)
2864         {
2865             /* Continue expanding */
2866             if (debug_level == 5)
2867             fprintf(stderr, "**<%s> \t{%s %s} visiting (%d, %d)%s [%d]\n",
2868                     ex->n->name, ex->t->name, ex->t->mod->name,
2869                     (a->page == HORZ) ? lasTile->y_pos + lasTile->y_len/2 :
2870                     starTile->y_pos + starTile->y_len/2,
2871                     (a->page == HORZ) ? starTile->y_pos + starTile->y_len/2 :
2872                     lasTile->y_pos + lasTile->y_len/2,
2873                     (a->page == VERT) ? "v" : "h",
2874                     t->cost);
2875
2876             /* Collect the set of tiles that can be moved into:  */
2877             tileSet = collect_tiles(starTile, routingRoot[t->direction][t->page]);
2878             tileSet = remove_tiles_on_circular_trail(ex, t, &tileSet);
2879
2880             /* Take these tiles, and build them into trail structures that can be tracked
2881                through the system... Create a new trail for every tile on the list.  The
2882                old trail has the first element of <tileSet> added to it explicitly;  All
2883                of the other elements have copies of <t> made, and added to.  */
2884             if (tileSet != NULL)
2885             {
2886                 for (tl = tileSet->next; tl != NULL; tl = tl->next)
2887                 {
2888                     tempTrail = copy_trail(t);
2889                     add_to_trail (tempTrail, tl->this);  /* !Does bookeeping for tile str.!*/
2890                     insert_trailE(tempTrail, ex);        /* Add to expn hash table */
2891                     push(tempTrail, &activeTrails);
2892
2893                     a = (asg_arc *)tl->this->this;
2894                     if (debug_level == 5)
2895                     fprintf(stderr, "<%s> \t{%s %s} expanding to (%d, %d)%s [%d] trail==%x\n",
2896                             ex->n->name, ex->t->name, ex->t->mod->name,
2897                             (a->page == HORZ) ? starTile->y_pos + starTile->y_len/2 :
2898                             tl->this->y_pos + tl->this->y_len/2,
2899                             (a->page == HORZ) ? tl->this->y_pos + tl->this->y_len/2 :
2900                             starTile->y_pos + starTile->y_len/2,
2901                             (a->page == VERT) ? "v" : "h",
2902                             tempTrail->cost, (int)tempTrail);
2903                 }
2904
2905                 for (tl = t->tr; tl != NULL; tl = tl->next)
2906                 {
2907                     remove_trailA(t, (asg_arc *)tl->this->this );  /* Pull from arc hash table */
2908                 }
2909                 add_to_trail(t, tileSet->this);         /* Do bookeeping for tile str. */
2910                 insert_trailE(t, ex);                        /* Add to expn hash table */
2911                 push(t, &activeTrails);
2912
2913                 a = (asg_arc *)tileSet->this->this;
2914                 if (debug_level == 5)
2915                 fprintf(stderr, "<%s> \t{%s %s} expanding to (%d, %d)%s [%d] trail==%x\n",
2916                         ex->n->name, ex->t->name, ex->t->mod->name,
2917                         (a->page == HORZ) ? starTile->y_pos + starTile->y_len/2 :
2918                         tileSet->this->y_pos + tileSet->this->y_len/2,
2919                         (a->page == HORZ) ? tileSet->this->y_pos + tileSet->this->y_len/2 :
2920                         starTile->y_pos + starTile->y_len/2,
2921                         (a->page == VERT) ? "v" : "h",
2922                         t->cost, (int)t);
2923                 free_list(tileSet);
2924             }
2925
2926             else        /* Got a problem.... */
2927             {
2928                 /* Let the expansion spin;  This is an infinite loop,  which can only be
2929                    terminated by having another expansion terminate. */
2930                 /* However, this permision should only occur iff the current expansion
2931                    <ex> is NOT part of a terminated series (ie: his ->siblings field is
2932                    of length 2 or more & this trail has a valid ->jEx field).   */
2933                 if ((list_length(*trailsCompleted) > 1) && /* Not a pathological case */
2934                     (t->jEx != NULL) &&                    /* This trail has completed */
2935                     (list_length(ex->siblings) >= 2) &&    /* somewhere AND */
2936                     (list_length(ex->n->expns) -           /* There is some other expn */
2937                      list_length(ex->n->done) >= 2))       /* waiting to complete... */
2938                 {
2939                     insert_trailE(t, t->ex);        /* Add it back to the hash table so
2940                                                        others can find it... */
2941                     t->ex->eCount = FALSE;          /* Mark it */
2942                     if (debug_level == 4)
2943                     {
2944                         fprintf(stderr, "<%s> \t{%s %s} spinning on trail %x.\n",
2945                                 ex->n->name, ex->t->name, ex->t->mod->name, t);
2946                     }
2947                     /* This needs a clause to catch the completley pathological case. */
2948                 }
2949                 else
2950                 /* Since you couldn't expand this trail any more, simply delete it: */
2951                 {
2952                     delete_trail(t);
2953                 }
2954             }
2955
2956             if ((debug_level == 1) &&
2957                 (net_name_located_p(net_under_study, ex->n) == TRUE))
2958             {
2959                 a->count += 1;
2960                 a->local = t->cost;
2961             }
2962             return 0;
2963         }
2964         else /* There is at least one possbile termination */
2965         {
2966             insert_trailE(t, t->ex);     /* Add it back to the hash table so others
2967                                             can find it... */
2968
2969             for (exl = possibleTerminations; exl != NULL; exl = exl->next)
2970 /*          exl = possibleTerminations;
2971             if (exl != NULL) */
2972             {
2973                 nextEx = exl->this;
2974
2975                 if (debug_level == 5)
2976                 {
2977                     fprintf(stderr, "**<%s> \t{%s %s} may terminate w/ {%s %s} in (%d, %d)%s [%d]\n",
2978                             ex->n->name, ex->t->name, ex->t->mod->name,
2979                             nextEx->t->name, nextEx->t->mod->name,
2980                             (a->page == HORZ) ? lasTile->y_pos + lasTile->y_len/2 :
2981                             starTile->y_pos + starTile->y_len/2,
2982                             (a->page == HORZ) ? starTile->y_pos + starTile->y_len/2 :
2983                             lasTile->y_pos + lasTile->y_len/2,
2984                             (a->page == VERT) ? "v" : "h",
2985                             t->cost);
2986                 }
2987
2988                 /* Now check to see if this trail is better than the trails in <nextEx>;
2989                    If it is, then go ahead and terminate it;  Otherwise, leave it in
2990                    the hash table (to be found again, and the whole process to repeat)
2991                    until either t->cost < min-cost {all trails in <nextEx>} OR <ex>
2992                    is terminated by another expansion.  */
2993
2994                 tempTrail = examine_best_trail_in_expn_group(nextEx);
2995                 if ((tempTrail == NULL) || (tempTrail->ex->eCount == FALSE) ||
2996                     (t->cost <= tempTrail->cost))
2997                 pushnew(t, trailsCompleted);
2998                 else
2999                 {
3000                     secondaryTerminations = check_for_termination(tempTrail);
3001                     if (member_p(t->ex, secondaryTerminations, identity) == TRUE)
3002                     {
3003                         if (t->cost < tempTrail->cost) push(t, trailsCompleted);
3004                         else push(tempTrail, trailsCompleted);
3005                     }
3006                     free_list(secondaryTerminations);
3007                 }
3008             }
3009             free_list(possibleTerminations);            /* Collect Garbage */
3010
3011             return 0;
3012         }
3013     }
3014     return 0;
3015 }
3016
3017 /*------------------------------------------------------------------------------------*/
3018 /*------------------------------------------------------------------------------------*/
3019
3020 int unique_trail(t, uniqueTraiList)
3021     trail *t;
3022     trlist **uniqueTraiList;
3023 {
3024     /* Return true, and add <t> to <uniqueTraiList> iff <t> is unique from all other
3025        trails in <uniqueTraiList>.  Otherwise, return FALSE.  */
3026
3027     trlist *trl;
3028     tilist *tl, *tll;
3029     int mayBeDuplicate = FALSE;
3030
3031     for(trl = *uniqueTraiList; trl != NULL; trl = trl->next)
3032     {
3033         for(tl = trl->this->tr; tl != NULL; tl = tl->next)
3034         {
3035             for(tll = t->tr; tll != NULL; tll = tll->next)
3036             {
3037                 if (tll->this != tl->this)
3038                 {
3039                     push(t, uniqueTraiList);
3040                     tl = tll = NULL;            /* Break */
3041                 }
3042                 else mayBeDuplicate = TRUE;
3043             }
3044         }
3045         if (mayBeDuplicate == TRUE) return(FALSE);
3046     }
3047     return(TRUE);
3048 }
3049
3050 /*-------------------------------------------------------------------------------------*/
3051
3052 int terminal_spacer(t, axis)
3053     term *t;
3054     int axis;
3055 {
3056     /* This returns the margin along the given axis that should be added to the
3057        given terminal.  Typically 1 or -1. */
3058
3059     int margin = 0;
3060     if (axis == X)
3061     {
3062         if (t->side == RIGHT) margin = TERM_MARGIN;
3063         else if (t->side == LEFT) margin = -TERM_MARGIN;
3064     }
3065     else if (axis == Y)
3066     {
3067         if (t->side == UP) margin = TERM_MARGIN;
3068         else if (t->side == DOWN) margin = -TERM_MARGIN;
3069     }
3070     return (margin);
3071 }
3072
3073 /*------------------------------------------------------------------------------------*/
3074
3075 tile *locate_first_tile(side, x_pos, y_pos, page)
3076     int side, x_pos, y_pos, page;
3077 {
3078     tile *hTile = NULL;
3079
3080     if ((side == LEFT) || (side == RIGHT))      /* IN or OUT terminals... */
3081     {
3082         hTile = locate(routingRoot[HORZ][page], x_pos, y_pos);
3083         if (!hTile || (hTile->y_pos + hTile->y_len == y_pos)) {
3084             hTile = locate(hTile, x_pos, y_pos + 1);
3085         }
3086         if (!hTile) {
3087             /* Maybe type inout without being on the left or right? */
3088             hTile = locate(routingRoot[VERT][page], y_pos, x_pos);
3089         }
3090     }
3091     else        /* For inout terminals.... */
3092     {
3093         hTile = locate(routingRoot[VERT][page], y_pos, x_pos);
3094     }
3095
3096     return(hTile);
3097 }
3098
3099 /*------------------------------------------------------------------------------------*/
3100
3101 tile *initial_move(ex, page)
3102     expn *ex;
3103     int page;
3104 {
3105     /* Return the horizontal Tile in which to start a move */
3106     /* This takes an expansion and moves it into the htile that the terminal
3107        must be routed through.  NOTE:  All first moves occur in the hspace.    This
3108        may be incorrect;  If a terminal starts on the UP/DOWN side, perhaps they
3109        should start in the vspace.      */
3110     term *t = ex->t;
3111     module *m = t->mod;
3112
3113     int x_pos = t->x_pos + m->x_pos + terminal_spacer(t, X);
3114     int y_pos = t->y_pos + m->y_pos + terminal_spacer(t, Y);
3115     tile *hTile = locate_first_tile(t->side, x_pos, y_pos, page);
3116
3117     return(hTile);
3118 }
3119
3120 /*------------------------------------------------------------------------------------*/
3121
3122 trail *make_startup_trail(ex, starTile, page)
3123     expn *ex;
3124     tile *starTile;
3125     int page;
3126 {
3127     trail *tr;
3128
3129     if ((ex->t->side == LEFT) || (ex->t->side == RIGHT))    /* IN or OUT terminals... */
3130     {
3131         tr = create_trail(starTile, ex, page, VERT);
3132     }
3133     else        /* For INOUT terminals.... */
3134     {
3135         tr = create_trail(starTile, ex, page, HORZ);
3136     }
3137
3138     tr->cost = trail_cost(tr);
3139
3140     return(tr);
3141 }
3142
3143 /*------------------------------------------------------------------------------------*/
3144
3145 trail *old_make_first_move(ex, page)
3146     expn *ex;
3147     int page;
3148 {
3149     /* This takes an expansion and moves it into the htile that the terminal
3150        must be routed through.  NOTE:  All first moves occur in the hspace.    This
3151        may be incorrect;  If a terminal starts on the UP/DOWN side, perhaps they
3152        should start in the vspace.      */
3153     term *t = ex->t;
3154     module *m = t->mod;
3155
3156     int x_pos = t->x_pos + m->x_pos + terminal_spacer(t, X);
3157     int y_pos = t->y_pos + m->y_pos + terminal_spacer(t, Y);
3158     tile *hTile = locate_first_tile(t->side, x_pos, y_pos, page);
3159     trail *tr;
3160
3161     if ((t->side == LEFT) || (t->side == RIGHT))        /* IN or OUT terminals... */
3162     {
3163         tr = create_trail(hTile, ex, page, VERT);
3164     }
3165     else        /* For inout terminals.... */
3166     {
3167         tr = create_trail(hTile, ex, page, HORZ);
3168     }
3169
3170     tr->cost = trail_cost(tr);
3171
3172     return(tr);
3173 }
3174
3175 /*------------------------------------------------------------------------------------*/
3176
3177 expn *make_first_moves(ActiveExpns, AllExpns, p)
3178     expnlist **ActiveExpns;     /* source list for active expansions */
3179     expnlist *AllExpns;
3180     int p;              /* partition being worked on */
3181 {
3182     expnlist *exl;
3183     expn *ex;
3184     tile *ti;
3185     trail *t;
3186     asg_arc *a;
3187
3188     /* make the first (required) moves for this set of expansions.  */
3189     for (exl = AllExpns; exl != NULL; exl = exl->next)
3190     {
3191         ex = exl->this;
3192         ex->eCount += 1;                /* Keep Statistics */
3193
3194         t = make_startup_trail(ex, initial_move(ex, p), p);
3195         if (t->tr == NULL) {
3196             error("make_first_moves: trail has NULL component", "");
3197             break;      /* Something has gone wrong. . . */
3198         }
3199         a = (asg_arc *)t->tr->this->this;
3200         insert_trailA(t, a);
3201
3202
3203         if (check_for_AND_terminate_expn(t, ActiveExpns) == FALSE)
3204         {
3205             insert_trailE(t, ex);
3206         }
3207
3208         if ((debug_level == 1) &&
3209             (net_name_located_p(net_under_study, ex->n) == TRUE))
3210         {
3211             a->count += 1;
3212         }
3213     }
3214 }
3215
3216 /*------------------------------------------------------------------------------------*/
3217
3218 int trail_cost_order(t1, t2)
3219     trail *t1, *t2;
3220 {
3221     if (t1 == NULL) return(FALSE);              /* Not good... */
3222     else if (t2 == NULL) return(TRUE);          /* Not good... */
3223     else if (t1->cost <=  t2->cost) return(TRUE);
3224     else return(FALSE);
3225 }
3226
3227 /*------------------------------------------------------------------------------------*/
3228
3229 int in_trailCost_order(e1, e2)
3230     expn *e1, *e2;
3231 {
3232     trail *t1 = examine_best_trail_in_expn_group(e1);
3233     trail *t2 = examine_best_trail_in_expn_group(e2);
3234
3235     if (t1 == NULL) return(FALSE);              /* Not good... */
3236     else if (t2 == NULL) return(TRUE);          /* Not good... */
3237     else if (t1->cost <=  t2->cost) return(TRUE);
3238     else return(FALSE);
3239 }
3240
3241 /*------------------------------------------------------------------------------------*/
3242
3243 int move_expns(expnsToMove)
3244     expnlist **expnsToMove;
3245 {
3246     /* this function performs a breadth-first Lee-type weighted, multi-source maze
3247        route to arrange the given <nets> within the routing space.  <expns> is a
3248        list of source terminals/expansions, such that there is one terminal/expansion
3249        listed per net. */
3250
3251     /* As this may well be operating on a partial schematic, only those terminals
3252        listed are acted upon; In this same way, expansion information is maintained,
3253        even as sections of the route are completed, and ranges are placed in the
3254        appropriate arcs(tiles).  */
3255
3256     expn *jEx;
3257     expnlist *exl, *etemp, *terminationCandidates;
3258     trail *t, *temp;
3259     trlist *trl, *ttemp, *trailsCompleted = NULL;
3260
3261     while(*expnsToMove != NULL)
3262     {
3263         /* have all expansions (there is one for every terminal) made the least-expensive
3264            (upward?) expansions:
3265            - Do not enter an area to which this terminal has already expanded.   */
3266
3267         /* Move all active expansion groups one step... */
3268         for (exl = (expnlist *)sort_list(*expnsToMove, in_trailCost_order);
3269              exl != NULL; exl = exl->next)
3270         {
3271             if (make_next_best_move(exl->this, &trailsCompleted) < 0) {
3272                error("move_expns:  make_next_best_move returned error condition");
3273                return -1;
3274             }
3275         }
3276
3277         /* check all expansion groups for terminations: */
3278         trl = (trlist *)sort_list(trailsCompleted, trail_cost_order);
3279         while (trl != NULL)
3280         {
3281
3282             ttemp = trl->next;
3283             t = trl->this;
3284
3285             terminationCandidates = check_for_termination(t);
3286             exl = terminationCandidates;
3287             while (exl != NULL)
3288             {
3289                 etemp = exl->next;
3290                 jEx = exl->this;/* Still to be terminated? */
3291                 if (jEx != NULL)/* Other terminations may have superceded this one... */
3292                 {
3293                     temp = examine_best_trail_in_expn_group(t->ex);
3294                     if (temp == t)
3295                     {
3296                         remove_trailE(t, t->ex);
3297                         terminate_expansion(t->ex, jEx, t->tr->this->this, t, expnsToMove);
3298                     }
3299                     free_list(terminationCandidates);
3300                     /* Break added by Tim (9/24/03);            */
3301                     /* otherwise, exl is invalid on next loop   */
3302                     /* break; */
3303                 }
3304                 else
3305                 {
3306                     jEx = jEx;          /* NOP */
3307                 }
3308                 exl = etemp;
3309             }
3310             trailsCompleted = (trlist *)free_list(trailsCompleted); /* Collect garbage */
3311             trl = ttemp;
3312         }
3313     }
3314     return 0;
3315 }
3316
3317 /*------------------------------------------------------------------------------------*/
3318
3319 int first_cut(expns, part)
3320     expnlist *expns;
3321     int part;
3322 {
3323     expnlist *exl, *ExpCopy = (expnlist *)rcopy_list(expns);
3324     /* <ExpCopy> is the list of expansions that have not terminated. Its length
3325        corresponds to <expCount>.  */
3326
3327
3328     /* Make the first set of expansions, checking them to see if there are any
3329        expansions that are immediately terminated: */
3330     make_first_moves(&ExpCopy, expns, part);
3331
3332     return move_expns(&ExpCopy);
3333 }
3334
3335 /*------------------------------------------------------------------------------------*/
3336 /*------------------------------------------------------------------------------------*/
3337
3338 asg_arc *Nth(modTlist, n)
3339     tilist *modTlist;
3340     int n;
3341 {
3342     tile *t = (tile *)nth(modTlist, n);
3343     return((asg_arc *)t->this);
3344 }
3345
3346 /*------------------------------------------------------------------------------------*/
3347
3348 int filled_p(a)
3349     asg_arc *a;
3350 {
3351     /* returns TRUE if the given asg_arc is filled */
3352     if (a->mod == NULL) return(FALSE);
3353     else return(TRUE);
3354 }
3355
3356 /*------------------------------------------------------------------------------------*/
3357
3358 void set_arc_costs(netsToSet)
3359     nlist *netsToSet;
3360 {
3361     /* This walks through the connection trails for each of the given nets,
3362        painting the tiles traversed with an estimate of their usage(congestion). */
3363
3364     expn *ex;
3365     nlist *nl;
3366     trail *bt;
3367     trlist *trl;
3368     tilist *tl;
3369     asg_arc *a;
3370
3371     for (nl = netsToSet; nl!=NULL; nl = nl->next)
3372     {
3373         ex = (expn *)nl->this->done->this;
3374         for (trl = ex->connections; trl != NULL; trl = trl->next)
3375         {
3376             bt = trl->this;
3377             for (tl = bt->tr; tl != NULL; tl = tl->next)
3378             {
3379                 /* Paint each arc with the usage - assume VERT tiles essentially have
3380                    only the vertical tracks employed, and HORZ tiles the horizontal
3381                    tracks. */
3382                 a =(asg_arc *)tl->this->this;
3383                 pushnew(nl->this, &a->nets);            /* Mark the global route used */
3384                 (*set_congestion_value)(a);
3385             }
3386         }
3387     }
3388 }
3389
3390 /*------------------------------------------------------------------------------------*/
3391
3392 return_best_trails_to_arcs(n,expnsToReroute, part)
3393     net *n;
3394     expnlist *expnsToReroute;
3395     int part;           /* Not used */
3396 {
3397     /* This returns the best trails contained in <n> to the appropriate hash tables. */
3398     asg_arc *ar;
3399     expnlist *exl, *sibList;
3400     expn *ex, *temp;
3401     trail *t;
3402     trlist *trl;
3403     tilist *tl, *affectedTiles = NULL;
3404
3405     if (n->done == NULL) return;        /* Nothing to return */
3406
3407     ex = (expn *)n->done->this;
3408
3409     /* return the 'best routes' to the expansion hash tables for the next go-round
3410        It is important to create an extra trail for to insure that all of the known
3411        (especially the implicitly-known) complete trails are available to be found.  */
3412     for (trl = ex->connections; trl != NULL; trl = trl->next)
3413     {
3414         insert_trailE(trl->this, trl->this->ex);
3415         for (tl = trl->this->tr; tl != NULL; tl = tl->next)
3416         {
3417             ar = (asg_arc *)tl->this->this;
3418             rem_item(n, &ar->nets);
3419         }
3420     }
3421     ex->connections = (trlist *)free_list(ex->connections);
3422
3423     /* Now reset all of the information in the expansion structures: */
3424     sibList = ex->siblings;
3425
3426     for (exl = sibList; exl != NULL; exl = exl->next)
3427     {
3428         ex = exl->this;
3429
3430         /* Clean up the parent net: */
3431         rem_item(ex, &n->done);
3432         ex->siblings = NULL;
3433         push(ex, &ex->siblings);
3434         ex->connections = NULL;
3435         ex->eCount = 0;              /* Start the visitation count over */
3436
3437         rehashE(ex);
3438     }
3439     free_list(sibList);
3440
3441     /* Reorder the hash tables for those arcs that have had things added back to them */
3442     for (tl = ex->seen; tl != NULL; tl = tl->next)
3443     {
3444         rehashA(tl->this->this, ex);
3445     }
3446 }
3447
3448 /*------------------------------------------------------------------------------------*/
3449
3450 reset_all_trail_costs(nets, part)
3451     nlist *nets;
3452     int part;
3453 {
3454     /* This resets the trail costs for the entire seasg_arch space. */
3455     asg_arc *ar;
3456     nlist *nl;
3457     expnlist *exl;
3458     expn *ex;
3459     trlist *trl;
3460     tilist *tl, *affectedTiles = NULL;
3461
3462     /* Reorder the hash tables for all arcs in the routing space */
3463
3464     affectedTiles = allspace(routingRoot[VERT][part], &affectedTiles);
3465     for (tl = affectedTiles; tl != NULL; tl = tl->next)
3466     {
3467         ar = (asg_arc *)tl->this->this;
3468         full_rehashA(ar);
3469     }
3470     affectedTiles = (tilist *)free_list(affectedTiles);
3471
3472     affectedTiles = allspace(routingRoot[HORZ][part], &affectedTiles);
3473     for (tl = affectedTiles; tl != NULL; tl = tl->next)
3474     {
3475         full_rehashA(tl->this->this);
3476     }
3477     affectedTiles = (tilist *)free_list(affectedTiles);
3478
3479     for (nl = nets; nl != NULL; nl = nl->next)
3480     {
3481         ex = (expn *)nl->this->done->this;
3482
3483         /* For each net, */
3484         /* Rehash the expansion tables and the current (active) trail: */
3485         for (exl = ex->siblings; exl != NULL; exl = exl->next)
3486         {
3487             rehashE(ex);
3488         }
3489
3490         /* Recost the trails in the net structure: (probably pointless, as these get
3491            added back to the arcs again later...) */
3492         for (trl = ex->connections; trl != NULL; trl = trl->next)
3493         {
3494             trl->this->cost = trail_cost(trl->this);
3495         }
3496     }
3497 }
3498
3499 /*------------------------------------------------------------------------------------*/
3500
3501 improve_route(n, part)
3502     net *n;
3503     int part;
3504 {
3505     /* This function takes the most best arcs on the net, returns them to the hash table
3506        (rips them up) and tries again after rehashing the tables.  This causes a
3507        rehash on all of the expansion tables for this net, and for all of the tiles
3508        traversed by the trails returned to an `unused' status (see `return_best_trails_
3509        to_arcs' above).  */
3510
3511     expnlist *expns_to_reroute = (expnlist *)rcopy_list(n->done);
3512
3513     /* List the expansion nodes from these affected nets: (Controls the re-route) */
3514     /* Then rip out the nets from the page :*/
3515
3516     /* Only expansions belonging to <n> will be re-routed (and hopefully improved...)*/
3517
3518     n->rflag = RIPPED;
3519
3520     return_best_trails_to_arcs(n, expns_to_reroute, part);
3521
3522     /* Reroute the expansions: (This means, continue where the routing left off...*/
3523     move_expns(&expns_to_reroute);
3524     free_list(expns_to_reroute);
3525 }
3526
3527 /*------------------------------------------------------------------------------------*/
3528
3529 allow_for_further_routing(activeNets, part)
3530     nlist *activeNets;
3531     int part;                           /* Not Used */
3532 {
3533     /* Trash all of the existing trails, then return all of the completed routes
3534        belonging to <activeNets>.  Arrange the data structures so that
3535        the insertion and routing algorithms can be rerun */
3536
3537     nlist *nl;
3538     expnlist *exl;
3539
3540     for (nl = activeNets; nl != NULL; nl = nl->next)
3541     {
3542         /* Blow away the extraneous Global Routing stuff... */
3543         for (exl = (expnlist *)nl->this->expns; exl != NULL; exl = exl->next)
3544         {
3545             kill_hashE(exl->this);              /* Blam! */
3546         }
3547
3548         /* Blow away the Local Routing stuff... */
3549         if (nl->this->done != NULL)
3550         {
3551             delete_all_corners(nl->this->route);
3552             nl->this->route = NULL;
3553         }
3554
3555         return_best_trails_to_arcs(nl->this, part);
3556         nl->this->rflag = NULL;
3557
3558         if (debug_level > 2)
3559         {
3560             fprintf(stderr,"...net<%s> reset", nl->this->name);
3561         }
3562     }
3563     if (debug_level > 2)
3564     {
3565         fprintf(stderr,"...done\n");
3566     }
3567 }
3568
3569 /*------------------------------------------------------------------------------------*/
3570 /*------------------------------------------------------------------------------------*/
3571
3572 int no_terminals(n)
3573     net *n;
3574 {
3575     /* This fuction determines if the given net has no terminals (Dummy Net) */
3576     if (n->terms == NULL) return(TRUE);
3577     else return(FALSE);
3578 }
3579
3580 /*------------------------------------------------------------------------------------*/
3581
3582 int been_rerouted(n)
3583     net *n;
3584 {
3585     /* This fuction determines if the given net has been rerouted. */
3586     return((n->rflag == RIPPED));
3587 }
3588
3589 /*------------------------------------------------------------------------------------*/
3590
3591 asg_arc *worst_arc_on_net(n)
3592     net *n;
3593 {
3594     /* This returns the most congested arc on the current route path of the given net */
3595
3596     expn *ex;
3597     asg_arc *a, *worstArc = NULL;
3598     int congestionLevel = 0;
3599     trail *besTrail;
3600     trlist *trl;
3601     tilist *tl;
3602
3603     ex = (expn *)n->expns->this;
3604     for (trl = ex->connections; trl != NULL; trl = trl->next)
3605     {
3606         /* Pick the best trail, so as to trace along it: */
3607         besTrail = trl->this;
3608
3609         /* Walk back along the trail, looking for the most congested arc: */
3610         for (tl = besTrail->tr; tl != NULL; tl = tl->next)
3611         {
3612             a = (asg_arc *)tl->this->this;
3613             if (congestion_cost(a) >= congestionLevel)
3614             {
3615                 congestionLevel = congestion_cost(a);
3616                 worstArc = a;
3617             }
3618         }
3619     }
3620     return(worstArc);
3621 }
3622
3623 /*------------------------------------------------------------------------------------*/
3624
3625 nlist *non_ripped_up_nets(nl)
3626     nlist *nl;
3627 {
3628     /* return a list of non-ripped-up nets.  (Unsorted) */
3629     nlist *nll = (nlist *)copy_list(nl);
3630     return((nlist *)delete_if(&nll, been_rerouted));
3631 }
3632
3633 /*------------------------------------------------------------------------------------*/
3634 /*------------------------------------------------------------------------------------*/
3635
3636 void ps_print_arc(f, t)
3637     FILE *f;
3638     tile *t;
3639 {
3640     /* This function prints the contents of the given arc in PostScript
3641        format to file <F>. */
3642     asg_arc *a = (arc *)t->this;
3643     int x1, x2, y1, y2, count = 0;
3644     nlist *nl;
3645     net *n;
3646     rnglist *rl;
3647
3648     float gray_level = 1.0 - (float)list_length(a->nets) /
3649                                   (2.5 * (float)list_length(nets));
3650
3651     x1 = t->x_pos;
3652     y1 = t->y_pos;
3653     x2 = x1 + t->x_len;
3654     y2 = y1 + t->y_len;
3655
3656     if (a->mod == NULL)
3657     {
3658         /* Fill in the area with gray, shaded to show the number of nets contained */
3659         fprintf(f, "newpath %d %d moveto %d %d lineto ", x1, y1, x2, y1);
3660         fprintf(f, "%d %d lineto %d %d lineto ", x2, y2, x1, y2);
3661         fprintf(f, "closepath %.3f setgray fill 0 setgray\n", gray_level);
3662
3663         y2 -= 1;                /* <y2> becomes the y pos to print at, <x1> the x pos.*/
3664         x1 += 1;
3665
3666         /* Type in the net names: */
3667         for (nl = a->nets; nl != NULL; nl = nl->next)
3668         {
3669             n = nl->this;                       /* Only print the net_under_study */
3670             if (net_name_located_p(net_under_study, n) == TRUE)
3671             {
3672                 if ((x1 + strlen(n->name)) <= x2)
3673                 {
3674                     ps_put_label(f, n->name, (float)(x1), (float)(y2));
3675                     x1 += strlen(n->name) + 2;
3676                 }
3677                 else if (y2 >= y1)
3678                 {
3679                     y2 -= 1;
3680                     x1 = t->x_pos + 1;
3681                     ps_put_label(f, n->name, (float)(x1), (float)(y2));
3682                     x1 += strlen(n->name) + 2;
3683                 }
3684             }
3685         }
3686     }
3687
3688     else        /* Print out the module icon */
3689     {
3690         ps_print_mod(f, a->mod);
3691     }
3692 }
3693
3694 /*------------------------------------------------------------------------------------*/
3695
3696 int check_terminal_p(ter, ex)
3697     expn *ex;
3698     term *ter;
3699 {
3700     if (ter == ex->t) return(TRUE);
3701     else return(FALSE);
3702 }
3703
3704 /*------------------------------------------------------------------------------------*/
3705
3706 map_terminals_into_active_expansions(ml, ActiveExpns)
3707     mlist *ml;                          /* List of modules to expand on */
3708     expnlist **ActiveExpns;
3709 {
3710     /* This takes a list of modules and digs out all of the terminals contained therein.
3711        These terminals are then mapped into the appropriate points on the appropriate
3712        edge structures.  It is expected that the list of modules being routed is given
3713
3714        Active expansions are the expansions associated with source (OUT|INOUT) terminals.
3715        Each active expansion is places on the <ActiveExpns> list for use in first_cut,
3716        etc. all inactive expansions make their first moves, and then wait to be located
3717        by the active expansions. (see first_cut, make next_best_move, etc..)    */
3718
3719     tilist *tl;         /* Dummy tile list */
3720     tlist *trl, *trll;          /* terminal list */
3721     term *ter;
3722     module *mod;        /* */
3723     mlist *mll;
3724     expn *ex;
3725     expnlist *oldExpns;
3726
3727     asg_arc *tarc, *ArcUsed;
3728
3729     for (mll = ml; mll != NULL; mll = mll->next)
3730     {
3731         /* Walk through the list of terminals in each tile... */
3732         mod = mll->this;
3733         tarc = (asg_arc *)mod->htile->this;          /* As set in 1st loop in "map_into_arcs" */
3734
3735         /* For each terminal belonging to the module, create the expansion structure
3736            associated with it, and add this structure to the list of active terminals. */
3737         for (trl = mod->terms; trl != NULL; trl = trl->next)
3738         {
3739             ter = trl->this;
3740
3741             /* Only create expansions for terminals that do not already have
3742                expansions created for them, and that have nets that can terminate
3743                (more than just one one terminal on the net) */
3744             if ((ter->nt != NULL) && (list_length(ter->nt->terms) > 1) &&
3745                     /* Not obvious... It is needed for partial routing of a schematic */
3746                 (member_p(ter, ter->nt->terms, identity) == TRUE))
3747             {
3748                 /* If you've got one piece of a good net, get all of it */
3749                 for(trll = ter->nt->terms; trll != NULL; trll = trll->next)
3750                 {
3751                     if (member_p(trll->this, *ActiveExpns, check_terminal_p)== FALSE)
3752                     {
3753                         oldExpns = (expnlist *)member(trll->this, ter->nt->expns,
3754                                                  check_terminal_p);
3755                         if ((oldExpns == NULL) &&
3756                             (trll->this->nt != NULL)) /* Skip Specialized terminals */
3757                         {
3758                             ex = create_expansion(trll->this);
3759                             /* Save all expansions as 'Active' ones: (terminals) */
3760                             push(ex, ActiveExpns);
3761                         }
3762                         /* Otherwise look for old expansions to put on the list */
3763                         else
3764                         {
3765                             pushnew(oldExpns->this, ActiveExpns);
3766                         }
3767                     }
3768                 }
3769             }
3770         }
3771     }
3772 }
3773
3774 /*------------------------------------------------------------------------------------*/
3775
3776 void set_file_and_net()
3777 {
3778     /* This prompts the user and gets a filename to which the global route and expansion
3779        details are to be dumped.   This sets the globals <df> and <net_under_study>.  */
3780
3781     strcpy(dfname, "asg_groute.info");
3782 /*
3783     fprintf(stderr, "File to dump global route info to -> ");
3784     scanf("%s", dfname);
3785 */
3786
3787    if ((df = fopen(dfname, "w")) == NULL)
3788     {
3789         fprintf(stderr,"can't open %s\n", dfname);
3790         /* exit(1); */
3791         return;
3792     }
3793     else fprintf(stderr,"%s, used for global routing dump file\n", dfname);
3794
3795     sprintf(stderr, "gnd");
3796 /*
3797     fprintf(stderr, "Please name the net being traced: ");
3798     scanf("%s", net_under_study);
3799 */
3800
3801     /* now start the dump file: */
3802     if (latex != TRUE)
3803     {
3804         ps_print_standard_header(df);
3805         fprintf(df, "\n(%s: global route trace for net %s) %d %d %d %d init\n",
3806                 getenv("USER"), net_under_study, xfloor, yfloor, x_sizes[0], y_sizes[0]);
3807     }
3808     else
3809     {
3810         ps_print_standard_header(df);
3811         fprintf(df, "swidth setlinewidth\n/Courier findfont fwidth scalefont setfont\n");
3812         fprintf(df,"%%%%BoundingBox: %d %d %d %d\n",
3813                 xfloor - CHANNEL_LENGTH, yfloor - CHANNEL_HEIGHT,
3814                 x_sizes[0] + CHANNEL_LENGTH, y_sizes[0] + CHANNEL_HEIGHT);
3815     }
3816 }
3817
3818 /*------------------------------------------------------------------------------------*/
3819 /*------------------------------------------------------------------------------------*/
3820
3821 int net_cost(n)
3822     net *n;
3823 {
3824     /* estimate the cost of the global route for this net: */
3825     expn *ex = (expn *)n->done->this;
3826     trail *besTrail;
3827     trlist *trl;
3828     int cost = 0;
3829
3830     for (trl = ex->connections; trl != NULL; trl = trl->next)
3831     {
3832         besTrail = trl->this;
3833         cost += trail_cost(besTrail);
3834     }
3835     return (cost);
3836 }
3837
3838 /*------------------------------------------------------------------------------------*/
3839
3840 int in_cost_order(n1, n2)
3841     net *n1, *n2;
3842 {
3843     /* order the two nets - the more expensive net goes to the left */
3844     if (net_cost(n1) > net_cost(n2)) return(TRUE);
3845     else return(FALSE);
3846 }
3847
3848 /*------------------------------------------------------------------------------------*/
3849
3850 void reset_net_structures(nl)
3851     nlist **nl;
3852 {
3853     /* Remove any NULL Nets from the list.*/
3854
3855     nlist *nll, *last;
3856     for (nll = *nl; nll != NULL; nll = nll->next)
3857     {
3858         if (nll->this->terms != NULL)
3859         {
3860             /* Non-Null net: */
3861             nll->this->rflag = NULL;
3862         }
3863         else rem_item(nll->this, nl);
3864     }
3865 }
3866
3867 /*------------------------------------------------------------------------------------*/
3868 /*------------------------------------------------------------------------------------*/
3869
3870 void create_routing_space(ml, p, xlen, ylen, xorg, yorg)
3871     mlist *ml;
3872     int p, xorg, yorg;
3873 {
3874     /* This function creates the data structures used for global routing on the
3875        given page <p>.  This should be called only once, and prior to the call
3876        to "first_global_route". */
3877
3878     expnlist *ActiveExpns = NULL;  /* list of all active terminals */
3879     tilist *allVSpace = NULL, *allHSpace = NULL;
3880
3881     /* See 'BoundingBox' definition in "debug.c";  <routingRoot>s are globals */
3882     routingRoot[HORZ][p] =
3883              create_tile(xlen + 2 * CHANNEL_LENGTH + 2 * TERM_MARGIN,
3884                          ylen + 2 * CHANNEL_HEIGHT + 2 * TERM_MARGIN,
3885                          NULL,
3886                          xorg - CHANNEL_LENGTH - TERM_MARGIN,
3887                          yorg - CHANNEL_LENGTH - TERM_MARGIN);
3888
3889     routingRoot[VERT][p] =
3890             create_tile(ylen + 2 * CHANNEL_HEIGHT + 2 * TERM_MARGIN,
3891                         xlen + 2 * CHANNEL_LENGTH + 2 * TERM_MARGIN,
3892                         NULL,
3893                         yorg - CHANNEL_HEIGHT - TERM_MARGIN,
3894                         xorg - CHANNEL_LENGTH - TERM_MARGIN);
3895
3896
3897     insert_all_modules(routingRoot[HORZ][p], routingRoot[VERT][p], ml);
3898
3899     /* the next stage is to create the structures that are used to control this
3900      * stage of the routing process.  */
3901     allHSpace = allspace(routingRoot[HORZ][p], &allHSpace);
3902     allVSpace = allspace(routingRoot[VERT][p], &allVSpace);
3903
3904     reform_tile_space(allHSpace, HORZ);
3905     reform_tile_space(allVSpace, VERT);
3906
3907     /* Assign the global 'solidp' function for insertions, now that the tile-space
3908        has been reformed */
3909     solidp = solidp_for_arcs;
3910
3911     reset_net_structures(&nets);
3912 }
3913
3914 /*------------------------------------------------------------------------------------*/
3915
3916 nlist *first_global_route(ml, p, onceOnly, congestionRule)
3917     mlist *ml;
3918     int p, onceOnly, congestionRule;
3919 {
3920     /* This function performs the global routing for the circuit.  This begins by
3921        evaluating where the available routing space is. */
3922
3923     /* This fn must be called at least once */
3924
3925     /* This function is meant to serve in two modes: Either for creating a completed
3926        route on a completed routing space (non-incremental-mode:<onceOnly> == FALSE),
3927        or for completing the first-pass global route for a route that will be
3928        incrementally added to. (<onceOnly> == TRUE) */
3929
3930     expnlist *expns = NULL, *exl;
3931     nlist *non_ripped = NULL, *nl, *nll, *ActiveNets = NULL;
3932     asg_arc *worstArc;
3933
3934     /* First, set the congestion evaluation function... */
3935     select_congestion_rule(congestionRule);
3936
3937     map_terminals_into_active_expansions(ml, &expns);
3938
3939     /* Collect the nets that are being dealt with: */
3940     for (exl = expns; exl != NULL; exl = exl->next)
3941     {
3942         pushnew(exl->this->n, &ActiveNets);
3943     }
3944
3945     if (debug_level == 1) set_file_and_net();
3946     else if (debug_level == 10) prepare_tile_spaces(FALSE);
3947     else if (debug_level == 11) prepare_tile_spaces(TRUE);
3948
3949     if (first_cut(expns, p) < 0) {
3950         free_list(expns);
3951         return NULL;
3952     }
3953
3954     if (onceOnly == FALSE)
3955     {
3956         reset_all_trail_costs(ActiveNets, p);
3957
3958         /* Remove any dummy terminals from the master netlist, as they can
3959            cause problems: */
3960         non_ripped = (stopAtFirstCut == TRUE) ? NULL :
3961                      (nlist *)delete_if(&ActiveNets, no_terminals);
3962
3963         if (debug_level >= 3)
3964         {
3965             for (nl = non_ripped; nl != NULL; nl = nl->next)
3966             fprintf(stderr,"cost for net <%s> is %d\n",
3967                     nl->this->name, net_cost(nl->this));
3968         }
3969         if (debug_level >= 3)
3970         {
3971             fprintf(stderr, "..............First Cut at GR Completed..............\n");
3972             fprintf(stderr, "Before Improvement...");
3973             dump_net_costs(ActiveNets);
3974         }
3975
3976         /* Iteratively improve the route until all nets have been relaid once. */
3977         for(nl = (nlist *)sort_list(non_ripped, in_cost_order);
3978             nl != NULL; nl = nl->next)
3979         {
3980             if(debug_level >= 3)
3981             {
3982                 fprintf(stderr,"\nBefore improving net <%s>:\n", nl->this->name);
3983                 exl = (expnlist *)nl->this->done;
3984                 long_dump_trails(exl->this->connections);
3985             }
3986
3987             /* worstArc = worst_arc_on_net(nl->this); */
3988             improve_route(nl->this, p);
3989             set_arc_costs(ActiveNets);
3990
3991             if (debug_level >= 3)
3992             {
3993                 fprintf(stderr, "\nAfter improving net %s:\n",
3994                         nl->this->name);
3995                 exl = (expnlist *)nl->this->done;
3996                 long_dump_trails(exl->this->connections);
3997                 dump_net_costs(ActiveNets);
3998             }
3999         }
4000     }
4001
4002     free_list(expns);
4003
4004     return(ActiveNets);
4005 }
4006
4007 /*------------------------------------------------------------------------------------*/
4008
4009 nlist *incremental_global_route(newMods, modsSoFar, oldNets, p)
4010     mlist *newMods;                     /* Modules to be added to diagram */
4011     mlist *modsSoFar;                   /* Modules to form global route for */
4012     nlist *oldNets;
4013     int p;                              /* Virtual Page No. to add them to */
4014 {
4015     /* This function performs the global routing for the circuit.  This begins by
4016        evaluating where the available routing space is. */
4017
4018     expnlist *expns = NULL, *exl;
4019     nlist *non_ripped = NULL, *nl, *ActiveNets = NULL;
4020     tlist *tl;
4021     asg_arc *worstArc;
4022
4023     allow_for_further_routing(oldNets, p);
4024
4025     add_modules(newMods, p);
4026     map_terminals_into_active_expansions(modsSoFar, &expns);
4027
4028     /* Must collect ALL nets that are to be routed. */
4029     for (exl = expns; exl != NULL; exl = exl->next)
4030     {
4031         pushnew(exl->this->n, &ActiveNets);
4032     }
4033
4034     first_cut(expns, p);
4035
4036     reset_all_trail_costs(ActiveNets, p);
4037
4038     if (debug_level >= 3) fprintf(stderr, "...First Cut at Incremental GR Completed.\n");
4039
4040     /* Remove any dummy terminals from the master netlist, as they can cause problems: */
4041     non_ripped = (stopAtFirstCut == TRUE) ? NULL :
4042                  (nlist *)delete_if(&ActiveNets, no_terminals);
4043
4044     if(debug_level >= 3)
4045     {
4046         fprintf(stderr, "Before Improvement...");
4047         dump_net_costs(ActiveNets);
4048     }
4049
4050     /* Iteratively improve the route until all nets have been relaid at least once, or
4051        no improvement is found. */
4052     for(nl = (nlist *)sort_list(non_ripped, in_cost_order);
4053         nl != NULL; nl = nl->next)
4054     {
4055         if(debug_level >= 3)
4056         {
4057             fprintf(stderr,"\nBefore improving net <%s>:\n", nl->this->name);
4058             exl = (expnlist *)nl->this->done;
4059             long_dump_trails(exl->this->connections);
4060         }
4061
4062 /*      worstArc = worst_arc_on_net(nl->this); */
4063         improve_route(nl->this, worstArc, p);
4064         set_arc_costs(ActiveNets);
4065
4066         if(debug_level >= 3)
4067         {
4068             fprintf(stderr,"\nAfter improving net <%s>:\n", nl->this->name);
4069             exl = (expnlist *)nl->this->done;
4070             long_dump_trails(exl->this->connections);
4071             dump_net_costs(ActiveNets);
4072         }
4073     }
4074
4075     free_list(oldNets);
4076     free_list(expns);
4077
4078     return(ActiveNets);
4079 }
4080
4081 /*------------------------------------------------------------------------------------*/
4082
4083 void print_global_route(f)
4084     FILE *f;
4085 {
4086     /* for date and time */
4087     long time_loc;
4088     extern long int time();
4089
4090    /* Define the bounding box for the post-script code: */
4091     fprintf(f,"%%%%BoundingBox: %d %d %d %d\n",
4092             xfloor - CHANNEL_LENGTH, yfloor - CHANNEL_HEIGHT,
4093             x_sizes[0] + CHANNEL_LENGTH, y_sizes[0] + CHANNEL_HEIGHT);
4094
4095
4096     /* now dump the result */
4097     time_loc = time(0L);
4098
4099     if (latex != TRUE) /* Not in latex mode */
4100     {
4101         ps_print_standard_header(f);
4102         fprintf(f, "\n(N2A ?? %s %s %s)\n",
4103                 getenv("USER"), ctime(&time_loc),
4104                 (stopAtFirstCut == TRUE) ? "(first cut only)" : "with rip-up");
4105
4106         fprintf(f, "(using flags-> rule #%d s:%d c:%d part:%d dir:%d)\n",
4107                 partition_rule, max_partition_size, max_partition_conn,
4108                 partition_count, matrix_type);
4109
4110         fprintf(f,"%d %d %d %d init\n", xfloor, yfloor, x_sizes[0], y_sizes[0]);
4111     }
4112     else /* This stuff replaces the init for latex mode */
4113     {
4114         ps_print_standard_header(f);
4115         fprintf(f, "swidth setlinewidth\n/Courier findfont fwidth scalefont setfont\n");
4116         fprintf(f,"%%%%BoundingBox: %d %d %d %d\n",
4117                 xfloor - CHANNEL_LENGTH, yfloor - CHANNEL_HEIGHT,
4118                 x_sizes[0] + CHANNEL_LENGTH, y_sizes[0] + CHANNEL_HEIGHT);
4119     }
4120
4121     ps_print_tile_space(routingRoot[HORZ][0], f, ps_print_arc, TRUE);
4122
4123     if (latex != TRUE) fprintf(f, "showpage\n");
4124 }
4125
4126
4127 /*---------------------------------------------------------------------------------*/
4128
4129 dump_nets(nets)
4130     nlist *nets;
4131 {
4132     nlist *nl;
4133     for(nl=nets; nl!=NULL; nl = nl->next)
4134     {
4135         fprintf(stderr, "<%s>...", nl->this->name);
4136     }
4137     fprintf(stderr, "\n");
4138 }
4139
4140 /*---------------------------------------------------------------------------------*/
4141
4142 dump_net_costs(nets)
4143     nlist *nets;
4144 {
4145     nlist *nl;
4146     for(nl=nets; nl!=NULL; nl = nl->next)
4147     {
4148         fprintf(stderr, "<%s>=%d...", nl->this->name, net_cost(nl->this));
4149     }
4150     fprintf(stderr, "\n");
4151 }
4152
4153 /*---------------------------------------------------------------------------------*/
4154
4155 dump_modules(mods)
4156     mlist *mods;
4157 {
4158     mlist *nl;
4159     for(nl=mods; nl!=NULL; nl = nl->next)
4160     {
4161         fprintf(stderr, "<%s>...", nl->this->name);
4162     }
4163     fprintf(stderr, "\n");
4164 }
4165
4166 /*---------------------------------------------------------------------------------*/
4167 /*---------------------------------------------------------------------------------*/
4168
4169 dump_tile(t)
4170     tile *t;
4171 {
4172     asg_arc *a = (asg_arc *)t->this;
4173     if (a->page == HORZ)
4174     fprintf(stderr, "(%d,%d),(%d,%d)H...",
4175             t->x_pos, t->y_pos, t->x_pos + t->x_len, t->y_pos + t->y_len);
4176     else
4177     fprintf(stderr, "(%d,%d),(%d,%d)V...",
4178             t->y_pos, t->x_pos, t->y_pos + t->y_len, t->x_pos + t->x_len);
4179 }
4180
4181 /*---------------------------------------------------------------------------------*/
4182
4183 dump_trail(t)
4184     trail *t;
4185 {
4186     tilist *temp = NULL, *tl;
4187
4188     if (t->jEx == NULL)
4189     {
4190         fprintf(stderr, "\tn<%s> t<%s>-> ", t->ex->t->nt->name, t->ex->t->mod->name);
4191     }
4192     else
4193     {
4194         fprintf(stderr, "\tn<%s> t<%s> & <%s>-> ", t->ex->t->nt->name,
4195                 t->ex->t->mod->name, t->jEx->t->mod->name);
4196     }
4197     temp = (tilist *)rcopy_list(t->tr);
4198     for (tl = temp; tl != NULL; tl = tl->next)
4199     {
4200         fprintf(stderr, "%x...", tl->this);
4201     }
4202     fprintf(stderr, "[%d]...", list_length(temp));
4203
4204     free_list(temp);
4205 }
4206
4207 /*------------------------------------------------------------------------------------*/
4208
4209 dump_tiles(tilesToSee)
4210     tilist *tilesToSee;
4211 {
4212     tilist *tl;
4213     /* Dump Tile List to the screen: */
4214     for (tl = tilesToSee; tl != NULL; tl = tl->next)
4215     {
4216         dump_tile(tl->this);
4217     }
4218     fprintf (stderr, "\n");
4219 }
4220
4221 /*---------------------------------------------------------------------------------*/
4222
4223 long_dump_trail(t)
4224     trail *t;
4225 {
4226     tilist *temp = NULL, *tl;
4227
4228     if (t->jEx == NULL)
4229     {
4230         fprintf(stderr, "\tn<%s> t<%s>-> ", t->ex->t->nt->name, t->ex->t->mod->name);
4231     }
4232     else
4233     {
4234         fprintf(stderr, "\tn<%s> t<%s> & <%s>-> ", t->ex->t->nt->name,
4235                 t->ex->t->mod->name, t->jEx->t->mod->name);
4236     }
4237     temp = (tilist *)rcopy_list(t->tr);
4238     dump_tiles(temp);
4239     fprintf(stderr, "[%d]$%d...", list_length(temp), trail_cost(t));
4240
4241     free_list(temp);
4242 }
4243
4244 /*------------------------------------------------------------------------------------*/
4245
4246 long_dump_trails(trailsToSee)
4247     trlist *trailsToSee;
4248 {
4249     trlist *trl;
4250     /* Dump Trail List to the screen: */
4251     for (trl = trailsToSee; trl != NULL; trl = trl->next)
4252     {
4253         long_dump_trail(trl->this);
4254         fprintf (stderr, "\n");
4255     }
4256     fprintf (stderr, "\n");
4257 }
4258
4259 /*------------------------------------------------------------------------------------*/
4260
4261 dump_trails(trailsToSee)
4262     trlist *trailsToSee;
4263 {
4264     trlist *trl;
4265     /* Dump Trail List to the screen: */
4266     for (trl = trailsToSee; trl != NULL; trl = trl->next)
4267     {
4268         dump_trail(trl->this);
4269         fprintf (stderr, "\n");
4270     }
4271     fprintf (stderr, "\n");
4272 }
4273
4274 /*------------------------------------------------------------------------------------*/
4275
4276 dump_arcs(arcsToSee)
4277     arclist *arcsToSee;
4278 {
4279     arclist *al;
4280     tile *t;
4281     /* Dump Arc List to the screen: */
4282     for (al = arcsToSee; al != NULL; al = al->next)
4283     {
4284         t = al->this->t;
4285         if (al->this->page == HORZ)
4286         fprintf(stderr, "(%d,%d),(%d,%d)H...",
4287                 t->x_pos, t->y_pos, t->x_pos + t->x_len, t->y_pos + t->y_len);
4288         else
4289         fprintf(stderr, "(%d,%d),(%d,%d)V...",
4290                 t->y_pos, t->x_pos, t->y_pos + t->y_len, t->x_pos + t->x_len);
4291     }
4292     fprintf (stderr, "\n");
4293 }
4294
4295 /*-------------------------------------------------------------------------------------*/
4296
4297 void prepare_tile_spaces(netFlag)
4298 {
4299     strcpy(dfname, "asg_vtiles.info");
4300 /*
4301     fprintf(stderr, "File to dump vertical tiles to -> ");
4302     scanf("%s", dfname);
4303 */
4304     if ((vf = fopen(dfname, "w")) == NULL)
4305     {
4306         fprintf(stderr,"Sorry, can't open %s\n", dfname);
4307         /* exit(1); */
4308         return;
4309     }
4310
4311     strcpy(dfname, "asg_htiles.info");
4312 /*
4313     fprintf(stderr, "File to dump horizontal tiles to -> ");
4314     scanf("%s", dfname);
4315 */
4316     if ((hf = fopen(dfname, "w")) == NULL)
4317     {
4318         fprintf(stderr,"Sorry, can't open %s\n", dfname);
4319         /* exit(1); */
4320         return;
4321     }
4322
4323     if (netFlag == TRUE)
4324     {
4325         /* Get the net name to study: */
4326         strcpy(net_under_study, "gnd");
4327 /*
4328         fprintf(stderr, "Please name the net being traced: ");
4329         scanf("%s", net_under_study);
4330 */
4331     }
4332 }
4333
4334 /*------------------------------------------------------------------------------------*/
4335 /* END OF FILE "global_route.c"  */