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,
TiogaTreeOps;
TreeSliceImpl:
CEDAR MONITOR
IMPORTS TiogaNodeOps, TiogaTreeOps EXPORTS TreeSlice SHARES TiogaNode = BEGIN
OPEN TreeSlice;
***** Slice support routines
freeSlice: Slice; -- free list of slices
numFreeSlices: NAT ← 0;
maxFreeSlices: NAT = 15;
minSliceSize: NAT = 10;
Ref: TYPE = TiogaNode.Ref;
Path: TYPE = TiogaNode.Path;
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:
PUBLIC
PROC [node: RefBranchNode]
RETURNS [before, after: Slice] = {
last: NAT;
Slicer:
PROC [node: Ref, height:
NAT]
RETURNS [level:
NAT] = {
parent: Ref ← TiogaTreeOps.Parent[node];
height ← height+1;
IF parent=
NIL
OR ~TiogaNodeOps.IsBranch[parent]
THEN {
-- have reached end of slice
before ← GetSlice[height]; before.kind ← before;
after ← GetSlice[height+1]; after.kind ← after;
before[0] ← IF parent#NIL THEN parent ELSE node;
after[0] ← NIL;
RETURN [1] };
level ← Slicer[parent, height];
before[level] ← node;
after[level] ← TiogaTreeOps.Next[node];
RETURN [level+1] };
IF node=NIL THEN RETURN;
last ← Slicer[node,0];
before.length ← last;
IF (node ← TiogaTreeOps.BranchChild[node]) # NIL THEN { after[last] ← node; 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 };
DeletePrefix:
PUBLIC
PROC [slice: Slice, depth:
NAT] = {
remove entries from start of slice
newLen: NAT;
IF slice.length < depth THEN ERROR;
newLen ← slice.length-depth;
FOR i:NAT IN [0..newLen) DO slice[i] ← slice[i+depth]; ENDLOOP;
FOR i:NAT IN [newLen..slice.length) DO slice[i] ← NIL; ENDLOOP;
slice.length ← newLen };
InsertPrefix:
PUBLIC PROC [first, last: Slice, firstLen:
NAT]
RETURNS [new: Slice] = {
new[i]=first[i] for i in [0..firstLen)
new[i+firstLen]=last[i] for i in [0..last.length)
new.length=last.length+firstLen
newLen: NAT;
IF first =
NIL
OR last =
NIL
OR first.kind # before
OR last.kind # before
OR
first.length < firstLen THEN ERROR;
new ← GetSlice[newLen ← firstLen + last.length];
new.kind ← before; new.length ← newLen;
FOR i: NAT IN [0..firstLen) DO new[i] ← first[i]; ENDLOOP;
FOR i: NAT IN [0..last.length) DO new[firstLen+i] ← last[i]; ENDLOOP };
CompareSliceOrder:
PUBLIC
PROC [s1, s2: Slice]
RETURNS [order: Order] = {
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 THEN RETURN [disjoint];
IF s1.kind # before OR s2.kind # before THEN ERROR; -- only valid for parent slices
s1Len ← s1.length; s2Len ← s2.length;
IF s1Len=0 OR s2Len=0 OR s1[0] # s2[0] THEN RETURN [disjoint];
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 scanning siblings
s2Node: Ref ← s2[i];
FOR n: Ref ← s1[i], n.next
DO
-- search from fp1 to fp2
IF s2Node=n THEN RETURN [before];
IF n.last THEN RETURN [after];
ENDLOOP };
ENDLOOP };
SliceOrder:
PUBLIC
PROC [alpha, beta: TiogaTreeOps.BranchSpan, aBefore, aBottom, bBefore, bBottom: Slice]
RETURNS [overlap: BOOLEAN, head, tail: TiogaTreeOps.BranchSpan, startOrder, endOrder: Order] = {
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,TiogaTreeOps.MakeBranchLoc[TiogaTreeOps.Backward[beta.start.node].back]],
same => TiogaTreeOps.nullBranchSpan,
after => [beta.start,TiogaTreeOps.MakeBranchLoc[TiogaTreeOps.Backward[alpha.start.node].back]],
ENDCASE => ERROR;
tail ←
SELECT endOrder
FROM
before => [TiogaTreeOps.MakeBranchLoc[TiogaTreeOps.Forward[alpha.end.node].nx],beta.end],
same => TiogaTreeOps.nullBranchSpan,
after => [TiogaTreeOps.MakeBranchLoc[TiogaTreeOps.Forward[beta.end.node].nx],alpha.end],
ENDCASE => ERROR;
overlap ← TRUE };
END.