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.MonotonicNonNull; 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 java.util.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 * java.util.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 @MonotonicNonNull Strength keyStrength; 102 @MonotonicNonNull Strength valueStrength; 103 104 @MonotonicNonNull 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}