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