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