DIRECTORY Cabbage, CabbageObstacles, Connections, DABasics; CabbageObstaclesImpl: CEDAR PROGRAM IMPORTS Cabbage EXPORTS CabbageObstacles = { 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]]]}; 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}; 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}; 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] ~ { 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}; FindUpperRange: PUBLIC PROC [adjustedRange: Connections.Range, obstacles: CabbageObstacles.BitTable] RETURNS [newRange: Connections.Range] ~ { 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}; FindMiddleRange: PUBLIC PROC [adjustedRange: Connections.Range, obstacles: CabbageObstacles.BitTable] RETURNS [newRange: Connections.Range] ~ { 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