1/*
2 * Copyright (C) 2009 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkArgument;
18import static com.google.common.base.Preconditions.checkNotNull;
19import static com.google.common.base.Preconditions.checkState;
20import static com.google.common.collect.MapMakerInternalMap.Strength.SOFT;
21
22import com.google.common.annotations.GwtCompatible;
23import com.google.common.annotations.GwtIncompatible;
24import com.google.common.base.Ascii;
25import com.google.common.base.Equivalence;
26import com.google.common.base.Function;
27import com.google.common.base.MoreObjects;
28import com.google.common.base.Throwables;
29import com.google.common.base.Ticker;
30import com.google.common.collect.MapMakerInternalMap.Strength;
31
32import java.io.Serializable;
33import java.lang.ref.SoftReference;
34import java.lang.ref.WeakReference;
35import java.util.AbstractMap;
36import java.util.Collections;
37import java.util.ConcurrentModificationException;
38import java.util.Map;
39import java.util.Set;
40import java.util.concurrent.ConcurrentHashMap;
41import java.util.concurrent.ConcurrentMap;
42import java.util.concurrent.ExecutionException;
43import java.util.concurrent.TimeUnit;
44
45import javax.annotation.Nullable;
46
47/**
48 * <p>A builder of {@link ConcurrentMap} instances having any combination of the following features:
49 *
50 * <ul>
51 * <li>keys or values automatically wrapped in {@linkplain WeakReference weak} or {@linkplain
52 *     SoftReference soft} references
53 * <li>notification of evicted (or otherwise removed) entries
54 * <li>on-demand computation of values for keys not already present
55 * </ul>
56 *
57 * <p>Usage example: <pre>   {@code
58 *
59 *   ConcurrentMap<Request, Stopwatch> timers = new MapMaker()
60 *       .concurrencyLevel(4)
61 *       .weakKeys()
62 *       .makeMap();}</pre>
63 *
64 * <p>These features are all optional; {@code new MapMaker().makeMap()} returns a valid concurrent
65 * map that behaves similarly to a {@link ConcurrentHashMap}.
66 *
67 * <p>The returned map is implemented as a hash table with similar performance characteristics to
68 * {@link ConcurrentHashMap}. It supports all optional operations of the {@code ConcurrentMap}
69 * interface. It does not permit null keys or values.
70 *
71 * <p><b>Note:</b> by default, the returned map uses equality comparisons (the {@link Object#equals
72 * equals} method) to determine equality for keys or values. However, if {@link #weakKeys} was
73 * specified, the map uses identity ({@code ==}) comparisons instead for keys. Likewise, if {@link
74 * #weakValues} or {@link #softValues} was specified, the map uses identity comparisons for values.
75 *
76 * <p>The view collections of the returned map have <i>weakly consistent iterators</i>. This means
77 * that they are safe for concurrent use, but if other threads modify the map after the iterator is
78 * created, it is undefined which of these changes, if any, are reflected in that iterator. These
79 * iterators never throw {@link ConcurrentModificationException}.
80 *
81 * <p>If {@link #weakKeys}, {@link #weakValues}, or {@link #softValues} are requested, it is
82 * possible for a key or value present in the map to be reclaimed by the garbage collector. Entries
83 * with reclaimed keys or values may be removed from the map on each map modification or on
84 * occasional map accesses; such entries may be counted by {@link Map#size}, but will never be
85 * visible to read or write operations. A partially-reclaimed entry is never exposed to the user.
86 * Any {@link java.util.Map.Entry} instance retrieved from the map's
87 * {@linkplain Map#entrySet entry set} is a snapshot of that entry's state at the time of
88 * retrieval; such entries do, however, support {@link java.util.Map.Entry#setValue}, which simply
89 * calls {@link Map#put} on the entry's key.
90 *
91 * <p>The maps produced by {@code MapMaker} are serializable, and the deserialized maps retain all
92 * the configuration properties of the original map. During deserialization, if the original map had
93 * used soft or weak references, the entries are reconstructed as they were, but it's not unlikely
94 * they'll be quickly garbage-collected before they are ever accessed.
95 *
96 * <p>{@code new MapMaker().weakKeys().makeMap()} is a recommended replacement for {@link
97 * java.util.WeakHashMap}, but note that it compares keys using object identity whereas {@code
98 * WeakHashMap} uses {@link Object#equals}.
99 *
100 * @author Bob Lee
101 * @author Charles Fry
102 * @author Kevin Bourrillion
103 * @since 2.0 (imported from Google Collections Library)
104 */
105@GwtCompatible(emulated = true)
106public final class MapMaker extends GenericMapMaker<Object, Object> {
107  private static final int DEFAULT_INITIAL_CAPACITY = 16;
108  private static final int DEFAULT_CONCURRENCY_LEVEL = 4;
109  private static final int DEFAULT_EXPIRATION_NANOS = 0;
110
111  static final int UNSET_INT = -1;
112
113  // TODO(kevinb): dispense with this after benchmarking
114  boolean useCustomMap;
115
116  int initialCapacity = UNSET_INT;
117  int concurrencyLevel = UNSET_INT;
118  int maximumSize = UNSET_INT;
119
120  Strength keyStrength;
121  Strength valueStrength;
122
123  long expireAfterWriteNanos = UNSET_INT;
124  long expireAfterAccessNanos = UNSET_INT;
125
126  RemovalCause nullRemovalCause;
127
128  Equivalence<Object> keyEquivalence;
129
130  Ticker ticker;
131
132  /**
133   * Constructs a new {@code MapMaker} instance with default settings, including strong keys, strong
134   * values, and no automatic eviction of any kind.
135   */
136  public MapMaker() {}
137
138  /**
139   * Sets a custom {@code Equivalence} strategy for comparing keys.
140   *
141   * <p>By default, the map uses {@link Equivalence#identity} to determine key equality when {@link
142   * #weakKeys} is specified, and {@link Equivalence#equals()} otherwise. The only place this is
143   * used is in {@link Interners.WeakInterner}.
144   */
145  @GwtIncompatible("To be supported")
146  @Override
147  MapMaker keyEquivalence(Equivalence<Object> equivalence) {
148    checkState(keyEquivalence == null, "key equivalence was already set to %s", keyEquivalence);
149    keyEquivalence = checkNotNull(equivalence);
150    this.useCustomMap = true;
151    return this;
152  }
153
154  Equivalence<Object> getKeyEquivalence() {
155    return MoreObjects.firstNonNull(keyEquivalence, getKeyStrength().defaultEquivalence());
156  }
157
158  /**
159   * Sets the minimum total size for the internal hash tables. For example, if the initial capacity
160   * is {@code 60}, and the concurrency level is {@code 8}, then eight segments are created, each
161   * having a hash table of size eight. Providing a large enough estimate at construction time
162   * avoids the need for expensive resizing operations later, but setting this value unnecessarily
163   * high wastes memory.
164   *
165   * @throws IllegalArgumentException if {@code initialCapacity} is negative
166   * @throws IllegalStateException if an initial capacity was already set
167   */
168  @Override
169  public MapMaker initialCapacity(int initialCapacity) {
170    checkState(this.initialCapacity == UNSET_INT, "initial capacity was already set to %s",
171        this.initialCapacity);
172    checkArgument(initialCapacity >= 0);
173    this.initialCapacity = initialCapacity;
174    return this;
175  }
176
177  int getInitialCapacity() {
178    return (initialCapacity == UNSET_INT) ? DEFAULT_INITIAL_CAPACITY : initialCapacity;
179  }
180
181  /**
182   * Specifies the maximum number of entries the map may contain. Note that the map <b>may evict an
183   * entry before this limit is exceeded</b>. As the map size grows close to the maximum, the map
184   * evicts entries that are less likely to be used again. For example, the map may evict an entry
185   * because it hasn't been used recently or very often.
186   *
187   * <p>When {@code size} is zero, elements can be successfully added to the map, but are evicted
188   * immediately. This has the same effect as invoking {@link #expireAfterWrite
189   * expireAfterWrite}{@code (0, unit)} or {@link #expireAfterAccess expireAfterAccess}{@code (0,
190   * unit)}. It can be useful in testing, or to disable caching temporarily without a code change.
191   *
192   * <p>Caching functionality in {@code MapMaker} has been moved to
193   * {@link com.google.common.cache.CacheBuilder}.
194   *
195   * @param size the maximum size of the map
196   * @throws IllegalArgumentException if {@code size} is negative
197   * @throws IllegalStateException if a maximum size was already set
198   * @deprecated Caching functionality in {@code MapMaker} has been moved to
199   *     {@link com.google.common.cache.CacheBuilder}, with {@link #maximumSize} being
200   *     replaced by {@link com.google.common.cache.CacheBuilder#maximumSize}. Note that {@code
201   *     CacheBuilder} is simply an enhanced API for an implementation which was branched from
202   *     {@code MapMaker}.
203   */
204  @Deprecated
205  @Override
206  MapMaker maximumSize(int size) {
207    checkState(this.maximumSize == UNSET_INT, "maximum size was already set to %s",
208        this.maximumSize);
209    checkArgument(size >= 0, "maximum size must not be negative");
210    this.maximumSize = size;
211    this.useCustomMap = true;
212    if (maximumSize == 0) {
213      // SIZE trumps EXPIRED
214      this.nullRemovalCause = RemovalCause.SIZE;
215    }
216    return this;
217  }
218
219  /**
220   * Guides the allowed concurrency among update operations. Used as a hint for internal sizing. The
221   * table is internally partitioned to try to permit the indicated number of concurrent updates
222   * without contention. Because assignment of entries to these partitions is not necessarily
223   * uniform, the actual concurrency observed may vary. Ideally, you should choose a value to
224   * accommodate as many threads as will ever concurrently modify the table. Using a significantly
225   * higher value than you need can waste space and time, and a significantly lower value can lead
226   * to thread contention. But overestimates and underestimates within an order of magnitude do not
227   * usually have much noticeable impact. A value of one permits only one thread to modify the map
228   * at a time, but since read operations can proceed concurrently, this still yields higher
229   * concurrency than full synchronization. Defaults to 4.
230   *
231   * <p><b>Note:</b> Prior to Guava release 9.0, the default was 16. It is possible the default will
232   * change again in the future. If you care about this value, you should always choose it
233   * explicitly.
234   *
235   * @throws IllegalArgumentException if {@code concurrencyLevel} is nonpositive
236   * @throws IllegalStateException if a concurrency level was already set
237   */
238  @Override
239  public MapMaker concurrencyLevel(int concurrencyLevel) {
240    checkState(this.concurrencyLevel == UNSET_INT, "concurrency level was already set to %s",
241        this.concurrencyLevel);
242    checkArgument(concurrencyLevel > 0);
243    this.concurrencyLevel = concurrencyLevel;
244    return this;
245  }
246
247  int getConcurrencyLevel() {
248    return (concurrencyLevel == UNSET_INT) ? DEFAULT_CONCURRENCY_LEVEL : concurrencyLevel;
249  }
250
251  /**
252   * Specifies that each key (not value) stored in the map should be wrapped in a {@link
253   * WeakReference} (by default, strong references are used).
254   *
255   * <p><b>Warning:</b> when this method is used, the resulting map will use identity ({@code ==})
256   * comparison to determine equality of keys, which is a technical violation of the {@link Map}
257   * specification, and may not be what you expect.
258   *
259   * @throws IllegalStateException if the key strength was already set
260   * @see WeakReference
261   */
262  @GwtIncompatible("java.lang.ref.WeakReference")
263  @Override
264  public MapMaker weakKeys() {
265    return setKeyStrength(Strength.WEAK);
266  }
267
268  MapMaker setKeyStrength(Strength strength) {
269    checkState(keyStrength == null, "Key strength was already set to %s", keyStrength);
270    keyStrength = checkNotNull(strength);
271    checkArgument(keyStrength != SOFT, "Soft keys are not supported");
272    if (strength != Strength.STRONG) {
273      // STRONG could be used during deserialization.
274      useCustomMap = true;
275    }
276    return this;
277  }
278
279  Strength getKeyStrength() {
280    return MoreObjects.firstNonNull(keyStrength, Strength.STRONG);
281  }
282
283  /**
284   * Specifies that each value (not key) stored in the map should be wrapped in a
285   * {@link WeakReference} (by default, strong references are used).
286   *
287   * <p>Weak values will be garbage collected once they are weakly reachable. This makes them a poor
288   * candidate for caching; consider {@link #softValues} instead.
289   *
290   * <p><b>Warning:</b> when this method is used, the resulting map will use identity ({@code ==})
291   * comparison to determine equality of values. This technically violates the specifications of
292   * the methods {@link Map#containsValue containsValue},
293   * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)} and
294   * {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}, and may not be what you
295   * expect.
296   *
297   * @throws IllegalStateException if the value strength was already set
298   * @see WeakReference
299   */
300  @GwtIncompatible("java.lang.ref.WeakReference")
301  @Override
302  public MapMaker weakValues() {
303    return setValueStrength(Strength.WEAK);
304  }
305
306  /**
307   * Specifies that each value (not key) stored in the map should be wrapped in a
308   * {@link SoftReference} (by default, strong references are used). Softly-referenced objects will
309   * be garbage-collected in a <i>globally</i> least-recently-used manner, in response to memory
310   * demand.
311   *
312   * <p><b>Warning:</b> in most circumstances it is better to set a per-cache {@linkplain
313   * #maximumSize maximum size} instead of using soft references. You should only use this method if
314   * you are well familiar with the practical consequences of soft references.
315   *
316   * <p><b>Warning:</b> when this method is used, the resulting map will use identity ({@code ==})
317   * comparison to determine equality of values. This technically violates the specifications of
318   * the methods {@link Map#containsValue containsValue},
319   * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)} and
320   * {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}, and may not be what you
321   * expect.
322   *
323   * @throws IllegalStateException if the value strength was already set
324   * @see SoftReference
325   * @deprecated Caching functionality in {@code MapMaker} has been moved to {@link
326   *     com.google.common.cache.CacheBuilder}, with {@link #softValues} being replaced by {@link
327   *     com.google.common.cache.CacheBuilder#softValues}. Note that {@code CacheBuilder} is simply
328   *     an enhanced API for an implementation which was branched from {@code MapMaker}. <b>This
329   *     method is scheduled for removal in March 2015.</b>
330   */
331  @Deprecated
332  @GwtIncompatible("java.lang.ref.SoftReference")
333  @Override
334  public MapMaker softValues() {
335    return setValueStrength(Strength.SOFT);
336  }
337
338  MapMaker setValueStrength(Strength strength) {
339    checkState(valueStrength == null, "Value strength was already set to %s", valueStrength);
340    valueStrength = checkNotNull(strength);
341    if (strength != Strength.STRONG) {
342      // STRONG could be used during deserialization.
343      useCustomMap = true;
344    }
345    return this;
346  }
347
348  Strength getValueStrength() {
349    return MoreObjects.firstNonNull(valueStrength, Strength.STRONG);
350  }
351
352  /**
353   * Specifies that each entry should be automatically removed from the map once a fixed duration
354   * has elapsed after the entry's creation, or the most recent replacement of its value.
355   *
356   * <p>When {@code duration} is zero, elements can be successfully added to the map, but are
357   * evicted immediately. This has a very similar effect to invoking {@link #maximumSize
358   * maximumSize}{@code (0)}. It can be useful in testing, or to disable caching temporarily without
359   * a code change.
360   *
361   * <p>Expired entries may be counted by {@link Map#size}, but will never be visible to read or
362   * write operations. Expired entries are currently cleaned up during write operations, or during
363   * occasional read operations in the absense of writes; though this behavior may change in the
364   * future.
365   *
366   * @param duration the length of time after an entry is created that it should be automatically
367   *     removed
368   * @param unit the unit that {@code duration} is expressed in
369   * @throws IllegalArgumentException if {@code duration} is negative
370   * @throws IllegalStateException if the time to live or time to idle was already set
371   * @deprecated Caching functionality in {@code MapMaker} has been moved to
372   *     {@link com.google.common.cache.CacheBuilder}, with {@link #expireAfterWrite} being
373   *     replaced by {@link com.google.common.cache.CacheBuilder#expireAfterWrite}. Note that {@code
374   *     CacheBuilder} is simply an enhanced API for an implementation which was branched from
375   *     {@code MapMaker}.
376   */
377  @Deprecated
378  @Override
379  MapMaker expireAfterWrite(long duration, TimeUnit unit) {
380    checkExpiration(duration, unit);
381    this.expireAfterWriteNanos = unit.toNanos(duration);
382    if (duration == 0 && this.nullRemovalCause == null) {
383      // SIZE trumps EXPIRED
384      this.nullRemovalCause = RemovalCause.EXPIRED;
385    }
386    useCustomMap = true;
387    return this;
388  }
389
390  private void checkExpiration(long duration, TimeUnit unit) {
391    checkState(expireAfterWriteNanos == UNSET_INT, "expireAfterWrite was already set to %s ns",
392        expireAfterWriteNanos);
393    checkState(expireAfterAccessNanos == UNSET_INT, "expireAfterAccess was already set to %s ns",
394        expireAfterAccessNanos);
395    checkArgument(duration >= 0, "duration cannot be negative: %s %s", duration, unit);
396  }
397
398  long getExpireAfterWriteNanos() {
399    return (expireAfterWriteNanos == UNSET_INT) ? DEFAULT_EXPIRATION_NANOS : expireAfterWriteNanos;
400  }
401
402  /**
403   * Specifies that each entry should be automatically removed from the map once a fixed duration
404   * has elapsed after the entry's last read or write access.
405   *
406   * <p>When {@code duration} is zero, elements can be successfully added to the map, but are
407   * evicted immediately. This has a very similar effect to invoking {@link #maximumSize
408   * maximumSize}{@code (0)}. It can be useful in testing, or to disable caching temporarily without
409   * a code change.
410   *
411   * <p>Expired entries may be counted by {@link Map#size}, but will never be visible to read or
412   * write operations. Expired entries are currently cleaned up during write operations, or during
413   * occasional read operations in the absense of writes; though this behavior may change in the
414   * future.
415   *
416   * @param duration the length of time after an entry is last accessed that it should be
417   *     automatically removed
418   * @param unit the unit that {@code duration} is expressed in
419   * @throws IllegalArgumentException if {@code duration} is negative
420   * @throws IllegalStateException if the time to idle or time to live was already set
421   * @deprecated Caching functionality in {@code MapMaker} has been moved to
422   *     {@link com.google.common.cache.CacheBuilder}, with {@link #expireAfterAccess} being
423   *     replaced by {@link com.google.common.cache.CacheBuilder#expireAfterAccess}. Note that
424   *     {@code CacheBuilder} is simply an enhanced API for an implementation which was branched
425   *     from {@code MapMaker}.
426   */
427  @Deprecated
428  @GwtIncompatible("To be supported")
429  @Override
430  MapMaker expireAfterAccess(long duration, TimeUnit unit) {
431    checkExpiration(duration, unit);
432    this.expireAfterAccessNanos = unit.toNanos(duration);
433    if (duration == 0 && this.nullRemovalCause == null) {
434      // SIZE trumps EXPIRED
435      this.nullRemovalCause = RemovalCause.EXPIRED;
436    }
437    useCustomMap = true;
438    return this;
439  }
440
441  long getExpireAfterAccessNanos() {
442    return (expireAfterAccessNanos == UNSET_INT)
443        ? DEFAULT_EXPIRATION_NANOS : expireAfterAccessNanos;
444  }
445
446  Ticker getTicker() {
447    return MoreObjects.firstNonNull(ticker, Ticker.systemTicker());
448  }
449
450  /**
451   * Specifies a listener instance, which all maps built using this {@code MapMaker} will notify
452   * each time an entry is removed from the map by any means.
453   *
454   * <p>Each map built by this map maker after this method is called invokes the supplied listener
455   * after removing an element for any reason (see removal causes in {@link RemovalCause}). It will
456   * invoke the listener during invocations of any of that map's public methods (even read-only
457   * methods).
458   *
459   * <p><b>Important note:</b> Instead of returning <i>this</i> as a {@code MapMaker} instance,
460   * this method returns {@code GenericMapMaker<K, V>}. From this point on, either the original
461   * reference or the returned reference may be used to complete configuration and build the map,
462   * but only the "generic" one is type-safe. That is, it will properly prevent you from building
463   * maps whose key or value types are incompatible with the types accepted by the listener already
464   * provided; the {@code MapMaker} type cannot do this. For best results, simply use the standard
465   * method-chaining idiom, as illustrated in the documentation at top, configuring a {@code
466   * MapMaker} and building your {@link Map} all in a single statement.
467   *
468   * <p><b>Warning:</b> if you ignore the above advice, and use this {@code MapMaker} to build a map
469   * or cache whose key or value type is incompatible with the listener, you will likely experience
470   * a {@link ClassCastException} at some <i>undefined</i> point in the future.
471   *
472   * @throws IllegalStateException if a removal listener was already set
473   * @deprecated Caching functionality in {@code MapMaker} has been moved to
474   *     {@link com.google.common.cache.CacheBuilder}, with {@link #removalListener} being
475   *     replaced by {@link com.google.common.cache.CacheBuilder#removalListener}. Note that {@code
476   *     CacheBuilder} is simply an enhanced API for an implementation which was branched from
477   *     {@code MapMaker}.
478   */
479  @Deprecated
480  @GwtIncompatible("To be supported")
481  <K, V> GenericMapMaker<K, V> removalListener(RemovalListener<K, V> listener) {
482    checkState(this.removalListener == null);
483
484    // safely limiting the kinds of maps this can produce
485    @SuppressWarnings("unchecked")
486    GenericMapMaker<K, V> me = (GenericMapMaker<K, V>) this;
487    me.removalListener = checkNotNull(listener);
488    useCustomMap = true;
489    return me;
490  }
491
492  /**
493   * Builds a thread-safe map, without on-demand computation of values. This method does not alter
494   * the state of this {@code MapMaker} instance, so it can be invoked again to create multiple
495   * independent maps.
496   *
497   * <p>The bulk operations {@code putAll}, {@code equals}, and {@code clear} are not guaranteed to
498   * be performed atomically on the returned map. Additionally, {@code size} and {@code
499   * containsValue} are implemented as bulk read operations, and thus may fail to observe concurrent
500   * writes.
501   *
502   * @return a serializable concurrent map having the requested features
503   */
504  @Override
505  public <K, V> ConcurrentMap<K, V> makeMap() {
506    if (!useCustomMap) {
507      return new ConcurrentHashMap<K, V>(getInitialCapacity(), 0.75f, getConcurrencyLevel());
508    }
509    return (nullRemovalCause == null)
510        ? new MapMakerInternalMap<K, V>(this)
511        : new NullConcurrentMap<K, V>(this);
512  }
513
514  /**
515   * Returns a MapMakerInternalMap for the benefit of internal callers that use features of
516   * that class not exposed through ConcurrentMap.
517   */
518  @Override
519  @GwtIncompatible("MapMakerInternalMap")
520  <K, V> MapMakerInternalMap<K, V> makeCustomMap() {
521    return new MapMakerInternalMap<K, V>(this);
522  }
523
524  /**
525   * Builds a map that supports atomic, on-demand computation of values. {@link Map#get} either
526   * returns an already-computed value for the given key, atomically computes it using the supplied
527   * function, or, if another thread is currently computing the value for this key, simply waits for
528   * that thread to finish and returns its computed value. Note that the function may be executed
529   * concurrently by multiple threads, but only for distinct keys.
530   *
531   * <p>New code should use {@link com.google.common.cache.CacheBuilder}, which supports
532   * {@linkplain com.google.common.cache.CacheStats statistics} collection, introduces the
533   * {@link com.google.common.cache.CacheLoader} interface for loading entries into the cache
534   * (allowing checked exceptions to be thrown in the process), and more cleanly separates
535   * computation from the cache's {@code Map} view.
536   *
537   * <p>If an entry's value has not finished computing yet, query methods besides {@code get} return
538   * immediately as if an entry doesn't exist. In other words, an entry isn't externally visible
539   * until the value's computation completes.
540   *
541   * <p>{@link Map#get} on the returned map will never return {@code null}. It may throw:
542   *
543   * <ul>
544   * <li>{@link NullPointerException} if the key is null or the computing function returns a null
545   *     result
546   * <li>{@link ComputationException} if an exception was thrown by the computing function. If that
547   * exception is already of type {@link ComputationException} it is propagated directly; otherwise
548   * it is wrapped.
549   * </ul>
550   *
551   * <p><b>Note:</b> Callers of {@code get} <i>must</i> ensure that the key argument is of type
552   * {@code K}. The {@code get} method accepts {@code Object}, so the key type is not checked at
553   * compile time. Passing an object of a type other than {@code K} can result in that object being
554   * unsafely passed to the computing function as type {@code K}, and unsafely stored in the map.
555   *
556   * <p>If {@link Map#put} is called before a computation completes, other threads waiting on the
557   * computation will wake up and return the stored value.
558   *
559   * <p>This method does not alter the state of this {@code MapMaker} instance, so it can be invoked
560   * again to create multiple independent maps.
561   *
562   * <p>Insertion, removal, update, and access operations on the returned map safely execute
563   * concurrently by multiple threads. Iterators on the returned map are weakly consistent,
564   * returning elements reflecting the state of the map at some point at or since the creation of
565   * the iterator. They do not throw {@link ConcurrentModificationException}, and may proceed
566   * concurrently with other operations.
567   *
568   * <p>The bulk operations {@code putAll}, {@code equals}, and {@code clear} are not guaranteed to
569   * be performed atomically on the returned map. Additionally, {@code size} and {@code
570   * containsValue} are implemented as bulk read operations, and thus may fail to observe concurrent
571   * writes.
572   *
573   * @param computingFunction the function used to compute new values
574   * @return a serializable concurrent map having the requested features
575   * @deprecated Caching functionality in {@code MapMaker} has been moved to
576   *     {@link com.google.common.cache.CacheBuilder}, with {@link #makeComputingMap} being replaced
577   *     by {@link com.google.common.cache.CacheBuilder#build}. See the
578   *     <a href="http://code.google.com/p/guava-libraries/wiki/MapMakerMigration">MapMaker
579   *     Migration Guide</a> for more details.
580   */
581  @Deprecated
582  @Override
583  <K, V> ConcurrentMap<K, V> makeComputingMap(
584      Function<? super K, ? extends V> computingFunction) {
585    return (nullRemovalCause == null)
586        ? new MapMaker.ComputingMapAdapter<K, V>(this, computingFunction)
587        : new NullComputingConcurrentMap<K, V>(this, computingFunction);
588  }
589
590  /**
591   * Returns a string representation for this MapMaker instance. The exact form of the returned
592   * string is not specificed.
593   */
594  @Override
595  public String toString() {
596    MoreObjects.ToStringHelper s = MoreObjects.toStringHelper(this);
597    if (initialCapacity != UNSET_INT) {
598      s.add("initialCapacity", initialCapacity);
599    }
600    if (concurrencyLevel != UNSET_INT) {
601      s.add("concurrencyLevel", concurrencyLevel);
602    }
603    if (maximumSize != UNSET_INT) {
604      s.add("maximumSize", maximumSize);
605    }
606    if (expireAfterWriteNanos != UNSET_INT) {
607      s.add("expireAfterWrite", expireAfterWriteNanos + "ns");
608    }
609    if (expireAfterAccessNanos != UNSET_INT) {
610      s.add("expireAfterAccess", expireAfterAccessNanos + "ns");
611    }
612    if (keyStrength != null) {
613      s.add("keyStrength", Ascii.toLowerCase(keyStrength.toString()));
614    }
615    if (valueStrength != null) {
616      s.add("valueStrength", Ascii.toLowerCase(valueStrength.toString()));
617    }
618    if (keyEquivalence != null) {
619      s.addValue("keyEquivalence");
620    }
621    if (removalListener != null) {
622      s.addValue("removalListener");
623    }
624    return s.toString();
625  }
626
627  /**
628   * An object that can receive a notification when an entry is removed from a map. The removal
629   * resulting in notification could have occured to an entry being manually removed or replaced, or
630   * due to eviction resulting from timed expiration, exceeding a maximum size, or garbage
631   * collection.
632   *
633   * <p>An instance may be called concurrently by multiple threads to process different entries.
634   * Implementations of this interface should avoid performing blocking calls or synchronizing on
635   * shared resources.
636   *
637   * @param <K> the most general type of keys this listener can listen for; for
638   *     example {@code Object} if any key is acceptable
639   * @param <V> the most general type of values this listener can listen for; for
640   *     example {@code Object} if any key is acceptable
641   */
642  interface RemovalListener<K, V> {
643    /**
644     * Notifies the listener that a removal occurred at some point in the past.
645     */
646    void onRemoval(RemovalNotification<K, V> notification);
647  }
648
649  /**
650   * A notification of the removal of a single entry. The key or value may be null if it was already
651   * garbage collected.
652   *
653   * <p>Like other {@code Map.Entry} instances associated with MapMaker, this class holds strong
654   * references to the key and value, regardless of the type of references the map may be using.
655   */
656  static final class RemovalNotification<K, V> extends ImmutableEntry<K, V> {
657    private static final long serialVersionUID = 0;
658
659    private final RemovalCause cause;
660
661    RemovalNotification(@Nullable K key, @Nullable V value, RemovalCause cause) {
662      super(key, value);
663      this.cause = cause;
664    }
665
666    /**
667     * Returns the cause for which the entry was removed.
668     */
669    public RemovalCause getCause() {
670      return cause;
671    }
672
673    /**
674     * Returns {@code true} if there was an automatic removal due to eviction (the cause is neither
675     * {@link RemovalCause#EXPLICIT} nor {@link RemovalCause#REPLACED}).
676     */
677    public boolean wasEvicted() {
678      return cause.wasEvicted();
679    }
680  }
681
682  /**
683   * The reason why an entry was removed.
684   */
685  enum RemovalCause {
686    /**
687     * The entry was manually removed by the user. This can result from the user invoking
688     * {@link Map#remove}, {@link ConcurrentMap#remove}, or {@link java.util.Iterator#remove}.
689     */
690    EXPLICIT {
691      @Override
692      boolean wasEvicted() {
693        return false;
694      }
695    },
696
697    /**
698     * The entry itself was not actually removed, but its value was replaced by the user. This can
699     * result from the user invoking {@link Map#put}, {@link Map#putAll},
700     * {@link ConcurrentMap#replace(Object, Object)}, or
701     * {@link ConcurrentMap#replace(Object, Object, Object)}.
702     */
703    REPLACED {
704      @Override
705      boolean wasEvicted() {
706        return false;
707      }
708    },
709
710    /**
711     * The entry was removed automatically because its key or value was garbage-collected. This can
712     * occur when using {@link #softValues}, {@link #weakKeys}, or {@link #weakValues}.
713     */
714    COLLECTED {
715      @Override
716      boolean wasEvicted() {
717        return true;
718      }
719    },
720
721    /**
722     * The entry's expiration timestamp has passed. This can occur when using {@link
723     * #expireAfterWrite} or {@link #expireAfterAccess}.
724     */
725    EXPIRED {
726      @Override
727      boolean wasEvicted() {
728        return true;
729      }
730    },
731
732    /**
733     * The entry was evicted due to size constraints. This can occur when using {@link
734     * #maximumSize}.
735     */
736    SIZE {
737      @Override
738      boolean wasEvicted() {
739        return true;
740      }
741    };
742
743    /**
744     * Returns {@code true} if there was an automatic removal due to eviction (the cause is neither
745     * {@link #EXPLICIT} nor {@link #REPLACED}).
746     */
747    abstract boolean wasEvicted();
748  }
749
750  /** A map that is always empty and evicts on insertion. */
751  static class NullConcurrentMap<K, V> extends AbstractMap<K, V>
752      implements ConcurrentMap<K, V>, Serializable {
753    private static final long serialVersionUID = 0;
754
755    private final RemovalListener<K, V> removalListener;
756    private final RemovalCause removalCause;
757
758    NullConcurrentMap(MapMaker mapMaker) {
759      removalListener = mapMaker.getRemovalListener();
760      removalCause = mapMaker.nullRemovalCause;
761    }
762
763    // implements ConcurrentMap
764
765    @Override
766    public boolean containsKey(@Nullable Object key) {
767      return false;
768    }
769
770    @Override
771    public boolean containsValue(@Nullable Object value) {
772      return false;
773    }
774
775    @Override
776    public V get(@Nullable Object key) {
777      return null;
778    }
779
780    void notifyRemoval(K key, V value) {
781      RemovalNotification<K, V> notification =
782          new RemovalNotification<K, V>(key, value, removalCause);
783      removalListener.onRemoval(notification);
784    }
785
786    @Override
787    public V put(K key, V value) {
788      checkNotNull(key);
789      checkNotNull(value);
790      notifyRemoval(key, value);
791      return null;
792    }
793
794    @Override
795    public V putIfAbsent(K key, V value) {
796      return put(key, value);
797    }
798
799    @Override
800    public V remove(@Nullable Object key) {
801      return null;
802    }
803
804    @Override
805    public boolean remove(@Nullable Object key, @Nullable Object value) {
806      return false;
807    }
808
809    @Override
810    public V replace(K key, V value) {
811      checkNotNull(key);
812      checkNotNull(value);
813      return null;
814    }
815
816    @Override
817    public boolean replace(K key, @Nullable V oldValue, V newValue) {
818      checkNotNull(key);
819      checkNotNull(newValue);
820      return false;
821    }
822
823    @Override
824    public Set<Entry<K, V>> entrySet() {
825      return Collections.emptySet();
826    }
827  }
828
829  /** Computes on retrieval and evicts the result. */
830  static final class NullComputingConcurrentMap<K, V> extends NullConcurrentMap<K, V> {
831    private static final long serialVersionUID = 0;
832
833    final Function<? super K, ? extends V> computingFunction;
834
835    NullComputingConcurrentMap(
836        MapMaker mapMaker, Function<? super K, ? extends V> computingFunction) {
837      super(mapMaker);
838      this.computingFunction = checkNotNull(computingFunction);
839    }
840
841    @SuppressWarnings("unchecked") // unsafe, which is why Cache is preferred
842    @Override
843    public V get(Object k) {
844      K key = (K) k;
845      V value = compute(key);
846      checkNotNull(value, "%s returned null for key %s.", computingFunction, key);
847      notifyRemoval(key, value);
848      return value;
849    }
850
851    private V compute(K key) {
852      checkNotNull(key);
853      try {
854        return computingFunction.apply(key);
855      } catch (ComputationException e) {
856        throw e;
857      } catch (Throwable t) {
858        throw new ComputationException(t);
859      }
860    }
861  }
862
863  /**
864   * Overrides get() to compute on demand. Also throws an exception when {@code null} is returned
865   * from a computation.
866   */
867  /*
868   * This might make more sense in ComputingConcurrentHashMap, but it causes a javac crash in some
869   * cases there: http://code.google.com/p/guava-libraries/issues/detail?id=950
870   */
871  static final class ComputingMapAdapter<K, V>
872      extends ComputingConcurrentHashMap<K, V> implements Serializable {
873    private static final long serialVersionUID = 0;
874
875    ComputingMapAdapter(MapMaker mapMaker,
876        Function<? super K, ? extends V> computingFunction) {
877      super(mapMaker, computingFunction);
878    }
879
880    @SuppressWarnings("unchecked") // unsafe, which is one advantage of Cache over Map
881    @Override
882    public V get(Object key) {
883      V value;
884      try {
885        value = getOrCompute((K) key);
886      } catch (ExecutionException e) {
887        Throwable cause = e.getCause();
888        Throwables.propagateIfInstanceOf(cause, ComputationException.class);
889        throw new ComputationException(cause);
890      }
891
892      if (value == null) {
893        throw new NullPointerException(computingFunction + " returned null for key " + key + ".");
894      }
895      return value;
896    }
897  }
898}
899