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