KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > toolkits > graph > SlowPseudoTopologicalOrderer


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 1997-1999 Raja Vallee-Rai, Patrick Lam
3  *
4  * This library is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU Lesser General Public
6  * License as published by the Free Software Foundation; either
7  * version 2.1 of the License, or (at your option) any later version.
8  *
9  * This library is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12  * Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public
15  * License along with this library; if not, write to the
16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17  * Boston, MA 02111-1307, USA.
18  */
19
20 /*
21  * Modified by the Sable Research Group and others 1997-1999.
22  * See the 'credits' file distributed with Soot for the complete list of
23  * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
24  */
25
26
27 package soot.toolkits.graph;
28
29 import soot.*;
30 import soot.util.*;
31 import java.util.*;
32
33
34 /**
35  * Provide the pseudo topological order of a graph's nodes.
36  * It has same functionality as PseudoTopologicalOrderer;
37  * however, this class considers the order of successors.
38  * It runs slower but more precise. Currently it was only used by
39  * ArrayBoundsCheckerAnalysis to reduce the iteration numbers.
40  *
41  * @see: PseudoTopologicalOrderer
42  */
43
44 public class SlowPseudoTopologicalOrderer
45 {
46     public SlowPseudoTopologicalOrderer( Singletons.Global g ) {}
47     public static SlowPseudoTopologicalOrderer v() { return G.v().soot_toolkits_graph_SlowPseudoTopologicalOrderer(); }
48
49     public static final boolean REVERSE = true;
50     public SlowPseudoTopologicalOrderer() {}
51     public SlowPseudoTopologicalOrderer(boolean isReversed) { mIsReversed = isReversed;}
52
53     private Map stmtToColor;
54     private static final int
55         WHITE = 0,
56         GRAY = 1,
57         BLACK = 2;
58
59     private LinkedList order;
60     private boolean mIsReversed = false;
61     private DirectedGraph graph;
62
63     private List reverseOrder;
64     private HashMap succsMap = new HashMap();
65
66     /**
67      * @param g a DirectedGraph instance whose nodes we which to order.
68      * @return a pseudo-topologically ordered list of the graph's nodes.
69      */
70     public List newList(DirectedGraph g)
71     {
72         return computeOrder(g);
73     }
74
75     /**
76      * Set the ordering for the orderer.
77      * @param isReverse specify if we want reverse pseudo-topological ordering, or not.
78      */
79     public void setReverseOrder(boolean isReversed)
80     {
81         mIsReversed = isReversed;
82     }
83
84     /**
85      * Check the ordering for the orderer.
86      * @return true if we have reverse pseudo-topological ordering, false otherwise.
87      */
88     public boolean isReverseOrder()
89     {
90         return mIsReversed;
91     }
92
93     /**
94      * Orders in pseudo-topological order.
95      * @param g a DirectedGraph instance we want to order the nodes for.
96      * @return an ordered list of the graph's nodes.
97      */
98     LinkedList computeOrder(DirectedGraph g)
99     {
100         stmtToColor = new HashMap();
101             
102         order = new LinkedList();
103         graph = g;
104
105     PseudoTopologicalReverseOrderer orderer =
106         new PseudoTopologicalReverseOrderer();
107
108     reverseOrder = orderer.newList(g);
109     
110         // Color all nodes white
111 {
112             
113
114             Iterator stmtIt = g.iterator();
115             while(stmtIt.hasNext())
116             {
117                 Object JavaDoc s = stmtIt.next();
118                 
119                 stmtToColor.put(s, new Integer JavaDoc(WHITE));
120             }
121         }
122         
123         // Visit each node
124 {
125             Iterator stmtIt = g.iterator();
126             
127             while(stmtIt.hasNext())
128             {
129                 Object JavaDoc s = stmtIt.next();
130                
131                 if(((Integer JavaDoc) stmtToColor.get(s)).intValue() == WHITE)
132                     visitNode(s);
133             }
134         }
135         
136         return order;
137     }
138
139     // Unfortunately, the nice recursive solution fails
140 // because of stack overflows
141
142     // Fill in the 'order' list with a pseudo topological order (possibly reversed)
143 // list of statements starting at s. Simulates recursion with a stack.
144
145     
146     private void visitNode(Object JavaDoc startStmt)
147     {
148         LinkedList stmtStack = new LinkedList();
149         LinkedList indexStack = new LinkedList();
150         
151         stmtToColor.put(startStmt, new Integer JavaDoc(GRAY));
152         
153         stmtStack.addLast(startStmt);
154         indexStack.addLast(new Integer JavaDoc(-1));
155         
156         while(!stmtStack.isEmpty())
157         {
158             int toVisitIndex = ((Integer JavaDoc) indexStack.removeLast()).intValue();
159             Object JavaDoc toVisitNode = stmtStack.getLast();
160             
161             toVisitIndex++;
162             
163             indexStack.addLast(new Integer JavaDoc(toVisitIndex));
164             
165             if(toVisitIndex >= graph.getSuccsOf(toVisitNode).size())
166             {
167                 // Visit this node now that we ran out of children
168 if(mIsReversed)
169                         order.addLast(toVisitNode);
170                     else
171                         order.addFirst(toVisitNode);
172                            
173                     stmtToColor.put(toVisitNode, new Integer JavaDoc(BLACK));
174                 
175                 // Pop this node off
176 stmtStack.removeLast();
177                     indexStack.removeLast();
178             }
179             else
180             {
181         List orderedSuccs = (List)succsMap.get(toVisitNode);
182         if (orderedSuccs == null)
183         {
184             orderedSuccs = new LinkedList();
185             succsMap.put(toVisitNode, orderedSuccs);
186             /* make ordered succs */
187             
188             List allsuccs = graph.getSuccsOf(toVisitNode);
189             
190             for (int i=0; i<allsuccs.size(); i++)
191             {
192             Object JavaDoc cur = allsuccs.get(i);
193             
194             int j=0;
195
196             for (; j<orderedSuccs.size(); j++)
197             {
198                 Object JavaDoc comp = orderedSuccs.get(j);
199
200                 int idx1 = reverseOrder.indexOf(cur);
201                 int idx2 = reverseOrder.indexOf(comp);
202
203                 if (idx1 < idx2)
204                 break;
205             }
206
207             orderedSuccs.add(j, cur);
208             }
209         }
210
211                 Object JavaDoc childNode = orderedSuccs.get(toVisitIndex);
212                 
213                 // Visit this child next if not already visited (or on stack)
214 if(((Integer JavaDoc) stmtToColor.get(childNode)).intValue() == WHITE)
215                     {
216                         stmtToColor.put(childNode, new Integer JavaDoc(GRAY));
217                         
218                         stmtStack.addLast(childNode);
219                         indexStack.addLast(new Integer JavaDoc(-1));
220                     }
221             }
222         }
223     }
224
225 private class PseudoTopologicalReverseOrderer
226 {
227     private Map stmtToColor;
228     private static final int
229         WHITE = 0,
230         GRAY = 1,
231         BLACK = 2;
232
233     private LinkedList order;
234     private boolean mIsReversed = false;
235     private DirectedGraph graph;
236
237     /**
238      * @param g a DirectedGraph instance whose nodes we which to order.
239      * @return a pseudo-topologically ordered list of the graph's nodes.
240      */
241     List newList(DirectedGraph g)
242     {
243         return computeOrder(g);
244     }
245
246     /**
247      * Orders in pseudo-topological order.
248      * @param g a DirectedGraph instance we want to order the nodes for.
249      * @return an ordered list of the graph's nodes.
250      */
251     LinkedList computeOrder(DirectedGraph g)
252     {
253         stmtToColor = new HashMap();
254             
255         order = new LinkedList();
256         graph = g;
257
258         // Color all nodes white
259 {
260             Iterator stmtIt = g.iterator();
261             while(stmtIt.hasNext())
262             {
263                 Object JavaDoc s = stmtIt.next();
264                 
265                 stmtToColor.put(s, new Integer JavaDoc(WHITE));
266             }
267         }
268         
269         // Visit each node
270 {
271             Iterator stmtIt = g.iterator();
272             
273             while(stmtIt.hasNext())
274             {
275                 Object JavaDoc s = stmtIt.next();
276                
277                 if(((Integer JavaDoc) stmtToColor.get(s)).intValue() == WHITE)
278                     visitNode(s);
279             }
280         }
281         
282         return order;
283     }
284
285     private void visitNode(Object JavaDoc startStmt)
286     {
287         LinkedList stmtStack = new LinkedList();
288         LinkedList indexStack = new LinkedList();
289         
290         stmtToColor.put(startStmt, new Integer JavaDoc(GRAY));
291         
292         stmtStack.addLast(startStmt);
293         indexStack.addLast(new Integer JavaDoc(-1));
294         
295         while(!stmtStack.isEmpty())
296         {
297             int toVisitIndex = ((Integer JavaDoc) indexStack.removeLast()).intValue();
298             Object JavaDoc toVisitNode = stmtStack.getLast();
299             
300             toVisitIndex++;
301             
302             indexStack.addLast(new Integer JavaDoc(toVisitIndex));
303             
304             if(toVisitIndex >= graph.getPredsOf(toVisitNode).size())
305             {
306                 // Visit this node now that we ran out of children
307 if(mIsReversed)
308                         order.addLast(toVisitNode);
309                     else
310                         order.addFirst(toVisitNode);
311                            
312                     stmtToColor.put(toVisitNode, new Integer JavaDoc(BLACK));
313                 
314                 // Pop this node off
315 stmtStack.removeLast();
316                     indexStack.removeLast();
317             }
318             else
319             {
320                 Object JavaDoc childNode = graph.getPredsOf(toVisitNode).get(toVisitIndex);
321                 
322                 // Visit this child next if not already visited (or on stack)
323 if(((Integer JavaDoc) stmtToColor.get(childNode)).intValue() == WHITE)
324                     {
325                         stmtToColor.put(childNode, new Integer JavaDoc(GRAY));
326                         
327                         stmtStack.addLast(childNode);
328                         indexStack.addLast(new Integer JavaDoc(-1));
329                     }
330             }
331         }
332     }
333     
334 }
335     
336 }
337
Popular Tags