[Cyan]<Cedar6.0>Tioga>TreeCheckImpl.mesa!1

-- TreeCheckImpl.Mesa

-- written by Pier. February, 1981

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

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

TreeCheck,

TextNode,

CheckNode;

TreeCheckImpl: CEDAR PROGRAM

IMPORTS CheckNode

EXPORTS TreeCheck =

BEGIN OPEN TreeCheck;

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

CheckNode.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. --TreeCheckImpl

Log

Created February 19, 1981, by Pier.

Modified 20-May-81, by Paxton