<<>> <> <> <> <> <> <> 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}; }.