17dd252788645e940eada959bdde927426e2531c9Paul Duffin/* 27dd252788645e940eada959bdde927426e2531c9Paul Duffin * Written by Doug Lea with assistance from members of JCP JSR-166 37dd252788645e940eada959bdde927426e2531c9Paul Duffin * Expert Group and released to the public domain, as explained at 47dd252788645e940eada959bdde927426e2531c9Paul Duffin * http://creativecommons.org/publicdomain/zero/1.0/ 57dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 67dd252788645e940eada959bdde927426e2531c9Paul Duffin 77dd252788645e940eada959bdde927426e2531c9Paul Duffin/* 87dd252788645e940eada959bdde927426e2531c9Paul Duffin * Source: 97dd252788645e940eada959bdde927426e2531c9Paul Duffin * http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166e/LongAdder.java?revision=1.8 107dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 117dd252788645e940eada959bdde927426e2531c9Paul Duffin 127dd252788645e940eada959bdde927426e2531c9Paul Duffinpackage com.google.common.cache; 137dd252788645e940eada959bdde927426e2531c9Paul Duffin 147dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.annotations.GwtCompatible; 157dd252788645e940eada959bdde927426e2531c9Paul Duffin 167dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.io.IOException; 177dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.io.ObjectInputStream; 180888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport java.io.ObjectOutputStream; 197dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.io.Serializable; 207dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.concurrent.atomic.AtomicLong; 217dd252788645e940eada959bdde927426e2531c9Paul Duffin 227dd252788645e940eada959bdde927426e2531c9Paul Duffin/** 237dd252788645e940eada959bdde927426e2531c9Paul Duffin * One or more variables that together maintain an initially zero 247dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code long} sum. When updates (method {@link #add}) are contended 257dd252788645e940eada959bdde927426e2531c9Paul Duffin * across threads, the set of variables may grow dynamically to reduce 267dd252788645e940eada959bdde927426e2531c9Paul Duffin * contention. Method {@link #sum} (or, equivalently, {@link 277dd252788645e940eada959bdde927426e2531c9Paul Duffin * #longValue}) returns the current total combined across the 287dd252788645e940eada959bdde927426e2531c9Paul Duffin * variables maintaining the sum. 297dd252788645e940eada959bdde927426e2531c9Paul Duffin * 307dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p> This class is usually preferable to {@link AtomicLong} when 317dd252788645e940eada959bdde927426e2531c9Paul Duffin * multiple threads update a common sum that is used for purposes such 327dd252788645e940eada959bdde927426e2531c9Paul Duffin * as collecting statistics, not for fine-grained synchronization 337dd252788645e940eada959bdde927426e2531c9Paul Duffin * control. Under low update contention, the two classes have similar 347dd252788645e940eada959bdde927426e2531c9Paul Duffin * characteristics. But under high contention, expected throughput of 357dd252788645e940eada959bdde927426e2531c9Paul Duffin * this class is significantly higher, at the expense of higher space 367dd252788645e940eada959bdde927426e2531c9Paul Duffin * consumption. 377dd252788645e940eada959bdde927426e2531c9Paul Duffin * 387dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>This class extends {@link Number}, but does <em>not</em> define 397dd252788645e940eada959bdde927426e2531c9Paul Duffin * methods such as {@code hashCode} and {@code compareTo} because 407dd252788645e940eada959bdde927426e2531c9Paul Duffin * instances are expected to be mutated, and so are not useful as 417dd252788645e940eada959bdde927426e2531c9Paul Duffin * collection keys. 427dd252788645e940eada959bdde927426e2531c9Paul Duffin * 437dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p><em>jsr166e note: This class is targeted to be placed in 447dd252788645e940eada959bdde927426e2531c9Paul Duffin * java.util.concurrent.atomic<em> 457dd252788645e940eada959bdde927426e2531c9Paul Duffin * 467dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 1.8 477dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Doug Lea 487dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 497dd252788645e940eada959bdde927426e2531c9Paul Duffin@GwtCompatible(emulated = true) 507dd252788645e940eada959bdde927426e2531c9Paul Duffinfinal class LongAdder extends Striped64 implements Serializable, LongAddable { 517dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final long serialVersionUID = 7249069246863182397L; 527dd252788645e940eada959bdde927426e2531c9Paul Duffin 530888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Version of plus for use in retryUpdate 550888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 560888a09821a98ac0680fad765217302858e70fa4Paul Duffin final long fn(long v, long x) { return v + x; } 570888a09821a98ac0680fad765217302858e70fa4Paul Duffin 580888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Creates a new adder with initial sum of zero. 600888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 610888a09821a98ac0680fad765217302858e70fa4Paul Duffin public LongAdder() { 620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 630888a09821a98ac0680fad765217302858e70fa4Paul Duffin 640888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Adds the given value. 660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param x the value to add 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 690888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void add(long x) { 700888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] as; long b, v; HashCode hc; Cell a; int n; 710888a09821a98ac0680fad765217302858e70fa4Paul Duffin if ((as = cells) != null || !casBase(b = base, b + x)) { 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean uncontended = true; 730888a09821a98ac0680fad765217302858e70fa4Paul Duffin int h = (hc = threadHashCode.get()).code; 740888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (as == null || (n = as.length) < 1 || 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin (a = as[(n - 1) & h]) == null || 760888a09821a98ac0680fad765217302858e70fa4Paul Duffin !(uncontended = a.cas(v = a.value, v + x))) 770888a09821a98ac0680fad765217302858e70fa4Paul Duffin retryUpdate(x, hc, uncontended); 780888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 790888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 800888a09821a98ac0680fad765217302858e70fa4Paul Duffin 810888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Equivalent to {@code add(1)}. 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 840888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void increment() { 850888a09821a98ac0680fad765217302858e70fa4Paul Duffin add(1L); 860888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 870888a09821a98ac0680fad765217302858e70fa4Paul Duffin 880888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Equivalent to {@code add(-1)}. 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void decrement() { 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin add(-1L); 937dd252788645e940eada959bdde927426e2531c9Paul Duffin } 940888a09821a98ac0680fad765217302858e70fa4Paul Duffin 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 960888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the current sum. The returned value is <em>NOT</em> an 970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * atomic snapshot: Invocation in the absence of concurrent 980888a09821a98ac0680fad765217302858e70fa4Paul Duffin * updates returns an accurate result, but concurrent updates that 990888a09821a98ac0680fad765217302858e70fa4Paul Duffin * occur while the sum is being calculated might not be 1000888a09821a98ac0680fad765217302858e70fa4Paul Duffin * incorporated. 1010888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1020888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the sum 1030888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1040888a09821a98ac0680fad765217302858e70fa4Paul Duffin public long sum() { 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin long sum = base; 1060888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] as = cells; 1070888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (as != null) { 1080888a09821a98ac0680fad765217302858e70fa4Paul Duffin int n = as.length; 1090888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = 0; i < n; ++i) { 1100888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell a = as[i]; 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (a != null) 1120888a09821a98ac0680fad765217302858e70fa4Paul Duffin sum += a.value; 1130888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1140888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1150888a09821a98ac0680fad765217302858e70fa4Paul Duffin return sum; 1167dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1170888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1180888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1190888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Resets variables maintaining the sum to zero. This method may 1200888a09821a98ac0680fad765217302858e70fa4Paul Duffin * be a useful alternative to creating a new adder, but is only 1210888a09821a98ac0680fad765217302858e70fa4Paul Duffin * effective if there are no concurrent updates. Because this 1220888a09821a98ac0680fad765217302858e70fa4Paul Duffin * method is intrinsically racy, it should only be used when it is 1230888a09821a98ac0680fad765217302858e70fa4Paul Duffin * known that no threads are concurrently updating. 1240888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1250888a09821a98ac0680fad765217302858e70fa4Paul Duffin public void reset() { 1260888a09821a98ac0680fad765217302858e70fa4Paul Duffin internalReset(0L); 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1290888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1300888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Equivalent in effect to {@link #sum} followed by {@link 1310888a09821a98ac0680fad765217302858e70fa4Paul Duffin * #reset}. This method may apply for example during quiescent 1320888a09821a98ac0680fad765217302858e70fa4Paul Duffin * points between multithreaded computations. If there are 1330888a09821a98ac0680fad765217302858e70fa4Paul Duffin * updates concurrent with this method, the returned value is 1340888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <em>not</em> guaranteed to be the final value occurring before 1350888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the reset. 1360888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1370888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the sum 1380888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin public long sumThenReset() { 1400888a09821a98ac0680fad765217302858e70fa4Paul Duffin long sum = base; 1410888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] as = cells; 1420888a09821a98ac0680fad765217302858e70fa4Paul Duffin base = 0L; 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (as != null) { 1440888a09821a98ac0680fad765217302858e70fa4Paul Duffin int n = as.length; 1450888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (int i = 0; i < n; ++i) { 1460888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell a = as[i]; 1470888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (a != null) { 1480888a09821a98ac0680fad765217302858e70fa4Paul Duffin sum += a.value; 1490888a09821a98ac0680fad765217302858e70fa4Paul Duffin a.value = 0L; 1500888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1510888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1527dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1530888a09821a98ac0680fad765217302858e70fa4Paul Duffin return sum; 1540888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1550888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the String representation of the {@link #sum}. 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the String representation of the {@link #sum} 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1600888a09821a98ac0680fad765217302858e70fa4Paul Duffin public String toString() { 1610888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Long.toString(sum()); 1620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1630888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1640888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Equivalent to {@link #sum}. 1660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return the sum 1680888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1690888a09821a98ac0680fad765217302858e70fa4Paul Duffin public long longValue() { 1700888a09821a98ac0680fad765217302858e70fa4Paul Duffin return sum(); 1710888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1720888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1730888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1740888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the {@link #sum} as an {@code int} after a narrowing 1750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * primitive conversion. 1760888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1770888a09821a98ac0680fad765217302858e70fa4Paul Duffin public int intValue() { 1780888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (int)sum(); 1790888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1800888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1810888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the {@link #sum} as a {@code float} 1830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * after a widening primitive conversion. 1840888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1850888a09821a98ac0680fad765217302858e70fa4Paul Duffin public float floatValue() { 1860888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (float)sum(); 1870888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1880888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1890888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Returns the {@link #sum} as a {@code double} after a widening 1910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * primitive conversion. 1920888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1930888a09821a98ac0680fad765217302858e70fa4Paul Duffin public double doubleValue() { 1940888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (double)sum(); 1950888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1960888a09821a98ac0680fad765217302858e70fa4Paul Duffin 1970888a09821a98ac0680fad765217302858e70fa4Paul Duffin private void writeObject(ObjectOutputStream s) 1980888a09821a98ac0680fad765217302858e70fa4Paul Duffin throws java.io.IOException { 1990888a09821a98ac0680fad765217302858e70fa4Paul Duffin s.defaultWriteObject(); 2000888a09821a98ac0680fad765217302858e70fa4Paul Duffin s.writeLong(sum()); 2010888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2020888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2030888a09821a98ac0680fad765217302858e70fa4Paul Duffin private void readObject(ObjectInputStream s) 2040888a09821a98ac0680fad765217302858e70fa4Paul Duffin throws IOException, ClassNotFoundException { 2050888a09821a98ac0680fad765217302858e70fa4Paul Duffin s.defaultReadObject(); 2060888a09821a98ac0680fad765217302858e70fa4Paul Duffin busy = 0; 2070888a09821a98ac0680fad765217302858e70fa4Paul Duffin cells = null; 2080888a09821a98ac0680fad765217302858e70fa4Paul Duffin base = s.readLong(); 2097dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2107dd252788645e940eada959bdde927426e2531c9Paul Duffin 2117dd252788645e940eada959bdde927426e2531c9Paul Duffin} 212