-- 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.
e6(635)\158b6B479b14B185b6B70i71I4i65I4i69I38i74I437b10B63i53I3i67I3i17I115i51I213i31I56i18I117i77I5i77I5i42I91i38I74i18I74i35I121i39I229i18I252i35I119i13I32i10I30i23I52i9I43i25I102i42I107b11B1076b12B519b10B51i57I305b11B615b19B545b16B262b16B241b12B292b13B33i40I158b13B33i24I131b13B31i38I326b14B30i39I38i82I96i37I130b10B77b9B70b6B877b10B60b12B47i38I169i39I