DIRECTORY TreeCheck, TextNode, CheckNode; TreeCheckImpl: CEDAR PROGRAM IMPORTS CheckNode EXPORTS TreeCheck = BEGIN OPEN TreeCheck; maxDepth: CARDINAL = 2000; Depth: TYPE = [0..maxDepth); 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: 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 badguy _ tnode; ENDLOOP; ENDLOOP; }; --FindSmashedLink END. --TreeCheckImpl Log Created February 19, 1981, by Pier. Modified 20-May-81, by Paxton h-- 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. --limits --globals --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. -- but is pointed to by badguy, a child of startparent -- or tnode=startparent.child and startparent=badguy Êd˜JšÏc™Jš"™"Jš-™-J˜Jš<™