Project: android_external_guava
Code Examples
/*
 * Copyright (C) 2009 Google Inc. 
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); 
 * you may not use this file except in compliance with the License. 
 * You may obtain a copy of the License at 
 * 
 * http://www.apache.org/licenses/LICENSE-2.0 
 * 
 * Unless required by applicable law or agreed to in writing, software 
 * distributed under the License is distributed on an "AS IS" BASIS, 
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 
 * See the License for the specific language governing permissions and 
 * limitations under the License. 
 */
 
package com.google.common.collect; 
 
import com.google.common.annotations.GwtCompatible; 
import com.google.common.annotations.GwtIncompatible; 
import com.google.common.base.FinalizableReferenceQueue; 
import com.google.common.base.FinalizableSoftReference; 
import com.google.common.base.FinalizableWeakReference; 
import com.google.common.base.Function; 
import com.google.common.collect.CustomConcurrentHashMap.ComputingStrategy; 
import com.google.common.collect.CustomConcurrentHashMap.Internals; 
 
import java.io.IOException; 
import java.io.ObjectInputStream; 
import java.io.ObjectOutputStream; 
import java.io.Serializable; 
import java.lang.ref.SoftReference; 
import java.lang.ref.WeakReference; 
import java.lang.reflect.Field; 
import java.util.Map; 
import java.util.TimerTask; 
import java.util.concurrent.ConcurrentHashMap; 
import java.util.concurrent.ConcurrentMap; 
import java.util.concurrent.TimeUnit; 
 
/**
 * A {@link ConcurrentMap} builder, providing any combination of these 
 * features: {@linkplain SoftReference soft} or {@linkplain WeakReference 
 * weak} keys, soft or weak values, timed expiration, and on-demand 
 * computation of values. Usage example: <pre> {@code 
 * 
 *   ConcurrentMap<Key, Graph> graphs = new MapMaker() 
 *       .concurrencyLevel(32) 
 *       .softKeys() 
 *       .weakValues() 
 *       .expiration(30, TimeUnit.MINUTES) 
 *       .makeComputingMap( 
 *           new Function<Key, Graph>() { 
 *             public Graph apply(Key key) { 
 *               return createExpensiveGraph(key); 
 *             } 
 *           });}</pre> 
 * 
 * These features are all optional; {@code new MapMaker().makeMap()} 
 * returns a valid concurrent map that behaves exactly like a 
 * {@link ConcurrentHashMap}. 
 * 
 * The returned map is implemented as a hash table with similar performance 
 * characteristics to {@link ConcurrentHashMap}. It supports all optional 
 * operations of the {@code ConcurrentMap} interface. It does not permit 
 * null keys or values. It is serializable; however, serializing a map that 
 * uses soft or weak references can give unpredictable results. 
 * 
 * <p><b>Note:</b> by default, the returned map uses equality comparisons 
 * (the {@link Object#equals(Object) equals} method) to determine equality 
 * for keys or values. However, if {@link #weakKeys()} or {@link 
 * #softKeys()} was specified, the map uses identity ({@code ==}) 
 * comparisons instead for keys. Likewise, if {@link #weakValues()} or 
 * {@link #softValues()} was specified, the map uses identity comparisons 
 * for values. 
 * 
 * <p>The returned map has <i>weakly consistent iteration</i>: an iterator 
 * over one of the map's view collections may reflect some, all or none of 
 * the changes made to the map after the iterator was created. 
 * 
 * <p>An entry whose key or value is reclaimed by the garbage collector 
 * immediately disappears from the map. (If the default settings of strong 
 * keys and strong values are used, this will never happen.) The client can 
 * never observe a partially-reclaimed entry. Any {@link java.util.Map.Entry} 
 * instance retrieved from the map's {@linkplain Map#entrySet() entry set} 
 * is snapshot of that entry's state at the time of retrieval. 
 * 
 * <p>{@code new MapMaker().weakKeys().makeMap()} can almost always be 
 * used as a drop-in replacement for {@link java.util.WeakHashMap}, adding 
 * concurrency, asynchronous cleanup, identity-based equality for keys, and 
 * great flexibility. 
 * 
 * @author Bob Lee 
 * @author Kevin Bourrillion 
 * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library) 
 */
 
@GwtCompatible(emulated = true
public final class MapMaker { 
  private Strength keyStrength = Strength.STRONG; 
  private Strength valueStrength = Strength.STRONG; 
  private long expirationNanos = 0
  private boolean useCustomMap; 
  private final CustomConcurrentHashMap.Builder builder 
      = new CustomConcurrentHashMap.Builder(); 
 
  /**
   * Constructs a new {@code MapMaker} instance with default settings, 
   * including strong keys, strong values, and no automatic expiration. 
   */
 
  public MapMaker() {} 
 
  /**
   * Sets a custom initial capacity (defaults to 16). Resizing this or 
   * any other kind of hash table is a relatively slow operation, so, 
   * when possible, it is a good idea to provide estimates of expected 
   * table sizes. 
   * 
   * @throws IllegalArgumentException if {@code initialCapacity} is 
   *   negative 
   * @throws IllegalStateException if an initial capacity was already set 
   */
 
  public MapMaker initialCapacity(int initialCapacity) { 
    builder.initialCapacity(initialCapacity); 
    return this
  } 
 
  /**
   * Guides the allowed concurrency among update operations. Used as a 
   * hint for internal sizing. The table is internally partitioned to try 
   * to permit the indicated number of concurrent updates without 
   * contention.  Because placement in hash tables is essentially random, 
   * the actual concurrency will vary. Ideally, you should choose a value 
   * to accommodate as many threads as will ever concurrently modify the 
   * table. Using a significantly higher value than you need can waste 
   * space and time, and a significantly lower value can lead to thread 
   * contention. But overestimates and underestimates within an order of 
   * magnitude do not usually have much noticeable impact. A value of one 
   * is appropriate when it is known that only one thread will modify and 
   * all others will only read. Defaults to 16. 
   * 
   * @throws IllegalArgumentException if {@code concurrencyLevel} is 
   *     nonpositive 
   * @throws IllegalStateException if a concurrency level was already set 
   */
 
  @GwtIncompatible("java.util.concurrent.ConcurrentHashMap concurrencyLevel"
  public MapMaker concurrencyLevel(int concurrencyLevel) { 
    builder.concurrencyLevel(concurrencyLevel); 
    return this
  } 
 
  /**
   * Specifies that each key (not value) stored in the map should be 
   * wrapped in a {@link WeakReference} (by default, strong references 
   * are used). 
   * 
   * <p><b>Note:</b> the map will use identity ({@code ==}) comparison 
   * to determine equality of weak keys, which may not behave as you expect. 
   * For example, storing a key in the map and then attempting a lookup 
   * using a different but {@link Object#equals(Object) equals}-equivalent 
   * key will always fail. 
   * 
   * @throws IllegalStateException if the key strength was already set 
   * @see WeakReference 
   */
 
  @GwtIncompatible("java.lang.ref.WeakReference"
  public MapMaker weakKeys() { 
    return setKeyStrength(Strength.WEAK); 
  } 
 
  /**
   * Specifies that each key (not value) stored in the map should be 
   * wrapped in a {@link SoftReference} (by default, strong references 
   * are used). 
   * 
   * <p><b>Note:</b> the map will use identity ({@code ==}) comparison 
   * to determine equality of soft keys, which may not behave as you expect. 
   * For example, storing a key in the map and then attempting a lookup 
   * using a different but {@link Object#equals(Object) equals}-equivalent 
   * key will always fail. 
   * 
   * @throws IllegalStateException if the key strength was already set 
   * @see SoftReference 
   */
 
  @GwtIncompatible("java.lang.ref.SoftReference"
  public MapMaker softKeys() { 
    return setKeyStrength(Strength.SOFT); 
  } 
 
  private MapMaker setKeyStrength(Strength strength) { 
    if (keyStrength != Strength.STRONG) { 
      throw new IllegalStateException("Key strength was already set to " 
          + keyStrength + "."); 
    } 
    keyStrength = strength; 
    useCustomMap = true
    return this
  } 
 
  /**
   * Specifies that each value (not key) stored in the map should be 
   * wrapped in a {@link WeakReference} (by default, strong references 
   * are used). 
   * 
   * <p>Weak values will be garbage collected once they are weakly 
   * reachable. This makes them a poor candidate for caching; consider 
   * {@link #softValues()} instead. 
   * 
   * <p><b>Note:</b> the map will use identity ({@code ==}) comparison 
   * to determine equality of weak values. This will notably impact 
   * the behavior of {@link Map#containsValue(Object) containsValue}, 
   * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)}, 
   * and {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}. 
   * 
   * @throws IllegalStateException if the key strength was already set 
   * @see WeakReference 
   */
 
  @GwtIncompatible("java.lang.ref.WeakReference"
  public MapMaker weakValues() { 
    return setValueStrength(Strength.WEAK); 
  } 
 
  /**
   * Specifies that each value (not key) stored in the map should be 
   * wrapped in a {@link SoftReference} (by default, strong references 
   * are used). 
   * 
   * <p>Soft values will be garbage collected in response to memory 
   * demand, and in a least-recently-used manner. This makes them a 
   * good candidate for caching. 
   * 
   * <p><b>Note:</b> the map will use identity ({@code ==}) comparison 
   * to determine equality of soft values. This will notably impact 
   * the behavior of {@link Map#containsValue(Object) containsValue}, 
   * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)}, 
   * and {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}. 
   * 
   * @throws IllegalStateException if the value strength was already set 
   * @see SoftReference 
   */
 
  @GwtIncompatible("java.lang.ref.SoftReference"
  public MapMaker softValues() { 
    return setValueStrength(Strength.SOFT); 
  } 
 
  private MapMaker setValueStrength(Strength strength) { 
    if (valueStrength != Strength.STRONG) { 
      throw new IllegalStateException("Value strength was already set to " 
          + valueStrength + "."); 
    } 
    valueStrength = strength; 
    useCustomMap = true
    return this
  } 
 
  /**
   * Specifies that each entry should be automatically removed from the 
   * map once a fixed duration has passed since the entry's creation. 
   * 
   * @param duration the length of time after an entry is created that it 
   *     should be automatically removed 
   * @param unit the unit that {@code duration} is expressed in 
   * @throws IllegalArgumentException if {@code duration} is not positive 
   * @throws IllegalStateException if the expiration time was already set 
   */
 
  public MapMaker expiration(long duration, TimeUnit unit) { 
    if (expirationNanos != 0) { 
      throw new IllegalStateException("expiration time of " 
          + expirationNanos + " ns was already set"); 
    } 
    if (duration <= 0) { 
      throw new IllegalArgumentException("invalid duration: " + duration); 
    } 
    this.expirationNanos = unit.toNanos(duration); 
    useCustomMap = true
    return this
  } 
 
  /**
   * Builds the final map, without on-demand computation of values. This method 
   * does not alter the state of this {@code MapMaker} instance, so it can be 
   * invoked again to create multiple independent maps. 
   * 
   * @param <K> the type of keys to be stored in the returned map 
   * @param <V> the type of values to be stored in the returned map 
   * @return a concurrent map having the requested features 
   */
 
  public <K, V> ConcurrentMap<K, V> makeMap() { 
    return useCustomMap 
        ? new StrategyImpl<K, V>(this).map 
        : new ConcurrentHashMap<K, V>(builder.getInitialCapacity(), 
            0.75f, builder.getConcurrencyLevel()); 
  } 
 
  /**
   * Builds a map that supports atomic, on-demand computation of values. {@link 
   * Map#get} either returns an already-computed value for the given key, 
   * atomically computes it using the supplied function, or, if another thread 
   * is currently computing the value for this key, simply waits for that thread 
   * to finish and returns its computed value. Note that the function may be 
   * executed concurrently by multiple threads, but only for distinct keys. 
   * 
   * <p>If an entry's value has not finished computing yet, query methods 
   * besides {@code get} return immediately as if an entry doesn't exist. In 
   * other words, an entry isn't externally visible until the value's 
   * computation completes. 
   * 
   * <p>{@link Map#get} on the returned map will never return {@code null}. It 
   * may throw: 
   * 
   * <ul> 
   * <li>{@link NullPointerException} if the key is null or the computing 
   *     function returns null 
   * <li>{@link ComputationException} if an exception was thrown by the 
   *     computing function. If that exception is already of type {@link 
   *     ComputationException}, it is propagated directly; otherwise it is 
   *     wrapped. 
   * </ul> 
   * 
   * <p><b>Note:</b> Callers of {@code get} <i>must</i> ensure that the key 
   * argument is of type {@code K}. The {@code get} method accepts {@code 
   * Object}, so the key type is not checked at compile time. Passing an object 
   * of a type other than {@code K} can result in that object being unsafely 
   * passed to the computing function as type {@code K}, and unsafely stored in 
   * the map. 
   * 
   * <p>If {@link Map#put} is called before a computation completes, other 
   * threads waiting on the computation will wake up and return the stored 
   * value. When the computation completes, its new result will overwrite the 
   * value that was put in the map manually. 
   * 
   * <p>This method does not alter the state of this {@code MapMaker} instance, 
   * so it can be invoked again to create multiple independent maps. 
   */
 
  public <K, V> ConcurrentMap<K, V> makeComputingMap
      Function<? super K, ? extends V> computingFunction) { 
    return new StrategyImpl<K, V>(this, computingFunction).map; 
  } 
 
  // Remainder of this file is private implementation details 
 
  private enum Strength { 
    WEAK { 
      @Override boolean equal(Object a, Object b) { 
        return a == b; 
      } 
      @Override int hash(Object o) { 
        return System.identityHashCode(o); 
      } 
      @Override <K, V> ValueReference<K, V> referenceValue
          ReferenceEntry<K, V> entry, V value) { 
        return new WeakValueReference<K, V>(value, entry); 
      } 
      @Override <K, V> ReferenceEntry<K, V> newEntry
          Internals<K, V, ReferenceEntry<K, V>> internals, K key, 
          int hash, ReferenceEntry<K, V> next) { 
        return (next == null
            ? new WeakEntry<K, V>(internals, key, hash) 
            : new LinkedWeakEntry<K, V>(internals, key, hash, next); 
      } 
      @Override <K, V> ReferenceEntry<K, V> copyEntry
          K key, ReferenceEntry<K, V> original, 
          ReferenceEntry<K, V> newNext) { 
        WeakEntry<K, V> from = (WeakEntry<K, V>) original; 
        return (newNext == null
            ? new WeakEntry<K, V>(from.internals, key, from.hash) 
            : new LinkedWeakEntry<K, V>( 
                from.internals, key, from.hash, newNext); 
      } 
    }, 
 
    SOFT { 
      @Override boolean equal(Object a, Object b) { 
        return a == b; 
      } 
      @Override int hash(Object o) { 
        return System.identityHashCode(o); 
      } 
      @Override <K, V> ValueReference<K, V> referenceValue
          ReferenceEntry<K, V> entry, V value) { 
        return new SoftValueReference<K, V>(value, entry); 
      } 
      @Override <K, V> ReferenceEntry<K, V> newEntry
          Internals<K, V, ReferenceEntry<K, V>> internals, K key, 
          int hash, ReferenceEntry<K, V> next) { 
        return (next == null
            ? new SoftEntry<K, V>(internals, key, hash) 
            : new LinkedSoftEntry<K, V>(internals, key, hash, next); 
      } 
      @Override <K, V> ReferenceEntry<K, V> copyEntry
          K key, ReferenceEntry<K, V> original, 
          ReferenceEntry<K, V> newNext) { 
        SoftEntry<K, V> from = (SoftEntry<K, V>) original; 
        return (newNext == null
            ? new SoftEntry<K, V>(from.internals, key, from.hash) 
            : new LinkedSoftEntry<K, V>( 
                from.internals, key, from.hash, newNext); 
      } 
    }, 
 
    STRONG { 
      @Override boolean equal(Object a, Object b) { 
        return a.equals(b); 
      } 
      @Override int hash(Object o) { 
        return o.hashCode(); 
      } 
      @Override <K, V> ValueReference<K, V> referenceValue
          ReferenceEntry<K, V> entry, V value) { 
        return new StrongValueReference<K, V>(value); 
      } 
      @Override <K, V> ReferenceEntry<K, V> newEntry
          Internals<K, V, ReferenceEntry<K, V>> internals, K key, 
          int hash, ReferenceEntry<K, V> next) { 
        return (next == null
            ? new StrongEntry<K, V>(internals, key, hash) 
            : new LinkedStrongEntry<K, V>( 
                internals, key, hash, next); 
      } 
      @Override <K, V> ReferenceEntry<K, V> copyEntry
          K key, ReferenceEntry<K, V> original, 
          ReferenceEntry<K, V> newNext) { 
        StrongEntry<K, V> from = (StrongEntry<K, V>) original; 
        return (newNext == null
            ? new StrongEntry<K, V>(from.internals, key, from.hash) 
            : new LinkedStrongEntry<K, V>( 
                from.internals, key, from.hash, newNext); 
      } 
    }; 
 
    /**
     * Determines if two keys or values are equal according to this 
     * strength strategy. 
     */
 
    abstract boolean equal(Object a, Object b); 
 
    /**
     * Hashes a key according to this strategy. 
     */
 
    abstract int hash(Object o); 
 
    /**
     * Creates a reference for the given value according to this value 
     * strength. 
     */
 
    abstract <K, V> ValueReference<K, V> referenceValue
        ReferenceEntry<K, V> entry, V value); 
 
    /**
     * Creates a new entry based on the current key strength. 
     */
 
    abstract <K, V> ReferenceEntry<K, V> newEntry
        Internals<K, V, ReferenceEntry<K, V>> internals, K key, 
        int hash, ReferenceEntry<K, V> next); 
 
    /**
     * Creates a new entry and copies the value and other state from an 
     * existing entry. 
     */
 
    abstract <K, V> ReferenceEntry<K, V> copyEntry(K key, 
        ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext); 
  } 
 
  private static class StrategyImpl<K, V> implements Serializable, 
      ComputingStrategy<K, V, ReferenceEntry<K, V>> { 
    final Strength keyStrength; 
    final Strength valueStrength; 
    final ConcurrentMap<K, V> map; 
    final long expirationNanos; 
    Internals<K, V, ReferenceEntry<K, V>> internals; 
 
    StrategyImpl(MapMaker maker) { 
      this.keyStrength = maker.keyStrength; 
      this.valueStrength = maker.valueStrength; 
      this.expirationNanos = maker.expirationNanos; 
 
      map = maker.builder.buildMap(this); 
    } 
 
    StrategyImpl
        MapMaker maker, Function<? super K, ? extends V> computer) { 
      this.keyStrength = maker.keyStrength; 
      this.valueStrength = maker.valueStrength; 
      this.expirationNanos = maker.expirationNanos; 
 
      map = maker.builder.buildComputingMap(this, computer); 
    } 
 
    public void setValue(ReferenceEntry<K, V> entry, V value) { 
      setValueReference( 
          entry, valueStrength.referenceValue(entry, value)); 
      if (expirationNanos > 0) { 
        scheduleRemoval(entry.getKey(), value); 
      } 
    } 
 
    void scheduleRemoval(K key, V value) { 
      /*
       * TODO: Keep weak reference to map, too. Build a priority 
       * queue out of the entries themselves instead of creating a 
       * task per entry. Then, we could have one recurring task per 
       * map (which would clean the entire map and then reschedule 
       * itself depending upon when the next expiration comes). We 
       * also want to avoid removing an entry prematurely if the 
       * entry was set to the same value again. 
       */
 
      final WeakReference<K> keyReference = new WeakReference<K>(key); 
      final WeakReference<V> valueReference = new WeakReference<V>(value); 
      ExpirationTimer.instance.schedule( 
          new TimerTask() { 
            @Override public void run() { 
              K key = keyReference.get(); 
              if (key != null) { 
                // Remove if the value is still the same. 
                map.remove(key, valueReference.get()); 
              } 
            } 
          }, TimeUnit.NANOSECONDS.toMillis(expirationNanos)); 
    } 
 
    public boolean equalKeys(K a, Object b) { 
      return keyStrength.equal(a, b); 
    } 
 
    public boolean equalValues(V a, Object b) { 
      return valueStrength.equal(a, b); 
    } 
 
    public int hashKey(Object key) { 
      return keyStrength.hash(key); 
    } 
 
    public K getKey(ReferenceEntry<K, V> entry) { 
      return entry.getKey(); 
    } 
 
    public int getHash(ReferenceEntry<K, V> entry) { 
      return entry.getHash(); 
    } 
 
    public ReferenceEntry<K, V> newEntry
        K key, int hash, ReferenceEntry<K, V> next) { 
      return keyStrength.newEntry(internals, key, hash, next); 
    } 
 
    public ReferenceEntry<K, V> copyEntry(K key, 
        ReferenceEntry<K, V> original, ReferenceEntry<K, V> newNext) { 
      ValueReference<K, V> valueReference = original.getValueReference(); 
      if (valueReference == COMPUTING) { 
        ReferenceEntry<K, V> newEntry 
            = newEntry(key, original.getHash(), newNext); 
        newEntry.setValueReference( 
            new FutureValueReference(original, newEntry)); 
        return newEntry; 
      } else { 
        ReferenceEntry<K, V> newEntry 
            = newEntry(key, original.getHash(), newNext); 
        newEntry.setValueReference(valueReference.copyFor(newEntry)); 
        return newEntry; 
      } 
    } 
 
    /**
     * Waits for a computation to complete. Returns the result of the 
     * computation or null if none was available. 
     */
 
    public V waitForValue(ReferenceEntry<K, V> entry) 
        throws InterruptedException { 
      ValueReference<K, V> valueReference = entry.getValueReference(); 
      if (valueReference == COMPUTING) { 
        synchronized (entry) { 
          while ((valueReference = entry.getValueReference()) 
              == COMPUTING) { 
            entry.wait(); 
          } 
        } 
      } 
      return valueReference.waitForValue(); 
    } 
 
    /**
     * Used by CustomConcurrentHashMap to retrieve values. Returns null 
     * instead of blocking or throwing an exception. 
     */
 
    public V getValue(ReferenceEntry<K, V> entry) { 
      ValueReference<K, V> valueReference = entry.getValueReference(); 
      return valueReference.get(); 
    } 
 
    public V compute(K key, final ReferenceEntry<K, V> entry, 
        Function<? super K, ? extends V> computer) { 
      V value; 
      try { 
        value = computer.apply(key); 
      } catch (ComputationException e) { 
        // if computer has thrown a computation exception, propagate rather 
        // than wrap 
        setValueReference(entry, 
            new ComputationExceptionReference<K, V>(e.getCause())); 
        throw e; 
      } catch (Throwable t) { 
        setValueReference( 
          entry, new ComputationExceptionReference<K, V>(t)); 
        throw new ComputationException(t); 
      } 
 
      if (value == null) { 
        String message 
            = computer + " returned null for key " + key + "."
        setValueReference( 
            entry, new NullOutputExceptionReference<K, V>(message)); 
        throw new NullOutputException(message); 
      } else { 
        setValue(entry, value); 
      } 
      return value; 
    } 
 
    /**
     * Sets the value reference on an entry and notifies waiting 
     * threads. 
     */
 
    void setValueReference(ReferenceEntry<K, V> entry, 
        ValueReference<K, V> valueReference) { 
      boolean notifyOthers = (entry.getValueReference() == COMPUTING); 
      entry.setValueReference(valueReference); 
      if (notifyOthers) { 
        synchronized (entry) { 
          entry.notifyAll(); 
        } 
      } 
    } 
 
    /**
     * Points to an old entry where a value is being computed. Used to 
     * support non-blocking copying of entries during table expansion, 
     * removals, etc. 
     */
 
    private class FutureValueReference implements ValueReference<K, V> { 
      final ReferenceEntry<K, V> original; 
      final ReferenceEntry<K, V> newEntry; 
 
      FutureValueReference
          ReferenceEntry<K, V> original, ReferenceEntry<K, V> newEntry) { 
        this.original = original; 
        this.newEntry = newEntry; 
      } 
 
      public V get() { 
        boolean success = false
        try { 
          V value = original.getValueReference().get(); 
          success = true
          return value; 
        } finally { 
          if (!success) { 
            removeEntry(); 
          } 
        } 
      } 
 
      public ValueReference<K, V> copyFor(ReferenceEntry<K, V> entry) { 
        return new FutureValueReference(original, entry); 
      } 
 
      public V waitForValue() throws InterruptedException { 
        boolean success = false
        try { 
          // assert that key != null 
          V value = StrategyImpl.this.waitForValue(original); 
          success = true
          return value; 
        } finally { 
          if (!success) { 
            removeEntry(); 
          } 
        } 
      } 
 
      /**
       * Removes the entry in the event of an exception. Ideally, 
       * we'd clean up as soon as the computation completes, but we 
       * can't do that without keeping a reference to this entry from 
       * the original. 
       */
 
      void removeEntry() { 
        internals.removeEntry(newEntry); 
      } 
    } 
 
    public ReferenceEntry<K, V> getNext
        ReferenceEntry<K, V> entry) { 
      return entry.getNext(); 
    } 
 
    public void setInternals
        Internals<K, V, ReferenceEntry<K, V>> internals) { 
      this.internals = internals; 
    } 
 
    private static final long serialVersionUID = 0
 
    private void writeObject(ObjectOutputStream out) 
        throws IOException { 
      // Custom serialization code ensures that the key and value 
      // strengths are written before the map. We'll need them to 
      // deserialize the map entries. 
      out.writeObject(keyStrength); 
      out.writeObject(valueStrength); 
      out.writeLong(expirationNanos); 
 
      // TODO: It is possible for the strategy to try to use the map 
      // or internals during deserialization, for example, if an 
      // entry gets reclaimed. We could detect this case and queue up 
      // removals to be flushed after we deserialize the map. 
      out.writeObject(internals); 
      out.writeObject(map); 
    } 
 
    /**
     * Fields used during deserialization. We use a nested class so we 
     * don't load them until we need them. We need to use reflection to 
     * set final fields outside of the constructor. 
     */
 
    private static class Fields { 
      static final Field keyStrength = findField("keyStrength"); 
      static final Field valueStrength = findField("valueStrength"); 
      static final Field expirationNanos = findField("expirationNanos"); 
      static final Field internals = findField("internals"); 
      static final Field map = findField("map"); 
 
      static Field findField(String name) { 
        try { 
          Field f = StrategyImpl.class.getDeclaredField(name); 
          f.setAccessible(true); 
          return f; 
        } catch (NoSuchFieldException e) { 
          throw new AssertionError(e); 
        } 
      } 
    } 
 
    private void readObject(ObjectInputStream in) 
        throws IOException, ClassNotFoundException { 
      try { 
        Fields.keyStrength.set(this, in.readObject()); 
        Fields.valueStrength.set(this, in.readObject()); 
        Fields.expirationNanos.set(this, in.readLong()); 
        Fields.internals.set(this, in.readObject()); 
        Fields.map.set(this, in.readObject()); 
      } catch (IllegalAccessException e) { 
        throw new AssertionError(e); 
      } 
    } 
  } 
 
  /** A reference to a value. */ 
  private interface ValueReference<K, V> { 
    /**
     * Gets the value. Does not block or throw exceptions. 
     */
 
    V get(); 
 
    /** Creates a copy of this reference for the given entry. */ 
    ValueReference<K, V> copyFor(ReferenceEntry<K, V> entry); 
 
    /**
     * Waits for a value that may still be computing. Unlike get(), 
     * this method can block (in the case of FutureValueReference) or 
     * throw an exception. 
     */
 
    V waitForValue() throws InterruptedException; 
  } 
 
  private static final ValueReference<Object, Object> COMPUTING 
      = new ValueReference<Object, Object>() { 
    public Object get() { 
      return null
    } 
    public ValueReference<Object, Object> copyFor( 
        ReferenceEntry<Object, Object> entry) { 
      throw new AssertionError(); 
    } 
    public Object waitForValue() { 
      throw new AssertionError(); 
    } 
  }; 
 
  /**
   * Singleton placeholder that indicates a value is being computed. 
   */
 
  @SuppressWarnings("unchecked"
  // Safe because impl never uses a parameter or returns any non-null value 
  private static <K, V> ValueReference<K, V> computing() { 
    return (ValueReference<K, V>) COMPUTING; 
  } 
 
  /** Used to provide null output exceptions to other threads. */ 
  private static class NullOutputExceptionReference<K, V> 
      implements ValueReference<K, V> { 
    final String message; 
    NullOutputExceptionReference(String message) { 
      this.message = message; 
    } 
    public V get() { 
      return null
    } 
    public ValueReference<K, V> copyFor
        ReferenceEntry<K, V> entry) { 
      return this
    } 
    public V waitForValue() { 
      throw new NullOutputException(message); 
    } 
  } 
 
  /** Used to provide computation exceptions to other threads. */ 
  private static class ComputationExceptionReference<K, V> 
      implements ValueReference<K, V> { 
    final Throwable t; 
    ComputationExceptionReference(Throwable t) { 
      this.t = t; 
    } 
    public V get() { 
      return null
    } 
    public ValueReference<K, V> copyFor
        ReferenceEntry<K, V> entry) { 
      return this
    } 
    public V waitForValue() { 
      throw new AsynchronousComputationException(t); 
    } 
  } 
 
  /** Wrapper class ensures that queue isn't created until it's used. */ 
  private static class QueueHolder { 
    static final FinalizableReferenceQueue queue 
        = new FinalizableReferenceQueue(); 
  } 
 
  /**
   * An entry in a reference map. 
   */
 
  private interface ReferenceEntry<K, V> { 
    /**
     * Gets the value reference from this entry. 
     */
 
    ValueReference<K, V> getValueReference(); 
 
    /**
     * Sets the value reference for this entry. 
     * 
     * @param valueReference 
     */
 
    void setValueReference(ValueReference<K, V> valueReference); 
 
    /**
     * Removes this entry from the map if its value reference hasn't 
     * changed.  Used to clean up after values. The value reference can 
     * just call this method on the entry so it doesn't have to keep 
     * its own reference to the map. 
     */
 
    void valueReclaimed(); 
 
    /** Gets the next entry in the chain. */ 
    ReferenceEntry<K, V> getNext(); 
 
    /** Gets the entry's hash. */ 
    int getHash(); 
 
    /** Gets the key for this entry. */ 
    public K getKey(); 
  } 
 
  /**
   * Used for strongly-referenced keys. 
   */
 
  private static class StrongEntry<K, V> implements ReferenceEntry<K, V> { 
    final K key; 
 
    StrongEntry(Internals<K, V, ReferenceEntry<K, V>> internals, K key, 
        int hash) { 
      this.internals = internals; 
      this.key = key; 
      this.hash = hash; 
    } 
 
    public K getKey() { 
      return this.key; 
    } 
 
    // The code below is exactly the same for each entry type. 
 
    final Internals<K, V, ReferenceEntry<K, V>> internals; 
    final int hash; 
    volatile ValueReference<K, V> valueReference = computing(); 
 
    public ValueReference<K, V> getValueReference() { 
      return valueReference; 
    } 
    public void setValueReference
        ValueReference<K, V> valueReference) { 
      this.valueReference = valueReference; 
    } 
    public void valueReclaimed() { 
      internals.removeEntry(thisnull); 
    } 
    public ReferenceEntry<K, V> getNext() { 
      return null
    } 
    public int getHash() { 
      return hash; 
    } 
  } 
 
  private static class LinkedStrongEntry<K, V> extends StrongEntry<K, V> { 
 
    LinkedStrongEntry(Internals<K, V, ReferenceEntry<K, V>> internals, 
        K key, int hash, ReferenceEntry<K, V> next) { 
      super(internals, key, hash); 
      this.next = next; 
    } 
 
    final ReferenceEntry<K, V> next; 
 
    @Override public ReferenceEntry<K, V> getNext() { 
      return next; 
    } 
  } 
 
  /**
   * Used for softly-referenced keys. 
   */
 
  private static class SoftEntry<K, V> extends FinalizableSoftReference<K> 
      implements ReferenceEntry<K, V> { 
    SoftEntry(Internals<K, V, ReferenceEntry<K, V>> internals, K key, 
        int hash) { 
      super(key, QueueHolder.queue); 
      this.internals = internals; 
      this.hash = hash; 
    } 
 
    public K getKey() { 
      return get(); 
    } 
 
    public void finalizeReferent() { 
      internals.removeEntry(this); 
    } 
 
    // The code below is exactly the same for each entry type. 
 
    final Internals<K, V, ReferenceEntry<K, V>> internals; 
    final int hash; 
    volatile ValueReference<K, V> valueReference = computing(); 
 
    public ValueReference<K, V> getValueReference() { 
      return valueReference; 
    } 
    public void setValueReference
        ValueReference<K, V> valueReference) { 
      this.valueReference = valueReference; 
    } 
    public void valueReclaimed() { 
      internals.removeEntry(thisnull); 
    } 
    public ReferenceEntry<K, V> getNext() { 
      return null
    } 
    public int getHash() { 
      return hash; 
    } 
  } 
 
  private static class LinkedSoftEntry<K, V> extends SoftEntry<K, V> { 
    LinkedSoftEntry(Internals<K, V, ReferenceEntry<K, V>> internals, 
        K key, int hash, ReferenceEntry<K, V> next) { 
      super(internals, key, hash); 
      this.next = next; 
    } 
 
    final ReferenceEntry<K, V> next; 
 
    @Override public ReferenceEntry<K, V> getNext() { 
      return next; 
    } 
  } 
 
  /**
   * Used for weakly-referenced keys. 
   */
 
  private static class WeakEntry<K, V> extends FinalizableWeakReference<K> 
      implements ReferenceEntry<K, V> { 
    WeakEntry(Internals<K, V, ReferenceEntry<K, V>> internals, K key, 
        int hash) { 
      super(key, QueueHolder.queue); 
      this.internals = internals; 
      this.hash = hash; 
    } 
 
    public K getKey() { 
      return get(); 
    } 
 
    public void finalizeReferent() { 
      internals.removeEntry(this); 
    } 
 
    // The code below is exactly the same for each entry type. 
 
    final Internals<K, V, ReferenceEntry<K, V>> internals; 
    final int hash; 
    volatile ValueReference<K, V> valueReference = computing(); 
 
    public ValueReference<K, V> getValueReference() { 
      return valueReference; 
    } 
    public void setValueReference
        ValueReference<K, V> valueReference) { 
      this.valueReference = valueReference; 
    } 
    public void valueReclaimed() { 
      internals.removeEntry(thisnull); 
    } 
    public ReferenceEntry<K, V> getNext() { 
      return null
    } 
    public int getHash() { 
      return hash; 
    } 
  } 
 
  private static class LinkedWeakEntry<K, V> extends WeakEntry<K, V> { 
    LinkedWeakEntry(Internals<K, V, ReferenceEntry<K, V>> internals, 
        K key, int hash, ReferenceEntry<K, V> next) { 
      super(internals, key, hash); 
      this.next = next; 
    } 
 
    final ReferenceEntry<K, V> next; 
 
    @Override public ReferenceEntry<K, V> getNext() { 
      return next; 
    } 
  } 
 
  /** References a weak value. */ 
  private static class WeakValueReference<K, V> 
      extends FinalizableWeakReference<V> 
      implements ValueReference<K, V> { 
    final ReferenceEntry<K, V> entry; 
 
    WeakValueReference(V referent, ReferenceEntry<K, V> entry) { 
      super(referent, QueueHolder.queue); 
      this.entry = entry; 
    } 
 
    public void finalizeReferent() { 
      entry.valueReclaimed(); 
    } 
 
    public ValueReference<K, V> copyFor
        ReferenceEntry<K, V> entry) { 
      return new WeakValueReference<K, V>(get(), entry); 
    } 
 
    public V waitForValue() { 
      return get(); 
    } 
  } 
 
  /** References a soft value. */ 
  private static class SoftValueReference<K, V> 
      extends FinalizableSoftReference<V> 
      implements ValueReference<K, V> { 
    final ReferenceEntry<K, V> entry; 
 
    SoftValueReference(V referent, ReferenceEntry<K, V> entry) { 
      super(referent, QueueHolder.queue); 
      this.entry = entry; 
    } 
 
    public void finalizeReferent() { 
      entry.valueReclaimed(); 
    } 
 
    public ValueReference<K, V> copyFor
        ReferenceEntry<K, V> entry) { 
      return new SoftValueReference<K, V>(get(), entry); 
    } 
 
    public V waitForValue() { 
      return get(); 
    } 
  } 
 
  /** References a strong value. */ 
  private static class StrongValueReference<K, V> 
      implements ValueReference<K, V> { 
    final V referent; 
 
    StrongValueReference(V referent) { 
      this.referent = referent; 
    } 
 
    public V get() { 
      return referent; 
    } 
 
    public ValueReference<K, V> copyFor
        ReferenceEntry<K, V> entry) { 
      return this
    } 
 
    public V waitForValue() { 
      return get(); 
    } 
  } 
}