DIRECTORY TiogaNode USING [OfNode, Ref, RefBasicNode, RefBoxNode, RefBranchNode, RefItemNode, RefListNode, RefTextNode], TiogaNodeOps, TreeCheck, CheckNode USING [CheckTextNode]; TreeCheckImpl: CEDAR PROGRAM IMPORTS CheckNode, TiogaNodeOps EXPORTS TreeCheck SHARES TiogaNode = BEGIN OPEN TreeCheck; maxDepth: CARDINAL = 2000; Depth: TYPE = [0..maxDepth); Verify: PUBLIC PROC [node:Node] ={ VerifyNode[node, NIL, 0] }; VerifyNode: PROC [me, parent:Node, depth:Depth] = { IF depth >= maxDepth THEN ERROR; -- too many kids to believe WITH me SELECT FROM branch:TiogaNode.RefBranchNode => VerifyBranchNode[branch, parent, depth]; item:TiogaNode.RefItemNode => VerifyItemNode[item, parent, depth]; basic:TiogaNode.RefBasicNode => VerifyBasicNode[basic, parent, depth]; ENDCASE => ERROR; -- must be one of above! }; VerifyBasicNode: PROCEDURE [me:TiogaNode.RefBasicNode, parent:Node, depth:Depth] = { IF depth >= maxDepth THEN ERROR; IF me.last AND me.next # parent THEN { IF me.next # NIL THEN FindSmashedLink[parent, me.next]; ERROR }}; VerifyBranchNode: PROCEDURE [me:TiogaNode.RefBranchNode, parent:Node, depth:Depth] = { sibN:Depth _ 0; IF depth >= maxDepth THEN ERROR; IF me.last AND me.next # parent THEN { IF me.next # NIL THEN FindSmashedLink[parent, me.next]; ERROR }; IF ~me.internalRepCreated THEN RETURN; IF me.contents # NIL THEN -- contents FOR this: TiogaNode.RefItemNode _ me.contents, NARROW[this.next] DO IF this = NIL THEN ERROR; VerifyItemNode[this, me, depth+1]; IF this.last THEN { IF this.next = me THEN EXIT; IF this.next # NIL THEN FindSmashedLink[parent, this.next]; ERROR }; IF (sibN _ sibN + 1) >= maxDepth THEN ERROR; -- too many children to believe ENDLOOP; IF me.child # NIL THEN -- children FOR this:TiogaNode.RefBranchNode _ me.child, NARROW[this.next] DO IF this = NIL THEN ERROR; VerifyBranchNode[this, me, depth+1]; IF this.last THEN { IF this.next = me THEN EXIT; IF this.next # NIL THEN FindSmashedLink[parent, this.next]; ERROR }; IF (sibN _ sibN + 1) >= maxDepth THEN ERROR; -- too many children to believe ENDLOOP }; VerifyItemNode: PROCEDURE [me:TiogaNode.RefItemNode, parent:Node, depth:Depth] = { sibN:Depth _ 0; contents: TiogaNode.Ref; branches: BOOL; IF depth >= maxDepth THEN ERROR; IF me.last AND me.next # parent THEN { IF me.next # NIL THEN FindSmashedLink[parent, me.next]; ERROR }; WITH me SELECT FROM tx: TiogaNode.RefTextNode => CheckNode.CheckTextNode[tx]; bx: TiogaNode.RefBoxNode => contents _ bx.contents; ls: TiogaNode.RefListNode => contents _ ls.contents; ENDCASE => ERROR; IF contents=NIL THEN RETURN; branches _ TiogaNodeOps.IsBranch[contents]; FOR this: TiogaNode.Ref _ contents, this.next DO IF this = NIL THEN ERROR; IF TiogaNodeOps.IsBranch[this] # branches THEN ERROR; VerifyNode[this, me, depth+1]; IF this.last THEN { IF this.next = me THEN EXIT; IF this.next # NIL THEN FindSmashedLink[parent, this.next]; ERROR }; IF (sibN _ sibN + 1) >= maxDepth THEN ERROR; -- too many children to believe ENDLOOP }; FindSmashedLink: PROC[startparent: Node, endparent: Node] = { badguy: Node _ startparent; -- this will finally be the node with a smashed pointer FOR tnode: Node _ startparent, tnode.next UNTIL tnode.last DO FOR bnode: Node _ endparent, 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; ERROR; -- this can't happen! }; --FindSmashedLink END. --TreeCheckImpl Log Created February 19, 1981, by Pier. Modified 20-May-81, by Paxton Modified February 24, 1983 by Lamming to handle Tioga2 structures ¾TreeCheckImpl.Mesa; written by Pier. February, 1981 edited by Paxton, August 16, 1983 1:59 pm edited by McGregor, May 9, 1983 2:20 pm 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 Check a branch - note that the sibling chain is checked by iteration to avoid stack overflow Check a branch - note that the sibling chain is checked by iteration to avoid stack overflow 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. ÊݘJšÏc3™3Jš)™)Jš'™'J˜JšÉ™ÉJ™šÏk ˜ Jšœ žœ_˜nJ˜ Jšœ ˜ Jšœ žœ˜ —J˜šœž ˜Jšžœ˜Jšžœ ˜Jšžœ ˜—J˜Jšžœžœ ˜J˜Jš™J˜Jšœ žœ˜Jšœžœ˜J˜Jš ™ J˜JšÏnœžœžœ žœ˜>J˜šŸ œžœ#˜3Jšžœžžœ˜<šžœžœž˜JšœJ˜JJšœB˜BJšœF˜FJšžœžœ˜+—˜J˜——šŸœž œ:˜TJ™\Jšžœž œ˜ šžœ žœžœ˜&Jšžœ žœžœ"˜7Jšžœ˜ —J˜—šŸœž œ;˜VJ™\Jšœ˜Jšžœž œ˜ šžœ žœžœ˜&Jšžœ žœžœ"˜7Jšžœ˜—Jšžœžœžœ˜&šžœžœžœ ˜&šžœ,žœ ž˜CJšžœžœž ˜Jšœ$˜$šžœ žœ˜Jšžœž œ˜Jšžœ žœžœ$˜;Jšžœ˜—Jšžœž œ!˜NJšžœ˜——šžœ žœžœ ˜"šžœ*žœ ž˜AJšžœžœž ˜Jšœ&˜&šžœ žœ˜Jšžœž œ˜Jšžœ žœžœ$˜;Jšžœ˜—Jšžœž œ!˜NJšžœ˜ ——J˜—šŸœž œ9˜RJšœ˜Jšœ˜Jšœ žœ˜Jšžœž œ˜ šžœ žœžœ˜&Jšžœ žœžœ"˜7Jšžœ˜—šžœžœž˜Jšœ9˜9J˜3J˜4Jšžœžœ˜—Jšžœ žœžœžœ˜Jšœ+˜+šžœ+ž˜0Jšžœžœž ˜Jšžœ(žœžœ˜5Jšœ ˜ šžœ žœ˜Jšžœž œ˜Jšžœ žœžœ$˜;Jšžœ˜—Jšžœž œ!˜NJšžœ˜ ——J˜JšŸœžœ(˜=J˜Jš™™™J˜Jšœ7˜Sšžœ'žœ ž˜=šžœ%žœ ž˜;šžœžœžœ ˜=Jš6˜6Jš4˜4——J˜Jšžœ˜—Jšžœ˜Jšžœ˜Jšœ˜J˜Jšžœ˜J˜J˜J˜J˜#J˜J˜A—…—bý