[_CDCSL_93-16_]<1>Cedar>release>Cinder>MobTreePack.mesa

MobTreePack.mesa

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

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

procedures for tree testing

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

procedures for tree traversal

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

procedures for list testing

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

procedures for list traversal

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

cross-table tree manipulation

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