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

        }.