1 /*
2 * Copyright (C) 2009 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15 package com.google.common.collect;
16
17 import static com.google.common.base.Preconditions.checkArgument;
18 import static com.google.common.base.Preconditions.checkNotNull;
19 import static com.google.common.base.Preconditions.checkState;
20
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.common.annotations.GwtIncompatible;
23 import com.google.common.base.Ascii;
24 import com.google.common.base.Equivalence;
25 import com.google.common.base.MoreObjects;
26 import com.google.common.collect.MapMakerInternalMap.Strength;
27 import com.google.errorprone.annotations.CanIgnoreReturnValue;
28 import java.lang.ref.WeakReference;
29 import java.util.ConcurrentModificationException;
30 import java.util.Map;
31 import java.util.concurrent.ConcurrentHashMap;
32 import java.util.concurrent.ConcurrentMap;
33 import org.checkerframework.checker.nullness.qual.Nullable;
34
35 /**
36 * A builder of {@link ConcurrentMap} instances that can have keys or values automatically wrapped
37 * in {@linkplain WeakReference weak} references.
38 *
39 * <p>Usage example:
40 *
41 * <pre>{@code
42 * ConcurrentMap<Request, Stopwatch> timers = new MapMaker()
43 * .concurrencyLevel(4)
44 * .weakKeys()
45 * .makeMap();
46 * }</pre>
47 *
48 * <p>These features are all optional; {@code new MapMaker().makeMap()} returns a valid concurrent
49 * map that behaves similarly to a {@link ConcurrentHashMap}.
50 *
51 * <p>The returned map is implemented as a hash table with similar performance characteristics to
52 * {@link ConcurrentHashMap}. It supports all optional operations of the {@code ConcurrentMap}
53 * interface. It does not permit null keys or values.
54 *
55 * <p><b>Note:</b> by default, the returned map uses equality comparisons (the {@link Object#equals
56 * equals} method) to determine equality for keys or values. However, if {@link #weakKeys} was
57 * specified, the map uses identity ({@code ==}) comparisons instead for keys. Likewise, if {@link
58 * #weakValues} was specified, the map uses identity comparisons for values.
59 *
60 * <p>The view collections of the returned map have <i>weakly consistent iterators</i>. This means
61 * that they are safe for concurrent use, but if other threads modify the map after the iterator is
62 * created, it is undefined which of these changes, if any, are reflected in that iterator. These
63 * iterators never throw {@link ConcurrentModificationException}.
64 *
65 * <p>If {@link #weakKeys} or {@link #weakValues} are requested, it is possible for a key or value
66 * present in the map to be reclaimed by the garbage collector. Entries with reclaimed keys or
67 * values may be removed from the map on each map modification or on occasional map accesses; such
68 * entries may be counted by {@link Map#size}, but will never be visible to read or write
69 * operations. A partially-reclaimed entry is never exposed to the user. Any {@link Map.Entry}
70 * instance retrieved from the map's {@linkplain Map#entrySet entry set} is a snapshot of that
71 * entry's state at the time of retrieval; such entries do, however, support {@link
72 * Map.Entry#setValue}, which simply calls {@link Map#put} on the entry's key.
73 *
74 * <p>The maps produced by {@code MapMaker} are serializable, and the deserialized maps retain all
75 * the configuration properties of the original map. During deserialization, if the original map had
76 * used weak references, the entries are reconstructed as they were, but it's not unlikely they'll
77 * be quickly garbage-collected before they are ever accessed.
78 *
79 * <p>{@code new MapMaker().weakKeys().makeMap()} is a recommended replacement for {@link
80 * java.util.WeakHashMap}, but note that it compares keys using object identity whereas {@code
81 * WeakHashMap} uses {@link Object#equals}.
82 *
83 * @author Bob Lee
84 * @author Charles Fry
85 * @author Kevin Bourrillion
86 * @since 2.0
87 */
88 @GwtCompatible(emulated = true)
89 public final class MapMaker {
90 private static final int DEFAULT_INITIAL_CAPACITY = 16;
91 private static final int DEFAULT_CONCURRENCY_LEVEL = 4;
92
93 static final int UNSET_INT = -1;
94
95 // TODO(kevinb): dispense with this after benchmarking
96 boolean useCustomMap;
97
98 int initialCapacity = UNSET_INT;
99 int concurrencyLevel = UNSET_INT;
100
101 @Nullable Strength keyStrength;
102 @Nullable Strength valueStrength;
103
104 @Nullable Equivalence<Object> keyEquivalence;
105
106 /**
107 * Constructs a new {@code MapMaker} instance with default settings, including strong keys, strong
108 * values, and no automatic eviction of any kind.
109 */
110 public MapMaker() {}
111
112 /**
113 * Sets a custom {@code Equivalence} strategy for comparing keys.
114 *
115 * <p>By default, the map uses {@link Equivalence#identity} to determine key equality when {@link
116 * #weakKeys} is specified, and {@link Equivalence#equals()} otherwise. The only place this is
117 * used is in {@link Interners.WeakInterner}.
118 */
119 @CanIgnoreReturnValue
120 @GwtIncompatible // To be supported
121 MapMaker keyEquivalence(Equivalence<Object> equivalence) {
122 checkState(keyEquivalence == null, "key equivalence was already set to %s", keyEquivalence);
123 keyEquivalence = checkNotNull(equivalence);
124 this.useCustomMap = true;
125 return this;
126 }
127
128 Equivalence<Object> getKeyEquivalence() {
129 return MoreObjects.firstNonNull(keyEquivalence, getKeyStrength().defaultEquivalence());
130 }
131
132 /**
133 * Sets the minimum total size for the internal hash tables. For example, if the initial capacity
134 * is {@code 60}, and the concurrency level is {@code 8}, then eight segments are created, each
135 * having a hash table of size eight. Providing a large enough estimate at construction time
136 * avoids the need for expensive resizing operations later, but setting this value unnecessarily
137 * high wastes memory.
138 *
139 * @throws IllegalArgumentException if {@code initialCapacity} is negative
140 * @throws IllegalStateException if an initial capacity was already set
141 */
142 @CanIgnoreReturnValue
143 public MapMaker initialCapacity(int initialCapacity) {
144 checkState(
145 this.initialCapacity == UNSET_INT,
146 "initial capacity was already set to %s",
147 this.initialCapacity);
148 checkArgument(initialCapacity >= 0);
149 this.initialCapacity = initialCapacity;
150 return this;
151 }
152
153 int getInitialCapacity() {
154 return (initialCapacity == UNSET_INT) ? DEFAULT_INITIAL_CAPACITY : initialCapacity;
155 }
156
157 /**
158 * Guides the allowed concurrency among update operations. Used as a hint for internal sizing. The
159 * table is internally partitioned to try to permit the indicated number of concurrent updates
160 * without contention. Because assignment of entries to these partitions is not necessarily
161 * uniform, the actual concurrency observed may vary. Ideally, you should choose a value to
162 * accommodate as many threads as will ever concurrently modify the table. Using a significantly
163 * higher value than you need can waste space and time, and a significantly lower value can lead
164 * to thread contention. But overestimates and underestimates within an order of magnitude do not
165 * usually have much noticeable impact. A value of one permits only one thread to modify the map
166 * at a time, but since read operations can proceed concurrently, this still yields higher
167 * concurrency than full synchronization. Defaults to 4.
168 *
169 * <p><b>Note:</b> Prior to Guava release 9.0, the default was 16. It is possible the default will
170 * change again in the future. If you care about this value, you should always choose it
171 * explicitly.
172 *
173 * @throws IllegalArgumentException if {@code concurrencyLevel} is nonpositive
174 * @throws IllegalStateException if a concurrency level was already set
175 */
176 @CanIgnoreReturnValue
177 public MapMaker concurrencyLevel(int concurrencyLevel) {
178 checkState(
179 this.concurrencyLevel == UNSET_INT,
180 "concurrency level was already set to %s",
181 this.concurrencyLevel);
182 checkArgument(concurrencyLevel > 0);
183 this.concurrencyLevel = concurrencyLevel;
184 return this;
185 }
186
187 int getConcurrencyLevel() {
188 return (concurrencyLevel == UNSET_INT) ? DEFAULT_CONCURRENCY_LEVEL : concurrencyLevel;
189 }
190
191 /**
192 * Specifies that each key (not value) stored in the map should be wrapped in a {@link
193 * WeakReference} (by default, strong references are used).
194 *
195 * <p><b>Warning:</b> when this method is used, the resulting map will use identity ({@code ==})
196 * comparison to determine equality of keys, which is a technical violation of the {@link Map}
197 * specification, and may not be what you expect.
198 *
199 * @throws IllegalStateException if the key strength was already set
200 * @see WeakReference
201 */
202 @CanIgnoreReturnValue
203 @GwtIncompatible // java.lang.ref.WeakReference
204 public MapMaker weakKeys() {
205 return setKeyStrength(Strength.WEAK);
206 }
207
208 MapMaker setKeyStrength(Strength strength) {
209 checkState(keyStrength == null, "Key strength was already set to %s", keyStrength);
210 keyStrength = checkNotNull(strength);
211 if (strength != Strength.STRONG) {
212 // STRONG could be used during deserialization.
213 useCustomMap = true;
214 }
215 return this;
216 }
217
218 Strength getKeyStrength() {
219 return MoreObjects.firstNonNull(keyStrength, Strength.STRONG);
220 }
221
222 /**
223 * Specifies that each value (not key) stored in the map should be wrapped in a {@link
224 * WeakReference} (by default, strong references are used).
225 *
226 * <p>Weak values will be garbage collected once they are weakly reachable. This makes them a poor
227 * candidate for caching.
228 *
229 * <p><b>Warning:</b> when this method is used, the resulting map will use identity ({@code ==})
230 * comparison to determine equality of values. This technically violates the specifications of the
231 * methods {@link Map#containsValue containsValue}, {@link ConcurrentMap#remove(Object, Object)
232 * remove(Object, Object)} and {@link ConcurrentMap#replace(Object, Object, Object) replace(K, V,
233 * V)}, and may not be what you expect.
234 *
235 * @throws IllegalStateException if the value strength was already set
236 * @see WeakReference
237 */
238 @CanIgnoreReturnValue
239 @GwtIncompatible // java.lang.ref.WeakReference
240 public MapMaker weakValues() {
241 return setValueStrength(Strength.WEAK);
242 }
243
244 /**
245 * A dummy singleton value type used by {@link Interners}.
246 *
247 * <p>{@link MapMakerInternalMap} can optimize for memory usage in this case; see {@link
248 * MapMakerInternalMap#createWithDummyValues}.
249 */
250 enum Dummy {
251 VALUE
252 }
253
254 MapMaker setValueStrength(Strength strength) {
255 checkState(valueStrength == null, "Value strength was already set to %s", valueStrength);
256 valueStrength = checkNotNull(strength);
257 if (strength != Strength.STRONG) {
258 // STRONG could be used during deserialization.
259 useCustomMap = true;
260 }
261 return this;
262 }
263
264 Strength getValueStrength() {
265 return MoreObjects.firstNonNull(valueStrength, Strength.STRONG);
266 }
267
268 /**
269 * Builds a thread-safe map. This method does not alter the state of this {@code MapMaker}
270 * instance, so it can be invoked again to create multiple independent maps.
271 *
272 * <p>The bulk operations {@code putAll}, {@code equals}, and {@code clear} are not guaranteed to
273 * be performed atomically on the returned map. Additionally, {@code size} and {@code
274 * containsValue} are implemented as bulk read operations, and thus may fail to observe concurrent
275 * writes.
276 *
277 * @return a serializable concurrent map having the requested features
278 */
279 public <K, V> ConcurrentMap<K, V> makeMap() {
280 if (!useCustomMap) {
281 return new ConcurrentHashMap<>(getInitialCapacity(), 0.75f, getConcurrencyLevel());
282 }
283 return MapMakerInternalMap.create(this);
284 }
285
286 /**
287 * Returns a string representation for this MapMaker instance. The exact form of the returned
288 * string is not specified.
289 */
290 @Override
291 public String toString() {
292 MoreObjects.ToStringHelper s = MoreObjects.toStringHelper(this);
293 if (initialCapacity != UNSET_INT) {
294 s.add("initialCapacity", initialCapacity);
295 }
296 if (concurrencyLevel != UNSET_INT) {
297 s.add("concurrencyLevel", concurrencyLevel);
298 }
299 if (keyStrength != null) {
300 s.add("keyStrength", Ascii.toLowerCase(keyStrength.toString()));
301 }
302 if (valueStrength != null) {
303 s.add("valueStrength", Ascii.toLowerCase(valueStrength.toString()));
304 }
305 if (keyEquivalence != null) {
306 s.addValue("keyEquivalence");
307 }
308 return s.toString();
309 }
310 }