<> <> <> <> 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] = { <<-->> <> <> <> <<-->> 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] = { <> <> <> <> <> <<>> 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 { 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] = { <> 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.