InternalTree.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Satterthwaite, May 8, 1986 4:15:01 pm PDT
DIRECTORY
Table: TYPE USING [Base, Finger, Selector, Limit, chunkType],
XTree: TYPE Tree USING [AttrId, Info, Link, NodeName, maxNSons],
Literals: TYPE USING [LitIndex],
Symbols: TYPE USING [ISEIndex, Name, nullName];
Tree: DEFINITIONS = {
treeType: Table.Selector = Table.chunkType;
Base: TYPE = Table.Base;
Finger: TYPE = Table.Finger;
Limit: CARDINAL = Table.Limit;
data structures
Link:
TYPE =
MACHINE DEPENDENT RECORD[
vp(0: 0..31):
SELECT tag(0): *
FROM
subtree => [index(1): Tree.Index],
hash => [index(1): Symbols.Name],
symbol => [index(1): Symbols.ISEIndex],
literal => [index(1): Literals.LitIndex],
ENDCASE];
Node:
TYPE =
MACHINE
DEPENDENT
RECORD[
free (0: 0..0): BOOL, -- reserved for allocator
name (0: 1..8): Tree.NodeName,
attr1 (0: 9..9), attr2 (0: 10..10), attr3 (0: 11..11): BOOL,
shared (0: 12..12): BOOL,
nSons (0: 13..15): [0..maxNSons],
info (1): Tree.Info,
son (2): ARRAY [1..1) OF Tree.Link];
NodeName: TYPE = XTree.NodeName;
Info: TYPE = XTree.Info;
AttrId: TYPE = XTree.AttrId;
maxNSons: NAT = XTree.maxNSons;
Index: TYPE = Base RELATIVE POINTER[0..CARDINAL.LAST) TO Tree.Node;
NullIndex: Tree.Index = Tree.Index.FIRST;
Null: Tree.Link = [subtree[index: Tree.NullIndex]];
NullId: Tree.Link = [hash[index: Symbols.nullName]];
tree manipulation
Id: TYPE = RECORD[baseP: Tree.Finger, link: Tree.Link];
Scan: TYPE = PROC[t: Tree.Link];
Map: TYPE = PROC[t: Tree.Link] RETURNS[v: Tree.Link];
Test: TYPE = PROC[t: Tree.Link] RETURNS[BOOL];
cross tree manipulation
MapToX: TYPE = PROC[t: Tree.Link] RETURNS[v: XTree.Link];
MapFromX: TYPE = PROC[t: XTree.Link] RETURNS[v: Tree.Link];
}.