1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Written by Doug Lea with assistance from members of JCP JSR-166 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Expert Group and released to the public domain, as explained at 4a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.util.concurrent.atomic; 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 9adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 10bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * An {@code AtomicMarkableReference} maintains an object reference 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * along with a mark bit, that can be updated atomically. 128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>Implementation note: This implementation maintains markable 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * references by creating internal objects representing "boxed" 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * [reference, boolean] pairs. 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @since 1.5 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @author Doug Lea 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param <V> The type of object referred to by this reference 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilsonpublic class AtomicMarkableReference<V> { 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static class Pair<T> { 248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final T reference; 258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson final boolean mark; 268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private Pair(T reference, boolean mark) { 278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.reference = reference; 288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.mark = mark; 298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson static <T> Pair<T> of(T reference, boolean mark) { 318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return new Pair<T>(reference, mark); 32adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 33adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 34adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private volatile Pair<V> pair; 36adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 37adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 38bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Creates a new {@code AtomicMarkableReference} with the given 39adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * initial values. 40adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 41adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param initialRef the initial reference 42adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param initialMark the initial mark 43adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public AtomicMarkableReference(V initialRef, boolean initialMark) { 458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson pair = Pair.of(initialRef, initialMark); 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 47adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 48adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 49adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the current value of the reference. 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 51adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the current value of the reference 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V getReference() { 548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return pair.reference; 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 56adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 57adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 58adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the current value of the mark. 59adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the current value of the mark 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean isMarked() { 638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return pair.mark; 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 65adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 66adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 67adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the current values of both the reference and the mark. 68bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * Typical usage is {@code boolean[1] holder; ref = v.get(holder); }. 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param markHolder an array of size of at least one. On return, 71bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * {@code markholder[0]} will hold the value of the mark. 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the current value of the reference 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public V get(boolean[] markHolder) { 758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Pair<V> pair = this.pair; 768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson markHolder[0] = pair.mark; 778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return pair.reference; 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 79adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 81adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Atomically sets the value of both the reference and mark 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * to the given update values if the 83bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * current reference is {@code ==} to the expected reference 84bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and the current mark is equal to the expected mark. 85bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * 8691770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p><a href="package-summary.html#weakCompareAndSet">May fail 8791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * spuriously and does not provide ordering guarantees</a>, so is 8891770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * only rarely an appropriate alternative to {@code compareAndSet}. 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 90adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedReference the expected value of the reference 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newReference the new value for the reference 92adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedMark the expected value of the mark 93adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newMark the new value for the mark 94adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return true if successful 95adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 96adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean weakCompareAndSet(V expectedReference, 97adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project V newReference, 98adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean expectedMark, 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean newMark) { 1008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return compareAndSet(expectedReference, newReference, 1018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson expectedMark, newMark); 102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Atomically sets the value of both the reference and mark 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * to the given update values if the 107bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * current reference is {@code ==} to the expected reference 108bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * and the current mark is equal to the expected mark. 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedReference the expected value of the reference 111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newReference the new value for the reference 112adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedMark the expected value of the mark 113adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newMark the new value for the mark 114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return true if successful 115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean compareAndSet(V expectedReference, 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project V newReference, 118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean expectedMark, 119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project boolean newMark) { 1208eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Pair<V> current = pair; 1218eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return 1228eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson expectedReference == current.reference && 1238eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson expectedMark == current.mark && 1248eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson ((newReference == current.reference && 1258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson newMark == current.mark) || 1268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson casPair(current, Pair.of(newReference, newMark))); 127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unconditionally sets the value of both the reference and mark. 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newReference the new value for the reference 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newMark the new value for the mark 134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 135adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public void set(V newReference, boolean newMark) { 1368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Pair<V> current = pair; 1378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (newReference != current.reference || newMark != current.mark) 1388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson this.pair = Pair.of(newReference, newMark); 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 140adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Atomically sets the value of the mark to the given update value 143bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * if the current reference is {@code ==} to the expected 144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * reference. Any given invocation of this operation may fail 145bba8d1acd6dfff06c94d761c67a30154ca5ca5dfJesse Wilson * (return {@code false}) spuriously, but repeated invocation 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * when the current value holds the expected value and no other 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * thread is also attempting to set the value will eventually 148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * succeed. 149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 150adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param expectedReference the expected value of the reference 151adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @param newMark the new value for the mark 152adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return true if successful 153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean attemptMark(V expectedReference, boolean newMark) { 1558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Pair<V> current = pair; 1568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return 1578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson expectedReference == current.reference && 1588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson (newMark == current.mark || 1598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson casPair(current, Pair.of(expectedReference, newMark))); 1608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Unsafe mechanics 1638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 164a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe(); 1658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private static final long pairOffset = 1668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson objectFieldOffset(UNSAFE, "pair", AtomicMarkableReference.class); 1678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private boolean casPair(Pair<V> cmp, Pair<V> val) { 1698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val); 1708eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 1718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 1728eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson static long objectFieldOffset(sun.misc.Unsafe UNSAFE, 1738eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson String field, Class<?> klazz) { 1748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson try { 1758eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field)); 1768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } catch (NoSuchFieldException e) { 1778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Convert Exception to corresponding Error 1788eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson NoSuchFieldError error = new NoSuchFieldError(field); 1798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson error.initCause(e); 1808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson throw error; 1818eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 184