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

  }.