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
017package com.google.common.collect;
018
019import static com.google.common.base.Objects.firstNonNull;
020import static com.google.common.base.Preconditions.checkArgument;
021import static com.google.common.base.Preconditions.checkNotNull;
022import static com.google.common.base.Preconditions.checkState;
023
024import com.google.common.annotations.Beta;
025import com.google.common.annotations.GwtCompatible;
026import com.google.common.annotations.GwtIncompatible;
027import com.google.common.base.Ascii;
028import com.google.common.base.Equivalence;
029import com.google.common.base.Function;
030import com.google.common.base.Objects;
031import com.google.common.base.Ticker;
032import com.google.common.collect.CustomConcurrentHashMap.Strength;
033
034import java.io.Serializable;
035import java.lang.ref.SoftReference;
036import java.lang.ref.WeakReference;
037import java.util.AbstractMap;
038import java.util.Collections;
039import java.util.Map;
040import java.util.Set;
041import java.util.concurrent.ConcurrentHashMap;
042import java.util.concurrent.ConcurrentMap;
043import java.util.concurrent.Executor;
044import 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)
110public 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}