CabbageObstaclesImpl.mesa
Copyright Ó 1986, 1987 by Xerox Corporation. All rights reversed.
Created by Bryan Preas, June 4, 1986 4:02:08 pm PDT
Last Edited by: Louis Monier April 23, 1987 4:18:11 pm PDT
Jean-Marc Frailong November 17, 1987 3:42:32 pm PST
Bertrand Serlet April 29, 1987 5:36:05 pm PDT
Bryan Preas September 10, 1987 5:13:21 pm PDT
DIRECTORY Cabbage, CabbageObstacles, Connections, DABasics;
CabbageObstaclesImpl: CEDAR PROGRAM
IMPORTS Cabbage
EXPORTS CabbageObstacles = {
Obstacle Manipulation Procedures
-- Assertion: obstacles do not overlap: if you insert a new obstacle and it overlaps an existing one in the table, the two are fused and the resulting union is put in the table; this should be maintained at all time
-- The table contains the projection of the pins with the design rule space on each side
-- [outerRange.min..outerRange.max] must map into [0..obstacles.size-1]
Translate: PROC [obstacles: CabbageObstacles.BitTable, pos: INT] RETURNS [bitIndex: NAT] ~ INLINE {
bitIndex ← (pos-obstacles.min)/obstacles.bitSize;
IF bitIndex NOT IN [0..obstacles.size) THEN ERROR};
CreateBitTable: PUBLIC PROC [min, max: INT, bitSize: NAT] RETURNS [bitTable: CabbageObstacles.BitTable] ~ {
size: NAT ← (max/bitSize)-(min/bitSize)+1;
bitTable ← NEW[CabbageObstacles.BitTableRec[size]];
bitTable.bitSize ← bitSize;
bitTable.min ← min;
bitTable.max ← max;
FOR i: NAT IN [0..size) DO
bitTable[i] ← FALSE;
ENDLOOP};
PositionOccupied: PROC [obstacles: CabbageObstacles.BitTable, pos: INT] RETURNS [BOOL] ~ INLINE {
RETURN[obstacles[Translate[obstacles, pos]]]};
-- Assertion: pos must be in (obstacles.min..obstacles.max)!!!
NextPos: PROC [obstacles: CabbageObstacles.BitTable, from: INT, goingUp: BOOL] RETURNS [next: INT] ~ INLINE {
next ← IF goingUp THEN from + obstacles.bitSize ELSE from - obstacles.bitSize};
Edge: PROC [obstacles: CabbageObstacles.BitTable, goingUp: BOOL] RETURNS [pos: INT] ~ INLINE {
pos ← IF goingUp THEN obstacles.max ELSE obstacles.min};
SetOccupied: PROC [obstacles: CabbageObstacles.BitTable, pos: INT] ~ INLINE {
IF pos NOT IN [obstacles.min..obstacles.max] THEN RETURN;
obstacles[Translate[obstacles, pos]] ← TRUE};
-- Bloat range by a spacing on each side on insertion; there is space here, you know it!
Insert: PUBLIC PROC [obstacles: CabbageObstacles.BitTable, range: Connections.Range, spacing: INT] ~ {
FOR pos: INT IN [range.min-spacing..range.max+spacing] DO
SetOccupied[obstacles, pos];
ENDLOOP};
-- when isFree, then nextTry=range.min
-- range must be valid (within outerRange)
IsFree: PROC [range: Connections.Range, obstacles: CabbageObstacles.BitTable, goingUp: BOOL] RETURNS [isFree: BOOL, nextTry: INT] ~ {
FOR pos: INT IN [range.min..range.max] DO
IF PositionOccupied[obstacles, pos] THEN RETURN[FALSE, FindNextFree[obstacles, pos, goingUp]];
ENDLOOP;
RETURN[TRUE, range.min]};
FindNextFree: PROC [obstacles: CabbageObstacles.BitTable, from: INT, goingUp: BOOL] RETURNS [free: INT] ~ {
free ← from;
WHILE PositionOccupied[obstacles, free] AND free#Edge[obstacles, goingUp] DO
free ← NextPos[obstacles, free, goingUp];
ENDLOOP};
FindLowerRange: PUBLIC PROC [adjustedRange: Connections.Range, obstacles: CabbageObstacles.BitTable] RETURNS [newRange: Connections.Range] ~ {
Bug: always add 1 point, new location might not be free !!!
find a neRange were pin is not hidden by a pin in obstacles and does not interfere with existing pin
pin should be close to outerRange.min
isFree: BOOL ← FALSE;
nextTry: INT;
newRange ← adjustedRange;
WHILE ~isFree DO
[isFree, nextTry] ← IsFree[newRange, obstacles, TRUE];
IF nextTry>=obstacles.max THEN Cabbage.Signal[noResource, "No space for pin on power bus side."];
newRange ← [nextTry + obstacles.bitSize, nextTry + obstacles.bitSize + (adjustedRange.max-adjustedRange.min)]; -- noop if isFree
ENDLOOP};
FindLowerRange: PUBLIC PROC [adjustedRange: Connections.Range, obstacles: CabbageObstacles.BitTable] RETURNS [newRange: Connections.Range] ~ {
find a neRange were pin is not hidden by a pin in obstacles and does not interfere with existing pin
pin should be close to outerRange.min
newRange ← adjustedRange;
DO
isFree: BOOL; nextTry: INT;
[isFree, nextTry] ← IsFree[newRange, obstacles, TRUE];
IF isFree THEN EXIT; -- we now have a free range of the required size
IF nextTry>=obstacles.max THEN {
Cabbage.Signal[noResource, "No space for pin on power bus side."];
EXIT; -- will return a bogus location, but no one cares ...
};
newRange ← [nextTry + obstacles.bitSize, nextTry + obstacles.bitSize + (adjustedRange.max-adjustedRange.min)]; -- add some breathing space
ENDLOOP;
};
FindUpperRange: PUBLIC PROC [adjustedRange: Connections.Range, obstacles: CabbageObstacles.BitTable] RETURNS [newRange: Connections.Range] ~ {
Bug: always remove 1 point, new location might not be free !!!
find a newRange were pin is not hidden by a pin in obstacles and does not interfere with existing pin
pin should be close to outerRange.max
isFree: BOOL ← FALSE;
nextTry: INT;
newRange ← adjustedRange;
WHILE ~isFree DO
[isFree, nextTry] ← IsFree[newRange, obstacles, FALSE];
IF nextTry<=obstacles.min THEN Cabbage.Signal[noResource, "No space for pin on power bus side."];
newRange ← [nextTry - obstacles.bitSize - (adjustedRange.max-adjustedRange.min), nextTry - obstacles.bitSize]; -- noop if isFree
ENDLOOP};
FindUpperRange: PUBLIC PROC [adjustedRange: Connections.Range, obstacles: CabbageObstacles.BitTable] RETURNS [newRange: Connections.Range] ~ {
find a newRange were pin is not hidden by a pin in obstacles and does not interfere with existing pin
pin should be close to outerRange.max
newRange ← adjustedRange;
DO
isFree: BOOL; nextTry: INT;
[isFree, nextTry] ← IsFree[newRange, obstacles, FALSE];
IF isFree THEN EXIT; -- we now have a free range of the required size
IF nextTry<=obstacles.min THEN {
Cabbage.Signal[noResource, "No space for pin on power bus side."];
EXIT; -- will return a bogus location, but no one cares ...
};
newRange ← [nextTry - obstacles.bitSize - (adjustedRange.max-adjustedRange.min), nextTry - obstacles.bitSize]; -- add some breathing space
ENDLOOP;
};
FindMiddleRange: PUBLIC PROC [adjustedRange: Connections.Range, obstacles: CabbageObstacles.BitTable] RETURNS [newRange: Connections.Range] ~ {
find a neRange were pin is not hidden by a pin in obstacles and does not interfere with existing pin
IF IsFree[adjustedRange, obstacles, FALSE].isFree THEN RETURN[adjustedRange]
ELSE {
fellOffLower, fellOffUpper: BOOL ← FALSE;
lower, upper: Connections.Range; -- CEDAR Bug! Signals in initialization
upper ← FindLowerRange[adjustedRange, obstacles ! Cabbage.Signal => IF errorType=noResource THEN {fellOffUpper ← TRUE; CONTINUE}];
lower ← FindUpperRange[adjustedRange, obstacles ! Cabbage.Signal => IF errorType=noResource THEN {fellOffLower ← TRUE; CONTINUE}];
IF fellOffUpper AND fellOffLower THEN Cabbage.Signal[noResource, "No space for pin on power bus side."];
IF fellOffUpper THEN RETURN[lower];
IF fellOffLower THEN RETURN[upper];
IF adjustedRange.min-lower.min<upper.min-adjustedRange.min THEN RETURN[lower];
RETURN[upper]}};
}.