// Copyright 2011 Google Inc. All Rights Reserved. package com.google.common.util.concurrent; import static com.google.common.base.Preconditions.checkNotNull; import com.google.common.annotations.Beta; import com.google.common.base.Function; import com.google.common.collect.Maps; import java.util.Collections; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.atomic.AtomicLong; /** * A map containing {@code long} values that can be atomically updated. While writes to a * traditional {@code Map} rely on {@code put(K, V)}, the typical mechanism for writing to this map * is {@code addAndGet(K, long)}, which adds a {@code long} to the value currently associated with * {@code K}. If a key has not yet been associated with a value, its implicit value is zero. * *
Most methods in this class treat absent values and zero values identically, as individually * documented. Exceptions to this are {@link #containsKey}, {@link #size}, {@link #isEmpty}, * {@link #asMap}, and {@link #toString}. * *
Instances of this class may be used by multiple threads concurrently. All operations are * atomic unless otherwise noted. * *
Note: If your values are always positive and less than 2^31, you may wish to use a
* {@link com.google.common.collect.Multiset} such as
* {@link com.google.common.collect.ConcurrentHashMultiset} instead.
*
* Warning: Unlike {@code Multiset}, entries whose values are zero are not automatically
* removed from the map. Instead they must be removed manually with {@link #removeAllZeros}.
*
* @author Charles Fry
* @since 11.0
*/
@Beta
public final class AtomicLongMap This method is not atomic: the map may be visible in intermediate states, where some
* of the zero values have been removed and others have not.
*/
public void removeAllZeros() {
for (K key : map.keySet()) {
AtomicLong atomic = map.get(key);
if (atomic != null && atomic.get() == 0L) {
map.remove(key, atomic);
}
}
}
/**
* Returns the sum of all values in this map.
*
* This method is not atomic: the sum may or may not include other concurrent operations.
*/
public long sum() {
long sum = 0L;
for (AtomicLong value : map.values()) {
sum = sum + value.get();
}
return sum;
}
private transient Map This method is not atomic: the map may not be empty after returning if there were concurrent
* writes.
*/
public void clear() {
map.clear();
}
@Override
public String toString() {
return map.toString();
}
/*
* ConcurrentMap operations which we may eventually add.
*
* The problem with these is that remove(K, long) has to be done in two phases by definition ---
* first decrementing to zero, and then removing. putIfAbsent or replace could observe the
* intermediate zero-state. Ways we could deal with this are:
*
* - Don't define any of the ConcurrentMap operations. This is the current state of affairs.
*
* - Define putIfAbsent and replace as treating zero and absent identically (as currently
* implemented below). This is a bit surprising with putIfAbsent, which really becomes
* putIfZero.
*
* - Allow putIfAbsent and replace to distinguish between zero and absent, but don't implement
* remove(K, long). Without any two-phase operations it becomes feasible for all remaining
* operations to distinguish between zero and absent. If we do this, then perhaps we should add
* replace(key, long).
*
* - Introduce a special-value private static final AtomicLong that would have the meaning of
* removal-in-progress, and rework all operations to properly distinguish between zero and
* absent.
*/
/**
* If {@code key} is not already associated with a value or if {@code key} is associated with
* zero, associate it with {@code newValue}. Returns the previous value associated with
* {@code key}, or zero if there was no mapping for {@code key}.
*/
long putIfAbsent(K key, long newValue) {
for (;;) {
AtomicLong atomic = map.get(key);
if (atomic == null) {
atomic = map.putIfAbsent(key, new AtomicLong(newValue));
if (atomic == null) {
return 0L;
}
// atomic is now non-null; fall through
}
long oldValue = atomic.get();
if (oldValue == 0L) {
// don't compareAndSet a zero
if (map.replace(key, atomic, new AtomicLong(newValue))) {
return 0L;
}
// atomic replaced
continue;
}
return oldValue;
}
}
/**
* If {@code (key, expectedOldValue)} is currently in the map, this method replaces
* {@code expectedOldValue} with {@code newValue} and returns true; otherwise, this method
* returns false.
*
* If {@code expectedOldValue} is zero, this method will succeed if {@code (key, zero)}
* is currently in the map, or if {@code key} is not in the map at all.
*/
boolean replace(K key, long expectedOldValue, long newValue) {
if (expectedOldValue == 0L) {
return putIfAbsent(key, newValue) == 0L;
} else {
AtomicLong atomic = map.get(key);
return (atomic == null) ? false : atomic.compareAndSet(expectedOldValue, newValue);
}
}
/**
* If {@code (key, value)} is currently in the map, this method removes it and returns
* true; otherwise, this method returns false.
*/
boolean remove(K key, long value) {
AtomicLong atomic = map.get(key);
if (atomic == null) {
return false;
}
long oldValue = atomic.get();
if (oldValue != value) {
return false;
}
if (oldValue == 0L || atomic.compareAndSet(oldValue, 0L)) {
// only remove after setting to zero, to avoid concurrent updates
map.remove(key, atomic);
// succeed even if the remove fails, since the value was already adjusted
return true;
}
// value changed
return false;
}
}