DIRECTORY DABasics, Cabbage, CD, Connections, Core, Rope, Route, RTBasic; CabbageObstacles: CEDAR DEFINITIONS = BEGIN 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 CreateBitTable: PROC [min, max: INT, bitSize: NAT] RETURNS [bitTable: BitTable]; Insert: PROC [obstacles: BitTable, range: Connections.Range, spacing: INT]; FindLowerRange: PROC [adjustedRange: Connections.Range, obstacles: BitTable] RETURNS [newRange: Connections.Range]; FindUpperRange: PROC [adjustedRange: Connections.Range, obstacles: BitTable] RETURNS [newRange: Connections.Range]; FindMiddleRange: PROC [adjustedRange: Connections.Range, obstacles: BitTable] RETURNS [newRange: Connections.Range]; END. άCabbageObstacles.mesa Copyright Σ 1987 by Xerox Corporation. All rights reserved. by Bryan Preas, September 14, 1987 10:30:41 pm PDT -- 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] -- Bloat range by a spacing on each side on insertion; there is space here, you know it! 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 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 find a neRange were pin is not hidden by a pin in obstacles and does not interfere with existing pin Κˆ˜šœ™Jšœ<™