1 /*
2 * mzSearch.c --
3 *
4 * Search strategy for maze router.
5 * Low level of Maze router (finding next interesting point) is done in
6 * mzSearchRight.c etc.
7 *
8 * *********************************************************************
9 * * Copyright (C) 1988, 1990 Michael H. Arnold and the Regents of the *
10 * * University of California. *
11 * * Permission to use, copy, modify, and distribute this *
12 * * software and its documentation for any purpose and without *
13 * * fee is hereby granted, provided that the above copyright *
14 * * notice appear in all copies. The University of California *
15 * * makes no representations about the suitability of this *
16 * * software for any purpose. It is provided "as is" without *
17 * * express or implied warranty. Export of this software outside *
18 * * of the United States of America may require an export license. *
19 * *********************************************************************
20 *
21 * SEARCH STRATEGY:
22 *
23 * Partial paths are expanded one interesting point at a time - that is a
24 * path is expanded to the next interesting point left, right, up and down
25 * and vias to neighboring layers are considered, then a new (though possibly
26 * one of the extensions just created) path is selected for expansion.
27 *
28 * The "search strategy" employed determines which partial-path is
29 * chosen for exansion at each stage.
30 *
31 * A windowed search strategy is used. At any given time the window
32 * bounds define a minimum and maximum distance to the goal. Partial paths
33 * are divided into three groups: those farther from the goal than the
34 * window, those within the window, and those nearer to the goal than the
35 * window. The window begins at the start point and is slowly shifted
36 * toward the goal over time. Normally the partial-path of least
37 * estimated-total-cost WITHIN
38 * the window is chosen for expansion, although a further path (i.e. one
39 * beyond the window) that has exceptionally low estimated-total-cost is
40 * sometimes chosen instead. When the trailing edge of the window reaches
41 * the goal, the search is deemed complete and the lowest cost complete
42 * path found is returned. However if no complete-path has been found
43 * searching will continue until the first complete path is found.
44 * The idea behind the windowed search is to
45 * expand the paths that promise to give the best (lowest cost) solution, but
46 * to slowly shift attention toward the goal to avoid the VERY long time
47 * it would take to examine all possible paths.
48 *
49 * In the case of many partial paths within the window, the above search may
50 * be too scattered; "blooming" is used to give a local-focus to the search
51 * by examining a number of expansions
52 * from a given partial path before going on to consider other paths. Blooming
53 * is equivalent to searching the move tree in chess before applyng static
54 * evaluations of "final" positions. In practice it makes the router behave
55 * much better.
56 *
57 * The search strategy is implemented with three heaps and four stacks:
58 *
59 * mzMaxToGoHeap - keeps partial paths NEARER the goal than the window.
60 * these paths are not yet eligible for expansion.
61 * Whenever the window is moved, the top elements of
62 * this heap (i.e. those furthest from the goal) are
63 * moved onto the mzMinCostHeap (i.e. into the window).
64 *
65 * mzMinCostHeap - keeps partial paths inside the window. the top of this
66 * heap, i.e. the least cost path inside
67 * the window, is compared with the least (penalized) cost of
68 * the paths beyond the window, and the lesser of these
69 * two is chosen for expansion.
70 *
71 * mzMinAdjCostHeap - keeps partial paths that are further from the goal
72 * than the
73 * window. These paths are sorted by adjusted cost.
74 * Adjusted cost is estimated-total-cost plus a penalty
75 * proportial to the distance of the path from the window.
76 * The ordering of the paths is independent of the current
77 * window position - so a "reference position" is used to
78 * avoid recomputing adjusted costs for these paths
79 * everytime the window moves. The adjusted cost of the
80 * top (least cost) element is normalized to the current
81 * window position before comparison with the least cost
82 * path on the mzMinCostHeap. The idea behind the
83 * mzMinAdjCostHeap is
84 * to discourage searching of paths beyond the window, but
85 * to do so in a gentle and flexible way, so that
86 * behaviour will degrade gracefully under unusual
87 * circumstances rather than fail catastrophically.
88 * For example, if the window moves too fast and all the
89 * reasonable paths are left behind, the search will
90 * degenerate to a simple cost-based search biased towards
91 * paths nearer to completion - a startegy that is
92 * adequate in many situations.
93 *
94 * mzBloomStack - paths in current local focus = all expansions of a given
95 * partial-path that do not exceed a given estimated-cost
96 * (also see stacks below)
97 *
98 * mzStraightStack - focus paths being extended in straight line.
99 *
100 * mzDownHillStack - focus paths followed only until cost increases.
101 *
102 * mzWalkStack - paths inside walk (i.e. inside blocked area adjacent to
103 * destination.
104 *
105 * If the walk stack is not empty the next path is taken from there (thus
106 * paths that have reached the threshold of a dest area are given priority.)
107 *
108 * Next priority is given to the down hill stack, thus a focus path is always
109 * expanded until the estimated cost increases.
110 *
111 * Next the straight stack is processed. The purpose of this stack is to
112 * consider straight extensions in all directions to some given minimum
113 * distance.
114 *
115 * Next the bloom stack itself is processed. All extensions derived from
116 * the bloom stack are placed on one of the stacks until a fixed cost increment
117 * is exceeded (in practice a small increment is used, thus the local focus
118 * is only extended in straight lines, and then downhill).
119 *
120 * If all the stacks are empty, a new focus is pickd from the heaps and
121 * the bloom stack is initialized with it.
122 *
123 */
124
125 #ifndef lint
126 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/mzrouter/mzSearch.c,v 1.2 2010/06/24 12:37:19 tim Exp $";
127 #endif /* not lint */
128
129 #include <stdio.h>
130
131 #include "utils/magic.h"
132 #include "utils/geometry.h"
133 #include "utils/geofast.h"
134 #include "utils/hash.h"
135 #include "utils/heap.h"
136 #include "tiles/tile.h"
137 #include "database/database.h"
138 #include "utils/signals.h"
139 #include "textio/textio.h"
140 #include "utils/malloc.h"
141 #include "utils/list.h"
142 #include "debug/debug.h"
143 #include "utils/styles.h"
144 #include "windows/windows.h"
145 #include "dbwind/dbwind.h"
146 #include "mzrouter/mzrouter.h"
147 #include "mzrouter/mzInternal.h"
148
149 /* Forward declarations */
150
151 extern void mzExtendViaLRContacts();
152 extern void mzExtendViaUDContacts();
153 extern void mzBloomInit();
154 extern void mzMakeStatReport();
155 extern void mzExtendPath(RoutePath *);
156
157
158 /*
159 * ----------------------------------------------------------------------------
160 *
161 * mzSearch --
162 *
163 * Find a path between one of the starting terminals and the
164 * destination. The path must lie within the
165 * area mzBoundingRect.
166 *
167 * Results:
168 * Returns a pointer to best complete RoutePath found (NULL
169 * if none found). This RoutePath may be passed to
170 * MZPaintPath() to be converted into paint.
171 *
172 * Side effects:
173 * Allocates RoutePaths from our own private storage area.
174 * The caller must copy these to permanent storage with
175 * mzCopyPath() prior to calling MZClean; otherwise,
176 * the returned RoutePath will be lost.
177 *
178 * ----------------------------------------------------------------------------
179 */
180 RoutePath *
mzSearch(mzResult)181 mzSearch(mzResult)
182 int *mzResult;
183 {
184 RoutePath *path; /* solution */
185 bool morePartialPaths = TRUE;
186 bool bloomLimitHit = FALSE;
187 bool windowSweepDoneAndCompletePathFound = FALSE;
188
189 /* Report intial cost estimate */
190 if(mzVerbosity>=VERB_STATS)
191 {
192 TxPrintf("Initial Cost Estimate: %.0f\n",
193 (double)(mzInitialEstimate));
194 }
195
196 if (DebugIsSet(mzDebugID, mzDebMaze))
197 {
198 TxPrintf("\nBEGINNING SEARCH.\n");
199 TxPrintf("\tmzWRate = %.0f\n", (double)(mzWRate));
200 TxPrintf("\tmzWInitialMinToGo = %.0f\n", (double)(mzWInitialMinToGo));
201 TxPrintf("\tmzWInitialMaxToGo = %.0f\n", (double)(mzWInitialMaxToGo));
202 TxPrintf("\tmzBloomDeltaCost = %.0f\n", (double)(mzBloomDeltaCost));
203 }
204
205 while (morePartialPaths &&
206 !windowSweepDoneAndCompletePathFound &&
207 !bloomLimitHit &&
208 !SigInterruptPending)
209 /* Find next path to extend from */
210 {
211 if (DebugIsSet(mzDebugID, mzDebMaze))
212 {
213 TxPrintf("\nABOUT TO SELECT NEXT PATH TO EXTEND.\n");
214 TxMore("");
215 }
216
217 /* pop a stack */
218 path = NULL;
219 if(mzWalkStack != NULL)
220 {
221 mzPathSource = SOURCE_WALK;
222 path = (RoutePath *) ListPop(&mzWalkStack);
223
224 if (DebugIsSet(mzDebugID, mzDebMaze))
225 {
226 TxPrintf("POPPING TOP OF WALK STACK for extension.\n");
227 mzPrintPathHead(path);
228 }
229 }
230 else if(mzDownHillStack != NULL)
231 {
232 mzPathSource = SOURCE_DOWNHILL;
233 path = (RoutePath *) ListPop(&mzDownHillStack);
234
235 if (DebugIsSet(mzDebugID, mzDebMaze))
236 {
237 TxPrintf("POPPING TOP OF DOWNHILL STACK for extension.\n");
238 mzPrintPathHead(path);
239 }
240 }
241 else if(mzStraightStack != NULL)
242 {
243 mzPathSource = SOURCE_STRAIGHT;
244 path = (RoutePath *) ListPop(&mzStraightStack);
245
246 if (DebugIsSet(mzDebugID, mzDebMaze))
247 {
248 TxPrintf("POPPING TOP OF STRAIGHT STACK for extension.\n");
249 mzPrintPathHead(path);
250 }
251 }
252 else if(mzBloomStack != NULL)
253 {
254 mzPathSource = SOURCE_BLOOM;
255 path = (RoutePath *) ListPop(&mzBloomStack);
256
257 if (DebugIsSet(mzDebugID, mzDebMaze))
258 {
259 TxPrintf("POPPING TOP OF BLOOM STACK for extension.\n");
260 mzPrintPathHead(path);
261 }
262 }
263
264 /* Stacks contained a path, go about the buisness of extending it */
265 if(path)
266 {
267 /* Check hashtable to see if path already obsolete,
268 * (i.e. cheaper path to its enpt found.)
269 */
270 {
271 HashEntry *he;
272 PointKey pk;
273 RoutePath *hashedPath;
274
275 pk.pk_point = path->rp_entry;
276 pk.pk_rLayer = path->rp_rLayer;
277 pk.pk_orient = path->rp_orient;
278 #if SIZEOF_VOID_P == 8
279 pk.pk_buffer = 0; /* Otherwise the hash function screws up */
280 #endif
281
282 he = HashFind(&mzPointHash, (char *) &pk);
283 hashedPath = (RoutePath *) HashGetValue(he);
284 ASSERT(hashedPath!=NULL,"mzFindPath");
285
286 if (path!=hashedPath)
287 {
288 /* DEBUG - report path rejected due to hash value. */
289 if (DebugIsSet(mzDebugID, mzDebMaze))
290 {
291 TxPrintf("HASH LOOKUP reveals better path, REJECT path.\n");
292 }
293
294 /* better path to this pt already exists,
295 * skip to next path
296 */
297 continue;
298 }
299 }
300
301 /* Make sure blockage planes have been generated around the path
302 * end.
303 */
304 {
305 Point *point = &(path->rp_entry);
306 Tile *tp = TiSrPointNoHint(mzHBoundsPlane, point);
307
308 if (TiGetType(tp)==TT_SPACE ||
309 point->p_x == LEFT(tp) || point->p_x == RIGHT(tp))
310 {
311 if (DebugIsSet(mzDebugID, mzDebMaze))
312 {
313 TxPrintf("Path ends on vertical boundary of blockage");
314 TxPrintf(" planes, BLOCKAGE PLANES BEING EXTENDED.\n");
315 }
316
317 mzExtendBlockBounds(point);
318 if(SigInterruptPending) continue;
319 }
320
321 else
322 {
323
324 tp = TiSrPointNoHint(mzVBoundsPlane, point);
325 if (point->p_y == BOTTOM(tp) || point->p_y == TOP(tp))
326 {
327 if (DebugIsSet(mzDebugID, mzDebMaze))
328 {
329 TxPrintf("Path ends on horizontal boundary");
330 TxPrintf("of blockage planes, BLOCKAGE PLANES");
331 TxPrintf("BEING EXTENDED.\n");
332 }
333
334 mzExtendBlockBounds(point);
335 if(SigInterruptPending) continue;
336 }
337 }
338 }
339
340 /* DEBUG - if single-stepping, print data, show path end visually,
341 * and pause.
342 */
343 if (DebugIsSet(mzDebugID, mzDebStep))
344 {
345 Rect box;
346 CellDef *boxDef;
347
348 /* print stats on this path */
349 {
350 int i;
351 RoutePath *p;
352
353 /* path # */
354 TxPrintf("READY TO EXTEND PATH ");
355 TxPrintf("(blooms: %d, points-processed: %d):\n",
356 mzNumBlooms,
357 mzNumPaths);
358 mzPrintPathHead(path);
359
360 /* # of segments in path segments */
361 i=0;
362 for(p=path; p->rp_back!=0; p=p->rp_back)
363 i++;
364 TxPrintf(" (%d segments in path)\n", i);
365 }
366
367 /* move box to path end-point */
368 if(ToolGetBox(&boxDef,&box))
369 {
370 int deltaX = box.r_xtop - box.r_xbot;
371 int deltaY = box.r_ytop - box.r_ybot;
372 box.r_ll = path->rp_entry;
373 box.r_ur.p_x = path->rp_entry.p_x + deltaX;
374 box.r_ur.p_y = path->rp_entry.p_y + deltaY;
375 DBWSetBox(mzRouteUse->cu_def, &box);
376 WindUpdate();
377 }
378
379 /* wait for user to continue */
380 TxMore("");
381 }
382
383 /* Extend Path */
384 mzExtendPath(path);
385
386 /* update statistics */
387 mzNumPaths++; /* increment number of paths processed */
388 if(--mzPathsTilReport == 0)
389 {
390 mzPathsTilReport = mzReportInterval;
391 mzMakeStatReport();
392 }
393
394 }
395 else
396 /* stacks are empty, choose path from heaps to initial them with */
397 {
398 HeapEntry maxToGoTopBuf, minCostTopBuf, buf;
399 HeapEntry *maxToGoTop, *minCostTop, *minAdjCostTop;
400
401 if (DebugIsSet(mzDebugID, mzDebMaze))
402 {
403 TxPrintf("BLOOM STACK EMPTY. ");
404 TxPrintf("Choosing path from heaps to initial it with.\n");
405 }
406
407 /* If the bloom limit has been exceeded, stop searching */
408 if(mzBloomLimit >0 &&
409 mzNumBlooms > mzBloomLimit)
410 {
411 if(mzVerbosity>=VERB_BRIEF)
412 {
413 TxPrintf("Bloom limit (%d) hit.\n", mzBloomLimit);
414 }
415
416 bloomLimitHit = TRUE;
417 continue;
418 }
419
420 /* set window thresholds */
421 {
422 dlong offset;
423
424 offset = (dlong) (mzWRate * mzNumBlooms);
425
426 if(offset <= mzWInitialMinToGo)
427 {
428 mzWindowMinToGo = mzWInitialMinToGo - offset;
429 }
430 else
431 {
432 mzWindowMinToGo = 0;
433 }
434
435 if(offset <= mzWInitialMaxToGo)
436 {
437 mzWindowMaxToGo = mzWInitialMaxToGo - offset;
438 }
439 else
440 {
441 mzWindowMaxToGo = 0;
442 }
443
444 if (DebugIsSet(mzDebugID, mzDebMaze))
445 {
446 TxPrintf("New window thresholds: ");
447 TxPrintf("windowMinToGo = %.0f, ",
448 (double)mzWindowMinToGo);
449 TxPrintf("windowMaxToGo = %.0f\n ",
450 (double)mzWindowMaxToGo);
451 }
452 }
453
454 /* If window sweep is complete, and a complete path
455 * has been found, stop searching.
456 */
457 if((mzWindowMaxToGo == 0) &&
458 HeapLookAtTop(&mzMinCostCompleteHeap))
459 {
460 if (DebugIsSet(mzDebugID, mzDebMaze))
461 {
462 TxPrintf("WINDOW SWEEP DONE AND COMPLETE PATH EXISTS.");
463 TxPrintf(" Stop searching.\n");
464 }
465
466 windowSweepDoneAndCompletePathFound = TRUE;
467 continue;
468 }
469
470 /* Move points that meet the minTogo threshold to window
471 * (Points are moved from the MaxToGo heap to the minCost heap)
472 */
473 {
474 if (DebugIsSet(mzDebugID, mzDebMaze))
475 {
476 TxPrintf("Moving paths into window ");
477 TxPrintf("(maxTogoHeap -> minCostHeap): \n");
478 }
479
480 while((maxToGoTop=HeapRemoveTop(&mzMaxToGoHeap,
481 &maxToGoTopBuf)) != NULL &&
482 (maxToGoTop->he_union.hu_dlong >= mzWindowMinToGo))
483 {
484 if (DebugIsSet(mzDebugID, mzDebMaze))
485 {
486 mzPrintPathHead((RoutePath*)(maxToGoTop->he_id));
487 }
488
489 HeapAddDLong(&mzMinCostHeap,
490 ((RoutePath *)(maxToGoTop->he_id))->rp_cost,
491 (char *) (maxToGoTop->he_id));
492 }
493 if(maxToGoTop!=NULL)
494 {
495 HeapAddDLong(&mzMaxToGoHeap,
496 maxToGoTop->he_union.hu_dlong,
497 (char *) (maxToGoTop->he_id));
498 }
499 }
500
501 /* Clear top of minCostHeap of points that no longer meet the
502 * mzWindowMaxToGo threshold.
503 * (minCostHeap -> minAdjCostHeap)
504 */
505 {
506 if (DebugIsSet(mzDebugID, mzDebMaze))
507 {
508 TxPrintf("Moving paths out of window ");
509 TxPrintf("(minCostHeap -> minAdjCostHeap): \n");
510 }
511
512 while((minCostTop=HeapRemoveTop(&mzMinCostHeap,
513 &minCostTopBuf))!=NULL &&
514 (((RoutePath *)(minCostTop->he_id))->rp_togo >
515 mzWindowMaxToGo))
516 {
517 dlong adjCost;
518
519 /* compute adjusted cost */
520 adjCost = (dlong)((RoutePath *)(minCostTop->he_id))->rp_togo;
521 adjCost = (dlong)(adjCost * mzPenalty.rf_mantissa);
522 adjCost = adjCost >> mzPenalty.rf_nExponent;
523 adjCost += minCostTop->he_union.hu_dlong;
524
525 if (DebugIsSet(mzDebugID, mzDebMaze))
526 {
527 mzPrintPathHead((RoutePath*)(minCostTop->he_id));
528 TxPrintf(" Heap-key adjCost = %.0f\n", (double)adjCost);
529 }
530
531 /* add to adjusted cost heap */
532 HeapAddDLong(&mzMinAdjCostHeap, adjCost,
533 (char *) (minCostTop->he_id));
534 }
535
536 if(minCostTop!=NULL)
537 {
538 HeapAddDLong(&mzMinCostHeap,
539 minCostTop->he_union.hu_dlong,
540 (char *) (minCostTop->he_id));
541 }
542 }
543
544 /* Peek at tops of heaps
545 * (equal cost elements might have got shuffled above when
546 * we placed the last poped element back on the heap.)
547 */
548 minAdjCostTop = HeapLookAtTop(&mzMinAdjCostHeap);
549 maxToGoTop = HeapLookAtTop(&mzMaxToGoHeap);
550 minCostTop = HeapLookAtTop(&mzMinCostHeap);
551
552 /* Print tops of maxToGo, minCost and minAdjCost heaps */
553 if (DebugIsSet(mzDebugID, mzDebMaze))
554 {
555 TxPrintf("Max togo top:\n");
556 if(maxToGoTop)
557 {
558 mzPrintPathHead((RoutePath*)(maxToGoTop->he_id));
559 }
560 else
561 {
562 TxPrintf(" nil\n");
563 }
564 TxPrintf("Min cost top:\n");
565 if(minCostTop)
566 {
567 mzPrintPathHead((RoutePath*)(minCostTop->he_id));
568 }
569 else
570 {
571 TxPrintf(" nil\n");
572 }
573 TxPrintf("Min adjcost top:\n");
574 if(minAdjCostTop)
575 {
576 TxPrintf(" Heap-key adjCost: %.0f\n",
577 (double)(minAdjCostTop->he_union.hu_dlong));
578 }
579 else
580 {
581 TxPrintf(" nil\n");
582 }
583 }
584
585 if(minCostTop && minAdjCostTop)
586 /* need to compare minCostTop and minAdjCostTop */
587 {
588 /* compute adjusted cost corresponding to current window
589 * position (we only penalize for amount toGo exceeding
590 * mzWindowMaxToGo)
591 */
592 dlong cost, adjCost;
593
594 cost =(dlong)((RoutePath *)(minAdjCostTop->he_id))->rp_cost;
595 adjCost = (dlong)((RoutePath *)(minAdjCostTop->he_id))->rp_togo;
596 ASSERT(adjCost >= mzWindowMaxToGo,"mzSearch");
597 adjCost -= mzWindowMaxToGo;
598 adjCost *= mzPenalty.rf_mantissa;
599 adjCost = adjCost >> mzPenalty.rf_nExponent;
600 adjCost += cost;
601 if (DebugIsSet(mzDebugID, mzDebMaze))
602 {
603 TxPrintf("WINDOW-CORRECTED ADJCOST: %.0f\n",
604 (double)(adjCost));
605 }
606 if(minCostTop->he_union.hu_dlong <= adjCost)
607 {
608 if (DebugIsSet(mzDebugID, mzDebMaze))
609 {
610 TxPrintf("INITIALIZING BLOOM STACK ");
611 TxPrintf("WITH TOP OF MIN COST HEAP.\n");
612 }
613 minCostTop = HeapRemoveTop(&mzMinCostHeap, &buf);
614 mzBloomInit((RoutePath *) (minCostTop->he_id));
615 }
616 else
617 {
618 if (DebugIsSet(mzDebugID, mzDebMaze))
619 {
620 TxPrintf("INITIALIZING BLOOM STACK ");
621 TxPrintf("WITH TOP OF MIN ADJCOST HEAP.\n");
622 }
623 minAdjCostTop = HeapRemoveTop(&mzMinAdjCostHeap, &buf);
624 mzBloomInit((RoutePath *) (minAdjCostTop->he_id));
625 mzNumOutsideBlooms++;
626 }
627 }
628 else if(minCostTop)
629 /* minAdjCostHeap empty, so bloom from minCostTop */
630 {
631 if (DebugIsSet(mzDebugID, mzDebMaze))
632 {
633 TxPrintf("INITIALIZING BLOOM STACK ");
634 TxPrintf("WITH TOP OF MIN COST HEAP.\n");
635 }
636 minCostTop = HeapRemoveTop(&mzMinCostHeap, &buf);
637 mzBloomInit((RoutePath *) (minCostTop->he_id));
638 }
639 else if(minAdjCostTop)
640 /* minCost Heap empty, so bloom from minAdjCostTop */
641 {
642 if (DebugIsSet(mzDebugID, mzDebMaze))
643 {
644 TxPrintf("INITIALIZING BLOOM STACK ");
645 TxPrintf("WITH TOP OF MIN ADJCOST HEAP.\n");
646 }
647 minAdjCostTop = HeapRemoveTop(&mzMinAdjCostHeap, &buf);
648 mzBloomInit((RoutePath *) (minAdjCostTop->he_id));
649 mzNumOutsideBlooms++;
650 }
651 else
652 /* minCost and minAdjCost heaps empty,
653 * bloom from top of TOGO heap */
654 {
655 if(maxToGoTop)
656 {
657 if (DebugIsSet(mzDebugID, mzDebMaze))
658 {
659 TxPrintf("INITIALIZING BLOOM STACK ");
660 TxPrintf("WITH TOP OF MAX TOGO HEAP.\n");
661 }
662 maxToGoTop = HeapRemoveTop(&mzMaxToGoHeap, &buf);
663 mzBloomInit((RoutePath *) (maxToGoTop->he_id));
664 mzNumOutsideBlooms++;
665 }
666 else
667 /* No paths left to extend from */
668 {
669 if (DebugIsSet(mzDebugID, mzDebMaze))
670 {
671 TxPrintf("NO PATHS LEFT TO EXTEND FROM.\n");
672 }
673 morePartialPaths = FALSE;
674 }
675 }
676 }
677 }
678
679 /* Give final stat report. */
680 mzMakeStatReport();
681
682 /* Return best complete path */
683 {
684 HeapEntry heEntry;
685
686 if(HeapRemoveTop(&mzMinCostCompleteHeap,&heEntry))
687 {
688 if (mzResult)
689 {
690 if (SigInterruptPending)
691 *mzResult = MZ_CURRENT_BEST;
692 else
693 *mzResult = MZ_SUCCESS;
694 }
695 return (RoutePath *)(heEntry.he_id);
696 }
697 else
698 {
699 if (mzResult)
700 {
701 if (SigInterruptPending)
702 *mzResult = MZ_INTERRUPTED;
703 else
704 *mzResult = MZ_FAILURE;
705 }
706 return NULL;
707 }
708 }
709 }
710
711
712 /*
713 * ----------------------------------------------------------------------------
714 *
715 * mzExtendPath --
716 *
717 * Spread out to next interesting point in four directions, and to adjacent
718 * layers through contacts.
719 *
720 * Results:
721 * None.
722 *
723 * Side effects:
724 * Adds new routepaths to the queues (ie. heaps and bloomstack).
725 *
726 * ----------------------------------------------------------------------------
727 */
728
729 void
mzExtendPath(path)730 mzExtendPath(path)
731 RoutePath *path;
732 {
733 int extendCode = path->rp_extendCode;
734
735 if (extendCode & EC_RIGHT)
736 {
737 mzExtendRight(path);
738 }
739
740 if (extendCode & EC_LEFT)
741 {
742 mzExtendLeft(path);
743 }
744
745 if (extendCode & EC_UP)
746 {
747 mzExtendUp(path);
748 }
749
750 if (extendCode & EC_DOWN)
751 {
752 mzExtendDown(path);
753 }
754
755 if (extendCode & EC_UDCONTACTS)
756 {
757 mzExtendViaUDContacts(path);
758 }
759 if (extendCode & EC_LRCONTACTS)
760 {
761 mzExtendViaLRContacts(path);
762 }
763
764 if (extendCode >= EC_WALKRIGHT)
765 {
766 if (extendCode & EC_WALKRIGHT)
767 {
768 mzWalkRight(path);
769 }
770 else if (extendCode & EC_WALKLEFT)
771 {
772 mzWalkLeft(path);
773 }
774
775 else if (extendCode & EC_WALKUP)
776 {
777 mzWalkUp(path);
778 }
779
780 else if (extendCode & EC_WALKDOWN)
781 {
782 mzWalkDown(path);
783 }
784 else if (extendCode & EC_WALKUDCONTACT)
785 {
786 mzWalkUDContact(path);
787 }
788 else if (extendCode & EC_WALKLRCONTACT)
789 {
790 mzWalkLRContact(path);
791 }
792 }
793
794 return;
795 }
796
797
798 /*
799 * ----------------------------------------------------------------------------
800 *
801 * mzExtendViaLRContacts --
802 *
803 * Spread from a point to other planes reachable from it,
804 * by using contacts. Stacked contacts are allowed. Search the horizontal
805 * block plane. Limit to areas that fit the contact minimum length.
806 *
807 * Results None.
808 *
809 * Side effects:
810 * Adds RoutePaths to the heap (mzReservePathCostHeap).
811 *
812 * ----------------------------------------------------------------------------
813 */
814 void
mzExtendViaLRContacts(path)815 mzExtendViaLRContacts(path)
816 RoutePath *path;
817 {
818 Point p = path->rp_entry, *lastCpos = NULL;
819 RouteLayer *rLayer = path->rp_rLayer;
820 RouteContact *rC;
821 List *cL;
822 RouteLayer *newRLayer;
823 Tile *tp;
824 TileType type, lastCtype = TT_SPACE;
825 RoutePath *spath;
826 int bendDist = 0;
827
828 /* DEBUG - trace calls to this routine */
829 if (DebugIsSet(mzDebugID, mzDebMaze))
830 TxPrintf("EXTENDING WITH CONTACTS (HORIZONTAL)\n");
831
832 /* Check what the last contact was and remember its */
833 /* position. Do not allow two contacts of the same */
834 /* type within a DRC error distance of each other. */
835
836 for (spath = path; spath && spath->rp_back && (spath->rp_orient != 'O');
837 spath = spath->rp_back);
838 if (spath->rp_back)
839 {
840 lastCpos = &spath->rp_entry;
841 rC = MZGetContact(spath, spath->rp_back);
842 lastCtype = rC->rc_routeType.rt_tileType;
843 }
844
845 /* Check where the last route bend is. Don't allow a */
846 /* contact within a DRC error distance of a bend. */
847
848 if (path)
849 {
850 if (path->rp_orient == 'V')
851 {
852 for (spath = path->rp_back; spath && spath->rp_orient == 'V';
853 spath = spath->rp_back);
854 if (spath && spath->rp_orient == 'H')
855 bendDist = spath->rp_entry.p_y - p.p_y;
856 if (bendDist < 0)
857 bendDist += rLayer->rl_routeType.rt_width;
858 }
859 else if (path->rp_orient == 'H')
860 {
861 for (spath = path->rp_back; spath && spath->rp_orient == 'H';
862 spath = spath->rp_back);
863 if (spath && spath->rp_orient == 'V')
864 bendDist = spath->rp_entry.p_x - p.p_x;
865 if (bendDist < 0)
866 bendDist += rLayer->rl_routeType.rt_width;
867 }
868 }
869
870 /* Loop through contacts that connect to current rLayer */
871 for (cL=rLayer->rl_contactL; cL!=NULL; cL=LIST_TAIL(cL))
872 {
873 rC = (RouteContact *) LIST_FIRST(cL);
874
875 /* Don't use inactive contacts */
876 if (!(rC->rc_routeType.rt_active))
877 continue;
878
879 /* Get "other" route Layer contact connects to */
880 if (rC->rc_rLayer1 == rLayer)
881 {
882 newRLayer = rC->rc_rLayer2;
883 }
884 else
885 {
886 ASSERT(rC->rc_rLayer2 == rLayer,
887 "mzExtendViaLRContacts");
888 newRLayer = rC->rc_rLayer1;
889 }
890
891 /* Don't spread to inactive layers */
892 if (!(newRLayer->rl_routeType.rt_active)) continue;
893
894 /* Find tile on contact plane that contains point. */
895
896 tp = TiSrPointNoHint(rC->rc_routeType.rt_hBlock, &p);
897 type = TiGetType(tp);
898
899 /* 1. If blocked, don't place a contact */
900 if ((type != TT_SPACE) && (type != TT_SAMENODE))
901 continue;
902
903 /* 2. If tile space is not long enough for the contact, don't place */
904 if (RIGHT(tp) - p.p_x <= rC->rc_routeType.rt_length
905 - rC->rc_routeType.rt_width)
906 continue;
907
908 /* 3. Check distance from last contact, if the same type */
909 if (rC->rc_routeType.rt_tileType == lastCtype)
910 {
911 int cdist = rC->rc_routeType.rt_spacing[lastCtype] +
912 rC->rc_routeType.rt_width;
913 if ((abs(p.p_x - lastCpos->p_x) < cdist) &&
914 (abs(p.p_y - lastCpos->p_y) < cdist))
915 continue;
916 }
917
918 /* 4. Check distance to last route bend */
919 if (bendDist != 0)
920 {
921 int cwidth = rC->rc_routeType.rt_width;
922 int spacing = rC->rc_routeType.rt_spacing[rLayer->rl_routeType.rt_tileType];
923 if (bendDist > cwidth && bendDist < cwidth + spacing)
924 continue;
925 if (bendDist < 0 && bendDist > -spacing)
926 continue;
927 }
928
929 /* OK to drop a contact here */
930 {
931 dlong conCost;
932 int extendCode;
933
934 /* set contact cost */
935 conCost = (dlong) rC->rc_cost;
936
937 /* determine appropriate extendcode */
938 tp = TiSrPointNoHint(newRLayer->rl_routeType.rt_hBlock, &p);
939 type = TiGetType(tp);
940
941 switch (type)
942 {
943 case TT_SPACE:
944 case TT_SAMENODE:
945 extendCode = EC_RIGHT | EC_LEFT | EC_UP | EC_DOWN;
946 break;
947
948 case TT_LEFT_WALK:
949 extendCode = EC_WALKRIGHT;
950 break;
951
952 case TT_RIGHT_WALK:
953 extendCode = EC_WALKLEFT;
954 break;
955
956 case TT_TOP_WALK:
957 extendCode = EC_WALKDOWN;
958 break;
959
960 case TT_BOTTOM_WALK:
961 extendCode = EC_WALKUP;
962 break;
963
964 case TT_ABOVE_LR_WALK:
965 case TT_BELOW_LR_WALK:
966 /* TO DO: Check if stacked contacts are allowed! */
967 extendCode = EC_WALKLRCONTACT;
968 break;
969
970 case TT_ABOVE_UD_WALK:
971 case TT_BELOW_UD_WALK:
972 /* TO DO: Check if stacked contacts are allowed! */
973 extendCode = EC_WALKUDCONTACT;
974 break;
975
976 case TT_DEST_AREA:
977
978 extendCode = EC_COMPLETE;
979 break;
980
981 default:
982 /* this shouldn't happen */
983 ASSERT(FALSE,"mzExtendViaLRContacts");
984 continue;
985 }
986
987 /* Finally add point after contact */
988 mzAddPoint(path, &p, newRLayer, 'O', extendCode, &conCost);
989 }
990 }
991
992 return;
993 }
994
995 /*
996 * ----------------------------------------------------------------------------
997 *
998 * mzExtendViaUDContacts --
999 *
1000 * Spread from a point to other planes reachable from it,
1001 * by using contacts. Stacked contacts are allowed. Search the vertical
1002 * block plane. Limit to areas that fit the contact minimum length.
1003 *
1004 * Results None.
1005 *
1006 * Side effects:
1007 * Adds RoutePaths to the heap (mzReservePathCostHeap).
1008 *
1009 * ----------------------------------------------------------------------------
1010 */
1011 void
mzExtendViaUDContacts(path)1012 mzExtendViaUDContacts(path)
1013 RoutePath *path;
1014 {
1015 Point p = path->rp_entry, *lastCpos = NULL;
1016 RouteLayer *rLayer = path->rp_rLayer;
1017 RouteContact *rC;
1018 List *cL;
1019 RouteLayer *newRLayer;
1020 Tile *tp;
1021 TileType type, lastCtype = TT_SPACE;
1022 RoutePath *spath;
1023 int bendDist = 0;
1024
1025 /* DEBUG - trace calls to this routine */
1026 if (DebugIsSet(mzDebugID, mzDebMaze))
1027 TxPrintf("EXTENDING WITH CONTACTS (VERTICAL)\n");
1028
1029 /* Check what the last contact was and remember its */
1030 /* position. Do not allow two contacts of the same */
1031 /* type within a DRC error distance of each other. */
1032
1033 for (spath = path; spath && spath->rp_back && (spath->rp_orient != 'X');
1034 spath = spath->rp_back);
1035 if (spath->rp_back)
1036 {
1037 lastCpos = &spath->rp_entry;
1038 rC = MZGetContact(spath, spath->rp_back);
1039 lastCtype = rC->rc_routeType.rt_tileType;
1040 }
1041
1042 /* Check where the last route bend is. Don't allow a */
1043 /* contact within a DRC error distance of a bend. */
1044
1045 if (path)
1046 {
1047 if (path->rp_orient == 'V')
1048 {
1049 for (spath = path->rp_back; spath && spath->rp_orient == 'V';
1050 spath = spath->rp_back);
1051 if (spath && spath->rp_orient == 'H')
1052 bendDist = spath->rp_entry.p_y - p.p_y;
1053 if (bendDist < 0)
1054 bendDist += rLayer->rl_routeType.rt_width;
1055 }
1056 else if (path->rp_orient == 'H')
1057 {
1058 for (spath = path->rp_back; spath && spath->rp_orient == 'H';
1059 spath = spath->rp_back);
1060 if (spath && spath->rp_orient == 'V')
1061 bendDist = spath->rp_entry.p_x - p.p_x;
1062 if (bendDist < 0)
1063 bendDist += rLayer->rl_routeType.rt_width;
1064 }
1065 }
1066
1067 /* Loop through contacts that connect to current rLayer */
1068 for (cL=rLayer->rl_contactL; cL!=NULL; cL=LIST_TAIL(cL))
1069 {
1070 rC = (RouteContact *) LIST_FIRST(cL);
1071
1072 /* Don't use inactive contacts */
1073 if (!(rC->rc_routeType.rt_active))
1074 continue;
1075
1076 /* Get "other" route Layer contact connects to */
1077 if (rC->rc_rLayer1 == rLayer)
1078 {
1079 newRLayer = rC->rc_rLayer2;
1080 }
1081 else
1082 {
1083 ASSERT(rC->rc_rLayer2 == rLayer,
1084 "mzExtendViaUDContacts");
1085 newRLayer = rC->rc_rLayer1;
1086 }
1087
1088 /* Don't spread to inactive layers */
1089 if (!(newRLayer->rl_routeType.rt_active)) continue;
1090
1091 /* Find tile on contact plane that contains point. */
1092
1093 tp = TiSrPointNoHint(rC->rc_routeType.rt_vBlock, &p);
1094 type = TiGetType(tp);
1095
1096 /* 1. If blocked, don't place a contact */
1097 if ((type != TT_SPACE) && (type != TT_SAMENODE))
1098 continue;
1099
1100 /* 2. If tile space is not long enough for the contact, don't place */
1101 if (TOP(tp) - p.p_y <= rC->rc_routeType.rt_length
1102 - rC->rc_routeType.rt_width)
1103 continue;
1104
1105 /* 3. Check distance from last contact, if the same type */
1106 if (rC->rc_routeType.rt_tileType == lastCtype)
1107 {
1108 int cdist = rC->rc_routeType.rt_spacing[lastCtype] +
1109 rC->rc_routeType.rt_width;
1110 if ((abs(p.p_x - lastCpos->p_x) < cdist) &&
1111 (abs(p.p_y - lastCpos->p_y) < cdist))
1112 continue;
1113 }
1114
1115 /* 4. Check distance to last route bend */
1116 if (bendDist != 0)
1117 {
1118 int cwidth = rC->rc_routeType.rt_width;
1119 int spacing = rC->rc_routeType.rt_spacing[rLayer->rl_routeType.rt_tileType];
1120 if (bendDist > cwidth && bendDist < cwidth + spacing)
1121 continue;
1122 if (bendDist < 0 && bendDist > -spacing)
1123 continue;
1124 }
1125
1126 /* OK to drop a contact here */
1127 {
1128 dlong conCost;
1129 int extendCode;
1130
1131 /* set contact cost */
1132 conCost = (dlong) rC->rc_cost;
1133
1134 /* determine appropriate extendcode */
1135 tp = TiSrPointNoHint(newRLayer->rl_routeType.rt_vBlock, &p);
1136 type = TiGetType(tp);
1137
1138 switch (type)
1139 {
1140 case TT_SPACE:
1141 case TT_SAMENODE:
1142 extendCode = EC_RIGHT | EC_LEFT | EC_UP | EC_DOWN;
1143 break;
1144
1145 case TT_LEFT_WALK:
1146 extendCode = EC_WALKRIGHT;
1147 break;
1148
1149 case TT_RIGHT_WALK:
1150 extendCode = EC_WALKLEFT;
1151 break;
1152
1153 case TT_TOP_WALK:
1154 extendCode = EC_WALKDOWN;
1155 break;
1156
1157 case TT_BOTTOM_WALK:
1158 extendCode = EC_WALKUP;
1159 break;
1160
1161 case TT_ABOVE_LR_WALK:
1162 case TT_BELOW_LR_WALK:
1163 /* TO DO: Check if stacked contacts are allowed! */
1164 extendCode = EC_WALKLRCONTACT;
1165 break;
1166
1167 case TT_ABOVE_UD_WALK:
1168 case TT_BELOW_UD_WALK:
1169 /* TO DO: Check if stacked contacts are allowed! */
1170 extendCode = EC_WALKUDCONTACT;
1171 break;
1172
1173 case TT_DEST_AREA:
1174
1175 extendCode = EC_COMPLETE;
1176 break;
1177
1178 default:
1179 /* this shouldn't happen */
1180 ASSERT(FALSE,"mzExtendViaUDContacts");
1181 continue;
1182 }
1183
1184 /* Finally add point after contact */
1185 mzAddPoint(path, &p, newRLayer, 'X', extendCode, &conCost);
1186 }
1187 }
1188
1189 return;
1190 }
1191
1192 /*
1193 * ----------------------------------------------------------------------------
1194 *
1195 * mzAddPoint --
1196 *
1197 * Process interesting point. If point within bounds and not redundant,
1198 * link to previous path, update cost, and add to heap.
1199 *
1200 *
1201 * Results:
1202 * None.
1203 *
1204 * Side effects:
1205 * Adds a RoutePath to the heap.
1206 *
1207 * ----------------------------------------------------------------------------
1208 */
1209 void
mzAddPoint(path,p,rLayer,orient,extendCode,costptr)1210 mzAddPoint(path, p, rLayer, orient, extendCode, costptr)
1211 RoutePath *path; /* path that new point extends */
1212 Point *p; /* new point */
1213 RouteLayer *rLayer; /* Route Layer of new point */
1214 int orient; /* 'H' = endpt of hor seg, 'V' = endpt of vert seg,
1215 * 'O' = LR contact, 'X' = UD contact,
1216 * 'B' = first point in path and blocked
1217 */
1218 int extendCode; /* interesting directions to extend in */
1219 dlong *costptr; /* Incremental cost of new path segment */
1220
1221 {
1222 RoutePath *newPath;
1223 RoutePath *hashedPath;
1224 HashEntry *he;
1225 PointKey pk;
1226 dlong togo, cost;
1227
1228 /* DEBUG - print candidate frontier point */
1229 if (DebugIsSet(mzDebugID, mzDebMaze))
1230 {
1231 TxPrintf("mzAddPoint called: point=(%d,%d), layer=%s, orient='%c'\n",
1232 p->p_x, p->p_y,
1233 DBTypeLongNameTbl[rLayer->rl_routeType.rt_tileType],
1234 orient);
1235 }
1236
1237 cost = *costptr;
1238 ASSERT(cost >= 0,"mzAddPoint");
1239
1240 /* Ignore if outside of bounding box */
1241 if (!GEO_ENCLOSE(p, &mzBoundingRect))
1242 return;
1243
1244 /* get estimated distance togo */
1245 if(extendCode == EC_COMPLETE)
1246 togo = 0;
1247 else
1248 togo = mzEstimatedCost(p);
1249
1250 /* compute (total) cost for new path */
1251 {
1252 /* initially cost = cost of new leg in path */
1253
1254 /* Add jogcost if appropriate */
1255
1256 if (path != NULL &&
1257 path->rp_rLayer == rLayer &&
1258 path->rp_orient != 'O' && path->rp_orient != 'X' &&
1259 path->rp_orient != orient)
1260 {
1261 cost += rLayer->rl_jogCost;
1262 }
1263
1264 /* Add estimated total cost prior to new point,
1265 * (or cost so far in the case of initial paths).
1266 */
1267 if (path != NULL)
1268 {
1269 cost += path->rp_cost;
1270 }
1271 /* If not initial path, subtract out old estimated cost togo */
1272 if (mzPathSource != SOURCE_INIT)
1273 {
1274 cost -= path->rp_togo;
1275 }
1276
1277 /* Add new estimated cost to completion */
1278 cost += togo;
1279 }
1280
1281 /* Check hash table to see if cheaper path to this point already
1282 * found - if so don't add this point.
1283 */
1284 pk.pk_point = *p;
1285 pk.pk_rLayer = rLayer;
1286 pk.pk_orient = orient;
1287 #if SIZEOF_VOID_P == 8
1288 pk.pk_buffer = 0; /* Otherwise the hash function screws up */
1289 #endif
1290
1291 he = HashFind(&mzPointHash, (char *) &pk);
1292 hashedPath = (RoutePath *) HashGetValue(he);
1293
1294 if (hashedPath != NULL && (hashedPath->rp_cost <= cost))
1295 {
1296 if (DebugIsSet(mzDebugID, mzDebMaze))
1297 {
1298 TxPrintf("new point NOT added, at least as good "
1299 "path to pt already exists: ");
1300 TxPrintf("new cost = %.0f, ",
1301 (double)(cost));
1302 TxPrintf("cheapest cost = %.0f\n",
1303 (double)(hashedPath->rp_cost));
1304 }
1305 return;
1306 }
1307
1308 /* If initial path, update min initial cost */
1309 if(mzPathSource==SOURCE_INIT)
1310 {
1311 if(cost < mzMinInitialCost)
1312 {
1313 mzMinInitialCost = cost;
1314 }
1315 }
1316
1317 /* Create new path element */
1318 newPath = NEWPATH();
1319 newPath->rp_rLayer = rLayer;
1320 newPath->rp_entry = *p;
1321 newPath->rp_orient = orient;
1322 newPath->rp_cost = cost;
1323 newPath->rp_extendCode = extendCode;
1324 newPath->rp_togo = togo;
1325 newPath->rp_back = path;
1326
1327 /* keep statistics */
1328 mzNumPathsGened++;
1329
1330 /* Enter in hash table */
1331 HashSetValue(he, (ClientData) newPath);
1332
1333 /* Add to appropriate queue or stack */
1334 if(extendCode == EC_COMPLETE)
1335 {
1336 if (DebugIsSet(mzDebugID, mzDebMaze))
1337 {
1338 TxPrintf("PATH COMPLETE (WALKED IN). Add to complete heap.\n");
1339 }
1340
1341 HeapAddDLong(&mzMinCostCompleteHeap, newPath->rp_cost,
1342 (char *) newPath);
1343
1344 /* compute stats and make completed path report */
1345 {
1346 mzNumComplete++;
1347
1348 if(mzVerbosity>=VERB_STATS)
1349 {
1350 dlong cost, excessCost;
1351 double excessPercent;
1352
1353 mzMakeStatReport();
1354
1355 TxPrintf("PATH #%d ", mzNumComplete);
1356
1357
1358 cost = newPath->rp_cost;
1359 TxPrintf("cst:%.0f, ", (double)(newPath->rp_cost));
1360 if(cost < mzInitialEstimate)
1361 {
1362 TxPrintf("(<est)");
1363 }
1364 else
1365 {
1366 excessCost = cost - mzInitialEstimate;
1367 excessPercent = 100.0 * (double)(excessCost)/
1368 (double)(mzInitialEstimate);
1369
1370 TxPrintf("overrun: %.0f%%", excessPercent);
1371 }
1372
1373 TxPrintf("\n");
1374 }
1375 }
1376 }
1377 else if(extendCode >= EC_WALKRIGHT)
1378 {
1379 LIST_ADD(newPath, mzWalkStack);
1380 }
1381 else
1382 {
1383 switch(mzPathSource)
1384 {
1385 case SOURCE_BLOOM:
1386 if(orient=='O')
1387 {
1388 /* just changing layers, add back to bloom */
1389 LIST_ADD(newPath, mzBloomStack);
1390 }
1391 else if((orient=='H' && rLayer->rl_hCost<=rLayer->rl_vCost) ||
1392 (orient=='V' && rLayer->rl_vCost<=rLayer->rl_hCost))
1393 {
1394 /* going in preferred direction */
1395 LIST_ADD(newPath, mzStraightStack);
1396 }
1397 else
1398 {
1399 /* non preferred, add to heaps */
1400 HeapAddDLong(&mzMaxToGoHeap, togo, (char *) newPath);
1401 }
1402 break;
1403
1404 case SOURCE_STRAIGHT:
1405 if(path->rp_orient==orient && (cost < mzBloomMaxCost))
1406 {
1407 /* straight and within bounds, keep going*/
1408 LIST_ADD(newPath, mzStraightStack);
1409 }
1410 else
1411 {
1412 /* from here on, follow downhill only */
1413 LIST_ADD(newPath, mzDownHillStack);
1414 }
1415 break;
1416
1417 case SOURCE_DOWNHILL:
1418 {
1419 dlong oldCostPlusOne;
1420
1421 oldCostPlusOne = path->rp_cost + 1;
1422 if(cost <oldCostPlusOne)
1423 {
1424 /* cost within a unit, keep following down hill */
1425 LIST_ADD(newPath, mzDownHillStack);
1426 }
1427 else
1428 {
1429 /* increased cost, add to heaps */
1430 HeapAddDLong(&mzMaxToGoHeap, togo, (char *) newPath);
1431 }
1432 }
1433 break;
1434
1435 case SOURCE_INIT:
1436 /* Initial points go on heap */
1437 HeapAddDLong(&mzMaxToGoHeap, togo, (char *) newPath);
1438 break;
1439 }
1440 }
1441 return;
1442 }
1443
1444
1445 /*
1446 * ----------------------------------------------------------------------------
1447 *
1448 * mzBloomInit --
1449 *
1450 * Initialize bloom stack with given path.
1451 *
1452 * Results:
1453 * None.
1454 *
1455 * Side effects:
1456 * Adds a routepath to bloom stack, and sets mzBloomMaxCost.
1457 *
1458 * ----------------------------------------------------------------------------
1459 */
1460 void
mzBloomInit(path)1461 mzBloomInit(path)
1462 RoutePath *path; /* path that new point extends */
1463 {
1464 ASSERT(mzBloomStack==NULL,"mzBloomInit");
1465
1466 LIST_ADD(path, mzBloomStack);
1467 mzBloomMaxCost = path->rp_cost + mzBloomDeltaCost;
1468
1469 mzNumBlooms++;
1470
1471 return;
1472 }
1473
1474 /*
1475 * ----------------------------------------------------------------------------
1476 *
1477 * mzMakeStatReport --
1478 *
1479 * Print out route statistics
1480 *
1481 * Results:
1482 * None.
1483 *
1484 * Side effects:
1485 * Output via TxPrintf()
1486 *
1487 * ----------------------------------------------------------------------------
1488 */
1489
1490 void
mzMakeStatReport()1491 mzMakeStatReport()
1492 {
1493
1494 /* if we aren't being verbose, skip this */
1495 if(mzVerbosity<VERB_STATS) return;
1496
1497 TxPrintf(" Blms:%d(%d)", mzNumBlooms - mzNumOutsideBlooms,
1498 mzNumBlooms);
1499
1500 TxPrintf(" Wndw:%.0f(%.0f%%)", (double)(mzWindowMaxToGo),
1501 (100.0 * (1- (double)(mzWindowMaxToGo)/
1502 ((double)(mzInitialEstimate) +(double)(mzWWidth)))));
1503
1504 TxPrintf(" Pts:%d(%d)",
1505 mzNumPaths,
1506 mzNumPathsGened);
1507
1508 TxPrintf(" Blkgen: %dx%.0f",
1509 mzBlockGenCalls,
1510 mzBlockGenArea/mzBlockGenCalls);
1511
1512 TxPrintf("(%.0f/icst)",
1513 (double)mzBlockGenArea/(double)(mzInitialEstimate));
1514
1515 TxPrintf("\n");
1516 return;
1517 }
1518
1519