|
1
20
21
26
27
28 package soot.toolkits.scalar;
29
30 import soot.util.*;
31 import java.util.*;
32
33
34
37 public class ArrayPackedSet extends AbstractBoundedFlowSet
38 {
39 ObjectIntMapper map;
40 int[] bits;
41
42 public ArrayPackedSet(FlowUniverse universe) {
43 this(new ObjectIntMapper(universe));
44 }
45
46 ArrayPackedSet(ObjectIntMapper map)
47 {
48
50
52 this(map, new int[map.size() / 32 + (((map.size() % 32) != 0) ? 1 : 0)]);
53 }
54
55 ArrayPackedSet(ObjectIntMapper map, int[] bits)
56 {
57 this.map = map;
58 this.bits = (int[]) bits.clone();
59 }
60
61
62 private boolean sameType(Object  flowSet)
63 {
64 return (flowSet instanceof ArrayPackedSet &&
65 ((ArrayPackedSet)flowSet).map == map);
66 }
67
68 public Object clone()
69 {
70 return new ArrayPackedSet(map, bits);
71 }
72
73 public Object emptySet()
74 {
75 return new ArrayPackedSet(map);
76 }
77
78 public int size()
79 {
80 int count = 0;
81
82 for(int i = 0; i < bits.length; i++)
83 {
84 int word = bits[i];
85
86 for(int j = 0; j < 32; j++)
87 if((word & (1 << j)) != 0)
88 count++;
89 }
90
91 return count;
92 }
93
94 public boolean isEmpty()
95 {
96 for(int i = 0; i < bits.length; i++)
97 if(bits[i] != 0)
98 return false;
99
100 return true;
101 }
102
103
104 public void clear()
105 {
106 for(int i = 0; i < bits.length; i++)
107 bits[i] = 0;
108 }
109
110
111 public List toList(int low, int high)
112 {
113 List elements = new ArrayList();
114
115 int startWord = low / 32,
116 startBit = low % 32;
117
118 int endWord = high / 32,
119 endBit = high % 32;
120
121 if(low > high)
122 return elements;
123
124 {
126 int word = bits[startWord];
127
128 int offset = startWord * 32;
129 int lastBit = (startWord != endWord) ? 32 : (endBit + 1);
130
131 for(int j = startBit; j < lastBit; j++)
132 {
133 if((word & (1 << j)) != 0)
134 elements.add(map.getObject(offset + j));
135 }
136 }
137
138 if(startWord != endWord && startWord + 1 != endWord)
140 {
141 for(int i = startWord + 1; i < endWord; i++)
142 {
143 int word = bits[i];
144 int offset = i * 32;
145
146 for(int j = 0; j < 32; j++)
147 {
148 if((word & (1 << j)) != 0)
149 elements.add(map.getObject(offset + j));
150 }
151 }
152 }
153
154 if(startWord != endWord)
156 {
157 int word = bits[endWord];
158 int offset = endWord * 32;
159 int lastBit = endBit + 1;
160
161 for(int j = 0; j < lastBit; j++)
162 {
163 if((word & (1 << j)) != 0)
164 elements.add(map.getObject(offset + j));
165 }
166 }
167
168 return elements;
169 }
170
171
172 public List toList()
173 {
174 List elements = new ArrayList();
175
176 for(int i = 0; i < bits.length; i++)
177 {
178 int word = bits[i];
179 int offset = i * 32;
180
181 for(int j = 0; j < 32; j++)
182 if((word & (1 << j)) != 0)
183 elements.add(map.getObject(offset + j));
184 }
185
186 return elements;
187 }
188
189 public void add(Object obj)
190 {
191 int bitNum = map.getInt(obj);
192
193 bits[bitNum / 32] |= 1 << (bitNum % 32);
194 }
195
196 public void complement(FlowSet destFlow)
197 {
198 if (sameType(destFlow)) {
199 ArrayPackedSet dest = (ArrayPackedSet) destFlow;
200
201 for(int i = 0; i < bits.length; i++)
202 dest.bits[i] = ~(this.bits[i]);
203
204 if(bits.length >= 1)
206 {
207 int lastValidBitCount = map.size() % 32;
208
209 if(lastValidBitCount != 0)
210 dest.bits[bits.length - 1] &= ~(0xFFFFFFFF << lastValidBitCount);
211 }
212 } else
213 super.complement(destFlow);
214 }
215
216 public void remove(Object obj)
217 {
218 int bitNum = map.getInt(obj);
219
220 bits[bitNum / 32] &= ~(1 << (bitNum % 32));
221 }
222
223 public void union(FlowSet otherFlow, FlowSet destFlow)
224 {
225 if (sameType(otherFlow) &&
226 sameType(destFlow)) {
227 ArrayPackedSet other = (ArrayPackedSet) otherFlow;
228 ArrayPackedSet dest = (ArrayPackedSet) destFlow;
229
230 if(!(other instanceof ArrayPackedSet) || bits.length != other.bits.length)
231 throw new RuntimeException ("Incompatible other set for union");
232
233 for(int i = 0; i < bits.length; i++)
234 dest.bits[i] = this.bits[i] | other.bits[i];
235 } else
236 super.union(otherFlow, destFlow);
237 }
238
239 public void difference(FlowSet otherFlow, FlowSet destFlow)
240 {
241 if (sameType(otherFlow) &&
242 sameType(destFlow)) {
243 ArrayPackedSet other = (ArrayPackedSet) otherFlow;
244 ArrayPackedSet dest = (ArrayPackedSet) destFlow;
245
246 if(!(other instanceof ArrayPackedSet) || bits.length != other.bits.length)
247 throw new RuntimeException ("Incompatible other set for union");
248
249 for(int i = 0; i < bits.length; i++)
250 dest.bits[i] = this.bits[i] & ~other.bits[i];
251 } else
252 super.difference(otherFlow, destFlow);
253 }
254
255 public void intersection(FlowSet otherFlow, FlowSet destFlow)
256 {
257 if (sameType(otherFlow) &&
258 sameType(destFlow)) {
259 ArrayPackedSet other = (ArrayPackedSet) otherFlow;
260 ArrayPackedSet dest = (ArrayPackedSet) destFlow;
261
262 if(!(other instanceof ArrayPackedSet) || bits.length != other.bits.length)
263 throw new RuntimeException ("Incompatible other set for union");
264
265 for(int i = 0; i < bits.length; i++)
266 dest.bits[i] = this.bits[i] & other.bits[i];
267 } else
268 super.intersection(otherFlow, destFlow);
269 }
270
271
273 public boolean contains(Object obj)
274 {
275
278 if (!map.contains(obj)) return false;
279
280 int bitNum = map.getInt(obj);
281
282 return (bits[bitNum / 32] & (1 << (bitNum % 32))) != 0;
283 }
284
285 public boolean equals(Object otherFlow)
286 {
287 if (sameType(otherFlow)) {
288 ArrayPackedSet other = (ArrayPackedSet) otherFlow;
289
290 for(int i = 0; i < bits.length; i++)
291 if(this.bits[i] != other.bits[i])
292 return false;
293
294 return true;
295 } else
296 return super.equals(otherFlow);
297 }
298
299 public void copy(FlowSet destFlow)
300 {
301 if (sameType(destFlow)) {
302 ArrayPackedSet dest = (ArrayPackedSet) destFlow;
303
304 for(int i = 0; i < bits.length; i++)
305 dest.bits[i] = this.bits[i];
306 } else
307 super.copy(destFlow);
308 }
309
310 }
311
312 |
Popular Tags |
Java API By Example, From Geeks To Geeks.