KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > spark > solver > TopoSorter


1 /* Soot - a J*va Optimization Framework
2  * Copyright (C) 2002 Ondrej Lhotak
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 package soot.jimple.spark.solver;
21 import soot.jimple.spark.*;
22 import soot.jimple.spark.pag.*;
23 import soot.*;
24 import soot.util.*;
25 import java.util.*;
26 import soot.jimple.spark.sets.PointsToSetInternal;
27
28 /** Performs a pseudo-topological sort on the VarNodes in a PAG.
29  * @author Ondrej Lhotak
30  */
31
32 public class TopoSorter {
33     /** Actually perform the topological sort on the PAG. */
34     public void sort() {
35         for( Iterator it = pag.getVarNodeNumberer().iterator(); it.hasNext(); ) {
36             dfsVisit( (VarNode) it.next() );
37         }
38         visited = null;
39     }
40     public TopoSorter( PAG pag, boolean ignoreTypes ) {
41         this.pag = pag;
42         this.ignoreTypes = ignoreTypes;
43         //this.visited = new NumberedSet( pag.getVarNodeNumberer() );
44 this.visited = new HashSet();
45     }
46     
47     /* End of public methods. */
48     /* End of package methods. */
49
50     protected boolean ignoreTypes;
51     protected PAG pag;
52     protected int nextFinishNumber = 1;
53     protected HashSet visited;
54     protected void dfsVisit( VarNode n ) {
55         if( visited.contains( n ) ) return;
56         visited.add( n );
57         Node[] succs = pag.simpleLookup( n );
58         for( int i = 0; i < succs.length; i++ ) {
59             if( ignoreTypes
60             || pag.getTypeManager().castNeverFails(
61                     n.getType(), succs[i].getType() ) ) {
62                 dfsVisit( (VarNode) succs[i] );
63             }
64         }
65         n.setFinishingNumber( nextFinishNumber++ );
66     }
67 }
68
69
70
71
Popular Tags