[Indigo]<Cedar5.3>Binder>BcdTree.mesa!1

file BcdTree.Mesa

last modified by Satterthwaite, January 10, 1983 12:38 pm

DIRECTORY

BcdDefs: TYPE USING [treetype],

Literals: TYPE USING [LitIndex],

Symbols: TYPE USING [HTIndex, htNull, STIndex],

Table: TYPE USING [Base, Finger, Limit, Selector];

Tree: DEFINITIONS={

treeType: Table.Selector~BcdDefs.treetype;

Base: TYPE~Table.Base;

Finger: TYPE~Table.Finger;

Limit: CARDINAL~Table.Limit;

data structures

Link: TYPE~RECORD [

SELECT tag: * FROM

subtree => [index: Tree.Index],

hash => [index: Symbols.HTIndex],

symbol => [index: Symbols.STIndex],

literal => [index: Literals.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 BOOL ← ALL[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];

}.