1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 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 * 31adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Written by Doug Lea with assistance from members of JCP JSR-166 32adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Expert Group and released to the public domain, as explained at 33a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 35adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util.concurrent.atomic; 37adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 38adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 39bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * An {@code AtomicMarkableReference} maintains an object reference 40adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * along with a mark bit, that can be updated atomically. 418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>Implementation note: This implementation maintains markable 43adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * references by creating internal objects representing "boxed" 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * [reference, boolean] pairs. 45adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 47adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 48adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param <V> The type of object referred to by this reference 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilsonpublic class AtomicMarkableReference<V> { 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static class Pair<T> { 538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final T reference; 548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final boolean mark; 558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private Pair(T reference, boolean mark) { 568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.reference = reference; 578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.mark = mark; 588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson static <T> Pair<T> of(T reference, boolean mark) { 608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return new Pair<T>(reference, mark); 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private volatile Pair<V> pair; 65adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 66adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 67bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Creates a new {@code AtomicMarkableReference} with the given 68adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * initial values. 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param initialRef the initial reference 71adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param initialMark the initial mark 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public AtomicMarkableReference(V initialRef, boolean initialMark) { 748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson pair = Pair.of(initialRef, initialMark); 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 77adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the current value of the reference. 79adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the current value of the reference 81adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V getReference() { 838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return pair.reference; 84adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the current value of the mark. 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the current value of the mark 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean isMarked() { 928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return pair.mark; 93adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 94adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 95adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 96adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the current values of both the reference and the mark. 97bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Typical usage is {@code boolean[1] holder; ref = v.get(holder); }. 98adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param markHolder an array of size of at least one. On return, 100edf43d27e240d82106f39ae91404963c23987234Narayan Kamath * {@code markHolder[0]} will hold the value of the mark. 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the current value of the reference 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V get(boolean[] markHolder) { 1048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Pair<V> pair = this.pair; 1058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson markHolder[0] = pair.mark; 1068eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return pair.reference; 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Atomically sets the value of both the reference and mark 111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * to the given update values if the 112bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * current reference is {@code ==} to the expected reference 113bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and the current mark is equal to the expected mark. 114bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 11591770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p><a href="package-summary.html#weakCompareAndSet">May fail 11691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * spuriously and does not provide ordering guarantees</a>, so is 11791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * only rarely an appropriate alternative to {@code compareAndSet}. 118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedReference the expected value of the reference 120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newReference the new value for the reference 121adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedMark the expected value of the mark 122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newMark the new value for the mark 123b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @return {@code true} if successful 124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean weakCompareAndSet(V expectedReference, 126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project V newReference, 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean expectedMark, 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean newMark) { 1298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return compareAndSet(expectedReference, newReference, 1308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson expectedMark, newMark); 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Atomically sets the value of both the reference and mark 135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * to the given update values if the 136bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * current reference is {@code ==} to the expected reference 137bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and the current mark is equal to the expected mark. 138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedReference the expected value of the reference 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newReference the new value for the reference 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedMark the expected value of the mark 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newMark the new value for the mark 143b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @return {@code true} if successful 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean compareAndSet(V expectedReference, 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project V newReference, 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean expectedMark, 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean newMark) { 1498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Pair<V> current = pair; 1508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return 1518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson expectedReference == current.reference && 1528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson expectedMark == current.mark && 1538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson ((newReference == current.reference && 1548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson newMark == current.mark) || 1558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson casPair(current, Pair.of(newReference, newMark))); 156adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 158adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 159adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unconditionally sets the value of both the reference and mark. 160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newReference the new value for the reference 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newMark the new value for the mark 163adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void set(V newReference, boolean newMark) { 1658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Pair<V> current = pair; 1668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newReference != current.reference || newMark != current.mark) 1678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.pair = Pair.of(newReference, newMark); 168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Atomically sets the value of the mark to the given update value 172bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * if the current reference is {@code ==} to the expected 173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * reference. Any given invocation of this operation may fail 174bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (return {@code false}) spuriously, but repeated invocation 175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * when the current value holds the expected value and no other 176adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * thread is also attempting to set the value will eventually 177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * succeed. 178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedReference the expected value of the reference 180adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newMark the new value for the mark 181b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak * @return {@code true} if successful 182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean attemptMark(V expectedReference, boolean newMark) { 1848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Pair<V> current = pair; 1858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return 1868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson expectedReference == current.reference && 1878eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson (newMark == current.mark || 1888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson casPair(current, Pair.of(expectedReference, newMark))); 1898eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Unsafe mechanics 1928eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 193b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 194b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private static final long PAIR; 195b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak static { 196ed4f365789d43b1961657195df223a19bf4ef20fPrzemyslaw Szczepaniak try { 197b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak PAIR = U.objectFieldOffset 198b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak (AtomicMarkableReference.class.getDeclaredField("pair")); 199b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 200b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak throw new Error(e); 201ed4f365789d43b1961657195df223a19bf4ef20fPrzemyslaw Szczepaniak } 2025328e07d282bef36ac8b757bbee16a761415b2c4Przemyslaw Szczepaniak } 203b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak 204b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak private boolean casPair(Pair<V> cmp, Pair<V> val) { 205b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak return U.compareAndSwapObject(this, PAIR, cmp, val); 206b8b75116273ecfdb8ffdd1869b1c0dd04570a95ePrzemyslaw Szczepaniak } 207adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 208