[Pixel]<Imaging>7.0>Tioga>TreeCheckImpl.mesa!4

TreeCheckImpl.mesa

written by Pier. February, 1981

last written by Paxton. 20-May-81 13:47:47

Doug Wyatt, September 17, 1986 10:53:01 am PDT

-- TreeCheck: a procedure called to verify that a Tioga tree

-- structure is valid. If a problem is discovered, an exit

-- to the debugger with an error message and locale is taken.

-- If no problem, returns TRUE.

DIRECTORY

Tioga USING [Node],

TiogaPrivate USING [Check];

TreeCheckImpl: CEDAR PROGRAM

IMPORTS TiogaPrivate

EXPORTS TiogaPrivate =

BEGIN

Node: TYPE ~ Tioga.Node;

--limits

maxDepth: CARDINAL = 2000;

Depth: TYPE = [0..maxDepth);

--globals

Verify: PUBLIC PROC [node: Node] = { VerifyNode[node,0] };

VerifyNode: PROC [parent: Node, vdepth: Depth] = {

hDepth: Depth ← 0;

TiogaPrivate.Check[parent]; -- checks rope & runs for text node

IF vdepth >= maxDepth THEN ERROR; -- tree is too deep to believe

IF parent.child = NIL THEN RETURN;

FOR tn: Node ← parent.child, tn.next DO

IF tn = NIL THEN ERROR;

VerifyNode[tn, vdepth+1];

IF tn.last THEN {

IF tn.next = parent THEN RETURN;

IF tn.next # NIL THEN FindSmashedLink[parent, tn.next];

ERROR };

IF (hDepth ← hDepth + 1) >= maxDepth THEN ERROR; -- too many siblings to believe

ENDLOOP;

}; --VerifyNode

--FindSmashedLink is called when the node pointed to at the end of

--a sibling chain is not the parent who started the chain. We assume

--some pointer in that chain is smashed and is pointing to some

--other random but wellformed section of the tree. We then traverse

--the startparent sibling chain, looking for the first node whose immediate

--sibling is a son of the endparent. That is the smashed node, called badguy.

FindSmashedLink: PROC[startparent: Node, endparent: Node] = {

badguy: Node ← startparent; -- this will finally be the node with a smashed pointer

FOR tnode: Node ← startparent.child, tnode.next UNTIL tnode.last DO

FOR bnode: Node ← endparent.child, bnode.next UNTIL bnode.last DO

IF tnode = bnode THEN ERROR; -- tnode is a child of endparent

-- but is pointed to by badguy, a child of startparent

-- or tnode=startparent.child and startparent=badguy

badguy ← tnode;

ENDLOOP;

}; --FindSmashedLink

END.