DIRECTORY Asserting, IO, RedBlackTree, Rope;LichenDataStructure: 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 = RedBlackTree.Table;SymbolTableHolder: TYPE = REF SymbolTable;Assertions: TYPE = Asserting.Assertions;GraphID: TYPE = {A, B, Unspecified};RealGraphID: TYPE = GraphID[A .. B];Color: TYPE = HashTableIndex;noColor: Color = LAST[Color];HashTableIndex: TYPE = CARDINAL;NullIndex: HashTableIndex = LAST[HashTableIndex];VertexClass: TYPE = {net, cell};OtherClass: ARRAY VertexClass OF VertexClass = [net: cell, cell: net];EquivClass: TYPE = ROPE;implicitClass: EquivClass = NIL;NamesList: TYPE = LIST OF Names;Names: TYPE = RECORD [designed, unknown, progged: RopeList _ NIL];Design: TYPE = REF DesignRep;DesignRep: TYPE = RECORD [name: ROPE,cellTypesByName: SymbolTable,cellTypesByAddress: SymbolTable,other: Assertions _ NIL,allKnown, allKept: BOOL _ FALSE];CellType: TYPE = REF CellTypeRep;CellTypeRep: TYPE = RECORD [design: Design,names: Names,file: ROPE,equivClass: EquivClass _ implicitClass,color: Color _ noColor,inittedFor: NAT _ 0,publicKnown, privateKnown, wasntNormalized: BOOL _ FALSE,ports: PortS _ NIL,parts: SymbolTable _ NIL,mirror: Vertex _ NIL,	--the outside world, as seen from the insideasArray: Array _ NIL,netCount, cellCount: NAT _ 0,firstInstance, lastInstance: Vertex _ NIL,otherPublic, otherPrivate: Assertions _ NIL];PortS: TYPE = REF PortSeq;PortSeq: TYPE = RECORD [ports: SEQUENCE length: PortIndex OF Port];PortIndex: TYPE = NAT;NullPortIndex: PortIndex = LAST[PortIndex];Port: TYPE = RECORD [names: Names _ [NIL, NIL, NIL], equivClass: EquivClass _ implicitClass, netNames: RopeList _ NIL, other: Assertions _ NIL, color: Color _ noColor];AliasList: TYPE = LIST OF Alias;Alias: TYPE = REF AliasRep;AliasRep: TYPE = RECORD [name: ROPE,thing: REF ANY];VertexList: TYPE = LIST OF Vertex;Vertex: TYPE = REF VertexRep;VertexRep: TYPE = RECORD [names: Names,QNext: Vertex _ notInQ,colorNext, equiv: Vertex _ NIL,firstEdge, lastEdge: Edge _ NIL,nextInstance, prevInstance: Vertex _ NIL,type, parent: CellType _ NIL,extraConnections: SymbolTable _ NIL,other: Assertions _ NIL,oldColor, curColor: Color _ noColor,graph: GraphID _ Unspecified,class: VertexClass,unique, suspect: BOOL _ FALSE];Edge: TYPE = REF EdgeRep;EdgeRep: TYPE = RECORD [sides: ARRAY VertexClass OF RECORD [v: Vertex, next, prev: Edge],color: Color, portIndex: CARDINAL];ExtraConnection: TYPE = REF ExtraConnectionRep;ExtraConnectionRep: TYPE = RECORD [parentNet, subCell, childNet: Vertex];Array: TYPE = REF ArrayRep;ArrayRep: TYPE = RECORD [eltType: CellType,shape: ARRAY Dim OF Range,joints: ARRAY Dim--perp to joint-- OF ARRAY EO--perp to dim-- OF ARRAY EO--along dim-- OF Joint _ ALL[ALL[ALL[NIL]]],portConnections: ArrayPortConnections,porting: SEQUENCE eltPorts: PortIndex OF Porting];Dim--ension--: TYPE = {Foo, Bar};OtherDim: ARRAY Dim OF Dim = [Foo: Bar, Bar: Foo];Range: TYPE = RECORD [min, maxPlusOne: INT];EO: TYPE = {Even, Odd};OtherEO: ARRAY EO OF EO = [Even: Odd, Odd: Even];Joint: TYPE = REF JointSeq;JointSeq: TYPE = RECORD [joints: SEQUENCE eltPorts: PortIndex OF RECORD [low, high: PortIndex]];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 PortIndex,sideIndices: ARRAY End OF ARRAY Dim OF SideIndex,slots: SEQUENCE length: NAT OF PortIndex];End: TYPE = {low, high};OtherEnd: ARRAY End OF End = [low: high, high: low];SideIndex: TYPE = RECORD [same: BOOL, firstSlot: NAT];ArrayPortConnections: TYPE = REF ArrayPortConnectionSeq;ArrayPortConnectionSeq: TYPE = RECORD [SEQUENCE arrayPorts: PortIndex OF ARRAY End OF ARRAY Dim OF SideConnection];SideConnection: TYPE = RECORD [range: Range, sockets: ArraySocketList];ArraySocketList: TYPE = LIST OF ArraySocket;ArraySocket: TYPE = RECORD [ai: ArrayIndex, pi: PortIndex];ArrayIndex: TYPE = ARRAY Dim OF INT;notInQ: Vertex --don't look:-- = NIL --you looked!--;endOfQ: Vertex;Socket: TYPE = REF SocketRep;SocketRep: TYPE = RECORD [ct: CellType, portIndex: PortIndex];HashTable: TYPE = REF HashTableRep;HashTableRep: TYPE = RECORD [firstNonEmpty: HashTableIndex _ NullIndex,entries: SEQUENCE length: HashTableIndex OF HashTableEntry];HashTableEntry: TYPE = RECORD [v: Vertex _ NIL,nextNonEmpty: HashTableIndex _ NullIndex,count: ARRAY RealGraphID OF CARDINAL _ [0, 0],newColor: Color _ noColor,suspect, multicolored: BOOL _ FALSE];graphIDToRope: ARRAY GraphID OF ROPE;GetIDKey, GetAliasKey, GetECParentNet, GetECSubCell, GetECChildNet: RedBlackTree.GetKey;CompareRopes, CompareAliases, CompareByAddress, CompareECParentNet, CompareECSubCell, CompareECChildNet, CompareECSubCellThenChildNet: RedBlackTree.Compare;MirrorName: ROPE;END.  d  LichenDataStructure.MesaLast Edited by: Spreitzer, July 11, 1985 9:14:44 pm PDTAt most one of these two should be present:Fully general description:AM1: A mirror is not entered in its parent's parts table.AM2: A mirror is not linked in as an instance of its type.Counts are redundant with parts and asArray.Array assertions:AA1: Each connection between adjacent elements involves exactly one port of each element.AA2: Each port of an array connects to no more than one port of each element.AA3: For any port of an array, all of the element ports it connects to are connected by array elements.redundant with porting.porting[p] gives port connections for e[f, b].p, for all f, b on edge of array.e[i].pl f e[i+1].ph W j[pl].high = ph & j[ph].low = ple[i].pl not connected to any e[i+1].ph W j[pl].high = NullPortIndexe[Foo.LAST, Bar.LAST].p f a.q W porting[p].corners[high][high] = qNullPortIndex means elt port not connected to any array port.sideIndices[low][Foo] covers [f, b] , f = FIRST[Foo] & b B (FIRST[BAR] .. LAST[BAR])newColor and multicolored are indexed by oldColor; the rest by curColor.Э╩5  Ц"cedar" styleШ IcodeЩJЩ7KШ KЪ╧k	ЬЭЬШ,KШ Ъ╨bxЬЭЬЭЬШ(KШ KЪЭШKШ KЪЭЬЭЬЭЬЭЬЭЬЭЬШKЪ
ЭЬЭЬЭЬЭЬЭЬШKЪЭЬЭЬЭЬШKЪ	Ь
ЭЬЭЬЭЬЭЬШKЪЬЭЬШ'KЪЬЭЬЭЬШ*KЪЬЭЬШ(KШ KЪЬ	ЭЬЭЬЭЬШ$KЪЬЭЬЭЬЭЬШ$KЪЬЭЬШKЪЬЭЬШKЪЬЭЬЭЬШ KЪЬЭЬШ1KЪЬЭЬШ KЪЬЭЬЭЬ&ШFKЪЬЭЬЭЬШKЪЬЭЬШ KШ KЪЬЭЬЭЬЭЬШ KЪЬЭЬЭЬ)ЭЬШBKШ KЪЬЭЬЭЬШЪЬЭЬЭЬШKЪЬЭЬШKШKШ KЪЬЭЬШKЪЬЭЬЭШKШЧKШ KЪЬ
ЭЬЭЬШ!ЪЬЭЬЭЬШKШKЪЬШKЪЬЭЬШKЪЬ'Ш'KШKЪЬЭЬШKЪЬ,ЭЬЭЬШ9KЪЬЭЬШЩ+ЩKЪЬЭЬШЪЬЭЬ╧c,ШBKЩ9KЩ:ЧЧKЪЬЭЬШЧЪЬЭЬШKЩ,ЧKЪЬ&ЭЬШ*KЪЬ(ЭЬШ-ЧKШ KЪЬЭЬЭЬ	ШKЪ	Ь	ЭЬЭЬ	ЭЬЭЬШCKЪЬЭЬЭЬШKЪЬЭЬШ+KШ KЪЬЭЬЭЬЭЬЭЬЭЬ@ЭЬЭЬШиKШ KЪЬЭЬЭЬЭЬШ KЪЬЭЬЭЬ
ШЪЬ
ЭЬЭЬШKЪЬЭЬШKЪЬЭЬЭЬШЧKШ KЪЬЭЬЭЬЭЬШ"KЪЬЭЬЭЬШЪЬЭЬЭЬШKЪЬШKШKЪЬЭЬШKЪЬЭЬШ KЪЬ%ЭЬШ)KЪЬЭЬШKЪЬ ЭЬШ$KЪЬЭЬШKШ$KЪЬШKШKЪЬЭЬЭЬШЧKШ KЪЬЭЬЭЬ	ШЪЬ	ЭЬЭЬШKЪЬЭЬЭЬЭЬШAKЪЬЭЬШ#ЧKШ KЪЬЭЬЭЬШ/KЪЬЭЬЭЬ(ШIKШ ЩKЩYKЩMKЩgЧKШ KЪЬЭЬЭЬ
ШЪЬ
ЭЬЭЬШKШKЪЬЭЬЭЬШKЪЬЭЬЯЬЭЬЭЬЭЯЬЭЬЭЬЭЯЬЭЬ	ЭЬЭЬЭЬЭЬШuШ&KЪЬЩЧЪЬ	ЭЬЭЬШ0KЪЬOЩOЧKШЧKШ KЪЬЯ
ЬЭЬШ!KЪЬ
ЭЬЭЬШ2KЪЬЭЬЭЬЭЬШ,KЪЭЬЭЬШKЪ	Ь	ЭЬЭЬЭЬЭЬШ1KЪЬЭЬЭЬ
ШЪЬ
ЭЬЭЬ
ЭЬЭЬЭЬШ`KЪЬ╧mЬаЬ!Щ6KЪЬ'аЬЩCЧKШ KЪ	Ь	ЭЬЭЬЭЬЯAЬШZKЪЬШKЪЬШKЪЬЭЬЭЬШ/ЪЬЭЬЭЬШ#ЪЬ	ЭЬЯЬЭЬЭЬЯЬЭЬШ;KЪЬаЬаЬ#ЩBKЪЬ=Щ=ЧЪ	ЬЭЬЭЬЭЬЭЬШ1KЪЬ$аЬЭЬ
аЬЭЬЭЬЭЬЭЬЩTЧKЪЬЭЬ	ЭЬЭЬШ*ЧKШ KЪЬЭЬШKЪЬ
ЭЬЭЬШ4KШ KЪ	ЬЭЬЭЬЭЬЭЬШ6KШ KЪЬЭЬЭЬШ8KЪЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬЭЬШsKЪЬЭЬЭЬ*ШGKЪЬЭЬЭЬЭЬШ,KЪЬЭЬЭЬ!Ш;KЪ	ЬЭЬЭЬЭЬЭЬШ$KШ KЪЬЯЬЭЬЯЬШ5KЪЬШKШ KЪЬЭЬЭЬШKЪЬЭЬЭЬ&Ш>KШ KЪЬЭЬЭЬШ#ЪЬЭЬЭЬШKЪЬ*Ш*KЪЬ	ЭЬЭЬШ<ЧKШ ЪЬЭЬЭЬШKЪЬЭЬШKЪЬ)Ш)KЪЬЭЬЭЬЭЬ
Ш.KШKЪЬЭЬЭШ#KШKЪЬHЩHЧKШ KЪЬЭЬ	ЭЬЭЬШ%KШ KШXKЪЬЬШЬKШ KЪЬЭЬШKШ KЪЭЬШЧЧ ЕЧ    ╓   o  