60 lines
1.2 KiB
Java
60 lines
1.2 KiB
Java
package cd.util;
|
|
|
|
import cd.ir.BasicBlock;
|
|
import cd.ir.ControlFlowGraph;
|
|
|
|
import java.util.*;
|
|
|
|
/**
|
|
* A potentially handy iterator which yields the blocks in a control-flow
|
|
* graph. The order is pre-order, depth-first. Pre-order means that a
|
|
* node is visited before its successors.
|
|
*/
|
|
public class DepthFirstSearchPreOrder implements Iterable<BasicBlock> {
|
|
|
|
public final ControlFlowGraph cfg;
|
|
|
|
public DepthFirstSearchPreOrder(ControlFlowGraph cfg) {
|
|
this.cfg = cfg;
|
|
}
|
|
|
|
public Iterator<BasicBlock> iterator() {
|
|
return new Iterator<BasicBlock>() {
|
|
|
|
/** Blocks we still need to visit */
|
|
private final Stack<BasicBlock> stack = new Stack<BasicBlock>();
|
|
|
|
/** Blocks we pushed thus far */
|
|
private final Set<BasicBlock> pushed = new HashSet<BasicBlock>();
|
|
|
|
{
|
|
stack.add(cfg.start);
|
|
pushed.add(cfg.start);
|
|
}
|
|
|
|
public boolean hasNext() {
|
|
return !stack.isEmpty();
|
|
}
|
|
|
|
public BasicBlock next() {
|
|
if (stack.isEmpty())
|
|
throw new NoSuchElementException();
|
|
|
|
BasicBlock res = stack.pop();
|
|
for (BasicBlock s : res.successors)
|
|
if (!pushed.contains(s)) {
|
|
pushed.add(s);
|
|
stack.add(s);
|
|
}
|
|
|
|
return res;
|
|
}
|
|
|
|
public void remove() {
|
|
throw new UnsupportedOperationException();
|
|
}
|
|
|
|
};
|
|
}
|
|
|
|
}
|