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
015package com.google.common.collect;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019import static com.google.common.base.Preconditions.checkState;
020
021import com.google.common.annotations.GwtCompatible;
022import com.google.common.annotations.GwtIncompatible;
023import com.google.common.base.Ascii;
024import com.google.common.base.Equivalence;
025import com.google.common.base.MoreObjects;
026import com.google.common.collect.MapMakerInternalMap.Strength;
027import com.google.errorprone.annotations.CanIgnoreReturnValue;
028import java.lang.ref.WeakReference;
029import java.util.ConcurrentModificationException;
030import java.util.Map;
031import java.util.concurrent.ConcurrentHashMap;
032import java.util.concurrent.ConcurrentMap;
033import org.checkerframework.checker.nullness.qual.Nullable;
034
035/**
036 * A builder of {@link ConcurrentMap} instances that can have keys or values automatically wrapped
037 * in {@linkplain WeakReference weak} references.
038 *
039 * <p>Usage example:
040 *
041 * <pre>{@code
042 * ConcurrentMap<Request, Stopwatch> timers = new MapMaker()
043 *     .concurrencyLevel(4)
044 *     .weakKeys()
045 *     .makeMap();
046 * }</pre>
047 *
048 * <p>These features are all optional; {@code new MapMaker().makeMap()} returns a valid concurrent
049 * map that behaves similarly to a {@link ConcurrentHashMap}.
050 *
051 * <p>The returned map is implemented as a hash table with similar performance characteristics to
052 * {@link ConcurrentHashMap}. It supports all optional operations of the {@code ConcurrentMap}
053 * interface. It does not permit null keys or values.
054 *
055 * <p><b>Note:</b> by default, the returned map uses equality comparisons (the {@link Object#equals
056 * equals} method) to determine equality for keys or values. However, if {@link #weakKeys} was
057 * specified, the map uses identity ({@code ==}) comparisons instead for keys. Likewise, if {@link
058 * #weakValues} was specified, the map uses identity comparisons for values.
059 *
060 * <p>The view collections of the returned map have <i>weakly consistent iterators</i>. This means
061 * that they are safe for concurrent use, but if other threads modify the map after the iterator is
062 * created, it is undefined which of these changes, if any, are reflected in that iterator. These
063 * iterators never throw {@link ConcurrentModificationException}.
064 *
065 * <p>If {@link #weakKeys} or {@link #weakValues} are requested, it is possible for a key or value
066 * present in the map to be reclaimed by the garbage collector. Entries with reclaimed keys or
067 * values may be removed from the map on each map modification or on occasional map accesses; such
068 * entries may be counted by {@link Map#size}, but will never be visible to read or write
069 * operations. A partially-reclaimed entry is never exposed to the user. Any {@link Map.Entry}
070 * instance retrieved from the map's {@linkplain Map#entrySet entry set} is a snapshot of that
071 * entry's state at the time of retrieval; such entries do, however, support {@link
072 * Map.Entry#setValue}, which simply calls {@link Map#put} on the entry's key.
073 *
074 * <p>The maps produced by {@code MapMaker} are serializable, and the deserialized maps retain all
075 * the configuration properties of the original map. During deserialization, if the original map had
076 * used weak references, the entries are reconstructed as they were, but it's not unlikely they'll
077 * be quickly garbage-collected before they are ever accessed.
078 *
079 * <p>{@code new MapMaker().weakKeys().makeMap()} is a recommended replacement for {@link
080 * java.util.WeakHashMap}, but note that it compares keys using object identity whereas {@code
081 * WeakHashMap} uses {@link Object#equals}.
082 *
083 * @author Bob Lee
084 * @author Charles Fry
085 * @author Kevin Bourrillion
086 * @since 2.0
087 */
088@GwtCompatible(emulated = true)
089public final class MapMaker {
090  private static final int DEFAULT_INITIAL_CAPACITY = 16;
091  private static final int DEFAULT_CONCURRENCY_LEVEL = 4;
092
093  static final int UNSET_INT = -1;
094
095  // TODO(kevinb): dispense with this after benchmarking
096  boolean useCustomMap;
097
098  int initialCapacity = UNSET_INT;
099  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}