TiogaPathOrderImpl.mesa; written by Bill Paxton, June 1981
edited by Bill Paxton, July 18, 1983 2:40 pm
DIRECTORY
TiogaPathOrder,
TiogaNode,
TiogaNodeOps,
TiogaPathOps;
TiogaPathOrderImpl:
CEDAR MONITOR
IMPORTS TiogaPathOps EXPORTS TiogaPathOrder SHARES TiogaNode = BEGIN
OPEN TiogaPathOrder;
***** FullPath support routines
freeFullPath: FullPath; -- free list
numFreeFullPaths: NAT ← 0;
maxFreeFullPaths: NAT = 15;
minFullPathSize: NAT = 10;
GetFullPath:
ENTRY
PROC [len:
NAT]
RETURNS [fp: FullPath] = {
ENABLE UNWIND => NULL;
IF freeFullPath #
NIL
THEN {
-- look on free list
prev: FullPath;
IF freeFullPath.maxLength >= len
THEN {
-- take the first from list
fp ← freeFullPath; freeFullPath ← freeFullPath.next;
fp.next ← NIL;
numFreeFullPaths ← numFreeFullPaths-1; RETURN };
prev ← freeFullPath;
FOR fp: FullPath ← freeFullPath.next, fp.next
UNTIL fp=
NIL
DO
IF fp.maxLength >= len
THEN {
-- take this one
prev.next ← fp.next; fp.next ← NIL;
numFreeFullPaths ← numFreeFullPaths-1; RETURN [fp] };
prev ← fp;
ENDLOOP };
RETURN [NEW[FullPathArray[MAX[len,minFullPathSize]]]] };
FreeFullPath:
PUBLIC ENTRY
PROC [fp: FullPath] = {
ENABLE UNWIND => NULL;
IF fp=
NIL
OR numFreeFullPaths >= maxFreeFullPaths
OR fp.maxLength < minFullPathSize
THEN RETURN;
FOR i:NAT IN [0..fp.length) DO fp[i] ← NIL; ENDLOOP;
fp.next ← freeFullPath; freeFullPath ← fp;
numFreeFullPaths ← numFreeFullPaths+1 };
CompareFullPaths:
PUBLIC PROC [fp1, fp2: FullPath]
RETURNS [order: Order] = {
determines relative order in tree of last nodes in the fps
returns "same" if fps are identical
returns "before" if last node of fp1 comes before last node of fp2
returns "after" if last node of fp1 comes after last node of fp2
returns "disjoint" if fps are not from the same tree
fp1Len, fp2Len: NAT;
IF fp1=
NIL
OR fp2=
NIL
OR (fp1Len𡤏p1.length)=0
OR (fp2Len𡤏p2.length)=0
OR fp1[0] # fp2[0]
THEN RETURN [disjoint];
FOR i:
NAT ← 1, i+1
DO
-- know that fp1[j]=fp2[j] for j<i
SELECT i
FROM
fp1Len => {
IF i=fp2Len THEN RETURN [same]; -- fp1Last=fp2Last
RETURN [before] }; -- fp1Last is a parent of fp2Last
fp2Len => RETURN [after]; -- fp2Last is a parent of fp1Last
ENDCASE;
IF fp1[i] # fp2[i]
THEN {
-- they are siblings, so can check order by scanning siblings
Since applications and formals are included in full paths, can simply use next pointers in nodes rather than calling TiogaPathOps.Next
fp2Node: Ref ← fp2[i];
FOR n: Ref ← fp1[i], n.next
DO
-- search from fp1 to fp2
IF fp2Node=n THEN RETURN [before];
IF n.last THEN RETURN [after];
ENDLOOP };
ENDLOOP };
Compare:
PUBLIC
PROC [path1, path2: Path]
RETURNS [order: Order] = {
fp1, fp2: FullPath;
IF path1.node=NIL OR path2.node=NIL THEN RETURN [disjoint];
IF TiogaPathOps.Equal[path1, path2] THEN RETURN [same];
fp1 ← MakeFullPath[path1];
fp2 ← MakeFullPath[path2];
order ← CompareFullPaths[fp1,fp2];
FreeFullPath[fp1]; FreeFullPath[fp2] };
MakeFullPath:
PUBLIC
PROC [p: Path]
RETURNS [fp: FullPath] = {
before[0]=root; before[i]=PathParent[before[i+1]]; before[before.length-1]=p.node
FullPathMaker:
PROC [path: Path, height:
NAT]
RETURNS [level:
NAT] = {
height ← height+1;
IF path.node=
NIL
THEN {
-- have gone beyond root
fp ← GetFullPath[height];
RETURN [0] };
level ← FullPathMaker[PathParent[path],height];
fp[level] ← path.node;
RETURN [level+1] };
PathParent:
PROC [p: Path]
RETURNS [parent: Path] =
INLINE {
Similar to TiogaPathOps.Parent, but includes applications and formals.
node: Ref;
IF (node ← p.node)=NIL THEN RETURN [[NIL,NIL]];
UNTIL node.last DO node ← node.next; ENDLOOP;
IF node.next # NIL THEN RETURN [[node.next, p.path]];
IF p.path=NIL THEN RETURN [[NIL,NIL]];
RETURN [p.path^] };
IF p.node=NIL THEN RETURN;
fp.length ← FullPathMaker[p,0] };
END.