TreeSliceImpl.mesa; written by Bill Paxton, June 1981
edited by McGregor, February 14, 1983 1:59 pm
edited by Bill Paxton, June 1, 1983 10:39 am
edited by Maxwell, January 5, 1983 12:47 pm
DIRECTORY
TreeSlice,
TiogaNode,
TiogaNodeOps;
TreeSliceImpl:
CEDAR MONITOR
IMPORTS TiogaNodeOps EXPORTS TreeSlice, TiogaNodeOps = BEGIN
OPEN TreeSlice, TiogaNodeOps;
***** Slice support routines
freeSlice: Slice; -- free list of slices
numFreeSlices: NAT ← 0;
maxFreeSlices: NAT = 15;
minSliceSize: NAT = 10;
RefTextNode: TYPE = TiogaNode.RefTextNode;
GetSlice:
PUBLIC
ENTRY
PROC [len:
NAT]
RETURNS [slice: Slice] = {
ENABLE UNWIND => NULL;
IF freeSlice #
NIL
THEN {
-- look on free list
prev: Slice;
IF freeSlice.maxLength >= len
THEN {
-- take the first from list
slice ← freeSlice; freeSlice ← freeSlice.next;
slice.next ← NIL;
numFreeSlices ← numFreeSlices-1; RETURN };
prev ← freeSlice;
FOR s: Slice ← freeSlice.next, s.next
UNTIL s=
NIL
DO
IF s.maxLength >= len
THEN {
-- take this one
prev.next ← s.next; s.next ← NIL;
numFreeSlices ← numFreeSlices-1; RETURN [s] };
prev ← s;
ENDLOOP };
RETURN [NEW[SliceArray[MAX[len,minSliceSize]]]] };
FreeSlice:
PUBLIC
ENTRY
PROC [slice: Slice] = {
ENABLE UNWIND => NULL;
IF slice=
NIL
OR numFreeSlices >= maxFreeSlices
OR slice.maxLength < minSliceSize
THEN RETURN;
FOR i:NAT IN [0..slice.length) DO slice[i] ← NIL; ENDLOOP;
slice.next ← freeSlice; freeSlice ← slice;
numFreeSlices ← numFreeSlices+1 };
MakeSlices:
PROC [node: Ref]
RETURNS [before, after: Slice] = {
--
before[0]=root; before[i]=Parent[before[i+1]]; before[before.length-1]=node
after[i]=Next[before[i]]
if IsBranch[node] and BranchChild[node]#NIL THEN after[before.length]=node.child
--
last: NAT;
br, child: TiogaNode.RefBranchNode;
Slicer:
PROC [node: Ref, height:
NAT]
RETURNS [level:
NAT] = {
height ← height+1;
IF node=
NIL
THEN {
-- have gone beyond root
before ← GetSlice[height]; before.kind ← before;
after ← GetSlice[height+1]; after.kind ← after;
RETURN [0] };
level ← Slicer[TiogaNodeOps.Parent[node],height];
before[level] ← node;
after[level] ← TiogaNodeOps.Next[node];
RETURN [level+1] };
IF node=NIL THEN RETURN;
last ← Slicer[node,0];
before.length ← last;
IF (br ← TiogaNodeOps.NarrowToBranchNode[node]) #
NIL
AND
(child ← TiogaNodeOps.BranchChild[br]) # NIL THEN {
after[last] ← child; after.length ← last+1 }
ELSE after.length ← last;
FOR i:
NAT ← after.length, i-1
DO
-- delete trailing NIL's from after
IF i=0 THEN { after.length ← 0; EXIT };
IF after[i-1] # NIL THEN { after.length ← i; EXIT };
ENDLOOP };
CompareSliceOrder:
PUBLIC
PROC [s1, s2: Slice]
RETURNS [order: NodeOrder] = {
determines relative order in tree of last nodes in the slices
returns "same" if slices are identical
returns "before" if last node of s1 comes before last node of s2
returns "after" if last node of s1 comes after last node of s2
returns "disjoint" if slices are not from the same tree
s1Len, s2Len: NAT;
IF s1=
NIL
OR s2=
NIL
OR (s1Len←s1.length)=0
OR (s2Len←s2.length)=0
OR s1[0] # s2[0]
THEN RETURN [disjoint];
IF s1.kind # before OR s2.kind # before THEN ERROR; -- only valid for parent slices
FOR i:
NAT ← 1, i+1
DO
-- know that s1[j]=s2[j] for j<i
SELECT i
FROM
s1Len => {
IF i=s2Len THEN RETURN [same]; -- s1Last=s2Last
RETURN [before] }; -- s1Last is a parent of s2Last
s2Len => RETURN [after]; -- s2Last is a parent of s1Last
ENDCASE;
IF s1[i] # s2[i]
THEN {
-- they are siblings, so can check order by Next's
s2Node: Ref ← s2[i];
FOR n:Ref ← TiogaNodeOps.Next[s1[i]], TiogaNodeOps.Next[n]
DO
-- search from s1 to s2
SELECT n
FROM
s2Node => RETURN [before];
NIL => RETURN [after];
ENDCASE;
ENDLOOP };
ENDLOOP };
CompareNodeOrder:
PUBLIC
PROC [node1, node2: Ref]
RETURNS [order: NodeOrder] = {
s1, s2: Slice;
IF node1=NIL OR node2=NIL THEN RETURN [disjoint];
IF node1=node2 THEN RETURN [same];
s1 ← MakeParentSlice[node1];
s2 ← MakeParentSlice[node2];
order ← CompareSliceOrder[s1,s2];
FreeSlice[s1]; FreeSlice[s2] };
MakeParentSlice:
PROC [node: Ref]
RETURNS [slice: Slice] = {
result is same as MakeSlices[node].before
Slicer:
PROC [node: Ref, height:
NAT]
RETURNS [level:
NAT] = {
height ← height+1;
IF node=
NIL
THEN {
-- have gone beyond root
slice ← GetSlice[height]; slice.kind ← before;
RETURN [0] };
level ← Slicer[TiogaNodeOps.Parent[node],height];
slice[level] ← node;
RETURN [level+1] };
IF node=NIL THEN RETURN;
slice.length ← Slicer[node,0] };
SliceOrder:
PUBLIC
PROC [alpha, beta: Span, aBefore, aBottom, bBefore, bBottom: Slice]
RETURNS [overlap: BOOLEAN, head, tail: Span, startOrder, endOrder: NodeOrder] = {
IF CompareSliceOrder[aBottom,bBefore]#after
--alphaend before betastart
OR CompareSliceOrder[aBefore,bBottom]#before
--alphastart after betaend
THEN { overlap ← FALSE; RETURN };
startOrder ← CompareSliceOrder[aBefore,bBefore];
endOrder ← CompareSliceOrder[aBottom,bBottom];
head ←
SELECT startOrder
FROM
before => [alpha.start,TiogaNodeOps.BackLoc[beta.start]],
same => TiogaNode.nullSpan,
after => [beta.start,TiogaNodeOps.BackLoc[alpha.start]],
ENDCASE => ERROR;
tail ←
SELECT endOrder
FROM
before => [TiogaNodeOps.ForwardLoc[alpha.end],beta.end],
same => TiogaNode.nullSpan,
after => [TiogaNodeOps.ForwardLoc[beta.end],alpha.end],
ENDCASE => ERROR;
overlap ← TRUE };
END.