<> <> <> <> <> <> <<>> DIRECTORY Cabbage, CabbageObstacles, Connections, DABasics; CabbageObstaclesImpl: CEDAR PROGRAM IMPORTS Cabbage EXPORTS CabbageObstacles = { <> <<-- 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] ~ { <