001: /**
002: * Copyright (C) 2006 Google Inc.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */package com.google.inject.util;
016:
017: import static com.google.inject.util.ReferenceType.STRONG;
018:
019: import java.io.IOException;
020: import java.io.ObjectInputStream;
021: import java.io.ObjectOutputStream;
022: import java.io.Serializable;
023: import java.lang.ref.Reference;
024: import java.util.ArrayList;
025: import java.util.Collection;
026: import java.util.Collections;
027: import java.util.HashSet;
028: import java.util.Map;
029: import java.util.Set;
030: import java.util.concurrent.ConcurrentHashMap;
031: import java.util.concurrent.ConcurrentMap;
032:
033: /**
034: * Concurrent hash map that wraps keys and/or values in soft or weak
035: * references. Does not support null keys or values. Uses identity equality
036: * for weak and soft keys.
037: *
038: * <p>The concurrent semantics of {@link ConcurrentHashMap} combined with the
039: * fact that the garbage collector can asynchronously reclaim and clean up
040: * after keys and values at any time can lead to some racy semantics. For
041: * example, {@link #size()} returns an upper bound on the size, i.e. the actual
042: * size may be smaller in cases where the key or value has been reclaimed but
043: * the map entry has not been cleaned up yet.
044: *
045: * <p>Another example: If {@link #get(Object)} cannot find an existing entry
046: * for a key, it will try to create one. This operation is not atomic. One
047: * thread could {@link #put(Object, Object)} a value between the time another
048: * thread running {@code get()} checks for an entry and decides to create one.
049: * In this case, the newly created value will replace the put value in the
050: * map. Also, two threads running {@code get()} concurrently can potentially
051: * create duplicate values for a given key.
052: *
053: * <p>In other words, this class is great for caching but not atomicity.
054: *
055: * @author crazybob@google.com (Bob Lee)
056: */
057: @SuppressWarnings("unchecked")
058: public class ReferenceMap<K, V> implements Map<K, V>, Serializable {
059:
060: private static final long serialVersionUID = 0;
061:
062: transient ConcurrentMap<Object, Object> delegate;
063:
064: final ReferenceType keyReferenceType;
065: final ReferenceType valueReferenceType;
066:
067: /**
068: * Concurrent hash map that wraps keys and/or values based on specified
069: * reference types.
070: *
071: * @param keyReferenceType key reference type
072: * @param valueReferenceType value reference type
073: */
074: public ReferenceMap(ReferenceType keyReferenceType,
075: ReferenceType valueReferenceType) {
076: ensureNotNull(keyReferenceType, valueReferenceType);
077:
078: if (keyReferenceType == ReferenceType.PHANTOM
079: || valueReferenceType == ReferenceType.PHANTOM) {
080: throw new IllegalArgumentException(
081: "Phantom references not supported.");
082: }
083:
084: this .delegate = new ConcurrentHashMap<Object, Object>();
085: this .keyReferenceType = keyReferenceType;
086: this .valueReferenceType = valueReferenceType;
087: }
088:
089: V internalGet(K key) {
090: Object valueReference = delegate
091: .get(makeKeyReferenceAware(key));
092: return valueReference == null ? null
093: : (V) dereferenceValue(valueReference);
094: }
095:
096: public V get(final Object key) {
097: ensureNotNull(key);
098: return internalGet((K) key);
099: }
100:
101: V execute(Strategy strategy, K key, V value) {
102: ensureNotNull(key, value);
103: Object keyReference = referenceKey(key);
104: Object valueReference = strategy.execute(this , keyReference,
105: referenceValue(keyReference, value));
106: return valueReference == null ? null
107: : (V) dereferenceValue(valueReference);
108: }
109:
110: public V put(K key, V value) {
111: return execute(putStrategy(), key, value);
112: }
113:
114: public V remove(Object key) {
115: ensureNotNull(key);
116: Object referenceAwareKey = makeKeyReferenceAware(key);
117: Object valueReference = delegate.remove(referenceAwareKey);
118: return valueReference == null ? null
119: : (V) dereferenceValue(valueReference);
120: }
121:
122: public int size() {
123: return delegate.size();
124: }
125:
126: public boolean isEmpty() {
127: return delegate.isEmpty();
128: }
129:
130: public boolean containsKey(Object key) {
131: ensureNotNull(key);
132: Object referenceAwareKey = makeKeyReferenceAware(key);
133: return delegate.containsKey(referenceAwareKey);
134: }
135:
136: public boolean containsValue(Object value) {
137: ensureNotNull(value);
138: for (Object valueReference : delegate.values()) {
139: if (value.equals(dereferenceValue(valueReference))) {
140: return true;
141: }
142: }
143: return false;
144: }
145:
146: public void putAll(Map<? extends K, ? extends V> t) {
147: for (Map.Entry<? extends K, ? extends V> entry : t.entrySet()) {
148: put(entry.getKey(), entry.getValue());
149: }
150: }
151:
152: public void clear() {
153: delegate.clear();
154: }
155:
156: /**
157: * Returns an unmodifiable set view of the keys in this map. As this method
158: * creates a defensive copy, the performance is O(n).
159: */
160: public Set<K> keySet() {
161: return Collections.unmodifiableSet(dereferenceKeySet(delegate
162: .keySet()));
163: }
164:
165: /**
166: * Returns an unmodifiable set view of the values in this map. As this
167: * method creates a defensive copy, the performance is O(n).
168: */
169: public Collection<V> values() {
170: return Collections
171: .unmodifiableCollection(dereferenceValues(delegate
172: .values()));
173: }
174:
175: public V putIfAbsent(K key, V value) {
176: // TODO (crazybob) if the value has been gc'ed but the entry hasn't been
177: // cleaned up yet, this put will fail.
178: return execute(putIfAbsentStrategy(), key, value);
179: }
180:
181: public boolean remove(Object key, Object value) {
182: ensureNotNull(key, value);
183: Object referenceAwareKey = makeKeyReferenceAware(key);
184: Object referenceAwareValue = makeValueReferenceAware(value);
185: return delegate.remove(referenceAwareKey, referenceAwareValue);
186: }
187:
188: public boolean replace(K key, V oldValue, V newValue) {
189: ensureNotNull(key, oldValue, newValue);
190: Object keyReference = referenceKey(key);
191:
192: Object referenceAwareOldValue = makeValueReferenceAware(oldValue);
193: return delegate.replace(keyReference, referenceAwareOldValue,
194: referenceValue(keyReference, newValue));
195: }
196:
197: public V replace(K key, V value) {
198: // TODO (crazybob) if the value has been gc'ed but the entry hasn't been
199: // cleaned up yet, this will succeed when it probably shouldn't.
200: return execute(replaceStrategy(), key, value);
201: }
202:
203: /**
204: * Returns an unmodifiable set view of the entries in this map. As this
205: * method creates a defensive copy, the performance is O(n).
206: */
207: public Set<Map.Entry<K, V>> entrySet() {
208: Set<Map.Entry<K, V>> entrySet = new HashSet<Map.Entry<K, V>>();
209: for (Map.Entry<Object, Object> entry : delegate.entrySet()) {
210: Map.Entry<K, V> dereferenced = dereferenceEntry(entry);
211: if (dereferenced != null) {
212: entrySet.add(dereferenced);
213: }
214: }
215: return Collections.unmodifiableSet(entrySet);
216: }
217:
218: /**
219: * Dereferences an entry. Returns null if the key or value has been gc'ed.
220: */
221: Entry dereferenceEntry(Map.Entry<Object, Object> entry) {
222: K key = dereferenceKey(entry.getKey());
223: V value = dereferenceValue(entry.getValue());
224: return (key == null || value == null) ? null : new Entry(key,
225: value);
226: }
227:
228: /**
229: * Creates a reference for a key.
230: */
231: Object referenceKey(K key) {
232: switch (keyReferenceType) {
233: case STRONG:
234: return key;
235: case SOFT:
236: return new SoftKeyReference(key);
237: case WEAK:
238: return new WeakKeyReference(key);
239: default:
240: throw new AssertionError();
241: }
242: }
243:
244: /**
245: * Converts a reference to a key.
246: */
247: K dereferenceKey(Object o) {
248: return (K) dereference(keyReferenceType, o);
249: }
250:
251: /**
252: * Converts a reference to a value.
253: */
254: V dereferenceValue(Object o) {
255: return (V) dereference(valueReferenceType, o);
256: }
257:
258: /**
259: * Returns the refererent for reference given its reference type.
260: */
261: Object dereference(ReferenceType referenceType, Object reference) {
262: return referenceType == STRONG ? reference
263: : ((Reference) reference).get();
264: }
265:
266: /**
267: * Creates a reference for a value.
268: */
269: Object referenceValue(Object keyReference, Object value) {
270: switch (valueReferenceType) {
271: case STRONG:
272: return value;
273: case SOFT:
274: return new SoftValueReference(keyReference, value);
275: case WEAK:
276: return new WeakValueReference(keyReference, value);
277: default:
278: throw new AssertionError();
279: }
280: }
281:
282: /**
283: * Dereferences a set of key references.
284: */
285: Set<K> dereferenceKeySet(Set keyReferences) {
286: return keyReferenceType == STRONG ? keyReferences
287: : dereferenceCollection(keyReferenceType,
288: keyReferences, new HashSet());
289: }
290:
291: /**
292: * Dereferences a collection of value references.
293: */
294: Collection<V> dereferenceValues(Collection valueReferences) {
295: return valueReferenceType == STRONG ? valueReferences
296: : dereferenceCollection(valueReferenceType,
297: valueReferences, new ArrayList(valueReferences
298: .size()));
299: }
300:
301: /**
302: * Wraps key so it can be compared to a referenced key for equality.
303: */
304: Object makeKeyReferenceAware(Object o) {
305: return keyReferenceType == STRONG ? o
306: : new KeyReferenceAwareWrapper(o);
307: }
308:
309: /**
310: * Wraps value so it can be compared to a referenced value for equality.
311: */
312: Object makeValueReferenceAware(Object o) {
313: return valueReferenceType == STRONG ? o
314: : new ReferenceAwareWrapper(o);
315: }
316:
317: /**
318: * Dereferences elements in {@code in} using
319: * {@code referenceType} and puts them in {@code out}. Returns
320: * {@code out}.
321: */
322: <T extends Collection<Object>> T dereferenceCollection(
323: ReferenceType referenceType, T in, T out) {
324: for (Object reference : in) {
325: out.add(dereference(referenceType, reference));
326: }
327: return out;
328: }
329:
330: /**
331: * Marker interface to differentiate external and internal references.
332: */
333: interface InternalReference {
334: }
335:
336: static int keyHashCode(Object key) {
337: return System.identityHashCode(key);
338: }
339:
340: /**
341: * Tests weak and soft references for identity equality. Compares references
342: * to other references and wrappers. If o is a reference, this returns true
343: * if r == o or if r and o reference the same non null object. If o is a
344: * wrapper, this returns true if r's referent is identical to the wrapped
345: * object.
346: */
347: static boolean referenceEquals(Reference r, Object o) {
348: // compare reference to reference.
349: if (o instanceof InternalReference) {
350: // are they the same reference? used in cleanup.
351: if (o == r) {
352: return true;
353: }
354:
355: // do they reference identical values? used in conditional puts.
356: Object referent = ((Reference) o).get();
357: return referent != null && referent == r.get();
358: }
359:
360: // is the wrapped object identical to the referent? used in lookups.
361: return ((ReferenceAwareWrapper) o).unwrap() == r.get();
362: }
363:
364: /**
365: * Big hack. Used to compare keys and values to referenced keys and values
366: * without creating more references.
367: */
368: static class ReferenceAwareWrapper {
369:
370: final Object wrapped;
371:
372: ReferenceAwareWrapper(Object wrapped) {
373: this .wrapped = wrapped;
374: }
375:
376: Object unwrap() {
377: return wrapped;
378: }
379:
380: public int hashCode() {
381: return wrapped.hashCode();
382: }
383:
384: public boolean equals(Object obj) {
385: // defer to reference's equals() logic.
386: return obj.equals(this );
387: }
388: }
389:
390: /**
391: * Used for keys. Overrides hash code to use identity hash code.
392: */
393: static class KeyReferenceAwareWrapper extends ReferenceAwareWrapper {
394:
395: public KeyReferenceAwareWrapper(Object wrapped) {
396: super (wrapped);
397: }
398:
399: public int hashCode() {
400: return System.identityHashCode(wrapped);
401: }
402: }
403:
404: class SoftKeyReference extends FinalizableSoftReference<Object>
405: implements InternalReference {
406:
407: final int hashCode;
408:
409: public SoftKeyReference(Object key) {
410: super (key);
411: this .hashCode = keyHashCode(key);
412: }
413:
414: public void finalizeReferent() {
415: delegate.remove(this );
416: }
417:
418: @Override
419: public int hashCode() {
420: return this .hashCode;
421: }
422:
423: @Override
424: public boolean equals(Object o) {
425: return referenceEquals(this , o);
426: }
427: }
428:
429: class WeakKeyReference extends FinalizableWeakReference<Object>
430: implements InternalReference {
431:
432: final int hashCode;
433:
434: public WeakKeyReference(Object key) {
435: super (key);
436: this .hashCode = keyHashCode(key);
437: }
438:
439: public void finalizeReferent() {
440: delegate.remove(this );
441: }
442:
443: @Override
444: public int hashCode() {
445: return this .hashCode;
446: }
447:
448: @Override
449: public boolean equals(Object o) {
450: return referenceEquals(this , o);
451: }
452: }
453:
454: class SoftValueReference extends FinalizableSoftReference<Object>
455: implements InternalReference {
456:
457: final Object keyReference;
458:
459: public SoftValueReference(Object keyReference, Object value) {
460: super (value);
461: this .keyReference = keyReference;
462: }
463:
464: public void finalizeReferent() {
465: delegate.remove(keyReference, this );
466: }
467:
468: @Override
469: public boolean equals(Object obj) {
470: return referenceEquals(this , obj);
471: }
472: }
473:
474: class WeakValueReference extends FinalizableWeakReference<Object>
475: implements InternalReference {
476:
477: final Object keyReference;
478:
479: public WeakValueReference(Object keyReference, Object value) {
480: super (value);
481: this .keyReference = keyReference;
482: }
483:
484: public void finalizeReferent() {
485: delegate.remove(keyReference, this );
486: }
487:
488: @Override
489: public boolean equals(Object obj) {
490: return referenceEquals(this , obj);
491: }
492: }
493:
494: protected interface Strategy {
495: public Object execute(ReferenceMap map, Object keyReference,
496: Object valueReference);
497: }
498:
499: protected Strategy putStrategy() {
500: return PutStrategy.PUT;
501: }
502:
503: protected Strategy putIfAbsentStrategy() {
504: return PutStrategy.PUT_IF_ABSENT;
505: }
506:
507: protected Strategy replaceStrategy() {
508: return PutStrategy.REPLACE;
509: }
510:
511: protected enum PutStrategy implements Strategy {
512: PUT {
513: public Object execute(ReferenceMap map,
514: Object keyReference, Object valueReference) {
515: return map.delegate.put(keyReference, valueReference);
516: }
517: },
518:
519: REPLACE {
520: public Object execute(ReferenceMap map,
521: Object keyReference, Object valueReference) {
522: return map.delegate.replace(keyReference,
523: valueReference);
524: }
525: },
526:
527: PUT_IF_ABSENT {
528: public Object execute(ReferenceMap map,
529: Object keyReference, Object valueReference) {
530: return map.delegate.putIfAbsent(keyReference,
531: valueReference);
532: }
533: };
534: };
535:
536: private static PutStrategy defaultPutStrategy;
537:
538: protected PutStrategy getPutStrategy() {
539: return defaultPutStrategy;
540: }
541:
542: class Entry implements Map.Entry<K, V> {
543:
544: final K key;
545: final V value;
546:
547: public Entry(K key, V value) {
548: this .key = key;
549: this .value = value;
550: }
551:
552: public K getKey() {
553: return this .key;
554: }
555:
556: public V getValue() {
557: return this .value;
558: }
559:
560: public V setValue(V value) {
561: return put(key, value);
562: }
563:
564: public int hashCode() {
565: return key.hashCode() * 31 + value.hashCode();
566: }
567:
568: public boolean equals(Object o) {
569: if (!(o instanceof ReferenceMap.Entry)) {
570: return false;
571: }
572:
573: Entry entry = (Entry) o;
574: return key.equals(entry.key) && value.equals(entry.value);
575: }
576:
577: public String toString() {
578: return key + "=" + value;
579: }
580: }
581:
582: static void ensureNotNull(Object o) {
583: if (o == null) {
584: throw new NullPointerException();
585: }
586: }
587:
588: static void ensureNotNull(Object... array) {
589: for (int i = 0; i < array.length; i++) {
590: if (array[i] == null) {
591: throw new NullPointerException("Argument #" + i
592: + " is null.");
593: }
594: }
595: }
596:
597: private void writeObject(ObjectOutputStream out) throws IOException {
598: out.defaultWriteObject();
599: out.writeInt(size());
600: for (Map.Entry<Object, Object> entry : delegate.entrySet()) {
601: Object key = dereferenceKey(entry.getKey());
602: Object value = dereferenceValue(entry.getValue());
603:
604: // don't persist gc'ed entries.
605: if (key != null && value != null) {
606: out.writeObject(key);
607: out.writeObject(value);
608: }
609: }
610: out.writeObject(null);
611: }
612:
613: private void readObject(ObjectInputStream in) throws IOException,
614: ClassNotFoundException {
615: in.defaultReadObject();
616: int size = in.readInt();
617: this .delegate = new ConcurrentHashMap<Object, Object>(size);
618: while (true) {
619: K key = (K) in.readObject();
620: if (key == null) {
621: break;
622: }
623: V value = (V) in.readObject();
624: put(key, value);
625: }
626: }
627:
628: }
|