KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > spark > sets > SortedArraySet


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.sets;
21 import soot.jimple.spark.*;
22 import soot.jimple.spark.pag.Node;
23 import soot.jimple.spark.pag.PAG;
24 import soot.jimple.spark.internal.*;
25 import soot.util.*;
26 import soot.Type;
27
28 /** Implementation of points-to set using a sorted array.
29  * @author Ondrej Lhotak
30  */
31 public final class SortedArraySet extends PointsToSetInternal {
32     public SortedArraySet( Type type, PAG pag ) {
33         super( type );
34         this.pag = pag;
35     }
36     /** Returns true if this set contains no run-time objects. */
37     public final boolean isEmpty() {
38         return size == 0;
39     }
40     /** Adds contents of other into this set, returns true if this set
41      * changed. */
42     public final boolean addAll( final PointsToSetInternal other,
43             final PointsToSetInternal exclude ) {
44         boolean ret = false;
45         BitVector typeMask = ((TypeManager)pag.getTypeManager()).get( type );
46         if( other instanceof SortedArraySet ) {
47             SortedArraySet o = (SortedArraySet) other;
48             Node[] mya = nodes;
49             Node[] oa = o.nodes;
50             int osize = o.size;
51             Node[] newa = new Node[ size + osize ];
52             int myi = 0;
53             int oi = 0;
54             int newi = 0;
55             for( ;; ) {
56                 if( myi < size ) {
57                     if( oi < osize ) {
58                         int myhc = mya[myi].getNumber();
59                         int ohc = oa[oi].getNumber();
60                         if( myhc < ohc ) {
61                             newa[ newi++ ] = mya[ myi++ ];
62                         } else if( myhc > ohc ) {
63                             if( ( type == null || typeMask == null ||
64                                         typeMask.get(ohc) )
65                             && ( exclude == null || !exclude.contains( oa[oi] ) ) ) {
66                                 newa[ newi++ ] = oa[ oi ];
67                                 ret = true;
68                             }
69                             oi++;
70                         } else {
71                             newa[ newi++ ] = mya[ myi++ ];
72                             oi++;
73                         }
74                     } else { // oi >= osize
75 newa[ newi++ ] = mya[ myi++ ];
76                     }
77                 } else { // myi >= size
78 if( oi < osize ) {
79                         int ohc = oa[oi].getNumber();
80                         if( ( type == null || typeMask == null ||
81                                     typeMask.get(ohc) )
82                         && ( exclude == null || !exclude.contains( oa[oi] ) ) ) {
83                             newa[ newi++ ] = oa[ oi ];
84                             ret = true;
85                         }
86                         oi++;
87                     } else {
88                         break;
89                     }
90                 }
91             }
92             nodes = newa;
93             size = newi;
94             return ret;
95         }
96         return super.addAll( other, exclude );
97     }
98     /** Calls v's visit method on all nodes in this set. */
99     public final boolean forall( P2SetVisitor v ) {
100         for( int i = 0; i < size; i++ ) {
101             v.visit( nodes[i] );
102         }
103         return v.getReturnValue();
104     }
105     /** Adds n to this set, returns true if n was not already in this set. */
106     public final boolean add( Node n ) {
107         if( pag.getTypeManager().castNeverFails( n.getType(), type ) ) {
108             if( contains(n) ) return false;
109             int left = 0;
110             int right = size;
111             int mid;
112             int hc = n.getNumber();
113             while( left < right ) {
114                 mid = (left + right)/2;
115                 int midhc = nodes[mid].getNumber();
116                 if( midhc < hc ) {
117                     left = mid+1;
118                 } else if( midhc > hc ) {
119                     right = mid;
120                 } else break;
121             }
122             if( nodes == null ) {
123                 nodes = new Node[size+4];
124             } else if( size == nodes.length ) {
125                 Node[] newNodes = new Node[size+4];
126                 System.arraycopy( nodes, 0, newNodes, 0, nodes.length );
127                 nodes = newNodes;
128             }
129             System.arraycopy( nodes, left, nodes, left+1, size-left );
130             nodes[left] = n;
131             size++;
132             return true;
133         }
134         return false;
135     }
136     /** Returns true iff the set contains n. */
137     public final boolean contains( Node n ) {
138         int left = 0;
139         int right = size;
140         int hc = n.getNumber();
141         while( left < right ) {
142             int mid = (left + right)/2;
143             int midhc = nodes[mid].getNumber();
144             if( midhc < hc ) {
145                 left = mid+1;
146             } else if( midhc > hc ) {
147                 right = mid;
148             } else return true;
149         }
150         return false;
151     }
152     public final static P2SetFactory getFactory() {
153         return new P2SetFactory() {
154             public final PointsToSetInternal newSet( Type type, PAG pag ) {
155                 return new SortedArraySet( type, pag );
156             }
157         };
158     }
159
160     /* End of public methods. */
161     /* End of package methods. */
162
163     private Node[] nodes = null;
164     private int size = 0;
165     private PAG pag = null;
166 }
167
168
Popular Tags