LockSet


1   /*
2    * Bytecode Analysis Framework
3    * Copyright (C) 2003,2004 University of Maryland
4    * 
5    * This library is free software; you can redistribute it and/or
6    * modify it under the terms of the GNU Lesser General Public
7    * License as published by the Free Software Foundation; either
8    * version 2.1 of the License, or (at your option) any later version.
9    * 
10   * This library is distributed in the hope that it will be useful,
11   * but WITHOUT ANY WARRANTY; without even the implied warranty of
12   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13   * Lesser General Public License for more details.
14   * 
15   * You should have received a copy of the GNU Lesser General Public
16   * License along with this library; if not, write to the Free Software
17   * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package edu.umd.cs.findbugs.ba;
21  
22  import java.util.Collection  ;
23  import java.util.HashSet  ;
24  
25  import edu.umd.cs.findbugs.ba.vna.ValueNumber;
26  import edu.umd.cs.findbugs.ba.vna.ValueNumberAnalysis;
27  import edu.umd.cs.findbugs.ba.vna.ValueNumberFactory;
28  import edu.umd.cs.findbugs.ba.vna.ValueNumberFrame;
29  
30  /**
31   * Lock counts for values (as produced by ValueNumberAnalysis).
32   * A LockSet tells us the lock counts for all values in a method,
33   * insofar as we can accurately determine them.
34   *
35   * @author David Hovemeyer
36   * @see ValueNumberAnalysis
37   */
38  public final class LockSet {
39      /**
40       * An uninitialized lock value.
41       */
42      public static final int TOP = -1;
43  
44      /**
45       * An invalid lock count resulting from the meet of two
46       * different (inconsistent) lock counts.
47       */
48      public static final int BOTTOM = -2;
49  
50      private static final int INVALID = -1;
51      private static final int DEFAULT_CAPACITY = 8;
52  
53      /**
54       * Lock counts are stored in an array.
55       * Even indices <i>i</i> are value numbers of lock objects.
56       * Odd indices <i>i+1</i> are lock counts.
57       * This representation is fairly compact in memory.
58       */
59      private int[] array;
60  
61      /**
62       * The lock count value to return for nonexistent lock entries.
63       */
64      private int defaultLockCount;
65  
66      /**
67       * Constructor.
68       * Creates an empty lock set which returns TOP for
69       * nonexistent lock entries.
70       */
71      public LockSet() {
72          this.array = new int[DEFAULT_CAPACITY];
73          this.defaultLockCount = TOP;
74          clear();
75      }
76  
77      /**
78       * Get the lock count for given lock object.
79       *
80       * @param valueNumber value number of the lock object
81       * @return the lock count for the lock object
82       */
83      public int getLockCount(int valueNumber) {
84          int index = findIndex(valueNumber);
85          if (index < 0)
86              return defaultLockCount;
87          else
88              return array[index + 1];
89      }
90  
91      public boolean isTop() {
92          return defaultLockCount == TOP;
93      }
94      /**
95       * Set the lock count for a lock object.
96       *
97       * @param valueNumber value number of the lock object
98       * @param lockCount   the lock count for the lock
99       */
100     public void setLockCount(int valueNumber, int lockCount) {
101         int index = findIndex(valueNumber);
102         if (index < 0) {
103             addEntry(index, valueNumber, lockCount);
104         } else {
105             array[index + 1] = lockCount;
106         }
107     }
108 
109     /**
110      * Set the default lock count to return for nonexistent lock entries.
111      *
112      * @param defaultLockCount the default lock count value
113      */
114     public void setDefaultLockCount(int defaultLockCount) {
115         this.defaultLockCount = defaultLockCount;
116     }
117 
118     /**
119      * Get the number of distinct lock values with positive lock counts.
120      */
121     public int getNumLockedObjects() {
122         int result = 0;
123         for (int i = 0; i < array.length; i += 2) {
124             if (array[i] == INVALID)
125                 break;
126             if (array[i + 1] > 0)
127                 ++result;
128         }
129         return result;
130     }
131 
132     /**
133      * Make this LockSet the same as the given one.
134      *
135      * @param other the LockSet to copy
136      */
137     public void copyFrom(LockSet other) {
138         if (other.array.length != array.length) {
139             array = new int[other.array.length];
140         }
141         System.arraycopy(other.array, 0, array, 0, array.length);
142         this.defaultLockCount = other.defaultLockCount;
143     }
144 
145     /**
146      * Clear all entries out of this LockSet.
147      */
148     public void clear() {
149         for (int i = 0; i < array.length; i += 2) {
150             array[i] = INVALID;
151         }
152     }
153 
154     /**
155      * Meet this LockSet with another LockSet,
156      * storing the result in this object.
157      *
158      * @param other the other LockSet
159      */
160     public void meetWith(LockSet other) {
161         for (int i = 0; i < array.length; i += 2) {
162             int valueNumber = array[i];
163             if (valueNumber < 0)
164                 break;
165 
166             int mine = array[i + 1];
167             int his = other.getLockCount(valueNumber);
168             array[i + 1] = mergeValues(mine, his);
169         }
170 
171         for (int i = 0; i < other.array.length; i += 2) {
172             int valueNumber = other.array[i];
173             if (valueNumber < 0)
174                 break;
175 
176             int mine = getLockCount(valueNumber);
177             int his = other.array[i + 1];
178             setLockCount(valueNumber, mergeValues(mine, his));
179         }
180 
181         setDefaultLockCount(0);
182     }
183 
184     /**
185      * Return whether or not this LockSet is the same as the one given.
186      *
187      * @param other the other LockSet
188      */
189     public boolean sameAs(LockSet other) {
190         return this.identicalSubset(other) && other.identicalSubset(this);
191     }
192 
193     /**
194      * Determine whether or not this lock set contains any
195      * locked values which are method return values.
196      *
197      * @param factory the ValueNumberFactory that produced the lock values
198      */
199     public boolean containsReturnValue(ValueNumberFactory factory) {
200         for (int i = 0; i < array.length; i += 2) {
201             int valueNumber = array[i];
202             if (valueNumber < 0)
203                 break;
204             int lockCount = array[i + 1];
205             if (lockCount > 0 && factory.forNumber(valueNumber).hasFlag(ValueNumber.RETURN_VALUE))
206                 return true;
207         }
208         return false;
209     }
210 
211     /**
212      * Destructively intersect this lock set with another.
213      * Note that this is <em>not</em> a dataflow merge:
214      * we are interested in finding out which locks are held
215      * in both sets, not in the exact lock counts.
216      *
217      * @param other the other LockSet
218      */
219     public void intersectWith(LockSet other) {
220         for (int i = 0; i < array.length; i += 2) {
221             int valueNumber = array[i];
222             if (valueNumber < 0)
223                 break;
224             int myLockCount = array[i + 1];
225             if (myLockCount <= 0)
226                 continue;
227             int otherLockCount = other.getLockCount(valueNumber);
228             if (otherLockCount <= 0) {
229                 /* This set holds the lock, but the other one doesn't. */
230                 array[i + 1] = 0;
231             }
232         }
233     }
234 
235     /**
236      * Return whether or not this lock set is empty,
237      * meaning that no locks have a positive lock count.
238      *
239      * @return true if no locks are held, false if at least
240      *         one lock is held
241      */
242     public boolean isEmpty() {
243         for (int i = 0; i < array.length; i += 2) {
244             int valueNumber = array[i];
245             if (valueNumber < 0)
246                 return true;
247             int myLockCount = array[i + 1];
248             if (myLockCount > 0)
249                 return false;
250         }
251         return true;
252     }
253 
254     private boolean identicalSubset(LockSet other) {
255         for (int i = 0; i < array.length; i += 2) {
256             int valueNumber = array[i];
257             if (valueNumber < 0)
258                 break;
259             int mine = array[i + 1];
260             int his = other.getLockCount(valueNumber);
261             if (mine != his)
262                 return false;
263             //System.out.println("For value " + valueNumber + ", " + mine + "==" + his);
264         }
265         return true;
266     }
267 
268     private static int mergeValues(int a, int b) {
269         if (a == TOP)
270             return b;
271         else if (b == TOP)
272             return a;
273         else if (a == BOTTOM || b == BOTTOM)
274             return BOTTOM;
275         else if (a == b)
276             return a;
277         else
278             return BOTTOM;
279     }
280 
281     private int findIndex(int valueNumber) {
282         for (int i = 0; i < array.length; i += 2) {
283             int value = array[i];
284             if (value < 0)
285                 return -(i + 1); // didn't find requested valueNumber - return first available slot
286             else if (value == valueNumber)
287                 return i; // found requested valueNumber
288         }
289         return -(array.length + 1); // didn't find requested valueNumber, and array is full
290     }
291 
292     private void addEntry(int index, int valueNumber, int lockCount) {
293         index = -(index + 1);
294         int origCapacity = array.length;
295         if (index == origCapacity) {
296             // Grow the array.
297 
298             // Allocate twice the space of the old array
299             int[] data = new int[origCapacity * 2];
300 
301             // Copy existing data
302             System.arraycopy(array, 0, data, 0, origCapacity);
303 
304             // Clear entries in the new part of the array
305             // that won't be used to store the entry that's
306             // being added
307             for (int i = index + 2; i < data.length; i += 2) {
308                 data[i] = INVALID;
309             }
310 
311             // Now we're ready to use the new array
312             array = data;
313         }
314 
315         array[index] = valueNumber;
316         array[index + 1] = lockCount;
317     }
318 
319     @Override  
320          public String   toString() {
321         StringBuffer   buf = new StringBuffer  ();
322         buf.append('[');
323         boolean first = true;
324         if (defaultLockCount == 0) {
325             buf.append("default=0");
326             first = false;
327         }
328         for (int i = 0; i < array.length; i += 2) {
329             int valueNumber = array[i];
330             if (valueNumber < 0)
331                 continue;
332             int lockCount = array[i + 1];
333             if (lockCount == 0)
334                 continue;
335             if (first)
336                 first = false;
337             else
338                 buf.append(',');
339             buf.append(valueNumber);
340             buf.append('=');
341             if (lockCount == TOP)
342                 buf.append("TOP");
343             else if (lockCount == BOTTOM)
344                 buf.append("BOTTOM");
345             else
346                 buf.append(lockCount);
347         }
348         buf.append(']');
349         return buf.toString();
350     }
351 
352     /**
353      * @param frame
354      * @return a set of the locked value numbers
355      */
356     public Collection  <ValueNumber> getLockedValueNumbers(ValueNumberFrame frame) {
357         if (frame == null) throw new IllegalArgumentException  ("Null Frame");
358         HashSet  <ValueNumber> result = new HashSet  <ValueNumber>();
359         for(ValueNumber v : frame.allSlots())
360             if (v != null && getLockCount(v.getNumber()) > 0)
361                 result.add(v);
362         return result;
363     }
364 
365     
366 /*
367     public static void main(String[] argv) {
368         LockSet l = new LockSet();
369         l.setLockCount(0, 1);
370         System.out.println(l);
371         l.setLockCount(0, 2);
372         System.out.println(l);
373         l.setLockCount(15, 1);
374         System.out.println(l);
375         LockSet ll = new LockSet();
376         ll.setLockCount(0, 1);
377         ll.setLockCount(15, 1);
378         ll.setLockCount(69, 3);
379         LockSet tmp = new LockSet();
380         tmp.copyFrom(ll);
381         ll.meetWith(l);
382         System.out.println(l + " merge with " + tmp + " ==> " + ll);
383 
384         LockSet dup = new LockSet();
385         dup.copyFrom(ll);
386         System.out.println(ll + " == " + dup + " ==> " + ll.sameAs(dup));
387         System.out.println(ll + " == " + l + " ==> " + ll.sameAs(l));
388     }
389 */
390 }
391 
392 // vim:ts=4
393
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags