LichenArrayImpl.Mesa
Last tweaked by Mike Spreitzer on April 30, 1987 1:46:29 pm PDT
DIRECTORY Basics, Convert, GList, InterpreterOps, IntHashTable, IO, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenSetTheory, RefTab, Rope;
LichenArrayImpl: CEDAR MONITOR
IMPORTS Basics, GList, IntHashTable, LichenArrayStuff, LichenDataOps, LichenDataStructure, LichenSetTheory, RefTab
EXPORTS LichenArrayStuff, LichenDataStructure
INVARIANT
tie.completion is redundant with the information in the rpd.links.
tie.completion = NIL iff tie.completion.nIncomplete = 0.
a SidedPortData has links iff needed or array is being created.
=
BEGIN OPEN LichenSetTheory, LichenDataStructure, LichenArrayStuff, LichenDataOps;
Quit: ERROR = CODE;
PackedArrayIndex: PUBLIC TYPE = INT;
PackArrayIndex: PUBLIC PROC [ai: ArrayIndex] RETURNS [PackedArrayIndex]
= {RETURN [PackArrayIndexI[ai]]};
PackArrayIndexI: PROC [ai: ArrayIndex] RETURNS [PackedArrayIndex]
= INLINE {RETURN [LOOPHOLE[Nat2[ai[Foo], ai[Bar]]]]};
UnpackArrayIndex: PUBLIC PROC [pai: PackedArrayIndex] RETURNS [ArrayIndex]
= {RETURN [UnpackArrayIndexI[pai]]};
UnpackArrayIndexI: PROC [pai: PackedArrayIndex] RETURNS [ArrayIndex]
= INLINE {RETURN [[LOOPHOLE[pai, Nat2][Foo], LOOPHOLE[pai, Nat2][Bar]]]};
Central: PUBLIC PROC [a: Array, ai: ArrayIndex] RETURNS [BOOL] = {
RETURN [
ai[Foo] > 0 AND ai[Foo]+1 < a.size[Foo] AND
ai[Bar] > 0 AND ai[Bar]+1 < a.size[Bar]];
};
ComputeGroupingsIndex: PUBLIC PROC [a: Array, ai: ArrayIndex] RETURNS [gi2, gii2: Nat2, gi, cgii: NAT] = {
ngii: Nat2 ← [1, 1];
Gi1D: PROC [d: Dim] = {
i: INT = ai[d];
SELECT TRUE FROM
i < a.groupingParmses[d].middle.min => gi2[d] ← i;
i >= a.groupingParmses[d].middle.maxPlusOne => gi2[d] ← i + a.groupingParmses[d].d;
ENDCASE => {
t: NAT = a.jointsPeriod[d];
f: NAT = i MOD t;
jiir: Range = Range1Div[a.groupingParmses[d].middle, t, f];
gi2[d] ← a.groupingParmses[d].middle.min + f;
gii2[d] ← i/a.jointsPeriod[d] - jiir.min;
ngii[d] ← RangeLength[jiir];
}};
gii2 ← [0, 0];
Gi1D[Foo]; Gi1D[Bar];
gi ← a.groupingParmses[Bar].sum * gi2[Foo] + gi2[Bar];
cgii ← ngii[Bar] * gii2[Foo] + gii2[Bar]};
ComputeJointGroupingsIndex: PUBLIC PROC [a: Array, j: Joint, jii: Nat2] RETURNS [jgi2: Nat2, jgi, ctii: NAT, jiir: Range2] = {
njgii: Nat2 ← [1, 1];
jgii2: Nat2 ← [0, 0];
Gi1D: PROC [d: Dim] = {
i: NAT = jii[d];
jiir[d] ← [min: i, maxPlusOne: i+1];
SELECT TRUE FROM
i < j.groupingParmses[d].middle.min => jgi2[d] ← i;
i >= j.groupingParmses[d].middle.maxPlusOne => jgi2[d] ← i + j.groupingParmses[d].d;
ENDCASE => {
jgi2[d] ← j.groupingParmses[d].middle.min;
jiir[d] ← j.groupingParmses[d].middle;
jgii2[d] ← i - jgi2[d];
njgii[d] ← RangeLength[jiir[d]];
}};
Gi1D[Foo]; Gi1D[Bar];
jgi ← j.groupingParmses[Bar].sum * jgi2[Foo] + jgi2[Bar];
ctii ← njgii[Bar] * jgii2[Foo] + jgii2[Bar]};
AddTiedGroups: PROC [d: Dim, j: Joint, side: End, jgi: NAT, g: Group, to: GroupList] RETURNS [tied: GroupList] = {
IF g = NIL THEN RETURN [to];
IF FetchTie[j, side, jgi, g] # NIL THEN RETURN [CONS[g, to]];
IF g.stopLooking[d][side] THEN RETURN [to];
tied ← to;
FOR worse: GroupList ← g.worse, worse.rest WHILE worse # NIL DO
tied ← AddTiedGroups[d, j, side, jgi, worse.first, tied];
ENDLOOP;
tied ← tied;
};
AddListTiedGroups: PROC [d: Dim, j: Joint, side: End, jgi: NAT, gs, to: GroupList] RETURNS [tied: GroupList] = {
tied ← NIL;
FOR gs ← gs, gs.rest WHILE gs # NIL DO
tied ← AddTiedGroups[d, j, side, jgi, gs.first, tied];
ENDLOOP;
tied ← tied;
};
ArrayWireForGroup: PUBLIC PROC [a: Array, index: ArrayIndex, gi: NAT, g: Group, mayAdd: BOOL] RETURNS [aw: ArrayWire] ~ {
pai: PackedArrayIndex ~ PackArrayIndexI[index];
last: IntTable --PackedArrayIndex b ArrayWire-- ~ NARROW[a.toWire.Fetch[g].val];
IF g.ports=NIL THEN ERROR;
IF last # NIL THEN {
aw ← NARROW[last.Fetch[pai].value];
IF aw # NIL THEN RETURN;
};
IF NOT mayAdd THEN RETURN [NIL];
aw ← NEW [ArrayWirePrivate ← [
members: CreateHashMapper[],
ports: CreateHashSet[]
]];
IF NOT a.wires.UnionSingleton[aw] THEN ERROR;
AddEltToArrayWire[a, aw, [g, index]];
};
SetGroupInWireAt: PROC [a: Array, gi2: Nat2, g: Group, aw: ArrayWire, ai: ArrayIndex] RETURNS [news: BOOL] ~ {
air: Range2 ~ Gi2ToAir[a, gi2].air;
shape: Nat2 ~ RangeShape[air];
gii: Nat2 ~ Nat2Div[Int2SubN[ai, Range2Min[air]], a.jointsPeriod];
index: NAT ~ shape[Bar] * gii[Foo] + gii[Bar];
bs: BoolSeq ← NARROW[aw.members.Map[g]];
IF g.ports=NIL THEN ERROR;
IF bs = NIL AND NOT aw.members.PutMapping[g, bs ← CreateBoolSeq[Nat2Area[shape]]].newDomain THEN ERROR;
IF bs[index] THEN RETURN [FALSE];
{
last: IntTable --PackedArrayIndex b ArrayWire--NARROW[a.toWire.Fetch[g].val];
pai: PackedArrayIndex ~ PackArrayIndexI[ai];
IF last = NIL AND NOT a.toWire.Insert[g, last ← CreateIntTable[]] THEN ERROR;
[] ← last.Store[pai, aw];
news ← bs[index] ← TRUE;
}};
AddEltToArrayWire: PROC [a: Array, aw: ArrayWire, elt: ArrayWireElt] = {
NoteConnection: PROC [ain: ArrayIndex, gn: Group] ~ {
IF gn.ports#NIL THEN {
gi2n: Nat2 ~ ComputeGroupingsIndex[a, ain].gi2;
IF SetGroupInWireAt[a, gi2n, gn, aw, ain].news THEN stack ← CONS[[gn, ain], stack];
};
};
stack: LIST OF ArrayWireElt ← NIL;
NoteConnection[elt.ai, elt.g];
WHILE stack # NIL DO
elt: ArrayWireElt ~ stack.first;
gi: NAT ~ ComputeGroupingsIndex[a, elt.ai].gi;
stack ← stack.rest;
EnumerateLocalConnections[a, elt.ai, gi, elt.g, NoteConnection];
stack ← stack;
ENDLOOP;
stack ← stack;
};
JoinArrayWires: PROC [a: Array, aw1, aw2: ArrayWire] ~ {
MoveElt: PROC [domain, range: REF ANY] ~ {
g: Group ~ NARROW[domain];
bs: BoolSeq ~ NARROW[range];
air: Range2 ~ Gi2ToAir[a, g.gi2].air;
shape: Nat2 ~ RangeShape[air];
FOR aif: NAT ← air[Foo].min, aif+a.jointsPeriod[Foo] WHILE aif < air[Foo].maxPlusOne DO FOR aib: NAT ← air[Bar].min, aib+a.jointsPeriod[Bar] WHILE aib < air[Bar].maxPlusOne DO
ai: ArrayIndex ~ [aif, aib];
gii: Nat2 ~ Nat2Div[Int2SubN[ai, Range2Min[air]], a.jointsPeriod];
index: NAT ~ shape[Bar] * gii[Foo] + gii[Bar];
IF bs[index] THEN {
AddEltToArrayWire[a, aw1, [g, ai]];
Quit;
};
ENDLOOP ENDLOOP;
};
MovePort: PROC [ra: REF ANY] ~ {
ap: Port ~ NARROW[ra];
IF NOT aw1.ports.UnionSingleton[ap] THEN ERROR;
IF NOT a.portWire.Replace[ap, aw1] THEN ERROR;
};
aw2.members.EnumerateMap[MoveElt !Quit => CONTINUE];
aw2.ports.Enumerate[MovePort];
IF NOT a.wires.RemoveElt[aw2] THEN ERROR;
};
EnumerateLocalConnections: PROC [a: Array, index: ArrayIndex, gi: NAT, g: Group, Consume: PROC [ain: ArrayIndex, gn: Group]] = {
FOR d: Dim IN Dim DO FOR side: End IN End DO
otherSide: End = OtherEnd[side];
lai: ArrayIndex = Int2Tweak[index, d, SELECT side FROM low => 0, high => -1, ENDCASE => ERROR];
hai: ArrayIndex = Int2Tweak[lai, d, 1];
IF lai[d] < 0 OR hai[d] >= a.size[d] THEN LOOP;
{jii: Nat2 = [lai[Foo]/a.jointsPeriod[Foo], lai[Bar]/a.jointsPeriod[Bar]];
phase: Nat2 = [lai[Foo] - jii[Foo]*a.jointsPeriod[Foo], lai[Bar] - jii[Bar]*a.jointsPeriod[Bar]];
j: Joint = GetArrayJoint[a, d, phase];
jgi: NAT = ComputeJointGroupingsIndex[a, j, jii].jgi;
tie: Tie = FetchTie[j, side, jgi, g];
IF tie = NIL THEN LOOP;
IF tie.groups[side] # g THEN ERROR;
IF tie.groups[otherSide] # NIL THEN Consume[SELECT side FROM low => hai, high => lai, ENDCASE => ERROR, tie.groups[otherSide]];
}ENDLOOP ENDLOOP;
a ← a;
};
EnumerateArrays: PUBLIC PROC [cellType: CellType, Consume: PROC [CellType]] = {
FOR act: CellType ← cellType.firstArray, act.asArray.nextArray WHILE act # NIL DO
Consume[act];
ENDLOOP;
};
Jgi2ToGi: PUBLIC PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, side: End] RETURNS [gi2: Nat2, gi: NAT] = {
Do1: PROC [d: Dim] RETURNS [ji: NAT] = {
SELECT TRUE FROM
jgi2[d] < j.groupingParmses[d].middle.min => RETURN [jgi2[d]];
jgi2[d] >= j.groupingParmses[d].firstHigh => RETURN [jgi2[d]-j.groupingParmses[d].d];
ENDCASE => RETURN [j.groupingParmses[d].middle.min];
};
ji2: Int2 = [Foo: Do1[Foo], Bar: Do1[Bar]];
lai: ArrayIndex = [
Foo: phase[Foo] + a.jointsPeriod[Foo] * ji2[Foo],
Bar: phase[Bar] + a.jointsPeriod[Bar] * ji2[Bar]];
[gi2: gi2, gi: gi] ← ComputeGroupingsIndex[a, IF side = low THEN lai ELSE Int2Tweak[lai, d, 1]];
};
Jgi2ToGip: PUBLIC PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2] RETURNS [gip: GIPair] = {
gip ← [
low: Jgi2ToGi[a, d, phase, j, jgi2, low].gi,
high: Jgi2ToGi[a, d, phase, j, jgi2, high].gi];
};
AgiToAi: PUBLIC PROC [a: Array, gi2, gii2: Nat2] RETURNS [ai: ArrayIndex] = {
Do: PROC [d: Dim] RETURNS [INT] = {
SELECT TRUE FROM
gi2[d] < a.groupingParmses[d].middle.min => RETURN [gi2[d]];
gi2[d] >= a.groupingParmses[d].firstHigh => RETURN [gi2[d] - a.groupingParmses[d].d];
ENDCASE => {
t: NAT = a.jointsPeriod[d];
f: NAT = gi2[d] - a.groupingParmses[d].middle.min;
min: NAT = CeilDiv[MAX[a.groupingParmses[d].middle.min, f] - f, t];
RETURN [(gii2[d] + min) * t + f];
};
};
ai[Foo] ← Do[Foo];
ai[Bar] ← Do[Bar];
};
JGRListize: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, lowRange: Range2] RETURNS [jgrl: JGRList] = {
jiir: Range2 = Range2Div[lowRange, a.jointsPeriod, phase];
Enum: PROC [de: Dim, Per: PROC [NAT, NAT, NAT, NAT, NAT, INT, INT, Range, Range]] = {
D: INT = IF de = d THEN 1 ELSE 0;
fh: NAT = ((phase[de]+D) MOD a.jointsPeriod[de]);
giml: NAT = a.groupingParmses[de].middle.min + phase[de];
gimh: NAT = a.groupingParmses[de].middle.min + fh;
jirm: ARRAY End OF Range = [
low: Range1Div[a.groupingParmses[de].middle, a.jointsPeriod[de], phase[de]],
high: Range1Div[RangeOff[a.groupingParmses[de].middle, -D], a.jointsPeriod[de], phase[de]]];
nm: ARRAY End OF NAT = [low: RangeLength[jirm[low]], high: RangeLength[jirm[high]]];
gijl: NAT ← jiir[de].min;
gial: NAT ← gijl * a.jointsPeriod[de] + phase[de];
ji: NAT ← jiir[de].maxPlusOne-1;
ai: NAT ← ji * a.jointsPeriod[de] + phase[de] + D;
giah: INT ← ai + a.groupingParmses[de].d;
gijh: INT ← ji + j.groupingParmses[de].d;
lowLimit: NAT = MIN[j.groupingParmses[de].middle.min, jiir[de].maxPlusOne];
highLimit: NAT = MAX[j.groupingParmses[de].middle.maxPlusOne, jiir[de].min];
FOR gijl ← gijl, gijl+1 WHILE gijl < lowLimit DO
this: Range = [min: gijl, maxPlusOne: gijl+1];
nh: NAT ← 1;
giah: INT ← gial + D;
IF D=1 AND gial=a.groupingParmses[de].middle.min-1
THEN {giah ← gimh; nh ← nm[high]};
Per[gial, giah, gijl, 1, nh, gijl, gijl, this, this];
gial ← gial + a.jointsPeriod[de];
ENDLOOP;
FOR ji ← ji, ji-1 WHILE ji >= highLimit DO
this: Range = [min: ji, maxPlusOne: ji + 1];
nl: NAT ← 1;
jii0al: INT ← ji;
gial: INT ← giah - D;
IF D=1 AND giah=a.groupingParmses[de].firstHigh
THEN {gial ← giml; nl ← nm[low]; jii0al ← jirm[low].min};
Per[gial, giah, gijh, nl, 1, jii0al, ji, this, this];
giah ← giah - a.jointsPeriod[de];
gijh ← gijh - 1;
ENDLOOP;
IF RangesIntersect[jiir[de], j.groupingParmses[de].middle] THEN {
mjir: Range = [
min: MAX[j.groupingParmses[de].middle.min, jiir[de].min],
maxPlusOne: MIN[j.groupingParmses[de].middle.maxPlusOne, jiir[de].maxPlusOne]];
Per[
giml,
gimh,
j.groupingParmses[de].middle.min,
nm[low],
nm[high],
jirm[low].min,
jirm[high].min,
mjir,
j.groupingParmses[de].middle
];
};
};
PerFoo: PROC [gialf, giahf, gijf, ngiilf, ngiihf: NAT, jii0alf, jii0ahf: INT, jirf, fullJiirf: Range] = {
cf: BOOL = jirf = fullJiirf;
PerBar: PROC [gialb, giahb, gijb, ngiilb, ngiihb: NAT, jii0alb, jii0ahb: INT, jirb, fullJiirb: Range] = {
cb: BOOL = jirb = fullJiirb;
jgrl ← CONS[
[
gis: [
low: a.groupingParmses[Bar].sum * gialf + gialb,
high: a.groupingParmses[Bar].sum * giahf + giahb],
ngii: [low: [ngiilf, ngiilb], high: [ngiihf, ngiihb]],
firstJIIOfGI: [low: [jii0alf, jii0alb], high: [jii0ahf, jii0ahb]],
jgi2: [Foo: gijf, Bar: gijb],
jgi: j.groupingParmses[Bar].sum * gijf + gijb,
jiir: [Foo: jirf, Bar: jirb],
fullJiir: [Foo: fullJiirf, Bar: fullJiirb],
complete: cf AND cb
],
jgrl];
};
Enum[Bar, PerBar];
};
jgrl ← NIL;
Enum[Foo, PerFoo];
jgrl ← jgrl;
};
JGRList: TYPE = LIST OF READONLY JGR;
JGR: TYPE = RECORD [
gis: ARRAY End OF NAT,
ngii: ARRAY End OF ARRAY Dim OF NAT,
firstJIIOfGI: ARRAY End OF Int2,
jgi2: Nat2,
jgi: NAT,
jiir, fullJiir: Range2,
complete: BOOL
];
ngii[side] is the number of instances of gis[side] in the entire array.
firstJIIOfGI[side] is the jii of the first joint in the entire array that has gis[side] on side; note that this may include imaginary joints along the low sides of the array.
MakeArrayConnection: PUBLIC PROC [ct: CellType, d: Dim, lowRange: Range2, rp1, rp2: SidedPort, may: BOOL] RETURNS [connected: BOOL] = {
o: Dim = OtherDim[d];
a: Array = ct.asArray;
tf: NAT = a.jointsPeriod[Foo];
tb: NAT = a.jointsPeriod[Bar];
IF a = NIL THEN ERROR;
IF lowRange[d].min<0 OR lowRange[d].maxPlusOne>=a.size[d] THEN ERROR;
IF lowRange[o].min<0 OR lowRange[o].maxPlusOne>a.size[o] THEN ERROR;
IF a.jointsPeriod[d] > a.size[d] THEN ERROR;
FOR ff: NAT IN [0 .. tf) DO FOR fb: NAT IN [0 .. tb) DO
phase2: Nat2 = [ff, fb];
j: Joint = GetArrayJoint[a, d, phase2];
jgrl: JGRList ← JGRListize[a, d, phase2, j, lowRange];
FOR jgrl ← jgrl, jgrl.rest WHILE jgrl # NIL DO
jgr: JGR = jgrl.first;
njgiib: NAT = RangeLength[jgr.fullJiir[Bar]];
g1: Group = GetGroup[a, jgr.gis[rp1.side], rp1.port, may];
g2: Group = GetGroup[a, jgr.gis[rp2.side], rp2.port, may];
tie: Tie;
rpd1, rpd2: SidedPortData;
IF g1 = NIL OR g2 = NIL THEN {IF may THEN ERROR ELSE RETURN [FALSE]};
[tie, rpd1, rpd2] ← GetTieAndRPD[a, d, phase2, j, jgr.jgi2, jgr.jgi, jgr.fullJiir, rp1, rp2, g1, g2, jgr.gis[rp1.side], jgr.gis[rp2.side], may];
IF tie = NIL THEN {IF may THEN ERROR ELSE RETURN [FALSE]};
IF may AND tie.completion # NIL THEN {
FOR jiif: INT IN [jgr.jiir[Foo].min .. jgr.jiir[Foo].maxPlusOne) DO FOR jiib: INT IN [jgr.jiir[Bar].min .. jgr.jiir[Bar].maxPlusOne) DO
lai: ArrayIndex = [
Foo: jiif*a.jointsPeriod[Foo] + ff,
Bar: jiib*a.jointsPeriod[Bar] + fb];
giis: ARRAY End OF NAT = [
low: jgr.ngii[low][Bar] * (jiif - jgr.firstJIIOfGI[low][Foo]) + jiib - jgr.firstJIIOfGI[low][Bar],
high: jgr.ngii[high][Bar] * (jiif - jgr.firstJIIOfGI[high][Foo]) + jiib - jgr.firstJIIOfGI[high][Bar]];
ctii: NAT = njgiib * (jiif - jgr.fullJiir[Foo].min) + jiib - jgr.fullJiir[Bar].min;
Merge[a, d, lai, j, jgr.jgi, tie, rpd1, rpd2, ctii];
tie ← BestTie[tie];
IF tie.completion = NIL THEN GOTO Completed;
ENDLOOP ENDLOOP;
EXITS Completed => tie ← tie;
};
ENDLOOP;
ENDLOOP ENDLOOP;
connected ← TRUE;
IF NOT may THEN RETURN;
FOR f: NAT IN [NAT[lowRange[Foo].min] .. NAT[lowRange[Foo].maxPlusOne]) DO FOR b: NAT IN [NAT[lowRange[Bar].min] .. NAT[lowRange[Bar].maxPlusOne]) DO
ais: ARRAY End OF ArrayIndex = [[f, b], Int2Tweak[[f, b], d, 1]];
gis: ARRAY End OF NAT = [ComputeGroupingsIndex[a, ais[low]].gi, ComputeGroupingsIndex[a, ais[high]].gi];
g1: Group = GetGroup[a, gis[rp1.side], rp1.port, FALSE];
g2: Group = GetGroup[a, gis[rp2.side], rp2.port, FALSE];
aw1: ArrayWire = ArrayWireForGroup[a, ais[rp1.side], gis[rp1.side], g1, FALSE];
aw2: ArrayWire = ArrayWireForGroup[a, ais[rp2.side], gis[rp2.side], g2, FALSE];
IF aw1 = aw2 THEN NULL
ELSE IF aw2 = NIL THEN AddEltToArrayWire[a, aw1, [g2, ais[rp2.side]]]
ELSE IF aw1 = NIL THEN AddEltToArrayWire[a, aw2, [g1, ais[rp1.side]]]
ELSE JoinArrayWires[a, aw1, aw2];
ENDLOOP ENDLOOP;
};
MakeGroupsForPort: PUBLIC PROC [a: Array, ep: Port] ~ {
a ← a;
FOR gi: NATURAL IN [0 .. a.groupingses.length) DO
[] ← GetGroup[a, gi, ep, TRUE];
ENDLOOP;
a ← a;
};
GetGroup: PUBLIC PROC [a: Array, gi: NAT, ep: Port, mayAdd: BOOL] RETURNS [g: Group] ~ {
gs: Groupings ~ NARROW[a.groupingses[gi]];
g ← NARROW[gs.toGroup.Fetch[ep].val];
IF g = NIL AND mayAdd THEN {
gi2: Nat2 ~ GiToGi2[a, gi];
g ← MakeGroup[a, gi2, gs];
AddPortToGroup[a, gi, ep, g, TRUE];
IF gs.toGroup.Fetch[ep].val # g THEN ERROR};
};
MakeGroup: PUBLIC PROC [a: Array, gi2: Nat2, gs: Groupings] RETURNS [g: Group] = {
g ← NEW [GroupPrivate ← [gi2: gi2]];
IF NOT gs.groups.UnionSingleton[g] THEN ERROR;
g ← g};
AddPortToGroup: PUBLIC PROC [a: Array, gi: NATURAL, ep: Port, g: Group, links: BOOL] ~ {
gs: Groupings ~ NARROW[a.groupingses[gi]];
IF g.better#NIL OR g.worse#NIL THEN ERROR;
g.ports ← CONS[ep, g.ports];
IF NOT gs.toGroup.Insert[ep, g] THEN ERROR;
FOR d: Dim IN Dim DO
FOR side: End IN End DO
EnsureRPD[a, d, [side: side, port: ep], links];
ENDLOOP;
ENDLOOP;
g ← g};
RemovePortFromGroup: PUBLIC PROC [a: Array, gi: NATURAL, ep: Port, g: Group] ~ {
gs: Groupings ~ NARROW[a.groupingses[gi]];
IF g.better#NIL OR g.worse#NIL THEN ERROR;
IF gs.toGroup.Fetch[ep].val # g THEN ERROR;
g.ports ← NARROW[GList.DRemove[ep, g.ports]];
IF NOT gs.toGroup.Delete[ep] THEN ERROR;
g ← g};
UnrolePort: PUBLIC PROC [a: Array, ep: Port] ~ {
FOR d: Dim IN Dim DO FOR s: End IN End DO
spd: SidedPortData ~ NARROW[a.toRole[d][s].Fetch[ep].val];
IF a.roles[d].refs[spd.index] # spd THEN ERROR;
IF spd.index+1 = a.nextRP[d] THEN {
a.nextRP[d] ← a.nextRP[d]-1;
a.roles[d].length ← a.roles[d].length-1};
a.roles[d].refs[spd.index] ← NIL;
IF NOT a.toRole[d][s].Delete[ep] THEN ERROR;
ENDLOOP ENDLOOP;
a ← a;
};
EnsureRPD: PROC [a: Array, d: Dim, rp: SidedPort, links: BOOL] = {
rpd: SidedPortData ← FetchRPD[a, d, rp];
IF rpd = NIL THEN {
rpd ← NEW [SidedPortDataPrivate ← [
port: rp.port,
side: rp.side,
index: a.nextRP[d],
links: NIL
]];
IF a.roles[d].length # rpd.index THEN ERROR;
VarRefSeqAppend[a.roles[d], rpd];
a.nextRP[d] ← a.nextRP[d] + 1;
IF NOT a.toRole[d][rp.side].Store[rp.port, rpd] THEN ERROR;
IF links THEN AddLinks[a, d, rpd];
};
rpd ← rpd};
GetTieAndRPD: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, jgi: NAT, jiir: Range2, rp1, rp2: SidedPort, g1, g2: Group, gi1, gi2: NAT, may: BOOL] RETURNS [tie: Tie, rpd1, rpd2: SidedPortData] = {
tie1: Tie = GetTie[a, d, phase, j, rp1.side, jgi2, jgi, jiir, g1, gi1, may];
tie2: Tie = GetTie[a, d, phase, j, rp2.side, jgi2, jgi, jiir, g2, gi2, may];
tie ← SELECT TRUE FROM
tie1 = tie2 => tie1,
NOT may => NIL,
ENDCASE => JoinTies[a, d, phase, j, jgi2, jgi, jiir, LIST[tie1, tie2], TRUE];
IF may AND tie.completion # NIL THEN {
rpd1 ← FetchRPD[a, d, rp1];
rpd2 ← FetchRPD[a, d, rp2];
};
};
GetTie: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, side: End, jgi2: Nat2, jgi: NAT, jiir: Range2, g: Group, gi: NAT, may: BOOL] RETURNS [tie: Tie] = {
tie ← FetchTie[j, side, jgi, g];
IF tie = NIL AND may THEN {
cn: Completion ← NIL;
IF g.ports # NIL AND g.ports.rest # NIL THEN {
ntii: NAT = RangeArea[jiir];
tii, ni: NAT ← 0;
D: Nat2 ← [0, 0];
cn ← NEW [CompletionPrivate[ntii]];
IF side = high THEN D[d] ← 1;
FOR jiif: INT IN [jiir[Foo].min .. jiir[Foo].maxPlusOne) DO FOR jiib: INT IN [jiir[Bar].min .. jiir[Bar].maxPlusOne) DO
lai: ArrayIndex = [jiif*a.jointsPeriod[Foo]+phase[Foo], jiib*a.jointsPeriod[Bar]+phase[Bar]];
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
IF NOT (cn[tii] ← ComputeGroupCompleteAt[a, g, jSize[Bar]*lai[Foo]+lai[Bar], d, side]) THEN ni ← ni + 1;
ENDLOOP ENDLOOP;
cn.nIncomplete ← ni;
IF ni = 0 THEN cn ← NIL;
};
tie ← NEW [TiePrivate ← [
groups: ALL[NIL],
completion: cn
]];
tie.groups[side] ← g;
g.stopLooking[d][side] ← TRUE;
AddTie[j, jgi, tie];
};
};
JoinTies: PROC [a: Array, d: Dim, phase: Nat2, j: Joint, jgi2: Nat2, jgi: NAT, jiir: Range2, ties: TieList, mayJoinGroups: BOOL] RETURNS [tie: Tie] = {
ntii: NAT = RangeArea[jiir];
groups: ARRAY End OF Group ← ALL[NIL];
urTies: TieList = ties;
doomeds: TieList ← NIL;
gi2s: ARRAY End OF Nat2;
gis: ARRAY End OF NAT;
hPhase: Nat2 ← phase;
hPhase[d] ← (phase[d] + 1) MOD a.jointsPeriod[d];
FOR ts: TieList ← ties, ts.rest WHILE ts # NIL DO
tie: Tie = ts.first;
IF tie.better # NIL THEN ERROR;
IF GList.Member[tie, ts.rest] THEN ERROR;
ENDLOOP;
FOR side: End IN End DO
olds: GroupList ← NIL;
[gi2s[side], gis[side]] ← Jgi2ToGi[a, d, phase, j, jgi2, side];
FOR ts: TieList ← ties, ts.rest WHILE ts # NIL DO
g: Group = BestGroup[ts.first.groups[side]];
IF g # NIL AND NOT GList.Member[g, olds] THEN olds ← CONS[g, olds];
ENDLOOP;
groups[side] ← IF olds # NIL THEN IF olds.rest = NIL THEN olds.first ELSE IF mayJoinGroups THEN JoinGroups[a, phase, gi2s[side], olds, NARROW[a.groupingses[gis[side]]]] ELSE ERROR ELSE NIL;
ENDLOOP;
FOR side: End IN End DO
best: Group = groups[side] ← BestGroup[groups[side]];
FOR worses: GroupList ← AddTiedGroups[d, j, side, jgi, best, NIL], worses.rest WHILE worses # NIL DO
worse: Group = worses.first;
tie: Tie = FetchTie[j, side, jgi, worse];
IF tie = NIL THEN ERROR
ELSE IF NOT GList.Member[tie, doomeds] THEN doomeds ← CONS[tie, doomeds];
ENDLOOP;
ENDLOOP;
FOR ts: TieList ← urTies, ts.rest WHILE ts # NIL DO
IF NOT GList.Member[ts.first, doomeds] THEN ERROR;
ENDLOOP;
tie ← NEW [TiePrivate ← [groups: groups]];
FOR ts: TieList ← doomeds, ts.rest WHILE ts # NIL DO
doomed: Tie = ts.first;
Incompletify[a, d, doomed, ntii];
doomed.better ← tie;
ENDLOOP;
FinishIncompletion[a, d, phase, tie, ntii];
FOR ts: TieList ← doomeds, ts.rest WHILE ts # NIL DO
doomed: Tie = ts.first;
DeleteTie[j, jgi, doomed];
ENDLOOP;
AddTie[j, jgi, tie];
FOR sideg: End IN End DO --make sure all ties for group on this side are joined
gPhase: Nat2 = IF sideg = low THEN phase ELSE hPhase;
g: Group = groups[sideg];
IF g # NIL THEN {
FOR de: Dim IN Dim DO
FOR sidee: End IN End DO
Consume: PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi: NAT, j: Joint] = {
oldTies: TieList ← NIL;
FOR ws: GroupList ← AddTiedGroups[de, j, sidee, jgi, g, NIL], ws.rest WHILE ws # NIL DO
worse: Group = ws.first;
tie: Tie = FetchTie[j, sidee, jgi, worse];
IF tie = NIL THEN ERROR
ELSE IF NOT GList.Member[tie, oldTies] THEN oldTies ← CONS[tie, oldTies];
ENDLOOP;
IF oldTies # NIL AND (oldTies.rest # NIL OR oldTies.first.groups[sidee] # g) THEN {
jiir: Range2 = Jgi2ToLair[a, gPhase, j, jgi2].jiir;
newTie: Tie = JoinTies[a, de, gPhase, j, jgi2, jgi, jiir, oldTies, FALSE];
IF newTie.groups[sidee] # g THEN ERROR;
oldTies ← oldTies;
};
oldTies ← oldTies;
};
EnumerateJointsForGi[a, de, sidee, gPhase, gi2s[sideg], Consume];
g.stopLooking[de][sidee] ← TRUE;
ENDLOOP;
ENDLOOP;
IF g.stopLooking = ALL[ALL[TRUE]] THEN KillWorse[g];
};
ENDLOOP;
tie ← tie;
};
KillWorse: PROC [g: Group] = {
FOR ws: GroupList ← g.worse, ws.rest WHILE ws # NIL DO
KillWorse[ws.first];
ENDLOOP;
g.worse ← NIL;
};
JoinGroups: PROC [a: Array, phase: Nat2, gi2: Nat2, groups: GroupList, gs: Groupings] RETURNS [g: Group] = {
bests: GroupList ← NIL;
ports: PortList ← NIL;
FOR raws: GroupList ← groups, raws.rest WHILE raws # NIL DO
IF raws.first = NIL THEN LOOP;
IF raws.first.ports = NIL THEN ERROR;
{best: Group = BestGroup[raws.first];
IF NOT GList.Member[best, bests] THEN {
bests ← CONS[best, bests];
ports ← NARROW[GList.Append[best.ports, ports]];
};
}ENDLOOP;
IF bests = NIL THEN ERROR;
IF bests.rest = NIL THEN RETURN [bests.first];
g ← NEW [GroupPrivate ← [ports: ports, worse: bests, gi2: gi2]];
FOR pl: PortList ← g.ports, pl.rest WHILE pl # NIL DO
IF NOT gs.toGroup.Replace[pl.first, g] THEN ERROR;
ENDLOOP;
IF NOT gs.groups.UnionSingleton[g] THEN ERROR;
FOR worse: GroupList ← bests, worse.rest WHILE worse # NIL DO
IF NOT gs.groups.RemoveElt[worse.first] THEN ERROR;
worse.first.better ← g;
ENDLOOP;
FOR d: Dim IN Dim DO
FOR side: End IN End DO
Consume: PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi: NAT, j: Joint] = {
otherSide: End = OtherEnd[side];
otherGs: Groupings = NARROW[a.groupingses[otherGi]];
otherSideGroups: GroupList ← NIL;
FOR ws: GroupList ← AddListTiedGroups[d, j, side, jgi, bests, NIL], ws.rest WHILE ws # NIL DO
worse: Group = ws.first;
tie: Tie = FetchTie[j, side, jgi, worse];
IF tie = NIL THEN ERROR
ELSE IF tie.groups[otherSide] # NIL THEN otherSideGroups ← CONS[tie.groups[otherSide], otherSideGroups];
ENDLOOP;
IF otherSideGroups # NIL AND otherSideGroups.rest # NIL THEN [] ← JoinGroups[a, otherPhase, otherGi2, otherSideGroups, otherGs];
};
EnumerateJointsForGi[a, d, side, phase, gi2, Consume];
ENDLOOP;
ENDLOOP;
g ← g;
};
EnumerateJointsForGi: PROC [a: Array, d: Dim, side: End, phase, gi2: Nat2, Consume: PROC [otherPhase, otherGi2, jgi2: Nat2, otherGi, jgi: NAT, j: Joint]] = {
lowPhase, highPhase: Nat2 ← phase;
IF side = high THEN {
lowPhase[d] ← (phase[d] + a.jointsPeriod[d] - 1) MOD a.jointsPeriod[d];
}
ELSE {
highPhase[d] ← (phase[d] + 1) MOD a.jointsPeriod[d];
};
{j: Joint = GetArrayJoint[a, d, lowPhase];
otherPhase: Nat2 = IF side = low THEN highPhase ELSE lowPhase;
otherGi2, jgi2: Nat2 ← [LAST[NAT], LAST[NAT]];
Do1: PROC [de: Dim, Consume1: PROC] = {
SELECT TRUE FROM
de # d => {
otherGi2[de] ← gi2[de];
SELECT TRUE FROM
gi2[de] < a.groupingParmses[de].middle.min => jgi2[de] ← gi2[de] / a.jointsPeriod[de];
gi2[de] >= a.groupingParmses[de].firstHigh => {
lai: NAT = gi2[de] - a.groupingParmses[de].d;
jii: NAT = lai / a.jointsPeriod[de];
jgi2[de] ← jii + j.groupingParmses[de].d};
ENDCASE => jgi2[de] ← j.groupingParmses[de].middle.min;
Consume1[];
};
side = low => SELECT TRUE FROM
gi2[de] < a.groupingParmses[de].middle.min => IF gi2[de]+1 < a.groupingParmses[de].sum THEN {
jgi2[de] ← gi2[de] / a.jointsPeriod[de];
IF gi2[de]+1 < a.groupingParmses[de].middle.min THEN otherGi2[de] ← gi2[de]+1
ELSE IF HasMiddle[a.groupingParmses[de]] THEN otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de]
ELSE otherGi2[de] ← a.groupingParmses[de].middle.maxPlusOne;
Consume1[];
};
gi2[de] >= a.groupingParmses[de].firstHigh => IF gi2[de]+1 < a.groupingParmses[de].sum THEN {
lai: NAT = gi2[de] - a.groupingParmses[de].d;
jii: NAT = lai / a.jointsPeriod[de];
jgi2[de] ← jii + j.groupingParmses[de].d;
otherGi2[de] ← gi2[de] + 1;
Consume1[];
};
ENDCASE => {
IF HasMiddle[j.groupingParmses[de]] THEN {
otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de];
jgi2[de] ← j.groupingParmses[de].middle.min;
Consume1[];
};
IF highPhase[de] = (a.groupingParmses[de].middle.maxPlusOne MOD a.jointsPeriod[de]) AND a.groupingParmses[de].firstHigh < a.groupingParmses[de].sum THEN {
jgi2[de] ← j.groupingParmses[de].firstHigh;
otherGi2[de] ← a.groupingParmses[de].firstHigh;
Consume1[];
};
};
side = high => SELECT TRUE FROM
gi2[de] < a.groupingParmses[de].middle.min => IF gi2[de] > 0 THEN {
otherGi2[de] ← gi2[de] - 1;
jgi2[de] ← otherGi2[de] / a.jointsPeriod[de];
Consume1[];
};
gi2[de] >= a.groupingParmses[de].firstHigh => IF gi2[de] > 0 THEN {
lai, jii: NAT;
IF gi2[de] > a.groupingParmses[de].firstHigh THEN {
otherGi2[de] ← gi2[de]-1;
lai ← otherGi2[de] - a.groupingParmses[de].d;
jii ← lai / a.jointsPeriod[de];
jgi2[de] ← jii + j.groupingParmses[de].d;
}
ELSE IF HasMiddle[a.groupingParmses[de]] THEN {
otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de];
jgi2[de] ← j.groupingParmses[de].firstHigh;
}
ELSE {
otherGi2[de] ← a.groupingParmses[de].middle.min-1;
jgi2[de] ← j.groupingParmses[de].firstHigh;
};
Consume1[];
};
ENDCASE => {
IF HasMiddle[j.groupingParmses[de]] THEN {
otherGi2[de] ← a.groupingParmses[de].middle.min + otherPhase[de];
jgi2[de] ← j.groupingParmses[de].middle.min;
Consume1[];
};
IF highPhase[de] = (a.groupingParmses[de].middle.min MOD a.jointsPeriod[de]) AND a.groupingParmses[de].middle.min > 0 THEN {
jgi2[de] ← j.groupingParmses[de].middle.min-1;
otherGi2[de] ← a.groupingParmses[de].middle.min-1;
Consume1[];
};
};
ENDCASE => ERROR;
};
PerFoo: PROC = {Do1[Bar, PerBoth]};
PerBoth: PROC = {
Consume[otherPhase, otherGi2, jgi2, a.groupingParmses[Bar].sum*otherGi2[Foo] + otherGi2[Bar], j.groupingParmses[Bar].sum*jgi2[Foo] + jgi2[Bar], j];
};
Do1[Foo, PerFoo];
}};
AddTie: PUBLIC PROC [j: Joint, jgi: NAT, tie: Tie] = {
ties: Set--of Tie-- = NARROW[j.ties[jgi]];
IF NOT ties.UnionSingleton[tie] THEN ERROR;
FOR side: End IN End DO
last: RefTable--Group b Tie-- = NARROW[j.toTie[side][jgi]];
g: Group = tie.groups[side];
IF g # NIL THEN {
IF NOT last.Insert[g, tie] THEN ERROR;
};
ENDLOOP;
};
DeleteGroup: PUBLIC PROC [a: Array, g: Group] ~ {
gs: Groupings ~ NARROW[a.groupingses[ComposeGI[a, g.gi2]]];
Untie: PROC [d: Dim, phase: Nat2, jgi: NATURAL, jgi2: Nat2, j: Joint, tie: Tie, side: End] ~ {
IF tie.completion#NIL OR tie.groups[side]#g THEN ERROR;
IF FetchTie[j, side, jgi, g] # tie THEN ERROR;
tie.groups[side] ← NIL;
IF tie.groups = ALL[NIL] THEN DeleteTie[j, jgi, tie];
};
places: IntTable ~ NARROW[a.toWire.Fetch[g].val];
IF places # NIL THEN {
Unwire: PROC [key: PackedArrayIndex, value: REF ANY] RETURNS [quit: BOOLFALSE] --IntHashTable.EachPairAction-- ~ {
aw: ArrayWire ~ NARROW[value];
[] ← aw.members.PutMapping[g, NIL];
};
IF places.Pairs[Unwire] THEN ERROR;
IF NOT a.toWire.Delete[g] THEN ERROR;
};
EnumerateTiesOfGroup[a, g.gi2, g, Untie];
FOR ports: PortList ← g.ports, ports.rest WHILE ports # NIL DO
IF gs.toGroup.Fetch[ports.first].val # g THEN ERROR;
IF NOT gs.toGroup.Delete[ports.first] THEN ERROR;
ENDLOOP;
IF NOT gs.groups.RemoveElt[g] THEN ERROR;
};
DeleteTie: PUBLIC PROC [j: Joint, jgi: NAT, tie: Tie] = {
ties: Set--of Tie-- = NARROW[j.ties[jgi]];
IF NOT ties.RemoveElt[tie] THEN ERROR;
FOR side: End IN End DO
last: RefTable--Group b Tie-- = NARROW[j.toTie[side][jgi]];
IF tie.groups[side] # NIL AND NOT last.Delete[tie.groups[side]] THEN ERROR;
ENDLOOP;
};
PortPair: TYPE = ARRAY [1 .. 2] OF Port;
MergeStack: TYPE = LIST OF MergeStackFrame;
MergeStackFrame: TYPE = RECORD [
lai: ArrayIndex,
d: Dim,
side: End,
pair: PortPair];
Merge: PROC [a: Array, d: Dim, lai: ArrayIndex, j: Joint, jgi: NAT, tie: Tie, rpd1, rpd2: SidedPortData, ctii: NAT] = {
stack: MergeStack ← NIL;
Consider: PROC [ai: ArrayIndex, d: Dim, eltSide: End, pair: PortPair] = {
jointSide: End = OtherEnd[eltSide];
o: Dim = OtherDim[d];
lai: ArrayIndex = IF eltSide = high THEN ai ELSE Int2Tweak[ai, d, -1];
IF lai[d] IN [0 .. a.size[d]-1) AND lai[o] IN [0 .. a.size[o]) THEN {
stack ← CONS[[lai, d, jointSide, pair], stack];
};
};
DO
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
clai: INT = jSize[Bar] * lai[Foo] + lai[Bar];
r1: NAT = GetRoot[a, d, rpd1, clai];
r2: NAT = GetRoot[a, d, rpd2, clai];
IF r1 # r2 THEN {
o: Dim = OtherDim[d];
hai: Int2 = Int2Tweak[lai, d, 1];
IF tie.completion[ctii] THEN ERROR;
FOR side: End IN End DO
g: Group = tie.groups[side];
ai: ArrayIndex = IF side = low THEN lai ELSE hai;
pair: PortPair ← ALL[NIL];
otherSide: End = OtherEnd[side];
IF rpd1.side = side AND rpd2.side = side THEN pair ← [rpd1.port, rpd2.port]
ELSE {
IF g # NIL THEN FOR pl: PortList ← g.ports, pl.rest WHILE pl # NIL DO
rpd: SidedPortData = FetchRPD[a, d, [side, pl.first]];
r: NAT = GetRoot[a, d, rpd, clai];
i: INT = SELECT r FROM r1 => 1, r2 => 2, ENDCASE => 3;
IF i IN [1 .. 2] AND pair[i] = NIL THEN {
pair[i] ← pl.first;
IF pair[3-i] # NIL THEN EXIT};
ENDLOOP;
};
IF pair[1] # NIL AND pair[2] # NIL THEN {
Consider[ai, d, side, pair];
Consider[ai, o, side, pair];
Consider[ai, o, otherSide, pair];
};
ENDLOOP;
IF r1 < r2 THEN SetNext[a, d, r2, clai, r1] ELSE SetNext[a, d, r1, clai, r2];
IF tie.completion[ctii] ← ComputeTieCompleteAt[a, d, tie, clai] THEN {
IF (tie.completion.nIncomplete ← tie.completion.nIncomplete - 1) = 0 THEN CompletifyTie[a, d, tie];
};
};
DO
IF stack = NIL THEN GOTO Dun;
{msf: MergeStackFrame = stack.first;
stack ← stack.rest;
d ← msf.d;
lai ← msf.lai;
{ai: ArrayIndex = IF msf.side = low THEN lai ELSE Int2Tweak[lai, d, 1];
gi: NAT = ComputeGroupingsIndex[a, ai].gi;
jii: Nat2 = [
Foo: lai[Foo] / a.jointsPeriod[Foo],
Bar: lai[Bar] / a.jointsPeriod[Bar]];
phase: Nat2 = [
Foo: lai[Foo] - jii[Foo] * a.jointsPeriod[Foo],
Bar: lai[Bar] - jii[Bar] * a.jointsPeriod[Bar]];
rp1: SidedPort = [msf.side, msf.pair[1]];
rp2: SidedPort = [msf.side, msf.pair[2]];
g1: Group = GetGroup[a, gi, rp1.port, TRUE];
g2: Group = GetGroup[a, gi, rp2.port, TRUE];
jgi2: Nat2;
jiir: Range2;
j ← GetArrayJoint[a, d, phase];
[jgi2, jgi, ctii, jiir] ← ComputeJointGroupingsIndex[a, j, jii];
[tie, rpd1, rpd2] ← GetTieAndRPD[a, d, phase, j, jgi2, jgi, jiir, rp1, rp2, g1, g2, gi, gi, TRUE];
IF tie.completion # NIL THEN EXIT;
}}ENDLOOP;
ENDLOOP;
EXITS
Dun => a ← a;
};
Incompletify: PROC [a: Array, d: Dim, tie: Tie, ntii: NAT] = {
IF tie.completion # NIL THEN RETURN;
tie.completion ← NEW [CompletionPrivate[ntii]];
tie.completion.nIncomplete ← 0;
FOR tii: NAT IN [0 .. tie.completion.length) DO
tie.completion[tii] ← TRUE;
ENDLOOP;
tie ← tie;
};
CompletifyTie: PROC [a: Array, d: Dim, tie: Tie] = {
IF tie.completion = NIL THEN ERROR;
tie.completion ← NIL;
};
FinishIncompletion: PROC [a: Array, d: Dim, phase: Nat2, tie: Tie, ntii: NAT] = {
IF tie.completion # NIL THEN ERROR;
tie.completion ← NEW [CompletionPrivate[ntii]];
tie.completion.nIncomplete ← ntii;
FOR ctii: NAT IN [0 .. ntii) DO tie.completion[ctii] ← FALSE ENDLOOP;
};
AddLinks: PROC [a: Array, d: Dim, rpd: SidedPortData] = {
IF rpd.links # NIL THEN ERROR;
IF rpd.index = 0 THEN RETURN;
{
linksNeeded: NAT = Nat2Area[Nat2Tweak[a.size, d, -1]];
linkSize, wordsNeeded: NAT;
lgLinksPerWord: Sublg;
[linkSize, lgLinksPerWord] ← ChooseLinkSize[rpd.index];
wordsNeeded ← CeilDiv[linkSize * linksNeeded, Basics.bitsPerWord];
rpd.links ← NEW [LinksPrivate[wordsNeeded]];
rpd.links.linkSize ← linkSize;
rpd.links.negLinkSize ← - linkSize;
rpd.links.negLgLinksPerWord ← - lgLinksPerWord;
rpd.links.lgLinksPerWord ← lgLinksPerWord;
FOR clai: NAT IN [0 .. linksNeeded) DO
SetNext[a, d, rpd.index, clai, rpd.index];
ENDLOOP;
rpd ← rpd;
}};
ChooseLinkSize: PROC [index: NAT] RETURNS [linkSize: NAT, lgLinksPerWord: Sublg] = {
SELECT index FROM
<1 => ERROR;
<2 => RETURN [1, Basics.logBitsPerWord];
<4 => RETURN [2, Basics.logBitsPerWord-1];
<16 => RETURN [4, Basics.logBitsPerWord-2];
<256 => RETURN [8, Basics.logBitsPerWord-3];
<=32767 => RETURN [16, Basics.logBitsPerWord-4];
ENDCASE => ERROR;
};
RPDNeedsLinks: PUBLIC PROC [a: Array, d: Dim, rpd: SidedPortData] RETURNS [needs: BOOL] = {
phase: NAT ← 0;
needs ← FALSE;
FOR ff: INT IN [0 .. a.jointsPeriod[Foo]) DO FOR fb: INT IN [0 .. a.jointsPeriod[Bar]) DO
j: Joint = NARROW[a.joints[d][phase]];
jgi: NAT ← 0;
FOR jgif: NAT IN [0 .. j.groupingParmses[Foo].sum) DO
FOR jgib: NAT IN [0 .. j.groupingParmses[Bar].sum) DO
gi: NAT = Jgi2ToGi[a, d, [ff, fb], j, [jgif, jgib], rpd.side].gi;
gs: Groupings = NARROW[a.groupingses[gi]];
g: Group = NARROW[gs.toGroup.Fetch[rpd.port].val];
IF g # NIL THEN {
tie: Tie = FetchTie[j, rpd.side, jgi, g];
IF tie # NIL AND tie.completion # NIL THEN RETURN [TRUE];
};
jgi ← jgi + 1;
ENDLOOP;
ENDLOOP;
phase ← phase + 1;
ENDLOOP ENDLOOP;
needs ← needs;
};
GroupCompleteAt: PROC [a: Array, gi: NAT, g: Group, ai: ArrayIndex] RETURNS [complete: BOOL] = {
complete ← FALSE;
FOR d: Dim IN Dim DO
Try: PROC [side: End, lai: ArrayIndex] RETURNS [determined: BOOL] = {
jii: Nat2 = [lai[Foo]/a.jointsPeriod[Foo], lai[Bar]/a.jointsPeriod[Bar]];
phase: Nat2 = [lai[Foo] - jii[Foo]*a.jointsPeriod[Foo], lai[Bar] - jii[Bar]*a.jointsPeriod[Bar]];
j: Joint = GetArrayJoint[a, d, phase];
jgi: NAT = ComputeJointGroupingsIndex[a, j, jii].jgi;
tie: Tie = FetchTie[j, side, jgi, g];
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
IF tie = NIL THEN RETURN [FALSE];
complete ← tie.completion = NIL OR ComputeGroupCompleteAt[a, g, jSize[Bar]*lai[Foo]+lai[Bar], d, side];
determined ← TRUE;
};
IF
(ai[d] < a.size[d]-1 AND Try[low, ai]) OR
(ai[d] > 0 AND Try[high, Int2Tweak[ai, d, -1]])
THEN EXIT;
ENDLOOP;
RETURN;
};
ComputeGroupCompleteAt: PROC [a: Array, g: Group, clai: NAT, d: Dim, side: End--of joint--] RETURNS [complete: BOOL] = {
root: NAT;
first: BOOLTRUE;
someNIL, someNonNIL: BOOLFALSE;
complete ← TRUE;
{FOR pl: PortList ← g.ports, pl.rest WHILE pl # NIL DO
rpd: SidedPortData = FetchRPD[a, d, [side, pl.first]];
r2: NAT;
IF rpd.index = 0 THEN r2 ← 0
ELSE IF rpd.links = NIL THEN {r2 ← LAST[NAT]; someNIL ← TRUE}
ELSE {r2 ← GetRoot[a, d, rpd, clai]; someNonNIL ← TRUE};
IF first
THEN {root ← r2; first ← FALSE}
ELSE IF r2 # root THEN GOTO Fail;
ENDLOOP;
EXITS Fail => complete ← FALSE};
IF someNIL AND someNonNIL THEN ERROR;
};
ComputeTieCompleteAt: PUBLIC PROC [a: Array, d: Dim, tie: Tie, clai: NAT] RETURNS [complete: BOOL] = {
root: NAT;
first: BOOLTRUE;
someNIL, someNonNIL: BOOLFALSE;
complete ← TRUE;
{FOR side: End IN End DO
g: Group = tie.groups[side];
IF g # NIL THEN FOR pl: PortList ← g.ports, pl.rest WHILE pl # NIL DO
rpd: SidedPortData = FetchRPD[a, d, [side, pl.first]];
r2: NAT;
IF rpd.index = 0 THEN r2 ← 0
ELSE IF rpd.links = NIL THEN {r2 ← LAST[NAT]; someNIL ← TRUE}
ELSE {r2 ← GetRoot[a, d, rpd, clai]; someNonNIL ← TRUE};
IF first
THEN {root ← r2; first ← FALSE}
ELSE IF r2 # root THEN GOTO Fail;
ENDLOOP;
ENDLOOP;
EXITS Fail => complete ← FALSE};
IF someNIL AND someNonNIL THEN ERROR;
};
WordPtr: TYPE = LONG POINTER TO WORD;
GetNext: PUBLIC PROC [rp: SidedPortData, clai: NAT] RETURNS [next: NAT] = TRUSTED {
IF rp.index = 0 THEN RETURN [rp.index];
{ls: Links = rp.links;
wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
rightShift: INTEGER = ls.negLinkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
mask: WORD = last[ls.linkSize];
next ← Basics.BITAND[Basics.BITSHIFT[wordPtr^, rightShift], mask];
}};
ArrayEltPortsConnectedByJoint: PUBLIC PROC [a: Array, d: Dim, lowIndex: ArrayIndex, rp1, rp2: SidedPort] RETURNS [hypothetically, really: BOOL] = {
o: Dim = OtherDim[d];
IF NOT (lowIndex[d] IN [0 .. a.size[d]-1) AND lowIndex[o] IN [0 .. a.size[o])) THEN RETURN [FALSE, FALSE];
{phase: Nat2 = [
Foo: lowIndex[Foo] MOD a.jointsPeriod[Foo],
Bar: lowIndex[Bar] MOD a.jointsPeriod[Bar]];
j: Joint = GetArrayJoint[a, d, phase];
jii: Nat2 = [
Foo: lowIndex[Foo] / a.jointsPeriod[Foo],
Bar: lowIndex[Bar] / a.jointsPeriod[Bar]];
jgi2: Nat2;
jgi, ctii: NAT;
jiir: Range2;
[jgi2, jgi, ctii, jiir] ← ComputeJointGroupingsIndex[a, j, jii];
{gis: ARRAY End OF NAT = [
low: Jgi2ToGi[a, d, phase, j, jgi2, low].gi,
high: Jgi2ToGi[a, d, phase, j, jgi2, high].gi];
g1: Group = GetGroup[a, gis[rp1.side], rp1.port, FALSE];
g2: Group = GetGroup[a, gis[rp2.side], rp2.port, FALSE];
IF g1 = NIL OR g2 = NIL THEN RETURN [FALSE, FALSE];
{tie1: Tie = FetchTie[j, rp1.side, jgi, g1];
tie2: Tie = FetchTie[j, rp2.side, jgi, g2];
jSize: Nat2 = Nat2Tweak[a.size, d, -1];
IF tie1 # tie2 OR tie1 = NIL THEN RETURN [FALSE, FALSE]
ELSE IF tie1.completion = NIL THEN RETURN [TRUE, TRUE]
ELSE {
rpd1: SidedPortData = FetchRPD[a, d, rp1];
rpd2: SidedPortData = FetchRPD[a, d, rp2];
clai: INT = jSize[Bar] * lowIndex[Foo] + lowIndex[Bar];
really ← GetRoot[a, d, rpd1, clai] = GetRoot[a, d, rpd2, clai];
hypothetically ← TRUE;
};
}}}};
ArrayEltPortsConnected: PUBLIC PROC [a: Array, ai1, ai2: ArrayIndex, ep1, ep2: Port] RETURNS [hypothetically: BOOL] = {
gi1: NAT = ComputeGroupingsIndex[a, ai1].gi;
gi2: NAT = ComputeGroupingsIndex[a, ai2].gi;
g1: Group = GetGroup[a, gi1, ep1, FALSE];
g2: Group = GetGroup[a, gi2, ep2, FALSE];
IF g1 = NIL OR g2 = NIL THEN RETURN [FALSE];
{aw1: ArrayWire = ArrayWireForGroup[a, ai1, gi1, g1, TRUE];
aw2: ArrayWire = ArrayWireForGroup[a, ai2, gi2, g2, TRUE];
RETURN [aw1 = aw2];
}};
GroupsHypotheticallyConnected: PUBLIC PROC [a: Array, j: Joint, jgi: NAT, gs: ARRAY End OF Group] RETURNS [BOOL] = {
Get: PROC [side: End] RETURNS [tie: Tie] = {
rt: RefTable = NARROW[j.toTie[side][jgi]];
tie ← NARROW[rt.Fetch[gs[side]].val]};
RETURN [Get[low] = Get[high]];
};
GetRoot: PUBLIC PROC [a: Array, d: Dim, rp: SidedPortData, clai: NAT] RETURNS [root: NAT] = TRUSTED {
IF rp.index = 0 THEN RETURN [rp.index];
{ls: Links = rp.links;
wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
rightShift: INTEGER = ls.negLinkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
mask: WORD = last[ls.linkSize];
next: NAT = Basics.BITAND[Basics.BITSHIFT[wordPtr^, rightShift], mask];
IF next = rp.index THEN RETURN [rp.index];
{rp2: SidedPortData = NARROW[a.roles[d].refs[next]];
IF next # rp2.index THEN ERROR;
root ← GetRoot[a, d, rp2, clai];
IF root # next THEN {
leftShift: INTEGER = - rightShift;
shiftedMask: WORD = Basics.BITNOT[Basics.BITSHIFT[mask, leftShift]];
shiftedRoot: WORD = Basics.BITSHIFT[root, leftShift];
word: WORD = Basics.BITOR[shiftedRoot, Basics.BITAND[shiftedMask, wordPtr^]];
wordPtr^ ← word;
};
}}};
SetNext: PROC [a: Array, d: Dim, index, clai, next: NAT] = TRUSTED {
IF index = 0 THEN ERROR;
{rpd: SidedPortData = NARROW[a.roles[d].refs[index]];
ls: Links = rpd.links;
wordPtr: WordPtr = @ls[Basics.BITSHIFT[clai, ls.negLgLinksPerWord]];
leftShift: INTEGER = ls.linkSize * INTEGER[Basics.BITAND[clai, last[ls.lgLinksPerWord]]];
shiftedMask: WORD = Basics.BITNOT[Basics.BITSHIFT[last[ls.linkSize], leftShift]];
shiftedNext: WORD = Basics.BITSHIFT[next, leftShift];
word: WORD = Basics.BITOR[shiftedNext, Basics.BITAND[shiftedMask, wordPtr^]];
IF Basics.BITAND[shiftedNext, shiftedMask] # 0 THEN ERROR;
wordPtr^ ← word;
}};
last: ARRAY [0 .. Basics.bitsPerWord] OF WORD = [
00000H,
00001H, 00003H, 00007H, 0000FH,
0001FH, 0003FH, 0007FH, 000FFH,
001FFH, 003FFH, 007FFH, 00FFFH,
01FFFH, 03FFFH, 07FFFH, 0FFFFH];
EnsurePortForGroups: PUBLIC PROC [act: CellType, gis, giis: ARRAY End OF Nat2, gss: GroupListPair] RETURNS [ap: Port] = {
a: Array = act.asArray;
ais: ARRAY End OF ArrayIndex = [AgiToAi[a, gis[low], giis[low]], AgiToAi[a, gis[high], giis[high]]];
Enumerate: PROC [Consume: PROC [ai: ArrayIndex, ep: Port] RETURNS [stop: BOOLFALSE]] RETURNS [aborted: BOOL] = {
FOR side: End IN End DO
FOR gs: GroupList ← gss[side], gs.rest WHILE gs # NIL DO
g: Group = gs.first;
FOR ps: PortList ← g.ports, ps.rest WHILE ps # NIL DO
IF Consume[ais[side], ps.first] THEN RETURN [TRUE];
ENDLOOP;
ENDLOOP;
ENDLOOP;
aborted ← FALSE;
};
Search: PROC [ai: ArrayIndex, ep: Port] RETURNS [stop: BOOLFALSE] = {
stop ← (NOT Central[a, ai]) AND (ap ← GetArrayPortForPort[act, a, ai, ep, FALSE]) # NIL;
};
Export: PROC [ai: ArrayIndex, ep: Port] RETURNS [stop: BOOLFALSE] = {
IF NOT Central[a, ai] THEN SetArrayPortForPort[a, ai, ep, ap];
};
IF Enumerate[Search] THEN RETURN;
IF act.port = NIL THEN ERROR --is it true that a cell type always has a port?--;
ap ← FullyAddPort[[parent: act.port]].port;
IF Enumerate[Export] THEN ERROR;
};
CrossATie: PUBLIC PROC [ct: CellType, d: Dim, fromP: Port, fromS: End] RETURNS [toP: Port] = {
toS: End = OtherEnd[fromS];
a: Array = ct.asArray;
tf: INT = a.jointsPeriod[Foo];
tb: INT = a.jointsPeriod[Bar];
candidates: PortList ← NIL;
first: BOOLTRUE;
FOR ff: INT IN [0 .. tf) DO FOR fb: INT IN [0 .. tb) DO
phase: Nat2 = [ff, fb];
j: Joint = GetArrayJoint[a, d, phase];
FOR jgif: NAT IN [0 .. j.groupingParmses[Foo].sum) DO FOR jgib: NAT IN [0 .. j.groupingParmses[Bar].sum) DO
jgi2: Nat2 = [jgif, jgib];
jgi: NAT = j.groupingParmses[Bar].sum * jgif + jgib;
gif: NAT = Jgi2ToGi[a, d, phase, j, jgi2, fromS].gi;
gf: Group = GetGroup[a, gif, fromP, FALSE];
IF gf = NIL THEN RETURN [NIL];
{tie: Tie = FetchTie[j, fromS, jgi, gf];
IF tie = NIL THEN RETURN [NIL];
{gt: Group = tie.groups[toS];
IF gt = NIL THEN NULL
ELSE IF first THEN {first ← FALSE; candidates ← gt.ports}
ELSE candidates ← NARROW[GList.Intersection[candidates, gt.ports]];
IF candidates = NIL THEN RETURN [NIL];
}}ENDLOOP ENDLOOP;
ENDLOOP ENDLOOP;
toP ← IF candidates # NIL THEN candidates.first ELSE NIL;
};
END.