DIRECTORY Asserting, HashTable, IntHashTable, LichenSetTheory, Rope; LichenDataStructure: CEDAR DEFINITIONS IMPORTS HashTable, IntHashTable = BEGIN OPEN LichenSetTheory; nyet: ERROR --not yet implemented--; Warning: SIGNAL [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL]; Error: ERROR [msg: ROPE, v1, v2, v3, v4, v5: REF ANY _ NIL]; LORA: TYPE = LIST OF REF ANY; LOLORA: TYPE = LIST OF LORA; ROPE: TYPE = Rope.ROPE; RopeList: TYPE = LIST OF ROPE; Assertions: TYPE = Asserting.Assertions; RefTable: TYPE = HashTable.Table; CreateRefTable: PROC RETURNS [rt: RefTable] = INLINE {rt _ HashTable.Create[]}; IntTable: TYPE = IntHashTable.Table; CreateIntTable: PROC RETURNS [it: IntTable] = INLINE {it _ IntHashTable.Create[]}; GraphID: TYPE = {A, B, Unspecified}; RealGraphID: TYPE = GraphID[A .. B]; OtherGraph: ARRAY RealGraphID OF RealGraphID = [A: B, B: A]; graphIDToRope: ARRAY GraphID OF ROPE; Color: TYPE = INT; noColor: Color = LAST[Color]; someColor: Color = 871; FilterColor: PROC [color: Color] RETURNS [filtered: Color] = INLINE { filtered _ IF color # noColor THEN color ELSE someColor}; Design: TYPE = REF DesignPrivate; DesignPrivate: TYPE = RECORD [ cellTypes: Set, other: Assertions _ NIL, allKnown: BOOL _ FALSE]; nameReln: ATOM; --relative to narrowest enclosing scope Describe: PROC [subject: REF ANY, relativeTo: REF ANY _ NIL, nameGen: NameGenerator _ NIL] RETURNS [ROPE]; NameGenerator: TYPE = REF NameGeneratorPrivate; NameGeneratorPrivate: TYPE = RECORD [ GenerateName: PROC [data, subject: REF ANY] RETURNS [ROPE], data: REF ANY _ NIL ]; EnumerateCellTypes: PROC [design: Design, Consume: PROC [CellType]]; CellClass: TYPE = REF CellClassPrivate; CellClassPrivate: TYPE = RECORD [ DefinePrivates: PROC [CellType] ]; CellType: TYPE = REF CellTypePrivate; CellTypePrivate: TYPE = RECORD [ class: CellClass, designs: Set, publicKnown, privateKnown: BOOL _ FALSE, wasntNormalized: BOOL _ FALSE, port: Port _ NIL, asUnorganized: Unorganized _ NIL, asArray: Array _ NIL, firstInstance, lastInstance: CellInstance _ NIL, firstArray, lastArray: CellType _ NIL, useCount: INT _ 0 --#instances + #arrays--, otherPublic, otherPrivate: Assertions _ NIL, color: Color _ noColor]; EnumeratePorts: PROC [cellType: CellType, Consume: PROC [Port]]; EnumerateInstances: PROC [cellType: CellType, Consume: PROC [CellInstance]]; EnumerateArrays: PROC [cellType: CellType, Consume: PROC [CellType]]; partsByNameKey: ATOM; PortList: TYPE = LIST OF Port; Port: TYPE = REF PortPrivate; PortPrivate: TYPE = RECORD [ next, prev: Port, firstChild, lastChild: Port, parent: REF ANY--UNION [Port, CellType]--, wire: Wire _ NIL, other: Assertions _ NIL, color: Color _ noColor]; PortCCT: PROC [port: Port] RETURNS [containingCT: CellType]; FirstChildPort: PROC [port: Port] RETURNS [child: Port] = INLINE {child _ port.firstChild}; NextChildPort: PROC [child: Port] RETURNS [sibling: Port] = INLINE {sibling _ child.next}; PortIndex: PROC [parent, child: Port] RETURNS [index: INT]; SubPort: PROC [parent: Port, index: INT] RETURNS [child: Port]; Unorganized: TYPE = REF UnorganizedPrivate; UnorganizedPrivate: TYPE = RECORD [ internalWire: Wire _ NIL, containedInstances: Set--of CellInstance-- _ NIL, mirror: CellInstance _ NIL --the outside world, as seen from the inside ]; Vertex: TYPE = REF VertexPrivate; VertexPrivate: TYPE = RECORD [ containingCT: CellType, QNext: Vertex _ notInQ, colorNext, equiv: Vertex _ NIL, firstEdge, lastEdge: Edge _ NIL, other: Assertions _ NIL, oldColor, curColor: Color _ noColor, graph: GraphID _ Unspecified, unique, suspect: BOOL _ FALSE, variant: SELECT class: VertexClass FROM cell => [ type: CellType _ NIL, nextInstance, prevInstance: CellInstance _ NIL ], intermediate => [ port: Port ], wire => [ containingWire: Wire _ NIL, next, prev: Wire _ NIL, --Siblings firstChild, lastChild: Wire _ NIL ], ENDCASE]; VertexClass: TYPE = {cell, intermediate, wire}; CellInstance: TYPE = REF cell VertexPrivate; Intermediary: TYPE = REF intermediate VertexPrivate; Wire: TYPE = REF wire VertexPrivate; WireIndex: PROC [parent, child: Wire] RETURNS [index: INT]; SubWire: PROC [parent: Wire, index: INT] RETURNS [child: Wire]; EnumeratePortAndWire: PROC [port: Port, wire: Wire, Consume: PROC [Port, Wire]]; FirstChildWire: PROC [parent: Wire] RETURNS [child: Wire] = INLINE {child _ parent.firstChild}; NextChildWire: PROC [child: Wire] RETURNS [sibling: Wire] = INLINE {sibling _ child.next}; Edge: TYPE = REF EdgePrivate; EdgePrivate: TYPE = RECORD [ sides: ARRAY GraphDirection OF RECORD [v: Vertex, next, prev: Edge], port: Port --what the wireward vertex is connected to ]; GraphDirection: TYPE = {cellward, wireward}; OppositeDirection: ARRAY GraphDirection OF GraphDirection = [cellward: wireward, wireward: cellward]; notInQ: Vertex --don't look:-- = NIL --you looked!--; endOfQ: Vertex; EnumerateImmediateEdges: PROC [v: Vertex, Consume: PROC [Port, Vertex, Edge], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], order: Order _ any]; EnumerateImmediateConnections: PROC [v: Vertex, Consume: PROC [Port, Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE], order: Order _ any]; EnumerateTransitiveConnections: PROC [v: Vertex, Consume: PROC [Port, Vertex]]; EnumerateTopEdges: PROC [ci: CellInstance, Consume: PROC [Port, Wire, Edge]]; EnumerateTopConnections: PROC [ci: CellInstance, Consume: PROC [Port, Wire]]; EnumerateNeighboringVertices: PROC [v: Vertex, Consume: PROC [Vertex], filter: ARRAY GraphDirection OF BOOL _ ALL[TRUE]]; FindImmediateConnection: PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex]; FindImmediateEdge: PROC [cellward: Vertex, port: Port, hint: Order _ any] RETURNS [w: Vertex, e: Edge]; FindTransitiveConnection: PROC [cellward: Vertex, port: Port] RETURNS [w: Wire]; ImParent: PROC [im: Intermediary] RETURNS [v: Vertex]; Order: TYPE = {forward, backward, any}; Array: TYPE = REF ArrayPrivate; ArrayPrivate: TYPE = RECORD [ eltType: CellType _ NIL, nextArray, prevArray: CellType _ NIL, size: Size2 _ ALL[1], joints: ARRAY Dim--in which we are joining-- OF RefSeq--of Joint-- _ ALL[NIL], jointsPeriod: Size2 _ ALL[1], portConnections: RefTable--ap B array.port _ apc: ArrayPortConnections--, porting: RefTable--ep B eltType.port _ p: Porting-- _ NIL ]; Dim--ension--: TYPE = {Foo, Bar}; OtherDim: ARRAY Dim OF Dim = [Foo: Bar, Bar: Foo]; Size2: TYPE = ARRAY Dim OF INT; Range: TYPE = RECORD [min, maxPlusOne: INT]; Range2: TYPE = ARRAY Dim OF Range; Joint: TYPE = REF JointPrivate; JointPrivate: TYPE = RECORD [ lowToHigh, highToLow: RefTable--Port _ Port-- _ NIL, lowToIncompleteness, highToIncompleteness: RefTable--Port _ Incompleteness-- _ NIL ]; Incompleteness: TYPE = REF IncompletenessPrivate; IncompletenessPrivate: TYPE = RECORD [ nIncomplete: INT _ 0, incomplete: PACKED SEQUENCE length: NAT--composite joint index-- OF BOOL ]; GetArrayJoint: PROC [a: Array, d: Dim, phase: ArrayIndex] RETURNS [j: Joint] = INLINE {j _ NARROW[a.joints[d][phase[Foo]*a.jointsPeriod[Bar] + phase[Bar]]]}; Porting: TYPE = REF ANY --actually UNION [{notPorted, unknownPorting}, DetailedPorting]--; notPorted: Porting; unknownPorting: Porting; DetailedPorting: TYPE = REF DetailedPortingRep; DetailedPortingRep: TYPE = RECORD [ corners: ARRAY End--Foo-- OF ARRAY End--Bar-- OF Port, sideIndices: ARRAY End OF ARRAY Dim OF SideIndex, slots: SEQUENCE length: NAT OF Port]; End: TYPE = {low, high}; OtherEnd: ARRAY End OF End = [low: high, high: low]; SideIndex: TYPE = RECORD [same: BOOL, firstSlot: NAT]; ArrayPortConnections: TYPE = REF ArrayPortConnectionsPrivate; ArrayPortConnectionsPrivate: TYPE = ARRAY End OF ARRAY Dim OF SideConnection; SideConnection: TYPE = IntTable--index[other dim] _ elt Port--; ArrayIndex: TYPE = ARRAY Dim OF INT; GetArrayPort: PROC [a: Array, index: ArrayIndex, ep: Port] RETURNS [arrayPort: Port]; RefSeq: TYPE = REF RefSequence; RefSequence: TYPE = RECORD [ elts: SEQUENCE length: NAT OF REF ANY]; CreateRefSeq: PROC [len: NAT] RETURNS [rs: RefSeq] = INLINE {rs _ NEW [RefSequence[len]]}; BoolSeq: TYPE = REF BoolSequence; BoolSequence: TYPE = RECORD [elts: PACKED SEQUENCE length: NAT OF BOOL]; CreateBoolSeq: PROC [len: NAT, b0: BOOL _ FALSE] RETURNS [bs: BoolSeq] = INLINE {bs _ NEW [BoolSequence[len]]; FOR i: NAT IN [0 .. len) DO bs[i] _ b0 ENDLOOP}; END. rLichenDataStructure.Mesa Last Edited by: Spreitzer, June 12, 1986 5:23:05 pm PDT Leftover private CellType _ Mapper(ROPE _ Vertex) AM1: A mirror is not entered in containedInstances. AM2: A mirror is not counted as an instance of its type. AM3: mirror.type = mirror.container The connections to/from cells. AI1: The edges are in the following order: first, the cellward ones, if any, in any order, then the wireward ones, ordered by port. the Port is the wireward one. redundant with porting. porting[p] gives port connections for e[f, b].p, for all f, b on edge of array. e[Foo.LAST, Bar.LAST].p f a.q W porting[p].corners[high][high] = q NIL means elt port not connected to any array port. sideIndices[low][Foo] covers [f, b] , f = FIRST[Foo] & b B (FIRST[BAR] .. LAST[BAR]) ArraySocketList: TYPE = LIST OF ArraySocket; ArraySocket: TYPE = RECORD [ai: ArrayIndex, p: Port]; Э╩└Ц "cedar" styleШcodeЩJЩ7ЧKШKЪ╧k Ь;ШDKШЪ╨bxЬЭЬЭШ&KЪЭЬШ!KШKЪЭЬЭЬШKШKЪ╨blЬЭЬ╧cЬШ$KШKЪЯЬЭЬЭЬЭЬЭЬЭЬШ?KШKЪЯЬЭЬЭЬЭЬЭЬЭЬШ