1 /*
2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3  *
4  * This code is free software; you can redistribute it and/or modify it
5  * under the terms of the GNU General Public License version 2 only, as
6  * published by the Free Software Foundation.  Oracle designates this
7  * particular file as subject to the "Classpath" exception as provided
8  * by Oracle in the LICENSE file that accompanied this code.
9  *
10  * This code is distributed in the hope that it will be useful, but WITHOUT
11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
13  * version 2 for more details (a copy is included in the LICENSE file that
14  * accompanied this code).
15  *
16  * You should have received a copy of the GNU General Public License version
17  * 2 along with this work; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19  *
20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21  * or visit www.oracle.com if you need additional information or have any
22  * questions.
23  */
24 
25 /*
26  * This file is available under and governed by the GNU General Public
27  * License version 2 only, as published by the Free Software Foundation.
28  * However, the following notice accompanied the original version of this
29  * file:
30  *
31  * Written by Doug Lea with assistance from members of JCP JSR-166
32  * Expert Group and released to the public domain, as explained at
33  * http://creativecommons.org/publicdomain/zero/1.0/
34  */
35 
36 package java.util.concurrent.atomic;
37 
38 import java.lang.reflect.Array;
39 import java.util.Arrays;
40 import java.util.function.BinaryOperator;
41 import java.util.function.UnaryOperator;
42 
43 /**
44  * An array of object references in which elements may be updated
45  * atomically.  See the {@link java.util.concurrent.atomic} package
46  * specification for description of the properties of atomic
47  * variables.
48  * @since 1.5
49  * @author Doug Lea
50  * @param <E> The base class of elements held in this array
51  */
52 public class AtomicReferenceArray<E> implements java.io.Serializable {
53     private static final long serialVersionUID = -6209656149925076980L;
54 
55     private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe();
56     private static final long ARRAY;
57     private static final int ABASE;
58     private static final int ASHIFT;
59     private final Object[] array; // must have exact type Object[]
60 
61     static {
62         try {
63             ARRAY = U.objectFieldOffset
64                 (AtomicReferenceArray.class.getDeclaredField("array"));
65             ABASE = U.arrayBaseOffset(Object[].class);
66             int scale = U.arrayIndexScale(Object[].class);
67             if ((scale & (scale - 1)) != 0)
68                 throw new Error("array index scale not a power of two");
69             ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
70         } catch (ReflectiveOperationException e) {
71             throw new Error(e);
72         }
73     }
74 
checkedByteOffset(int i)75     private long checkedByteOffset(int i) {
76         if (i < 0 || i >= array.length)
77             throw new IndexOutOfBoundsException("index " + i);
78 
79         return byteOffset(i);
80     }
81 
byteOffset(int i)82     private static long byteOffset(int i) {
83         return ((long) i << ASHIFT) + ABASE;
84     }
85 
86     /**
87      * Creates a new AtomicReferenceArray of the given length, with all
88      * elements initially null.
89      *
90      * @param length the length of the array
91      */
AtomicReferenceArray(int length)92     public AtomicReferenceArray(int length) {
93         array = new Object[length];
94     }
95 
96     /**
97      * Creates a new AtomicReferenceArray with the same length as, and
98      * all elements copied from, the given array.
99      *
100      * @param array the array to copy elements from
101      * @throws NullPointerException if array is null
102      */
AtomicReferenceArray(E[] array)103     public AtomicReferenceArray(E[] array) {
104         // Visibility guaranteed by final field guarantees
105         this.array = Arrays.copyOf(array, array.length, Object[].class);
106     }
107 
108     /**
109      * Returns the length of the array.
110      *
111      * @return the length of the array
112      */
length()113     public final int length() {
114         return array.length;
115     }
116 
117     /**
118      * Gets the current value at position {@code i}.
119      *
120      * @param i the index
121      * @return the current value
122      */
get(int i)123     public final E get(int i) {
124         return getRaw(checkedByteOffset(i));
125     }
126 
127     @SuppressWarnings("unchecked")
getRaw(long offset)128     private E getRaw(long offset) {
129         return (E) U.getObjectVolatile(array, offset);
130     }
131 
132     /**
133      * Sets the element at position {@code i} to the given value.
134      *
135      * @param i the index
136      * @param newValue the new value
137      */
set(int i, E newValue)138     public final void set(int i, E newValue) {
139         U.putObjectVolatile(array, checkedByteOffset(i), newValue);
140     }
141 
142     /**
143      * Eventually sets the element at position {@code i} to the given value.
144      *
145      * @param i the index
146      * @param newValue the new value
147      * @since 1.6
148      */
lazySet(int i, E newValue)149     public final void lazySet(int i, E newValue) {
150         U.putOrderedObject(array, checkedByteOffset(i), newValue);
151     }
152 
153     /**
154      * Atomically sets the element at position {@code i} to the given
155      * value and returns the old value.
156      *
157      * @param i the index
158      * @param newValue the new value
159      * @return the previous value
160      */
161     @SuppressWarnings("unchecked")
getAndSet(int i, E newValue)162     public final E getAndSet(int i, E newValue) {
163         return (E)U.getAndSetObject(array, checkedByteOffset(i), newValue);
164     }
165 
166     /**
167      * Atomically sets the element at position {@code i} to the given
168      * updated value if the current value {@code ==} the expected value.
169      *
170      * @param i the index
171      * @param expect the expected value
172      * @param update the new value
173      * @return {@code true} if successful. False return indicates that
174      * the actual value was not equal to the expected value.
175      */
compareAndSet(int i, E expect, E update)176     public final boolean compareAndSet(int i, E expect, E update) {
177         return compareAndSetRaw(checkedByteOffset(i), expect, update);
178     }
179 
compareAndSetRaw(long offset, E expect, E update)180     private boolean compareAndSetRaw(long offset, E expect, E update) {
181         return U.compareAndSwapObject(array, offset, expect, update);
182     }
183 
184     /**
185      * Atomically sets the element at position {@code i} to the given
186      * updated value if the current value {@code ==} the expected value.
187      *
188      * <p><a href="package-summary.html#weakCompareAndSet">May fail
189      * spuriously and does not provide ordering guarantees</a>, so is
190      * only rarely an appropriate alternative to {@code compareAndSet}.
191      *
192      * @param i the index
193      * @param expect the expected value
194      * @param update the new value
195      * @return {@code true} if successful
196      */
weakCompareAndSet(int i, E expect, E update)197     public final boolean weakCompareAndSet(int i, E expect, E update) {
198         return compareAndSet(i, expect, update);
199     }
200 
201     /**
202      * Atomically updates the element at index {@code i} with the results
203      * of applying the given function, returning the previous value. The
204      * function should be side-effect-free, since it may be re-applied
205      * when attempted updates fail due to contention among threads.
206      *
207      * @param i the index
208      * @param updateFunction a side-effect-free function
209      * @return the previous value
210      * @since 1.8
211      */
getAndUpdate(int i, UnaryOperator<E> updateFunction)212     public final E getAndUpdate(int i, UnaryOperator<E> updateFunction) {
213         long offset = checkedByteOffset(i);
214         E prev, next;
215         do {
216             prev = getRaw(offset);
217             next = updateFunction.apply(prev);
218         } while (!compareAndSetRaw(offset, prev, next));
219         return prev;
220     }
221 
222     /**
223      * Atomically updates the element at index {@code i} with the results
224      * of applying the given function, returning the updated value. The
225      * function should be side-effect-free, since it may be re-applied
226      * when attempted updates fail due to contention among threads.
227      *
228      * @param i the index
229      * @param updateFunction a side-effect-free function
230      * @return the updated value
231      * @since 1.8
232      */
updateAndGet(int i, UnaryOperator<E> updateFunction)233     public final E updateAndGet(int i, UnaryOperator<E> updateFunction) {
234         long offset = checkedByteOffset(i);
235         E prev, next;
236         do {
237             prev = getRaw(offset);
238             next = updateFunction.apply(prev);
239         } while (!compareAndSetRaw(offset, prev, next));
240         return next;
241     }
242 
243     /**
244      * Atomically updates the element at index {@code i} with the
245      * results of applying the given function to the current and
246      * given values, returning the previous value. The function should
247      * be side-effect-free, since it may be re-applied when attempted
248      * updates fail due to contention among threads.  The function is
249      * applied with the current value at index {@code i} as its first
250      * argument, and the given update as the second argument.
251      *
252      * @param i the index
253      * @param x the update value
254      * @param accumulatorFunction a side-effect-free function of two arguments
255      * @return the previous value
256      * @since 1.8
257      */
getAndAccumulate(int i, E x, BinaryOperator<E> accumulatorFunction)258     public final E getAndAccumulate(int i, E x,
259                                     BinaryOperator<E> accumulatorFunction) {
260         long offset = checkedByteOffset(i);
261         E prev, next;
262         do {
263             prev = getRaw(offset);
264             next = accumulatorFunction.apply(prev, x);
265         } while (!compareAndSetRaw(offset, prev, next));
266         return prev;
267     }
268 
269     /**
270      * Atomically updates the element at index {@code i} with the
271      * results of applying the given function to the current and
272      * given values, returning the updated value. The function should
273      * be side-effect-free, since it may be re-applied when attempted
274      * updates fail due to contention among threads.  The function is
275      * applied with the current value at index {@code i} as its first
276      * argument, and the given update as the second argument.
277      *
278      * @param i the index
279      * @param x the update value
280      * @param accumulatorFunction a side-effect-free function of two arguments
281      * @return the updated value
282      * @since 1.8
283      */
accumulateAndGet(int i, E x, BinaryOperator<E> accumulatorFunction)284     public final E accumulateAndGet(int i, E x,
285                                     BinaryOperator<E> accumulatorFunction) {
286         long offset = checkedByteOffset(i);
287         E prev, next;
288         do {
289             prev = getRaw(offset);
290             next = accumulatorFunction.apply(prev, x);
291         } while (!compareAndSetRaw(offset, prev, next));
292         return next;
293     }
294 
295     /**
296      * Returns the String representation of the current values of array.
297      * @return the String representation of the current values of array
298      */
toString()299     public String toString() {
300         int iMax = array.length - 1;
301         if (iMax == -1)
302             return "[]";
303 
304         StringBuilder b = new StringBuilder();
305         b.append('[');
306         for (int i = 0; ; i++) {
307             b.append(getRaw(byteOffset(i)));
308             if (i == iMax)
309                 return b.append(']').toString();
310             b.append(',').append(' ');
311         }
312     }
313 
314     /**
315      * Reconstitutes the instance from a stream (that is, deserializes it).
316      * @param s the stream
317      * @throws ClassNotFoundException if the class of a serialized object
318      *         could not be found
319      * @throws java.io.IOException if an I/O error occurs
320      */
readObject(java.io.ObjectInputStream s)321     private void readObject(java.io.ObjectInputStream s)
322         throws java.io.IOException, ClassNotFoundException {
323         // Note: This must be changed if any additional fields are defined
324         Object a = s.readFields().get("array", null);
325         if (a == null || !a.getClass().isArray())
326             throw new java.io.InvalidObjectException("Not array type");
327         if (a.getClass() != Object[].class)
328             a = Arrays.copyOf((Object[])a, Array.getLength(a), Object[].class);
329         U.putObjectVolatile(this, ARRAY, a);
330     }
331 
332 }
333