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