Java > Open Source Codes > com > google > inject > util > ReferenceMap


1 /**
2  * Copyright (C) 2006 Google Inc.
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 com.google.inject.util;
18
19 import static com.google.inject.util.ReferenceType.STRONG;
20
21 import java.io.IOException ;
22 import java.io.ObjectInputStream ;
23 import java.io.ObjectOutputStream ;
24 import java.io.Serializable ;
25 import java.lang.ref.Reference ;
26 import java.util.ArrayList ;
27 import java.util.Collection ;
28 import java.util.Collections ;
29 import java.util.HashSet ;
30 import java.util.Map ;
31 import java.util.Set ;
32 import java.util.concurrent.ConcurrentHashMap ;
33 import java.util.concurrent.ConcurrentMap ;
34
35 /**
36  * Concurrent hash map that wraps keys and/or values in soft or weak
37  * references. Does not support null keys or values. Uses identity equality
38  * for weak and soft keys.
39  *
40  * <p>The concurrent semantics of {@link ConcurrentHashMap} combined with the
41  * fact that the garbage collector can asynchronously reclaim and clean up
42  * after keys and values at any time can lead to some racy semantics. For
43  * example, {@link #size()} returns an upper bound on the size, i.e. the actual
44  * size may be smaller in cases where the key or value has been reclaimed but
45  * the map entry has not been cleaned up yet.
46  *
47  * <p>Another example: If {@link #get(Object)} cannot find an existing entry
48  * for a key, it will try to create one. This operation is not atomic. One
49  * thread could {@link #put(Object, Object)} a value between the time another
50  * thread running {@code get()} checks for an entry and decides to create one.
51  * In this case, the newly created value will replace the put value in the
52  * map. Also, two threads running {@code get()} concurrently can potentially
53  * create duplicate values for a given key.
54  *
55  * <p>In other words, this class is great for caching but not atomicity.
56  *
57  * @author crazybob@google.com (Bob Lee)
58  */
59 @SuppressWarnings ("unchecked")
60 public class ReferenceMap<K, V> implements Map <K, V>, Serializable {
61
62   private static final long serialVersionUID = 0;
63
64   transient ConcurrentMap <Object , Object > delegate;
65
66   final ReferenceType keyReferenceType;
67   final ReferenceType valueReferenceType;
68
69   /**
70    * Concurrent hash map that wraps keys and/or values based on specified
71    * reference types.
72    *
73    * @param keyReferenceType key reference type
74    * @param valueReferenceType value reference type
75    */
76   public ReferenceMap(ReferenceType keyReferenceType,
77       ReferenceType valueReferenceType) {
78     ensureNotNull(keyReferenceType, valueReferenceType);
79
80     if (keyReferenceType == ReferenceType.PHANTOM
81         || valueReferenceType == ReferenceType.PHANTOM) {
82       throw new IllegalArgumentException ("Phantom references not supported.");
83     }
84
85     this.delegate = new ConcurrentHashMap <Object , Object >();
86     this.keyReferenceType = keyReferenceType;
87     this.valueReferenceType = valueReferenceType;
88   }
89
90   V internalGet(K key) {
91     Object valueReference = delegate.get(makeKeyReferenceAware(key));
92     return valueReference == null
93         ? null
94         : (V) dereferenceValue(valueReference);
95   }
96
97   public V get(final Object key) {
98     ensureNotNull(key);
99     return internalGet((K) key);
100   }
101
102   V execute(Strategy strategy, K key, V value) {
103     ensureNotNull(key, value);
104     Object keyReference = referenceKey(key);
105     Object valueReference = strategy.execute(
106       this,
107       keyReference,
108       referenceValue(keyReference, value)
109     );
110     return valueReference == null ? null
111         : (V) dereferenceValue(valueReference);
112   }
113
114   public V put(K key, V value) {
115     return execute(putStrategy(), key, value);
116   }
117
118   public V remove(Object key) {
119     ensureNotNull(key);
120     Object referenceAwareKey = makeKeyReferenceAware(key);
121     Object valueReference = delegate.remove(referenceAwareKey);
122     return valueReference == null ? null
123         : (V) dereferenceValue(valueReference);
124   }
125
126   public int size() {
127     return delegate.size();
128   }
129
130   public boolean isEmpty() {
131     return delegate.isEmpty();
132   }
133
134   public boolean containsKey(Object key) {
135     ensureNotNull(key);
136     Object referenceAwareKey = makeKeyReferenceAware(key);
137     return delegate.containsKey(referenceAwareKey);
138   }
139
140   public boolean containsValue(Object value) {
141     ensureNotNull(value);
142     for (Object valueReference : delegate.values()) {
143       if (value.equals(dereferenceValue(valueReference))) {
144         return true;
145       }
146     }
147     return false;
148   }
149
150   public void putAll(Map <? extends K, ? extends V> t) {
151     for (Map.Entry <? extends K, ? extends V> entry : t.entrySet()) {
152       put(entry.getKey(), entry.getValue());
153     }
154   }
155
156   public void clear() {
157     delegate.clear();
158   }
159
160   /**
161    * Returns an unmodifiable set view of the keys in this map. As this method
162    * creates a defensive copy, the performance is O(n).
163    */
164   public Set <K> keySet() {
165     return Collections.unmodifiableSet(
166         dereferenceKeySet(delegate.keySet()));
167   }
168
169   /**
170    * Returns an unmodifiable set view of the values in this map. As this
171    * method creates a defensive copy, the performance is O(n).
172    */
173   public Collection <V> values() {
174     return Collections.unmodifiableCollection(
175         dereferenceValues(delegate.values()));
176   }
177
178   public V putIfAbsent(K key, V value) {
179     // TODO (crazybob) if the value has been gc'ed but the entry hasn't been
180 // cleaned up yet, this put will fail.
181 return execute(putIfAbsentStrategy(), key, value);
182   }
183
184   public boolean remove(Object key, Object value) {
185     ensureNotNull(key, value);
186     Object referenceAwareKey = makeKeyReferenceAware(key);
187     Object referenceAwareValue = makeValueReferenceAware(value);
188     return delegate.remove(referenceAwareKey, referenceAwareValue);
189   }
190
191   public boolean replace(K key, V oldValue, V newValue) {
192     ensureNotNull(key, oldValue, newValue);
193     Object keyReference = referenceKey(key);
194
195     Object referenceAwareOldValue = makeValueReferenceAware(oldValue);
196     return delegate.replace(
197       keyReference,
198       referenceAwareOldValue,
199       referenceValue(keyReference, newValue)
200     );
201   }
202
203   public V replace(K key, V value) {
204     // TODO (crazybob) if the value has been gc'ed but the entry hasn't been
205 // cleaned up yet, this will succeed when it probably shouldn't.
206 return execute(replaceStrategy(), key, value);
207   }
208
209   /**
210    * Returns an unmodifiable set view of the entries in this map. As this
211    * method creates a defensive copy, the performance is O(n).
212    */
213   public Set <Map.Entry <K, V>> entrySet() {
214     Set <Map.Entry <K, V>> entrySet = new HashSet <Map.Entry <K, V>>();
215     for (Map.Entry <Object , Object > entry : delegate.entrySet()) {
216       Map.Entry <K, V> dereferenced = dereferenceEntry(entry);
217       if (dereferenced != null) {
218         entrySet.add(dereferenced);
219       }
220     }
221     return Collections.unmodifiableSet(entrySet);
222   }
223
224   /**
225    * Dereferences an entry. Returns null if the key or value has been gc'ed.
226    */
227   Entry dereferenceEntry(Map.Entry <Object , Object > entry) {
228     K key = dereferenceKey(entry.getKey());
229     V value = dereferenceValue(entry.getValue());
230     return (key == null || value == null)
231         ? null
232         : new Entry(key, value);
233   }
234
235   /**
236    * Creates a reference for a key.
237    */
238   Object referenceKey(K key) {
239     switch (keyReferenceType) {
240       case STRONG: return key;
241       case SOFT: return new SoftKeyReference(key);
242       case WEAK: return new WeakKeyReference(key);
243       default: throw new AssertionError ();
244     }
245   }
246
247   /**
248    * Converts a reference to a key.
249    */
250   K dereferenceKey(Object o) {
251     return (K) dereference(keyReferenceType, o);
252   }
253
254   /**
255    * Converts a reference to a value.
256    */
257   V dereferenceValue(Object o) {
258     return (V) dereference(valueReferenceType, o);
259   }
260
261   /**
262    * Returns the refererent for reference given its reference type.
263    */
264   Object dereference(ReferenceType referenceType, Object reference) {
265     return referenceType == STRONG ? reference : ((Reference ) reference).get();
266   }
267
268   /**
269    * Creates a reference for a value.
270    */
271   Object referenceValue(Object keyReference, Object value) {
272     switch (valueReferenceType) {
273       case STRONG: return value;
274       case SOFT: return new SoftValueReference(keyReference, value);
275       case WEAK: return new WeakValueReference(keyReference, value);
276       default: throw new AssertionError ();
277     }
278   }
279
280   /**
281    * Dereferences a set of key references.
282    */
283   Set <K> dereferenceKeySet(Set keyReferences) {
284     return keyReferenceType == STRONG
285         ? keyReferences
286         : dereferenceCollection(keyReferenceType, keyReferences, new HashSet ());
287   }
288
289   /**
290    * Dereferences a collection of value references.
291    */
292   Collection <V> dereferenceValues(Collection valueReferences) {
293     return valueReferenceType == STRONG
294         ? valueReferences
295         : dereferenceCollection(valueReferenceType, valueReferences,
296             new ArrayList (valueReferences.size()));
297   }
298
299   /**
300    * Wraps key so it can be compared to a referenced key for equality.
301    */
302   Object makeKeyReferenceAware(Object o) {
303     return keyReferenceType == STRONG ? o : new KeyReferenceAwareWrapper(o);
304   }
305
306   /**
307    * Wraps value so it can be compared to a referenced value for equality.
308    */
309   Object makeValueReferenceAware(Object o) {
310     return valueReferenceType == STRONG ? o : new ReferenceAwareWrapper(o);
311   }
312
313   /**
314    * Dereferences elements in {@code in} using
315    * {@code referenceType} and puts them in {@code out}. Returns
316    * {@code out}.
317    */
318   <T extends Collection <Object >> T dereferenceCollection(
319       ReferenceType referenceType, T in, T out) {
320     for (Object reference : in) {
321       out.add(dereference(referenceType, reference));
322     }
323     return out;
324   }
325
326   /**
327    * Marker interface to differentiate external and internal references.
328    */
329   interface InternalReference {}
330
331   static int keyHashCode(Object key) {
332     return System.identityHashCode(key);
333   }
334
335   /**
336    * Tests weak and soft references for identity equality. Compares references
337    * to other references and wrappers. If o is a reference, this returns true
338    * if r == o or if r and o reference the same non null object. If o is a
339    * wrapper, this returns true if r's referent is identical to the wrapped
340    * object.
341    */
342   static boolean referenceEquals(Reference r, Object o) {
343     // compare reference to reference.
344 if (o instanceof InternalReference) {
345       // are they the same reference? used in cleanup.
346 if (o == r) {
347         return true;
348       }
349
350       // do they reference identical values? used in conditional puts.
351 Object referent = ((Reference ) o).get();
352       return referent != null && referent == r.get();
353     }
354
355     // is the wrapped object identical to the referent? used in lookups.
356 return ((ReferenceAwareWrapper) o).unwrap() == r.get();
357   }
358
359   /**
360    * Big hack. Used to compare keys and values to referenced keys and values
361    * without creating more references.
362    */
363   static class ReferenceAwareWrapper {
364
365     final Object wrapped;
366
367     ReferenceAwareWrapper(Object wrapped) {
368       this.wrapped = wrapped;
369     }
370
371     Object unwrap() {
372       return wrapped;
373     }
374
375     public int hashCode() {
376       return wrapped.hashCode();
377     }
378
379     public boolean equals(Object obj) {
380       // defer to reference's equals() logic.
381 return obj.equals(this);
382     }
383   }
384
385   /**
386    * Used for keys. Overrides hash code to use identity hash code.
387    */
388   static class KeyReferenceAwareWrapper extends ReferenceAwareWrapper {
389
390     public KeyReferenceAwareWrapper(Object wrapped) {
391       super(wrapped);
392     }
393
394     public int hashCode() {
395       return System.identityHashCode(wrapped);
396     }
397   }
398
399   class SoftKeyReference extends FinalizableSoftReference<Object >
400       implements InternalReference {
401
402     final int hashCode;
403
404     public SoftKeyReference(Object key) {
405       super(key);
406       this.hashCode = keyHashCode(key);
407     }
408
409     public void finalizeReferent() {
410       delegate.remove(this);
411     }
412
413     @Override public int hashCode() {
414       return this.hashCode;
415     }
416
417     @Override public boolean equals(Object o) {
418       return referenceEquals(this, o);
419     }
420   }
421
422   class WeakKeyReference extends FinalizableWeakReference<Object >
423       implements InternalReference {
424
425     final int hashCode;
426
427     public WeakKeyReference(Object key) {
428       super(key);
429       this.hashCode = keyHashCode(key);
430     }
431
432     public void finalizeReferent() {
433       delegate.remove(this);
434     }
435
436     @Override public int hashCode() {
437       return this.hashCode;
438     }
439
440     @Override public boolean equals(Object o) {
441       return referenceEquals(this, o);
442     }
443   }
444
445   class SoftValueReference extends FinalizableSoftReference<Object >
446       implements InternalReference {
447
448     final Object keyReference;
449
450     public SoftValueReference(Object keyReference, Object value) {
451       super(value);
452       this.keyReference = keyReference;
453     }
454
455     public void finalizeReferent() {
456       delegate.remove(keyReference, this);
457     }
458
459     @Override public boolean equals(Object obj) {
460       return referenceEquals(this, obj);
461     }
462   }
463
464   class WeakValueReference extends FinalizableWeakReference<Object >
465       implements InternalReference {
466
467     final Object keyReference;
468
469     public WeakValueReference(Object keyReference, Object value) {
470       super(value);
471       this.keyReference = keyReference;
472     }
473
474     public void finalizeReferent() {
475       delegate.remove(keyReference, this);
476     }
477
478     @Override public boolean equals(Object obj) {
479       return referenceEquals(this, obj);
480     }
481   }
482
483   protected interface Strategy {
484     public Object execute(ReferenceMap map, Object keyReference,
485         Object valueReference);
486   }
487
488   protected Strategy putStrategy() {
489     return PutStrategy.PUT;
490   }
491
492   protected Strategy putIfAbsentStrategy() {
493     return PutStrategy.PUT_IF_ABSENT;
494   }
495
496   protected Strategy replaceStrategy() {
497     return PutStrategy.REPLACE;
498   }
499
500   protected enum PutStrategy implements Strategy {
501     PUT {
502       public Object execute(ReferenceMap map, Object keyReference,
503           Object valueReference) {
504         return map.delegate.put(keyReference, valueReference);
505       }
506     },
507
508     REPLACE {
509       public Object execute(ReferenceMap map, Object keyReference,
510           Object valueReference) {
511         return map.delegate.replace(keyReference, valueReference);
512       }
513     },
514
515     PUT_IF_ABSENT {
516       public Object execute(ReferenceMap map, Object keyReference,
517           Object valueReference) {
518         return map.delegate.putIfAbsent(keyReference, valueReference);
519       }
520     };
521   };
522
523   private static PutStrategy defaultPutStrategy;
524
525   protected PutStrategy getPutStrategy() {
526     return defaultPutStrategy;
527   }
528
529
530   class Entry implements Map.Entry <K, V> {
531
532     final K key;
533     final V value;
534
535     public Entry(K key, V value) {
536       this.key = key;
537       this.value = value;
538     }
539
540     public K getKey() {
541       return this.key;
542     }
543
544     public V getValue() {
545       return this.value;
546     }
547
548     public V setValue(V value) {
549       return put(key, value);
550     }
551
552     public int hashCode() {
553       return key.hashCode() * 31 + value.hashCode();
554     }
555
556     public boolean equals(Object o) {
557       if (!(o instanceof ReferenceMap.Entry)) {
558         return false;
559       }
560
561       Entry entry = (Entry) o;
562       return key.equals(entry.key) && value.equals(entry.value);
563     }
564
565     public String toString() {
566       return key + "=" + value;
567     }
568   }
569
570   static void ensureNotNull(Object o) {
571     if (o == null) {
572       throw new NullPointerException ();
573     }
574   }
575
576   static void ensureNotNull(Object ... array) {
577     for (int i = 0; i < array.length; i++) {
578       if (array[i] == null) {
579         throw new NullPointerException ("Argument #" + i + " is null.");
580       }
581     }
582   }
583
584   private void writeObject(ObjectOutputStream out) throws IOException {
585     out.defaultWriteObject();
586     out.writeInt(size());
587     for (Map.Entry <Object , Object > entry : delegate.entrySet()) {
588       Object key = dereferenceKey(entry.getKey());
589       Object value = dereferenceValue(entry.getValue());
590
591       // don't persist gc'ed entries.
592 if (key != null && value != null) {
593         out.writeObject(key);
594         out.writeObject(value);
595       }
596     }
597     out.writeObject(null);
598   }
599
600   private void readObject(ObjectInputStream in) throws IOException ,
601       ClassNotFoundException {
602     in.defaultReadObject();
603     int size = in.readInt();
604     this.delegate = new ConcurrentHashMap <Object , Object >(size);
605     while (true) {
606       K key = (K) in.readObject();
607       if (key == null) {
608         break;
609       }
610       V value = (V) in.readObject();
611       put(key, value);
612     }
613   }
614
615 }
616

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags