1 /* grouteTile.c -
2 *
3 * Global signal router code for tile and channel related things.
4 *
5 * *********************************************************************
6 * * Copyright (C) 1985, 1990 Regents of the University of California. *
7 * * Permission to use, copy, modify, and distribute this *
8 * * software and its documentation for any purpose and without *
9 * * fee is hereby granted, provided that the above copyright *
10 * * notice appear in all copies. The University of California *
11 * * makes no representations about the suitability of this *
12 * * software for any purpose. It is provided "as is" without *
13 * * express or implied warranty. Export of this software outside *
14 * * of the United States of America may require an export license. *
15 * *********************************************************************
16 */
17
18 #ifndef lint
19 static char sccsid[] = "@(#)grouteTile.c 4.3 MAGIC (Berkeley) 10/31/85";
20 #endif /* not lint */
21
22 #include <stdio.h>
23
24 #include "utils/magic.h"
25 #include "utils/geometry.h"
26 #include "utils/hash.h"
27 #include "utils/heap.h"
28 #include "tiles/tile.h"
29 #include "database/database.h"
30 #include "debug/debug.h"
31 #include "gcr/gcr.h"
32 #include "windows/windows.h"
33 #include "graphics/graphics.h"
34 #include "utils/main.h"
35 #include "dbwind/dbwind.h"
36 #include "utils/signals.h"
37 #include "router/router.h"
38 #include "grouter/grouter.h"
39 #include "utils/styles.h"
40 #include "textio/textio.h"
41
42 bool GlDebugCrossings = FALSE;
43
44 #define isSpaceTile(tile) (TiGetBody(tile) == NULL)
45
46
47 /*
48 * ----------------------------------------------------------------------------
49 *
50 * glAdjacentChannel --
51 *
52 * Figure out which channel borders the given channel at the given
53 * point. If the given channel is NULL, then assume the point is at
54 * the edge of a cell, and return the channel adjacent to the cell.
55 *
56 * Results:
57 * Pointer to the adjacent channel, or NULL if none exists.
58 *
59 * Side effects:
60 * None.
61 *
62 * ----------------------------------------------------------------------------
63 */
64
65 GCRChannel *
glAdjacentChannel(ch,point)66 glAdjacentChannel(ch, point)
67 GCRChannel *ch; /* The tile corresponding to a channel */
68 Point *point; /* A point somewhere on the channel edge */
69 {
70 Point p;
71 int side;
72
73 ASSERT(ch!=(GCRChannel *) NULL, "Null channel in glAdjacentChannel");
74 side = glPointToSide(ch, point);
75
76 p = * point;
77 switch(side)
78 {
79 case GEO_NORTH:
80 case GEO_EAST:
81 break;
82 case GEO_SOUTH:
83 p.p_y--;
84 break;
85 case GEO_WEST:
86 p.p_x--;
87 break;
88 default:
89 ASSERT(FALSE, "glAdjacentChannel point not on channel");
90 return((GCRChannel *) NULL);
91 break;
92 }
93
94 return (glTileToChannel(TiSrPointNoHint(RtrChannelPlane, &p)));
95 }
96
97 /*
98 * ----------------------------------------------------------------------------
99 *
100 * glBadChannel --
101 *
102 * Decide if a prospective channel is okay to use in global routing
103 * propagation. If it creates a loop for the particular path under
104 * investigation, then forget it. If it doesn't exist, then forget it.
105 *
106 * Results:
107 * FALSE if the channel is okay to use, otherwise TRUE.
108 *
109 * Side effects:
110 * None.
111 *
112 * ----------------------------------------------------------------------------
113 */
114
115 bool
glBadChannel(oldCh,newCh,entryPt)116 glBadChannel(oldCh, newCh, entryPt)
117 GCRChannel *oldCh; /* The current channel */
118 GCRChannel *newCh; /* See if this new one is okay to use */
119 GlPoint *entryPt; /* List of previously used points */
120 {
121 GlPoint *temp;
122
123 /* Reject a null channel */
124 if ((oldCh == (GCRChannel *) NULL) || (newCh == (GCRChannel *) NULL))
125 return (TRUE);
126
127 /* Reject the channel if using it creates a loop in the routing path */
128 for (temp = entryPt; temp != (GlPoint *) NULL; temp = temp->gl_parent)
129 if (temp->gl_ch == newCh)
130 return (TRUE);
131
132 return (FALSE);
133 }
134
135 /*
136 * ----------------------------------------------------------------------------
137 *
138 * glDebug --
139 *
140 * Code to display crossing points on the screen.
141 *
142 * Results:
143 * None.
144 *
145 * Side effects:
146 * None.
147 *
148 * ----------------------------------------------------------------------------
149 */
150
151 void
glDebug(point,text,value,size)152 glDebug(point, text, value, size)
153 Point *point; /* Location to be marked */
154 char *text; /* Text to associate with error paint */
155 int value; /* An integer value to go into the text */
156 int size; /* How big to make the error paint box */
157 {
158 char buffer1[1024], buffer2[1024];
159 Rect area;
160
161 if (!GlDebugCrossings)
162 return;
163
164 (void) strcpy(buffer1, text);
165 (void) sprintf(buffer2, "(value = %d)", value);
166 (void) strcat(buffer1, buffer2);
167 area.r_ll.p_x = point->p_x - size;
168 area.r_ur.p_x = point->p_x + size;
169 area.r_ll.p_y = point->p_y - size;
170 area.r_ur.p_y = point->p_y + size;
171 DBWFeedbackAdd(&area, buffer1, EditCellUse->cu_def, 1,
172 STYLE_PALEHIGHLIGHTS);
173 GrFlush();
174 (void) sprintf(buffer2, "%s --more--", buffer1);
175 (void) TxGetLinePrompt(buffer1, sizeof buffer1, buffer2);
176 if (buffer1[0] == 'q')
177 GlDebugCrossings = FALSE;
178 TxPrintf("\n");
179 }
180
181 /*
182 * ----------------------------------------------------------------------------
183 *
184 * glPointToChannel --
185 *
186 * Given a point and a direction, return a pointer to the channel
187 * adjacent to the given point, in the given direction. The point
188 * must be on the edge of a channel. If on the edge of a cell, the
189 * point location must be the modified location returned by RtrStemTip.
190 *
191 * Results:
192 * Pointer to the channel.
193 *
194 * Side effects:
195 * None.
196 *
197 * ----------------------------------------------------------------------------
198 */
199
200 GCRChannel *
glPointToChannel(point,dir)201 glPointToChannel(point, dir)
202 Point *point; /* The point from which the channel is found */
203 int dir; /* The direction in which the search goes */
204 {
205 Point p;
206
207 p = *point;
208 switch (dir)
209 {
210 case GEO_NORTH:
211 case GEO_EAST:
212 break;
213 case GEO_SOUTH:
214 p.p_y--;
215 break;
216 case GEO_WEST:
217 p.p_x--;
218 break;
219 default:
220 ASSERT(FALSE, "glPointToChannel: bad direction argument");
221 return ((GCRChannel *) NULL);
222 }
223 return (glTileToChannel(TiSrPointNoHint(RtrChannelPlane, &p)));
224 }
225
226 /*
227 * ----------------------------------------------------------------------------
228 *
229 * glPointToSide --
230 *
231 * Given a point somewhere on the perimeter of a channel, determine
232 * which side it is on. The channel is given to prevent ambiguity,
233 * since the point may fall on a border between two channels.
234 *
235 * Results:
236 * The compass direction corresponding to the side of the channel on
237 * which the point lies.
238 *
239 * Side effects:
240 * None.
241 *
242 * ----------------------------------------------------------------------------
243 */
244
245 int
glPointToSide(ch,pt)246 glPointToSide(ch, pt)
247 GCRChannel * ch; /* Channel containing the given point */
248 Point * pt; /* The point on some side of the channel*/
249 {
250
251 /* The point is on the left */
252 if (ch->gcr_area->r_xbot == pt->p_x)
253 return (GEO_WEST);
254
255 /* The point is on the bottom */
256 if (ch->gcr_area->r_ybot == pt->p_y)
257 return (GEO_SOUTH);
258
259 /* The point is on the right */
260 if (ch->gcr_area->r_xtop == pt->p_x)
261 return (GEO_EAST);
262
263 /* The point is on the top */
264 if (ch->gcr_area->r_ytop == pt->p_y)
265 return (GEO_NORTH);
266
267 ASSERT(FALSE, "glPointToSide point not on edge");
268 return (GEO_CENTER);
269 }
270
271 /*
272 * ----------------------------------------------------------------------------
273 *
274 * glSide --
275 *
276 * Determine which side of a cell a terminal label is on by looking on
277 * the channel plane for channel tiles in each of the quadrants. A
278 * terminal label must not fall on space or on a corner. It must lie
279 * on a flat edge of a cell tile.
280 *
281 * Are all these calls to TiSrPoint really necessary? I think so,
282 * because a label might fall on the edge of a particular tile but
283 * still appear over contiguous cell tiles.
284 *
285 * Results:
286 * A direction GEO_NORTH, SOUTH, EAST, WEST, or CENTER if internal or
287 * a corner. This indicates the side of the cell on which the terminal
288 * lies.
289 *
290 * Side effects:
291 * None.
292 *
293 * ----------------------------------------------------------------------------
294 */
295
296 int
glSide(point)297 glSide(point)
298 Point *point; /* The lower left point of the label rectangle */
299 {
300 int glSrFunc();
301 Tile *t;
302 Point p;
303
304 p = *point;
305 t = TiSrPoint((Tile *) NULL, RtrChannelPlane, &p);
306
307 if(TiGetBody(t) != NULL) /* _?|X_ */
308 { /* ?|? */
309 p.p_x--;
310 t = TiSrPoint(t, RtrChannelPlane, &p);
311 if(TiGetBody(t) != NULL) /* _X|X_ */
312 { /* ?|? */
313 p.p_y--;
314 t = TiSrPoint(t, RtrChannelPlane, &p);
315 if(TiGetBody(t) != NULL) /* _X|X_ */
316 return(GEO_CENTER); /* X|? */
317 p.p_x++;
318 t = TiSrPoint(t, RtrChannelPlane, &p);
319 if(TiGetBody(t) != NULL) /* _X|X_ */
320 return(GEO_CENTER); /* |X */
321 else return(GEO_SOUTH);
322 }
323 else /* __|X_ */
324 { /* ?|? */
325 p.p_y--;
326 t = TiSrPoint(t, RtrChannelPlane, &p);
327 if(TiGetBody(t) != NULL) /* __|X_ */
328 return(GEO_CENTER); /* X|? */
329 p.p_x++;
330 t = TiSrPoint(t, RtrChannelPlane, &p);
331 if(TiGetBody(t) != NULL) /* __|X_ */
332 return(GEO_WEST); /* |X */
333 }
334 }
335 else /* Forget about S or W */
336 {
337 p.p_x--;
338 t = TiSrPoint(t, RtrChannelPlane, &p);
339 if(TiGetBody(t) != NULL) /* _X|__ */
340 { /* ?|? */
341 p.p_y--;
342 t = TiSrPoint(t, RtrChannelPlane, &p);
343 if(TiGetBody(t) == NULL) /* _X|__ */
344 return(GEO_CENTER); /* |? */
345 p.p_x++;
346 t = TiSrPoint(t, RtrChannelPlane, &p);
347 if(TiGetBody(t) != NULL) /* _X|__ */
348 return(GEO_CENTER); /* X|X */
349 else return(GEO_EAST);
350 }
351 else /* __|__ */
352 { /* ?|? */
353 p.p_y--;
354 t = TiSrPoint(t, RtrChannelPlane, &p);
355 if(TiGetBody(t) == NULL) /* __|__ */
356 return(GEO_CENTER); /* |? */
357 p.p_x++;
358 t = TiSrPoint(t, RtrChannelPlane, &p);
359 if(TiGetBody(t) != NULL) /* __|__ */
360 return(GEO_NORTH); /* X|X */
361 }
362 }
363 return(GEO_CENTER);
364 }
365
366 /*
367 * ----------------------------------------------------------------------------
368 *
369 * glTileToChannel --
370 *
371 * Figure out which channel corresponds to the given tile.
372 *
373 * Results:
374 * Pointer to the channel.
375 *
376 * Side effects:
377 * None.
378 *
379 * ----------------------------------------------------------------------------
380 */
381
382 GCRChannel *
glTileToChannel(tile)383 glTileToChannel(tile)
384 Tile *tile; /* Should point to a channel (space) tile */
385 {
386 HashEntry *he;
387
388 if (!isSpaceTile(tile))
389 return ((GCRChannel *) NULL);
390 he = HashLookOnly(&RtrTileToChannel, (char *) tile);
391 if (he == (HashEntry *) NULL)
392 return ((GCRChannel *) NULL);
393 return (GCRChannel *) HashGetValue(he);
394 }
395