Method and system for selecting instrumentation points in a computer program5790858Abstract The present invention provides a method in a computer system for selecting instrumentation points in a computer program. Instrumentation points are locations within the computer program at which instrumentation code is inserted. The method includes identifying code portions such as basic blocks in the computer program code, creating a control flow graph out of the code portions, generating a spanning tree for the control flow graph, and then selecting those edges of the control flow graph which are not a part of the spanning tree as instrumentation points. After instrumentation points are selected, instrumentation code may be added at those locations. When the computer program is executed, the added instrumentation code records execution information such as how many times an instrumentation point is accessed during execution of the computer program. Using the recorded execution information and direction specified in the control flow graph, execution information for the non-instrumented blocks may then be calculated. Claims I claim: Description TECHNICAL FIELD
TABLE A
______________________________________
A (1) i:=m-1
(2) j:=n
(3) t.sub.1 :=4*n
(4) v:=a›t.sub.1 !
B (5) i:=i+1
(6) t.sub.2 :=4*i
(7) t.sub.3:=a›t.sub.2 !
(8) if t.sub.3 <v goto B
C (9) j:=j-1
(10) t.sub.4 :=4*j
(11) t.sub.5 :=a›t.sub.4 !
(12) ift.sub.5 >v goto C
D (13) ifi>=j goto F
E (14) t.sub.6 :=4*i
(15) x:=a›t.sub.6 !
(16) t.sub.7 :=4*i
(17) t.sub.8 :=4*j
(18) t.sub.9 :=a›t.sub.8 !
(19) a›t.sub.7 !:=t.sub.9
(20) t.sub.10 :=4*j
(21) a›t.sub.10 !:=x
(22) goto B
F (23) t.sub.11 :=4*i
(24) x:=a›t.sub.11 !
(25) t.sub.12 :=4*i
(26) t.sub.13 :=4*n
(27) t.sub.14 :=a›t.sub.13 !
(28) a›t.sub.12 !:=t.sub.14
(29) t.sub.15 :=4*n
(30) a›t.sub.15 !:=x
______________________________________
The instructions shown above in Table A have been divided into six blocks: block A contains instructions (1)-(4); block B contains instructions (5)-(8); block C contains instructions (9)-(12); block D contains instruction (13); block E contains instructions (14)-(22); and block F contains instructions (23)-(30). Referring to FIG. 1, the control flow graph 100 includes six nodes 102, 104, 106, 108, 110, and 112, one node for each basic block identified above in Table A. The exit instruction for each block determines which block will be next in the flow of execution. For example, block A in Table A includes the exit instruction "v:=a›t.sub.1 !." This instruction indicates a fall through to the entrance instruction of block B. This flow of execution is represented by edge 114 from node 102 to node 104 in the control flow graph 100. Block B is said to be the "follower" of block A. As a further example, code block C includes the exit instruction "if t.sub.5 >v goto C." If the condition is true, then the flow of execution jumps to the entrance instruction of block C; if the condition is false, then the instruction within block D is executed. The flow of execution from the exit instruction of block C to the entrance instruction of block C is represented by edge 116 from node 106 back to node 106 in the control flow graph 100. The flow of execution from the exit instruction of block C to the entrance instruction of block D is represented by edge 118 between node 106 and node 108 in the control flow graph 100. Block C is said to be the "target" of block C, while block D is said to be the "follower" of block C. The generation of a control flow graph is described in more detail in A. AHO, R. SETHI, J. ULLMAN, COMPILERS, PRINCIPLES, TECHNIQUES, AND TOOLS (1986), which is hereby incorporated by reference. FIG. 2 is an overview flow diagram of a method for recording execution information for selected instrumentation points in a computer program and then using the recorded execution information to calculate execution information for every basic block in the computer program in accordance with a preferred embodiment of the present invention. The method includes identifying the basic blocks that make up the computer program (step 120), creating a control flow graph for the basic blocks (step 121), generating a spanning tree for the control flow graph (step 122), selecting as instrumentation points edges from the control flow graph which are not a part of the spanning tree (step 123), inserting instrumentation code at the selected instrumentation points (step 124), executing the computer program so that the inserted instrumentation code records how many times each instrumentation point is accessed (step 125), and then using the recorded execution information and the direction specified in the control flow graph to calculate execution information for the basic blocks which were not selected as instrumentation points (step 126). This method is explained in more detail with reference to FIGS. 3-9B. FIG. 3 is a block diagram of a computer system 130 configured to implement a preferred embodiment of the present invention. The computer system 130 includes a main memory 132, a central processing unit 134, and a secondary memory 136. A computer program 139 and a corresponding control flow graph 140 for the computer program 139 are stored in the secondary memory 136. The control flow graph 140 is created using a conventional control flow graph routine (not shown). A Span.sub.-- Tree routine 138 provided by the present invention is loaded into to the main memory 132 to be executed. The Span.sub.-- Tree routine 138 receives as input the control flow graph 140, traverses the nodes and edges in the control flow graph 140 to determine paths, and then outputs a spanning tree for the control flow graph 140. A spanning tree is an acyclic tree formed from all of the nodes and selected edges of the control flow graph 140. FIG. 4 is a flow diagram of the Span.sub.-- Tree routine 138 in accordance with a preferred embodiment of the present invention. The Span.sub.-- Tree routine traverses every node in the control flow graph 140, and then labels every node and selected edges in the control flow graph 140 with a path identifier. A path identifier is a value associated with nodes and edges that indicates to which path the node or edge is connected. In step 141 of FIG. 4, the Span.sub.-- Tree routine initializes a node list by pushing a pointer to the root node of the control flow graph 140 onto the node list. The node list is used to defer processing of nodes which may be the starting node of a path. Preferably, the node list is a data structure in which pointers to nodes are "pushed" onto the top of the node list and "popped" from the bottom of the node list. In step 142, the Span.sub.-- Tree routine determines whether the node list is empty. If the node list is empty, then the Span.sub.-- Tree routine terminates. If the node list is not empty, then in step 144 the Span.sub.-- Tree routine pops a node off of the node list and sets a pointer CurNode to point to the popped node. The pointer CurNode is used to keep track of the current node that is being processed. In step 146, the Span.sub.-- Tree routine determines whether CurNode is labeled with a path identifier. If CurNode is labeled with a path identifier, then the Span.sub.-- Tree routine loops back to step 142. Step 146 prevents a node that has already been labeled with a path identifier from being re-labeled. If CurNode is not labeled with a path identifier, then in step 148 the Span.sub.-- Tree routine increments a variable Path.sub.-- ID. The variable Path.sub.-- ID is used to keep track of a current path identifier. Path.sub.-- ID is initially set to zero. In step 150, the Span.sub.-- Tree routine determines whether CurNode contains a nil value. A nil value stored in CurNode will cause the Span.sub.-- Tree routine to loop back to step 142. A nil value is stored in CurNode by the Span.sub.-- Tree routine when the end of a path is encountered. If the Span.sub.-- Tree routine determines that CurNode does not contain a nil value, then in step 152 the Span.sub.-- Tree routine determines whether CurNode is labeled with a path identifier. This check for a path identifier in step 152 will identify when a different, already-labeled path is encountered, thereby identifying the end of the current path. If CurNode is labeled with a path identifier, then in step 154 the Span.sub.-- Tree routine sets CurNode equal to nil and loops to step 150. After step 150 is executed, another node will be popped off of the node list in step 142, if any more nodes are stored in the node list. If CurNode is not labeled with a path identifier (step 152), then in step 156 the Span.sub.-- Tree routine labels CurNode with the value stored in Path.sub.-- ID. In step 158, if the Span.sub.-- Tree routine determines that CurNode has two output edges, then in step 160 the Span.sub.-- Tree routine calls a routine ProcessTwo. The routine ProcessTwo is described below in more detail with reference to FIG. 5. Generally, the ProcessTwo routine determines which one of the two output edges, if any, should be labeled with the value stored in Path.sub.-- ID. That is, the ProcessTwo routine determines with which output edge of CurNode to continue the current path. The destination node of the output edge will be labeled with the value stored in Path.sub.-- ID and a pointer to the destination node of the other output edge will be pushed onto the node list for later processing. Any node on the node list is potentially a starting node for a new path. After the ProcessTwo routine executes, the Span.sub.-- Tree routine loops back to step 150. If the Span.sub.-- Tree routine determines in step 158 that CurNode does not have two output edges, then in step 162 the Span.sub.-- Tree routine determines whether CurNode has one output edge. If CurNode has one output edge, then in step 164 the Span.sub.-- Tree routine calls a routine ProcessOne. The ProcessOne routine is described in more detail below with reference to FIG. 6. Generally, the ProcessOne routine determines whether the destination node of the output edge should be labeled with the same path identifier as CurNode, that is, is it on the same path as CurNode. After the ProcessOne routine executes, the Span.sub.-- Tree routine loops back to step 150. If the Span.sub.-- Tree routine determines in step 162 that CurNode has zero output edges or more than two output edges, then the Span.sub.-- Tree routine loops back to step 150 to terminate the current path. More than two output edges indicates the presence of a statement with multiple targets, such as a case statement. The current path is terminated by storing a nil value in CurNode in step 154, after determining in step 152 that CurNode was already labeled with a path identifier. Storing a nil value in CurNode will cause the Span.sub.-- Tree routine to loop back to step 142. The Span.sub.-- Tree routine repeats steps 142-164 until every node in the control flow graph is labeled with a path identifier. FIG. 5 is a flow diagram of the ProcessTwo routine. The ProcessTwo routine analyzes the destination nodes of the two output edges of CurNode to determine which node, if any, should be labeled with the current path identifier. For purposes of this detailed description, these nodes are known as target or follower nodes. The target node represents the block of code that is the destination of a branch or jump instruction of the exit instruction of the current node. The follower node represents the block of code that is the "fall through" block; that is, no branch or jump instruction is needed to access the block. In step 180 of FIG. 5, the ProcessTwo routine determines whether the target node and the follower node are already labeled with the same path identifier as CurNode, that is, whether both output edges of CurNode loop back to the current path. If both output edges of CurNode loop back to the current path, then control returns to the Span.sub.-- Tree routine at step 150 in FIG. 4. Because neither output edge is labeled, both edges will be selected as instrumentation points. If it is determined that both output edges of CurNode do not loop back to the current path (step 180), then in step 186 the ProcessTwo routine determines whether the target node or the follower node of CurNode loop back to the current path. For purposes of this discussion, a node that loops back to the current path is referred to as a looping node. If either the target node or the follower node is a looping node, then in step 188 the output edge from CurNode to the non-looping node of CurNode is labeled with the value stored in Path.sub.-- ID. Additionally, in step 188 CurNode is set to point to the non-looping node. After step 188, control is returned to the Span.sub.-- Tree routine at step 150 in FIG. 4. If it is determined that neither the target node nor the follower node of CurNode loops back to the current path, then in step 190 the ProcessTwo routine determines whether the target node was already labeled with a path identifier. If it is determined that the target node is labeled with a path identifier, then in step 192 a pointer to the follower node of CurNode is pushed onto the node list and the edge between CurNode and the target node is labeled with the value stored in Path.sub.-- ID. In step 194, a pointer to the target node is stored in CurNode. After step 194, control is returned to the Span.sub.-- Tree routine at step 150 in FIG. 4. ›Note: In step 152, the Span.sub.-- Tree routine will determine that CurNode was already labeled with a path identifier so the Span.sub.-- Tree routine will terminate the current path.! If it is determined in step 190 that the target node of CurNode is not labeled with a path identifier, then in step 196 a pointer to the target node of CurNode is pushed onto the node list and the edge from CurNode to the follower node of CurNode is labeled with the value stored in Path.sub.-- ID. Step 190 occurs because in a preferred embodiment of the present invention, a path follows the follower nodes, if possible. Of course, maintaining a path using the target nodes is acceptable in an alternate embodiment of the present invention. In step 198, CurNode is set to point to the follower node of CurNode. After step 198, control is returned to the Span.sub.-- Tree routine at step 150 in FIG. 4. FIG. 6 is a flow diagram of the ProcessOne routine. The ProcessOne routine determines whether the current path should include the next node after CurNode. In step 170, the ProcessOne routine determines whether the next node after CurNode was already labeled with the current path identifier. If the next node was already labeled with the current path identifier, then, in step 172, the ProcessOne routine determines whether a previous node having two output edges exists on the current path. This node is referred to as the last branching node. The last branching node is located so that the path can be redirected at that point to avoid the loop detected in step 170. A loop is avoided because it makes an imperfect spanning tree. Recall that in a spanning tree, there should be only one path to every node. The current path is redirected by clearing the path identifiers from the nodes and edges in between the last branching node and CurNode, including CurNode. If no last branching node exists, then, in step 178, the ProcessOne routine stores a nil value in CurNode. Storing a nil value in CurNode will cause the current path to be terminated when control is returned to the Span.sub.-- Tree routine. If a last branching node does exist, then, in step 174, the ProcessOne routine calls a BackTrace routine, which causes the redirection of the current path from the last branching node. The BackTrace routine is described in more detail below with reference to FIG. 7. If the next node is not already labeled with the same path identifier as CurNode (step 170), then, in step 176, the edge from CurNode to the next node is labeled with the value stored in Path.sub.-- ID, and a pointer to the next node is stored in CurNode. After steps 176 and 178, control is returned to the Span.sub.-- Tree routine at step 150 in FIG. 4. FIG. 7 is a block diagram of the BackTrace routine. The BackTrace routine is called by the ProcessOne routine when the next node loops back to the current path. As described briefly above, when the next node loops back to the current path, the current path is redirected from the last branching node to avoid the loop. The input to the BackTrace routine is a pointer to the last branching node before CurNode. In step 200, the BackTrace routine stores a pointer to a node immediately following the last branching node and having the same path identifier as the last branching node in a variable NextNode. In step 202, NextNode is pushed onto the node list. In step 204, it is determined whether NextNode is the follower node or the target node of the last branching node. If NextNode is the target node, then in step 206 a pointer to the follower node is stored in CurNode. If it is determined that NextNode is the follower node of the last branching node, then in step 208 a pointer to the target node is stored in CurNode. After steps 206 and 208, in step 210 the path identifiers of NextNode and the nodes and edges after NextNode that have the same path identifier as NextNode are cleared. After step 210, control is returned to the Span.sub.-- Tree routine at step 150 in FIG. 4. After describing the Span.sub.-- Tree routine in detail, it is helpful to trace through the steps of the routine using an illustrative control flow graph as input. FIG. 8A is a block diagram of an illustrative control flow graph 230. The control flow graph 230 is designed to represent a portion of a computer program. Those skilled in the art will appreciate that a computer program may contain multiple control flow graphs. For purposes of this example, every node in the control flow graph 230 has at most two output edges. However, those skilled in the art will appreciate that a basic block in a computer program may branch to more than two different basic blocks. A switch statement in the C programming language that contains multiple case statements is an example of when an instruction branches to more than two basic blocks. Referring again to FIG. 8A, the control flow graph 230 has a root node 232. The Span.sub.-- Tree routine initializes a node list by pushing a pointer to the root node 232 and any other root nodes of other control flow graphs onto the node list (step 140, FIG. 4). The Span.sub.-- Tree routine then determines whether the node list is empty (step 142). The node list is not empty, therefore the Span.sub.-- Tree routine pops node 232 off of the node list and stores a pointer to node 232 in CurNode (step 144). The Span.sub.-- Tree routine then determines whether CurNode is labeled with a path identifier (step 146). Node 232 is not labeled with a path identifier, therefore the Span.sub.-- Tree routine increments a variable Path.sub.-- ID (step 148). Because the variable Path.sub.-- ID is initially set to zero, Path.sub.-- ID now contains the value "1." The Span.sub.-- Tree routine then determines whether CurNode contains a nil value (step 150). CurNode does not contain a nil value, therefore the Span.sub.-- Tree routine determines whether CurNode is labeled with a path identifier (step 152). CurNode is not labeled with a path identifier, therefore the Span.sub.-- Tree routine labels CurNode with the value stored in Path.sub.-- ID (step 156). Node 232 is now labeled with the path identifier "1." Next, the Span.sub.-- Tree routine determines whether CurNode has two output edges (step 158). Because node 232 has an output edge 272 to a follower node 234 and an output edge 274 to a target node 236, the Span.sub.-- Tree routine calls the routine ProcessTwo (step 160). For purposes of this example, the rightmost node is the target node and the leftmost node is the follower node. The ProcessTwo routine determines that neither the follower node 234 nor the target node 236 have already been labeled with the current path identifier "1" (steps 180 and 186, FIG. 5). The ProcessTwo routine then determines whether the target node 236 has already been labeled with a path identifier (step 190). Because the target node 236 has not already been labeled with a path identifier, the ProcessTwo routine pushes a pointer to the target node 236 onto the node list and labels the edge 272 with the value stored in Path.sub.-- ID. Edge 272 is now labeled with the value "1." The ProcessTwo routine stores a pointer to the follower node 234 in CurNode (step 198). A pointer to node 234 is now stored in CurNode. Node 234 has an edge 276 to a follower node 238 and an edge 320 to a target node 240. The Span.sub.-- Tree routine labels node 234 with the path identifier "1" (step 156, FIG. 4) and the ProcessTwo routine is called (step 160). The ProcessTwo routine pushes a pointer to the target node 240 onto the node list and labels the edge 276 with the path identifier "1" (step196, FIG. 5). A pointer to the follower node 238 is then stored in CurNode (step 198). The Span.sub.-- Tree routine then determines whether CurNode has already been labeled with a path identifier (step 152, FIG. 4). After determining that CurNode has not already been labeled with a path identifier, the Span.sub.-- Tree routine labels CurNode with the path identifier "1" (step 156). Because node 238 has only one output edge--edge 278, the Span.sub.-- Tree routine calls the routine ProcessOne routine (step 164). The ProcessOne routine determines whether the edge 278 loops back to the current path (step 170, FIG. 6). Because edge 278 does not loop back to the current path, the ProcessOne routine labels edge 278 with the path identifier "1" and stores a pointer to node 244 in CurNode (step 174). The Span.sub.-- Tree routine continues in a similar manner, labeling nodes 244, 250, 256, 262 and edges 282, 284, 286 with the path identifier "1." When a pointer to node 262 is stored in CurNode, the Span.sub.-- Tree routine calls the routine ProcessTwo because node 262 has two output edges, edge 288 and edge 290. The ProcessTwo routine determines that both output edges loop back to the current path (step 180, FIG. 5). The path identified as "1" terminates with node 262 because node 262 contains two output edges that both loop back to the current path. After path "1" is terminated, the Span.sub.-- Tree routine pops a new pointer off of the node list and stores it in CurNode. In this example, a pointer to node 236 is the next pointer on the node list. The Span.sub.-- Tree routine then labels the remaining nodes in the control flow graph 230. FIG. 8B is a block diagram of the control flow graph 230 of FIG. 8A, including path identifiers for each node. Nodes 232, 234, 238, 244, 250, 256, and 262, along with edges 272, 276, 278, 282, 284, and 286 are labeled with the path identifier "1." Nodes 236, 240, 246, 254, 260, 264, and 268, along with edges 300, 302, 304, 306, and 296 are labeled with the path identifier "2." Nodes 252 and 258, and edges 310 and 294 are labeled with the path identifier "3." Nodes 242 and 248, along with edges 312 and 314 are labeled with the path identifier "4." Node 266 and edge 316 are labeled with the path identifier "5." Node 270 and edge 318 are labeled with the path identifier "6." When combined, paths "1" through "6" form a spanning tree for the control flow graph 230. Edges 274, 284, 288, 290, 320, 322, 324, 326, 328, 330, and 332, shown in the block diagram of FIG. 8B as dashed arrows, are not labeled with a path identifier, and are therefore not a part of the spanning tree. These edges are selected as instrumentation points. In addition, edge 231 is selected an instrumentation point. Edge 231 represents an exit instruction from a "dummy" block. The exit instruction of the "dummy" block may be a jump instruction that initiates execution of the computer program represented by the control flow graph 230. Selecting these edges as instrumentation points means that instrumentation code will be added to the exit instructions represented by the selected edges. After instrumentation code is added to the computer program, the computer program is executed. During execution of the computer program, the instrumentation code records, among other things, each time an instrumented edge is executed. FIG. 9A is a block diagram of the control flow graph of FIG. 8A, including illustrative execution information for each edge that was selected as an instrumentation point. As described above, edges 231, 274, 284, 288, 290, 320, 322, 324, 326, 328, 330, and 332 were selected as instrumentation points. The illustrative execution information represents how many times an instrumented exit instruction was executed during execution of the computer program. The execution information for an instruction is represented as a "weight" of a corresponding edge. Edge 231 has a weight of 20; edge 274 has a weight of 10; edge 284 has a weight of 2; edge 288 has a weight of 2; edge 290 has a weight of 1; edge 320 has a weight of 6; edge 322 has a weight of 8; edge 324 has a weight of 4; edge 326 has a weight of 2; edge 328 has a weight of 1; edge 330 has a weight of 5; and edge 332 has a weight of 3. Now that the weight of selected edges is known, the weight of every other edge can be determined using a variation of Kirchhoff's electrical current law and the direction specified within the control flow graph. Kirchhoff's electrical current law teaches that the algebraic sum of all the currents at any node in a circuit equals zero. Applying a principle similar to Kirchhoff's law to a control flow graph, we can say that the sum of edge weights at any node in a control flow graph equals zero. Direction must be specified in the control flow graph for this principle to work. For example, consider the node 232 in the control flow graph 230 of FIG. 9A. The weight of the input edge 231 of the node 232 was determined to be 20, and the weight of the exit edge 274 of the node 232 was determined to be 10. Therefore the weight of the output edge 272 must be 10. The weight of output edge 272 is calculated by subtracting the sum of the weights of the output edges from the sum of the weights of the input edges ›20-(10+x)=0; x=10!. Applying this principle to the rest of the control flow graph 230, the weight of each edge can be determined. FIG. 9B is a block diagram of the control flow graph 230, including the weight of every edge. Note that the weight of the input edge 231 is equal to the weight of the output edge 334. In an alternate embodiment of the present invention, at the start of the Span.sub.-- Tree routine, every edge in the control flow graph is selected as an instrumentation point. The Span.sub.-- Tree routine traverses the control flow graph to determine which instrumentation points will be "skipped." This alternate embodiment is presented below in Table B as a routine Alt.sub.-- Span.sub.-- Tree. A data structure CurNode is used to keep track of whether a node's follower node or target node is part of a current path. CurNode contains the following data fields: CurNode->Skip, CurNode->Label, CurNode->Type, CurNode->Follower, and CurNode->Target. When identifying a path through the control flow graph, this alternate embodiment examines the type of the exit instruction of a block rather than examining the number of output edges of a corresponding node.
TABLE B
______________________________________
Alt.sub.-- Span.sub.-- Tree
Initialize StartList
while (StartList is not empty)
Initialize CurLabel
Node = PopStartList()
if (Node is Labeled) continue
PushNode(Node)
while (NodeList is not empty)
Node = PopNodeList()
if (Node is Labeled) continue
CurLabel++
LastBranch = NIL
CurNode = Node
while (CurNode is not NIL)
if (CurNode is Labeled)
CurNode = NIL
break;
CurNode->Label = CurLabel
Switch (CurNode->Type)
case BranchConditional:
DetermineSkip(CurNode->Follower, CurNode->
Target)
break;
case CallConditional:
case Call:
if (CurNode->Follower |= NIL)
PushNode(CurNode->Follower)
case Branch:
DetermineSkip(CurNode->Target, NIL)
break;
case BranchConditionalIndirect:
case FallThrough:
DetermineSkip(CurNode->Follower, NIL)
break;
case CallConditionalIndirect:
case CallIndirect:
if (CurNode->Follower |= NIL)
PushNode(CurNode->Follower)
break;
case BranchIndirect:
endswitch
endwhile
endwhile
endwhile
DetermineSkip(Node1, Node2)
Loop = DetermineLoop(Node1, Node2)
switch (Loop)
ParentNode = CurNode
case NeitherLoop:
if ((Node2 |= NIL) && (Node2 is Labeled))
PushNode(Node1)
LastBranch = CurNode
CurNode = Node2
ParentNode->Skip = Node2
else
if (Node2 |= NIL)
PushNode(Node2)
LastBranch = CurNode
endif
CurNode = Node1
ParentNode->Skip = Node1
endif
break;
case Node1Loop:
if (N2 |= NIL)
LastBranch = CurNode
CurNode = Node2
ParentNode->Skip = Node2
else
CurNode = NIL
endif
break;
case Node2Loop:
LastBranch = CurNode
CurNode = Node1
ParentNode->Skip = Node1
break;
case BothLoop:
If (LastBranch |= NIL) BackTrace()
break;
return
BackTrace()
PutNode(LastBranch->Skip)
if (LastBranch->Skip = LastBranch->Follower)
CurNode = LastBranch->Target
else
CurNode = LastBranch->Follower
endif
NextNode = LastBranch->Skip
LastBranch->Skip = CurNode
do
NextNode->Label = 0
PrevNode = NextNode
NextNode = NextNode->Skip
PrevNode->Skip = 0
while (NextNode |= NIL)
LastBranch = NIL
return
______________________________________
Although the present invention has been described in terms of a preferred embodiment, it is not intended that the invention be limited to this embodiment. Modifications within the spirit of the invention will be apparent to those skilled in the art; the scope of the present invention is defined by the claims which follow.
|
Same subclass Same class Consider this |
||||||||||