View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    * 
9    *     http://www.apache.org/licenses/LICENSE-2.0
10   * 
11   * Unless required by applicable law or agreed to in writing, software 
12   * distributed under the License is distributed on an "AS IS" BASIS, 
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
14   * See the License for the specific language governing permissions and 
15   * limitations under the License.
16   */
17  
18  package org.apache.jdo.util;
19  
20  import java.lang.ref.ReferenceQueue;
21  import java.lang.ref.WeakReference;
22  
23  import java.util.AbstractCollection;
24  import java.util.AbstractSet;
25  import java.util.Collection;
26  import java.util.HashMap;
27  import java.util.Iterator;
28  import java.util.Map;
29  import java.util.NoSuchElementException;
30  import java.util.Set;
31  
32  /**
33   * A WeakValueHashMap is implemented as a HashMap that maps keys to
34   * WeakValues.  Because we don't have access to the innards of the
35   * HashMap, we have to wrap/unwrap value objects with WeakValues on
36   * every operation.  Fortunately WeakValues are small, short-lived
37   * objects, so the added allocation overhead is tolerable. This
38   * implementaton directly extends java.util.HashMap.
39   *
40   * @author	Markus Fuchs
41   * @see		java.util.HashMap
42   * @see         java.lang.ref.WeakReference
43   */
44  
45  public class WeakValueHashMap extends HashMap {
46  
47      /* Reference queue for cleared WeakValues */
48      private ReferenceQueue queue = new ReferenceQueue();
49  
50      /**
51       * Returns the number of key-value mappings in this map.<p>
52       * @return the number of key-value mappings in this map.
53       */
54      public int size() {
55          // delegate to entrySet, as super.size() also counts WeakValues
56          return entrySet().size();
57      }
58  
59      /**
60       * Returns <tt>true</tt> if this map contains no key-value mappings.<p>
61       * @return <tt>true</tt> if this map contains no key-value mappings.
62       */
63      public boolean isEmpty() {
64          return size() == 0;
65      }
66  
67      /**
68       * Returns <tt>true</tt> if this map contains a mapping for the specified
69       * key.<p>
70       * @param key key whose presence in this map is to be tested
71       * @return <tt>true</tt> if this map contains a mapping for the specified
72       * key.
73       */
74      public boolean containsKey(Object key) {
75          // need to clean up gc'ed values before invoking super method
76          processQueue();
77          return super.containsKey(key);
78      }
79  
80     /**
81       * Returns <tt>true</tt> if this map maps one or more keys to the
82       * specified value.<p>
83       * @param value value whose presence in this map is to be tested
84       * @return <tt>true</tt> if this map maps one or more keys to this value.
85       */
86      public boolean containsValue(Object value) {
87          return super.containsValue(WeakValue.create(value));
88      }
89  
90      /**
91       * Gets the value for the given key.<p>
92       * @param key key whose associated value, if any, is to be returned
93       * @return the value to which this map maps the specified key.
94       */
95      public Object get(Object key) {
96          // We don't need to remove garbage collected values here;
97          // if they are garbage collected, the get() method returns null;
98          // the next put() call with the same key removes the old value
99          // automatically so that it can be completely garbage collected
100         return getReferenceObject((WeakReference) super.get(key));
101     }
102 
103     /**
104      * Puts a new (key,value) into the map.<p>
105      * @param key key with which the specified value is to be associated.
106      * @param value value to be associated with the specified key.
107      * @return previous value associated with specified key, or null
108      * if there was no mapping for key or the value has been garbage
109      * collected by the garbage collector.
110      */
111     public Object put(Object key, Object value) {
112         // If the map already contains an equivalent key, the new key
113         // of a (key, value) pair is NOT stored in the map but the new
114         // value only. But as the key is strongly referenced by the
115         // map, it can not be removed from the garbage collector, even
116         // if the key becomes weakly reachable due to the old
117         // value. So, it isn't necessary to remove all garbage
118         // collected values with their keys from the map before the
119         // new entry is made. We only clean up here to distribute
120         // clean up calls on different operations.
121         processQueue();
122 
123         WeakValue oldValue = 
124             (WeakValue)super.put(key, WeakValue.create(key, value, queue));
125         return getReferenceObject(oldValue);
126     }
127 
128     /**
129      * Removes key and value for the given key.<p>
130      * @param key key whose mapping is to be removed from the map.
131      * @return previous value associated with specified key, or null
132      * if there was no mapping for key or the value has been garbage
133      * collected by the garbage collector.
134      */
135     public Object remove(Object key) {
136         return getReferenceObject((WeakReference) super.remove(key));
137     }
138 
139     /**
140      * A convenience method to return the object held by the
141      * weak reference or <code>null</code> if it does not exist.
142      */
143     private final Object getReferenceObject(WeakReference ref) {
144         return (ref == null) ? null : ref.get();
145     }
146 
147     /**
148      * Removes all garbage collected values with their keys from the map.
149      * Since we don't know how much the ReferenceQueue.poll() operation
150      * costs, we should not call it every map operation.
151      */
152     private void processQueue() {
153         WeakValue wv = null;
154 
155         while ((wv = (WeakValue) this.queue.poll()) != null) {
156             // "super" is not really necessary but use it
157             // to be on the safe side
158             super.remove(wv.key);
159         }
160     }
161 
162     /* -- Helper classes -- */
163 
164     /**
165      * We need this special class to keep the backward reference from
166      * the value to the key, so that we are able to remove the key if
167      * the value is garbage collected.
168      */
169     private static class WeakValue extends WeakReference {
170         /**
171          * It's the same as the key in the map. We need the key to remove
172          * the value if it is garbage collected.
173          */
174         private Object key;
175 
176         private WeakValue(Object value) {
177             super(value);
178         }
179 
180         /**
181          * Creates a new weak reference without adding it to a
182          * ReferenceQueue.
183          */
184 	private static WeakValue create(Object value) {
185 	    if (value == null) return null;
186 	    else return new WeakValue(value);
187         }
188 
189         private WeakValue(Object key, Object value, ReferenceQueue queue) {
190             super(value, queue);
191             this.key = key;
192         }
193 
194         /**
195          * Creates a new weak reference and adds it to the given queue.
196          */
197         private static WeakValue create(Object key, Object value, 
198                                         ReferenceQueue queue) {
199 	    if (value == null) return null;
200 	    else return new WeakValue(key, value, queue);
201         }
202 
203         /**
204          * A WeakValue is equal to another WeakValue iff they both refer
205          * to objects that are, in turn, equal according to their own
206          * equals methods.
207          */
208         public boolean equals(Object obj) {
209             if (this == obj)
210                 return true;
211 
212             if (!(obj instanceof WeakValue))
213                 return false;
214 
215             Object ref1 = this.get();
216             Object ref2 = ((WeakValue) obj).get();
217 
218             if (ref1 == ref2)
219                 return true;
220 
221             if ((ref1 == null) || (ref2 == null))
222                 return false;
223 
224             return ref1.equals(ref2);
225         }
226 
227         /**
228          *
229          */
230         public int hashCode() {
231             Object ref = this.get();
232 
233             return (ref == null) ? 0 : ref.hashCode();
234         }
235     }
236 
237     /** 
238      * Internal class for entries. This class wraps/unwraps the
239      * values of the Entry objects returned from the underlying map.
240      */
241     private class Entry implements Map.Entry {
242         private Map.Entry ent;
243         private Object value;	/* Strong reference to value, so that the
244 				   GC will leave it alone as long as this
245 				   Entry exists */
246 
247         Entry(Map.Entry ent, Object value) {
248             this.ent = ent;
249             this.value = value;
250         }
251 
252         public Object getKey() {
253             return ent.getKey();
254         }
255 
256         public Object getValue() {
257             return value;
258         }
259 
260         public Object setValue(Object value) {
261             // This call changes the map. Please see the comment on 
262             // the put method for the correctness remark.
263             Object oldValue = this.value;
264             this.value = value;
265             ent.setValue(WeakValue.create(getKey(), value, queue));
266             return oldValue;
267         }
268 
269         private boolean valEquals(Object o1, Object o2) {
270             return (o1 == null) ? (o2 == null) : o1.equals(o2);
271         }
272 
273         public boolean equals(Object o) {
274             if (!(o instanceof Map.Entry)) return false;
275             Map.Entry e = (Map.Entry) o;
276             return (valEquals(ent.getKey(), e.getKey())
277                     && valEquals(value, e.getValue()));
278         }
279 
280         public int hashCode() {
281             Object k;
282             return ((((k = ent.getKey()) == null) ? 0 : k.hashCode())
283                     ^ ((value == null) ? 0 : value.hashCode()));
284         }
285 
286     }
287 
288     /**
289      * Internal class for entry sets to unwrap/wrap WeakValues stored
290      * in the map.
291      */
292     private class EntrySet extends AbstractSet {
293 
294         public Iterator iterator() {
295             // remove garbage collected elements
296             processQueue();
297 
298             return new Iterator() {
299                 Iterator hashIterator = hashEntrySet.iterator();
300                 Entry next = null;
301 
302                 public boolean hasNext() {
303                     if (hashIterator.hasNext()) {
304                         // since we removed garbage collected elements,
305                         // we can simply return the next entry.
306                         Map.Entry ent = (Map.Entry) hashIterator.next();
307                         WeakValue wv = (WeakValue) ent.getValue();
308                         Object v = (wv == null) ? null : wv.get();
309                         next = new Entry(ent, v);
310                         return true;
311                     }
312                     return false;
313                 }
314 
315                 public Object next() {
316                     if ((next == null) && !hasNext())
317                         throw new NoSuchElementException();
318                     Entry e = next;
319                     next = null;
320                     return e;
321                 }
322 
323                 public void remove() {
324                     hashIterator.remove();
325                 }
326 
327             };
328         }
329 
330         public boolean isEmpty() {
331             return !(iterator().hasNext());
332         }
333 
334         public int size() {
335             int j = 0;
336             for (Iterator i = iterator(); i.hasNext(); i.next()) j++;
337             return j;
338         }
339 
340         public boolean remove(Object o) {
341             if (!(o instanceof Map.Entry)) return false;
342             Map.Entry e = (Map.Entry) o;
343             Object ek = e.getKey();
344             Object ev = e.getValue();
345             Object hv = WeakValueHashMap.this.get(ek);
346             if (hv == null) {
347                 // if the map's value is null, we have to check, if the
348                 // entry's value is null and the map contains the key
349                 if ((ev == null) && WeakValueHashMap.this.containsKey(ek)) {
350                     WeakValueHashMap.this.remove(ek);
351                     return true;
352                 } else {
353                     return false;
354                 }
355                 // otherwise, simply compare the values
356             } else if (hv.equals(ev)) {
357                 WeakValueHashMap.this.remove(ek);
358                 return true;
359             }                
360                 
361             return false;
362         }
363 
364         public int hashCode() {
365             int h = 0;
366             for (Iterator i = hashEntrySet.iterator(); i.hasNext(); ) {
367                 Map.Entry ent = (Map.Entry) i.next();
368                 Object k;
369                 WeakValue wv = (WeakValue) ent.getValue();
370                 if (wv == null) continue;
371                 h += ((((k = ent.getKey()) == null) ? 0 : k.hashCode())
372                         ^ wv.hashCode());
373             }
374             return h;
375         }
376 
377     }
378 
379     // internal helper variable, because we can't access
380     // entrySet from the superclass inside the EntrySet class
381     private Set hashEntrySet = null;
382     // stores the EntrySet instance
383     private Set entrySet = null;
384 
385     /**
386      * Returns a <code>Set</code> view of the mappings in this map.<p>
387      * @return a <code>Set</code> view of the mappings in this map.
388      */
389     public Set entrySet() {
390         if (entrySet == null) {
391             hashEntrySet = super.entrySet();
392             entrySet = new EntrySet();
393         }
394         return entrySet;
395     }
396 
397     // stores the value collection
398     private transient Collection values = null;
399 
400     /**
401      * Returns a <code>Collection</code> view of the values contained
402      * in this map.<p>
403      * @return a <code>Collection</code> view of the values contained
404      * in this map.
405      */
406     public Collection values() {
407         // delegates to entrySet, because super method returns
408         // WeakValues instead of value objects
409 	if (values == null) {
410 	    values = new AbstractCollection() {
411 		public Iterator iterator() {
412 		    return new Iterator() {
413 			private Iterator i = entrySet().iterator();
414 
415 			public boolean hasNext() {
416 			    return i.hasNext();
417 			}
418 
419 			public Object next() {
420 			    return ((Entry)i.next()).getValue();
421 			}
422 
423 			public void remove() {
424 			    i.remove();
425 			}
426                     };
427                 }
428 
429 		public int size() {
430 		    return WeakValueHashMap.this.size();
431 		}
432 
433 		public boolean contains(Object v) {
434 		    return WeakValueHashMap.this.containsValue(v);
435 		}
436 	    };
437 	}
438 	return values;
439     }
440 
441 }