-- File: DisjointGather.mesa
-- Finds similar cells
-- Written by Martin Newell/Dan Fitzpatrick February 1981
-- Last edited (Pilot): August 6, 1981 3:47 PM

DIRECTORY

DisjointGatherDefs: FROM "DisjointGatherDefs",
DisjointSplitDefs: FROM "DisjointSplitDefs" USING [Split],
DisjointTypes: FROM "DisjointTypes" USING [DisCell, Instance, Rectangle, Symbol, PIP, Geometry],
DisjointAllocDefs: FROM "DisjointAllocDefs" USING [AllocateInstance, AllocateSymbol, FreeInstance, FreeSymbol, FreeRectangle, FreeDisCell, FreePIP, AllocateGeometry, FreeGeometry, Alloc, Free],
Inline: FROM "Inline" USING [LowHalf],
Real: FROM "Real" USING [Fix];

DisjointGather: PROGRAM
IMPORTS DisjointSplitDefs, DisjointAllocDefs, Inline, Real
EXPORTS DisjointGatherDefs =
BEGIN
OPEN DisjointTypes, DisjointSplitDefs, DisjointAllocDefs, Inline, Real;

Gather: PUBLIC PROCEDURE[symbol: Symbol, DisCellList: DisCell] =
BEGIN
-- for each cell in the discell list, see if a Instance has been defined,
-- if not create a new Instance and hash it into the InstanceTable.
-- then create Instance pointing to the Instance with the correct offset
next: DisCell;
tmp,ptr: SCell;
-- hold instances previously attached to symbol so DisCells can point to them
HoldInstList[symbol.insts];
symbol.insts ← NIL;
FOR a: DisCell ← DisCellList, next UNTIL a = NIL DO
x: REAL;
y: REAL;
usymb: Symbol;
next ← a.next;
x ← a.windows.l; -- find offset
y ← a.windows.b;
usymb ← FindSymbol[a,x,y];
MakeInstance[usymb,x,y,symbol];
ENDLOOP;
ptr ← SCellList;
SCellList ← NIL;
FOR ptr ← ptr,tmp UNTIL ptr = NIL DO
tmp ← ptr.next;
Expand[ptr.symbol];
FreeSCell[ptr];
ENDLOOP;
END;

FindSymbol: PROCEDURE[dc:DisCell, x,y: REAL] RETURNS[usymb: Symbol] =
-- Returns a pointer to a Instance in the symbol table,
-- creating one if necessary, which corresponds with the DisCell ’dc’
-- relative to x & y
BEGIN
found: BOOLEAN;
hash: INTEGER ← 0;

SortDisCell[dc];
usymb ← AllocateSymbol[];
usymb.insts ← NIL;
-- create list of instances with their relative offset
FOR b:PIP ← dc.insts,b.next UNTIL b = NIL DO
desc: Instance ← AllocateInstance[];
desc↑ ← [
next: NIL,
symbol: b.inst.symbol,
xOffset: b.inst.xOffset - x,
yOffset: b.inst.yOffset - y
];

-- add desc into usymb’s desc list
desc.next ← usymb.insts;
usymb.insts ← desc;

-- make hash function
hash ← hash + (LowHalf[desc.symbol] +
LowHalf[Fix[3*(desc.xOffset)]+Fix[13*(desc.yOffset)]]);
ENDLOOP;
-- can let new symbol point to window list since neither DisCells or window will
-- change the contents of the window list. (Free window list if found dc already
-- in DisCell table and freeing new symbol.)
usymb.windows ← dc.windows;
FOR b:Rectangle ← usymb.windows,b.next UNTIL b = NIL DO
-- make windows relative to symbol origin
b.l ← b.l - x;
b.b ← b.b - y;
b.r ← b.r - x;
b.t ← b.t - y;
-- make hash function
hash ← hash + LowHalf[Fix[b.l + 5*b.b + 11*b.r + b.t]];
ENDLOOP;
-- Add geometry of symbol from DisCell
usymb.geom ← NIL;
FOR gptr: Geometry ← dc.geom,gptr.next UNTIL gptr = NIL DO
g: Geometry ← AllocateGeometry[];
-- make geometry relative to symbol origin
gptr.l ← gptr.l - x;
gptr.b ← gptr.b - y;
gptr.r ← gptr.r - x;
gptr.t ← gptr.t - y;
g↑ ← [
next: usymb.geom,
layer: gptr.layer,
l: gptr.l,
b: gptr.b,
r: gptr.r,
t: gptr.t
];
usymb.geom ← g;
-- make hash function
hash ← hash + LowHalf[Fix[g.l + g.b + g.r + 7*g.t + 17*g.layer]];
ENDLOOP;
found ← FALSE;
hash ← ABS[hash MOD TblSize];
FOR ptr:DisCell ← DisCellTable[hash],ptr.next UNTIL ptr = NIL DO
IF SameDisCell[dc,ptr] THEN {
next: Rectangle;
-- Free windows attached to usymb & dc
FOR w:Rectangle ← usymb.windows, next UNTIL w = NIL DO
next ← w.next;
FreeRectangle[w];
ENDLOOP;
-- release usymb
ReleaseSymbol[usymb];
-- release dc
ReleaseDisCell[dc];
-- make usymb point to ptr
usymb ← ptr.symbol;
found ← TRUE;
EXIT; --this loop
}
ENDLOOP;
IF NOT found THEN {
-- add usymb to Symbol Table
sCell: SCell;
dc.symbol ← usymb;
dc.next ← DisCellTable[hash];
DisCellTable[hash] ← dc;
-- also mark this symbol to be expanded later
sCell ← AllocSCell[];
sCell.next ← SCellList;
SCellList ← sCell;
sCell.symbol ← usymb;
}
END;

SameDisCell: PROCEDURE[dc1,dc2: DisCell] RETURNS[BOOLEAN] =
BEGIN
--Returns true if us1 and us2 represent same comibnation of primInstances
-- and window boxes are the same
pip1: PIP ← dc1.insts;
pip2: PIP ← dc2.insts;
xOffset: REAL ← pip2.inst.xOffset - pip1.inst.xOffset;
yOffset: REAL ← pip2.inst.yOffset - pip1.inst.yOffset;
IF pip1.inst.symbol # pip2.inst.symbol THEN RETURN[FALSE];
-- first symbols are the same, check the rest of the symbols and their
-- relative offsets.
pip1 ← pip1.next;pip2 ← pip2.next;
UNTIL pip1 = NIL DO
IF pip2 = NIL THEN RETURN[FALSE];
IF pip1.inst.symbol # pip2.inst.symbol THEN RETURN[FALSE];
IF pip1.inst.xOffset # pip2.inst.xOffset - xOffset THEN RETURN[FALSE];
IF pip1.inst.yOffset # pip2.inst.yOffset - yOffset THEN RETURN[FALSE];
pip1 ← pip1.next;pip2 ← pip2.next;
ENDLOOP;
IF pip2 # NIL THEN RETURN[FALSE];
-- Now check geometry
IF NOT SameGeometry[dc1.geom,dc2.geom,xOffset,yOffset] THEN
RETURN[FALSE];
-- Now check window list
IF NOT SameWindow[dc1.windows,dc2.windows] THEN
RETURN[FALSE];
RETURN[TRUE];
END;

SameGeometry: PROCEDURE[g1,g2:Geometry, xOffset,yOffset:REAL] RETURNS[BOOLEAN] =
-- Returns true if r1 and r2 are the same list of rectangles
BEGIN
UNTIL g1 = NIL DO
IF g2 = NIL THEN RETURN[FALSE];
IF g1.layer # g2.layer THEN RETURN[FALSE];
IF g1.r # g2.r - xOffset THEN RETURN[FALSE];
IF g1.l # g2.l - xOffset THEN RETURN[FALSE];
IF g1.t # g2.t - yOffset THEN RETURN[FALSE];
IF g1.b # g2.b - yOffset THEN RETURN[FALSE];
g1 ← g1.next; g2 ← g2.next;
ENDLOOP;
IF g2 # NIL THEN RETURN[FALSE];
RETURN[TRUE];
END;

SameWindow: PROCEDURE[r1,r2:Rectangle] RETURNS[BOOLEAN] =
-- Returns true if r1 and r2 are the same list of rectangles
BEGIN
UNTIL r1 = NIL DO
IF r2 = NIL THEN RETURN[FALSE];
IF r1.r # r2.r THEN RETURN[FALSE];
IF r1.l # r2.l THEN RETURN[FALSE];
IF r1.t # r2.t THEN RETURN[FALSE];
IF r1.b # r2.b THEN RETURN[FALSE];
r1 ← r1.next; r2 ← r2.next;
ENDLOOP;
IF r2 # NIL THEN RETURN[FALSE];
RETURN[TRUE];
END;

SortDisCell: PROCEDURE[dc:DisCell] =
BEGIN
list: PIP ← NIL;
next: PIP;

-- first sort all the instances of dc onto list
FOR pip: PIP ← dc.insts,next UNTIL pip = NIL DO
next ← pip.next;
IF list=NIL OR InstanceLessThan[pip.inst,list.inst] THEN {
pip.next ← list;
list ← pip;
}
ELSE {
a:PIP;
FOR a ← list,a.next UNTIL a.next = NIL DO
IF InstanceLessThan[pip.inst,a.next.inst] THEN EXIT;
ENDLOOP;
pip.next ← a.next;
a.next ← pip;
}
ENDLOOP;
-- list is now sorted, make dc point to this list
dc.insts ← list;
-- now sort the geometry of the discell
SortDisCellGeometry[dc];
END;

SortDisCellGeometry: PROCEDURE[dc:DisCell] =
BEGIN
list: Geometry ← NIL;
next: Geometry;

-- first sort all the geometry of dc onto list
FOR rec: Geometry ← dc.geom,next UNTIL rec = NIL DO
next ← rec.next;
IF list=NIL OR GeometryLessThan[rec,list] THEN {
rec.next ← list;
list ← rec;
}
ELSE {
a:Geometry;
FOR a ← list,a.next UNTIL a.next = NIL DO
IF GeometryLessThan[rec,a.next] THEN EXIT;
ENDLOOP;
rec.next ← a.next;
a.next ← rec;
}
ENDLOOP;
-- list is now sorted, make dc point to this list
dc.geom ← list;
END;

InstanceLessThan: PROCEDURE[p1,p2:Instance] RETURNS[BOOLEAN] =
BEGIN
c1: LONG CARDINAL ← LOOPHOLE[p1.symbol];
c2: LONG CARDINAL ← LOOPHOLE[p2.symbol];
RETURN[c1<c2 OR
(c1=c2 AND (p1.xOffset<p2.xOffset OR
(p1.xOffset=p2.xOffset AND p1.yOffset<p2.yOffset)))];
END;

GeometryLessThan: PROCEDURE[g1,g2:Geometry] RETURNS[BOOLEAN] =
BEGIN
RETURN[g1.l<g2.l OR
(g1.l=g2.l AND (g1.b<g2.b OR
(g1.b=g2.b AND g1.layer<g2.layer OR
(g1.layer=g2.layer AND g1.r<g2.r OR
(g1.r=g2.r AND g1.t<g2.t)))))];
END;

MakeInstance: PROCEDURE[symb:Symbol, x,y:REAL, topSymb: Symbol] =
-- make an instance of symbol offset by x & y
-- these are instances of topSymb
BEGIN
ui: Instance;
ui ← AllocateInstance[];
ui↑ ← [
next: topSymb.insts,
symbol: symb,
xOffset: x,
yOffset: y
];
topSymb.insts ← ui;
END;

HoldInstList: PROCEDURE[inst: Instance] =
-- hold a list of Instances in InstHoldList
BEGIN
next: Instance;
FOR ptr:Instance ← inst,next UNTIL ptr = NIL DO
next ← ptr.next;
ptr.next ← InstHoldList;
InstHoldList ← ptr;
ENDLOOP;
END;

FreeInstList: PROCEDURE[inst: Instance] =
-- free a list of Instances
BEGIN
next: Instance;
FOR ptr:Instance ← inst,next UNTIL ptr = NIL DO
next ← ptr.next;
FreeInstance[ptr];
ENDLOOP;
END;

ReleaseSymbol: PROCEDURE[symb: Symbol] =
-- remove symbol, and it’s attached crude
BEGIN
--nextr: Rectangle;
nextg: Geometry;
FreeInstList[symb.insts];
--FOR ptr:Rectangle ← symb.windows,nextr UNTIL ptr = NIL DO
--nextr ← ptr.next;
--FreeRectangle[ptr];
--ENDLOOP;
FOR ptr:Geometry ← symb.geom,nextg UNTIL ptr = NIL DO
nextg ← ptr.next;
FreeGeometry[ptr];
ENDLOOP;
FreeSymbol[symb];
END;

ReleaseDisCell: PROCEDURE[dc: DisCell] =
-- remove DisCell, and it’s attached crude
BEGIN
nextp: PIP;
nextg: Geometry;
-- Free the PIP’s attached to DisCell, but not the instances pointed to by PIP’s
FOR ptr:PIP ← dc.insts,nextp UNTIL ptr = NIL DO
nextp ← ptr.next;
FreePIP[ptr];
ENDLOOP;
-- Free the geometry of the DisCell
FOR ptr:Geometry ← dc.geom,nextg UNTIL ptr = NIL DO
nextg ← ptr.next;
FreeGeometry[ptr];
ENDLOOP;
FreeDisCell[dc];
END;

AllocSCell: PROCEDURE RETURNS[SCell] =
BEGIN
RETURN[Alloc[SIZE[SCellRecord]]];
END;

FreeSCell: PROCEDURE[cell:SCell] =
BEGIN
Free[cell,SIZE[SCellRecord]];
END;

Expand: PUBLIC PROCEDURE[symb:Symbol] =
BEGIN
next: Instance;
insts: Instance ← symb.insts;
symb.insts ← NIL;
FOR insts ← insts,next UNTIL insts = NIL DO
next ← insts.next;
FOR in: Instance ← insts.symbol.insts,in.next UNTIL in = NIL DO
desc: Instance ← AllocateInstance[];
desc↑ ← [
next: symb.insts,
symbol: in.symbol,
xOffset: in.xOffset + insts.xOffset,
yOffset: in.yOffset + insts.yOffset
];
symb.insts ← desc;
ENDLOOP;
-- Add geometry of symbol from DisCell
FOR gptr: Geometry ← insts.symbol.geom,gptr.next UNTIL gptr = NIL DO
g: Geometry ← AllocateGeometry[];
g↑ ← [
next: symb.geom,
layer: gptr.layer,
l: gptr.l + insts.xOffset,
b: gptr.b + insts.yOffset,
r: gptr.r + insts.xOffset,
t: gptr.t + insts.yOffset
];
symb.geom ← g;
ENDLOOP;
FreeInstance[insts];
ENDLOOP;
Split[symb];
END;

InitGather: PUBLIC PROCEDURE =
BEGIN
DisCellTable ← ALL[NIL];
END;

FinishGather: PUBLIC PROCEDURE =
BEGIN
next: DisCell;
-- free the DisCells held in DisCellTable
FOR i: CARDINAL IN [0..TblSize) DO
FOR ptr: DisCell ← DisCellTable[i],next UNTIL ptr = NIL DO
next ← ptr.next;
ReleaseDisCell[ptr];
ENDLOOP;
ENDLOOP;
-- free the Instances held in InstHoldList
FreeInstList[InstHoldList];
END;

DisCellTable: ARRAY [0..TblSize) OF DisCell;
InstHoldList: Instance ← NIL;

TblSize: CARDINAL = 512;

SCellList: SCell ← NIL;
SCell: TYPE = LONG POINTER TO SCellRecord;
SCellRecord: TYPE = RECORD [
next: SCell,
symbol: Symbol
];

InitGather[];

END.