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: 93ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/jsr166e/Striped64.java?revision=1.9 107dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 117dd252788645e940eada959bdde927426e2531c9Paul Duffin 127dd252788645e940eada959bdde927426e2531c9Paul Duffinpackage com.google.common.cache; 137dd252788645e940eada959bdde927426e2531c9Paul Duffin 147dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Random; 159dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffinimport java.util.concurrent.atomic.AtomicIntegerFieldUpdater; 169dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul 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. 513ecfa412eddc4b084663f38d562537b86b9734d5Paul 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 { 969dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin @SuppressWarnings("UnusedDeclaration") 970888a09821a98ac0680fad765217302858e70fa4Paul Duffin volatile long p0, p1, p2, p3, p4, p5, p6; 980888a09821a98ac0680fad765217302858e70fa4Paul Duffin volatile long value; 999dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul 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) { 1049dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin return valueUpdater.compareAndSet(this, cmp, val); 1050888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1063ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin 1079dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin private static final AtomicLongFieldUpdater<Cell> valueUpdater = 1089dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin AtomicLongFieldUpdater.newUpdater(Cell.class, "value"); 1097dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1107dd252788645e940eada959bdde927426e2531c9Paul Duffin 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1123ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * ThreadLocal holding a single-slot int array holding hash code. 1133ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Unlike the JDK8 version of this class, we use a suboptimal 1143ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * int[] representation to avoid introducing a new type that can 1153ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * impede class-unloading when ThreadLocals are not removed. 1160888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1173ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin static final ThreadLocal<int[]> threadHashCode = new ThreadLocal<int[]>(); 1187dd252788645e940eada959bdde927426e2531c9Paul Duffin 1190888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1203ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin * Generator of new random hash codes 1210888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1223ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin static final Random rng = new Random(); 1237dd252788645e940eada959bdde927426e2531c9Paul Duffin 1240888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** Number of CPUS, to place bound on table size */ 1250888a09821a98ac0680fad765217302858e70fa4Paul Duffin static final int NCPU = Runtime.getRuntime().availableProcessors(); 1267dd252788645e940eada959bdde927426e2531c9Paul Duffin 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Table of cells. When non-null, size is a power of 2. 1290888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1300888a09821a98ac0680fad765217302858e70fa4Paul Duffin transient volatile Cell[] cells; 1317dd252788645e940eada959bdde927426e2531c9Paul Duffin 1320888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1330888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Base value, used mainly when there is no contention, but also as 1340888a09821a98ac0680fad765217302858e70fa4Paul Duffin * a fallback during table initialization races. Updated via CAS. 1350888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1360888a09821a98ac0680fad765217302858e70fa4Paul Duffin transient volatile long base; 1377dd252788645e940eada959bdde927426e2531c9Paul Duffin 1380888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Spinlock (locked via CAS) used when resizing and/or creating Cells. 1400888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1410888a09821a98ac0680fad765217302858e70fa4Paul Duffin transient volatile int busy; 1427dd252788645e940eada959bdde927426e2531c9Paul Duffin 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1440888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Package-private default constructor 1450888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1460888a09821a98ac0680fad765217302858e70fa4Paul Duffin Striped64() { 1470888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1487dd252788645e940eada959bdde927426e2531c9Paul Duffin 1490888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1500888a09821a98ac0680fad765217302858e70fa4Paul Duffin * CASes the base field. 1510888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1520888a09821a98ac0680fad765217302858e70fa4Paul Duffin final boolean casBase(long cmp, long val) { 1539dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin return baseUpdater.compareAndSet(this, cmp, val); 1540888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1557dd252788645e940eada959bdde927426e2531c9Paul Duffin 1560888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1570888a09821a98ac0680fad765217302858e70fa4Paul Duffin * CASes the busy field from 0 to 1 to acquire lock. 1580888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin final boolean casBusy() { 1609dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin return busyUpdater.compareAndSet(this, 0, 1); 1610888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 1627dd252788645e940eada959bdde927426e2531c9Paul Duffin 1630888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1640888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Computes the function of current and new value. Subclasses 1650888a09821a98ac0680fad765217302858e70fa4Paul Duffin * should open-code this update function for most uses, but the 1660888a09821a98ac0680fad765217302858e70fa4Paul Duffin * virtualized form is needed within retryUpdate. 1670888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param currentValue the current value (of either base or a cell) 1690888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param newValue the argument from a user update call 1700888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @return result of the update function 1710888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1720888a09821a98ac0680fad765217302858e70fa4Paul Duffin abstract long fn(long currentValue, long newValue); 1737dd252788645e940eada959bdde927426e2531c9Paul Duffin 1740888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 1750888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Handles cases of updates involving initialization, resizing, 1760888a09821a98ac0680fad765217302858e70fa4Paul Duffin * creating new Cells, and/or contention. See above for 1770888a09821a98ac0680fad765217302858e70fa4Paul Duffin * explanation. This method suffers the usual non-modularity 1780888a09821a98ac0680fad765217302858e70fa4Paul Duffin * problems of optimistic retry code, relying on rechecked sets of 1790888a09821a98ac0680fad765217302858e70fa4Paul Duffin * reads. 1800888a09821a98ac0680fad765217302858e70fa4Paul Duffin * 1810888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param x the value 1820888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param hc the hash code holder 1830888a09821a98ac0680fad765217302858e70fa4Paul Duffin * @param wasUncontended false if CAS failed before call 1840888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 1853ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin final void retryUpdate(long x, int[] hc, boolean wasUncontended) { 1863ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin int h; 1873ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin if (hc == null) { 1883ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin threadHashCode.set(hc = new int[1]); // Initialize randomly 1893ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin int r = rng.nextInt(); // Avoid zero to allow xorShift rehash 1903ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin h = hc[0] = (r == 0) ? 1 : r; 1913ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin } 1923ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin else 1933ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin h = hc[0]; 1940888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean collide = false; // True if last slot nonempty 1950888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (;;) { 1960888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] as; Cell a; int n; long v; 1970888a09821a98ac0680fad765217302858e70fa4Paul Duffin if ((as = cells) != null && (n = as.length) > 0) { 1980888a09821a98ac0680fad765217302858e70fa4Paul Duffin if ((a = as[(n - 1) & h]) == null) { 1990888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (busy == 0) { // Try to attach new Cell 2000888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell r = new Cell(x); // Optimistically create 2010888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (busy == 0 && casBusy()) { 2020888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean created = false; 2030888a09821a98ac0680fad765217302858e70fa4Paul Duffin try { // Recheck under lock 2040888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] rs; int m, j; 2050888a09821a98ac0680fad765217302858e70fa4Paul Duffin if ((rs = cells) != null && 2060888a09821a98ac0680fad765217302858e70fa4Paul Duffin (m = rs.length) > 0 && 2070888a09821a98ac0680fad765217302858e70fa4Paul Duffin rs[j = (m - 1) & h] == null) { 2080888a09821a98ac0680fad765217302858e70fa4Paul Duffin rs[j] = r; 2090888a09821a98ac0680fad765217302858e70fa4Paul Duffin created = true; 2100888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2110888a09821a98ac0680fad765217302858e70fa4Paul Duffin } finally { 2120888a09821a98ac0680fad765217302858e70fa4Paul Duffin busy = 0; 2130888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2140888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (created) 2150888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 2160888a09821a98ac0680fad765217302858e70fa4Paul Duffin continue; // Slot is now non-empty 2170888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2180888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2190888a09821a98ac0680fad765217302858e70fa4Paul Duffin collide = false; 2207dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2210888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (!wasUncontended) // CAS already known to fail 2220888a09821a98ac0680fad765217302858e70fa4Paul Duffin wasUncontended = true; // Continue after rehash 2230888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (a.cas(v = a.value, fn(v, x))) 2240888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 2250888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (n >= NCPU || cells != as) 2260888a09821a98ac0680fad765217302858e70fa4Paul Duffin collide = false; // At max size or stale 2270888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (!collide) 2280888a09821a98ac0680fad765217302858e70fa4Paul Duffin collide = true; 2290888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (busy == 0 && casBusy()) { 2300888a09821a98ac0680fad765217302858e70fa4Paul Duffin try { 2310888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (cells == as) { // Expand table unless stale 2320888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] rs = new Cell[n << 1]; 2339dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin System.arraycopy(as, 0, rs, 0, n); 2340888a09821a98ac0680fad765217302858e70fa4Paul Duffin cells = rs; 2350888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2360888a09821a98ac0680fad765217302858e70fa4Paul Duffin } finally { 2370888a09821a98ac0680fad765217302858e70fa4Paul Duffin busy = 0; 2380888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2390888a09821a98ac0680fad765217302858e70fa4Paul Duffin collide = false; 2400888a09821a98ac0680fad765217302858e70fa4Paul Duffin continue; // Retry with expanded table 2410888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2420888a09821a98ac0680fad765217302858e70fa4Paul Duffin h ^= h << 13; // Rehash 2430888a09821a98ac0680fad765217302858e70fa4Paul Duffin h ^= h >>> 17; 2440888a09821a98ac0680fad765217302858e70fa4Paul Duffin h ^= h << 5; 2453ecfa412eddc4b084663f38d562537b86b9734d5Paul Duffin hc[0] = h; // Record index for next time 2467dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2470888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (busy == 0 && cells == as && casBusy()) { 2480888a09821a98ac0680fad765217302858e70fa4Paul Duffin boolean init = false; 2490888a09821a98ac0680fad765217302858e70fa4Paul Duffin try { // Initialize table 2500888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (cells == as) { 2510888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] rs = new Cell[2]; 2520888a09821a98ac0680fad765217302858e70fa4Paul Duffin rs[h & 1] = new Cell(x); 2530888a09821a98ac0680fad765217302858e70fa4Paul Duffin cells = rs; 2540888a09821a98ac0680fad765217302858e70fa4Paul Duffin init = true; 2550888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2560888a09821a98ac0680fad765217302858e70fa4Paul Duffin } finally { 2570888a09821a98ac0680fad765217302858e70fa4Paul Duffin busy = 0; 2580888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2590888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (init) 2600888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; 2617dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2620888a09821a98ac0680fad765217302858e70fa4Paul Duffin else if (casBase(v = base, fn(v, x))) 2630888a09821a98ac0680fad765217302858e70fa4Paul Duffin break; // Fall back on using base 2647dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2650888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2660888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2670888a09821a98ac0680fad765217302858e70fa4Paul Duffin /** 2680888a09821a98ac0680fad765217302858e70fa4Paul Duffin * Sets base and all cells to the given value. 2690888a09821a98ac0680fad765217302858e70fa4Paul Duffin */ 2700888a09821a98ac0680fad765217302858e70fa4Paul Duffin final void internalReset(long initialValue) { 2710888a09821a98ac0680fad765217302858e70fa4Paul Duffin Cell[] as = cells; 2720888a09821a98ac0680fad765217302858e70fa4Paul Duffin base = initialValue; 2730888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (as != null) { 2749dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin for (Cell a : as) { 2750888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (a != null) 2769dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin a.value = initialValue; 2770888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2787dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2797dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2807dd252788645e940eada959bdde927426e2531c9Paul Duffin 2819dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin private static final AtomicLongFieldUpdater<Striped64> baseUpdater = 2829dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin AtomicLongFieldUpdater.newUpdater(Striped64.class, "base"); 2839dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin private static final AtomicIntegerFieldUpdater<Striped64> busyUpdater = 2849dd148481d0f4705aa7f560a24c9d8a72a493a9aPaul Duffin AtomicIntegerFieldUpdater.newUpdater(Striped64.class, "busy"); 2857dd252788645e940eada959bdde927426e2531c9Paul Duffin} 286