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.GwtCompatible;
024 import com.google.common.annotations.GwtIncompatible;
025 import com.google.common.base.Equivalence;
026 import com.google.common.base.Function;
027 import com.google.common.base.Objects;
028 import com.google.common.collect.CustomConcurrentHashMap.Strength;
029
030 import java.io.Serializable;
031 import java.lang.ref.SoftReference;
032 import java.lang.ref.WeakReference;
033 import java.util.Map;
034 import java.util.concurrent.ConcurrentHashMap;
035 import java.util.concurrent.ConcurrentMap;
036 import java.util.concurrent.TimeUnit;
037
038 /**
039 * <p>A {@link ConcurrentMap} builder, providing any combination of these
040 * features: {@linkplain SoftReference soft} or {@linkplain WeakReference
041 * weak} keys, soft or weak values, timed expiration, and on-demand
042 * computation of values. Usage example: <pre> {@code
043 *
044 * ConcurrentMap<Key, Graph> graphs = new MapMaker()
045 * .concurrencyLevel(32)
046 * .softKeys()
047 * .weakValues()
048 * .expiration(30, TimeUnit.MINUTES)
049 * .makeComputingMap(
050 * new Function<Key, Graph>() {
051 * public Graph apply(Key key) {
052 * return createExpensiveGraph(key);
053 * }
054 * });}</pre>
055 *
056 * These features are all optional; {@code new MapMaker().makeMap()}
057 * returns a valid concurrent map that behaves exactly like a
058 * {@link ConcurrentHashMap}.
059 *
060 * The returned map is implemented as a hash table with similar performance
061 * characteristics to {@link ConcurrentHashMap}. It supports all optional
062 * operations of the {@code ConcurrentMap} interface. It does not permit
063 * null keys or values. It is serializable; however, serializing a map that
064 * uses soft or weak references can give unpredictable results.
065 *
066 * <p><b>Note:</b> by default, the returned map uses equality comparisons
067 * (the {@link Object#equals(Object) equals} method) to determine equality
068 * for keys or values. However, if {@link #weakKeys()} or {@link
069 * #softKeys()} was specified, the map uses identity ({@code ==})
070 * comparisons instead for keys. Likewise, if {@link #weakValues()} or
071 * {@link #softValues()} was specified, the map uses identity comparisons
072 * for values.
073 *
074 * <p>The returned map has <i>weakly consistent iteration</i>: an iterator
075 * over one of the map's view collections may reflect some, all or none of
076 * the changes made to the map after the iterator was created.
077 *
078 * <p>An entry whose key or value is reclaimed by the garbage collector
079 * immediately disappears from the map. (If the default settings of strong
080 * keys and strong values are used, this will never happen.) The client can
081 * never observe a partially-reclaimed entry. Any {@link java.util.Map.Entry}
082 * instance retrieved from the map's {@linkplain Map#entrySet() entry set}
083 * is a snapshot of that entry's state at the time of retrieval; such entries
084 * do, however, support {@link java.util.Map.Entry#setValue}.
085 *
086 * <p>{@code new MapMaker().weakKeys().makeMap()} can almost always be
087 * used as a drop-in replacement for {@link java.util.WeakHashMap}, adding
088 * concurrency, asynchronous cleanup, identity-based equality for keys, and
089 * great flexibility.
090 *
091 * @author Bob Lee
092 * @author Kevin Bourrillion
093 * @since 2 (imported from Google Collections Library)
094 */
095 @GwtCompatible(emulated = true)
096 public final class MapMaker {
097 private static final int DEFAULT_INITIAL_CAPACITY = 16;
098 private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
099 private static final int DEFAULT_EXPIRATION_NANOS = 0;
100
101 private static final int UNSET_INITIAL_CAPACITY = -1;
102 private static final int UNSET_CONCURRENCY_LEVEL = -1;
103 static final int UNSET_EXPIRATION_NANOS = -1;
104 static final int UNSET_MAXIMUM_SIZE = -1;
105
106 int initialCapacity = UNSET_INITIAL_CAPACITY;
107 int concurrencyLevel = UNSET_CONCURRENCY_LEVEL;
108 int maximumSize = UNSET_MAXIMUM_SIZE;
109
110 Strength keyStrength;
111 Strength valueStrength;
112
113 long expirationNanos = UNSET_EXPIRATION_NANOS;
114
115 private boolean useCustomMap;
116
117 Equivalence<Object> keyEquivalence;
118 Equivalence<Object> valueEquivalence;
119
120 /**
121 * Constructs a new {@code MapMaker} instance with default settings,
122 * including strong keys, strong values, and no automatic expiration.
123 */
124 public MapMaker() {}
125
126 // TODO: undo this indirection if keyEquiv gets released
127 MapMaker privateKeyEquivalence(Equivalence<Object> equivalence) {
128 checkState(keyEquivalence == null,
129 "key equivalence was already set to " + keyEquivalence);
130 keyEquivalence = checkNotNull(equivalence);
131 this.useCustomMap = true;
132 return this;
133 }
134
135 Equivalence<Object> getKeyEquivalence() {
136 return Objects.firstNonNull(keyEquivalence,
137 getKeyStrength().defaultEquivalence());
138 }
139
140 // TODO: undo this indirection if valueEquiv gets released
141 MapMaker privateValueEquivalence(Equivalence<Object> equivalence) {
142 checkState(valueEquivalence == null,
143 "value equivalence was already set to " + valueEquivalence);
144 this.valueEquivalence = checkNotNull(equivalence);
145 this.useCustomMap = true;
146 return this;
147 }
148
149 Equivalence<Object> getValueEquivalence() {
150 return Objects.firstNonNull(valueEquivalence,
151 getValueStrength().defaultEquivalence());
152 }
153
154 /**
155 * Sets a custom initial capacity (defaults to 16). Resizing this or
156 * any other kind of hash table is a relatively slow operation, so,
157 * when possible, it is a good idea to provide estimates of expected
158 * table sizes.
159 *
160 * @throws IllegalArgumentException if {@code initialCapacity} is
161 * negative
162 * @throws IllegalStateException if an initial capacity was already set
163 */
164 public MapMaker initialCapacity(int initialCapacity) {
165 checkState(this.initialCapacity == UNSET_INITIAL_CAPACITY,
166 "initial capacity was already set to " + this.initialCapacity);
167 checkArgument(initialCapacity >= 0);
168 this.initialCapacity = initialCapacity;
169 return this;
170 }
171
172 int getInitialCapacity() {
173 return (initialCapacity == UNSET_INITIAL_CAPACITY)
174 ? DEFAULT_INITIAL_CAPACITY : initialCapacity;
175 }
176
177 /**
178 * Specifies the maximum number of entries the map may contain. While the
179 * number of entries in the map is not guaranteed to grow to the maximum,
180 * the map will attempt to make the best use of memory without exceeding the
181 * maximum number of entries. As the map size grows close to the maximum,
182 * the map will evict entries that are less likely to be used again. For
183 * example, the map may evict an entry because it hasn't been used recently
184 * or very often.
185 *
186 * @throws IllegalArgumentException if {@code size} is negative
187 * @throws IllegalStateException if a maximum size was already set
188 */
189 // TODO: Implement and make public.
190 MapMaker maximumSize(int size) {
191 // TODO: Should we disallow maximumSize < concurrencyLevel? If we allow it,
192 // should we return a dummy map that doesn't actually retain any
193 // entries?
194
195 checkState(this.maximumSize == UNSET_MAXIMUM_SIZE,
196 "maximum size was already set to " + this.maximumSize);
197 checkArgument(initialCapacity >= 0);
198 this.maximumSize = size;
199 this.useCustomMap = true;
200 return this;
201 }
202
203 /**
204 * Guides the allowed concurrency among update operations. Used as a
205 * hint for internal sizing. The table is internally partitioned to try
206 * to permit the indicated number of concurrent updates without
207 * contention. Because placement in hash tables is essentially random,
208 * the actual concurrency will vary. Ideally, you should choose a value
209 * to accommodate as many threads as will ever concurrently modify the
210 * table. Using a significantly higher value than you need can waste
211 * space and time, and a significantly lower value can lead to thread
212 * contention. But overestimates and underestimates within an order of
213 * magnitude do not usually have much noticeable impact. A value of one
214 * is appropriate when it is known that only one thread will modify and
215 * all others will only read. Defaults to 16.
216 *
217 * @throws IllegalArgumentException if {@code concurrencyLevel} is
218 * nonpositive
219 * @throws IllegalStateException if a concurrency level was already set
220 */
221 @GwtIncompatible("java.util.concurrent.ConcurrentHashMap concurrencyLevel")
222 public MapMaker concurrencyLevel(int concurrencyLevel) {
223 checkState(this.concurrencyLevel == UNSET_CONCURRENCY_LEVEL,
224 "concurrency level was already set to " + this.concurrencyLevel);
225 checkArgument(concurrencyLevel > 0);
226 this.concurrencyLevel = concurrencyLevel;
227 return this;
228 }
229
230 int getConcurrencyLevel() {
231 return (concurrencyLevel == UNSET_CONCURRENCY_LEVEL)
232 ? DEFAULT_CONCURRENCY_LEVEL : concurrencyLevel;
233 }
234
235 /**
236 * Specifies that each key (not value) stored in the map should be
237 * wrapped in a {@link WeakReference} (by default, strong references
238 * are used).
239 *
240 * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
241 * to determine equality of weak keys, which may not behave as you expect.
242 * For example, storing a key in the map and then attempting a lookup
243 * using a different but {@link Object#equals(Object) equals}-equivalent
244 * key will always fail.
245 *
246 * @throws IllegalStateException if the key strength was already set
247 * @see WeakReference
248 */
249 @GwtIncompatible("java.lang.ref.WeakReference")
250 public MapMaker weakKeys() {
251 return setKeyStrength(Strength.WEAK);
252 }
253
254 /**
255 * Specifies that each key (not value) stored in the map should be
256 * wrapped in a {@link SoftReference} (by default, strong references
257 * are used).
258 *
259 * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
260 * to determine equality of soft keys, which may not behave as you expect.
261 * For example, storing a key in the map and then attempting a lookup
262 * using a different but {@link Object#equals(Object) equals}-equivalent
263 * key will always fail.
264 *
265 * @throws IllegalStateException if the key strength was already set
266 * @see SoftReference
267 */
268 @GwtIncompatible("java.lang.ref.SoftReference")
269 public MapMaker softKeys() {
270 return setKeyStrength(Strength.SOFT);
271 }
272
273 MapMaker setKeyStrength(Strength strength) {
274 checkState(keyStrength == null,
275 "Key strength was already set to " + keyStrength + ".");
276 keyStrength = checkNotNull(strength);
277 if (strength != Strength.STRONG) {
278 // STRONG could be used during deserialization.
279 useCustomMap = true;
280 }
281 return this;
282 }
283
284 Strength getKeyStrength() {
285 return Objects.firstNonNull(keyStrength, Strength.STRONG);
286 }
287
288 /**
289 * Specifies that each value (not key) stored in the map should be
290 * wrapped in a {@link WeakReference} (by default, strong references
291 * are used).
292 *
293 * <p>Weak values will be garbage collected once they are weakly
294 * reachable. This makes them a poor candidate for caching; consider
295 * {@link #softValues()} instead.
296 *
297 * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
298 * to determine equality of weak values. This will notably impact
299 * the behavior of {@link Map#containsValue(Object) containsValue},
300 * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)},
301 * and {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}.
302 *
303 * @throws IllegalStateException if the key strength was already set
304 * @see WeakReference
305 */
306 @GwtIncompatible("java.lang.ref.WeakReference")
307 public MapMaker weakValues() {
308 return setValueStrength(Strength.WEAK);
309 }
310
311 /**
312 * Specifies that each value (not key) stored in the map should be
313 * wrapped in a {@link SoftReference} (by default, strong references
314 * are used).
315 *
316 * <p>Soft values will be garbage collected in response to memory
317 * demand, and in a least-recently-used manner. This makes them a
318 * good candidate for caching.
319 *
320 * <p><b>Note:</b> the map will use identity ({@code ==}) comparison
321 * to determine equality of soft values. This will notably impact
322 * the behavior of {@link Map#containsValue(Object) containsValue},
323 * {@link ConcurrentMap#remove(Object, Object) remove(Object, Object)},
324 * and {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V, V)}.
325 *
326 * @throws IllegalStateException if the value strength was already set
327 * @see SoftReference
328 */
329 @GwtIncompatible("java.lang.ref.SoftReference")
330 public MapMaker softValues() {
331 return setValueStrength(Strength.SOFT);
332 }
333
334 MapMaker setValueStrength(Strength strength) {
335 checkState(valueStrength == null,
336 "Value strength was already set to " + valueStrength + ".");
337 valueStrength = checkNotNull(strength);
338 if (strength != Strength.STRONG) {
339 // STRONG could be used during deserialization.
340 useCustomMap = true;
341 }
342 return this;
343 }
344
345 Strength getValueStrength() {
346 return Objects.firstNonNull(valueStrength, Strength.STRONG);
347 }
348
349 /**
350 * Specifies that each entry should be automatically removed from the
351 * map once a fixed duration has passed since the entry's creation.
352 * Note that changing the value of an entry will reset its expiration
353 * time.
354 *
355 * @param duration the length of time after an entry is created that it
356 * should be automatically removed
357 * @param unit the unit that {@code duration} is expressed in
358 * @throws IllegalArgumentException if {@code duration} is not positive
359 * @throws IllegalStateException if the expiration time was already set
360 */
361 public MapMaker expiration(long duration, TimeUnit unit) {
362 checkState(expirationNanos == UNSET_EXPIRATION_NANOS,
363 "expiration time of " + expirationNanos + " ns was already set");
364 checkArgument(duration > 0,
365 "invalid duration: " + duration);
366 this.expirationNanos = unit.toNanos(duration);
367 useCustomMap = true;
368 return this;
369 }
370
371 long getExpirationNanos() {
372 return (expirationNanos == UNSET_EXPIRATION_NANOS)
373 ? DEFAULT_EXPIRATION_NANOS : expirationNanos;
374 }
375
376 /**
377 * Builds a map, without on-demand computation of values. This method
378 * does not alter the state of this {@code MapMaker} instance, so it can be
379 * invoked again to create multiple independent maps.
380 *
381 * @param <K> the type of keys to be stored in the returned map
382 * @param <V> the type of values to be stored in the returned map
383 * @return a serializable concurrent map having the requested features
384 */
385 public <K, V> ConcurrentMap<K, V> makeMap() {
386 return useCustomMap
387 ? new CustomConcurrentHashMap<K, V>(this)
388 : new ConcurrentHashMap<K, V>(getInitialCapacity(),
389 0.75f, getConcurrencyLevel());
390 }
391
392 /**
393 * Builds a caching function, which either returns an already-computed value
394 * for a given key or atomically computes it using the supplied function.
395 * If another thread is currently computing the value for this key, simply
396 * waits for that thread to finish and returns its computed value. Note that
397 * the function may be executed concurrently by multiple threads, but only for
398 * distinct keys.
399 *
400 * <p>The {@code Map} view of the {@code Cache}'s cache is only
401 * updated when function computation completes. In other words, an entry isn't
402 * visible until the value's computation completes. No methods on the {@code
403 * Map} will ever trigger computation.
404 *
405 * <p>{@link Cache#apply} in the returned function implementation may
406 * throw:
407 *
408 * <ul>
409 * <li>{@link NullPointerException} if the key is null or the
410 * computing function returns null
411 * <li>{@link ComputationException} if an exception was thrown by the
412 * computing function. If that exception is already of type {@link
413 * ComputationException} it is propagated directly; otherwise it is
414 * wrapped.
415 * </ul>
416 *
417 * <p>If {@link Map#put} is called on the underlying map before a computation
418 * completes, other threads waiting on the computation will wake up and return
419 * the stored value. When the computation completes, its new result will
420 * overwrite the value that was put in the map manually.
421 *
422 * <p>This method does not alter the state of this {@code MapMaker} instance,
423 * so it can be invoked again to create multiple independent maps.
424 *
425 * @param <K> the type of keys to be stored in the returned cache
426 * @param <V> the type of values to be stored in the returned cache
427 * @return a serializable cache having the requested features
428 */
429 // TODO: figure out the Cache interface first
430 <K, V> Cache<K, V> makeCache(
431 Function<? super K, ? extends V> computingFunction) {
432 return new ComputingConcurrentHashMap<K, V>(this, computingFunction);
433 }
434
435 /**
436 * Builds a map that supports atomic, on-demand computation of values. {@link
437 * Map#get} either returns an already-computed value for the given key,
438 * atomically computes it using the supplied function, or, if another thread
439 * is currently computing the value for this key, simply waits for that thread
440 * to finish and returns its computed value. Note that the function may be
441 * executed concurrently by multiple threads, but only for distinct keys.
442 *
443 * <p>If an entry's value has not finished computing yet, query methods
444 * besides {@code get} return immediately as if an entry doesn't exist. In
445 * other words, an entry isn't externally visible until the value's
446 * computation completes.
447 *
448 * <p>{@link Map#get} on the returned map will never return {@code null}. It
449 * may throw:
450 *
451 * <ul>
452 * <li>{@link NullPointerException} if the key is null or the computing
453 * function returns null
454 * <li>{@link ComputationException} if an exception was thrown by the
455 * computing function. If that exception is already of type {@link
456 * ComputationException} it is propagated directly; otherwise it is
457 * wrapped.
458 * </ul>
459 *
460 * <p><b>Note:</b> Callers of {@code get} <i>must</i> ensure that the key
461 * argument is of type {@code K}. The {@code get} method accepts {@code
462 * Object}, so the key type is not checked at compile time. Passing an object
463 * of a type other than {@code K} can result in that object being unsafely
464 * passed to the computing function as type {@code K}, and unsafely stored in
465 * the map.
466 *
467 * <p>If {@link Map#put} is called before a computation completes, other
468 * threads waiting on the computation will wake up and return the stored
469 * value. When the computation completes, its new result will overwrite the
470 * value that was put in the map manually.
471 *
472 * <p>This method does not alter the state of this {@code MapMaker} instance,
473 * so it can be invoked again to create multiple independent maps.
474 */
475 public <K, V> ConcurrentMap<K, V> makeComputingMap(
476 Function<? super K, ? extends V> computingFunction) {
477 Cache<K, V> cache = makeCache(computingFunction);
478 return new ComputingMapAdapter<K, V>(cache);
479 }
480
481 /**
482 * A function which caches the result of each application (computation). This
483 * interface does not specify the caching semantics, but does expose a {@code
484 * ConcurrentMap} view of cached entries.
485 *
486 * @author Bob Lee
487 */
488 interface Cache<K, V> extends Function<K, V> {
489
490 /**
491 * Returns a map view of the cached entries.
492 */
493 ConcurrentMap<K, V> asMap();
494 }
495
496 /**
497 * Overrides get() to compute on demand.
498 */
499 static class ComputingMapAdapter<K, V> extends ForwardingConcurrentMap<K, V>
500 implements Serializable {
501 private static final long serialVersionUID = 0;
502
503 final Cache<K, V> cache;
504
505 ComputingMapAdapter(Cache<K, V> cache) {
506 this.cache = cache;
507 }
508
509 @Override protected ConcurrentMap<K, V> delegate() {
510 return cache.asMap();
511 }
512
513 @SuppressWarnings("unchecked") // unsafe, which is why this is deprecated
514 @Override public V get(Object key) {
515 return cache.apply((K) key);
516 }
517 }
518 }