DIRECTORY MPLeaves USING [HTIndex, ISEIndex], MPTree USING [AttrId, Id, Handle, Link, Map, Node, NodeName, Scan, SonId, SubInfo, Test, Null, NullHandle], MPTreeOps USING [], Process USING [GetCurrent, InitializeCondition, EnableAborts, MsecToTicks]; MPTreeImpl: CEDAR MONITOR IMPORTS Process EXPORTS MPTreeOps = BEGIN OPEN MPLeaves, Tree: MPTree; initialized: BOOL ¬ FALSE; StackIncr: CARDINAL = 32; LinkStack: TYPE = RECORD [SEQUENCE size: NAT OF Tree.Link]; stack: REF LinkStack ¬ NIL; sI: NAT; done: CONDITION; InitializeDone: PROC RETURNS [BOOL ¬ FALSE] ~ TRUSTED { Process.InitializeCondition[@done, Process.MsecToTicks[500]]; Process.EnableAborts[@done]; }; inUse: BOOL ¬ InitializeDone[]; owner: PROCESS ¬ NIL; Initialize: PUBLIC ENTRY PROC = { WHILE inUse DO WAIT done; ENDLOOP; owner ¬ Process.GetCurrent[]; IF initialized THEN initialized ¬ FALSE; stack ¬ AllocStack[StackIncr]; sI ¬ 0; initialized ¬ TRUE; }; Reset: PUBLIC PROC = { IF owner # Process.GetCurrent[] THEN ERROR; -- Client misuse IF initialized AND stack.size > 2*StackIncr THEN stack ¬ AllocStack[StackIncr]; }; Finalize: PUBLIC PROC = { LockedFinalize: ENTRY PROC ~ { inUse ¬ FALSE; initialized ¬ FALSE; owner ¬ NIL; }; IF owner # Process.GetCurrent[] THEN ERROR; -- Client misuse LockedFinalize[]; }; AllocStack: PROC [size: NAT, forceNew: BOOL ¬ FALSE] RETURNS [st: REF LinkStack] = { st ¬ IF forceNew THEN NIL ELSE stack; IF st = NIL OR st.size < size THEN st ¬ NEW[LinkStack[size]]; }; ExpandStack: PROC = { newStack: REF LinkStack = AllocStack[stack.size+StackIncr, TRUE]; FOR i: NAT IN [0 .. stack.size) DO newStack[i] ¬ stack[i] ENDLOOP; stack ¬ newStack}; PushTree: PUBLIC PROC [v: Tree.Link] = { IF owner # Process.GetCurrent[] THEN ERROR; -- Client misuse IF sI >= stack.size THEN ExpandStack[]; stack[sI] ¬ v; sI ¬ sI+1; }; PopTree: PUBLIC PROC RETURNS [Tree.Link] = { IF owner # Process.GetCurrent[] THEN ERROR; -- Client misuse RETURN [stack[sI¬sI-1]]; }; InsertTree: PUBLIC PROC [v: Tree.Link, n: NAT] = { i: NAT ¬ sI; IF sI >= stack.size THEN ExpandStack[]; sI ¬ sI+1; THROUGH [1 .. n) DO stack[i] ¬ stack[i-1]; i ¬ i-1 ENDLOOP; stack[i] ¬ v}; ExtractTree: PUBLIC PROC [n: NAT] RETURNS [v: Tree.Link] = { i: NAT ¬ sI - n; v ¬ stack[i]; THROUGH [1 .. n) DO stack[i] ¬ stack[i+1]; i ¬ i+1 ENDLOOP; sI ¬ sI - 1; RETURN}; MakeNode: PUBLIC PROC [name: Tree.NodeName, count: INTEGER] RETURNS [Tree.Link] = { PushNode[name, count]; RETURN [PopTree[]]}; MakeList: PUBLIC PROC [size: INTEGER] RETURNS [Tree.Link] = { PushList[size]; RETURN [PopTree[]]}; PushNode: PUBLIC PROC [name: Tree.NodeName, count: INTEGER] = { nSons: NAT = ABS[count]; node: Tree.Handle = NEW[Tree.Node[nSons]]; node.name ¬ name; IF count >= 0 THEN FOR i: Tree.SonId DECREASING IN [1..nSons] DO node.son[i] ¬ stack[sI¬sI-1] ENDLOOP ELSE FOR i: Tree.SonId IN [1..nSons] DO node.son[i] ¬ stack[sI¬sI-1] ENDLOOP; IF sI >= stack.size THEN ExpandStack[]; stack[sI] ¬ node; sI ¬ sI+1}; PushList: PUBLIC PROC [size: INTEGER] = { nSons: NAT = ABS[size]; SELECT nSons FROM 1 => NULL; 0 => PushTree[Tree.Null]; ENDCASE => { node: Tree.Handle = NEW[Tree.Node[nSons]]; node.name ¬ list; IF size > 0 THEN FOR i: Tree.SonId DECREASING IN [1..nSons] DO node.son[i] ¬ stack[sI¬sI-1] ENDLOOP ELSE FOR i: Tree.SonId IN [1..nSons] DO node.son[i] ¬ stack[sI¬sI-1] ENDLOOP; IF sI >= stack.size THEN ExpandStack[]; stack[sI] ¬ node; sI ¬ sI+1}}; PushProperList: PUBLIC PROC [size: INTEGER] = { IF size NOT IN [-1..1] THEN PushList[size] ELSE { node: Tree.Handle = NEW[Tree.Node[ABS[size]]]; node.name ¬ list; IF size # 0 THEN node.son[1] ¬ PopTree[]; PushTree[node]; }}; SetInfo: PUBLIC PROC [info: CARDINAL] = { v: Tree.Link = stack[sI-1]; WITH v SELECT FROM node: Tree.Handle => node.info ¬ info; ENDCASE => ERROR}; SetSubInfo: PUBLIC PROC [subInfo: Tree.SubInfo] = { v: Tree.Link = stack[sI-1]; WITH v SELECT FROM node: Tree.Handle => node.subInfo¬ subInfo; ENDCASE => ERROR}; SetAttr: PUBLIC PROC [which: Tree.AttrId, value: BOOL] = { v: Tree.Link = stack[sI-1]; WITH v SELECT FROM node: Tree.Handle => node.attr[which] ¬ value; ENDCASE => ERROR}; GetHash: PUBLIC PROC [t: Tree.Link] RETURNS [HTIndex] = { RETURN [WITH t SELECT FROM id: HTIndex => id, ENDCASE => ERROR]}; GetNode: PUBLIC PROC [t: Tree.Link] RETURNS [Tree.Handle] = { RETURN [WITH t SELECT FROM node: Tree.Handle => node, ENDCASE => ERROR]}; GetSe: PUBLIC PROC [t: Tree.Link] RETURNS [ISEIndex] = { RETURN [GetHash[t].name]}; NthSon: PUBLIC PROC [t: Tree.Link, n: Tree.SonId] RETURNS [Tree.Link] = { RETURN [WITH t SELECT FROM node: Tree.Handle => node.son[n], ENDCASE => ERROR]}; NSons: PUBLIC PROC [t: Tree.Link] RETURNS [NAT] = { RETURN [WITH t SELECT FROM node: Tree.Handle => node.sonLimit-1, ENDCASE => 0]}; OpName: PUBLIC PROC [t: Tree.Link] RETURNS [Tree.NodeName] = { RETURN [WITH t SELECT FROM node: Tree.Handle => node.name, ENDCASE => none]}; ScanSons: PUBLIC PROC [root: Tree.Link, action: Tree.Scan] = { WITH root SELECT FROM node: Tree.Handle => FOR i: Tree.SonId IN [1 .. node.sonLimit) DO action[node.son[i]] ENDLOOP; ENDCASE}; UpdateLeaves: PUBLIC PROC [root: Tree.Link, map: Tree.Map] RETURNS [v: Tree.Link] = { IF root = Tree.Null THEN v ¬ Tree.Null ELSE WITH root SELECT FROM node: Tree.Handle => { FOR i: Tree.SonId IN [1 .. node.sonLimit) DO node.son[i] ¬ map[node.son[i]] ENDLOOP; v ¬ root}; ENDCASE => v ¬ map[root]; RETURN}; ListLength: PUBLIC PROC [t: Tree.Link] RETURNS [NAT] = { RETURN [ IF t = Tree.Null THEN 0 ELSE WITH t SELECT FROM node: Tree.Handle => IF node.name # list THEN 1 ELSE node.sonLimit-1, ENDCASE => 1]}; ListHead: PUBLIC PROC [t: Tree.Link] RETURNS [Tree.Link] = { RETURN [WITH t SELECT FROM node: Tree.Handle => SELECT TRUE FROM (node.name # list) => t, (node.sonLimit # 1) => node.son[1], ENDCASE => Tree.Null, ENDCASE => t]}; ListTail: PUBLIC PROC [t: Tree.Link] RETURNS [Tree.Link] = { RETURN [WITH t SELECT FROM node: Tree.Handle => SELECT TRUE FROM (node.name # list) => t, (node.sonLimit # 1) => node.son[ListLength[t]], ENDCASE => Tree.Null, ENDCASE => t]}; ScanList: PUBLIC PROC [root: Tree.Link, action: Tree.Scan] = { IF root # Tree.Null THEN WITH root SELECT FROM node: Tree.Handle => IF node.name # list THEN action[root] ELSE FOR i: Tree.SonId IN [1..node.sonLimit) DO action[node.son[i]] ENDLOOP; ENDCASE => action[root]}; ReverseScanList: PUBLIC PROC [root: Tree.Link, action: Tree.Scan] = { IF root # Tree.Null THEN WITH root SELECT FROM node: Tree.Handle => IF node.name # list THEN action[root] ELSE FOR i: Tree.SonId DECREASING IN [1..node.sonLimit) DO action[node.son[i]] ENDLOOP; ENDCASE => action[root]}; SearchList: PUBLIC PROC [root: Tree.Link, test: Tree.Test] = { IF root # Tree.Null THEN WITH root SELECT FROM node: Tree.Handle => IF node.name # list THEN [] ¬ test[root] ELSE FOR i: Tree.SonId IN [1..node.sonLimit) DO IF test[node.son[i]] THEN EXIT ENDLOOP; ENDCASE => [] ¬ test[root]}; UpdateList: PUBLIC PROC [root: Tree.Link, map: Tree.Map] RETURNS [Tree.Link] = { IF root = Tree.Null THEN RETURN [Tree.Null]; WITH root SELECT FROM node: Tree.Handle => { IF node.name # list THEN RETURN [map[root]]; FOR i: Tree.SonId IN [1..node.sonLimit) DO node.son[i] ¬ map[node.son[i]] ENDLOOP; RETURN [root]}; ENDCASE => RETURN [map[root]]}; ReverseUpdateList: PUBLIC PROC [root: Tree.Link, map: Tree.Map] RETURNS [Tree.Link] = { IF root = Tree.Null THEN RETURN [Tree.Null]; WITH root SELECT FROM node: Tree.Handle => { IF node.name # list THEN RETURN [map[root]]; FOR i: Tree.SonId DECREASING IN [1..node.sonLimit) DO node.son[i] ¬ map[node.son[i]] ENDLOOP; RETURN [root]}; ENDCASE => RETURN [map[root]]}; CopyTree: PUBLIC PROC [root: Tree.Id, map: Tree.Map] RETURNS [v: Tree.Link] = { WITH root SELECT FROM sNode: Tree.Handle => { IF sNode = Tree.NullHandle THEN v ¬ Tree.Null ELSE { dNode: Tree.Handle = NEW[Tree.Node[NSons[sNode]]]; dNode.name ¬ sNode.name; dNode.attr ¬ sNode.attr; dNode.info ¬ sNode.info; FOR i: Tree.SonId IN [1..sNode.sonLimit) DO dNode.son[i] ¬ map[sNode.son[i]]; ENDLOOP; v ¬ dNode}}; ENDCASE => v ¬ map[root]; }; IdentityMap: PUBLIC Tree.Map = { RETURN [IF ISTYPE[t, Tree.Handle] THEN CopyTree[t, IdentityMap] ELSE t]}; END. ‚ MPTreeImpl.mesa Copyright Σ 1985, 1986, 1987, 1991 by Xerox Corporation. All rights reserved. Satterthwaite, January 13, 1981 9:27 AM Russ Atkinson (RRA) January 19, 1987 7:53:05 pm PST Michael Plass, September 6, 1991 0:11 am PDT procedures for tree testing procedures for tree traversal procedures for list testing procedures for list traversal cross-table tree manipulation Κ œ–(cedarcode) style•NewlineDelimiter ™codešœ™Kšœ ΟeœC™NKšœ(™(K™3K™,—K˜šΟk ˜ Kšœ žœ˜#Kšœžœ_˜kKšœ žœ˜Kšœžœ>˜KK˜—š Οn œžœžœžœ žœ ˜=Kšžœžœ˜"K˜Kšœ žœžœ˜K˜Kšœ žœ˜K˜Kš œ žœžœžœžœžœ ˜;K˜Kšœžœ žœ˜Kšœžœ˜K˜Kšœž œ˜š Ÿœžœžœžœžœžœ˜7Kšœ=˜=Kšœ˜Kšœ˜—Kšœžœ˜Kšœžœžœ˜šŸ œžœž œ˜!šžœž˜Kšžœ˜ Kšžœ˜—Kšœ˜Kšžœ žœžœ˜(K˜K˜Kšœžœ˜Kšœ˜K˜—šŸœžœžœ˜KšžœžœžœΟc˜Kš žœžœžœžœ!žœ ˜MK˜K˜—Kšœ™K˜šŸœžœžœ)˜>šžœžœž˜˜Kšžœžœžœžœ˜I—Kšžœ˜ K˜——šŸ œžœžœ"žœ˜Ušžœ˜Kšžœ˜šž˜šžœžœž˜˜šžœžœ˜)Kšžœ žœ˜*—K˜ —Kšžœ˜———Kšžœ˜K˜K˜—Kšœ™K˜š Ÿ œžœžœžœžœ˜8šžœ˜Kšžœžœ˜šžœžœžœž˜Kšœžœžœžœ˜EKšžœ˜K˜———šŸœžœžœžœ˜<šžœžœžœž˜˜šžœžœž˜K˜K˜#Kšžœ˜——Kšžœ˜K˜——šŸœžœžœžœ˜<šžœžœžœž˜˜šžœžœž˜K˜K˜/Kšžœ˜——Kšžœ˜K˜K˜——Kšœ™K˜šŸœžœžœ)˜>šžœ˜šž˜šžœžœž˜˜šžœ˜Kšžœ ˜šž˜šžœžœ˜'Kšžœžœ˜————Kšžœ˜K˜————šŸœžœžœ)˜Ešžœ˜šž˜šžœžœž˜˜šžœ˜Kšžœ ˜šž˜šžœž œžœ˜2Kšžœžœ˜————Kšžœ˜K˜————šŸ œžœžœ'˜>šžœ˜šž˜šžœžœž˜˜šžœ˜Kšžœ˜šž˜šžœžœ˜'Kš žœžœžœžœžœ˜*————Kšžœ˜K˜————šŸ œžœžœ"žœ˜PKšžœžœžœ ˜,šžœžœž˜˜Kšžœžœžœ ˜,šžœžœ˜'Kšžœ žœ˜*—Kšžœ ˜—Kšžœžœ˜K˜——šŸœžœžœ"žœ˜WKšžœžœžœ ˜,šžœžœž˜˜Kšžœžœžœ ˜,šžœž œžœ˜2Kšžœ žœ˜*—Kšžœ ˜—Kšžœžœ˜K˜K˜——Kšœ™˜šŸœžœžœ žœ˜Ošžœžœž˜˜šžœ˜Kšžœ˜šžœ˜Kšœžœ˜2Kšœ˜Kšœ˜Kšœ˜šžœžœ˜(Kšžœ"˜$Kšžœ˜—K˜ ———Kšžœ˜—Kšœ˜K˜—šœ žœ ˜ šžœžœžœ˜!Kšžœ˜Kšžœ˜ K˜——Kšžœ˜———…—ώ/