Imported 1.3.103

1 files changed, 129 insertions, 78 deletions

diff --git a/maze.c b/maze.c
index dfeea06..ac6833e 100644
--- a/maze.c
+++ b/maze.c
@@ -224,8 +224,8 @@ void clear_non_source_targets(NET net, POINT *pushlist)
 		      gpoint->x1 = x;
 		      gpoint->y1 = y;
 		      gpoint->layer = lay;
-		      gpoint->next = *pushlist;
-		      *pushlist = gpoint;
+		      gpoint->next = pushlist[1];
+		      pushlist[1] = gpoint;
 		   }
 		}
 	    }
@@ -355,9 +355,10 @@ count_targets(NET net)
 /* will be no way to route the net.				*/
 /*--------------------------------------------------------------*/
 
-int set_node_to_net(NODE node, int newflags, POINT *pushlist, SEG bbox, u_char stage)
+int set_node_to_net(NODE node, int newflags, POINT *pushlist,
+	SEG bbox, u_char stage)
 {
-    int x, y, lay, obsnet = 0;
+    int x, y, lay, rank, base, obsnet = 0;
     int result = 0;
     u_char found_one = FALSE;
     NODEINFO lnode;
@@ -419,6 +420,22 @@ int set_node_to_net(NODE node, int newflags, POINT *pushlist, SEG bbox, u_char s
 
 	  Pr->prdata.cost = (newflags == PR_SOURCE) ? 0 : MAXRT;
 
+	  // Rank the position according to how difficult it is to route to:
+	  //
+	  // 0: no restrictions
+	  // 1: requires a stub route
+	  // 2: inside the halo
+	  // 3: requires an offset
+	  // 4: requires an offset and a stub route
+
+	  rank = 0;
+          if (lay < Pinlayers) {
+	     if (lnode = NODEIPTR(x, y, lay)) {
+		if (lnode->flags & NI_OFFSET_MASK) rank = 2;
+		if (lnode->flags & NI_STUB_MASK) rank++;
+	     }
+          }
+
 	  // push this point on the stack to process
 
 	  if (pushlist != NULL) {
@@ -428,8 +445,8 @@ int set_node_to_net(NODE node, int newflags, POINT *pushlist, SEG bbox, u_char s
 	        gpoint->x1 = x;
 	        gpoint->y1 = y;
 	        gpoint->layer = lay;
-	        gpoint->next = *pushlist;
-		*pushlist = gpoint;
+	        gpoint->next = pushlist[rank];
+		pushlist[rank] = gpoint;
 	     }
 	  }
 	  found_one = TRUE;
@@ -456,10 +473,15 @@ int set_node_to_net(NODE node, int newflags, POINT *pushlist, SEG bbox, u_char s
        // Don't process extended areas if they coincide with other nodes,
        // or those that are out-of-bounds
 
+       base = 0;
        if (lay < Pinlayers) {
 	  lnode = NODEIPTR(x, y, lay);
 	  if (lnode == NULL) continue;
 	  if (lnode->nodesav != node) continue;
+
+	  // Otherwise, rank according to ease of reaching the tap.
+          if (lnode->flags & NI_OFFSET_MASK) base = 2;
+          if (lnode->flags & NI_STUB_MASK) base++;
        }
 
        Pr = &OBS2VAL(x, y, lay);
@@ -493,14 +515,10 @@ int set_node_to_net(NODE node, int newflags, POINT *pushlist, SEG bbox, u_char s
 	        gpoint->x1 = x;
 	        gpoint->y1 = y;
 	        gpoint->layer = lay;
-		if (found_one) {
-	            gpoint->next = pushlist[1];
-		    pushlist[1] = gpoint;
-		}
-		else {
-	            gpoint->next = *pushlist;
-		    *pushlist = gpoint;
-		}
+		rank = (found_one == TRUE) ? 2 + base : base;
+
+	        gpoint->next = pushlist[rank];
+		pushlist[rank] = gpoint;
 	     }
 	  }
 	  found_one = TRUE;
@@ -541,8 +559,8 @@ int set_node_to_net(NODE node, int newflags, POINT *pushlist, SEG bbox, u_char s
 }
 
 /*--------------------------------------------------------------*/
-/* Set all taps of node "node" to MAXNETNUM, so that it will not	*/
-/* be routed to. 						*/
+/* Set all taps of node "node" to MAXNETNUM, so that it will	*/
+/* not be routed to. 						*/
 /*--------------------------------------------------------------*/
 
 int disable_node_nets(NODE node)
@@ -693,33 +711,39 @@ int set_route_to_net_recursive(NET net, ROUTE rt, int newflags,
     if (rt->flags & RT_START_NODE) {
 	for (route = net->routes; route; route = route->next) {
 	    if (!(route->flags & RT_START_NODE) && (route->start.route == rt)) {
-		result = set_route_to_net(net, route, newflags, pushlist, bbox, stage);
+		result = set_route_to_net_recursive(net, route, newflags,
+				pushlist, bbox, stage);
 		if (result < 0) return result;
 	    }
 	    if (!(route->flags & RT_END_NODE) && (route->end.route == rt)) {
-		result = set_route_to_net(net, route, newflags, pushlist, bbox, stage);
+		result = set_route_to_net_recursive(net, route, newflags,
+				pushlist, bbox, stage);
 		if (result < 0) return result;
 	    }
 	}
     }
     else {
-	result = set_route_to_net(net, rt->start.route, newflags, pushlist, bbox, stage);
+	result = set_route_to_net_recursive(net, rt->start.route, newflags,
+			pushlist, bbox, stage);
 	if (result < 0) return result;
     }
     if (rt->flags & RT_END_NODE) {
 	for (route = net->routes; route; route = route->next) {
 	    if (!(route->flags & RT_START_NODE) && (route->start.route == rt)) {
-		result = set_route_to_net(net, route, newflags, pushlist, bbox, stage);
+		result = set_route_to_net_recursive(net, route, newflags,
+				pushlist, bbox, stage);
 		if (result < 0) return result;
 	    }
 	    if (!(route->flags & RT_END_NODE) && (route->end.route == rt)) {
-		result = set_route_to_net(net, route, newflags, pushlist, bbox, stage);
+		result = set_route_to_net_recursive(net, route, newflags,
+				pushlist, bbox, stage);
 		if (result < 0) return result;
 	    }
 	}
     }
     else {
-	result = set_route_to_net(net, rt->end.route, newflags, pushlist, bbox, stage);
+	result = set_route_to_net_recursive(net, rt->end.route, newflags,
+			pushlist, bbox, stage);
 	if (result < 0) return result;
     }
     return result;
@@ -918,7 +942,7 @@ NETLIST find_colliding(NET net, int *ripnum)
 
    if ((nl != NULL) && (Verbose > 0)) {
       Fprintf(stdout, "Best route of %s collides with net%s: ",
-		net->netname, (rnum > 1) ? "" : "s");
+		net->netname, (rnum > 1) ? "s" : "");
       for (cnl = nl; cnl; cnl = cnl->next) {
          Fprintf(stdout, "%s ", cnl->net->netname);
       }
@@ -1024,11 +1048,11 @@ void analyze_route_overwrite(int x, int y, int lay, int netnum)
 			    /* so rip up the net now.			 */
 			    Fprintf(stderr, "Taking evasive action against net "
 					"%d\n", netnum);
-			    ripup_net(fnet, TRUE, FALSE);
+			    ripup_net(fnet, TRUE, FALSE, FALSE);
 			    return;
 			}
 			if ((sx == seg->x2) && (sy == seg->y2)) {
-			    if ((seg->segtype == ST_WIRE) || (l == (lay + 1))) break;
+			    if ((seg->segtype == ST_WIRE) || (l >= (lay + 1))) break;
 			    else l++;
 			}
 			else {
@@ -1046,6 +1070,57 @@ void analyze_route_overwrite(int x, int y, int lay, int netnum)
 }
 
 /*--------------------------------------------------------------*/
+/* Remove all route records from a net.				*/
+/*--------------------------------------------------------------*/
+
+void remove_routes(ROUTE netroutes, u_char flagged)
+{
+   ROUTE rt, rsave, rlast;
+   SEG seg;
+
+   /* Remove all flagged routing information from this net	*/
+   /* if "flagged" is true, otherwise remove all routing	*/
+   /* information.						*/
+
+   if (flagged && (netroutes != NULL)) {
+      rlast = NULL;
+      rsave = netroutes;
+      while (rsave) {
+	 if (rsave->flags & RT_RIP) {
+	    rt = rsave;
+	    if (rlast == NULL)
+		netroutes = rsave->next;
+	    else
+		rlast->next = rsave->next;
+	    rsave = rsave->next;
+	    while (rt->segments) {
+	       seg = rt->segments->next;
+	       free(rt->segments);
+	       rt->segments = seg;
+	    }
+	    free(rt);
+	 }
+	 else {
+	    rlast = rsave;
+	    rsave = rsave->next;
+	 }
+      }
+   }
+   else {
+      while (netroutes) {
+         rt = netroutes;
+         netroutes = rt->next;
+         while (rt->segments) {
+	    seg = rt->segments->next;
+	    free(rt->segments);
+	    rt->segments = seg;
+         }
+         free(rt);
+      }
+   }
+}
+
+/*--------------------------------------------------------------*/
 /* ripup_net ---						*/
 /*								*/
 /* Rip up the entire network located at position x, y, lay.	*/
@@ -1056,14 +1131,19 @@ void analyze_route_overwrite(int x, int y, int lay, int netnum)
 /*								*/
 /* If argument "flagged" is TRUE, then only remove routes	*/
 /* that have been flagged with RT_RIP.				*/
+/*								*/
+/* If argument "retain" is TRUE, then do not remove the route	*/
+/* records from the net.  This assumes that the calling routine	*/
+/* will retain them for possible replacement in case of route	*/
+/* failure.							*/
 /*--------------------------------------------------------------*/
 
-u_char ripup_net(NET net, u_char restore, u_char flagged)
+u_char ripup_net(NET net, u_char restore, u_char flagged, u_char retain)
 {
    int thisnet, oldnet, x, y, lay, dir;
    NODEINFO lnode;
    NODE node;
-   ROUTE rt, rsave, rlast;
+   ROUTE rt;
    SEG seg;
    DPOINT ntap;
 
@@ -1190,50 +1270,15 @@ u_char ripup_net(NET net, u_char restore, u_char flagged)
       }
    }
 
-   /* Remove all flagged routing information from this net	*/
-   /* if "flagged" is true, otherwise remove all routing	*/
-   /* information.						*/
+   if (retain == FALSE) {
 
-   if (flagged && (net->routes != NULL)) {
-      rlast = NULL;
-      rsave = net->routes;
-      while (rsave) {
-	 if (rsave->flags & RT_RIP) {
-	    rt = rsave;
-	    if (rlast == NULL)
-		net->routes = rsave->next;
-	    else
-		rlast->next = rsave->next;
-	    rsave = rsave->next;
-	    while (rt->segments) {
-	       seg = rt->segments->next;
-	       free(rt->segments);
-	       rt->segments = seg;
-	    }
-	    free(rt);
-	 }
-	 else {
-	    rlast = rsave;
-	    rsave = rsave->next;
-	 }
-      }
-   }
-   else {
-      while (net->routes) {
-         rt = net->routes;
-         net->routes = rt->next;
-         while (rt->segments) {
-	    seg = rt->segments->next;
-	    free(rt->segments);
-	    rt->segments = seg;
-         }
-         free(rt);
-      }
-   }
+      remove_routes(net->routes, flagged);
+      net->routes = NULL;
 
-   // If we just ripped out a few of the routes, make sure all the
-   // other net routes have not been overwritten.
-   if (flagged) writeback_all_routes(net);
+      // If we just ripped out a few of the routes, make sure all the
+      // other net routes have not been overwritten.
+      if (flagged) writeback_all_routes(net);
+   }
 
    // If this was a specialnet (numnodes set to 0), then routes are
    // considered fixed obstructions and cannot be removed.
@@ -1745,14 +1790,20 @@ route_set_connections(net, route)
 
    /* Does last route segment connect to a node? */
 
-   for (; seg->next; seg = seg->next);
+   /* NOTE:  Avoid the case where the route is exactly one via connecting */
+   /* a node to a route directly above, in which case the following code  */
+   /* would flag the node twice, incorrectly.				  */
+
    found = FALSE;
-   if (seg->layer < Pinlayers) {
-      lnode = NODEIPTR(seg->x2, seg->y2, seg->layer);
-      if (lnode != NULL) {
-	 route->end.node = lnode->nodesav;
-	 route->flags |= RT_END_NODE;
-	 found = TRUE;
+   if ((seg->next != NULL) || !(seg->segtype & ST_VIA)) {
+      for (; seg->next; seg = seg->next);
+      if (seg->layer < Pinlayers) {
+         lnode = NODEIPTR(seg->x2, seg->y2, seg->layer);
+         if (lnode != NULL) {
+	    route->end.node = lnode->nodesav;
+	    route->flags |= RT_END_NODE;
+	    found = TRUE;
+	 }
       }
    }
 
@@ -1771,7 +1822,7 @@ route_set_connections(net, route)
 	    if (!match) continue;
 	    x = s->x1;
 	    y = s->y1;
-	    if (x == seg->x2 && y == seg->y2) {
+	    if (x == seg->x2 && y == seg->y2 && nr != route->start.route) {
 	       found = TRUE;
 	       route->end.route = nr;
 	       break;
@@ -1779,7 +1830,7 @@ route_set_connections(net, route)
 	    while (TRUE) {
 	       if (s->x2 != s->x1) x += ((s->x2 > s->x1) ? 1 : -1);
 	       if (s->y2 != s->y1) y += ((s->y2 > s->y1) ? 1 : -1);
-	       if (x == seg->x2 && y == seg->y2) {
+	       if (x == seg->x2 && y == seg->y2 && nr != route->start.route) {
 		  found = TRUE;
 		  route->end.route = nr;
 		  break;