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 import java.lang.reflect.Array;
10 import java.util.Arrays;
11 import java.util.function.BinaryOperator;
12 import java.util.function.UnaryOperator;
13 
14 /**
15  * An array of object references in which elements may be updated
16  * atomically.  See the {@link java.util.concurrent.atomic} package
17  * specification for description of the properties of atomic
18  * variables.
19  * @since 1.5
20  * @author Doug Lea
21  * @param <E> The base class of elements held in this array
22  */
23 public class AtomicReferenceArray<E> implements java.io.Serializable {
24     private static final long serialVersionUID = -6209656149925076980L;
25 
26     private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
27     private static final long ARRAY;
28     private static final int ABASE;
29     private static final int ASHIFT;
30     private final Object[] array; // must have exact type Object[]
31 
32     static {
33         try {
34             ARRAY = U.objectFieldOffset
35                 (AtomicReferenceArray.class.getDeclaredField("array"));
36             ABASE = U.arrayBaseOffset(Object[].class);
37             int scale = U.arrayIndexScale(Object[].class);
38             if ((scale & (scale - 1)) != 0)
39                 throw new Error("array index scale not a power of two");
40             ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
41         } catch (ReflectiveOperationException e) {
42             throw new Error(e);
43         }
44     }
45 
checkedByteOffset(int i)46     private long checkedByteOffset(int i) {
47         if (i < 0 || i >= array.length)
48             throw new IndexOutOfBoundsException("index " + i);
49 
50         return byteOffset(i);
51     }
52 
byteOffset(int i)53     private static long byteOffset(int i) {
54         return ((long) i << ASHIFT) + ABASE;
55     }
56 
57     /**
58      * Creates a new AtomicReferenceArray of the given length, with all
59      * elements initially null.
60      *
61      * @param length the length of the array
62      */
AtomicReferenceArray(int length)63     public AtomicReferenceArray(int length) {
64         array = new Object[length];
65     }
66 
67     /**
68      * Creates a new AtomicReferenceArray with the same length as, and
69      * all elements copied from, the given array.
70      *
71      * @param array the array to copy elements from
72      * @throws NullPointerException if array is null
73      */
AtomicReferenceArray(E[] array)74     public AtomicReferenceArray(E[] array) {
75         // Visibility guaranteed by final field guarantees
76         this.array = Arrays.copyOf(array, array.length, Object[].class);
77     }
78 
79     /**
80      * Returns the length of the array.
81      *
82      * @return the length of the array
83      */
length()84     public final int length() {
85         return array.length;
86     }
87 
88     /**
89      * Gets the current value at position {@code i}.
90      *
91      * @param i the index
92      * @return the current value
93      */
get(int i)94     public final E get(int i) {
95         return getRaw(checkedByteOffset(i));
96     }
97 
98     @SuppressWarnings("unchecked")
getRaw(long offset)99     private E getRaw(long offset) {
100         return (E) U.getObjectVolatile(array, offset);
101     }
102 
103     /**
104      * Sets the element at position {@code i} to the given value.
105      *
106      * @param i the index
107      * @param newValue the new value
108      */
set(int i, E newValue)109     public final void set(int i, E newValue) {
110         U.putObjectVolatile(array, checkedByteOffset(i), newValue);
111     }
112 
113     /**
114      * Eventually sets the element at position {@code i} to the given value.
115      *
116      * @param i the index
117      * @param newValue the new value
118      * @since 1.6
119      */
lazySet(int i, E newValue)120     public final void lazySet(int i, E newValue) {
121         U.putOrderedObject(array, checkedByteOffset(i), newValue);
122     }
123 
124     /**
125      * Atomically sets the element at position {@code i} to the given
126      * value and returns the old value.
127      *
128      * @param i the index
129      * @param newValue the new value
130      * @return the previous value
131      */
132     @SuppressWarnings("unchecked")
getAndSet(int i, E newValue)133     public final E getAndSet(int i, E newValue) {
134         return (E)U.getAndSetObject(array, checkedByteOffset(i), newValue);
135     }
136 
137     /**
138      * Atomically sets the element at position {@code i} to the given
139      * updated value if the current value {@code ==} the expected value.
140      *
141      * @param i the index
142      * @param expect the expected value
143      * @param update the new value
144      * @return {@code true} if successful. False return indicates that
145      * the actual value was not equal to the expected value.
146      */
compareAndSet(int i, E expect, E update)147     public final boolean compareAndSet(int i, E expect, E update) {
148         return compareAndSetRaw(checkedByteOffset(i), expect, update);
149     }
150 
compareAndSetRaw(long offset, E expect, E update)151     private boolean compareAndSetRaw(long offset, E expect, E update) {
152         return U.compareAndSwapObject(array, offset, expect, update);
153     }
154 
155     /**
156      * Atomically sets the element at position {@code i} to the given
157      * updated value if the current value {@code ==} the expected value.
158      *
159      * <p><a href="package-summary.html#weakCompareAndSet">May fail
160      * spuriously and does not provide ordering guarantees</a>, so is
161      * only rarely an appropriate alternative to {@code compareAndSet}.
162      *
163      * @param i the index
164      * @param expect the expected value
165      * @param update the new value
166      * @return {@code true} if successful
167      */
weakCompareAndSet(int i, E expect, E update)168     public final boolean weakCompareAndSet(int i, E expect, E update) {
169         return compareAndSet(i, expect, update);
170     }
171 
172     /**
173      * Atomically updates the element at index {@code i} with the results
174      * of applying the given function, returning the previous value. The
175      * function should be side-effect-free, since it may be re-applied
176      * when attempted updates fail due to contention among threads.
177      *
178      * @param i the index
179      * @param updateFunction a side-effect-free function
180      * @return the previous value
181      * @since 1.8
182      */
getAndUpdate(int i, UnaryOperator<E> updateFunction)183     public final E getAndUpdate(int i, UnaryOperator<E> updateFunction) {
184         long offset = checkedByteOffset(i);
185         E prev, next;
186         do {
187             prev = getRaw(offset);
188             next = updateFunction.apply(prev);
189         } while (!compareAndSetRaw(offset, prev, next));
190         return prev;
191     }
192 
193     /**
194      * Atomically updates the element at index {@code i} with the results
195      * of applying the given function, returning the updated value. The
196      * function should be side-effect-free, since it may be re-applied
197      * when attempted updates fail due to contention among threads.
198      *
199      * @param i the index
200      * @param updateFunction a side-effect-free function
201      * @return the updated value
202      * @since 1.8
203      */
updateAndGet(int i, UnaryOperator<E> updateFunction)204     public final E updateAndGet(int i, UnaryOperator<E> updateFunction) {
205         long offset = checkedByteOffset(i);
206         E prev, next;
207         do {
208             prev = getRaw(offset);
209             next = updateFunction.apply(prev);
210         } while (!compareAndSetRaw(offset, prev, next));
211         return next;
212     }
213 
214     /**
215      * Atomically updates the element at index {@code i} with the
216      * results of applying the given function to the current and
217      * given values, returning the previous value. The function should
218      * be side-effect-free, since it may be re-applied when attempted
219      * updates fail due to contention among threads.  The function is
220      * applied with the current value at index {@code i} as its first
221      * argument, and the given update as the second argument.
222      *
223      * @param i the index
224      * @param x the update value
225      * @param accumulatorFunction a side-effect-free function of two arguments
226      * @return the previous value
227      * @since 1.8
228      */
getAndAccumulate(int i, E x, BinaryOperator<E> accumulatorFunction)229     public final E getAndAccumulate(int i, E x,
230                                     BinaryOperator<E> accumulatorFunction) {
231         long offset = checkedByteOffset(i);
232         E prev, next;
233         do {
234             prev = getRaw(offset);
235             next = accumulatorFunction.apply(prev, x);
236         } while (!compareAndSetRaw(offset, prev, next));
237         return prev;
238     }
239 
240     /**
241      * Atomically updates the element at index {@code i} with the
242      * results of applying the given function to the current and
243      * given values, returning the updated value. The function should
244      * be side-effect-free, since it may be re-applied when attempted
245      * updates fail due to contention among threads.  The function is
246      * applied with the current value at index {@code i} as its first
247      * argument, and the given update as the second argument.
248      *
249      * @param i the index
250      * @param x the update value
251      * @param accumulatorFunction a side-effect-free function of two arguments
252      * @return the updated value
253      * @since 1.8
254      */
accumulateAndGet(int i, E x, BinaryOperator<E> accumulatorFunction)255     public final E accumulateAndGet(int i, E x,
256                                     BinaryOperator<E> accumulatorFunction) {
257         long offset = checkedByteOffset(i);
258         E prev, next;
259         do {
260             prev = getRaw(offset);
261             next = accumulatorFunction.apply(prev, x);
262         } while (!compareAndSetRaw(offset, prev, next));
263         return next;
264     }
265 
266     /**
267      * Returns the String representation of the current values of array.
268      * @return the String representation of the current values of array
269      */
toString()270     public String toString() {
271         int iMax = array.length - 1;
272         if (iMax == -1)
273             return "[]";
274 
275         StringBuilder b = new StringBuilder();
276         b.append('[');
277         for (int i = 0; ; i++) {
278             b.append(getRaw(byteOffset(i)));
279             if (i == iMax)
280                 return b.append(']').toString();
281             b.append(',').append(' ');
282         }
283     }
284 
285     /**
286      * Reconstitutes the instance from a stream (that is, deserializes it).
287      * @param s the stream
288      * @throws ClassNotFoundException if the class of a serialized object
289      *         could not be found
290      * @throws java.io.IOException if an I/O error occurs
291      */
readObject(java.io.ObjectInputStream s)292     private void readObject(java.io.ObjectInputStream s)
293         throws java.io.IOException, ClassNotFoundException {
294         // Note: This must be changed if any additional fields are defined
295         Object a = s.readFields().get("array", null);
296         if (a == null || !a.getClass().isArray())
297             throw new java.io.InvalidObjectException("Not array type");
298         if (a.getClass() != Object[].class)
299             a = Arrays.copyOf((Object[])a, Array.getLength(a), Object[].class);
300         U.putObjectVolatile(this, ARRAY, a);
301     }
302 
303 }
304