1 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 31 public final class SortedArraySet extends PointsToSetInternal { 32 public SortedArraySet( Type type, PAG pag ) { 33 super( type ); 34 this.pag = pag; 35 } 36 37 public final boolean isEmpty() { 38 return size == 0; 39 } 40 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 { newa[ newi++ ] = mya[ myi++ ]; 76 } 77 } else { 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 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 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 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 161 162 163 private Node[] nodes = null; 164 private int size = 0; 165 private PAG pag = null; 166 } 167 168 | Popular Tags |