DIRECTORY TreeSlice, TiogaNode, TiogaNodeOps, TiogaTreeOps; TreeSliceImpl: CEDAR MONITOR IMPORTS TiogaNodeOps, TiogaTreeOps EXPORTS TreeSlice SHARES TiogaNode = BEGIN OPEN TreeSlice; 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. š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 ***** Slice support routines remove entries from start of 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 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 Êm˜Jšœ5™5Jšœ-™-Jšœ,™,Jšœ+™+J˜JšÏk ˜ J˜ J˜ J˜ J˜ J˜šœ œ˜Jšœœ œ ˜MJšœ ˜—J˜Jšœ™J˜JšœÏc˜(Jšœœ˜Jšœœ˜Jšœœ˜J˜Jšœœ˜Jšœœ˜Jšœ œ˜*J˜š Ïnœœœœœœ˜AJšœœœ˜šœ œœž˜.J˜ šœœž˜@J˜.Jšœ œ˜Jšœ!œ˜*—J˜šœ#œœ˜4šœœž˜-Jšœœ˜!Jšœ!œ˜.—J˜ Jšœ˜ ——Jšœœ œ˜2J˜—šŸ œœœœ˜/Jšœœœ˜šœœœ œ˜PJšœœ˜ —Jš œœœœ œœ˜:J˜*J˜"J˜—šŸ œœœœ˜PJšœœ˜ š Ÿœœœœ œ˜>Jšœ(˜(J˜š œœœ œž˜SJ˜0J˜/Jš œ œœœœ˜0Jšœ œ˜Jšœ˜ —Jšœ˜Jšœ˜Jšœ'˜'Jšœ ˜—Jšœœœœ˜J˜J˜Jšœ+œœ.˜cJšœ˜šœœœž#˜EJšœœœ˜'Jšœœœœ˜4Jšœ˜ J˜——šŸ œœœœ˜8Jšœ"™"Jšœœ˜ Jšœœœ˜#J˜Jš œœœ œœ˜?Jš œœœœ œœ˜?J˜J˜—šŸ œ œ œœ˜VJšž&™&Jšž1™1Jšž™Jšœœ˜ š œ œœœœœ˜LJšœœœ˜#—J˜0J˜'Jš œœœœœ˜:Jš œœœœœ˜GJ˜—šŸœœœœ˜IJ˜Jšœ=™=Jšœ&™&Jšœ@™@Jšœ>™>Jšœ7™7J™Jšœœ˜Jš œœœœœœ ˜+Jš œœœœž˜SJšœ%˜%Jš œ œ œœœ ˜>šœœ œž ˜6šœ˜ ˜ Jšœ œœ ž˜/Jšœ ž˜2—Jšœ œ ž˜8Jšœ˜—šœœž=˜UJ˜šœœž˜7Jšœ œœ ˜!Jšœœœ ˜Jšœ˜ ——Jšœ˜ J˜——šŸ œœœR˜iJšœ œG˜`šœ*ž˜Gšœ+ž˜GJšœ œœ˜!——J˜0J˜.šœœ ˜Jšœ`˜`Jšœ$˜$Jšœ_˜_Jšœœ˜—šœœ ˜JšœY˜YJšœ$˜$JšœX˜XJšœœ˜—Jšœ œ˜J˜—Jšœ˜J˜J˜—…—îõ