1 19 20 25 26 27 package soot.toolkits.graph; 28 29 import soot.*; 30 import soot.util.*; 31 import java.util.*; 32 33 34 38 39 40 41 public class PseudoTopologicalOrderer 42 { 43 public static final boolean REVERSE = true; 44 public PseudoTopologicalOrderer() {} 45 public PseudoTopologicalOrderer(boolean isReversed) { mIsReversed = isReversed;} 46 47 private Map stmtToColor; 48 private static final Object GRAY = new Object (); 49 private LinkedList order; 50 private boolean mIsReversed = false; 51 private DirectedGraph graph; 52 private int[] indexStack; 53 private Object [] stmtStack; 54 private int last; 55 56 60 public List newList(DirectedGraph g) 61 { 62 return computeOrder(g); 63 } 64 65 69 public void setReverseOrder(boolean isReversed) 70 { 71 mIsReversed = isReversed; 72 } 73 74 78 public boolean isReverseOrder() 79 { 80 return mIsReversed; 81 } 82 83 88 LinkedList computeOrder(DirectedGraph g) 89 { 90 stmtToColor = new HashMap((3*g.size())/2,0.7f); 91 indexStack = new int[g.size()]; 92 stmtStack = new Object [g.size()]; 93 order = new LinkedList(); 94 graph = g; 95 96 { 98 Iterator stmtIt = g.iterator(); 99 while(stmtIt.hasNext()) 100 { 101 Object s = stmtIt.next(); 102 if(stmtToColor.get(s) == null) 103 visitNode(s); 104 } 105 } 106 indexStack = null; 107 stmtStack = null; 108 stmtToColor = null; 109 return order; 110 } 111 112 115 118 119 private void visitNode(Object startStmt) 120 { 121 last = 0; 122 123 stmtToColor.put(startStmt, GRAY); 124 125 stmtStack[last] = startStmt; 126 indexStack[last++]= -1; 127 while(last > 0) 128 { 129 int toVisitIndex = ++indexStack[last-1]; 130 Object toVisitNode = stmtStack[last-1]; 131 132 if(toVisitIndex >= graph.getSuccsOf(toVisitNode).size()) 133 { 134 if(mIsReversed) 136 order.addLast(toVisitNode); 137 else 138 order.addFirst(toVisitNode); 139 140 last--; 141 } 142 else 143 { 144 Object childNode = graph.getSuccsOf(toVisitNode).get(toVisitIndex); 145 146 if(stmtToColor.get(childNode) == null) 147 { 148 stmtToColor.put(childNode, GRAY); 149 stmtStack[last]=childNode; 150 indexStack[last++]=-1; 151 } 152 } 153 } 154 } 155 156 } 157 | Popular Tags |