CabbageObstacles.mesa
Copyright Ó 1987 by Xerox Corporation. All rights reserved.
by Bryan Preas, September 14, 1987 10:30:41 pm PDT
DIRECTORY
DABasics, Cabbage, CD, Connections, Core, Rope, Route, RTBasic;
CabbageObstacles:
CEDAR
DEFINITIONS =
BEGIN
-- 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
BitTable: TYPE = REF BitTableRec;
BitTableRec:
TYPE =
RECORD[
bitSize: NAT ← 8, -- DABasics.Number per lambdas
min, max: INT ← 0, -- outerRange
bits: PACKED SEQUENCE size: NAT OF BOOL]; -- TRUE=busy
-- [outerRange.min..outerRange.max] must map into [0..obstacles.size-1]
CreateBitTable:
PROC [min, max:
INT, bitSize:
NAT]
RETURNS [bitTable: BitTable];
-- Bloat range by a spacing on each side on insertion; there is space here, you know it!
Insert: PROC [obstacles: BitTable, range: Connections.Range, spacing: INT];
FindLowerRange:
PROC [adjustedRange: Connections.Range, obstacles: 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
FindUpperRange:
PROC [adjustedRange: Connections.Range, obstacles: 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
FindMiddleRange:
PROC [adjustedRange: Connections.Range, obstacles: 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
END.