001 /*
002 * Copyright (C) 2009 Google Inc.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021 import static com.google.common.base.Preconditions.checkState;
022
023 import com.google.common.annotations.Beta;
024 import com.google.common.annotations.GwtCompatible;
025 import com.google.common.annotations.GwtIncompatible;
026 import com.google.common.base.Equivalence;
027 import com.google.common.base.Function;
028 import com.google.common.base.Objects;
029 import com.google.common.collect.CustomConcurrentHashMap.Strength;
030
031 import java.io.Serializable;
032 import java.lang.ref.SoftReference;
033 import java.lang.ref.WeakReference;
034 import java.util.Map;
035 import java.util.concurrent.ConcurrentHashMap;
036 import java.util.concurrent.ConcurrentMap;
037 import java.util.concurrent.TimeUnit;
038
039 /**
040 * <p>A {@link ConcurrentMap} builder, providing any combination of these
041 * features: {@linkplain SoftReference soft} or {@linkplain WeakReference
042 * weak} keys, soft or weak values, size-based evicition, timed expiration, and
043 * on-demand computation of values. Usage example: <pre> {@code
044 *
045 * ConcurrentMap<Key, Graph> graphs = new MapMaker()
046 * .concurrencyLevel(4)
047 * .softKeys()
048 * .weakValues()
049 * .maximumSize(10000)
050 * .expireAfterWrite(10, TimeUnit.MINUTES)
051 * .makeComputingMap(
052 * new Function<Key, Graph>() {
053 * public Graph apply(Key key) {
054 * return createExpensiveGraph(key);
055 * }
056 * });}</pre>
057 *
058 * These features are all optional; {@code new MapMaker().makeMap()}
059 * returns a valid concurrent map that behaves exactly like a
060 * {@link ConcurrentHashMap}.
061 *
062 * The returned map is implemented as a hash table with similar performance
063 * characteristics to {@link ConcurrentHashMap}. It supports all optional
064 * operations of the {@code ConcurrentMap} interface. It does not permit
065 * null keys or values.
066 *
067 * <p><b>Note:</b> by default, the returned map uses equality comparisons
068 * (the {@link Object#equals(Object) equals} method) to determine equality
069 * for keys or values. However, if {@link #weakKeys()} or {@link
070 * #softKeys()} was specified, the map uses identity ({@code ==})
071 * comparisons instead for keys. Likewise, if {@link #weakValues()} or
072 * {@link #softValues()} was specified, the map uses identity comparisons
073 * for values.
074 *
075 * <p>The returned map has <i>weakly consistent iteration</i>: an iterator
076 * over one of the map's view collections may reflect some, all or none of
077 * the changes made to the map after the iterator was created.
078 *
079 * <p>An entry whose key or value is reclaimed by the garbage collector
080 * immediately disappears from the map. (If the default settings of strong
081 * keys and strong values are used, this will never happen.) The client can
082 * never observe a partially-reclaimed entry. Any {@link java.util.Map.Entry}
083 * instance retrieved from the map's {@linkplain Map#entrySet() entry set}
084 * is a snapshot of that entry's state at the time of retrieval; such entries
085 * do, however, support {@link java.util.Map.Entry#setValue}.
086 *
087 * <p>The maps produced by {@code MapMaker} are serializable, and the
088 * deserialized maps retain all the configuration properties of the original
089 * map. If the map uses soft or weak references, the entries will be
090 * reconstructed as they were, but there is no guarantee that the entries won't
091 * be immediately reclaimed.
092 *
093 * <p>{@code new MapMaker().weakKeys().makeMap()} can almost always be
094 * used as a drop-in replacement for {@link java.util.WeakHashMap}, adding
095 * concurrency, asynchronous cleanup, identity-based equality for keys, and
096 * great flexibility.
097 *
098 * @author Bob Lee
099 * @author Kevin Bourrillion
100 * @since 2 (imported from Google Collections Library)
101 */
102 @GwtCompatible(emulated = true)
103 public final class MapMaker extends GenericMapMaker<Object, Object> {
104 private static final int DEFAULT_INITIAL_CAPACITY = 16;
105 private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
106 private static final int DEFAULT_EXPIRATION_NANOS = 0;
107
108 static final int UNSET_INT = -1;
109
110 int initialCapacity = UNSET_INT;
111 int concurrencyLevel = UNSET_INT;
112 int maximumSize = UNSET_INT;
113
114 Strength keyStrength;
115 Strength valueStrength;
116
117 long expireAfterWriteNanos = UNSET_INT;
118 long expireAfterAccessNanos = UNSET_INT;
119
120 // TODO(kevinb): dispense with this after benchmarking
121 boolean useCustomMap;
122
123 Equivalence<Object> keyEquivalence;
124 Equivalence<Object> valueEquivalence;
125
126 /**
127 * Constructs a new {@code MapMaker} instance with default settings,
128 * including strong keys, strong values, and no automatic expiration.
129 */
130 public MapMaker() {}
131
132 // TODO(kevinb): undo this indirection if keyEquiv gets released
133 MapMaker privateKeyEquivalence(Equivalence<Object> equivalence) {
134 checkState(keyEquivalence == null,
135 "key equivalence was already set to %s", keyEquivalence);
136 keyEquivalence = checkNotNull(equivalence);
137 this.useCustomMap = true;
138 return this;
139 }
140
141 Equivalence<Object> getKeyEquivalence() {
142 return Objects.firstNonNull(keyEquivalence,
143 getKeyStrength().defaultEquivalence());
144 }
145
146 // TODO(kevinb): undo this indirection if valueEquiv gets released
147 MapMaker privateValueEquivalence(Equivalence<Object> equivalence) {
148 checkState(valueEquivalence == null,
149 "value equivalence was already set to %s", valueEquivalence);
150 this.valueEquivalence = checkNotNull(equivalence);
151 this.useCustomMap = true;
152 return this;
153 }
154
155 Equivalence<Object> getValueEquivalence() {
156 return Objects.firstNonNull(valueEquivalence,
157 getValueStrength().defaultEquivalence());
158 }
159
160 /**
161 * Sets a custom initial capacity (defaults to 16). Resizing this or
162 * any other kind of hash table is a relatively slow operation, so,
163 * when possible, it is a good idea to provide estimates of expected
164 * table sizes.
165 *
166 * @throws IllegalArgumentException if {@code initialCapacity} is
167 * 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,
173 "initial capacity was already set to %s", this.initialCapacity);
174 checkArgument(initialCapacity >= 0);
175 this.initialCapacity = initialCapacity;
176 return this;
177 }
178
179 int getInitialCapacity() {
180 return (initialCapacity == UNSET_INT)
181 ? DEFAULT_INITIAL_CAPACITY : initialCapacity;
182 }
183
184 /**
185 * Specifies the maximum number of entries the map may contain. While the
186 * number of entries in the map is not guaranteed to grow to the maximum,
187 * the map will attempt to make the best use of memory without exceeding the
188 * maximum number of entries. As the map size grows close to the maximum,
189 * the map will evict entries that are less likely to be used again. For
190 * example, the map may evict an entry because it hasn't been used recently
191 * or very often.
192 *
193 * @param size the maximum size of the map
194 *
195 * @throws IllegalArgumentException if {@code size} is not greater than zero
196 * @throws IllegalStateException if a maximum size was already set
197 * @since 8
198 */
199 @Beta
200 @GwtIncompatible("To be supported")
201 @Override
202 public MapMaker maximumSize(int size) {
203 checkState(this.maximumSize == UNSET_INT,
204 "maximum size was already set to %s", this.maximumSize);
205 checkArgument(size > 0, "maximum size must be positive");
206 this.maximumSize = size;
207 this.useCustomMap = true;
208 return this;
209 }
210
211 /**
212 * Guides the allowed concurrency among update operations. Used as a
213 * hint for internal sizing. The table is internally partitioned to try
214 * to permit the indicated number of concurrent updates without
215 * contention. Because placement in hash tables is essentially random,
216 * the actual concurrency will vary. Ideally, you should choose a value
217 * to accommodate as many threads as will ever concurrently modify the
218 * table. Using a significantly higher value than you need can waste
219 * space and time, and a significantly lower value can lead to thread
220 * contention. But overestimates and underestimates within an order of
221 * magnitude do not usually have much noticeable impact. A value of one
222 * is appropriate when it is known that only one thread will modify and
223 * all others will only read. Defaults to 16.
224 *
225 * @throws IllegalArgumentException if {@code concurrencyLevel} is
226 * nonpositive
227 * @throws IllegalStateException if a concurrency level was already set
228 */
229 @GwtIncompatible("java.util.concurrent.ConcurrentHashMap concurrencyLevel")
230 @Override
231 public MapMaker concurrencyLevel(int concurrencyLevel) {
232 checkState(this.concurrencyLevel == UNSET_INT,
233 "concurrency level was already set to %s", this.concurrencyLevel);
234 checkArgument(concurrencyLevel > 0);
235 this.concurrencyLevel = concurrencyLevel;
236 return this;
237 }
238
239 int getConcurrencyLevel() {
240 return (concurrencyLevel == UNSET_INT)
241 ? DEFAULT_CONCURRENCY_LEVEL : concurrencyLevel;
242 }
243
244 /**
245 * Specifies that each key (not value) stored in the map should be
246 * wrapped in a {@link WeakReference} (by default, strong references
247 * are used).
248 *
249 * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
250 * to determine equality of weak keys, which may not behave as you expect.
251 * For example, storing a key in the map and then attempting a lookup
252 * using a different but {@link Object#equals(Object) equals}-equivalent
253 * key will always fail.
254 *
255 * @throws IllegalStateException if the key strength was already set
256 * @see WeakReference
257 */
258 @GwtIncompatible("java.lang.ref.WeakReference")
259 @Override
260 public MapMaker weakKeys() {
261 return setKeyStrength(Strength.WEAK);
262 }
263
264 /**
265 * Specifies that each key (not value) stored in the map should be
266 * wrapped in a {@link SoftReference} (by default, strong references
267 * are used).
268 *
269 * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
270 * to determine equality of soft keys, which may not behave as you expect.
271 * For example, storing a key in the map and then attempting a lookup
272 * using a different but {@link Object#equals(Object) equals}-equivalent
273 * key will always fail.
274 *
275 * @throws IllegalStateException if the key strength was already set
276 * @see SoftReference
277 */
278 @GwtIncompatible("java.lang.ref.SoftReference")
279 @Override
280 public MapMaker softKeys() {
281 return setKeyStrength(Strength.SOFT);
282 }
283
284 MapMaker setKeyStrength(Strength strength) {
285 checkState(keyStrength == null,
286 "Key strength was already set to %s", keyStrength);
287 keyStrength = checkNotNull(strength);
288 if (strength != Strength.STRONG) {
289 // STRONG could be used during deserialization.
290 useCustomMap = true;
291 }
292 return this;
293 }
294
295 Strength getKeyStrength() {
296 return Objects.firstNonNull(keyStrength, Strength.STRONG);
297 }
298
299 /**
300 * Specifies that each value (not key) stored in the map should be
301 * wrapped in a {@link WeakReference} (by default, strong references
302 * are used).
303 *
304 * <p>Weak values will be garbage collected once they are weakly
305 * reachable. This makes them a poor candidate for caching; consider
306 * {@link #softValues()} instead.
307 *
308 * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
309 * to determine equality of weak values. This will notably impact
310 * the behavior of {@link Map#containsValue(Object) containsValue},
311 * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)},
312 * and {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}.
313 *
314 * @throws IllegalStateException if the value strength was already set
315 * @see WeakReference
316 */
317 @GwtIncompatible("java.lang.ref.WeakReference")
318 @Override
319 public MapMaker weakValues() {
320 return setValueStrength(Strength.WEAK);
321 }
322
323 /**
324 * Specifies that each value (not key) stored in the map should be
325 * wrapped in a {@link SoftReference} (by default, strong references
326 * are used).
327 *
328 * <p>Soft values will be garbage collected in response to memory
329 * demand, and in a least-recently-used manner. This makes them a
330 * good candidate for caching.
331 *
332 * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
333 * to determine equality of soft values. This will notably impact
334 * the behavior of {@link Map#containsValue(Object) containsValue},
335 * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)},
336 * and {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}.
337 *
338 * @throws IllegalStateException if the value strength was already set
339 * @see SoftReference
340 */
341 @GwtIncompatible("java.lang.ref.SoftReference")
342 @Override
343 public MapMaker softValues() {
344 return setValueStrength(Strength.SOFT);
345 }
346
347 MapMaker setValueStrength(Strength strength) {
348 checkState(valueStrength == null,
349 "Value strength was already set to %s", valueStrength);
350 valueStrength = checkNotNull(strength);
351 if (strength != Strength.STRONG) {
352 // STRONG could be used during deserialization.
353 useCustomMap = true;
354 }
355 return this;
356 }
357
358 Strength getValueStrength() {
359 return Objects.firstNonNull(valueStrength, Strength.STRONG);
360 }
361
362 /**
363 * Old name of {@link #expireAfterWrite}.
364 *
365 * @deprecated use {@link #expireAfterWrite}, which behaves exactly the same.
366 * <b>This method is scheduled for deletion in July 2012.</b>
367 */
368 @Deprecated
369 @Override
370 public MapMaker expiration(long duration, TimeUnit unit) {
371 return expireAfterWrite(duration, unit);
372 }
373
374 /**
375 * Specifies that each entry should be automatically removed from the
376 * map once a fixed duration has passed since the entry's creation.
377 * Note that changing the value of an entry will reset its expiration
378 * time.
379 *
380 * @param duration the length of time after an entry is created that it
381 * should be automatically removed
382 * @param unit the unit that {@code duration} is expressed in
383 * @throws IllegalArgumentException if {@code duration} is not positive, or is
384 * larger than one hundred years
385 * @throws IllegalStateException if the time to live or time to idle was
386 * already set
387 * @since 8
388 */
389 @Beta
390 @Override
391 public MapMaker expireAfterWrite(long duration, TimeUnit unit) {
392 checkExpiration(duration, unit);
393 this.expireAfterWriteNanos = unit.toNanos(duration);
394 useCustomMap = true;
395 return this;
396 }
397
398 private void checkExpiration(long duration, TimeUnit unit) {
399 checkState(expireAfterWriteNanos == UNSET_INT,
400 "expireAfterWrite was already set to %s ns",
401 expireAfterWriteNanos);
402 checkState(expireAfterAccessNanos == UNSET_INT,
403 "expireAfterAccess was already set to %s ns",
404 expireAfterAccessNanos);
405 checkArgument(duration > 0, "duration must be positive: %s %s",
406 duration, unit);
407 }
408
409 long getExpireAfterWriteNanos() {
410 return (expireAfterWriteNanos == UNSET_INT)
411 ? DEFAULT_EXPIRATION_NANOS : expireAfterWriteNanos;
412 }
413
414 /**
415 * Specifies that each entry should be automatically removed from the
416 * map once a fixed duration has passed since the entry's last access.
417 *
418 * @param duration the length of time after an entry is last accessed
419 * that it should be automatically removed
420 * @param unit the unit that {@code duration} is expressed in
421 * @throws IllegalArgumentException if {@code duration} is not positive, or is
422 * larger than one hundred years
423 * @throws IllegalStateException if the time to idle or time to live was
424 * already set
425 * @since 8
426 */
427 @Beta
428 @GwtIncompatible("To be supported")
429 @Override
430 public MapMaker expireAfterAccess(long duration, TimeUnit unit) {
431 checkExpiration(duration, unit);
432 this.expireAfterAccessNanos = unit.toNanos(duration);
433 useCustomMap = true;
434 return this;
435 }
436
437 long getExpireAfterAccessNanos() {
438 return (expireAfterAccessNanos == UNSET_INT)
439 ? DEFAULT_EXPIRATION_NANOS : expireAfterAccessNanos;
440 }
441
442 /**
443 * Specifies a listener instance, which all maps built using this {@code
444 * MapMaker} will notify each time an entry is evicted.
445 *
446 * <p>A map built by this map maker will invoke the supplied listener after it
447 * evicts an entry, whether it does so due to timed expiration, exceeding the
448 * maximum size, or discovering that the key or value has been reclaimed by
449 * the garbage collector. It will invoke the listener synchronously, during
450 * invocations of any of that map's public methods (even read-only methods).
451 * The listener will <i>not</i> be invoked on manual removal.
452 *
453 * <p><b>Important note:</b> Instead of returning <em>this</em> as a {@code
454 * MapMaker} instance, this method returns {@code GenericMapMaker<K, V>}.
455 * From this point on, either the original reference or the returned
456 * reference may be used to complete configuration and build the map, but only
457 * the "generic" one is type-safe. That is, it will properly prevent you from
458 * building maps whose key or value types are incompatible with the types
459 * accepted by the listener already provided; the {@code MapMaker} type cannot
460 * do this. For best results, simply use the standard method-chaining idiom,
461 * as illustrated in the documentation at top, configuring a {@code MapMaker}
462 * and building your {@link Map} all in a single statement.
463 *
464 * <p><b>Warning:</b> if you ignore the above advice, and use this {@code
465 * MapMaker} to build maps whose key or value types are incompatible with the
466 * listener, you will likely experience a {@link ClassCastException} at an
467 * undefined point in the future.
468 *
469 * @throws IllegalStateException if an eviction listener was already set
470 * @since 7
471 */
472 @Beta
473 @GwtIncompatible("To be supported")
474 public <K, V> GenericMapMaker<K, V> evictionListener(
475 MapEvictionListener<K, V> listener) {
476 checkState(this.evictionListener == null);
477
478 // safely limiting the kinds of maps this can produce
479 @SuppressWarnings("unchecked")
480 GenericMapMaker<K, V> me = (GenericMapMaker<K, V>) this;
481 me.evictionListener = checkNotNull(listener);
482 useCustomMap = true;
483 return me;
484 }
485
486 /**
487 * Builds a map, without on-demand computation of values. This method
488 * does not alter the state of this {@code MapMaker} instance, so it can be
489 * invoked again to create multiple independent maps.
490 *
491 * @return a serializable concurrent map having the requested features
492 */
493 @Override
494 public <K, V> ConcurrentMap<K, V> makeMap() {
495 return useCustomMap
496 ? new CustomConcurrentHashMap<K, V>(this)
497 : new ConcurrentHashMap<K, V>(getInitialCapacity(),
498 0.75f, getConcurrencyLevel());
499 }
500
501 /**
502 * Builds a caching function, which either returns an already-computed value
503 * for a given key or atomically computes it using the supplied function.
504 * If another thread is currently computing the value for this key, simply
505 * waits for that thread to finish and returns its computed value. Note that
506 * the function may be executed concurrently by multiple threads, but only for
507 * distinct keys.
508 *
509 * <p>The {@code Map} view of the {@code Cache}'s cache is only
510 * updated when function computation completes. In other words, an entry isn't
511 * visible until the value's computation completes. No methods on the {@code
512 * Map} will ever trigger computation.
513 *
514 * <p>{@link Cache#apply} in the returned function implementation may
515 * throw:
516 *
517 * <ul>
518 * <li>{@link NullPointerException} if the key is null or the
519 * computing function returns null
520 * <li>{@link ComputationException} if an exception was thrown by the
521 * computing function. If that exception is already of type {@link
522 * ComputationException} it is propagated directly; otherwise it is
523 * wrapped.
524 * </ul>
525 *
526 * <p>If {@link Map#put} is called before a computation completes, other
527 * threads waiting on the computation will wake up and return the stored
528 * value. When the computation completes, its result will be ignored.
529 *
530 * <p>This method does not alter the state of this {@code MapMaker} instance,
531 * so it can be invoked again to create multiple independent maps.
532 *
533 * @param computingFunction the function used to compute new values
534 * @return a serializable cache having the requested features
535 */
536 // TODO(kevinb): figure out the Cache interface before making this public
537 <K, V> Cache<K, V> makeCache(
538 Function<? super K, ? extends V> computingFunction) {
539 return new ComputingConcurrentHashMap<K, V>(this, computingFunction);
540 }
541
542 /**
543 * Builds a map that supports atomic, on-demand computation of values. {@link
544 * Map#get} either returns an already-computed value for the given key,
545 * atomically computes it using the supplied function, or, if another thread
546 * is currently computing the value for this key, simply waits for that thread
547 * to finish and returns its computed value. Note that the function may be
548 * executed concurrently by multiple threads, but only for distinct keys.
549 *
550 * <p>If an entry's value has not finished computing yet, query methods
551 * besides {@code get} return immediately as if an entry doesn't exist. In
552 * other words, an entry isn't externally visible until the value's
553 * computation completes.
554 *
555 * <p>{@link Map#get} on the returned map will never return {@code null}. It
556 * may throw:
557 *
558 * <ul>
559 * <li>{@link NullPointerException} if the key is null or the computing
560 * function returns null
561 * <li>{@link ComputationException} if an exception was thrown by the
562 * computing function. If that exception is already of type {@link
563 * ComputationException} it is propagated directly; otherwise it is
564 * wrapped.
565 * </ul>
566 *
567 * <p><b>Note:</b> Callers of {@code get} <i>must</i> ensure that the key
568 * argument is of type {@code K}. The {@code get} method accepts {@code
569 * Object}, so the key type is not checked at compile time. Passing an object
570 * of a type other than {@code K} can result in that object being unsafely
571 * passed to the computing function as type {@code K}, and unsafely stored in
572 * the map.
573 *
574 * <p>If {@link Map#put} is called before a computation completes, other
575 * threads waiting on the computation will wake up and return the stored
576 * value.
577 *
578 * <p>This method does not alter the state of this {@code MapMaker} instance,
579 * so it can be invoked again to create multiple independent maps.
580 *
581 * @param computingFunction the function used to compute new values
582 * @return a serializable concurrent map having the requested features
583 */
584 @Override
585 public <K, V> ConcurrentMap<K, V> makeComputingMap(
586 Function<? super K, ? extends V> computingFunction) {
587 Cache<K, V> cache = makeCache(computingFunction);
588 return new ComputingMapAdapter<K, V>(cache);
589 }
590
591 /**
592 * A function which caches the result of each application (computation). This
593 * interface does not specify the caching semantics, but does expose a {@code
594 * ConcurrentMap} view of cached entries.
595 */
596 interface Cache<K, V> extends Function<K, V> {
597
598 /**
599 * Returns a map view of the cached entries.
600 */
601 ConcurrentMap<K, V> asMap();
602 }
603
604 /**
605 * Overrides get() to compute on demand.
606 */
607 static class ComputingMapAdapter<K, V> extends ForwardingConcurrentMap<K, V>
608 implements Serializable {
609 private static final long serialVersionUID = 0;
610
611 final Cache<K, V> cache;
612
613 ComputingMapAdapter(Cache<K, V> cache) {
614 this.cache = cache;
615 }
616
617 @Override protected ConcurrentMap<K, V> delegate() {
618 return cache.asMap();
619 }
620
621 @SuppressWarnings("unchecked") // unsafe, which is why this is deprecated
622 @Override public V get(Object key) {
623 return cache.apply((K) key);
624 }
625 }
626 }