[ivy]<Satterthwaite>Mimosa>Tree.mesa!4

Tree.mesa

Satterthwaite, June 18, 1986 12:17:23 pm PDT

Russ Atkinson (RRA) January 31, 1985 1:03:04 pm PST

DIRECTORY

Table: TYPE USING [Base, Finger, IndexRep, Selector, Tag, chunkType],

Literals: TYPE USING [LTIndex, STIndex, ltTag, stTag],

Symbols: TYPE USING [ISEIndex, Name, htTag, seTag, nullName];

Tree: DEFINITIONS = {

treeType: Table.Selector = Table.chunkType;

treeTag: Table.Tag = 0;

Base: TYPE = Table.Base;

Finger: TYPE = Table.Finger;

data structures

LinkTag: TYPE = MACHINE DEPENDENT {

subtree (treeTag),

hash (Symbols.htTag),

symbol (Symbols.seTag),

literal (Literals.ltTag),

string (Literals.stTag)};

Link: TYPE = RECORD [

SELECT COMPUTED LinkTag FROM

subtree => [index: Tree.Index],

hash => [index: Symbols.Name],

symbol => [index: Symbols.ISEIndex],

literal => [index: Literals.LTIndex],

string => [index: Literals.STIndex],

ENDCASE];

LinkRep: TYPE = Table.IndexRep;

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..15): BOOL,

nSons (1): NAT,

info (2): Tree.Info,

son (4): SEQUENCE COMPUTED [1..NAT.LAST] OF Tree.Link];

SonId: TYPE = [1..NAT.LAST);

Info: TYPE [SIZE[CARD]]; -- no exporter, conversions by LOOPHOLEs

AttrId: TYPE = [1..3];

Index: TYPE = Base RELATIVE LONG POINTER TO Tree.Node;

firstIndex: Tree.Index = LOOPHOLE[Table.IndexRep[tag: treeTag, highBits: 0, lowBits: 0]];

nullIndex: Tree.Index = firstIndex;

Null: Tree.Link = [subtree[index: Tree.nullIndex]];

nullId: Tree.Link = [hash[index: Symbols.nullName]];

nullInfo: Info = LOOPHOLE[CARD[0]];

NodeName: TYPE = {

general tree constructors

list, item,

declarations

decl, typedecl,

basicTC, enumeratedTC, recordTC, monitoredTC, variantTC,

refTC, pointerTC, listTC, arrayTC, arraydescTC, sequenceTC,

procTC, processTC, portTC, signalTC, errorTC, programTC,

anyTC, definitionTC, unionTC, relativeTC,

subrangeTC, longTC, opaqueTC, zoneTC, linkTC, varTC,

implicitTC, frameTC, discrimTC,

paintTC, spareTC,

unit, diritem, module, body, inline, lambda, block,

statements

assign, extract,

if,

case, casetest, caseswitch,

bind,

do, forseq, upthru, downthru,

return, result,

goto, exit, loop,

free,

resume, reject, continue, retry, catchmark,

restart, stop,

lock, wait, notify, broadcast, unlock,

null,

label,

open,

enable, catch,

dst, lste, lstf,

syscall, checked, lst, spareS3,

subst, call, portcall, signal, error, syserror, xerror,

start, join,

expressions

apply,

callx, portcallx, signalx, errorx, syserrorx, startx, fork, joinx,

index, dindex, seqindex, reloc,

construct, union, rowcons, sequence, listcons,

substx,

ifx, casex, bindx,

assignx, extractx,

or, and,

relE, relN, relL, relGE, relG, relLE, in, notin,

plus, minus, times, div, mod,

dot, cdot, dollar,

create,

not,

uminus,

addr,

uparrow,

min, max, lengthen, abs, all,

size, first, last, pred, succ,

arraydesc, length, base,

loophole,

nil,

new,

void,

clit, llit,

cast, check, float, pad, chop, safen,

syscallx, narrow, istype,

openx,

mwconst, cons,

atom, typecode,

stringinit, textlit, signalinit, procinit,

intOO, intOC, intCO, intCC,

thread,

none,

exlist,

initlist,

ditem,

shorten,

self,

gcrt, proccheck,

ord, val,

entry, internal,

mergecons};

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

}.