[_CDCSL_93-16_]<1>Cedar>release>MimosaOnly>Tree.mesa

Tree.mesa

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

Russ Atkinson (RRA) August 30, 1988 4:22:25 am PDT

DIRECTORY

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

Symbols USING [htTag, ISEIndex, Name, nullName, seTag],

Table USING [Base, chunkType, Finger, HighBits, lowBitHi, lowBitLo, LowBits, restBitHi, restBitLo, Selector, Tag, tagBitHi, tagBitLo];

Tree: DEFINITIONS = {

OPEN Table;

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 = MACHINE DEPENDENT RECORD [

(must be compatible with Table.IndexRep)

tag (0: tagBitLo..tagBitHi): LinkTag ¬ subtree,

highBits (0: restBitLo..restBitHi): HighBits ¬ HighBits.LAST,

lowBits (0: lowBitLo..lowBitHi): LowBits ¬ LowBits.LAST];

NodePtr: TYPE = LONG POINTER TO Node;

Node: TYPE = MACHINE DEPENDENT RECORD [

free (0: 0..0): BOOL, -- reserved for allocator

name (0: 1..8): NodeName,

attr1 (0: 9..9), attr2 (0: 10..10), attr3 (0: 11..11): BOOL,

subInfo (0: 12..15): SubInfo,

shared (0: 16..16): BOOL,

nSons (0: 17..31): NAT15,

info (0: 32..63): Info,

son (64/BITS[WORD]): SEQUENCE COMPUTED SonId OF Tree.Link];

SubInfo: TYPE = [0..15];

The following values for SubInfo are used in the optionTC case

packedOption: SubInfo = 1;

msbitOption: SubInfo = 2;

lsbitOption: SubInfo = 3;

nativeOption: SubInfo = 4;

word8Option: SubInfo = 5;

word16Option: SubInfo = 6;

word32Option: SubInfo = 7;

word64Option: SubInfo = 8;

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[Tree.LinkRep[tag: subtree, 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 = MACHINE DEPENDENT {

general tree constructors

list (0), item (1),

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, optionTC, 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, power,

dot, cdot, dollar,

create,

not,

uminus,

addr,

uparrow,

min, max, ord, val, 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,

lengthen, shorten,

self,

gcrt, proccheck,

entry, internal,

invalid};

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