common/collect/MapMaker.java

/*
 * 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(this, null);
    }
    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(this, null);
    }
    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(this, null);
    }
    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();
    }
  }
}