    001    /*
    002     * Copyright (C) 2009 The Guava Authors
    003     *
    004     * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
    005     * in compliance with the License. You may obtain a copy of the License at
    006     *
    007     * http://www.apache.org/licenses/LICENSE-2.0
    008     *
    009     * Unless required by applicable law or agreed to in writing, software distributed under the License
    010     * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
    011     * or implied. See the License for the specific language governing permissions and limitations under
    012     * the License.
    013     */
    014
    015    package com.google.common.collect;
    016
    017    import static com.google.common.base.Objects.firstNonNull;
    018    import static com.google.common.base.Preconditions.checkArgument;
    019    import static com.google.common.base.Preconditions.checkNotNull;
    020    import static com.google.common.base.Preconditions.checkState;
    021
    022    import com.google.common.annotations.Beta;
    023    import com.google.common.annotations.GwtCompatible;
    024    import com.google.common.annotations.GwtIncompatible;
    025    import com.google.common.base.Ascii;
    026    import com.google.common.base.Equivalence;
    027    import com.google.common.base.Equivalences;
    028    import com.google.common.base.Function;
    029    import com.google.common.base.Objects;
    030    import com.google.common.base.Ticker;
    031    import com.google.common.collect.MapEvictionListener;
    032    import com.google.common.collect.ComputingConcurrentHashMap.ComputingMapAdapter;
    033    import com.google.common.collect.CustomConcurrentHashMap.Strength;
    034
    035    import java.io.Serializable;
    036    import java.lang.ref.SoftReference;
    037    import java.lang.ref.WeakReference;
    038    import java.util.AbstractMap;
    039    import java.util.Collections;
    040    import java.util.ConcurrentModificationException;
    041    import java.util.Map;
    042    import java.util.Set;
    043    import java.util.concurrent.ConcurrentHashMap;
    044    import java.util.concurrent.ConcurrentMap;
    045    import java.util.concurrent.TimeUnit;
    046
    047    import javax.annotation.Nullable;
    048
    049    /**
    050     * <p>A builder of {@link ConcurrentMap} instances having any combination of the following features:
    051     *
    052     * <ul>
    053     * <li>keys or values automatically wrapped in {@linkplain WeakReference weak} or {@linkplain
    054     *     SoftReference soft} references
    055     * <li>least-recently-used eviction when a maximum size is exceeded
    056     * <li>time-based expiration of entries, measured since last access or last write
    057     * <li>notification of evicted (or otherwise removed) entries
    058     * <li>on-demand computation of values for keys not already present
    059     * </ul>
    060     *
    061     * <p>Usage example: <pre>   {@code
    062     *
    063     *   ConcurrentMap<Key, Graph> graphs = new MapMaker()
    064     *       .concurrencyLevel(4)
    065     *       .weakKeys()
    066     *       .maximumSize(10000)
    067     *       .expireAfterWrite(10, TimeUnit.MINUTES)
    068     *       .makeComputingMap(
    069     *           new Function<Key, Graph>() {
    070     *             public Graph apply(Key key) {
    071     *               return createExpensiveGraph(key);
    072     *             }
    073     *           });}</pre>
    074     *
    075     *
    076     * These features are all optional; {@code new MapMaker().makeMap()} returns a valid concurrent map
    077     * that behaves similarly to a {@link ConcurrentHashMap}.
    078     *
    079     * <p>The returned map is implemented as a hash table with similar performance characteristics to
    080     * {@link ConcurrentHashMap}. It supports all optional operations of the {@code ConcurrentMap}
    081     * interface. It does not permit null keys or values.
    082     *
    083     * <p><b>Note:</b> by default, the returned map uses equality comparisons (the {@link Object#equals
    084     * equals} method) to determine equality for keys or values. However, if {@link #weakKeys} or {@link
    085     * #softKeys} was specified, the map uses identity ({@code ==}) comparisons instead for keys.
    086     * Likewise, if {@link #weakValues} or {@link #softValues} was specified, the map uses identity
    087     * comparisons for values.
    088     *
    089     * <p>The view collections of the returned map have <i>weakly consistent iterators</i>. This means
    090     * that they are safe for concurrent use, but if other threads modify the map after the iterator is
    091     * created, it is undefined which of these changes, if any, are reflected in that iterator. These
    092     * iterators never throw {@link ConcurrentModificationException}.
    093     *
    094     * <p>If soft or weak references were requested, it is possible for a key or value present in the
    095     * the map to be reclaimed by the garbage collector. If this happens, the entry automatically
    096     * disappears from the map. A partially-reclaimed entry is never exposed to the user. Any {@link
    097     * java.util.Map.Entry} instance retrieved from the map's {@linkplain Map#entrySet entry set} is a
    098     * snapshot of that entry's state at the time of retrieval; such entries do, however, support {@link
    099     * java.util.Map.Entry#setValue}, which simply calls {@link Map#put} on the entry's key.
    100     *
    101     * <p>The maps produced by {@code MapMaker} are serializable, and the deserialized maps retain all
    102     * the configuration properties of the original map. During deserialization, if the original map had
    103     * used soft or weak references, the entries are reconstructed as they were, but it's not unlikely
    104     * they'll be quickly garbage-collected before they are ever accessed.
    105     *
    106     * <p>{@code new MapMaker().weakKeys().makeMap()} is a recommended replacement for {@link
    107     * java.util.WeakHashMap}, but note that it compares keys using object identity whereas {@code
    108     * WeakHashMap} uses {@link Object#equals}.
    109     *
    110     * @author Bob Lee
    111     * @author Charles Fry
    112     * @author Kevin Bourrillion
    113     * @since 2.0 (imported from Google Collections Library)
    114     */
    115    @GwtCompatible(emulated = true)
    116    public final class MapMaker extends GenericMapMaker<Object, Object> {
    117      private static final int DEFAULT_INITIAL_CAPACITY = 16;
    118      private static final int DEFAULT_CONCURRENCY_LEVEL = 4;
    119      private static final int DEFAULT_EXPIRATION_NANOS = 0;
    120
    121      static final int UNSET_INT = -1;
    122
    123      // TODO(kevinb): dispense with this after benchmarking
    124      boolean useCustomMap;
    125
    126      int initialCapacity = UNSET_INT;
    127      int concurrencyLevel = UNSET_INT;
    128      int maximumSize = UNSET_INT;
    129
    130      Strength keyStrength;
    131      Strength valueStrength;
    132
    133      long expireAfterWriteNanos = UNSET_INT;
    134      long expireAfterAccessNanos = UNSET_INT;
    135
    136      RemovalCause nullRemovalCause;
    137
    138      Equivalence<Object> keyEquivalence;
    139      Equivalence<Object> valueEquivalence;
    140
    141      Ticker ticker;
    142
    143      /**
    144       * Constructs a new {@code MapMaker} instance with default settings, including strong keys, strong
    145       * values, and no automatic eviction of any kind.
    146       */
    147      public MapMaker() {}
    148
    149      private boolean useNullMap() {
    150        return (nullRemovalCause == null);
    151      }
    152
    153      /**
    154       * Sets a custom {@code Equivalence} strategy for comparing keys.
    155       *
    156       * <p>By default, the map uses {@link Equivalences#identity} to determine key equality when
    157       * {@link #weakKeys} or {@link #softKeys} is specified, and {@link Equivalences#equals()}
    158       * otherwise.
    159       */
    160      @GwtIncompatible("To be supported")
    161      @Override
    162      MapMaker keyEquivalence(Equivalence<Object> equivalence) {
    163        checkState(keyEquivalence == null, "key equivalence was already set to %s", keyEquivalence);
    164        keyEquivalence = checkNotNull(equivalence);
    165        this.useCustomMap = true;
    166        return this;
    167      }
    168
    169      Equivalence<Object> getKeyEquivalence() {
    170        return firstNonNull(keyEquivalence, getKeyStrength().defaultEquivalence());
    171      }
    172
    173      /**
    174       * Sets a custom {@code Equivalence} strategy for comparing values.
    175       *
    176       * <p>By default, the map uses {@link Equivalences#identity} to determine value equality when
    177       * {@link #weakValues} or {@link #softValues} is specified, and {@link Equivalences#equals()}
    178       * otherwise.
    179       */
    180      @GwtIncompatible("To be supported")
    181      @Override
    182      MapMaker valueEquivalence(Equivalence<Object> equivalence) {
    183        checkState(valueEquivalence == null,
    184            "value equivalence was already set to %s", valueEquivalence);
    185        this.valueEquivalence = checkNotNull(equivalence);
    186        this.useCustomMap = true;
    187        return this;
    188      }
    189
    190      Equivalence<Object> getValueEquivalence() {
    191        return firstNonNull(valueEquivalence, getValueStrength().defaultEquivalence());
    192      }
    193
    194      /**
    195       * Sets the minimum total size for the internal hash tables. For example, if the initial capacity
    196       * is {@code 60}, and the concurrency level is {@code 8}, then eight segments are created, each
    197       * having a hash table of size eight. Providing a large enough estimate at construction time
    198       * avoids the need for expensive resizing operations later, but setting this value unnecessarily
    199       * high wastes memory.
    200       *
    201       * @throws IllegalArgumentException if {@code initialCapacity} is negative
    202       * @throws IllegalStateException if an initial capacity was already set
    203       */
    204      @Override
    205      public MapMaker initialCapacity(int initialCapacity) {
    206        checkState(this.initialCapacity == UNSET_INT, "initial capacity was already set to %s",
    207            this.initialCapacity);
    208        checkArgument(initialCapacity >= 0);
    209        this.initialCapacity = initialCapacity;
    210        return this;
    211      }
    212
    213      int getInitialCapacity() {
    214        return (initialCapacity == UNSET_INT) ? DEFAULT_INITIAL_CAPACITY : initialCapacity;
    215      }
    216
    217      /**
    218       * Specifies the maximum number of entries the map may contain. Note that the map <b>may evict an
    219       * entry before this limit is exceeded</b>. As the map size grows close to the maximum, the map
    220       * evicts entries that are less likely to be used again. For example, the map may evict an entry
    221       * because it hasn't been used recently or very often.
    222       *
    223       * <p>When {@code size} is zero, elements can be successfully added to the map, but are evicted
    224       * immediately. This has the same effect as invoking {@link #expireAfterWrite
    225       * expireAfterWrite}{@code (0, unit)} or {@link #expireAfterAccess expireAfterAccess}{@code (0,
    226       * unit)}. It can be useful in testing, or to disable caching temporarily without a code change.
    227       *
    228       * <p>Caching functionality in {@code MapMaker} is being moved to
    229       * {@link com.google.common.cache.CacheBuilder}.
    230       * <b>This method is scheduled for deletion from Guava in Guava release 11.0.</b>
    231       *
    232       * @param size the maximum size of the map
    233       * @throws IllegalArgumentException if {@code size} is negative
    234       * @throws IllegalStateException if a maximum size was already set
    235       * @since 8.0
    236       */
    237      @Beta
    238      @Override
    239      @Deprecated
    240      public MapMaker maximumSize(int size) {
    241        checkState(this.maximumSize == UNSET_INT, "maximum size was already set to %s",
    242            this.maximumSize);
    243        checkArgument(size >= 0, "maximum size must not be negative");
    244        this.maximumSize = size;
    245        this.useCustomMap = true;
    246        if (maximumSize == 0) {
    247          // SIZE trumps EXPIRED
    248          this.nullRemovalCause = RemovalCause.SIZE;
    249        }
    250        return this;
    251      }
    252
    253      /**
    254       * Guides the allowed concurrency among update operations. Used as a hint for internal sizing. The
    255       * table is internally partitioned to try to permit the indicated number of concurrent updates
    256       * without contention. Because assignment of entries to these partitions is not necessarily
    257       * uniform, the actual concurrency observed may vary. Ideally, you should choose a value to
    258       * accommodate as many threads as will ever concurrently modify the table. Using a significantly
    259       * higher value than you need can waste space and time, and a significantly lower value can lead
    260       * to thread contention. But overestimates and underestimates within an order of magnitude do not
    261       * usually have much noticeable impact. A value of one permits only one thread to modify the map
    262       * at a time, but since read operations can proceed concurrently, this still yields higher
    263       * concurrency than full synchronization. Defaults to 4.
    264       *
    265       * <p><b>Note:</b> Prior to Guava release 9.0, the default was 16. It is possible the default will
    266       * change again in the future. If you care about this value, you should always choose it
    267       * explicitly.
    268       *
    269       * @throws IllegalArgumentException if {@code concurrencyLevel} is nonpositive
    270       * @throws IllegalStateException if a concurrency level was already set
    271       */
    272      @Override
    273      public MapMaker concurrencyLevel(int concurrencyLevel) {
    274        checkState(this.concurrencyLevel == UNSET_INT, "concurrency level was already set to %s",
    275            this.concurrencyLevel);
    276        checkArgument(concurrencyLevel > 0);
    277        this.concurrencyLevel = concurrencyLevel;
    278        return this;
    279      }
    280
    281      int getConcurrencyLevel() {
    282        return (concurrencyLevel == UNSET_INT) ? DEFAULT_CONCURRENCY_LEVEL : concurrencyLevel;
    283      }
    284
    285      /**
    286       * Specifies that each key (not value) stored in the map should be strongly referenced.
    287       *
    288       * @throws IllegalStateException if the key strength was already set
    289       */
    290      @Override
    291      MapMaker strongKeys() {
    292        return setKeyStrength(Strength.STRONG);
    293      }
    294
    295      /**
    296       * Specifies that each key (not value) stored in the map should be wrapped in a {@link
    297       * WeakReference} (by default, strong references are used).
    298       *
    299       * <p><b>Warning:</b> when this method is used, the resulting map will use identity ({@code ==})
    300       * comparison to determine equality of keys, which is a technical violation of the {@link Map}
    301       * specification, and may not be what you expect.
    302       *
    303       * @throws IllegalStateException if the key strength was already set
    304       * @see WeakReference
    305       */
    306      @GwtIncompatible("java.lang.ref.WeakReference")
    307      @Override
    308      public MapMaker weakKeys() {
    309        return setKeyStrength(Strength.WEAK);
    310      }
    311
    312      /**
    313       * Specifies that each key (not value) stored in the map should be wrapped in a
    314       * {@link SoftReference} (by default, strong references are used). Softly-referenced objects will
    315       * be garbage-collected in a <i>globally</i> least-recently-used manner, in response to memory
    316       * demand.
    317       *
    318       * <p><b>Warning:</b> when this method is used, the resulting map will use identity ({@code ==})
    319       * comparison to determine equality of keys, which is a technical violation of the {@link Map}
    320       * specification, and may not be what you expect.
    321       *
    322       * @throws IllegalStateException if the key strength was already set
    323       * @see SoftReference
    324       * @deprecated use {@link #softValues} to create a memory-sensitive map, or {@link #weakKeys} to
    325       *     create a map that doesn't hold strong references to the keys.
    326       *     <b>This method is scheduled for deletion in January 2013.</b>
    327       */
    328      @Deprecated
    329      @GwtIncompatible("java.lang.ref.SoftReference")
    330      @Override
    331      public MapMaker softKeys() {
    332        return setKeyStrength(Strength.SOFT);
    333      }
    334
    335      MapMaker setKeyStrength(Strength strength) {
    336        checkState(keyStrength == null, "Key strength was already set to %s", keyStrength);
    337        keyStrength = checkNotNull(strength);
    338        if (strength != Strength.STRONG) {
    339          // STRONG could be used during deserialization.
    340          useCustomMap = true;
    341        }
    342        return this;
    343      }
    344
    345      Strength getKeyStrength() {
    346        return firstNonNull(keyStrength, Strength.STRONG);
    347      }
    348
    349      /**
    350       * Specifies that each value (not key) stored in the map should be strongly referenced.
    351       *
    352       * @throws IllegalStateException if the value strength was already set
    353       */
    354      @Override
    355      MapMaker strongValues() {
    356        return setValueStrength(Strength.STRONG);
    357      }
    358
    359      /**
    360       * Specifies that each value (not key) stored in the map should be wrapped in a
    361       * {@link WeakReference} (by default, strong references are used).
    362       *
    363       * <p>Weak values will be garbage collected once they are weakly reachable. This makes them a poor
    364       * candidate for caching; consider {@link #softValues} instead.
    365       *
    366       * <p><b>Warning:</b> when this method is used, the resulting map will use identity ({@code ==})
    367       * comparison to determine equality of values. This technically violates the specifications of
    368       * the methods {@link Map#containsValue containsValue},
    369       * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)} and
    370       * {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}, and may not be what you
    371       * expect.
    372       *
    373       * @throws IllegalStateException if the value strength was already set
    374       * @see WeakReference
    375       */
    376      @GwtIncompatible("java.lang.ref.WeakReference")
    377      @Override
    378      public MapMaker weakValues() {
    379        return setValueStrength(Strength.WEAK);
    380      }
    381
    382      /**
    383       * Specifies that each value (not key) stored in the map should be wrapped in a
    384       * {@link SoftReference} (by default, strong references are used). Softly-referenced objects will
    385       * be garbage-collected in a <i>globally</i> least-recently-used manner, in response to memory
    386       * demand.
    387       *
    388       * <p><b>Warning:</b> in most circumstances it is better to set a per-cache {@linkplain
    389       * #maximumSize maximum size} instead of using soft references. You should only use this method if
    390       * you are well familiar with the practical consequences of soft references.
    391       *
    392       * <p><b>Warning:</b> when this method is used, the resulting map will use identity ({@code ==})
    393       * comparison to determine equality of values. This technically violates the specifications of
    394       * the methods {@link Map#containsValue containsValue},
    395       * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)} and
    396       * {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}, and may not be what you
    397       * expect.
    398       *
    399       * @throws IllegalStateException if the value strength was already set
    400       * @see SoftReference
    401       */
    402      @GwtIncompatible("java.lang.ref.SoftReference")
    403      @Override
    404      public MapMaker softValues() {
    405        return setValueStrength(Strength.SOFT);
    406      }
    407
    408      MapMaker setValueStrength(Strength strength) {
    409        checkState(valueStrength == null, "Value strength was already set to %s", valueStrength);
    410        valueStrength = checkNotNull(strength);
    411        if (strength != Strength.STRONG) {
    412          // STRONG could be used during deserialization.
    413          useCustomMap = true;
    414        }
    415        return this;
    416      }
    417
    418      Strength getValueStrength() {
    419        return firstNonNull(valueStrength, Strength.STRONG);
    420      }
    421
    422      /**
    423       * Old name of {@link #expireAfterWrite}.
    424       *
    425       * @deprecated Caching functionality in {@code MapMaker} is being moved to
    426       *     {@link com.google.common.cache.CacheBuilder}. Functionality equivalent to
    427       *     {@link MapMaker#expiration} is provided by
    428       *     {@link com.google.common.cache.CacheBuilder#expireAfterWrite}.
    429       *     <b>This method is scheduled for deletion in July 2012.</b>
    430       */
    431      @Deprecated
    432      @Override
    433      public
    434      MapMaker expiration(long duration, TimeUnit unit) {
    435        return expireAfterWrite(duration, unit);
    436      }
    437
    438      /**
    439       * Specifies that each entry should be automatically removed from the map once a fixed duration
    440       * has elapsed after the entry's creation, or the most recent replacement of its value.
    441       *
    442       * <p>When {@code duration} is zero, elements can be successfully added to the map, but are
    443       * evicted immediately. This has a very similar effect to invoking {@link #maximumSize
    444       * maximumSize}{@code (0)}. It can be useful in testing, or to disable caching temporarily without
    445       * a code change.
    446       *
    447       * <p>Expired entries may be counted by {@link Map#size}, but will never be visible to read or
    448       * write operations. Expired entries are currently cleaned up during write operations, or during
    449       * occasional read operations in the absense of writes; though this behavior may change in the
    450       * future.
    451       *
    452       * <p>Caching functionality in {@code MapMaker} is being moved to
    453       * {@link com.google.common.cache.CacheBuilder}.
    454       * <b>This method is scheduled for deletion from Guava in Guava release 11.0.</b>
    455       *
    456       * @param duration the length of time after an entry is created that it should be automatically
    457       *     removed
    458       * @param unit the unit that {@code duration} is expressed in
    459       * @throws IllegalArgumentException if {@code duration} is negative
    460       * @throws IllegalStateException if the time to live or time to idle was already set
    461       * @since 8.0
    462       */
    463      @Override
    464      @Deprecated
    465      public MapMaker expireAfterWrite(long duration, TimeUnit unit) {
    466        checkExpiration(duration, unit);
    467        this.expireAfterWriteNanos = unit.toNanos(duration);
    468        if (duration == 0 && this.nullRemovalCause == null) {
    469          // SIZE trumps EXPIRED
    470          this.nullRemovalCause = RemovalCause.EXPIRED;
    471        }
    472        useCustomMap = true;
    473        return this;
    474      }
    475
    476      private void checkExpiration(long duration, TimeUnit unit) {
    477        checkState(expireAfterWriteNanos == UNSET_INT, "expireAfterWrite was already set to %s ns",
    478            expireAfterWriteNanos);
    479        checkState(expireAfterAccessNanos == UNSET_INT, "expireAfterAccess was already set to %s ns",
    480            expireAfterAccessNanos);
    481        checkArgument(duration >= 0, "duration cannot be negative: %s %s", duration, unit);
    482      }
    483
    484      long getExpireAfterWriteNanos() {
    485        return (expireAfterWriteNanos == UNSET_INT) ? DEFAULT_EXPIRATION_NANOS : expireAfterWriteNanos;
    486      }
    487
    488      /**
    489       * Specifies that each entry should be automatically removed from the map once a fixed duration
    490       * has elapsed after the entry's last read or write access.
    491       *
    492       * <p>When {@code duration} is zero, elements can be successfully added to the map, but are
    493       * evicted immediately. This has a very similar effect to invoking {@link #maximumSize
    494       * maximumSize}{@code (0)}. It can be useful in testing, or to disable caching temporarily without
    495       * a code change.
    496       *
    497       * <p>Expired entries may be counted by {@link Map#size}, but will never be visible to read or
    498       * write operations. Expired entries are currently cleaned up during write operations, or during
    499       * occasional read operations in the absense of writes; though this behavior may change in the
    500       * future.
    501       *
    502       * <p>Caching functionality in {@code MapMaker} is being moved to
    503       * {@link com.google.common.cache.CacheBuilder}.
    504       * <b>This method is scheduled for deletion from Guava in Guava release 11.0.</b>
    505       *
    506       * @param duration the length of time after an entry is last accessed that it should be
    507       *     automatically removed
    508       * @param unit the unit that {@code duration} is expressed in
    509       * @throws IllegalArgumentException if {@code duration} is negative
    510       * @throws IllegalStateException if the time to idle or time to live was already set
    511       * @since 8.0
    512       */
    513      @GwtIncompatible("To be supported")
    514      @Override
    515      @Deprecated
    516      public MapMaker expireAfterAccess(long duration, TimeUnit unit) {
    517        checkExpiration(duration, unit);
    518        this.expireAfterAccessNanos = unit.toNanos(duration);
    519        if (duration == 0 && this.nullRemovalCause == null) {
    520          // SIZE trumps EXPIRED
    521          this.nullRemovalCause = RemovalCause.EXPIRED;
    522        }
    523        useCustomMap = true;
    524        return this;
    525      }
    526
    527      long getExpireAfterAccessNanos() {
    528        return (expireAfterAccessNanos == UNSET_INT)
    529            ? DEFAULT_EXPIRATION_NANOS : expireAfterAccessNanos;
    530      }
    531
    532      Ticker getTicker() {
    533        return firstNonNull(ticker, Ticker.systemTicker());
    534      }
    535
    536      /**
    537       * Specifies a listener instance, which all maps built using this {@code MapMaker} will notify
    538       * each time an entry is removed from the map by any means.
    539       *
    540       * <p>Each map built by this map maker after this method is called invokes the supplied listener
    541       * after removing an element for any reason (see removal causes in {@link RemovalCause}). It will
    542       * invoke the listener during invocations of any of that map's public methods (even read-only
    543       * methods).
    544       *
    545       * <p><b>Important note:</b> Instead of returning <i>this</i> as a {@code MapMaker} instance,
    546       * this method returns {@code GenericMapMaker<K, V>}. From this point on, either the original
    547       * reference or the returned reference may be used to complete configuration and build the map,
    548       * but only the "generic" one is type-safe. That is, it will properly prevent you from building
    549       * maps whose key or value types are incompatible with the types accepted by the listener already
    550       * provided; the {@code MapMaker} type cannot do this. For best results, simply use the standard
    551       * method-chaining idiom, as illustrated in the documentation at top, configuring a {@code
    552       * MapMaker} and building your {@link Map} all in a single statement.
    553       *
    554       * <p><b>Warning:</b> if you ignore the above advice, and use this {@code MapMaker} to build a map
    555       * or cache whose key or value type is incompatible with the listener, you will likely experience
    556       * a {@link ClassCastException} at some <i>undefined</i> point in the future.
    557       *
    558       * @throws IllegalStateException if a removal listener was already set
    559       */
    560      @GwtIncompatible("To be supported")
    561      <K, V> GenericMapMaker<K, V> removalListener(RemovalListener<K, V> listener) {
    562        checkState(this.removalListener == null);
    563
    564        // safely limiting the kinds of maps this can produce
    565        @SuppressWarnings("unchecked")
    566        GenericMapMaker<K, V> me = (GenericMapMaker<K, V>) this;
    567        me.removalListener = checkNotNull(listener);
    568        useCustomMap = true;
    569        return me;
    570      }
    571
    572      /**
    573       * Class to hold the MapEvictionListener. Enables serialization if the
    574       * eviction listener is serializable to begin with.
    575       */
    576      static final class MapMakerRemovalListener<K, V> implements
    577          RemovalListener<K, V>, Serializable {
    578        private static final long serialVersionUID = 0;
    579
    580        private final MapEvictionListener<K, V> listener;
    581
    582        public MapMakerRemovalListener(final MapEvictionListener<K, V> listener) {
    583          this.listener = checkNotNull(listener);
    584        }
    585
    586        @Override
    587        public void onRemoval(final RemovalNotification<K, V> notification) {
    588          if (notification.wasEvicted()) {
    589            listener.onEviction(notification.getKey(), notification.getValue());
    590          }
    591        }
    592      }
    593
    594      /**
    595       * Specifies a listener instance, which all maps built using this {@code MapMaker} will notify
    596       * each time an entry is evicted.
    597       *
    598       * <p>A map built by this map maker will invoke the supplied listener after it evicts an entry,
    599       * whether it does so due to timed expiration, exceeding the maximum size, or discovering that the
    600       * key or value has been reclaimed by the garbage collector. It will invoke the listener
    601       * during invocations of any of that map's public methods (even read-only methods). The listener
    602       * will <i>not</i> be invoked on manual removal.
    603       *
    604       * <p><b>Important note:</b> Instead of returning <i>this</i> as a {@code MapMaker} instance,
    605       * this method returns {@code GenericMapMaker<K, V>}. From this point on, either the original
    606       * reference or the returned reference may be used to complete configuration and build the map,
    607       * but only the "generic" one is type-safe. That is, it will properly prevent you from building
    608       * maps whose key or value types are incompatible with the types accepted by the listener already
    609       * provided; the {@code MapMaker} type cannot do this. For best results, simply use the standard
    610       * method-chaining idiom, as illustrated in the documentation at top, configuring a {@code
    611       * MapMaker} and building your {@link Map} all in a single statement.
    612       *
    613       * <p><b>Warning:</b> if you ignore the above advice, and use this {@code MapMaker} to build maps
    614       * whose key or value types are incompatible with the listener, you will likely experience a
    615       * {@link ClassCastException} at an undefined point in the future.
    616       *
    617       * @throws IllegalStateException if an eviction listener was already set
    618       * @deprecated Caching functionality in {@code MapMaker} is being moved to
    619       *     {@link com.google.common.cache.CacheBuilder}. Functionality similar to
    620       *     {@link MapMaker#evictionListener} is provided by {@link
    621       *  com.google.common.cache.CacheBuilder#removalListener(com.google.common.cache.RemovalListener)}
    622       *     which also provides
    623       *     additional information about the entry being evicted; note that {@code evictionListener}
    624       *     only notifies on removals due to eviction, while {@code removalListener} also notifies on
    625       *     explicit removal (providing the {@link com.google.common.cache.RemovalCause} to
    626       *     indicate the specific cause of removal. <b>This method is scheduled for deletion in Guava
    627       *     release 11.</b>
    628       * @since 7.0
    629       */
    630      @Beta
    631      @Deprecated
    632      @GwtIncompatible("To be supported")
    633      public
    634      <K, V> GenericMapMaker<K, V> evictionListener(final MapEvictionListener<K, V> listener) {
    635        checkState(this.removalListener == null);
    636
    637        // safely limiting the kinds of maps this can produce
    638        @SuppressWarnings("unchecked")
    639        GenericMapMaker<K, V> me = (GenericMapMaker<K, V>) this;
    640        me.removalListener = new MapMakerRemovalListener<K, V>(listener);
    641        useCustomMap = true;
    642        return me;
    643      }
    644
    645      /**
    646       * Builds a thread-safe map, without on-demand computation of values. This method does not alter
    647       * the state of this {@code MapMaker} instance, so it can be invoked again to create multiple
    648       * independent maps.
    649       *
    650       * <p>The bulk operations {@code putAll}, {@code equals}, and {@code clear} are not guaranteed to
    651       * be performed atomically on the returned map. Additionally, {@code size} and {@code
    652       * containsValue} are implemented as bulk read operations, and thus may fail to observe concurrent
    653       * writes.
    654       *
    655       * @return a serializable concurrent map having the requested features
    656       */
    657      @Override
    658      public <K, V> ConcurrentMap<K, V> makeMap() {
    659        if (!useCustomMap) {
    660          return new ConcurrentHashMap<K, V>(getInitialCapacity(), 0.75f, getConcurrencyLevel());
    661        }
    662        return (nullRemovalCause == null)
    663            ? new CustomConcurrentHashMap<K, V>(this)
    664            : new NullConcurrentMap<K, V>(this);
    665      }
    666
    667      /**
    668       * Returns a CustomConcurrentHashMap for the benefit of internal callers that use features of
    669       * that class not exposed through ConcurrentMap.
    670       */
    671      @Override
    672      @GwtIncompatible("CustomConcurrentHashMap")
    673      <K, V> CustomConcurrentHashMap<K, V> makeCustomMap() {
    674        return new CustomConcurrentHashMap<K, V>(this);
    675      }
    676
    677      /**
    678       * Builds a map that supports atomic, on-demand computation of values. {@link Map#get} either
    679       * returns an already-computed value for the given key, atomically computes it using the supplied
    680       * function, or, if another thread is currently computing the value for this key, simply waits for
    681       * that thread to finish and returns its computed value. Note that the function may be executed
    682       * concurrently by multiple threads, but only for distinct keys.
    683       *
    684       * <p>New code should use {@link com.google.common.cache.CacheBuilder}, which supports
    685       * {@linkplain com.google.common.cache.CacheStats statistics} collection, introduces the
    686       * {@link com.google.common.cache.CacheLoader} interface for loading entries into the cache
    687       * (allowing checked exceptions to be thrown in the process), and more cleanly separates
    688       * computation from the cache's {@code Map} view.
    689       *
    690       * <p>If an entry's value has not finished computing yet, query methods besides {@code get} return
    691       * immediately as if an entry doesn't exist. In other words, an entry isn't externally visible
    692       * until the value's computation completes.
    693       *
    694       * <p>{@link Map#get} on the returned map will never return {@code null}. It may throw:
    695       *
    696       * <ul>
    697       * <li>{@link NullPointerException} if the key is null or the computing function returns a null
    698       *     result
    699       * <li>{@link ComputationException} if an exception was thrown by the computing function. If that
    700       * exception is already of type {@link ComputationException} it is propagated directly; otherwise
    701       * it is wrapped.
    702       * </ul>
    703       *
    704       * <p><b>Note:</b> Callers of {@code get} <i>must</i> ensure that the key argument is of type
    705       * {@code K}. The {@code get} method accepts {@code Object}, so the key type is not checked at
    706       * compile time. Passing an object of a type other than {@code K} can result in that object being
    707       * unsafely passed to the computing function as type {@code K}, and unsafely stored in the map.
    708       *
    709       * <p>If {@link Map#put} is called before a computation completes, other threads waiting on the
    710       * computation will wake up and return the stored value.
    711       *
    712       * <p>This method does not alter the state of this {@code MapMaker} instance, so it can be invoked
    713       * again to create multiple independent maps.
    714       *
    715       * <p>Insertion, removal, update, and access operations on the returned map safely execute
    716       * concurrently by multiple threads. Iterators on the returned map are weakly consistent,
    717       * returning elements reflecting the state of the map at some point at or since the creation of
    718       * the iterator. They do not throw {@link ConcurrentModificationException}, and may proceed
    719       * concurrently with other operations.
    720       *
    721       * <p>The bulk operations {@code putAll}, {@code equals}, and {@code clear} are not guaranteed to
    722       * be performed atomically on the returned map. Additionally, {@code size} and {@code
    723       * containsValue} are implemented as bulk read operations, and thus may fail to observe concurrent
    724       * writes.
    725       *
    726       * <p>Caching functionality in {@code MapMaker} is being moved to
    727       * {@link com.google.common.cache.CacheBuilder}, with {@link #makeComputingMap} being replaced by
    728       * {@link com.google.common.cache.CacheBuilder#build}. CacheBuilder does not yet support manual
    729       * insertion, so writeable maps should continue using makeComputingMap until release 11.0.
    730       * <b>This method is scheduled for deletion in February 2013.</b>
    731       *
    732       * @param computingFunction the function used to compute new values
    733       * @return a serializable concurrent map having the requested features
    734       */
    735      @Override
    736      @Deprecated
    737      public <K, V> ConcurrentMap<K, V> makeComputingMap(
    738          Function<? super K, ? extends V> computingFunction) {
    739        return useNullMap()
    740            ? new ComputingMapAdapter<K, V>(this, computingFunction)
    741            : new NullComputingConcurrentMap<K, V>(this, computingFunction);
    742      }
    743
    744      /**
    745       * Returns a string representation for this MapMaker instance. The exact form of the returned
    746       * string is not specificed.
    747       */
    748      @Override
    749      public String toString() {
    750        Objects.ToStringHelper s = Objects.toStringHelper(this);
    751        if (initialCapacity != UNSET_INT) {
    752          s.add("initialCapacity", initialCapacity);
    753        }
    754        if (concurrencyLevel != UNSET_INT) {
    755          s.add("concurrencyLevel", concurrencyLevel);
    756        }
    757        if (maximumSize != UNSET_INT) {
    758          s.add("maximumSize", maximumSize);
    759        }
    760        if (expireAfterWriteNanos != UNSET_INT) {
    761          s.add("expireAfterWrite", expireAfterWriteNanos + "ns");
    762        }
    763        if (expireAfterAccessNanos != UNSET_INT) {
    764          s.add("expireAfterAccess", expireAfterAccessNanos + "ns");
    765        }
    766        if (keyStrength != null) {
    767          s.add("keyStrength", Ascii.toLowerCase(keyStrength.toString()));
    768        }
    769        if (valueStrength != null) {
    770          s.add("valueStrength", Ascii.toLowerCase(valueStrength.toString()));
    771        }
    772        if (keyEquivalence != null) {
    773          s.addValue("keyEquivalence");
    774        }
    775        if (valueEquivalence != null) {
    776          s.addValue("valueEquivalence");
    777        }
    778        if (removalListener != null) {
    779          s.addValue("removalListener");
    780        }
    781        return s.toString();
    782      }
    783
    784      /**
    785       * An object that can receive a notification when an entry is removed from a map. The removal
    786       * resulting in notification could have occured to an entry being manually removed or replaced, or
    787       * due to eviction resulting from timed expiration, exceeding a maximum size, or garbage
    788       * collection.
    789       *
    790       * <p>An instance may be called concurrently by multiple threads to process different entries.
    791       * Implementations of this interface should avoid performing blocking calls or synchronizing on
    792       * shared resources.
    793       *
    794       * @param <K> the most general type of keys this listener can listen for; for
    795       *     example {@code Object} if any key is acceptable
    796       * @param <V> the most general type of values this listener can listen for; for
    797       *     example {@code Object} if any key is acceptable
    798       */
    799      interface RemovalListener<K, V> {
    800        /**
    801         * Notifies the listener that a removal occurred at some point in the past.
    802         */
    803        void onRemoval(RemovalNotification<K, V> notification);
    804      }
    805
    806      /**
    807       * A notification of the removal of a single entry. The key or value may be null if it was already
    808       * garbage collected.
    809       *
    810       * <p>Like other {@code Map.Entry} instances associated with MapMaker, this class holds strong
    811       * references to the key and value, regardless of the type of references the map may be using.
    812       */
    813      static final class RemovalNotification<K, V> extends ImmutableEntry<K, V> {
    814        private static final long serialVersionUID = 0;
    815
    816        private final RemovalCause cause;
    817
    818        RemovalNotification(@Nullable K key, @Nullable V value, RemovalCause cause) {
    819          super(key, value);
    820          this.cause = cause;
    821        }
    822
    823        /**
    824         * Returns the cause for which the entry was removed.
    825         */
    826        public RemovalCause getCause() {
    827          return cause;
    828        }
    829
    830        /**
    831         * Returns {@code true} if there was an automatic removal due to eviction (the cause is neither
    832         * {@link RemovalCause#EXPLICIT} nor {@link RemovalCause#REPLACED}).
    833         */
    834        public boolean wasEvicted() {
    835          return cause.wasEvicted();
    836        }
    837      }
    838
    839      /**
    840       * The reason why an entry was removed.
    841       */
    842      enum RemovalCause {
    843        /**
    844         * The entry was manually removed by the user. This can result from the user invoking
    845         * {@link Map#remove}, {@link ConcurrentMap#remove}, or {@link java.util.Iterator#remove}.
    846         */
    847        EXPLICIT {
    848          @Override
    849          boolean wasEvicted() {
    850            return false;
    851          }
    852        },
    853
    854        /**
    855         * The entry itself was not actually removed, but its value was replaced by the user. This can
    856         * result from the user invoking {@link Map#put}, {@link Map#putAll},
    857         * {@link ConcurrentMap#replace(Object, Object)}, or
    858         * {@link ConcurrentMap#replace(Object, Object, Object)}.
    859         */
    860        REPLACED {
    861          @Override
    862          boolean wasEvicted() {
    863            return false;
    864          }
    865        },
    866
    867        /**
    868         * The entry was removed automatically because its key or value was garbage-collected. This
    869         * can occur when using {@link #softKeys}, {@link #softValues}, {@link #weakKeys}, or {@link
    870         * #weakValues}.
    871         */
    872        COLLECTED {
    873          @Override
    874          boolean wasEvicted() {
    875            return true;
    876          }
    877        },
    878
    879        /**
    880         * The entry's expiration timestamp has passed. This can occur when using {@link
    881         * #expireAfterWrite} or {@link #expireAfterAccess}.
    882         */
    883        EXPIRED {
    884          @Override
    885          boolean wasEvicted() {
    886            return true;
    887          }
    888        },
    889
    890        /**
    891         * The entry was evicted due to size constraints. This can occur when using {@link
    892         * #maximumSize}.
    893         */
    894        SIZE {
    895          @Override
    896          boolean wasEvicted() {
    897            return true;
    898          }
    899        };
    900
    901        /**
    902         * Returns {@code true} if there was an automatic removal due to eviction (the cause is neither
    903         * {@link #EXPLICIT} nor {@link #REPLACED}).
    904         */
    905        abstract boolean wasEvicted();
    906      }
    907
    908      /** A map that is always empty and evicts on insertion. */
    909      static class NullConcurrentMap<K, V> extends AbstractMap<K, V>
    910          implements ConcurrentMap<K, V>, Serializable {
    911        private static final long serialVersionUID = 0;
    912
    913        private final RemovalListener<K, V> removalListener;
    914        private final RemovalCause removalCause;
    915
    916        NullConcurrentMap(MapMaker mapMaker) {
    917          removalListener = mapMaker.getRemovalListener();
    918          removalCause = mapMaker.nullRemovalCause;
    919        }
    920
    921        // implements ConcurrentMap
    922
    923        @Override
    924        public boolean containsKey(@Nullable Object key) {
    925          return false;
    926        }
    927
    928        @Override
    929        public boolean containsValue(@Nullable Object value) {
    930          return false;
    931        }
    932
    933        @Override
    934        public V get(@Nullable Object key) {
    935          return null;
    936        }
    937
    938        void notifyRemoval(K key, V value) {
    939          RemovalNotification<K, V> notification =
    940              new RemovalNotification<K, V>(key, value, removalCause);
    941          removalListener.onRemoval(notification);
    942        }
    943
    944        @Override
    945        public V put(K key, V value) {
    946          checkNotNull(key);
    947          checkNotNull(value);
    948          notifyRemoval(key, value);
    949          return null;
    950        }
    951
    952        @Override
    953        public V putIfAbsent(K key, V value) {
    954          return put(key, value);
    955        }
    956
    957        @Override
    958        public V remove(@Nullable Object key) {
    959          return null;
    960        }
    961
    962        @Override
    963        public boolean remove(@Nullable Object key, @Nullable Object value) {
    964          return false;
    965        }
    966
    967        @Override
    968        public V replace(K key, V value) {
    969          checkNotNull(key);
    970          checkNotNull(value);
    971          return null;
    972        }
    973
    974        @Override
    975        public boolean replace(K key, @Nullable V oldValue, V newValue) {
    976          checkNotNull(key);
    977          checkNotNull(newValue);
    978          return false;
    979        }
    980
    981        @Override
    982        public Set<Entry<K, V>> entrySet() {
    983          return Collections.emptySet();
    984        }
    985      }
    986
    987      /** Computes on retrieval and evicts the result. */
    988      static final class NullComputingConcurrentMap<K, V> extends NullConcurrentMap<K, V> {
    989        private static final long serialVersionUID = 0;
    990
    991        final Function<? super K, ? extends V> computingFunction;
    992
    993        NullComputingConcurrentMap(
    994            MapMaker mapMaker, Function<? super K, ? extends V> computingFunction) {
    995          super(mapMaker);
    996          this.computingFunction = checkNotNull(computingFunction);
    997        }
    998
    999        @SuppressWarnings("unchecked") // unsafe, which is why Cache is preferred
    1000        @Override
    1001        public V get(Object k) {
    1002          K key = (K) k;
    1003          V value = compute(key);
    1004          checkNotNull(value, computingFunction + " returned null for key " + key + ".");
    1005          notifyRemoval(key, value);
    1006          return value;
    1007        }
    1008
    1009        private V compute(K key) {
    1010          checkNotNull(key);
    1011          try {
    1012            return computingFunction.apply(key);
    1013          } catch (ComputationException e) {
    1014            throw e;
    1015          } catch (Throwable t) {
    1016            throw new ComputationException(t);
    1017          }
    1018        }
    1019      }
    1020
    1021    }