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