TreeCheckImpl.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
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;
ENDLOOP;
}; --FindSmashedLink
END.