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