001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2003 Ondrej Lhotak
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: package soot.util;
021:
022: /** This is the Soot internal implementation of java.util.BitSet with
023: * Felix and Jerome's clever efficient iterator. It was re-implemented
024: * from scratch by Ondrej Lhotak to avoid licence issues. It was named
025: * BitVector rather than BitSet to avoid a name clash with the one in
026: * the standard Java library.
027: *
028: * @author Ondrej Lhotak
029: */
030: public class BitVector {
031: public BitVector() {
032: this (64);
033: }
034:
035: /**Copy constructor*/
036: //Added by Adam Richard. More efficient than clone(), and easier to extend
037: public BitVector(BitVector other) {
038: bits = new long[other.bits.length];
039: System.arraycopy(other.bits, 0, bits, 0, other.bits.length);
040: }
041:
042: public BitVector(int numBits) {
043: int lastIndex = indexOf(numBits - 1);
044: bits = new long[lastIndex + 1];
045: }
046:
047: private long[] bits;
048:
049: private int indexOf(int bit) {
050: return bit >> 6;
051: }
052:
053: private long mask(int bit) {
054: return 1L << (bit & 63);
055: }
056:
057: public void and(BitVector other) {
058: if (this == other)
059: return;
060: long[] otherBits = other.bits;
061: int numToAnd = otherBits.length;
062: if (bits.length < numToAnd)
063: numToAnd = bits.length;
064: int i;
065: for (i = 0; i < numToAnd; i++) {
066: bits[i] = bits[i] & otherBits[i];
067: }
068: for (; i < bits.length; i++) {
069: bits[i] = 0L;
070: }
071: }
072:
073: public void andNot(BitVector other) {
074: long[] otherBits = other.bits;
075: int numToAnd = otherBits.length;
076: if (bits.length < numToAnd)
077: numToAnd = bits.length;
078: for (int i = 0; i < numToAnd; i++) {
079: bits[i] = bits[i] & ~otherBits[i];
080: }
081: }
082:
083: public void clear(int bit) {
084: if (indexOf(bit) < bits.length)
085: bits[indexOf(bit)] &= ~mask(bit);
086: }
087:
088: public Object clone() {
089: BitVector ret = new BitVector(length());
090: System.arraycopy(bits, 0, ret.bits, 0, ret.bits.length);
091: return ret;
092: }
093:
094: public boolean equals(Object o) {
095: if (!(o instanceof BitVector))
096: return false;
097: BitVector other = (BitVector) o;
098: int min = bits.length;
099: long[] longer = other.bits;
100: if (other.bits.length < min) {
101: min = other.bits.length;
102: longer = bits;
103: }
104: int i;
105: for (i = 0; i < min; i++) {
106: if (bits[i] != other.bits[i])
107: return false;
108: }
109: for (; i < longer.length; i++) {
110: if (longer[i] != 0L)
111: return false;
112: }
113: return true;
114: }
115:
116: public boolean get(int bit) {
117: if (indexOf(bit) >= bits.length)
118: return false;
119: return (bits[indexOf(bit)] & mask(bit)) != 0L;
120: }
121:
122: public int hashCode() {
123: long ret = 0;
124: for (long element : bits) {
125: ret ^= element;
126: }
127: return (int) ((ret >> 32) ^ ret);
128: }
129:
130: /** Returns index of highest-numbered one bit. */
131: public int length() {
132: int i;
133: for (i = bits.length - 1; i >= 0; i--) {
134: if (bits[i] != 0L)
135: break;
136: }
137: if (i < 0)
138: return 0;
139: long j = bits[i];
140: i++;
141: i <<= 6;
142: for (long k = 1L << 63; (k & j) == 0L; k >>= 1, i--)
143: ;
144: return i;
145: }
146:
147: public void copyFrom(BitVector other) {
148: if (this == other)
149: return;
150: long[] otherBits = other.bits;
151: int j;
152: for (j = otherBits.length - 1; j >= 0; j--) {
153: if (otherBits[j] != 0L)
154: break;
155: }
156: expand(j << 6);
157: int i = j + 1;
158: for (; j >= 0; j--) {
159: bits[j] = otherBits[j];
160: }
161: for (; i < bits.length; i++) {
162: bits[i] = 0L;
163: }
164: }
165:
166: public void or(BitVector other) {
167: if (this == other)
168: return;
169: long[] otherBits = other.bits;
170: int j;
171: for (j = otherBits.length - 1; j >= 0; j--) {
172: if (otherBits[j] != 0L)
173: break;
174: }
175: expand(j << 6);
176: for (; j >= 0; j--) {
177: bits[j] |= otherBits[j];
178: }
179: }
180:
181: /**Count the number of ones in the bitvector.
182: * @author Adam Richard
183: * This is Brian Kernighan's algorithm from:
184: * http://graphics.stanford.edu/~seander/bithacks.html
185: * and is efficient for sparse bit sets.
186: */
187: public int cardinality() {
188: int c = 0;
189: for (long v : bits) {
190: while (v != 0) {
191: v &= v - 1;
192: ++c;
193: }
194: }
195: return c;
196: }
197:
198: private void expand(int bit) {
199: int n = indexOf(bit) + 1;
200: if (n <= bits.length)
201: return;
202: if (bits.length * 2 > n)
203: n = bits.length * 2;
204: long[] newBits = new long[n];
205: System.arraycopy(bits, 0, newBits, 0, bits.length);
206: bits = newBits;
207: }
208:
209: public void xor(BitVector other) {
210: if (this == other)
211: return;
212: long[] otherBits = other.bits;
213: int j;
214: for (j = otherBits.length - 1; j >= 0; j--) {
215: if (otherBits[j] != 0L)
216: break;
217: }
218: expand(j << 6);
219: for (; j >= 0; j--) {
220: bits[j] ^= otherBits[j];
221: }
222: }
223:
224: public boolean set(int bit) {
225: expand(bit);
226: boolean ret = !get(bit);
227: bits[indexOf(bit)] |= mask(bit);
228: return ret;
229: }
230:
231: /** Returns number of bits in the underlying array. */
232: public int size() {
233: return bits.length << 6;
234: }
235:
236: public String toString() {
237: StringBuffer ret = new StringBuffer();
238: ret.append('{');
239: boolean start = true;
240: BitSetIterator it = new BitSetIterator(bits);
241: while (it.hasNext()) {
242: int bit = it.next();
243: if (!start)
244: ret.append(", ");
245: start = false;
246: ret.append(bit);
247: }
248: ret.append('}');
249: return ret.toString();
250: }
251:
252: /*
253: public boolean orAndAndNotCheck(BitVector orset, BitVector andset, BitVector andnotset) {
254: BitVector orAndAnd = (BitVector) orset.clone();
255: if( andset != null ) orAndAnd.and( andset );
256: if( andnotset != null ) orAndAnd.andNot( andnotset );
257: orAndAnd.or( this );
258: boolean ret = !orAndAnd.equals(this);
259: orAndAndNotOld( orset, andset, andnotset );
260: if( !this.equals( orAndAnd ) ) {
261: throw new RuntimeException( "orset is "+orset+"\nandset is "+andset+"\nandnotset is "+andnotset+"\nthis is "+this+"\ncorrect is "+orAndAnd );
262: }
263: return ret;
264: }
265: */
266: /**
267: * Computes this = this OR ((orset AND andset ) AND (NOT andnotset))
268: * Returns true iff this is modified.
269: * @param set a bit set.
270: */
271: public boolean orAndAndNot(BitVector orset, BitVector andset,
272: BitVector andnotset) {
273: boolean ret = false;
274: long[] a = null, b = null, c = null, d = null, e = null;
275: int al, bl, cl, dl;
276: a = this .bits;
277: al = a.length;
278: if (orset == null) {
279: bl = 0;
280: } else {
281: b = orset.bits;
282: bl = b.length;
283: }
284: if (andset == null) {
285: cl = 0;
286: } else {
287: c = andset.bits;
288: cl = c.length;
289: }
290: if (andnotset == null) {
291: dl = 0;
292: } else {
293: d = andnotset.bits;
294: dl = d.length;
295: }
296:
297: if (al < bl) {
298: e = new long[bl];
299: System.arraycopy(a, 0, e, 0, al);
300: this .bits = e;
301: } else {
302: e = a;
303: }
304: int i = 0;
305: long l;
306:
307: if (c == null) {
308: if (dl <= bl) {
309: while (i < dl) {
310: l = b[i] & ~d[i];
311: if ((l & ~e[i]) != 0)
312: ret = true;
313: e[i] |= l;
314: i++;
315: }
316: while (i < bl) {
317: l = b[i];
318: if ((l & ~e[i]) != 0)
319: ret = true;
320: e[i] |= l;
321: i++;
322: }
323: } else {
324: while (i < bl) {
325: l = b[i] & ~d[i];
326: if ((l & ~e[i]) != 0)
327: ret = true;
328: e[i] |= l;
329: i++;
330: }
331: }
332: } else if (bl <= cl && bl <= dl) {
333: // bl is the shortest
334: while (i < bl) {
335: l = b[i] & c[i] & ~d[i];
336: if ((l & ~e[i]) != 0)
337: ret = true;
338: e[i] |= l;
339: i++;
340: }
341: } else if (cl <= bl && cl <= dl) {
342: // cl is the shortest
343: while (i < cl) {
344: l = b[i] & c[i] & ~d[i];
345: if ((l & ~e[i]) != 0)
346: ret = true;
347: e[i] |= l;
348: i++;
349: }
350: } else {
351: // dl is the shortest
352: while (i < dl) {
353: l = b[i] & c[i] & ~d[i];
354: if ((l & ~e[i]) != 0)
355: ret = true;
356: e[i] |= l;
357: i++;
358: }
359: int shorter = cl;
360: if (bl < shorter)
361: shorter = bl;
362: while (i < shorter) {
363: l = b[i] & c[i];
364: if ((l & ~e[i]) != 0)
365: ret = true;
366: e[i] |= l;
367: i++;
368: }
369: }
370:
371: return ret;
372: }
373:
374: public static BitVector and(BitVector set1, BitVector set2) {
375: int min = set1.size();
376: {
377: int max = set2.size();
378: if (min > max) {
379: min = max;
380: }
381: // max is not necessarily correct at this point, so let it go
382: // out of scope
383: }
384:
385: BitVector ret = new BitVector(min);
386: long[] retbits = ret.bits;
387: long[] bits1 = set1.bits;
388: long[] bits2 = set2.bits;
389: min >>= 6;
390: for (int i = 0; i < min; i++) {
391: retbits[i] = bits1[i] & bits2[i];
392: }
393: return ret;
394: }
395:
396: public static BitVector or(BitVector set1, BitVector set2) {
397: int min = set1.size();
398: int max = set2.size();
399: if (min > max) {
400: min = max;
401: max = set1.size();
402: }
403:
404: BitVector ret = new BitVector(max);
405: long[] retbits = ret.bits;
406: long[] bits1 = set1.bits;
407: long[] bits2 = set2.bits;
408: min >>= 6;
409: max >>= 6;
410: for (int i = 0; i < min; i++) {
411: retbits[i] = bits1[i] | bits2[i];
412: }
413: if (bits1.length == min) {
414: System.arraycopy(bits2, min, retbits, min, max - min);
415: } else {
416: System.arraycopy(bits1, min, retbits, min, max - min);
417: }
418: return ret;
419: }
420:
421: public BitSetIterator iterator() {
422: return new BitSetIterator(bits);
423: }
424: }
|