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/Striped64.java?revision=1.7 107dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 117dd252788645e940eada959bdde927426e2531c9Paul Duffin 127dd252788645e940eada959bdde927426e2531c9Paul Duffinpackage com.google.common.cache; 137dd252788645e940eada959bdde927426e2531c9Paul Duffin 147dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Random; 15f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffinimport java.util.concurrent.atomic.AtomicIntegerFieldUpdater; 16f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffinimport java.util.concurrent.atomic.AtomicLongFieldUpdater; 177dd252788645e940eada959bdde927426e2531c9Paul Duffin 187dd252788645e940eada959bdde927426e2531c9Paul Duffin/** 197dd252788645e940eada959bdde927426e2531c9Paul Duffin * A package-local class holding common representation and mechanics 207dd252788645e940eada959bdde927426e2531c9Paul Duffin * for classes supporting dynamic striping on 64bit values. The class 217dd252788645e940eada959bdde927426e2531c9Paul Duffin * extends Number so that concrete subclasses must publicly do so. 227dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 237dd252788645e940eada959bdde927426e2531c9Paul Duffinabstract class Striped64 extends Number { 240888a09821a98ac0680fad765217302858e70fa4Paul Duffin /* 250888a09821a98ac0680fad765217302858e70fa4Paul Duffin * This class maintains a lazily-initialized table of atomically 260888a09821a98ac0680fad765217302858e70fa4Paul Duffin * updated variables, plus an extra "base" field. The table size 270888a09821a98ac0680fad765217302858e70fa4Paul Duffin * is a power of two. Indexing uses masked per-thread hash codes. 280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Nearly all declarations in this class are package-private, 290888a09821a98ac0680fad765217302858e70fa4Paul Duffin * accessed directly by subclasses. 300888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 310888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Table entries are of class Cell; a variant of AtomicLong padded 320888a09821a98ac0680fad765217302858e70fa4Paul Duffin * to reduce cache contention on most processors. Padding is 330888a09821a98ac0680fad765217302858e70fa4Paul Duffin * overkill for most Atomics because they are usually irregularly 340888a09821a98ac0680fad765217302858e70fa4Paul Duffin * scattered in memory and thus don't interfere much with each 350888a09821a98ac0680fad765217302858e70fa4Paul Duffin * other. But Atomic objects residing in arrays will tend to be 360888a09821a98ac0680fad765217302858e70fa4Paul Duffin * placed adjacent to each other, and so will most often share 370888a09821a98ac0680fad765217302858e70fa4Paul Duffin * cache lines (with a huge negative performance impact) without 380888a09821a98ac0680fad765217302858e70fa4Paul Duffin * this precaution. 390888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 400888a09821a98ac0680fad765217302858e70fa4Paul Duffin * In part because Cells are relatively large, we avoid creating 410888a09821a98ac0680fad765217302858e70fa4Paul Duffin * them until they are needed. When there is no contention, all 420888a09821a98ac0680fad765217302858e70fa4Paul Duffin * updates are made to the base field. Upon first contention (a 430888a09821a98ac0680fad765217302858e70fa4Paul Duffin * failed CAS on base update), the table is initialized to size 2. 440888a09821a98ac0680fad765217302858e70fa4Paul Duffin * The table size is doubled upon further contention until 450888a09821a98ac0680fad765217302858e70fa4Paul Duffin * reaching the nearest power of two greater than or equal to the 460888a09821a98ac0680fad765217302858e70fa4Paul Duffin * number of CPUS. Table slots remain empty (null) until they are 470888a09821a98ac0680fad765217302858e70fa4Paul Duffin * needed. 480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * A single spinlock ("busy") is used for initializing and 500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * resizing the table, as well as populating slots with new Cells. 510888a09821a98ac0680fad765217302858e70fa4Paul Duffin * There is no need for a blocking lock: When the lock is not 520888a09821a98ac0680fad765217302858e70fa4Paul Duffin * available, threads try other slots (or the base). During these 530888a09821a98ac0680fad765217302858e70fa4Paul Duffin * retries, there is increased contention and reduced locality, 540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * which is still better than alternatives. 550888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 560888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Per-thread hash codes are initialized to random values. 570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Contention and/or table collisions are indicated by failed 580888a09821a98ac0680fad765217302858e70fa4Paul Duffin * CASes when performing an update operation (see method 590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * retryUpdate). Upon a collision, if the table size is less than 600888a09821a98ac0680fad765217302858e70fa4Paul Duffin * the capacity, it is doubled in size unless some other thread 610888a09821a98ac0680fad765217302858e70fa4Paul Duffin * holds the lock. If a hashed slot is empty, and lock is 620888a09821a98ac0680fad765217302858e70fa4Paul Duffin * available, a new Cell is created. Otherwise, if the slot 630888a09821a98ac0680fad765217302858e70fa4Paul Duffin * exists, a CAS is tried. Retries proceed by "double hashing", 640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * using a secondary hash (Marsaglia XorShift) to try to find a 650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * free slot. 660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * The table size is capped because, when there are more threads 680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * than CPUs, supposing that each thread were bound to a CPU, 690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * there would exist a perfect hash function mapping threads to 700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * slots that eliminates collisions. When we reach capacity, we 710888a09821a98ac0680fad765217302858e70fa4Paul Duffin * search for this mapping by randomly varying the hash codes of 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * colliding threads. Because search is random, and collisions 730888a09821a98ac0680fad765217302858e70fa4Paul Duffin * only become known via CAS failures, convergence can be slow, 740888a09821a98ac0680fad765217302858e70fa4Paul Duffin * and because threads are typically not bound to CPUS forever, 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * may not occur at all. However, despite these limitations, 760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * observed contention rates are typically low in these cases. 770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * It is possible for a Cell to become unused when threads that 790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * once hashed to it terminate, as well as in the case where 800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * doubling the table causes no thread to hash to it under 810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * expanded mask. We do not try to detect or remove such cells, 820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * under the assumption that for long-running instances, observed 830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * contention levels will recur, so the cells will eventually be 840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * needed again; and for short-lived ones, it does not matter. 850888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 867dd252788645e940eada959bdde927426e2531c9Paul Duffin 870888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 880888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Padded variant of AtomicLong supporting only raw accesses plus CAS. 890888a09821a98ac0680fad765217302858e70fa4Paul Duffin * The value field is placed between pads, hoping that the JVM doesn't 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * reorder them. 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * JVM intrinsics note: It would be possible to use a release-only 930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * form of CAS here, if it were provided. 940888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin static final class Cell { 96f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin @SuppressWarnings("UnusedDeclaration") 970888a09821a98ac0680fad765217302858e70fa4Paul Duffin volatile long p0, p1, p2, p3, p4, p5, p6; 980888a09821a98ac0680fad765217302858e70fa4Paul Duffin volatile long value; 99f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin @SuppressWarnings("UnusedDeclaration") 1000888a09821a98ac0680fad765217302858e70fa4Paul Duffin volatile long q0, q1, q2, q3, q4, q5, q6; 1010888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell(long x) { value = x; } 1027dd252788645e940eada959bdde927426e2531c9Paul Duffin 1030888a09821a98ac0680fad765217302858e70fa4Paul Duffin final boolean cas(long cmp, long val) { 104f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin return valueUpdater.compareAndSet(this, cmp, val); 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1067dd252788645e940eada959bdde927426e2531c9Paul Duffin 107f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin private static final AtomicLongFieldUpdater<Cell> valueUpdater = 108f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin AtomicLongFieldUpdater.newUpdater(Cell.class, "value"); 1097dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1107dd252788645e940eada959bdde927426e2531c9Paul Duffin 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1120888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Holder for the thread-local hash code. The code is initially 1130888a09821a98ac0680fad765217302858e70fa4Paul Duffin * random, but may be set to a different value upon collisions. 1140888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1150888a09821a98ac0680fad765217302858e70fa4Paul Duffin static final class HashCode { 1160888a09821a98ac0680fad765217302858e70fa4Paul Duffin static final Random rng = new Random(); 1170888a09821a98ac0680fad765217302858e70fa4Paul Duffin int code; 1180888a09821a98ac0680fad765217302858e70fa4Paul Duffin HashCode() { 1190888a09821a98ac0680fad765217302858e70fa4Paul Duffin int h = rng.nextInt(); // Avoid zero to allow xorShift rehash 1200888a09821a98ac0680fad765217302858e70fa4Paul Duffin code = (h == 0) ? 1 : h; 1210888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1227dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1237dd252788645e940eada959bdde927426e2531c9Paul Duffin 1240888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1250888a09821a98ac0680fad765217302858e70fa4Paul Duffin * The corresponding ThreadLocal class 1260888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin static final class ThreadHashCode extends ThreadLocal<HashCode> { 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin public HashCode initialValue() { return new HashCode(); } 1297dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1307dd252788645e940eada959bdde927426e2531c9Paul Duffin 1310888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1320888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Static per-thread hash codes. Shared across all instances to 1330888a09821a98ac0680fad765217302858e70fa4Paul Duffin * reduce ThreadLocal pollution and because adjustments due to 1340888a09821a98ac0680fad765217302858e70fa4Paul Duffin * collisions in one table are likely to be appropriate for 1350888a09821a98ac0680fad765217302858e70fa4Paul Duffin * others. 1360888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1370888a09821a98ac0680fad765217302858e70fa4Paul Duffin static final ThreadHashCode threadHashCode = new ThreadHashCode(); 1387dd252788645e940eada959bdde927426e2531c9Paul Duffin 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** Number of CPUS, to place bound on table size */ 1400888a09821a98ac0680fad765217302858e70fa4Paul Duffin static final int NCPU = Runtime.getRuntime().availableProcessors(); 1417dd252788645e940eada959bdde927426e2531c9Paul Duffin 1420888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Table of cells. When non-null, size is a power of 2. 1440888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1450888a09821a98ac0680fad765217302858e70fa4Paul Duffin transient volatile Cell[] cells; 1467dd252788645e940eada959bdde927426e2531c9Paul Duffin 1470888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1480888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Base value, used mainly when there is no contention, but also as 1490888a09821a98ac0680fad765217302858e70fa4Paul Duffin * a fallback during table initialization races. Updated via CAS. 1500888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1510888a09821a98ac0680fad765217302858e70fa4Paul Duffin transient volatile long base; 1527dd252788645e940eada959bdde927426e2531c9Paul Duffin 1530888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1540888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Spinlock (locked via CAS) used when resizing and/or creating Cells. 1550888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin transient volatile int busy; 1577dd252788645e940eada959bdde927426e2531c9Paul Duffin 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Package-private default constructor 1600888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1610888a09821a98ac0680fad765217302858e70fa4Paul Duffin Striped64() { 1620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1637dd252788645e940eada959bdde927426e2531c9Paul Duffin 1640888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * CASes the base field. 1660888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1670888a09821a98ac0680fad765217302858e70fa4Paul Duffin final boolean casBase(long cmp, long val) { 168f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin return baseUpdater.compareAndSet(this, cmp, val); 1690888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1707dd252788645e940eada959bdde927426e2531c9Paul Duffin 1710888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1720888a09821a98ac0680fad765217302858e70fa4Paul Duffin * CASes the busy field from 0 to 1 to acquire lock. 1730888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1740888a09821a98ac0680fad765217302858e70fa4Paul Duffin final boolean casBusy() { 175f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin return busyUpdater.compareAndSet(this, 0, 1); 1760888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1777dd252788645e940eada959bdde927426e2531c9Paul Duffin 1780888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Computes the function of current and new value. Subclasses 1800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * should open-code this update function for most uses, but the 1810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * virtualized form is needed within retryUpdate. 1820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param currentValue the current value (of either base or a cell) 1840888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param newValue the argument from a user update call 1850888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return result of the update function 1860888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1870888a09821a98ac0680fad765217302858e70fa4Paul Duffin abstract long fn(long currentValue, long newValue); 1887dd252788645e940eada959bdde927426e2531c9Paul Duffin 1890888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1900888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Handles cases of updates involving initialization, resizing, 1910888a09821a98ac0680fad765217302858e70fa4Paul Duffin * creating new Cells, and/or contention. See above for 1920888a09821a98ac0680fad765217302858e70fa4Paul Duffin * explanation. This method suffers the usual non-modularity 1930888a09821a98ac0680fad765217302858e70fa4Paul Duffin * problems of optimistic retry code, relying on rechecked sets of 1940888a09821a98ac0680fad765217302858e70fa4Paul Duffin * reads. 1950888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1960888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param x the value 1970888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param hc the hash code holder 1980888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param wasUncontended false if CAS failed before call 1990888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2000888a09821a98ac0680fad765217302858e70fa4Paul Duffin final void retryUpdate(long x, HashCode hc, boolean wasUncontended) { 2010888a09821a98ac0680fad765217302858e70fa4Paul Duffin int h = hc.code; 2020888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean collide = false; // True if last slot nonempty 2030888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (;;) { 2040888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] as; Cell a; int n; long v; 2050888a09821a98ac0680fad765217302858e70fa4Paul Duffin if ((as = cells) != null && (n = as.length) > 0) { 2060888a09821a98ac0680fad765217302858e70fa4Paul Duffin if ((a = as[(n - 1) & h]) == null) { 2070888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (busy == 0) { // Try to attach new Cell 2080888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell r = new Cell(x); // Optimistically create 2090888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (busy == 0 && casBusy()) { 2100888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean created = false; 2110888a09821a98ac0680fad765217302858e70fa4Paul Duffin try { // Recheck under lock 2120888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] rs; int m, j; 2130888a09821a98ac0680fad765217302858e70fa4Paul Duffin if ((rs = cells) != null && 2140888a09821a98ac0680fad765217302858e70fa4Paul Duffin (m = rs.length) > 0 && 2150888a09821a98ac0680fad765217302858e70fa4Paul Duffin rs[j = (m - 1) & h] == null) { 2160888a09821a98ac0680fad765217302858e70fa4Paul Duffin rs[j] = r; 2170888a09821a98ac0680fad765217302858e70fa4Paul Duffin created = true; 2180888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2190888a09821a98ac0680fad765217302858e70fa4Paul Duffin } finally { 2200888a09821a98ac0680fad765217302858e70fa4Paul Duffin busy = 0; 2210888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2220888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (created) 2230888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 2240888a09821a98ac0680fad765217302858e70fa4Paul Duffin continue; // Slot is now non-empty 2250888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2260888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2270888a09821a98ac0680fad765217302858e70fa4Paul Duffin collide = false; 2287dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2290888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (!wasUncontended) // CAS already known to fail 2300888a09821a98ac0680fad765217302858e70fa4Paul Duffin wasUncontended = true; // Continue after rehash 2310888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (a.cas(v = a.value, fn(v, x))) 2320888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 2330888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (n >= NCPU || cells != as) 2340888a09821a98ac0680fad765217302858e70fa4Paul Duffin collide = false; // At max size or stale 2350888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (!collide) 2360888a09821a98ac0680fad765217302858e70fa4Paul Duffin collide = true; 2370888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (busy == 0 && casBusy()) { 2380888a09821a98ac0680fad765217302858e70fa4Paul Duffin try { 2390888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (cells == as) { // Expand table unless stale 2400888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] rs = new Cell[n << 1]; 241f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin System.arraycopy(as, 0, rs, 0, n); 2420888a09821a98ac0680fad765217302858e70fa4Paul Duffin cells = rs; 2430888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2440888a09821a98ac0680fad765217302858e70fa4Paul Duffin } finally { 2450888a09821a98ac0680fad765217302858e70fa4Paul Duffin busy = 0; 2460888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2470888a09821a98ac0680fad765217302858e70fa4Paul Duffin collide = false; 2480888a09821a98ac0680fad765217302858e70fa4Paul Duffin continue; // Retry with expanded table 2490888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2500888a09821a98ac0680fad765217302858e70fa4Paul Duffin h ^= h << 13; // Rehash 2510888a09821a98ac0680fad765217302858e70fa4Paul Duffin h ^= h >>> 17; 2520888a09821a98ac0680fad765217302858e70fa4Paul Duffin h ^= h << 5; 2537dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2540888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (busy == 0 && cells == as && casBusy()) { 2550888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean init = false; 2560888a09821a98ac0680fad765217302858e70fa4Paul Duffin try { // Initialize table 2570888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (cells == as) { 2580888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] rs = new Cell[2]; 2590888a09821a98ac0680fad765217302858e70fa4Paul Duffin rs[h & 1] = new Cell(x); 2600888a09821a98ac0680fad765217302858e70fa4Paul Duffin cells = rs; 2610888a09821a98ac0680fad765217302858e70fa4Paul Duffin init = true; 2620888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2630888a09821a98ac0680fad765217302858e70fa4Paul Duffin } finally { 2640888a09821a98ac0680fad765217302858e70fa4Paul Duffin busy = 0; 2650888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2660888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (init) 2670888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 2687dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2690888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (casBase(v = base, fn(v, x))) 2700888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; // Fall back on using base 2717dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2720888a09821a98ac0680fad765217302858e70fa4Paul Duffin hc.code = h; // Record index for next time 2730888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2740888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2750888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Sets base and all cells to the given value. 2770888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2780888a09821a98ac0680fad765217302858e70fa4Paul Duffin final void internalReset(long initialValue) { 2790888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] as = cells; 2800888a09821a98ac0680fad765217302858e70fa4Paul Duffin base = initialValue; 2810888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (as != null) { 282f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin for (Cell a : as) { 2830888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (a != null) 284f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin a.value = initialValue; 2850888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2867dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2877dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2887dd252788645e940eada959bdde927426e2531c9Paul Duffin 289f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin private static final AtomicLongFieldUpdater<Striped64> baseUpdater = 290f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin AtomicLongFieldUpdater.newUpdater(Striped64.class, "base"); 291f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin private static final AtomicIntegerFieldUpdater<Striped64> busyUpdater = 292f08592bfbbd7d91467623e313fd02baf98de85a0Paul Duffin AtomicIntegerFieldUpdater.newUpdater(Striped64.class, "busy"); 2937dd252788645e940eada959bdde927426e2531c9Paul Duffin} 294