DIRECTORY Alloc USING [Handle, Notifier, AddNotify, DropNotify, FreeChunk, GetChunk], MobHashTypes USING [HTIndex], MobSymbols USING [HTIndex], MobTree USING [AttrId, Base, Finger, Index, Info, Link, Map, Node, NodeName, Scan, maxNSons, null, nullIndex, treeType], MobTreeOps USING []; MobTreePack: PROGRAM IMPORTS Alloc EXPORTS MobTreeOps = { LitIndex: TYPE = MobHashTypes.HTIndex; endIndex: MobTree.Index = MobTree.Index.LAST; endMark: MobTree.Link = [subtree[index: endIndex]]; initialized: BOOL ¬ FALSE; table: Alloc.Handle; LinkSeq: TYPE = RECORD[SEQUENCE length: CARDINAL OF MobTree.Link]; LinkStack: TYPE = REF LinkSeq; stack: LinkStack; sI: CARDINAL; tb: MobTree.Base; -- tree base UpdateBase: Alloc.Notifier = {tb ¬ base[MobTree.treeType]}; Initialize: PUBLIC PROC[ownTable: Alloc.Handle] = { IF initialized THEN Finalize[]; stack ¬ NEW[LinkSeq[250]]; sI ¬ 0; table ¬ ownTable; table.AddNotify[UpdateBase]; IF MakeNode[$none,0] # MobTree.null THEN ERROR; -- reserve null initialized ¬ TRUE}; Reset: PUBLIC PROC = { IF initialized AND stack.length > 250 THEN { stack ¬ NEW[LinkSeq[250]]}}; Finalize: PUBLIC PROC = { table.DropNotify[UpdateBase]; table ¬ NIL; stack ¬ NIL; initialized ¬ FALSE}; ExpandStack: PROC = { newStack: LinkStack = NEW[LinkSeq[stack.length + 256]]; FOR i: CARDINAL IN [0 .. stack.length) DO newStack[i] ¬ stack[i] ENDLOOP; stack ¬ newStack}; PushTree: PUBLIC PROC[v: MobTree.Link] = { IF sI >= stack.length THEN ExpandStack[]; stack[sI] ¬ v; sI ¬ sI+1}; PopTree: PUBLIC PROC RETURNS[MobTree.Link] = {RETURN[stack[sI¬sI-1]]}; InsertTree: PUBLIC PROC[v: MobTree.Link, n: CARDINAL] = { i: CARDINAL; IF sI >= stack.length THEN ExpandStack[]; i ¬ sI; sI ¬ sI+1; THROUGH [1 .. n) DO stack[i] ¬ stack[i-1]; i ¬ i-1 ENDLOOP; stack[i] ¬ v}; ExtractTree: PUBLIC PROC[n: CARDINAL] RETURNS[v: MobTree.Link] = { i: CARDINAL ¬ sI - n; v ¬ stack[i]; THROUGH [1 .. n) DO stack[i] ¬ stack[i+1]; i ¬ i+1 ENDLOOP; sI ¬ sI - 1; RETURN[v]}; MakeNode: PUBLIC PROC[name: MobTree.NodeName, count: INTEGER] RETURNS[MobTree.Link] = { PushNode[name, count]; RETURN[PopTree[]]}; PushNode: PUBLIC PROC[name: MobTree.NodeName, count: INTEGER] = { nSons: CARDINAL = count.ABS; units: NAT = MobTree.Node[nSons].SIZE; node: MobTree.Index = table.GetChunk[units, MobTree.treeType]; i: CARDINAL; tb[node].name ¬ name; tb[node].nSons ¬ nSons; tb[node].info ¬ 0; tb[node].shared ¬ FALSE; tb[node].attrs ¬ ALL[FALSE]; IF count >= 0 THEN FOR i ¬ nSons, i-1 WHILE i >= 1 DO tb[node].son[i] ¬ stack[sI¬sI-1] ENDLOOP ELSE FOR i ¬ 1, i+1 WHILE i <= nSons DO tb[node].son[i] ¬ stack[sI¬sI-1] ENDLOOP; IF sI >= stack.length THEN ExpandStack[]; stack[sI] ¬ [subtree[index: node]]; sI ¬ sI+1}; PushList: PUBLIC PROC[size: INTEGER] = { nSons: CARDINAL = size.ABS; node: MobTree.Index; i: CARDINAL; SELECT nSons FROM 1 => NULL; 0 => PushTree[MobTree.null]; ENDCASE => { IF nSons IN (0..MobTree.maxNSons] THEN node ¬ table.GetChunk[MobTree.Node[nSons].SIZE, MobTree.treeType] ELSE { node ¬ table.GetChunk[MobTree.Node[nSons+1].SIZE, MobTree.treeType]; tb[node].son[nSons+1] ¬ endMark}; tb[node].name ¬ $list; tb[node].info ¬ 0; tb[node].shared ¬ FALSE; tb[node].attrs ¬ ALL[FALSE]; tb[node].nSons ¬ IF nSons IN (0..MobTree.maxNSons] THEN nSons ELSE 0; IF size > 0 THEN FOR i ¬ nSons, i-1 WHILE i >= 1 DO tb[node].son[i] ¬ stack[sI¬sI-1] ENDLOOP ELSE FOR i ¬ 1, i+1 WHILE i <= nSons DO tb[node].son[i] ¬ stack[sI¬sI-1] ENDLOOP; IF sI >= stack.length THEN ExpandStack[]; stack[sI] ¬ [subtree[index: node]]; sI ¬ sI+1}}; PushHash: PUBLIC PROC[hti: MobSymbols.HTIndex] = {PushTree[[hash[index: hti]]]}; SetInfo: PUBLIC PROC[info: MobTree.Info] = { WITH stack[sI-1] SELECT FROM v: MobTree.Link.subtree => IF v # MobTree.null THEN tb[v.index].info ¬ info; ENDCASE}; SetAttr: PUBLIC PROC[attr: MobTree.AttrId, value: BOOL] = { WITH stack[sI-1] SELECT FROM v: MobTree.Link.subtree => IF v = MobTree.null THEN ERROR ELSE tb[v.index].attrs[attr] ¬ value; ENDCASE => ERROR}; FreeNode: PUBLIC PROC[node: MobTree.Index] = { IF node # MobTree.nullIndex AND ~tb[node].shared THEN { i: CARDINAL; t: MobTree.Link; n: CARDINAL ¬ tb[node].nSons; IF tb[node].name # $list OR n # 0 THEN FOR i ¬ 1, i+1 WHILE i <= n DO t ¬ tb[node].son[i]; WITH t SELECT FROM subtree => FreeNode[index] ENDCASE; ENDLOOP ELSE { n ¬ 1; FOR i ¬ 1, i+1 UNTIL (t¬tb[node].son[i]) = endMark DO WITH t SELECT FROM subtree => FreeNode[index] ENDCASE; n ¬ n+1; ENDLOOP}; table.FreeChunk[node, MobTree.Node[n].SIZE, MobTree.treeType]}}; FreeTree: PUBLIC PROC[t: MobTree.Link] RETURNS[MobTree.Link] = { WITH t SELECT FROM subtree => FreeNode[index]; ENDCASE; RETURN[MobTree.null]}; GetNode: PUBLIC PROC[t: MobTree.Link] RETURNS[MobTree.Index] = { RETURN[NARROW[t, MobTree.Link.subtree].index]}; MarkShared: PUBLIC PROC[t: MobTree.Link, shared: BOOL] = { WITH t SELECT FROM subtree => IF t # MobTree.null THEN tb[index].shared ¬ shared; ENDCASE}; SonCount: PROC[node: MobTree.Index] RETURNS[CARDINAL] = INLINE { RETURN[SELECT node FROM MobTree.nullIndex, endIndex => 0, ENDCASE => IF tb[node].name = $list AND tb[node].nSons = 0 THEN ListLength[[subtree[index: node]]] ELSE tb[node].nSons]}; ScanSons: PUBLIC PROC[root: MobTree.Link, action: MobTree.Scan] = { IF root # MobTree.null THEN WITH root SELECT FROM subtree => { node: MobTree.Index = index; FOR i: CARDINAL IN [1 .. SonCount[node]] DO action[tb[node].son[i]] ENDLOOP}; ENDCASE; RETURN}; UpdateLeaves: PUBLIC PROC[root: MobTree.Link, map: MobTree.Map] RETURNS[v: MobTree.Link] = { IF root = MobTree.null THEN v ¬ MobTree.null ELSE WITH root SELECT FROM subtree => { node: MobTree.Index = index; FOR i: CARDINAL IN [1 .. SonCount[node]] DO tb[node].son[i] ¬ map[tb[node].son[i]]; ENDLOOP; v ¬ root}; ENDCASE => v ¬ map[root]; RETURN}; ListLength: PUBLIC PROC[t: MobTree.Link] RETURNS[CARDINAL] = { IF t = MobTree.null THEN RETURN[0]; WITH t SELECT FROM subtree => { node: MobTree.Index = index; n: CARDINAL; IF tb[node].name # $list THEN RETURN[1]; n ¬ tb[node].nSons; IF n # 0 THEN RETURN[n]; FOR i: CARDINAL ¬ 1, i+1 UNTIL tb[node].son[i] = endMark DO n ¬ n+1 ENDLOOP; RETURN[n]}; ENDCASE => RETURN[1]}; ScanList: PUBLIC PROC[root: MobTree.Link, action: MobTree.Scan] = { IF root # MobTree.null THEN WITH root SELECT FROM subtree => { node: MobTree.Index = index; i, n: CARDINAL; t: MobTree.Link; IF tb[node].name # $list THEN action[root] ELSE IF (n ¬ tb[node].nSons) # 0 THEN FOR i ¬ 1, i+1 WHILE i <= n DO action[tb[node].son[i]] ENDLOOP ELSE FOR i ¬ 1, i+1 UNTIL (t¬tb[node].son[i]) = endMark DO action[t] ENDLOOP}; ENDCASE => action[root]}; UpdateList: PUBLIC PROC[root: MobTree.Link, map: MobTree.Map] RETURNS[MobTree.Link] = { IF root = MobTree.null THEN RETURN[MobTree.null]; WITH root SELECT FROM subtree => { node: MobTree.Index = index; i, n: CARDINAL; t: MobTree.Link; IF tb[node].name # $list THEN RETURN[map[root]]; IF (n ¬ tb[node].nSons) # 0 THEN FOR i ¬ 1, i+1 WHILE i <= n DO tb[node].son[i] ¬ map[tb[node].son[i]] ENDLOOP ELSE FOR i ¬ 1, i+1 UNTIL (t¬tb[node].son[i]) = endMark DO tb[node].son[i] ¬ map[t] ENDLOOP; RETURN[root]}; ENDCASE => RETURN[map[root]]}; NodeSize: PUBLIC PROC[baseP: MobTree.Finger, node: MobTree.Index] RETURNS[size: CARDINAL] = { IF node = MobTree.nullIndex THEN size ¬ 0 ELSE IF baseP­[node].name # $list OR baseP­[node].nSons # 0 THEN size ¬ MobTree.Node[baseP­[node].nSons].SIZE ELSE { size ¬ MobTree.Node.SIZE + MobTree.Link.SIZE; FOR i: CARDINAL ¬ 1, i+1 UNTIL baseP­[node].son[i] = endMark DO size ¬ size + MobTree.Link.SIZE ENDLOOP}; RETURN}; }. ¨ MobTreePack.mesa Copyright Σ 1985, 1987, 1989, 1991 by Xerox Corporation. All rights reserved. Satterthwaite, April 17, 1986 1:16:48 pm PST Russ Atkinson (RRA) January 21, 1987 1:11:13 pm PST Andy Litman May 12, 1988 3:58:38 pm PDT JKF November 28, 1989 3:23:31 pm PST procedures for tree testing procedures for tree traversal procedures for list testing procedures for list traversal cross-table tree manipulation Κ B•NewlineDelimiter –(cedarcode) style™codešœ™Kšœ ΟeœC™NKšΟy)Πky™,KšœΟkœ ™3Kšž$Ÿ™'K™$—˜š  ˜ Kšœ œ@˜KKšœ  œ ˜Kšœ  œ ˜Kšœ œk˜xKšœ  œ˜K˜——šΟn œ œ œ œ˜9K˜Kšœ  œ˜&K˜Kšœ( œ˜-K˜3K˜Kšœ  œ œ˜K˜Kšœ˜K˜Kš œ  œ œ œ  œ œ˜BKšœ  œ œ ˜K˜Kšœ˜Kšœ œ˜ K˜šœΟc ˜K˜—Kš‘ œ1˜;K˜K˜š‘ œ œ œ˜3Kš œ  œ ˜Kšœ œ˜#K˜K˜Kš œ" œ œ’˜?Kšœ œ˜K˜—š‘œ œ œ˜š œ  œ œ˜,Kšœ œ˜K˜——š‘œ œ œ˜Kšœ& œ˜*Kšœ œ˜ Kšœ œ˜K˜K˜—š‘ œ œ˜Kšœ œ˜7Kš  œ œ œ œ œ˜IKšœ˜K˜K˜—š‘œ œ œ˜*Kš œ œ˜)K˜K˜—Kš ‘œ œ œ œ œ˜FK˜K˜š‘ œ œ œ œ˜9Kšœ œ˜ Kš œ œ˜)K˜Kš œ  œ  œ˜;K˜K˜—š ‘ œ œ œ œ œ˜BKšœ œ ˜K˜ Kš œ  œ  œ˜;K˜ Kš œ˜ K˜K˜—š ‘œ œ œ  œ œ˜WKšœ œ ˜+K˜—š‘œ œ œ  œ˜AKšœ œ  œ˜Kšœ œ œ˜&Kšœ>˜>Kšœ œ˜ K˜.Kšœ& œ˜,Kšœ œ œ˜š œ  ˜Kš œ œ œ" ˜K—š ˜Kš œ  œ  œ" œ˜L—Kš œ œ˜)K˜0K˜—š‘œ œ œ œ˜(Kšœ œ œ˜K˜Kšœ œ˜ š œ ˜Kšœ œ˜ K˜š œ˜ š œ œ ˜&Kšœ* œ˜A—š œ˜Kšœ, œ˜DK˜!—K˜Kšœ& œ˜,Kšœ œ œ˜Kš œ œ œ œ œ˜Eš œ  ˜Kš œ œ œ" ˜K—š ˜Kš œ  œ  œ" œ˜L—Kš œ œ˜)K˜1K˜———Kš‘œ œ œ;˜PK˜š‘œ œ œ˜,š œ  œ ˜Kšœ œ œ˜LKš œ˜ K˜——š‘œ œ œ œ˜;š œ  œ ˜˜Kš œ œ ˜Kš œ!˜%—Kš œ œ˜K˜K˜——š‘œ œ œ˜.š œ œ œ˜7Kšœ œ˜ K˜Kšœ œ˜š œ œ ˜&š œ  œ ˜K˜Kš œ œ œ œ˜6Kš ˜——š œ˜K˜š œ  œ ˜5Kš œ œ œ œ˜6K˜Kš œ˜ ——Kšœ& œ˜@K˜——š‘œ œ œ œ˜@Kš œ œ œ œ˜9Kš œ˜K˜K˜——šœ™K˜š‘œ œ œ œ˜@Kš œ œ"˜/K˜—š‘ œ œ œ œ˜:š œ œ ˜Kšœ  œ œ˜>Kš œ˜ K˜——š ‘œ œ œ œ œ˜@š œ œ ˜K˜!š œ œ œ˜:Kš œ#˜'Kš œ˜K˜K˜————šœ™K˜š‘œ œ œ.˜Cš œ ˜š œ œ ˜˜ K˜š œ œ œ ˜+Kšœ œ˜!——Kš œ˜——Kš œ˜K˜—š‘ œ œ œ' œ˜\Kš œ œ˜,š ˜š œ œ ˜˜ K˜š œ œ œ ˜+K˜'Kš œ˜—K˜ —Kš œ˜——Kš œ˜K˜K˜——šœ™K˜š ‘ œ œ œ œ œ˜>Kš œ œ œ˜#š œ œ ˜˜ K˜Kšœ œ˜ Kš œ œ œ˜(K˜Kš œ œ œ˜Kš  œ œ  œ œ  œ˜LKš œ˜ —Kš œ œ˜K˜———šœ™K˜š‘œ œ œ.˜Cš œ ˜š œ œ ˜˜ K˜Kšœ œ˜K˜Kš œ œ ˜*š œ œ ˜%Kš œ  œ œ ˜>—š ˜Kš œ  œ œ  œ˜I——Kš œ˜K˜———š‘ œ œ œ' œ˜WKš œ œ œ˜1š œ œ ˜˜ K˜Kšœ œ˜K˜Kš œ œ œ ˜0š œ ˜ Kš œ  œ œ( ˜M—š ˜š œ  œ ˜5Kšœ œ˜!——Kš œ˜—Kš œ œ ˜K˜———Kšœ™˜š ‘œ œ œ- œ œ˜]Kš œ œ ˜)š œ œ œ ˜@Kšœ( œ˜-—š œ˜Kšœ œ œ˜-š œ œ  œ ˜?Kšœ œ œ˜)——Kš œ˜K˜—K˜K˜——…—€*j