DIRECTORY Asserting, Basics, 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 [
size2: Size2,
size: INT--P size2--,
nrp: INT--number of roled ports--,
ties: Set,
toTie: ARRAY End OF RefTable--side of joint _ Port _ Tie--,
toRole: ARRAY End OF RefTable--side _ port _ roledPort--,
roles: VarRefSeq--index _ roledPort--
];

Tie: TYPE = REF TiePrivate;
TiePrivate: TYPE = RECORD [
ports: RoledPortDataList _ NIL,
n: INT--number of roledPorts in this tie-- _ 0,
mindex: INT--smallest index among this ties ports-- _ 0,
completion: Completion _ NIL
];

RoledPortDataList: TYPE = LIST OF RoledPortData;
RoledPortData: TYPE = REF RoledPortDataPrivate;
RoledPortDataPrivate: TYPE = RECORD [
port: Port,
side: End,
index: NAT,
links: Links _ NIL
];

RoledPort: TYPE = RECORD [side: End, port: Port];

Links: TYPE = REF LinksPrivate;
LinksPrivate: TYPE = RECORD [
linkSize: NAT,
negLinkSize, negLgLinksPerWord: INTEGER,
lgLinksPerWord: Sublg,
words: SEQUENCE length: NAT OF WORD
];

GetRoot: PROC [j: Joint, rp: RoledPortData, cji: NAT] RETURNS [root: NAT];
GetNext: PROC [j: Joint, rp: RoledPortData, cji: NAT] RETURNS [next: NAT];

Sublg: TYPE = NAT [0 .. Basics.logBitsPerWord];

Completion: TYPE = REF CompletionPrivate;
CompletionPrivate: TYPE = RECORD [
nIncomplete: INT _ 0,
complete: PACKED SEQUENCE length: NAT OF BOOL
];

GetArrayJoint: PROC [a: Array, d: Dim, phase: ArrayIndex] RETURNS [j: Joint]
= INLINE {j _ NARROW[a.joints[d][ArrayJointIndex[a, phase]]]};
ArrayJointIndex: PROC [a: Array, phase: ArrayIndex] RETURNS [i: INT] = INLINE {i _ 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]]};

VarRefSeq: TYPE = REF VarRefSequence;
VarRefSequence: TYPE = RECORD [
length: NAT,
refs: RefSeq];

CreateVarRefSeq: PROC [size: NAT _ 12] RETURNS [vrs: VarRefSeq]
= INLINE {vrs _ NEW [VarRefSequence _ [0, CreateRefSeq[size]]]};

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};

FloorDiv: PROC [num, den: INT] RETURNS [quot: INT];
CeilDiv: PROC [num, den: INT] RETURNS [quot: INT];

END.
NLichenDataStructure.Mesa
Last Edited by: Spreitzer, June 18, 1986 5:29:04 pm PDT
Mike Spreitzer June 22, 1986 8:52:49 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.
words[cji ShiftRight lgLinksPerWord] ShiftRight (linkSize*(cji MaskLast lgLinksPerWord)) MaskLast linkSize gives index of another roledPort connected to this one at ji
where:
cji = <size[Foo], size[Bar]> T <ji[Foo], ji[Bar]>
`T' is APL's `decode'
size is the number of instances of the containing joint
ji is the index of a particular instance of the joint
complete[cji] W all connections present at instance ji of containing joint
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™7K™+—K˜KšΟk	œC˜LK˜šΠbxœœ
˜&Kšœ˜!K˜Kšœ
œ˜K˜KšΠblœœ
Οcœ
˜$K˜KšŸœœœœ
œœ˜?K˜KšŸœœœœ
œœ˜<K˜Kšœœœ
œ
œ
œ
˜Kš
œœœ
œ
œ
˜Kšœœœ
˜Kš	œ
œœ
œ
œ
˜Kšœœ˜(K˜Kšœ
œ˜!šΟnœœ
œ˜+Kšœœ˜#—K˜Kšœ
œ˜$š‘œœ
œ˜+Kšœœ˜&—K˜Kšœ	œ˜$Kšœ
œ˜$Kšœœ
œ˜<Kšœœ	œ
œ
˜%K˜Kšœœœ
˜Kšœœ˜K˜š‘œœœœ˜EKšœœœœ˜9—K˜Kšœœœ˜!šœœœ˜K˜Kšœœ
˜Kšœ
œœ˜—K˜Kšœ
œ '˜7Kš‘œœœ
œœ
œœœœœ˜jK˜Kšœœœ˜/šœœœ˜%Kš‘œœœ
œœœ˜;Kšœœ
œ˜K˜—K˜Kš‘œœ‘œœ
˜DK˜Kšœœœ˜'šœœœ˜!Kš‘œœ˜K˜—K˜Kšœ
œœ˜%šœœœ˜ K˜K˜
Kšœœœ
˜(šœœœ
˜K™—Kšœ
œ
˜Kšœœ
˜!Kšœœ
˜Kšœ,œ
˜0Kšœ"œ
˜&Kšœ
œ œ
˜+Kšœ(œ
˜,Kš
œ˜—K˜Kš‘œœ‘œœ	˜@Kš‘œœ‘œœ˜LKš‘œœ‘œœ
˜EK˜šœœ
˜KšœΟm
œ
’
œ™(—K˜Kšœ
œœ
œ˜Kšœœœ
˜šœ
œœ˜K˜K˜Kšœœ
 œ
˜*Kšœ
œ
˜Kšœœ
˜Kš
œ˜—K˜Kš‘œœœ˜<š‘œœœ˜7Kšœœ˜#—š‘
œœœ˜9Kšœœ˜ —K˜Kš‘	œœœ	œ˜;Kš‘œœœœ˜?K˜Kšœ
œœ˜+šœœœ˜#Kšœœ
˜Kšœ œœ
˜1šœœ
 ,˜GKš
œ3™3K™8K™#—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šœœœ˜,Kšœœœ˜4Kšœœœ˜$K˜Kš‘	œœœ	œ˜;Kš‘œœœœ˜?Kš‘œœ‘œœ˜Pš‘œœœ˜9Kšœœ˜%—š‘
œœœ˜9Kšœœ˜ —K˜Kšœœœ
˜šœ
œœ˜Kšœœœ
œ˜DKšœ *˜5Kš
œ˜—K˜Kšœœ˜,Kšœœœ;˜eK˜Kšœ œœ
 œ
˜5Kš
œ˜K˜š‘œœ
‘œœœœ
œœ
œ˜”
K™—Kš‘œœ
‘œœœœ
œœ
œ˜”
Kš‘œœ
‘œœ˜OKš‘œœ‘œœ˜MKš‘œœ‘œœ˜MKš‘œœ
‘œœœœ
œœ
œ˜yKš‘œœ3œ
˜dKš‘œœ3œ˜gKš‘œœ œ˜PKš‘œœœ
˜6K˜Kšœœ˜'K˜Kšœœœ˜šœœœ˜Kšœœ
˜Kšœ!œ
˜%Kšœœ˜Kš
œœ œ
œ œœ
œ˜NKšœœ˜šœ Πcm
 £
 œ
˜IKš
œ™—šœ £
 £
 
œ˜9Kš
œO™O—K˜—K˜Kšœ 
œœ˜!Kšœ
œœ˜2K˜Kš	œœœœ
œ
˜Kšœœœœ˜,Kšœœœœ˜"K˜Kšœœœ˜šœœœ˜K˜
Kšœ Πcg
 œ
˜Kšœ œ
˜"K˜
Kšœœœ	 £
 £
 œ
˜;Kšœœœ	 £
 £
 œ
˜9Kšœ £
 ˜%K˜—K˜Kšœœœ˜šœœœ˜Kšœœ
˜Kšœ $œ˜/Kšœ (œ˜8Kšœ˜K˜—K˜Kšœœœ
œ˜0Kšœœœ˜/šœœœ˜%K˜K˜
Kšœœ
˜Kšœ˜K˜—K˜Kšœœœ˜1K˜Kšœœœ˜šœœœ˜Kšœ
œ
˜Kšœ œ
˜(Kš
œ˜Kšœœ	œ
œ
˜#K˜Kš
Ϥ
™§
š
œ™Kšœ’
œ™1Kšœ
’
œ™K™7K™5——K˜Kš
‘œœ$œœœ˜JKš
‘œœ$œœœ˜JK˜Kšœœœ˜/K˜Kšœœœ˜)šœœœ˜"Kšœ
œ˜Kš
œ
œ
œ	œ
œ
˜-K˜Kšœ’
œ;™J—K˜š‘
œœ'œ˜LKšœœœ*˜>—Kš
‘œœœœœ3˜€
K˜Kš	œ	œœ
œ
 Aœ
˜ZKš
œ˜Kš
œ˜Kšœœœ˜/šœœœ˜#š
œ	œ œ
œ
œ œ
œ˜6Kšœ’
œ’
œ#™BKš
œ3™3—š	œ
œœ
œœ˜1Kšœ$’
œœ
’
œœ
œœ
œ™T—Kšœœ	œ
œ˜%—K˜Kšœœ˜Kšœ
œœ˜4K˜Kš	œœœœ
œ˜6K˜Kšœœœ˜=Kšœœœœ
œœ˜MKšœœ £
 œ
˜?Kšœœœ
œ
™,Kšœ
œœ™5Kš	œœœœ
œ
˜$K˜Kš‘œœ)œ˜UK˜Kšœœœ
˜šœ
œœ˜Kšœœ	œ
œ
œ
œ˜'—K˜š‘œœœœ
˜2Kšœœœ˜'—K˜Kšœœœ˜%šœœœ˜Kšœœ
˜K˜—K˜š‘œœœœ˜?Kšœœœ-˜@—K˜Kšœ	œœ˜!Kšœœœœ
œ	œ
œ
œ˜HK˜š‘
œœœœœœ˜FKšœœœœœ
œœœ˜X—K˜Kš
‘œœœœœ˜3Kš
‘œœœœœ˜2K˜Kšœ
˜——…—%ή:f