WeakValueHashMap


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