1 /*
2  * Written by Doug Lea with assistance from members of JCP JSR-166
3  * Expert Group and released to the public domain, as explained at
4  * http://creativecommons.org/publicdomain/zero/1.0/
5  */
6 
7 package java.util.concurrent.atomic;
8 
9 /**
10  * An {@code AtomicMarkableReference} maintains an object reference
11  * along with a mark bit, that can be updated atomically.
12  *
13  * <p>Implementation note: This implementation maintains markable
14  * references by creating internal objects representing "boxed"
15  * [reference, boolean] pairs.
16  *
17  * @since 1.5
18  * @author Doug Lea
19  * @param <V> The type of object referred to by this reference
20  */
21 public class AtomicMarkableReference<V> {
22 
23     private static class Pair<T> {
24         final T reference;
25         final boolean mark;
Pair(T reference, boolean mark)26         private Pair(T reference, boolean mark) {
27             this.reference = reference;
28             this.mark = mark;
29         }
of(T reference, boolean mark)30         static <T> Pair<T> of(T reference, boolean mark) {
31             return new Pair<T>(reference, mark);
32         }
33     }
34 
35     private volatile Pair<V> pair;
36 
37     /**
38      * Creates a new {@code AtomicMarkableReference} with the given
39      * initial values.
40      *
41      * @param initialRef the initial reference
42      * @param initialMark the initial mark
43      */
AtomicMarkableReference(V initialRef, boolean initialMark)44     public AtomicMarkableReference(V initialRef, boolean initialMark) {
45         pair = Pair.of(initialRef, initialMark);
46     }
47 
48     /**
49      * Returns the current value of the reference.
50      *
51      * @return the current value of the reference
52      */
getReference()53     public V getReference() {
54         return pair.reference;
55     }
56 
57     /**
58      * Returns the current value of the mark.
59      *
60      * @return the current value of the mark
61      */
isMarked()62     public boolean isMarked() {
63         return pair.mark;
64     }
65 
66     /**
67      * Returns the current values of both the reference and the mark.
68      * Typical usage is {@code boolean[1] holder; ref = v.get(holder); }.
69      *
70      * @param markHolder an array of size of at least one. On return,
71      * {@code markholder[0]} will hold the value of the mark.
72      * @return the current value of the reference
73      */
get(boolean[] markHolder)74     public V get(boolean[] markHolder) {
75         Pair<V> pair = this.pair;
76         markHolder[0] = pair.mark;
77         return pair.reference;
78     }
79 
80     /**
81      * Atomically sets the value of both the reference and mark
82      * to the given update values if the
83      * current reference is {@code ==} to the expected reference
84      * and the current mark is equal to the expected mark.
85      *
86      * <p><a href="package-summary.html#weakCompareAndSet">May fail
87      * spuriously and does not provide ordering guarantees</a>, so is
88      * only rarely an appropriate alternative to {@code compareAndSet}.
89      *
90      * @param expectedReference the expected value of the reference
91      * @param newReference the new value for the reference
92      * @param expectedMark the expected value of the mark
93      * @param newMark the new value for the mark
94      * @return true if successful
95      */
weakCompareAndSet(V expectedReference, V newReference, boolean expectedMark, boolean newMark)96     public boolean weakCompareAndSet(V       expectedReference,
97                                      V       newReference,
98                                      boolean expectedMark,
99                                      boolean newMark) {
100         return compareAndSet(expectedReference, newReference,
101                              expectedMark, newMark);
102     }
103 
104     /**
105      * Atomically sets the value of both the reference and mark
106      * to the given update values if the
107      * current reference is {@code ==} to the expected reference
108      * and the current mark is equal to the expected mark.
109      *
110      * @param expectedReference the expected value of the reference
111      * @param newReference the new value for the reference
112      * @param expectedMark the expected value of the mark
113      * @param newMark the new value for the mark
114      * @return true if successful
115      */
compareAndSet(V expectedReference, V newReference, boolean expectedMark, boolean newMark)116     public boolean compareAndSet(V       expectedReference,
117                                  V       newReference,
118                                  boolean expectedMark,
119                                  boolean newMark) {
120         Pair<V> current = pair;
121         return
122             expectedReference == current.reference &&
123             expectedMark == current.mark &&
124             ((newReference == current.reference &&
125               newMark == current.mark) ||
126              casPair(current, Pair.of(newReference, newMark)));
127     }
128 
129     /**
130      * Unconditionally sets the value of both the reference and mark.
131      *
132      * @param newReference the new value for the reference
133      * @param newMark the new value for the mark
134      */
set(V newReference, boolean newMark)135     public void set(V newReference, boolean newMark) {
136         Pair<V> current = pair;
137         if (newReference != current.reference || newMark != current.mark)
138             this.pair = Pair.of(newReference, newMark);
139     }
140 
141     /**
142      * Atomically sets the value of the mark to the given update value
143      * if the current reference is {@code ==} to the expected
144      * reference.  Any given invocation of this operation may fail
145      * (return {@code false}) spuriously, but repeated invocation
146      * when the current value holds the expected value and no other
147      * thread is also attempting to set the value will eventually
148      * succeed.
149      *
150      * @param expectedReference the expected value of the reference
151      * @param newMark the new value for the mark
152      * @return true if successful
153      */
attemptMark(V expectedReference, boolean newMark)154     public boolean attemptMark(V expectedReference, boolean newMark) {
155         Pair<V> current = pair;
156         return
157             expectedReference == current.reference &&
158             (newMark == current.mark ||
159              casPair(current, Pair.of(expectedReference, newMark)));
160     }
161 
162     // Unsafe mechanics
163 
164     private static final sun.misc.Unsafe UNSAFE = sun.misc.Unsafe.getUnsafe();
165     private static final long pairOffset =
166         objectFieldOffset(UNSAFE, "pair", AtomicMarkableReference.class);
167 
casPair(Pair<V> cmp, Pair<V> val)168     private boolean casPair(Pair<V> cmp, Pair<V> val) {
169         return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
170     }
171 
objectFieldOffset(sun.misc.Unsafe UNSAFE, String field, Class<?> klazz)172     static long objectFieldOffset(sun.misc.Unsafe UNSAFE,
173                                   String field, Class<?> klazz) {
174         try {
175             return UNSAFE.objectFieldOffset(klazz.getDeclaredField(field));
176         } catch (NoSuchFieldException e) {
177             // Convert Exception to corresponding Error
178             NoSuchFieldError error = new NoSuchFieldError(field);
179             error.initCause(e);
180             throw error;
181         }
182     }
183 }
184