1b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak/* 229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is free software; you can redistribute it and/or modify it 529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * under the terms of the GNU General Public License version 2 only, as 629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * published by the Free Software Foundation. Oracle designates this 729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * particular file as subject to the "Classpath" exception as provided 829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * by Oracle in the LICENSE file that accompanied this code. 929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This code is distributed in the hope that it will be useful, but WITHOUT 1129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * version 2 for more details (a copy is included in the LICENSE file that 1429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * accompanied this code). 1529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 1629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * You should have received a copy of the GNU General Public License version 1729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2 along with this work; if not, write to the Free Software Foundation, 1829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 2029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2129957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * or visit www.oracle.com if you need additional information or have any 2229957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * questions. 2329957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer */ 2429957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer 2529957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer/* 2629957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * This file is available under and governed by the GNU General Public 2729957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * License version 2 only, as published by the Free Software Foundation. 2829957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * However, the following notice accompanied the original version of this 2929957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * file: 3029957558cf0db700bfaae360a80c42dc3871d0e5Tobias Thierer * 31b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Written by Doug Lea with assistance from members of JCP JSR-166 32b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Expert Group and released to the public domain, as explained at 33b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * http://creativecommons.org/publicdomain/zero/1.0/ 34b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 35b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 36b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakpackage java.util.concurrent.atomic; 37b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 38b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.Arrays; 39b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.concurrent.ThreadLocalRandom; 40b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.function.DoubleBinaryOperator; 41b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakimport java.util.function.LongBinaryOperator; 42b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 43b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak/** 44b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * A package-local class holding common representation and mechanics 45b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * for classes supporting dynamic striping on 64bit values. The class 46b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * extends Number so that concrete subclasses must publicly do so. 47b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 48b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak@SuppressWarnings("serial") 49b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniakabstract class Striped64 extends Number { 50b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /* 51b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * This class maintains a lazily-initialized table of atomically 52b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * updated variables, plus an extra "base" field. The table size 53b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * is a power of two. Indexing uses masked per-thread hash codes. 54b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Nearly all declarations in this class are package-private, 55b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * accessed directly by subclasses. 56b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 57b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Table entries are of class Cell; a variant of AtomicLong padded 58b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * (via @Contended) to reduce cache contention. Padding is 59b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * overkill for most Atomics because they are usually irregularly 60b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * scattered in memory and thus don't interfere much with each 61b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * other. But Atomic objects residing in arrays will tend to be 62b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * placed adjacent to each other, and so will most often share 63b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * cache lines (with a huge negative performance impact) without 64b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * this precaution. 65b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 66b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * In part because Cells are relatively large, we avoid creating 67b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * them until they are needed. When there is no contention, all 68b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * updates are made to the base field. Upon first contention (a 69b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * failed CAS on base update), the table is initialized to size 2. 70b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * The table size is doubled upon further contention until 71b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * reaching the nearest power of two greater than or equal to the 72b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * number of CPUS. Table slots remain empty (null) until they are 73b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * needed. 74b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 75b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * A single spinlock ("cellsBusy") is used for initializing and 76b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * resizing the table, as well as populating slots with new Cells. 77b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * There is no need for a blocking lock; when the lock is not 78b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * available, threads try other slots (or the base). During these 79b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * retries, there is increased contention and reduced locality, 80b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * which is still better than alternatives. 81b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 82b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * The Thread probe fields maintained via ThreadLocalRandom serve 83b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * as per-thread hash codes. We let them remain uninitialized as 84b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * zero (if they come in this way) until they contend at slot 85b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 0. They are then initialized to values that typically do not 86b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * often conflict with others. Contention and/or table collisions 87b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * are indicated by failed CASes when performing an update 88b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * operation. Upon a collision, if the table size is less than 89b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * the capacity, it is doubled in size unless some other thread 90b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * holds the lock. If a hashed slot is empty, and lock is 91b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * available, a new Cell is created. Otherwise, if the slot 92b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * exists, a CAS is tried. Retries proceed by "double hashing", 93b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * using a secondary hash (Marsaglia XorShift) to try to find a 94b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * free slot. 95b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 96b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * The table size is capped because, when there are more threads 97b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * than CPUs, supposing that each thread were bound to a CPU, 98b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * there would exist a perfect hash function mapping threads to 99b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * slots that eliminates collisions. When we reach capacity, we 100b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * search for this mapping by randomly varying the hash codes of 101b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * colliding threads. Because search is random, and collisions 102b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * only become known via CAS failures, convergence can be slow, 103b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * and because threads are typically not bound to CPUS forever, 104b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * may not occur at all. However, despite these limitations, 105b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * observed contention rates are typically low in these cases. 106b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 107b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * It is possible for a Cell to become unused when threads that 108b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * once hashed to it terminate, as well as in the case where 109b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * doubling the table causes no thread to hash to it under 110b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * expanded mask. We do not try to detect or remove such cells, 111b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * under the assumption that for long-running instances, observed 112b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * contention levels will recur, so the cells will eventually be 113b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * needed again; and for short-lived ones, it does not matter. 114b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 115b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 116b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 117b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Padded variant of AtomicLong supporting only raw accesses plus CAS. 118b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 119b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * JVM intrinsics note: It would be possible to use a release-only 120b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * form of CAS here, if it were provided. 121b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 1226975f84c2ed72e1e26d20190b6f318718c849008Tobias Thierer // @jdk.internal.vm.annotation.Contended // Android-removed 123b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final class Cell { 124b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak volatile long value; 125b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Cell(long x) { value = x; } 126b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final boolean cas(long cmp, long val) { 127b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapLong(this, VALUE, cmp, val); 128b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 129b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final void reset() { 130b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putLongVolatile(this, VALUE, 0L); 131b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 132b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final void reset(long identity) { 133b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putLongVolatile(this, VALUE, identity); 134b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 135b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 136b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // Unsafe mechanics 137b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 138b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long VALUE; 139b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static { 140b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak try { 141b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak VALUE = U.objectFieldOffset 142b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Cell.class.getDeclaredField("value")); 143b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 144b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new Error(e); 145b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 146b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 147b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 148b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 149b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** Number of CPUS, to place bound on table size */ 150b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final int NCPU = Runtime.getRuntime().availableProcessors(); 151b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 152b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 153b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Table of cells. When non-null, size is a power of 2. 154b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 155b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak transient volatile Cell[] cells; 156b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 157b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 158b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Base value, used mainly when there is no contention, but also as 159b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * a fallback during table initialization races. Updated via CAS. 160b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 161b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak transient volatile long base; 162b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 163b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 164b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Spinlock (locked via CAS) used when resizing and/or creating Cells. 165b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 166b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak transient volatile int cellsBusy; 167b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 168b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 169b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Package-private default constructor. 170b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 171b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Striped64() { 172b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 173b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 174b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 175b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * CASes the base field. 176b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 177b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final boolean casBase(long cmp, long val) { 178b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapLong(this, BASE, cmp, val); 179b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 180b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 181b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 182b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * CASes the cellsBusy field from 0 to 1 to acquire lock. 183b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 184b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final boolean casCellsBusy() { 185b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapInt(this, CELLSBUSY, 0, 1); 186b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 187b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 188b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 189b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Returns the probe value for the current thread. 190b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Duplicated from ThreadLocalRandom because of packaging restrictions. 191b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 192b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final int getProbe() { 193b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.getInt(Thread.currentThread(), PROBE); 194b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 195b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 196b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 197b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Pseudo-randomly advances and records the given probe value for the 198b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * given thread. 199b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Duplicated from ThreadLocalRandom because of packaging restrictions. 200b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 201b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static final int advanceProbe(int probe) { 202b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak probe ^= probe << 13; // xorshift 203b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak probe ^= probe >>> 17; 204b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak probe ^= probe << 5; 205b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak U.putInt(Thread.currentThread(), PROBE, probe); 206b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return probe; 207b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 208b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 209b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 210b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Handles cases of updates involving initialization, resizing, 211b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * creating new Cells, and/or contention. See above for 212b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * explanation. This method suffers the usual non-modularity 213b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * problems of optimistic retry code, relying on rechecked sets of 214b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * reads. 215b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * 216b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @param x the value 217b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @param fn the update function, or null for add (this convention 218b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * avoids the need for an extra field or function in LongAdder). 219b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @param wasUncontended false if CAS failed before call 220b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 221b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final void longAccumulate(long x, LongBinaryOperator fn, 222b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak boolean wasUncontended) { 223b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int h; 224b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((h = getProbe()) == 0) { 225b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ThreadLocalRandom.current(); // force initialization 226b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak h = getProbe(); 227b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak wasUncontended = true; 228b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 229b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak boolean collide = false; // True if last slot nonempty 230b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak done: for (;;) { 231b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Cell[] as; Cell a; int n; long v; 232b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((as = cells) != null && (n = as.length) > 0) { 233b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((a = as[(n - 1) & h]) == null) { 234b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (cellsBusy == 0) { // Try to attach new Cell 235b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Cell r = new Cell(x); // Optimistically create 236b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (cellsBusy == 0 && casCellsBusy()) { 237b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak try { // Recheck under lock 238b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Cell[] rs; int m, j; 239b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((rs = cells) != null && 240b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (m = rs.length) > 0 && 241b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rs[j = (m - 1) & h] == null) { 242b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rs[j] = r; 243b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break done; 244b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 245b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } finally { 246b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cellsBusy = 0; 247b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 248b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue; // Slot is now non-empty 249b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 250b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 251b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak collide = false; 252b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 253b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (!wasUncontended) // CAS already known to fail 254b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak wasUncontended = true; // Continue after rehash 255b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (a.cas(v = a.value, 256b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (fn == null) ? v + x : fn.applyAsLong(v, x))) 257b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 258b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (n >= NCPU || cells != as) 259b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak collide = false; // At max size or stale 260b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (!collide) 261b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak collide = true; 262b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (cellsBusy == 0 && casCellsBusy()) { 263b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak try { 264b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (cells == as) // Expand table unless stale 265b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cells = Arrays.copyOf(as, n << 1); 266b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } finally { 267b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cellsBusy = 0; 268b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 269b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak collide = false; 270b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue; // Retry with expanded table 271b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 272b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak h = advanceProbe(h); 273b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 274b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (cellsBusy == 0 && cells == as && casCellsBusy()) { 275b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak try { // Initialize table 276b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (cells == as) { 277b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Cell[] rs = new Cell[2]; 278b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rs[h & 1] = new Cell(x); 279b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cells = rs; 280b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break done; 281b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 282b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } finally { 283b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cellsBusy = 0; 284b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 285b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 286b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // Fall back on using base 287b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (casBase(v = base, 288b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (fn == null) ? v + x : fn.applyAsLong(v, x))) 289b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break done; 290b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 291b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 292b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 293b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static long apply(DoubleBinaryOperator fn, long v, double x) { 294b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak double d = Double.longBitsToDouble(v); 295b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak d = (fn == null) ? d + x : fn.applyAsDouble(d, x); 296b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return Double.doubleToRawLongBits(d); 297b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 298b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 299b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak /** 300b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * Same as longAccumulate, but injecting long/double conversions 301b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * in too many places to sensibly merge with long version, given 302b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * the low-overhead requirements of this class. So must instead be 303b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * maintained by copy/paste/adapt. 304b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak */ 305b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak final void doubleAccumulate(double x, DoubleBinaryOperator fn, 306b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak boolean wasUncontended) { 307b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak int h; 308b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((h = getProbe()) == 0) { 309b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak ThreadLocalRandom.current(); // force initialization 310b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak h = getProbe(); 311b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak wasUncontended = true; 312b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 313b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak boolean collide = false; // True if last slot nonempty 314b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak done: for (;;) { 315b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Cell[] as; Cell a; int n; long v; 316b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((as = cells) != null && (n = as.length) > 0) { 317b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((a = as[(n - 1) & h]) == null) { 318b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (cellsBusy == 0) { // Try to attach new Cell 319b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Cell r = new Cell(Double.doubleToRawLongBits(x)); 320b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (cellsBusy == 0 && casCellsBusy()) { 321b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak try { // Recheck under lock 322b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Cell[] rs; int m, j; 323b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if ((rs = cells) != null && 324b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (m = rs.length) > 0 && 325b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rs[j = (m - 1) & h] == null) { 326b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rs[j] = r; 327b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break done; 328b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 329b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } finally { 330b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cellsBusy = 0; 331b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 332b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue; // Slot is now non-empty 333b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 334b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 335b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak collide = false; 336b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 337b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (!wasUncontended) // CAS already known to fail 338b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak wasUncontended = true; // Continue after rehash 339b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (a.cas(v = a.value, apply(fn, v, x))) 340b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break; 341b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (n >= NCPU || cells != as) 342b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak collide = false; // At max size or stale 343b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (!collide) 344b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak collide = true; 345b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (cellsBusy == 0 && casCellsBusy()) { 346b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak try { 347b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (cells == as) // Expand table unless stale 348b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cells = Arrays.copyOf(as, n << 1); 349b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } finally { 350b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cellsBusy = 0; 351b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 352b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak collide = false; 353b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak continue; // Retry with expanded table 354b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 355b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak h = advanceProbe(h); 356b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 357b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (cellsBusy == 0 && cells == as && casCellsBusy()) { 358b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak try { // Initialize table 359b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak if (cells == as) { 360b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak Cell[] rs = new Cell[2]; 361b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak rs[h & 1] = new Cell(Double.doubleToRawLongBits(x)); 362b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cells = rs; 363b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break done; 364b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 365b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } finally { 366b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak cellsBusy = 0; 367b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 368b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 369b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // Fall back on using base 370b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak else if (casBase(v = base, apply(fn, v, x))) 371b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak break done; 372b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 373b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 374b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 375b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak // Unsafe mechanics 376b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 377b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long BASE; 378b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long CELLSBUSY; 379b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long PROBE; 380b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static { 381b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak try { 382b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak BASE = U.objectFieldOffset 383b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Striped64.class.getDeclaredField("base")); 384b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak CELLSBUSY = U.objectFieldOffset 385b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Striped64.class.getDeclaredField("cellsBusy")); 386b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 387b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak PROBE = U.objectFieldOffset 388b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (Thread.class.getDeclaredField("threadLocalRandomProbe")); 389b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 390b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new Error(e); 391b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 392b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 393b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 394b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak} 395