001/* 002 * Copyright (C) 2011 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.util.concurrent; 016 017import static com.google.common.base.Preconditions.checkNotNull; 018 019import com.google.common.annotations.GwtCompatible; 020import com.google.common.annotations.J2ktIncompatible; 021import com.google.common.base.Function; 022import com.google.common.collect.Maps; 023import com.google.errorprone.annotations.CanIgnoreReturnValue; 024import com.google.errorprone.annotations.concurrent.LazyInit; 025import java.io.Serializable; 026import java.util.Collections; 027import java.util.Iterator; 028import java.util.Map; 029import java.util.Map.Entry; 030import java.util.concurrent.ConcurrentHashMap; 031import java.util.concurrent.atomic.AtomicLong; 032import javax.annotation.CheckForNull; 033 034/** 035 * A map containing {@code long} values that can be atomically updated. While writes to a 036 * traditional {@code Map} rely on {@code put(K, V)}, the typical mechanism for writing to this map 037 * is {@code addAndGet(K, long)}, which adds a {@code long} to the value currently associated with 038 * {@code K}. If a key has not yet been associated with a value, its implicit value is zero. 039 * 040 * <p>Most methods in this class treat absent values and zero values identically, as individually 041 * documented. Exceptions to this are {@link #containsKey}, {@link #size}, {@link #isEmpty}, {@link 042 * #asMap}, and {@link #toString}. 043 * 044 * <p>Instances of this class may be used by multiple threads concurrently. All operations are 045 * atomic unless otherwise noted. 046 * 047 * <p>Instances of this class are serializable if the keys are serializable. 048 * 049 * <p><b>Note:</b> If your values are always positive and less than 2^31, you may wish to use a 050 * {@link com.google.common.collect.Multiset} such as {@link 051 * com.google.common.collect.ConcurrentHashMultiset} instead. 052 * 053 * <p><b>Warning:</b> Unlike {@code Multiset}, entries whose values are zero are not automatically 054 * removed from the map. Instead they must be removed manually with {@link #removeAllZeros}. 055 * 056 * @author Charles Fry 057 * @since 11.0 058 */ 059@GwtCompatible 060@J2ktIncompatible 061@ElementTypesAreNonnullByDefault 062public final class AtomicLongMap<K> implements Serializable { 063 private final ConcurrentHashMap<K, AtomicLong> map; 064 065 private AtomicLongMap(ConcurrentHashMap<K, AtomicLong> map) { 066 this.map = checkNotNull(map); 067 } 068 069 /** Creates an {@code AtomicLongMap}. */ 070 public static <K> AtomicLongMap<K> create() { 071 return new AtomicLongMap<K>(new ConcurrentHashMap<K, AtomicLong>()); 072 } 073 074 /** Creates an {@code AtomicLongMap} with the same mappings as the specified {@code Map}. */ 075 public static <K> AtomicLongMap<K> create(Map<? extends K, ? extends Long> m) { 076 AtomicLongMap<K> result = create(); 077 result.putAll(m); 078 return result; 079 } 080 081 /** 082 * Returns the value associated with {@code key}, or zero if there is no value associated with 083 * {@code key}. 084 */ 085 public long get(K key) { 086 AtomicLong atomic = map.get(key); 087 return atomic == null ? 0L : atomic.get(); 088 } 089 090 /** 091 * Increments by one the value currently associated with {@code key}, and returns the new value. 092 */ 093 @CanIgnoreReturnValue 094 public long incrementAndGet(K key) { 095 return addAndGet(key, 1); 096 } 097 098 /** 099 * Decrements by one the value currently associated with {@code key}, and returns the new value. 100 */ 101 @CanIgnoreReturnValue 102 public long decrementAndGet(K key) { 103 return addAndGet(key, -1); 104 } 105 106 /** 107 * Adds {@code delta} to the value currently associated with {@code key}, and returns the new 108 * value. 109 */ 110 @CanIgnoreReturnValue 111 public long addAndGet(K key, long delta) { 112 outer: 113 while (true) { 114 AtomicLong atomic = map.get(key); 115 if (atomic == null) { 116 atomic = map.putIfAbsent(key, new AtomicLong(delta)); 117 if (atomic == null) { 118 return delta; 119 } 120 // atomic is now non-null; fall through 121 } 122 123 while (true) { 124 long oldValue = atomic.get(); 125 if (oldValue == 0L) { 126 // don't compareAndSet a zero 127 if (map.replace(key, atomic, new AtomicLong(delta))) { 128 return delta; 129 } 130 // atomic replaced 131 continue outer; 132 } 133 134 long newValue = oldValue + delta; 135 if (atomic.compareAndSet(oldValue, newValue)) { 136 return newValue; 137 } 138 // value changed 139 } 140 } 141 } 142 143 /** 144 * Increments by one the value currently associated with {@code key}, and returns the old value. 145 */ 146 @CanIgnoreReturnValue 147 public long getAndIncrement(K key) { 148 return getAndAdd(key, 1); 149 } 150 151 /** 152 * Decrements by one the value currently associated with {@code key}, and returns the old value. 153 */ 154 @CanIgnoreReturnValue 155 public long getAndDecrement(K key) { 156 return getAndAdd(key, -1); 157 } 158 159 /** 160 * Adds {@code delta} to the value currently associated with {@code key}, and returns the old 161 * value. 162 */ 163 @CanIgnoreReturnValue 164 public long getAndAdd(K key, long delta) { 165 outer: 166 while (true) { 167 AtomicLong atomic = map.get(key); 168 if (atomic == null) { 169 atomic = map.putIfAbsent(key, new AtomicLong(delta)); 170 if (atomic == null) { 171 return 0L; 172 } 173 // atomic is now non-null; fall through 174 } 175 176 while (true) { 177 long oldValue = atomic.get(); 178 if (oldValue == 0L) { 179 // don't compareAndSet a zero 180 if (map.replace(key, atomic, new AtomicLong(delta))) { 181 return 0L; 182 } 183 // atomic replaced 184 continue outer; 185 } 186 187 long newValue = oldValue + delta; 188 if (atomic.compareAndSet(oldValue, newValue)) { 189 return oldValue; 190 } 191 // value changed 192 } 193 } 194 } 195 196 /** 197 * Associates {@code newValue} with {@code key} in this map, and returns the value previously 198 * associated with {@code key}, or zero if there was no such value. 199 */ 200 @CanIgnoreReturnValue 201 public long put(K key, long newValue) { 202 outer: 203 while (true) { 204 AtomicLong atomic = map.get(key); 205 if (atomic == null) { 206 atomic = map.putIfAbsent(key, new AtomicLong(newValue)); 207 if (atomic == null) { 208 return 0L; 209 } 210 // atomic is now non-null; fall through 211 } 212 213 while (true) { 214 long oldValue = atomic.get(); 215 if (oldValue == 0L) { 216 // don't compareAndSet a zero 217 if (map.replace(key, atomic, new AtomicLong(newValue))) { 218 return 0L; 219 } 220 // atomic replaced 221 continue outer; 222 } 223 224 if (atomic.compareAndSet(oldValue, newValue)) { 225 return oldValue; 226 } 227 // value changed 228 } 229 } 230 } 231 232 /** 233 * Copies all of the mappings from the specified map to this map. The effect of this call is 234 * equivalent to that of calling {@code put(k, v)} on this map once for each mapping from key 235 * {@code k} to value {@code v} in the specified map. The behavior of this operation is undefined 236 * if the specified map is modified while the operation is in progress. 237 */ 238 public void putAll(Map<? extends K, ? extends Long> m) { 239 for (Entry<? extends K, ? extends Long> entry : m.entrySet()) { 240 put(entry.getKey(), entry.getValue()); 241 } 242 } 243 244 /** 245 * Removes and returns the value associated with {@code key}. If {@code key} is not in the map, 246 * this method has no effect and returns zero. 247 */ 248 @CanIgnoreReturnValue 249 public long remove(K key) { 250 AtomicLong atomic = map.get(key); 251 if (atomic == null) { 252 return 0L; 253 } 254 255 while (true) { 256 long oldValue = atomic.get(); 257 if (oldValue == 0L || atomic.compareAndSet(oldValue, 0L)) { 258 // only remove after setting to zero, to avoid concurrent updates 259 map.remove(key, atomic); 260 // succeed even if the remove fails, since the value was already adjusted 261 return oldValue; 262 } 263 } 264 } 265 266 /** 267 * If {@code (key, value)} is currently in the map, this method removes it and returns true; 268 * otherwise, this method returns false. 269 */ 270 boolean remove(K key, long value) { 271 AtomicLong atomic = map.get(key); 272 if (atomic == null) { 273 return false; 274 } 275 276 long oldValue = atomic.get(); 277 if (oldValue != value) { 278 return false; 279 } 280 281 if (oldValue == 0L || atomic.compareAndSet(oldValue, 0L)) { 282 // only remove after setting to zero, to avoid concurrent updates 283 map.remove(key, atomic); 284 // succeed even if the remove fails, since the value was already adjusted 285 return true; 286 } 287 288 // value changed 289 return false; 290 } 291 292 /** 293 * Atomically remove {@code key} from the map iff its associated value is 0. 294 * 295 * @since 20.0 296 */ 297 @CanIgnoreReturnValue 298 public boolean removeIfZero(K key) { 299 return remove(key, 0); 300 } 301 302 /** 303 * Removes all mappings from this map whose values are zero. 304 * 305 * <p>This method is not atomic: the map may be visible in intermediate states, where some of the 306 * zero values have been removed and others have not. 307 */ 308 public void removeAllZeros() { 309 Iterator<Entry<K, AtomicLong>> entryIterator = map.entrySet().iterator(); 310 while (entryIterator.hasNext()) { 311 Entry<K, AtomicLong> entry = entryIterator.next(); 312 AtomicLong atomic = entry.getValue(); 313 if (atomic != null && atomic.get() == 0L) { 314 entryIterator.remove(); 315 } 316 } 317 } 318 319 /** 320 * Returns the sum of all values in this map. 321 * 322 * <p>This method is not atomic: the sum may or may not include other concurrent operations. 323 */ 324 public long sum() { 325 long sum = 0L; 326 for (AtomicLong value : map.values()) { 327 sum = sum + value.get(); 328 } 329 return sum; 330 } 331 332 @LazyInit @CheckForNull private transient Map<K, Long> asMap; 333 334 /** Returns a live, read-only view of the map backing this {@code AtomicLongMap}. */ 335 public Map<K, Long> asMap() { 336 Map<K, Long> result = asMap; 337 return (result == null) ? asMap = createAsMap() : result; 338 } 339 340 private Map<K, Long> createAsMap() { 341 return Collections.unmodifiableMap( 342 Maps.transformValues( 343 map, 344 new Function<AtomicLong, Long>() { 345 @Override 346 public Long apply(AtomicLong atomic) { 347 return atomic.get(); 348 } 349 })); 350 } 351 352 /** Returns true if this map contains a mapping for the specified key. */ 353 public boolean containsKey(Object key) { 354 return map.containsKey(key); 355 } 356 357 /** 358 * Returns the number of key-value mappings in this map. If the map contains more than {@code 359 * Integer.MAX_VALUE} elements, returns {@code Integer.MAX_VALUE}. 360 */ 361 public int size() { 362 return map.size(); 363 } 364 365 /** Returns {@code true} if this map contains no key-value mappings. */ 366 public boolean isEmpty() { 367 return map.isEmpty(); 368 } 369 370 /** 371 * Removes all of the mappings from this map. The map will be empty after this call returns. 372 * 373 * <p>This method is not atomic: the map may not be empty after returning if there were concurrent 374 * writes. 375 */ 376 public void clear() { 377 map.clear(); 378 } 379 380 @Override 381 public String toString() { 382 return map.toString(); 383 } 384 385 /* 386 * ConcurrentMap operations which we may eventually add. 387 * 388 * The problem with these is that remove(K, long) has to be done in two phases by definition --- 389 * first decrementing to zero, and then removing. putIfAbsent or replace could observe the 390 * intermediate zero-state. Ways we could deal with this are: 391 * 392 * - Don't define any of the ConcurrentMap operations. This is the current state of affairs. 393 * 394 * - Define putIfAbsent and replace as treating zero and absent identically (as currently 395 * implemented below). This is a bit surprising with putIfAbsent, which really becomes 396 * putIfZero. 397 * 398 * - Allow putIfAbsent and replace to distinguish between zero and absent, but don't implement 399 * remove(K, long). Without any two-phase operations it becomes feasible for all remaining 400 * operations to distinguish between zero and absent. If we do this, then perhaps we should add 401 * replace(key, long). 402 * 403 * - Introduce a special-value private static final AtomicLong that would have the meaning of 404 * removal-in-progress, and rework all operations to properly distinguish between zero and 405 * absent. 406 */ 407 408 /** 409 * If {@code key} is not already associated with a value or if {@code key} is associated with 410 * zero, associate it with {@code newValue}. Returns the previous value associated with {@code 411 * key}, or zero if there was no mapping for {@code key}. 412 */ 413 long putIfAbsent(K key, long newValue) { 414 while (true) { 415 AtomicLong atomic = map.get(key); 416 if (atomic == null) { 417 atomic = map.putIfAbsent(key, new AtomicLong(newValue)); 418 if (atomic == null) { 419 return 0L; 420 } 421 // atomic is now non-null; fall through 422 } 423 424 long oldValue = atomic.get(); 425 if (oldValue == 0L) { 426 // don't compareAndSet a zero 427 if (map.replace(key, atomic, new AtomicLong(newValue))) { 428 return 0L; 429 } 430 // atomic replaced 431 continue; 432 } 433 434 return oldValue; 435 } 436 } 437 438 /** 439 * If {@code (key, expectedOldValue)} is currently in the map, this method replaces {@code 440 * expectedOldValue} with {@code newValue} and returns true; otherwise, this method returns false. 441 * 442 * <p>If {@code expectedOldValue} is zero, this method will succeed if {@code (key, zero)} is 443 * currently in the map, or if {@code key} is not in the map at all. 444 */ 445 boolean replace(K key, long expectedOldValue, long newValue) { 446 if (expectedOldValue == 0L) { 447 return putIfAbsent(key, newValue) == 0L; 448 } else { 449 AtomicLong atomic = map.get(key); 450 return (atomic == null) ? false : atomic.compareAndSet(expectedOldValue, newValue); 451 } 452 } 453}