DIRECTORY Asserting, CardHashTableThreaded, IO, Rope, SymTab; StructuralComparisonDataStructure: CEDAR DEFINITIONS = BEGIN LORA: TYPE = LIST OF REF ANY; LOLORA: TYPE = LIST OF LORA; ROPE: TYPE = Rope.ROPE; RopeList: TYPE = LIST OF ROPE; SymbolTable: TYPE ~ SymTab.Ref; Assertions: TYPE = Asserting.Assertions; ColorTable: TYPE = CardHashTableThreaded.Table; GraphID: TYPE = {A, B, Unspecified}; RealGraphID: TYPE = GraphID[A .. B]; OtherGraph: ARRAY RealGraphID OF RealGraphID = [A: B, B: A]; graphIDToRope: GraphDescriptions; GraphDescriptions: TYPE ~ ARRAY GraphID OF ROPE; RealGraphDescriptions: TYPE ~ ARRAY RealGraphID OF ROPE; Color: TYPE = CARD; noColor: Color = LAST[Color]; someColor: Color = 87654321H; FilterColor: PROC [color: Color] RETURNS [filtered: Color] = INLINE { filtered _ IF color # noColor THEN color ELSE someColor}; VertexClass: TYPE = {net, cell}; OtherClass: ARRAY VertexClass OF VertexClass = [net: cell, cell: net]; CellType: TYPE = REF CellTypeRep; CellTypeRep: TYPE = RECORD [ name: ROPE _ NIL, color: Color _ noColor, ports: PortS _ NIL, internalsKnown, destroyed: BOOL _ FALSE, firstPart: Vertex _ NIL, size: NAT _ 0, --number of parts mirror: Vertex _ NIL, --the outside world, as seen from the inside netCount, cellCount: NAT _ 0, transCounts: TransCounts _ NIL, otherPublic, otherPrivate: Assertions _ NIL]; TransCounts: TYPE ~ REF TransCountsPrivate; TransCountsPrivate: TYPE ~ RECORD [flatTransistors, flatTransMerges: INT _ 0]; IsMirror: PROC [v: Vertex] RETURNS [is: BOOL] = INLINE {is _ v.isMirror}; EnumerateParts: PROC [ct: CellType, Consume: PROC [Vertex], mirrorToo: BOOL] = INLINE { next: Vertex; FOR v: Vertex _ ct.firstPart, next WHILE v # NIL DO next _ v.nextPart; IF NOT v.deleted THEN Consume[v] ENDLOOP; IF mirrorToo THEN Consume[ct.mirror]; }; PortS: TYPE = REF PortSeq; PortSeq: TYPE = RECORD [length: PortIndex, ports: SEQUENCE size: PortIndex OF Port]; PortIndex: TYPE = NAT; NullPortIndex: PortIndex = LAST[PortIndex]; Port: TYPE = RECORD [name: ROPE _ NIL, net: Vertex _ NIL, other: Assertions _ NIL, color: Color _ noColor]; VertexList: TYPE = LIST OF Vertex; Vertex: TYPE = REF VertexRep; VertexRep: PRIVATE TYPE = RECORD [ name: ROPE, QNext: Vertex _ notInQ, nextPart: Vertex _ NIL, colorNext, equiv: Vertex _ NIL, firstEdge, lastEdge: Edge _ NIL, type: CellType _ NIL, other: Assertions _ NIL, oldColor, curColor: Color _ noColor, better: Vertex _ NIL, graph: GraphID _ Unspecified, class: VertexClass, unique, suspect, isMirror, deleted: BOOL _ FALSE]; Edge: TYPE = REF EdgeRep; EdgeRep: TYPE = RECORD [ sides: ARRAY VertexClass OF RECORD [v: Vertex, next, prev: Edge], color: Color]; notInQ: Vertex --don't look:-- = NIL --you looked!--; endOfQ: Vertex; ColorData: TYPE = REF ColorDataPrivate; ColorDataPrivate: TYPE = RECORD [ color: Color, nextColor: ColorData _ NIL, firstVertex: Vertex _ NIL, count: ARRAY RealGraphID OF CARDINAL _ [0, 0], newColor: Color _ noColor, suspect, multicolored: BOOL _ FALSE ]; EnumerateEdges: PROC [v: Vertex, Consume: PROC [Color, Vertex], includeMirror: BOOL] = INLINE { FOR e: Edge _ v.firstEdge, e.sides[v.class].next WHILE e # NIL DO w: Vertex = e.sides[OtherClass[v.class]].v; IF e.sides[v.class].v # v THEN ERROR; IF includeMirror OR NOT IsMirror[w] THEN Consume[e.color, w]; ENDLOOP; }; EnumerateFullEdges: PROC [v: Vertex, Consume: PROC [e: Edge], includeMirror: BOOL] = INLINE { nextEdge: Edge _ v.firstEdge; FOR e: Edge _ v.firstEdge, nextEdge WHILE e # NIL DO w: Vertex = e.sides[OtherClass[v.class]].v; IF e.sides[v.class].v # v THEN ERROR; nextEdge _ e.sides[v.class].next; IF includeMirror OR NOT IsMirror[w] THEN Consume[e]; ENDLOOP; }; InitialColor: PROC [v: Vertex] RETURNS [Color]; VName: PROC [v: Vertex] RETURNS [r: ROPE] = INLINE {r _ v.name}; VDead: PROC [v: Vertex] RETURNS [ded: BOOL] = INLINE {ded _ v.class = cell AND v.type.destroyed}; OldColor: PROC [v: Vertex] RETURNS [c: Color] = INLINE {c _ v.oldColor}; SetOldColor: PROC [v: Vertex, c: Color] = INLINE {v.oldColor _ c}; CurColor: PROC [v: Vertex] RETURNS [c: Color] = INLINE {c _ v.curColor}; SetCurColor: PROC [v: Vertex, c: Color] = INLINE {v.curColor _ c}; GetGraph: PROC [v: Vertex] RETURNS [g: GraphID] = INLINE {g _ v.graph}; SetGraph: PROC [v: Vertex, g: GraphID] = INLINE {v.graph _ g}; GetUnique: PROC [v: Vertex] RETURNS [b: BOOL] = INLINE {b _ v.unique}; SetUnique: PROC [v: Vertex, b: BOOL] = INLINE {v.unique _ b}; GetSuspect: PROC [v: Vertex] RETURNS [b: BOOL] = INLINE {b _ v.suspect}; SetSuspect: PROC [v: Vertex, b: BOOL] = INLINE {v.suspect _ b}; GetQNext: PROC [v: Vertex] RETURNS [w: Vertex] = INLINE {w _ v.QNext}; SetQNext: PROC [v: Vertex, w: Vertex] = INLINE {v.QNext _ w}; GetColorNext: PROC [v: Vertex] RETURNS [w: Vertex] = INLINE {w _ v.colorNext}; SetColorNext: PROC [v: Vertex, w: Vertex] = INLINE {v.colorNext _ w}; GetEquiv: PROC [v: Vertex] RETURNS [w: Vertex] = INLINE {w _ v.equiv}; SetEquiv: PROC [v: Vertex, w: Vertex] = INLINE {v.equiv _ w}; END. ‚StructuralComparisonDataStructure.Mesa Last tweaked by Mike Spreitzer on March 4, 1989 1:40:02 pm PST AM1: A mirror is not entered in its parent's parts list. AM2: A mirror is not linked in as an instance of its type. Counts are redundant with parts. Not needed for anything, just comfortning info to have. newColor and multicolored are indexed by oldColor; the rest by curColor. Κb– "cedar" style˜code™&K™>—K˜KšΟk œ#œ˜=K˜šΠbx!œœ œ˜6K˜Kš˜K˜Kš œœœœœœ˜Kš œœœœœ˜Kšœœœ˜Kš œ œœœœ˜Kšœ œ˜Kšœ œ˜(Kšœ œ˜/K˜Kšœ œœœ˜$Kšœ œ œœ˜$Kšœ œ œ˜Kš Ÿ œœ œœœ˜FKšŸ œœœœ˜=Kš Ÿ œœ œœœ˜HKšŸ œœœœ˜?K˜KšŸœœ œœ˜FKšŸœœœ˜=KšŸ œœ œœ˜NKšŸ œœœ˜EKšŸœœ œœ˜FKšŸœœœ˜=K˜Kšœ˜——…—~b