001: /*
002: * Bytecode Analysis Framework
003: * Copyright (C) 2003,2004 University of Maryland
004: *
005: * This library is free software; you can redistribute it and/or
006: * modify it under the terms of the GNU Lesser General Public
007: * License as published by the Free Software Foundation; either
008: * version 2.1 of the License, or (at your option) any later version.
009: *
010: * This library is distributed in the hope that it will be useful,
011: * but WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * Lesser General Public License for more details.
014: *
015: * You should have received a copy of the GNU Lesser General Public
016: * License along with this library; if not, write to the Free Software
017: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
018: */
019:
020: package edu.umd.cs.findbugs.ba;
021:
022: import java.util.Collection;
023: import java.util.HashSet;
024:
025: import edu.umd.cs.findbugs.ba.vna.ValueNumber;
026: import edu.umd.cs.findbugs.ba.vna.ValueNumberAnalysis;
027: import edu.umd.cs.findbugs.ba.vna.ValueNumberFactory;
028: import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
029:
030: /**
031: * Lock counts for values (as produced by ValueNumberAnalysis).
032: * A LockSet tells us the lock counts for all values in a method,
033: * insofar as we can accurately determine them.
034: *
035: * @author David Hovemeyer
036: * @see ValueNumberAnalysis
037: */
038: public final class LockSet {
039: /**
040: * An uninitialized lock value.
041: */
042: public static final int TOP = -1;
043:
044: /**
045: * An invalid lock count resulting from the meet of two
046: * different (inconsistent) lock counts.
047: */
048: public static final int BOTTOM = -2;
049:
050: private static final int INVALID = -1;
051: private static final int DEFAULT_CAPACITY = 8;
052:
053: /**
054: * Lock counts are stored in an array.
055: * Even indices <i>i</i> are value numbers of lock objects.
056: * Odd indices <i>i+1</i> are lock counts.
057: * This representation is fairly compact in memory.
058: */
059: private int[] array;
060:
061: /**
062: * The lock count value to return for nonexistent lock entries.
063: */
064: private int defaultLockCount;
065:
066: /**
067: * Constructor.
068: * Creates an empty lock set which returns TOP for
069: * nonexistent lock entries.
070: */
071: public LockSet() {
072: this .array = new int[DEFAULT_CAPACITY];
073: this .defaultLockCount = TOP;
074: clear();
075: }
076:
077: /**
078: * Get the lock count for given lock object.
079: *
080: * @param valueNumber value number of the lock object
081: * @return the lock count for the lock object
082: */
083: public int getLockCount(int valueNumber) {
084: int index = findIndex(valueNumber);
085: if (index < 0)
086: return defaultLockCount;
087: else
088: return array[index + 1];
089: }
090:
091: public boolean isTop() {
092: return defaultLockCount == TOP;
093: }
094:
095: /**
096: * Set the lock count for a lock object.
097: *
098: * @param valueNumber value number of the lock object
099: * @param lockCount the lock count for the lock
100: */
101: public void setLockCount(int valueNumber, int lockCount) {
102: int index = findIndex(valueNumber);
103: if (index < 0) {
104: addEntry(index, valueNumber, lockCount);
105: } else {
106: array[index + 1] = lockCount;
107: }
108: }
109:
110: /**
111: * Set the default lock count to return for nonexistent lock entries.
112: *
113: * @param defaultLockCount the default lock count value
114: */
115: public void setDefaultLockCount(int defaultLockCount) {
116: this .defaultLockCount = defaultLockCount;
117: }
118:
119: /**
120: * Get the number of distinct lock values with positive lock counts.
121: */
122: public int getNumLockedObjects() {
123: int result = 0;
124: for (int i = 0; i < array.length; i += 2) {
125: if (array[i] == INVALID)
126: break;
127: if (array[i + 1] > 0)
128: ++result;
129: }
130: return result;
131: }
132:
133: /**
134: * Make this LockSet the same as the given one.
135: *
136: * @param other the LockSet to copy
137: */
138: public void copyFrom(LockSet other) {
139: if (other.array.length != array.length) {
140: array = new int[other.array.length];
141: }
142: System.arraycopy(other.array, 0, array, 0, array.length);
143: this .defaultLockCount = other.defaultLockCount;
144: }
145:
146: /**
147: * Clear all entries out of this LockSet.
148: */
149: public void clear() {
150: for (int i = 0; i < array.length; i += 2) {
151: array[i] = INVALID;
152: }
153: }
154:
155: /**
156: * Meet this LockSet with another LockSet,
157: * storing the result in this object.
158: *
159: * @param other the other LockSet
160: */
161: public void meetWith(LockSet other) {
162: for (int i = 0; i < array.length; i += 2) {
163: int valueNumber = array[i];
164: if (valueNumber < 0)
165: break;
166:
167: int mine = array[i + 1];
168: int his = other.getLockCount(valueNumber);
169: array[i + 1] = mergeValues(mine, his);
170: }
171:
172: for (int i = 0; i < other.array.length; i += 2) {
173: int valueNumber = other.array[i];
174: if (valueNumber < 0)
175: break;
176:
177: int mine = getLockCount(valueNumber);
178: int his = other.array[i + 1];
179: setLockCount(valueNumber, mergeValues(mine, his));
180: }
181:
182: setDefaultLockCount(0);
183: }
184:
185: /**
186: * Return whether or not this LockSet is the same as the one given.
187: *
188: * @param other the other LockSet
189: */
190: public boolean sameAs(LockSet other) {
191: return this .identicalSubset(other)
192: && other.identicalSubset(this );
193: }
194:
195: /**
196: * Determine whether or not this lock set contains any
197: * locked values which are method return values.
198: *
199: * @param factory the ValueNumberFactory that produced the lock values
200: */
201: public boolean containsReturnValue(ValueNumberFactory factory) {
202: for (int i = 0; i < array.length; i += 2) {
203: int valueNumber = array[i];
204: if (valueNumber < 0)
205: break;
206: int lockCount = array[i + 1];
207: if (lockCount > 0
208: && factory.forNumber(valueNumber).hasFlag(
209: ValueNumber.RETURN_VALUE))
210: return true;
211: }
212: return false;
213: }
214:
215: /**
216: * Destructively intersect this lock set with another.
217: * Note that this is <em>not</em> a dataflow merge:
218: * we are interested in finding out which locks are held
219: * in both sets, not in the exact lock counts.
220: *
221: * @param other the other LockSet
222: */
223: public void intersectWith(LockSet other) {
224: for (int i = 0; i < array.length; i += 2) {
225: int valueNumber = array[i];
226: if (valueNumber < 0)
227: break;
228: int myLockCount = array[i + 1];
229: if (myLockCount <= 0)
230: continue;
231: int otherLockCount = other.getLockCount(valueNumber);
232: if (otherLockCount <= 0) {
233: /* This set holds the lock, but the other one doesn't. */
234: array[i + 1] = 0;
235: }
236: }
237: }
238:
239: /**
240: * Return whether or not this lock set is empty,
241: * meaning that no locks have a positive lock count.
242: *
243: * @return true if no locks are held, false if at least
244: * one lock is held
245: */
246: public boolean isEmpty() {
247: for (int i = 0; i < array.length; i += 2) {
248: int valueNumber = array[i];
249: if (valueNumber < 0)
250: return true;
251: int myLockCount = array[i + 1];
252: if (myLockCount > 0)
253: return false;
254: }
255: return true;
256: }
257:
258: private boolean identicalSubset(LockSet other) {
259: for (int i = 0; i < array.length; i += 2) {
260: int valueNumber = array[i];
261: if (valueNumber < 0)
262: break;
263: int mine = array[i + 1];
264: int his = other.getLockCount(valueNumber);
265: if (mine != his)
266: return false;
267: //System.out.println("For value " + valueNumber + ", " + mine + "==" + his);
268: }
269: return true;
270: }
271:
272: private static int mergeValues(int a, int b) {
273: if (a == TOP)
274: return b;
275: else if (b == TOP)
276: return a;
277: else if (a == BOTTOM || b == BOTTOM)
278: return BOTTOM;
279: else if (a == b)
280: return a;
281: else
282: return BOTTOM;
283: }
284:
285: private int findIndex(int valueNumber) {
286: for (int i = 0; i < array.length; i += 2) {
287: int value = array[i];
288: if (value < 0)
289: return -(i + 1); // didn't find requested valueNumber - return first available slot
290: else if (value == valueNumber)
291: return i; // found requested valueNumber
292: }
293: return -(array.length + 1); // didn't find requested valueNumber, and array is full
294: }
295:
296: private void addEntry(int negatedIndex, int valueNumber,
297: int lockCount) {
298: int index = -(negatedIndex + 1);
299: int origCapacity = array.length;
300: if (index == origCapacity) {
301: // Grow the array.
302:
303: // Allocate twice the space of the old array
304: int[] data = new int[origCapacity * 2];
305:
306: // Copy existing data
307: System.arraycopy(array, 0, data, 0, origCapacity);
308:
309: // Clear entries in the new part of the array
310: // that won't be used to store the entry that's
311: // being added
312: for (int i = index + 2; i < data.length; i += 2) {
313: data[i] = INVALID;
314: }
315:
316: // Now we're ready to use the new array
317: array = data;
318: }
319:
320: array[index] = valueNumber;
321: array[index + 1] = lockCount;
322: }
323:
324: @Override
325: public String toString() {
326: StringBuffer buf = new StringBuffer();
327: buf.append('[');
328: boolean first = true;
329: if (defaultLockCount == 0) {
330: buf.append("default=0");
331: first = false;
332: }
333: for (int i = 0; i < array.length; i += 2) {
334: int valueNumber = array[i];
335: if (valueNumber < 0)
336: continue;
337: int lockCount = array[i + 1];
338: if (lockCount == 0)
339: continue;
340: if (first)
341: first = false;
342: else
343: buf.append(',');
344: buf.append(valueNumber);
345: buf.append('=');
346: if (lockCount == TOP)
347: buf.append("TOP");
348: else if (lockCount == BOTTOM)
349: buf.append("BOTTOM");
350: else
351: buf.append(lockCount);
352: }
353: buf.append(']');
354: return buf.toString();
355: }
356:
357: /**
358: * @param frame
359: * @return a set of the locked value numbers
360: */
361: public Collection<ValueNumber> getLockedValueNumbers(
362: ValueNumberFrame frame) {
363: if (frame == null)
364: throw new IllegalArgumentException("Null Frame");
365: HashSet<ValueNumber> result = new HashSet<ValueNumber>();
366: for (ValueNumber v : frame.allSlots())
367: if (v != null && getLockCount(v.getNumber()) > 0)
368: result.add(v);
369: return result;
370: }
371:
372: /*
373: public static void main(String[] argv) {
374: LockSet l = new LockSet();
375: l.setLockCount(0, 1);
376: System.out.println(l);
377: l.setLockCount(0, 2);
378: System.out.println(l);
379: l.setLockCount(15, 1);
380: System.out.println(l);
381: LockSet ll = new LockSet();
382: ll.setLockCount(0, 1);
383: ll.setLockCount(15, 1);
384: ll.setLockCount(69, 3);
385: LockSet tmp = new LockSet();
386: tmp.copyFrom(ll);
387: ll.meetWith(l);
388: System.out.println(l + " merge with " + tmp + " ==> " + ll);
389:
390: LockSet dup = new LockSet();
391: dup.copyFrom(ll);
392: System.out.println(ll + " == " + dup + " ==> " + ll.sameAs(dup));
393: System.out.println(ll + " == " + l + " ==> " + ll.sameAs(l));
394: }
395: */
396: }
397:
398: // vim:ts=4
|