DIRECTORY TiogaNode USING [OfNode, RefBasicNode, RefBoxNode, RefBranchNode, RefItemNode, RefListNode, RefTextNode], TreeCheck, CheckNode USING [CheckTextNode]; TreeCheckImpl: CEDAR PROGRAM IMPORTS CheckNode EXPORTS TreeCheck = BEGIN OPEN TreeCheck; maxDepth: CARDINAL = 2000; Depth: TYPE = [0..maxDepth); Verify: PUBLIC PROC [node:Node] ={ VerifyNode[node, NIL, 0] }; VerifyNode: PROC [me,parent:Node, childN:Depth] = { IF childN >= maxDepth THEN ERROR; -- too many kids to believe WITH me SELECT FROM branch:TiogaNode.RefBranchNode => VerifyBranchNode[branch, parent, childN]; item:TiogaNode.RefItemNode => VerifyItemNode[item, parent, childN]; basic:TiogaNode.RefBasicNode => VerifyBasicNode[basic, parent, childN]; ENDCASE => ERROR; -- must be one of above! }; VerifyNodeOfType: PROCEDURE [kind:TiogaNode.OfNode, me,parent:Node, childN:Depth] = { IF me.kind#kind THEN ERROR -- not of expected type ELSE VerifyNode[me, parent, childN]; }; VerifyBasicNode: PROCEDURE [me:TiogaNode.RefBasicNode, parent:Node, childN:Depth] = { ERROR; -- dont know how to verify a basic node yet }; VerifyBranchNode: PROCEDURE [me:TiogaNode.RefBranchNode, parent:Node, childN:Depth] = { sibN:Depth _ 0; IF me.internalRepCreated THEN { IF me.contents # NIL THEN VerifyNodeOfType[item, me.contents, me, childN]; -- contents IF me.child # NIL THEN -- children FOR this:TiogaNode.RefBranchNode _ me.child, NARROW[this.next] DO IF this = NIL THEN ERROR ELSE VerifyBranchNode[this, me, childN+1]; IF this.last THEN { IF this.next = me THEN RETURN; IF this.next # NIL THEN FindSmashedLink[parent, this.next]; ERROR; -- next link NIL! }; IF (sibN _ sibN + 1) >= maxDepth THEN ERROR; -- too many children to believe ENDLOOP; IF me.last THEN { IF me.next = parent THEN RETURN; IF me.next # NIL THEN FindSmashedLink[parent, me.next]; ERROR; -- next link NIL! } } ELSE { -- verify what you can then ERROR; }; }; VerifyItemNode: PROCEDURE [me:TiogaNode.RefItemNode, parent:Node, childN:Depth] = { sibN:Depth _ 0; VerifyItemConts: PROCEDURE [me:TiogaNode.RefItemNode, parent:Node, childN:Depth] = { WITH me SELECT FROM t:TiogaNode.RefTextNode => { CheckNode.CheckTextNode[t]; }; l:TiogaNode.RefListNode => ERROR; b:TiogaNode.RefBoxNode => ERROR; ENDCASE => ERROR; IF me.last THEN { IF me.next = parent THEN RETURN; IF me.next # NIL THEN FindSmashedLink[parent, me.next]; ERROR; -- next link NIL! }; }; FOR this: Node _ me, this.next DO IF this = NIL THEN ERROR; -- should point to next sib or parent IF this.kind = item THEN VerifyItemConts[NARROW[this], parent, childN] ELSE ERROR; IF this.last THEN { IF this.next = parent THEN RETURN; IF this.next # NIL THEN FindSmashedLink[parent, this.next]; ERROR; -- next link NIL! }; IF (sibN _ sibN + 1) >= maxDepth THEN ERROR; -- too many siblings 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, 20-May-81 13:47:47 edited by McGregor, May 9, 1983 2:20 pm Last Edited by: Lamming, April 13, 1983 12:04 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 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š0™0J˜JšÉ™ÉJ™šÏk ˜ Jšœ žœZ˜iJšœ ˜ Jšœ žœ˜ —J˜šœž ˜Jšžœ ˜Jšžœ ˜—J˜Jšžœžœ ˜J˜Jš™J˜Jšœ žœ˜Jšœžœ˜J˜Jš ™ J˜JšÏnœžœžœ žœ˜>J˜šŸ œžœ#˜3šžœž˜Jšžœ˜"—šžœžœž˜šœ!˜!Jšœ)˜)—šœ˜Jšœ%˜%—šœ˜Jšœ'˜'—Jšžœžœ˜+—˜J˜——šŸœž œ:˜Ušžœž˜Jšžœ˜—šžœ˜Jšœ˜—J˜J˜J˜—šŸœž œ;˜UJšžœ+˜2J˜J˜—šŸœž œ<˜WJ™\Jšœ˜šžœžœ˜ šžœžœž˜Jšœ3 ˜>—šžœ žœžœ ˜,šžœ*žœ ž˜AJšžœžœž ˜Jšžœ(˜,šžœ žœ˜Jšžœž œ˜Jšžœ žœžœ$˜;Jšžœ˜Jšœ˜—Jšžœž œ!˜NJšžœ˜J˜——šžœžœ˜šžœž˜Jšž˜—Jšžœ žœžœ"˜7Jšžœ˜J˜—J˜—šžœ˜"Jšžœ˜Jšœ˜J˜—J˜J˜—šŸœž œ:˜SJšœ˜šŸœž œ:˜Tšžœžœž˜šœ˜Jšœž˜J˜—Jšœžœ˜!Jšœžœ˜ Jšžœžœ˜—J˜šžœžœ˜šžœž˜Jšž˜—Jšžœ žœžœ"˜7Jšžœ˜J˜—J˜—J˜šžœž˜!Jšžœžœž œ%˜@Jšžœžœžœ˜FJšžœžœ˜ šžœ žœ˜šžœž˜Jšžœ˜—Jšžœ žœžœ$˜;Jšžœ˜Jšœ˜—šžœž˜%Jšžœ˜&—Jšžœ˜—J˜J˜—J˜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—…— ¶K