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.collect;
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.annotations.GwtCompatible;
026    import com.google.common.annotations.GwtIncompatible;
027    import com.google.common.base.Ascii;
028    import com.google.common.base.Equivalence;
029    import com.google.common.base.Function;
030    import com.google.common.base.Objects;
031    import com.google.common.base.Ticker;
032    import com.google.common.collect.CustomConcurrentHashMap.Strength;
033    
034    import java.io.Serializable;
035    import java.lang.ref.SoftReference;
036    import java.lang.ref.WeakReference;
037    import java.util.AbstractMap;
038    import java.util.Collections;
039    import java.util.Map;
040    import java.util.Set;
041    import java.util.concurrent.ConcurrentHashMap;
042    import java.util.concurrent.ConcurrentMap;
043    import java.util.concurrent.Executor;
044    import java.util.concurrent.TimeUnit;
045    
046    /**
047     * <p>A {@link ConcurrentMap} builder, providing any combination of these
048     * features: {@linkplain SoftReference soft} or {@linkplain WeakReference
049     * weak} keys, soft or weak values, size-based evicition, timed expiration, and
050     * on-demand computation of values. Usage example: <pre>   {@code
051     *
052     *   ConcurrentMap<Key, Graph> graphs = new MapMaker()
053     *       .concurrencyLevel(4)
054     *       .softKeys()
055     *       .weakValues()
056     *       .maximumSize(10000)
057     *       .expireAfterWrite(10, TimeUnit.MINUTES)
058     *       .makeComputingMap(
059     *           new Function<Key, Graph>() {
060     *             public Graph apply(Key key) {
061     *               return createExpensiveGraph(key);
062     *             }
063     *           });}</pre>
064     *
065     * These features are all optional; {@code new MapMaker().makeMap()}
066     * returns a valid concurrent map that behaves exactly like a
067     * {@link ConcurrentHashMap}.
068     *
069     * The returned map is implemented as a hash table with similar performance
070     * characteristics to {@link ConcurrentHashMap}. It supports all optional
071     * operations of the {@code ConcurrentMap} interface. It does not permit
072     * null keys or values.
073     *
074     * <p><b>Note:</b> by default, the returned map uses equality comparisons
075     * (the {@link Object#equals(Object) equals} method) to determine equality
076     * for keys or values. However, if {@link #weakKeys()} or {@link
077     * #softKeys()} was specified, the map uses identity ({@code ==})
078     * comparisons instead for keys. Likewise, if {@link #weakValues()} or
079     * {@link #softValues()} was specified, the map uses identity comparisons
080     * for values.
081     *
082     * <p>The returned map has <i>weakly consistent iteration</i>: an iterator
083     * over one of the map's view collections may reflect some, all or none of
084     * the changes made to the map after the iterator was created.
085     *
086     * <p>An entry whose key or value is reclaimed by the garbage collector
087     * immediately disappears from the map. (If the default settings of strong
088     * keys and strong values are used, this will never happen.) The client can
089     * never observe a partially-reclaimed entry. Any {@link java.util.Map.Entry}
090     * instance retrieved from the map's {@linkplain Map#entrySet() entry set}
091     * is a snapshot of that entry's state at the time of retrieval; such entries
092     * do, however, support {@link java.util.Map.Entry#setValue}.
093     *
094     * <p>The maps produced by {@code MapMaker} are serializable, and the
095     * deserialized maps retain all the configuration properties of the original
096     * map. If the map uses soft or weak references, the entries will be
097     * reconstructed as they were, but there is no guarantee that the entries won't
098     * be immediately reclaimed.
099     *
100     * <p>{@code new MapMaker().weakKeys().makeMap()} can almost always be
101     * used as a drop-in replacement for {@link java.util.WeakHashMap}, adding
102     * concurrency, asynchronous cleanup, identity-based equality for keys, and
103     * great flexibility.
104     *
105     * @author Bob Lee
106     * @author Kevin Bourrillion
107     * @since 2 (imported from Google Collections Library)
108     */
109    @GwtCompatible(emulated = true)
110    public final class MapMaker extends GenericMapMaker<Object, Object> {
111      private static final int DEFAULT_INITIAL_CAPACITY = 16;
112      private static final int DEFAULT_CONCURRENCY_LEVEL = 4;
113      private static final int DEFAULT_EXPIRATION_NANOS = 0;
114    
115      static final Executor DEFAULT_CLEANUP_EXECUTOR =
116          new Executor() {
117            @Override
118            public void execute(Runnable r) {
119              r.run();
120            }
121          };
122    
123      static final Ticker DEFAULT_TICKER =
124          new Ticker() {
125            @Override
126            public long read() {
127              return System.nanoTime();
128            }
129          };
130    
131      @SuppressWarnings("unchecked")
132      enum NullListener implements MapEvictionListener {
133        INSTANCE;
134        @Override public void onEviction(Object key, Object value) {}
135      }
136    
137      static final int UNSET_INT = -1;
138    
139      int initialCapacity = UNSET_INT;
140      int concurrencyLevel = UNSET_INT;
141      int maximumSize = UNSET_INT;
142    
143      Strength keyStrength;
144      Strength valueStrength;
145    
146      long expireAfterWriteNanos = UNSET_INT;
147      long expireAfterAccessNanos = UNSET_INT;
148    
149      // TODO(kevinb): dispense with this after benchmarking
150      boolean useCustomMap;
151      boolean useNullMap;
152    
153      Equivalence<Object> keyEquivalence;
154      Equivalence<Object> valueEquivalence;
155    
156      Executor cleanupExecutor;
157      Ticker ticker;
158    
159      /**
160       * Constructs a new {@code MapMaker} instance with default settings,
161       * including strong keys, strong values, and no automatic expiration.
162       */
163      public MapMaker() {}
164    
165      // TODO(kevinb): undo this indirection if keyEquiv gets released
166      MapMaker privateKeyEquivalence(Equivalence<Object> equivalence) {
167        checkState(keyEquivalence == null,
168            "key equivalence was already set to %s", keyEquivalence);
169        keyEquivalence = checkNotNull(equivalence);
170        this.useCustomMap = true;
171        return this;
172      }
173    
174      Equivalence<Object> getKeyEquivalence() {
175        return firstNonNull(keyEquivalence, getKeyStrength().defaultEquivalence());
176      }
177    
178      // TODO(kevinb): undo this indirection if valueEquiv gets released
179      MapMaker privateValueEquivalence(Equivalence<Object> equivalence) {
180        checkState(valueEquivalence == null,
181            "value equivalence was already set to %s", valueEquivalence);
182        this.valueEquivalence = checkNotNull(equivalence);
183        this.useCustomMap = true;
184        return this;
185      }
186    
187      Equivalence<Object> getValueEquivalence() {
188        return firstNonNull(valueEquivalence,
189            getValueStrength().defaultEquivalence());
190      }
191    
192      /**
193       * Sets a custom initial capacity (defaults to 16). Resizing this or
194       * any other kind of hash table is a relatively slow operation, so,
195       * when possible, it is a good idea to provide estimates of expected
196       * table sizes.
197       *
198       * @throws IllegalArgumentException if {@code initialCapacity} is
199       *   negative
200       * @throws IllegalStateException if an initial capacity was already set
201       */
202      @Override
203      public MapMaker initialCapacity(int initialCapacity) {
204        checkState(this.initialCapacity == UNSET_INT,
205            "initial capacity was already set to %s", this.initialCapacity);
206        checkArgument(initialCapacity >= 0);
207        this.initialCapacity = initialCapacity;
208        return this;
209      }
210    
211      int getInitialCapacity() {
212        return (initialCapacity == UNSET_INT)
213            ? DEFAULT_INITIAL_CAPACITY : initialCapacity;
214      }
215    
216      /**
217       * Specifies the maximum number of entries the map may contain. While the
218       * number of entries in the map is not guaranteed to grow to the maximum,
219       * the map will attempt to make the best use of memory without exceeding the
220       * maximum number of entries. As the map size grows close to the maximum,
221       * the map will evict entries that are less likely to be used again. For
222       * example, the map may evict an entry because it hasn't been used recently
223       * or very often.
224       *
225       * <p>When {@code size} is zero, elements can be successfully added to the
226       * map, but are evicted immediately.
227       *
228       * @param size the maximum size of the map
229       *
230       * @throws IllegalArgumentException if {@code size} is negative
231       * @throws IllegalStateException if a maximum size was already set
232       * @since 8
233       */
234      @Beta
235      @Override
236      public MapMaker maximumSize(int size) {
237        checkState(this.maximumSize == UNSET_INT,
238            "maximum size was already set to %s", this.maximumSize);
239        checkArgument(size >= 0, "maximum size must not be negative");
240        this.maximumSize = size;
241        this.useCustomMap = true;
242        this.useNullMap |= (maximumSize == 0);
243        return this;
244      }
245    
246      /**
247       * Guides the allowed concurrency among update operations. Used as a
248       * hint for internal sizing. The table is internally partitioned to try
249       * to permit the indicated number of concurrent updates without
250       * contention.  Because placement in hash tables is essentially random,
251       * the actual concurrency will vary. Ideally, you should choose a value
252       * to accommodate as many threads as will ever concurrently modify the
253       * table. Using a significantly higher value than you need can waste
254       * space and time, and a significantly lower value can lead to thread
255       * contention. But overestimates and underestimates within an order of
256       * magnitude do not usually have much noticeable impact. A value of one
257       * is appropriate when it is known that only one thread will modify and
258       * all others will only read. Defaults to 4.
259       *
260       * <p><b>Note:</b> Prior to Guava release 09, the default was 16. It is
261       * possible the default will change again in the future. If you care about
262       * this value, you should always choose it explicitly.
263       *
264       * @throws IllegalArgumentException if {@code concurrencyLevel} is
265       *     nonpositive
266       * @throws IllegalStateException if a concurrency level was already set
267       */
268      @GwtIncompatible("java.util.concurrent.ConcurrentHashMap concurrencyLevel")
269      @Override
270      public MapMaker concurrencyLevel(int concurrencyLevel) {
271        checkState(this.concurrencyLevel == UNSET_INT,
272            "concurrency level was already set to %s", this.concurrencyLevel);
273        checkArgument(concurrencyLevel > 0);
274        this.concurrencyLevel = concurrencyLevel;
275        return this;
276      }
277    
278      int getConcurrencyLevel() {
279        return (concurrencyLevel == UNSET_INT)
280            ? DEFAULT_CONCURRENCY_LEVEL : concurrencyLevel;
281      }
282    
283      /**
284       * Specifies that each key (not value) stored in the map should be
285       * wrapped in a {@link WeakReference} (by default, strong references
286       * are used).
287       *
288       * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
289       * to determine equality of weak keys, which may not behave as you expect.
290       * For example, storing a key in the map and then attempting a lookup
291       * using a different but {@link Object#equals(Object) equals}-equivalent
292       * key will always fail.
293       *
294       * @throws IllegalStateException if the key strength was already set
295       * @see WeakReference
296       */
297      @GwtIncompatible("java.lang.ref.WeakReference")
298      @Override
299      public MapMaker weakKeys() {
300        return setKeyStrength(Strength.WEAK);
301      }
302    
303      /**
304       * Specifies that each key (not value) stored in the map should be
305       * wrapped in a {@link SoftReference} (by default, strong references
306       * are used).
307       *
308       * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
309       * to determine equality of soft keys, which may not behave as you expect.
310       * For example, storing a key in the map and then attempting a lookup
311       * using a different but {@link Object#equals(Object) equals}-equivalent
312       * key will always fail.
313       *
314       * @throws IllegalStateException if the key strength was already set
315       * @see SoftReference
316       */
317      @GwtIncompatible("java.lang.ref.SoftReference")
318      @Override
319      public MapMaker softKeys() {
320        return setKeyStrength(Strength.SOFT);
321      }
322    
323      MapMaker setKeyStrength(Strength strength) {
324        checkState(keyStrength == null,
325            "Key strength was already set to %s", keyStrength);
326        keyStrength = checkNotNull(strength);
327        if (strength != Strength.STRONG) {
328          // STRONG could be used during deserialization.
329          useCustomMap = true;
330        }
331        return this;
332      }
333    
334      Strength getKeyStrength() {
335        return firstNonNull(keyStrength, Strength.STRONG);
336      }
337    
338      /**
339       * Specifies that each value (not key) stored in the map should be
340       * wrapped in a {@link WeakReference} (by default, strong references
341       * are used).
342       *
343       * <p>Weak values will be garbage collected once they are weakly
344       * reachable. This makes them a poor candidate for caching; consider
345       * {@link #softValues()} instead.
346       *
347       * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
348       * to determine equality of weak values. This will notably impact
349       * the behavior of {@link Map#containsValue(Object) containsValue},
350       * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)},
351       * and {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}.
352       *
353       * @throws IllegalStateException if the value strength was already set
354       * @see WeakReference
355       */
356      @GwtIncompatible("java.lang.ref.WeakReference")
357      @Override
358      public MapMaker weakValues() {
359        return setValueStrength(Strength.WEAK);
360      }
361    
362      /**
363       * Specifies that each value (not key) stored in the map should be
364       * wrapped in a {@link SoftReference} (by default, strong references
365       * are used).
366       *
367       * <p>Soft values will be garbage collected in response to memory
368       * demand, and in a least-recently-used manner. This makes them a
369       * good candidate for caching.
370       *
371       * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
372       * to determine equality of soft values. This will notably impact
373       * the behavior of {@link Map#containsValue(Object) containsValue},
374       * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)},
375       * and {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}.
376       *
377       * @throws IllegalStateException if the value strength was already set
378       * @see SoftReference
379       */
380      @GwtIncompatible("java.lang.ref.SoftReference")
381      @Override
382      public MapMaker softValues() {
383        return setValueStrength(Strength.SOFT);
384      }
385    
386      MapMaker setValueStrength(Strength strength) {
387        checkState(valueStrength == null,
388            "Value strength was already set to %s", valueStrength);
389        valueStrength = checkNotNull(strength);
390        if (strength != Strength.STRONG) {
391          // STRONG could be used during deserialization.
392          useCustomMap = true;
393        }
394        return this;
395      }
396    
397      Strength getValueStrength() {
398        return firstNonNull(valueStrength, Strength.STRONG);
399      }
400    
401      /**
402       * Old name of {@link #expireAfterWrite}.
403       *
404       * @deprecated use {@link #expireAfterWrite}, which behaves exactly the same.
405       *     <b>This method is scheduled for deletion in July 2012.</b>
406       */
407      @Deprecated
408      @Override
409      public MapMaker expiration(long duration, TimeUnit unit) {
410        return expireAfterWrite(duration, unit);
411      }
412    
413      /**
414       * Specifies that each entry should be automatically removed from the
415       * map once a fixed duration has passed since the entry's creation or
416       * replacement. Note that changing the value of an entry will reset its
417       * expiration time.
418       *
419       * <p>When {@code duration} is zero, elements can be successfully added to the
420       * map, but are evicted immediately.
421       *
422       * @param duration the length of time after an entry is created that it
423       *     should be automatically removed
424       * @param unit the unit that {@code duration} is expressed in
425       * @throws IllegalArgumentException if {@code duration} is negative
426       * @throws IllegalStateException if the time to live or time to idle was
427       *     already set
428       * @since 8
429       */
430      @Beta
431      @Override
432      public MapMaker expireAfterWrite(long duration, TimeUnit unit) {
433        checkExpiration(duration, unit);
434        this.expireAfterWriteNanos = unit.toNanos(duration);
435        useNullMap |= (duration == 0);
436        useCustomMap = true;
437        return this;
438      }
439    
440      private void checkExpiration(long duration, TimeUnit unit) {
441        checkState(expireAfterWriteNanos == UNSET_INT,
442            "expireAfterWrite was already set to %s ns",
443            expireAfterWriteNanos);
444        checkState(expireAfterAccessNanos == UNSET_INT,
445            "expireAfterAccess was already set to %s ns",
446            expireAfterAccessNanos);
447        checkArgument(duration >= 0, "duration cannot be negative: %s %s",
448            duration, unit);
449      }
450    
451      long getExpireAfterWriteNanos() {
452        return (expireAfterWriteNanos == UNSET_INT)
453            ? DEFAULT_EXPIRATION_NANOS : expireAfterWriteNanos;
454      }
455    
456      /**
457       * Specifies that each entry should be automatically removed from the
458       * map once a fixed duration has passed since the entry's last read or
459       * write access.
460       *
461       * <p>When {@code duration} is zero, elements can be successfully added to the
462       * map, but are evicted immediately.
463       *
464       * @param duration the length of time after an entry is last accessed
465       *     that it should be automatically removed
466       * @param unit the unit that {@code duration} is expressed in
467       * @throws IllegalArgumentException if {@code duration} is negative
468       * @throws IllegalStateException if the time to idle or time to live was
469       *     already set
470       * @since 8
471       */
472      @Beta
473      @GwtIncompatible("To be supported")
474      @Override
475      public MapMaker expireAfterAccess(long duration, TimeUnit unit) {
476        checkExpiration(duration, unit);
477        this.expireAfterAccessNanos = unit.toNanos(duration);
478        useNullMap |= (duration == 0);
479        useCustomMap = true;
480        return this;
481      }
482    
483      long getExpireAfterAccessNanos() {
484        return (expireAfterAccessNanos == UNSET_INT)
485            ? DEFAULT_EXPIRATION_NANOS : expireAfterAccessNanos;
486      }
487    
488      Executor getCleanupExecutor() {
489        return firstNonNull(cleanupExecutor, DEFAULT_CLEANUP_EXECUTOR);
490      }
491    
492      Ticker getTicker() {
493        return firstNonNull(ticker, DEFAULT_TICKER);
494      }
495    
496      /**
497       * Specifies a listener instance, which all maps built using this {@code
498       * MapMaker} will notify each time an entry is evicted.
499       *
500       * <p>A map built by this map maker will invoke the supplied listener after it
501       * evicts an entry, whether it does so due to timed expiration, exceeding the
502       * maximum size, or discovering that the key or value has been reclaimed by
503       * the garbage collector. It will invoke the listener synchronously, during
504       * invocations of any of that map's public methods (even read-only methods).
505       * The listener will <i>not</i> be invoked on manual removal.
506       *
507       * <p><b>Important note:</b> Instead of returning <em>this</em> as a {@code
508       * MapMaker} instance, this method returns {@code GenericMapMaker<K, V>}.
509       * From this point on, either the original reference or the returned
510       * reference may be used to complete configuration and build the map, but only
511       * the "generic" one is type-safe. That is, it will properly prevent you from
512       * building maps whose key or value types are incompatible with the types
513       * accepted by the listener already provided; the {@code MapMaker} type cannot
514       * do this. For best results, simply use the standard method-chaining idiom,
515       * as illustrated in the documentation at top, configuring a {@code MapMaker}
516       * and building your {@link Map} all in a single statement.
517       *
518       * <p><b>Warning:</b> if you ignore the above advice, and use this {@code
519       * MapMaker} to build maps whose key or value types are incompatible with the
520       * listener, you will likely experience a {@link ClassCastException} at an
521       * undefined point in the future.
522       *
523       * @throws IllegalStateException if an eviction listener was already set
524       * @since 7
525       */
526      @Beta
527      @GwtIncompatible("To be supported")
528      public <K, V> GenericMapMaker<K, V> evictionListener(
529          MapEvictionListener<K, V> listener) {
530        checkState(this.evictionListener == null);
531    
532        // safely limiting the kinds of maps this can produce
533        @SuppressWarnings("unchecked")
534        GenericMapMaker<K, V> me = (GenericMapMaker<K, V>) this;
535        me.evictionListener = checkNotNull(listener);
536        useCustomMap = true;
537        return me;
538      }
539    
540      // TODO(kevinb): should this go in GenericMapMaker to avoid casts?
541      @SuppressWarnings("unchecked")
542      <K, V> MapEvictionListener<K, V> getEvictionListener() {
543        return evictionListener == null
544            ? (MapEvictionListener<K, V>) NullListener.INSTANCE
545            : (MapEvictionListener<K, V>) evictionListener;
546      }
547    
548      /**
549       * Builds a map, without on-demand computation of values. This method
550       * does not alter the state of this {@code MapMaker} instance, so it can be
551       * invoked again to create multiple independent maps.
552       *
553       * @return a serializable concurrent map having the requested features
554       */
555      @Override
556      public <K, V> ConcurrentMap<K, V> makeMap() {
557        if (!useCustomMap) {
558          return new ConcurrentHashMap<K, V>(getInitialCapacity(),
559              0.75f, getConcurrencyLevel());
560        }
561        return useNullMap
562            ? new NullConcurrentMap<K, V>(this)
563            : new CustomConcurrentHashMap<K, V>(this);
564      }
565    
566      /**
567       * Builds a caching function, which either returns an already-computed value
568       * for a given key or atomically computes it using the supplied function.
569       * If another thread is currently computing the value for this key, simply
570       * waits for that thread to finish and returns its computed value. Note that
571       * the function may be executed concurrently by multiple threads, but only for
572       * distinct keys.
573       *
574       * <p>The {@code Map} view of the {@code Cache}'s cache is only
575       * updated when function computation completes. In other words, an entry isn't
576       * visible until the value's computation completes. No methods on the {@code
577       * Map} will ever trigger computation.
578       *
579       * <p>{@link Cache#apply} in the returned function implementation may
580       * throw:
581       *
582       * <ul>
583       * <li>{@link NullPointerException} if the key is null or the
584       *     computing function returns null
585       * <li>{@link ComputationException} if an exception was thrown by the
586       *     computing function. If that exception is already of type {@link
587       *     ComputationException} it is propagated directly; otherwise it is
588       *     wrapped.
589       * </ul>
590       *
591       * <p>If {@link Map#put} is called before a computation completes, other
592       * threads waiting on the computation will wake up and return the stored
593       * value. When the computation completes, its result will be ignored.
594       *
595       * <p>This method does not alter the state of this {@code MapMaker} instance,
596       * so it can be invoked again to create multiple independent maps.
597       *
598       * @param computingFunction the function used to compute new values
599       * @return a serializable cache having the requested features
600       */
601      // TODO(kevinb): figure out the Cache interface before making this public
602      <K, V> Cache<K, V> makeCache(
603          Function<? super K, ? extends V> computingFunction) {
604        return useNullMap
605            ? new NullComputingConcurrentMap<K, V>(this, computingFunction)
606            : new ComputingConcurrentHashMap<K, V>(this, computingFunction);
607      }
608    
609      /**
610       * Builds a map that supports atomic, on-demand computation of values. {@link
611       * Map#get} either returns an already-computed value for the given key,
612       * atomically computes it using the supplied function, or, if another thread
613       * is currently computing the value for this key, simply waits for that thread
614       * to finish and returns its computed value. Note that the function may be
615       * executed concurrently by multiple threads, but only for distinct keys.
616       *
617       * <p>If an entry's value has not finished computing yet, query methods
618       * besides {@code get} return immediately as if an entry doesn't exist. In
619       * other words, an entry isn't externally visible until the value's
620       * computation completes.
621       *
622       * <p>{@link Map#get} on the returned map will never return {@code null}. It
623       * may throw:
624       *
625       * <ul>
626       * <li>{@link NullPointerException} if the key is null or the computing
627       *     function returns null
628       * <li>{@link ComputationException} if an exception was thrown by the
629       *     computing function. If that exception is already of type {@link
630       *     ComputationException} it is propagated directly; otherwise it is
631       *     wrapped.
632       * </ul>
633       *
634       * <p><b>Note:</b> Callers of {@code get} <i>must</i> ensure that the key
635       * argument is of type {@code K}. The {@code get} method accepts {@code
636       * Object}, so the key type is not checked at compile time. Passing an object
637       * of a type other than {@code K} can result in that object being unsafely
638       * passed to the computing function as type {@code K}, and unsafely stored in
639       * the map.
640       *
641       * <p>If {@link Map#put} is called before a computation completes, other
642       * threads waiting on the computation will wake up and return the stored
643       * value.
644       *
645       * <p>This method does not alter the state of this {@code MapMaker} instance,
646       * so it can be invoked again to create multiple independent maps.
647       *
648       * @param computingFunction the function used to compute new values
649       * @return a serializable concurrent map having the requested features
650       */
651      @Override
652      public <K, V> ConcurrentMap<K, V> makeComputingMap(
653          Function<? super K, ? extends V> computingFunction) {
654        Cache<K, V> cache = makeCache(computingFunction);
655        return new ComputingMapAdapter<K, V>(cache);
656      }
657    
658      /**
659       * Returns a string representation for this MapMaker instance.
660       * The form of this representation is not guaranteed.
661       */
662      @Override
663      public String toString() {
664        Objects.ToStringHelper s = Objects.toStringHelper(this);
665        if (initialCapacity != UNSET_INT) {
666          s.add("initialCapacity", initialCapacity);
667        }
668        if (concurrencyLevel != UNSET_INT) {
669          s.add("concurrencyLevel", concurrencyLevel);
670        }
671        if (maximumSize != UNSET_INT) {
672          s.add("maximumSize", maximumSize);
673        }
674        if (expireAfterWriteNanos != UNSET_INT) {
675          s.add("expireAfterWrite", expireAfterWriteNanos + "ns");
676        }
677        if (expireAfterAccessNanos != UNSET_INT) {
678          s.add("expireAfterAccess", expireAfterAccessNanos + "ns");
679        }
680        if (keyStrength != null) {
681          s.add("keyStrength", Ascii.toLowerCase(keyStrength.toString()));
682        }
683        if (valueStrength != null) {
684          s.add("valueStrength", Ascii.toLowerCase(valueStrength.toString()));
685        }
686        if (keyEquivalence != null) {
687          s.addValue("keyEquivalence");
688        }
689        if (valueEquivalence != null) {
690          s.addValue("valueEquivalence");
691        }
692        if (evictionListener != null) {
693          s.addValue("evictionListener");
694        }
695        if (cleanupExecutor != null) {
696          s.addValue("cleanupExecutor");
697        }
698        return s.toString();
699      }
700    
701      /**
702       * A function which caches the result of each application (computation). This
703       * interface does not specify the caching semantics, but does expose a {@code
704       * ConcurrentMap} view of cached entries.
705       */
706      interface Cache<K, V> extends Function<K, V> {
707    
708        /**
709         * Returns a map view of the cached entries.
710         */
711        ConcurrentMap<K, V> asMap();
712      }
713    
714      /** A map that is always empty and evicts on insertion. */
715      static class NullConcurrentMap<K, V> extends AbstractMap<K, V>
716          implements ConcurrentMap<K, V>, Serializable {
717        private static final long serialVersionUID = 0;
718    
719        final MapEvictionListener<K, V> evictionListener;
720    
721        NullConcurrentMap(MapMaker mapMaker) {
722          evictionListener = mapMaker.getEvictionListener();
723        }
724    
725        @Override
726        public boolean containsKey(Object key) {
727          checkNotNull(key);
728          return false;
729        }
730    
731        @Override
732        public boolean containsValue(Object value) {
733          checkNotNull(value);
734          return false;
735        }
736    
737        @Override
738        public V get(Object key) {
739          checkNotNull(key);
740          return null;
741        }
742    
743        @Override
744        public V put(K key, V value) {
745          checkNotNull(key);
746          checkNotNull(value);
747          evictionListener.onEviction(key, value);
748          return null;
749        }
750    
751        @Override
752        public V putIfAbsent(K key, V value) {
753          return put(key, value);
754        }
755    
756        @Override
757        public V remove(Object key) {
758          checkNotNull(key);
759          return null;
760        }
761    
762        @Override
763        public boolean remove(Object key, Object value) {
764          checkNotNull(key);
765          checkNotNull(value);
766          return false;
767        }
768    
769        @Override
770        public V replace(K key, V value) {
771          checkNotNull(key);
772          checkNotNull(value);
773          return null;
774        }
775    
776        @Override
777        public boolean replace(K key, V oldValue, V newValue) {
778          checkNotNull(key);
779          checkNotNull(oldValue);
780          checkNotNull(newValue);
781          return false;
782        }
783    
784        @Override
785        public Set<Entry<K, V>> entrySet() {
786          return Collections.emptySet();
787        }
788      }
789    
790      /** Computes on retrieval and evicts the result. */
791      static final class NullComputingConcurrentMap<K, V>
792          extends NullConcurrentMap<K, V> implements Cache<K, V> {
793        private static final long serialVersionUID = 0;
794    
795        final Function<? super K, ? extends V> computingFunction;
796    
797        NullComputingConcurrentMap(MapMaker mapMaker,
798            Function<? super K, ? extends V> computingFunction) {
799          super(mapMaker);
800          this.computingFunction = checkNotNull(computingFunction);
801        }
802    
803        @Override
804        public V apply(K key) {
805          V value = compute(key);
806          checkNotNull(value,
807              computingFunction + " returned null for key " + key + ".");
808          evictionListener.onEviction(key, value);
809          return value;
810        }
811    
812        private V compute(K key) {
813          checkNotNull(key);
814          try {
815            return computingFunction.apply(key);
816          } catch (ComputationException e) {
817            throw e;
818          } catch (Throwable t) {
819            throw new ComputationException(t);
820          }
821        }
822    
823        @Override
824        public ConcurrentMap<K, V> asMap() {
825          return this;
826        }
827      }
828    
829      /**
830       * Overrides get() to compute on demand.
831       */
832      static class ComputingMapAdapter<K, V> extends ForwardingConcurrentMap<K, V>
833          implements Serializable {
834        private static final long serialVersionUID = 0;
835    
836        final Cache<K, V> cache;
837    
838        ComputingMapAdapter(Cache<K, V> cache) {
839          this.cache = cache;
840        }
841    
842        @Override protected ConcurrentMap<K, V> delegate() {
843          return cache.asMap();
844        }
845    
846        @SuppressWarnings("unchecked") // unsafe, which is why this is deprecated
847        @Override public V get(Object key) {
848          return cache.apply((K) key);
849        }
850      }
851    }