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 MapMaker setValueStrength(Strength strength) { 243 checkState(valueStrength == null, "Value strength was already set to %s", valueStrength); 244 valueStrength = checkNotNull(strength); 245 if (strength != Strength.STRONG) { 246 // STRONG could be used during deserialization. 247 useCustomMap = true; 248 } 249 return this; 250 } 251 252 Strength getValueStrength() { 253 return MoreObjects.firstNonNull(valueStrength, Strength.STRONG); 254 } 255 256 /** 257 * Builds a thread-safe map. This method does not alter the state of this {@code MapMaker} 258 * instance, so it can be invoked again to create multiple independent maps. 259 * 260 * <p>The bulk operations {@code putAll}, {@code equals}, and {@code clear} are not guaranteed to 261 * be performed atomically on the returned map. Additionally, {@code size} and 262 * {@code containsValue} are implemented as bulk read operations, and thus may fail to observe 263 * concurrent writes. 264 * 265 * @return a serializable concurrent map having the requested features 266 */ 267 public <K, V> ConcurrentMap<K, V> makeMap() { 268 if (!useCustomMap) { 269 return new ConcurrentHashMap<K, V>(getInitialCapacity(), 0.75f, getConcurrencyLevel()); 270 } 271 return MapMakerInternalMap.create(this); 272 } 273 274 /** 275 * Returns a MapMakerInternalMap for the benefit of internal callers that use features of that 276 * class not exposed through ConcurrentMap. 277 */ 278 @GwtIncompatible // MapMakerInternalMap 279 <K, V> MapMakerInternalMap<K, V, ?, ?> makeCustomMap() { 280 return MapMakerInternalMap.create(this); 281 } 282 283 /** 284 * Returns a string representation for this MapMaker instance. The exact form of the returned 285 * string is not specified. 286 */ 287 @Override 288 public String toString() { 289 MoreObjects.ToStringHelper s = MoreObjects.toStringHelper(this); 290 if (initialCapacity != UNSET_INT) { 291 s.add("initialCapacity", initialCapacity); 292 } 293 if (concurrencyLevel != UNSET_INT) { 294 s.add("concurrencyLevel", concurrencyLevel); 295 } 296 if (keyStrength != null) { 297 s.add("keyStrength", Ascii.toLowerCase(keyStrength.toString())); 298 } 299 if (valueStrength != null) { 300 s.add("valueStrength", Ascii.toLowerCase(valueStrength.toString())); 301 } 302 if (keyEquivalence != null) { 303 s.addValue("keyEquivalence"); 304 } 305 return s.toString(); 306 } 307}