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