BcdTree.Mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Satterthwaite, January 10, 1983 12:38 pm
Russ Atkinson (RRA) March 7, 1985 0:51:38 am PST
DIRECTORY
BcdDefs USING [treetype],
HashTypes USING [HTIndex],
Symbols USING [HTIndex, htNull, STIndex],
Table USING [Base, Finger, Limit, Selector];
Tree: DEFINITIONS = {
treeType: Table.Selector~BcdDefs.treetype;
Base: TYPE~Table.Base;
Finger: TYPE~Table.Finger;
Limit: CARDINAL~Table.Limit;
LitIndex: TYPE = HashTypes.HTIndex;
data structures
Link: TYPE~RECORD [
SELECT tag: * FROM
subtree => [index: Tree.Index],
hash => [index: Symbols.HTIndex],
symbol => [index: Symbols.STIndex],
literal => [index: LitIndex]
ENDCASE];
Node: TYPE~MACHINE DEPENDENT RECORD [
free (0: 0..0): BOOL, -- reserved for allocator
name (0: 1..4): NodeName,
attrs (0: 5..7): PACKED ARRAY AttrId OF BOOLALL[FALSE],
shared (0: 8..8): BOOL,
nSons (0: 9..15): [0..maxNSons],
info (1): Tree.Info,
son (2): ARRAY [1..1) OF Tree.Link];
Info: TYPE~CARDINAL;
AttrId: TYPE~{codeLinks, explicitLinkLoc, exportsALL};
maxNSons: CARDINAL~177b;
Index: TYPE~Base RELATIVE POINTER[0..Limit) TO Tree.Node;
nullIndex: Tree.Index~Tree.Index.FIRST;
null: Tree.Link~[subtree[index~Tree.nullIndex]];
nullId: Tree.Link~[hash[index~Symbols.htNull]];
NodeName: TYPE~{
general tree constructors
list, item,
declarations
source,
config,
expressions
module,
assign,
plus,
then,
file names
dot,
slash,
nil
none
};
tree manipulation
Id: TYPE~RECORD [baseP: 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];
}.