<> <> <> <> <> <<-- 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 CheckNode USING [Check], TreeCheck USING [Node]; 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; ENDLOOP; }; --FindSmashedLink END.