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