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
7package 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 */
21public class AtomicMarkableReference<V> {
22
23    private static class Pair<T> {
24        final T reference;
25        final boolean mark;
26        private Pair(T reference, boolean mark) {
27            this.reference = reference;
28            this.mark = mark;
29        }
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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     */
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
168    private boolean casPair(Pair<V> cmp, Pair<V> val) {
169        return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
170    }
171
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