    001    /*
    002     * Copyright (C) 2009 The Guava Authors
    003     *
    004     * Licensed under the Apache License, Version 2.0 (the "License");
    005     * you may not use this file except in compliance with the License.
    006     * You may obtain a copy of the License at
    007     *
    008     * http://www.apache.org/licenses/LICENSE-2.0
    009     *
    010     * Unless required by applicable law or agreed to in writing, software
    011     * distributed under the License is distributed on an "AS IS" BASIS,
    012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    013     * See the License for the specific language governing permissions and
    014     * limitations under the License.
    015     */
    016
    017    package com.google.common.cache;
    018
    019    import static com.google.common.base.Objects.firstNonNull;
    020    import static com.google.common.base.Preconditions.checkArgument;
    021    import static com.google.common.base.Preconditions.checkNotNull;
    022    import static com.google.common.base.Preconditions.checkState;
    023
    024    import com.google.common.annotations.Beta;
    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.Objects;
    029    import com.google.common.base.Supplier;
    030    import com.google.common.base.Suppliers;
    031    import com.google.common.base.Ticker;
    032    import com.google.common.cache.AbstractCache.SimpleStatsCounter;
    033    import com.google.common.cache.AbstractCache.StatsCounter;
    034    import com.google.common.cache.CustomConcurrentHashMap.Strength;
    035    import com.google.common.collect.ForwardingConcurrentMap;
    036    import com.google.common.util.concurrent.ExecutionError;
    037    import com.google.common.util.concurrent.UncheckedExecutionException;
    038
    039    import java.io.Serializable;
    040    import java.lang.ref.SoftReference;
    041    import java.lang.ref.WeakReference;
    042    import java.util.AbstractMap;
    043    import java.util.Collections;
    044    import java.util.ConcurrentModificationException;
    045    import java.util.Map;
    046    import java.util.Set;
    047    import java.util.concurrent.ConcurrentHashMap;
    048    import java.util.concurrent.ConcurrentMap;
    049    import java.util.concurrent.ExecutionException;
    050    import java.util.concurrent.TimeUnit;
    051
    052    import javax.annotation.CheckReturnValue;
    053    import javax.annotation.Nullable;
    054
    055    /**
    056     * <p>A builder of {@link Cache} instances having any combination of the following features:
    057     *
    058     * <ul>
    059     * <li>least-recently-used eviction when a maximum size is exceeded
    060     * <li>time-based expiration of entries, measured since last access or last write
    061     * <li>keys automatically wrapped in {@linkplain WeakReference weak} references
    062     * <li>values automatically wrapped in {@linkplain WeakReference weak} or
    063     *     {@linkplain SoftReference soft} references
    064     * <li>notification of evicted (or otherwise removed) entries
    065     * </ul>
    066     *
    067     * <p>Usage example: <pre>   {@code
    068     *
    069     *   Cache<Key, Graph> graphs = CacheBuilder.newBuilder()
    070     *       .concurrencyLevel(4)
    071     *       .weakKeys()
    072     *       .maximumSize(10000)
    073     *       .expireAfterWrite(10, TimeUnit.MINUTES)
    074     *       .build(
    075     *           new CacheLoader<Key, Graph>() {
    076     *             public Graph load(Key key) throws AnyException {
    077     *               return createExpensiveGraph(key);
    078     *             }
    079     *           });}</pre>
    080     *
    081     *
    082     * These features are all optional.
    083     *
    084     * <p>The returned cache is implemented as a hash table with similar performance characteristics to
    085     * {@link ConcurrentHashMap}. It implements the optional operations {@link Cache#invalidate},
    086     * {@link Cache#invalidateAll}, {@link Cache#size}, {@link Cache#stats}, and {@link Cache#asMap},
    087     * with the following qualifications:
    088     *
    089     * <ul>
    090     * <li>The {@code invalidateAll} method will invalidate all cached entries prior to returning, and
    091     *     removal notifications will be issued for all invalidated entries.
    092     * <li>The {@code asMap} view (and its collection views) have <i>weakly consistent iterators</i>.
    093     *     This means that they are safe for concurrent use, but if other threads modify the cache after
    094     *     the iterator is created, it is undefined which of these changes, if any, are reflected in
    095     *     that iterator. These iterators never throw {@link ConcurrentModificationException}.
    096     * </ul>
    097     *
    098     * <p><b>Note:</b> by default, the returned cache uses equality comparisons (the
    099     * {@link Object#equals equals} method) to determine equality for keys or values. However, if
    100     * {@link #weakKeys} was specified, the cache uses identity ({@code ==})
    101     * comparisons instead for keys. Likewise, if {@link #weakValues} or {@link #softValues} was
    102     * specified, the cache uses identity comparisons for values.
    103     *
    104     * <p>If soft or weak references were requested, it is possible for a key or value present in the
    105     * the cache to be reclaimed by the garbage collector. If this happens, the entry automatically
    106     * disappears from the cache. A partially-reclaimed entry is never exposed to the user.
    107     *
    108     * <p>Certain cache configurations will result in the accrual of periodic maintenance tasks which
    109     * will be performed during write operations, or during occasional read operations in the absense of
    110     * writes. The {@link Cache#cleanUp} method of the returned cache will also perform maintenance, but
    111     * calling it should not be necessary with a high throughput cache. Only caches built with
    112     * {@linkplain CacheBuilder#removalListener removalListener},
    113     * {@linkplain CacheBuilder#expireAfterWrite expireAfterWrite},
    114     * {@linkplain CacheBuilder#expireAfterAccess expireAfterAccess},
    115     * {@linkplain CacheBuilder#weakKeys weakKeys}, {@linkplain CacheBuilder#weakValues weakValues},
    116     * or {@linkplain CacheBuilder#softValues softValues} perform periodic maintenance.
    117     *
    118     * <p>The caches produced by {@code CacheBuilder} are serializable, and the deserialized caches
    119     * retain all the configuration properties of the original cache. Note that the serialized form does
    120     * <i>not</i> include cache contents, but only configuration.
    121     *
    122     * @param <K> the base key type for all caches created by this builder
    123     * @param <V> the base value type for all caches created by this builder
    124     * @author Charles Fry
    125     * @author Kevin Bourrillion
    126     * @since 10.0
    127     */
    128    @Beta
    129    public final class CacheBuilder<K, V> {
    130      private static final int DEFAULT_INITIAL_CAPACITY = 16;
    131      private static final int DEFAULT_CONCURRENCY_LEVEL = 4;
    132      private static final int DEFAULT_EXPIRATION_NANOS = 0;
    133
    134      static final Supplier<? extends StatsCounter> DEFAULT_STATS_COUNTER = Suppliers.ofInstance(
    135          new StatsCounter() {
    136            @Override
    137            public void recordHit() {}
    138
    139            @Override
    140            public void recordLoadSuccess(long loadTime) {}
    141
    142            @Override
    143            public void recordLoadException(long loadTime) {}
    144
    145            @Override
    146            public void recordConcurrentMiss() {}
    147
    148            @Override
    149            public void recordEviction() {}
    150
    151            @Override
    152            public CacheStats snapshot() {
    153              return EMPTY_STATS;
    154            }
    155          });
    156      static final CacheStats EMPTY_STATS = new CacheStats(0, 0, 0, 0, 0, 0);
    157
    158      static final Supplier<SimpleStatsCounter> CACHE_STATS_COUNTER =
    159          new Supplier<SimpleStatsCounter>() {
    160        @Override
    161        public SimpleStatsCounter get() {
    162          return new SimpleStatsCounter();
    163        }
    164      };
    165
    166      enum NullListener implements RemovalListener<Object, Object> {
    167        INSTANCE;
    168
    169        @Override
    170        public void onRemoval(RemovalNotification<Object, Object> notification) {}
    171      }
    172
    173      static final int UNSET_INT = -1;
    174
    175      int initialCapacity = UNSET_INT;
    176      int concurrencyLevel = UNSET_INT;
    177      int maximumSize = UNSET_INT;
    178
    179      Strength keyStrength;
    180      Strength valueStrength;
    181
    182      long expireAfterWriteNanos = UNSET_INT;
    183      long expireAfterAccessNanos = UNSET_INT;
    184
    185      RemovalCause nullRemovalCause;
    186
    187      Equivalence<Object> keyEquivalence;
    188      Equivalence<Object> valueEquivalence;
    189
    190      RemovalListener<? super K, ? super V> removalListener;
    191
    192      Ticker ticker;
    193
    194      // TODO(fry): make constructor private and update tests to use newBuilder
    195      CacheBuilder() {}
    196
    197      /**
    198       * Constructs a new {@code CacheBuilder} instance with default settings, including strong keys,
    199       * strong values, and no automatic eviction of any kind.
    200       */
    201      public static CacheBuilder<Object, Object> newBuilder() {
    202        return new CacheBuilder<Object, Object>();
    203      }
    204
    205      private boolean useNullCache() {
    206        return (nullRemovalCause == null);
    207      }
    208
    209      /**
    210       * Sets a custom {@code Equivalence} strategy for comparing keys.
    211       *
    212       * <p>By default, the cache uses {@link Equivalences#identity} to determine key equality when
    213       * {@link #weakKeys} is specified, and {@link Equivalences#equals()} otherwise.
    214       */
    215      CacheBuilder<K, V> keyEquivalence(Equivalence<Object> equivalence) {
    216        checkState(keyEquivalence == null, "key equivalence was already set to %s", keyEquivalence);
    217        keyEquivalence = checkNotNull(equivalence);
    218        return this;
    219      }
    220
    221      Equivalence<Object> getKeyEquivalence() {
    222        return firstNonNull(keyEquivalence, getKeyStrength().defaultEquivalence());
    223      }
    224
    225      /**
    226       * Sets a custom {@code Equivalence} strategy for comparing values.
    227       *
    228       * <p>By default, the cache uses {@link Equivalences#identity} to determine value equality when
    229       * {@link #weakValues} or {@link #softValues} is specified, and {@link Equivalences#equals()}
    230       * otherwise.
    231       */
    232      CacheBuilder<K, V> valueEquivalence(Equivalence<Object> equivalence) {
    233        checkState(valueEquivalence == null,
    234            "value equivalence was already set to %s", valueEquivalence);
    235        this.valueEquivalence = checkNotNull(equivalence);
    236        return this;
    237      }
    238
    239      Equivalence<Object> getValueEquivalence() {
    240        return firstNonNull(valueEquivalence, getValueStrength().defaultEquivalence());
    241      }
    242
    243      /**
    244       * Sets the minimum total size for the internal hash tables. For example, if the initial capacity
    245       * is {@code 60}, and the concurrency level is {@code 8}, then eight segments are created, each
    246       * having a hash table of size eight. Providing a large enough estimate at construction time
    247       * avoids the need for expensive resizing operations later, but setting this value unnecessarily
    248       * high wastes memory.
    249       *
    250       * @throws IllegalArgumentException if {@code initialCapacity} is negative
    251       * @throws IllegalStateException if an initial capacity was already set
    252       */
    253      public CacheBuilder<K, V> initialCapacity(int initialCapacity) {
    254        checkState(this.initialCapacity == UNSET_INT, "initial capacity was already set to %s",
    255            this.initialCapacity);
    256        checkArgument(initialCapacity >= 0);
    257        this.initialCapacity = initialCapacity;
    258        return this;
    259      }
    260
    261      int getInitialCapacity() {
    262        return (initialCapacity == UNSET_INT) ? DEFAULT_INITIAL_CAPACITY : initialCapacity;
    263      }
    264
    265      /**
    266       * Guides the allowed concurrency among update operations. Used as a hint for internal sizing. The
    267       * table is internally partitioned to try to permit the indicated number of concurrent updates
    268       * without contention. Because assignment of entries to these partitions is not necessarily
    269       * uniform, the actual concurrency observed may vary. Ideally, you should choose a value to
    270       * accommodate as many threads as will ever concurrently modify the table. Using a significantly
    271       * higher value than you need can waste space and time, and a significantly lower value can lead
    272       * to thread contention. But overestimates and underestimates within an order of magnitude do not
    273       * usually have much noticeable impact. A value of one permits only one thread to modify the cache
    274       * at a time, but since read operations can proceed concurrently, this still yields higher
    275       * concurrency than full synchronization. Defaults to 4.
    276       *
    277       * <p><b>Note:</b>The default may change in the future. If you care about this value, you should
    278       * always choose it explicitly.
    279       *
    280       * @throws IllegalArgumentException if {@code concurrencyLevel} is nonpositive
    281       * @throws IllegalStateException if a concurrency level was already set
    282       */
    283      public CacheBuilder<K, V> concurrencyLevel(int concurrencyLevel) {
    284        checkState(this.concurrencyLevel == UNSET_INT, "concurrency level was already set to %s",
    285            this.concurrencyLevel);
    286        checkArgument(concurrencyLevel > 0);
    287        this.concurrencyLevel = concurrencyLevel;
    288        return this;
    289      }
    290
    291      int getConcurrencyLevel() {
    292        return (concurrencyLevel == UNSET_INT) ? DEFAULT_CONCURRENCY_LEVEL : concurrencyLevel;
    293      }
    294
    295      /**
    296       * Specifies the maximum number of entries the cache may contain. Note that the cache <b>may evict
    297       * an entry before this limit is exceeded</b>. As the cache size grows close to the maximum, the
    298       * cache evicts entries that are less likely to be used again. For example, the cache may evict an
    299       * entry because it hasn't been used recently or very often.
    300       *
    301       * <p>When {@code size} is zero, elements will be evicted immediately after being loaded into the
    302       * cache. This has the same effect as invoking {@link #expireAfterWrite
    303       * expireAfterWrite}{@code (0, unit)} or {@link #expireAfterAccess expireAfterAccess}{@code (0,
    304       * unit)}. It can be useful in testing, or to disable caching temporarily without a code change.
    305       *
    306       * @param size the maximum size of the cache
    307       * @throws IllegalArgumentException if {@code size} is negative
    308       * @throws IllegalStateException if a maximum size was already set
    309       */
    310      public CacheBuilder<K, V> maximumSize(int size) {
    311        checkState(this.maximumSize == UNSET_INT, "maximum size was already set to %s",
    312            this.maximumSize);
    313        checkArgument(size >= 0, "maximum size must not be negative");
    314        this.maximumSize = size;
    315        if (maximumSize == 0) {
    316          // SIZE trumps EXPIRED
    317          this.nullRemovalCause = RemovalCause.SIZE;
    318        }
    319        return this;
    320      }
    321
    322      /**
    323       * Specifies that each key (not value) stored in the cache should be strongly referenced.
    324       *
    325       * @throws IllegalStateException if the key strength was already set
    326       */
    327      CacheBuilder<K, V> strongKeys() {
    328        return setKeyStrength(Strength.STRONG);
    329      }
    330
    331      /**
    332       * Specifies that each key (not value) stored in the cache should be wrapped in a {@link
    333       * WeakReference} (by default, strong references are used).
    334       *
    335       * <p><b>Warning:</b> when this method is used, the resulting cache will use identity ({@code ==})
    336       * comparison to determine equality of keys.
    337       *
    338       * <p>Entries with keys that have been garbage collected may be counted by {@link Cache#size}, but
    339       * will never be visible to read or write operations. Entries with garbage collected keys are
    340       * cleaned up as part of the routine maintenance described in the class javadoc.
    341       *
    342       * @throws IllegalStateException if the key strength was already set
    343       */
    344      public CacheBuilder<K, V> weakKeys() {
    345        return setKeyStrength(Strength.WEAK);
    346      }
    347
    348      CacheBuilder<K, V> setKeyStrength(Strength strength) {
    349        checkState(keyStrength == null, "Key strength was already set to %s", keyStrength);
    350        keyStrength = checkNotNull(strength);
    351        return this;
    352      }
    353
    354      Strength getKeyStrength() {
    355        return firstNonNull(keyStrength, Strength.STRONG);
    356      }
    357
    358      /**
    359       * Specifies that each value (not key) stored in the cache should be strongly referenced.
    360       *
    361       * @throws IllegalStateException if the value strength was already set
    362       */
    363      CacheBuilder<K, V> strongValues() {
    364        return setValueStrength(Strength.STRONG);
    365      }
    366
    367      /**
    368       * Specifies that each value (not key) stored in the cache should be wrapped in a
    369       * {@link WeakReference} (by default, strong references are used).
    370       *
    371       * <p>Weak values will be garbage collected once they are weakly reachable. This makes them a poor
    372       * candidate for caching; consider {@link #softValues} instead.
    373       *
    374       * <p><b>Note:</b> when this method is used, the resulting cache will use identity ({@code ==})
    375       * comparison to determine equality of values.
    376       *
    377       * <p>Entries with values that have been garbage collected may be counted by {@link Cache#size},
    378       * but will never be visible to read or write operations. Entries with garbage collected keys are
    379       * cleaned up as part of the routine maintenance described in the class javadoc.
    380       *
    381       * @throws IllegalStateException if the value strength was already set
    382       */
    383      public CacheBuilder<K, V> weakValues() {
    384        return setValueStrength(Strength.WEAK);
    385      }
    386
    387      /**
    388       * Specifies that each value (not key) stored in the cache should be wrapped in a
    389       * {@link SoftReference} (by default, strong references are used). Softly-referenced objects will
    390       * be garbage-collected in a <i>globally</i> least-recently-used manner, in response to memory
    391       * demand.
    392       *
    393       * <p><b>Warning:</b> in most circumstances it is better to set a per-cache {@linkplain
    394       * #maximumSize maximum size} instead of using soft references. You should only use this method if
    395       * you are well familiar with the practical consequences of soft references.
    396       *
    397       * <p><b>Note:</b> when this method is used, the resulting cache will use identity ({@code ==})
    398       * comparison to determine equality of values.
    399       *
    400       * <p>Entries with values that have been garbage collected may be counted by {@link Cache#size},
    401       * but will never be visible to read or write operations. Entries with garbage collected values
    402       * are cleaned up as part of the routine maintenance described in the class javadoc.
    403       *
    404       * @throws IllegalStateException if the value strength was already set
    405       */
    406      public CacheBuilder<K, V> softValues() {
    407        return setValueStrength(Strength.SOFT);
    408      }
    409
    410      CacheBuilder<K, V> setValueStrength(Strength strength) {
    411        checkState(valueStrength == null, "Value strength was already set to %s", valueStrength);
    412        valueStrength = checkNotNull(strength);
    413        return this;
    414      }
    415
    416      Strength getValueStrength() {
    417        return firstNonNull(valueStrength, Strength.STRONG);
    418      }
    419
    420      /**
    421       * Specifies that each entry should be automatically removed from the cache once a fixed duration
    422       * has elapsed after the entry's creation, or the most recent replacement of its value.
    423       *
    424       * <p>When {@code duration} is zero, elements will be evicted immediately after being loaded into
    425       * the cache. This has the same effect as invoking {@link #maximumSize maximumSize}{@code (0)}. It
    426       * can be useful in testing, or to disable caching temporarily without a code change.
    427       *
    428       * <p>Expired entries may be counted by {@link Cache#size}, but will never be visible to read or
    429       * write operations. Expired entries are cleaned up as part of the routine maintenance described
    430       * in the class javadoc.
    431       *
    432       * @param duration the length of time after an entry is created that it should be automatically
    433       *     removed
    434       * @param unit the unit that {@code duration} is expressed in
    435       * @throws IllegalArgumentException if {@code duration} is negative
    436       * @throws IllegalStateException if the time to live or time to idle was already set
    437       */
    438      public CacheBuilder<K, V> expireAfterWrite(long duration, TimeUnit unit) {
    439        checkExpiration(duration, unit);
    440        this.expireAfterWriteNanos = unit.toNanos(duration);
    441        if (duration == 0 && this.nullRemovalCause == null) {
    442          // SIZE trumps EXPIRED
    443          this.nullRemovalCause = RemovalCause.EXPIRED;
    444        }
    445        return this;
    446      }
    447
    448      private void checkExpiration(long duration, TimeUnit unit) {
    449        checkState(expireAfterWriteNanos == UNSET_INT, "expireAfterWrite was already set to %s ns",
    450            expireAfterWriteNanos);
    451        checkState(expireAfterAccessNanos == UNSET_INT, "expireAfterAccess was already set to %s ns",
    452            expireAfterAccessNanos);
    453        checkArgument(duration >= 0, "duration cannot be negative: %s %s", duration, unit);
    454      }
    455
    456      long getExpireAfterWriteNanos() {
    457        return (expireAfterWriteNanos == UNSET_INT) ? DEFAULT_EXPIRATION_NANOS : expireAfterWriteNanos;
    458      }
    459
    460      /**
    461       * Specifies that each entry should be automatically removed from the cache once a fixed duration
    462       * has elapsed after the entry's creation, or last access. Access time is reset by
    463       * {@link Cache#get} and {@link Cache#getUnchecked}, but not by operations on the view returned by
    464       * {@link Cache#asMap}.
    465       *
    466       * <p>When {@code duration} is zero, elements will be evicted immediately after being loaded into
    467       * the cache. This has the same effect as invoking {@link #maximumSize maximumSize}{@code (0)}. It
    468       * can be useful in testing, or to disable caching temporarily without a code change.
    469       *
    470       * <p>Expired entries may be counted by {@link Cache#size}, but will never be visible to read or
    471       * write operations. Expired entries are cleaned up as part of the routine maintenance described
    472       * in the class javadoc.
    473       *
    474       * @param duration the length of time after an entry is last accessed that it should be
    475       *     automatically removed
    476       * @param unit the unit that {@code duration} is expressed in
    477       * @throws IllegalArgumentException if {@code duration} is negative
    478       * @throws IllegalStateException if the time to idle or time to live was already set
    479       */
    480      public CacheBuilder<K, V> expireAfterAccess(long duration, TimeUnit unit) {
    481        checkExpiration(duration, unit);
    482        this.expireAfterAccessNanos = unit.toNanos(duration);
    483        if (duration == 0 && this.nullRemovalCause == null) {
    484          // SIZE trumps EXPIRED
    485          this.nullRemovalCause = RemovalCause.EXPIRED;
    486        }
    487        return this;
    488      }
    489
    490      long getExpireAfterAccessNanos() {
    491        return (expireAfterAccessNanos == UNSET_INT)
    492            ? DEFAULT_EXPIRATION_NANOS : expireAfterAccessNanos;
    493      }
    494
    495      /**
    496       * Specifies a nanosecond-precision time source for use in determining when entries should be
    497       * expired. By default, {@link System#nanoTime} is used.
    498       *
    499       * <p>The primary intent of this method is to facilitate testing of caches which have been
    500       * configured with {@link #expireAfterWrite} or {@link #expireAfterAccess}.
    501       *
    502       * @throws IllegalStateException if a ticker was already set
    503       */
    504      public CacheBuilder<K, V> ticker(Ticker ticker) {
    505        checkState(this.ticker == null);
    506        this.ticker = checkNotNull(ticker);
    507        return this;
    508      }
    509
    510      Ticker getTicker() {
    511        return firstNonNull(ticker, Ticker.systemTicker());
    512      }
    513
    514      /**
    515       * Specifies a listener instance, which all caches built using this {@code CacheBuilder} will
    516       * notify each time an entry is removed from the cache by any means.
    517       *
    518       * <p>Each cache built by this {@code CacheBuilder} after this method is called invokes the
    519       * supplied listener after removing an element for any reason (see removal causes in {@link
    520       * RemovalCause}). It will invoke the listener as part of the routine maintenance described
    521       * in the class javadoc.
    522       *
    523       * <p><b>Important note:</b> Instead of returning <em>this</em> as a {@code CacheBuilder}
    524       * instance, this method returns {@code CacheBuilder<K1, V1>}. From this point on, either the
    525       * original reference or the returned reference may be used to complete configuration and build
    526       * the cache, but only the "generic" one is type-safe. That is, it will properly prevent you from
    527       * building caches whose key or value types are incompatible with the types accepted by the
    528       * listener already provided; the {@code CacheBuilder} type cannot do this. For best results,
    529       * simply use the standard method-chaining idiom, as illustrated in the documentation at top,
    530       * configuring a {@code CacheBuilder} and building your {@link Cache} all in a single statement.
    531       *
    532       * <p><b>Warning:</b> if you ignore the above advice, and use this {@code CacheBuilder} to build
    533       * a cache whose key or value type is incompatible with the listener, you will likely experience
    534       * a {@link ClassCastException} at some <i>undefined</i> point in the future.
    535       *
    536       * @throws IllegalStateException if a removal listener was already set
    537       */
    538      @CheckReturnValue
    539      public <K1 extends K, V1 extends V> CacheBuilder<K1, V1> removalListener(
    540          RemovalListener<? super K1, ? super V1> listener) {
    541        checkState(this.removalListener == null);
    542
    543        // safely limiting the kinds of caches this can produce
    544        @SuppressWarnings("unchecked")
    545        CacheBuilder<K1, V1> me = (CacheBuilder<K1, V1>) this;
    546        me.removalListener = checkNotNull(listener);
    547        return me;
    548      }
    549
    550      // Make a safe contravariant cast now so we don't have to do it over and over.
    551      @SuppressWarnings("unchecked")
    552      <K1 extends K, V1 extends V> RemovalListener<K1, V1> getRemovalListener() {
    553        return (RemovalListener<K1, V1>) Objects.firstNonNull(removalListener, NullListener.INSTANCE);
    554      }
    555
    556      /**
    557       * Builds a cache, which either returns an already-loaded value for a given key or atomically
    558       * computes or retrieves it using the supplied {@code CacheLoader}. If another thread is currently
    559       * loading the value for this key, simply waits for that thread to finish and returns its
    560       * loaded value. Note that multiple threads can concurrently load values for distinct keys.
    561       *
    562       * <p>This method does not alter the state of this {@code CacheBuilder} instance, so it can be
    563       * invoked again to create multiple independent caches.
    564       *
    565       * @param loader the cache loader used to obtain new values
    566       * @return a cache having the requested features
    567       */
    568      public <K1 extends K, V1 extends V> Cache<K1, V1> build(CacheLoader<? super K1, V1> loader) {
    569        return useNullCache()
    570            ? new ComputingCache<K1, V1>(this, CACHE_STATS_COUNTER, loader)
    571            : new NullCache<K1, V1>(this, CACHE_STATS_COUNTER, loader);
    572      }
    573
    574      /**
    575       * Returns a string representation for this CacheBuilder instance. The exact form of the returned
    576       * string is not specificed.
    577       */
    578      @Override
    579      public String toString() {
    580        Objects.ToStringHelper s = Objects.toStringHelper(this);
    581        if (initialCapacity != UNSET_INT) {
    582          s.add("initialCapacity", initialCapacity);
    583        }
    584        if (concurrencyLevel != UNSET_INT) {
    585          s.add("concurrencyLevel", concurrencyLevel);
    586        }
    587        if (maximumSize != UNSET_INT) {
    588          s.add("maximumSize", maximumSize);
    589        }
    590        if (expireAfterWriteNanos != UNSET_INT) {
    591          s.add("expireAfterWrite", expireAfterWriteNanos + "ns");
    592        }
    593        if (expireAfterAccessNanos != UNSET_INT) {
    594          s.add("expireAfterAccess", expireAfterAccessNanos + "ns");
    595        }
    596        if (keyStrength != null) {
    597          s.add("keyStrength", Ascii.toLowerCase(keyStrength.toString()));
    598        }
    599        if (valueStrength != null) {
    600          s.add("valueStrength", Ascii.toLowerCase(valueStrength.toString()));
    601        }
    602        if (keyEquivalence != null) {
    603          s.addValue("keyEquivalence");
    604        }
    605        if (valueEquivalence != null) {
    606          s.addValue("valueEquivalence");
    607        }
    608        if (removalListener != null) {
    609          s.addValue("removalListener");
    610        }
    611        return s.toString();
    612      }
    613
    614      /** A map that is always empty and evicts on insertion. */
    615      static class NullConcurrentMap<K, V> extends AbstractMap<K, V>
    616          implements ConcurrentMap<K, V>, Serializable {
    617        private static final long serialVersionUID = 0;
    618
    619        private final RemovalListener<K, V> removalListener;
    620        private final RemovalCause removalCause;
    621
    622        NullConcurrentMap(CacheBuilder<? super K, ? super V> builder) {
    623          removalListener = builder.getRemovalListener();
    624          removalCause = builder.nullRemovalCause;
    625        }
    626
    627        // implements ConcurrentMap
    628
    629        @Override
    630        public boolean containsKey(@Nullable Object key) {
    631          return false;
    632        }
    633
    634        @Override
    635        public boolean containsValue(@Nullable Object value) {
    636          return false;
    637        }
    638
    639        @Override
    640        public V get(@Nullable Object key) {
    641          return null;
    642        }
    643
    644        void notifyRemoval(K key, V value) {
    645          RemovalNotification<K, V> notification =
    646              new RemovalNotification<K, V>(key, value, removalCause);
    647          removalListener.onRemoval(notification);
    648        }
    649
    650        @Override
    651        public V put(K key, V value) {
    652          checkNotNull(key);
    653          checkNotNull(value);
    654          notifyRemoval(key, value);
    655          return null;
    656        }
    657
    658        @Override
    659        public V putIfAbsent(K key, V value) {
    660          return put(key, value);
    661        }
    662
    663        @Override
    664        public V remove(@Nullable Object key) {
    665          return null;
    666        }
    667
    668        @Override
    669        public boolean remove(@Nullable Object key, @Nullable Object value) {
    670          return false;
    671        }
    672
    673        @Override
    674        public V replace(K key, V value) {
    675          checkNotNull(key);
    676          checkNotNull(value);
    677          return null;
    678        }
    679
    680        @Override
    681        public boolean replace(K key, @Nullable V oldValue, V newValue) {
    682          checkNotNull(key);
    683          checkNotNull(newValue);
    684          return false;
    685        }
    686
    687        @Override
    688        public Set<Entry<K, V>> entrySet() {
    689          return Collections.emptySet();
    690        }
    691      }
    692
    693      // TODO(fry): remove, as no code path can hit this
    694      /** Computes on retrieval and evicts the result. */
    695      static final class NullComputingConcurrentMap<K, V> extends NullConcurrentMap<K, V> {
    696        private static final long serialVersionUID = 0;
    697
    698        final CacheLoader<? super K, ? extends V> loader;
    699
    700        NullComputingConcurrentMap(CacheBuilder<? super K, ? super V> builder,
    701            CacheLoader<? super K, ? extends V> loader) {
    702          super(builder);
    703          this.loader = checkNotNull(loader);
    704        }
    705
    706        @SuppressWarnings("unchecked") // unsafe, which is why Cache is preferred
    707        @Override
    708        public V get(Object k) {
    709          K key = (K) k;
    710          V value = compute(key);
    711          checkNotNull(value, loader + " returned null for key " + key + ".");
    712          notifyRemoval(key, value);
    713          return value;
    714        }
    715
    716        private V compute(K key) {
    717          checkNotNull(key);
    718          try {
    719            return loader.load(key);
    720          } catch (Exception e) {
    721            throw new UncheckedExecutionException(e);
    722          } catch (Error e) {
    723            throw new ExecutionError(e);
    724          }
    725        }
    726      }
    727
    728      /** Computes on retrieval and evicts the result. */
    729      static final class NullCache<K, V> extends AbstractCache<K, V> {
    730        final NullConcurrentMap<K, V> map;
    731        final CacheLoader<? super K, V> loader;
    732
    733        final StatsCounter statsCounter;
    734
    735        NullCache(CacheBuilder<? super K, ? super V> builder,
    736            Supplier<? extends StatsCounter> statsCounterSupplier,
    737            CacheLoader<? super K, V> loader) {
    738          this.map = new NullConcurrentMap<K, V>(builder);
    739          this.statsCounter = statsCounterSupplier.get();
    740          this.loader = checkNotNull(loader);
    741        }
    742
    743        @Override
    744        public V get(K key) throws ExecutionException {
    745          V value = compute(key);
    746          map.notifyRemoval(key, value);
    747          return value;
    748        }
    749
    750        private V compute(K key) throws ExecutionException {
    751          checkNotNull(key);
    752          long start = System.nanoTime();
    753          V value = null;
    754          try {
    755            value = loader.load(key);
    756          } catch (RuntimeException e) {
    757            throw new UncheckedExecutionException(e);
    758          } catch (Exception e) {
    759            throw new ExecutionException(e);
    760          } catch (Error e) {
    761            throw new ExecutionError(e);
    762          } finally {
    763            long elapsed = System.nanoTime() - start;
    764            if (value == null) {
    765              statsCounter.recordLoadException(elapsed);
    766            } else {
    767              statsCounter.recordLoadSuccess(elapsed);
    768            }
    769            statsCounter.recordEviction();
    770          }
    771          if (value == null) {
    772            throw new NullPointerException();
    773          } else {
    774            return value;
    775          }
    776        }
    777
    778        @Override
    779        public long size() {
    780          return 0;
    781        }
    782
    783        @Override
    784        public void invalidate(Object key) {
    785          // no-op
    786        }
    787
    788        @Override public void invalidateAll() {
    789          // no-op
    790        }
    791
    792        @Override
    793        public CacheStats stats() {
    794          return statsCounter.snapshot();
    795        }
    796
    797        ConcurrentMap<K, V> asMap;
    798
    799        @Override
    800        public ConcurrentMap<K, V> asMap() {
    801          ConcurrentMap<K, V> am = asMap;
    802          return (am != null) ? am : (asMap = new CacheAsMap<K, V>(map));
    803        }
    804      }
    805
    806      static final class CacheAsMap<K, V> extends ForwardingConcurrentMap<K, V> {
    807        private final ConcurrentMap<K, V> delegate;
    808
    809        CacheAsMap(ConcurrentMap<K, V> delegate) {
    810          this.delegate = delegate;
    811        }
    812
    813        @Override
    814        protected ConcurrentMap<K, V> delegate() {
    815          return delegate;
    816        }
    817
    818        @Override
    819        public V put(K key, V value) {
    820          throw new UnsupportedOperationException();
    821        }
    822
    823        @Override
    824        public void putAll(Map<? extends K, ? extends V> map) {
    825          throw new UnsupportedOperationException();
    826        }
    827
    828        @Override
    829        public V putIfAbsent(K key, V value) {
    830          throw new UnsupportedOperationException();
    831        }
    832
    833        @Override
    834        public V replace(K key, V value) {
    835          throw new UnsupportedOperationException();
    836        }
    837
    838        @Override
    839        public boolean replace(K key, V oldValue, V newValue) {
    840          throw new UnsupportedOperationException();
    841        }
    842      }
    843
    844    }