View Javadoc

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