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 jdk.internal.misc.Unsafe U = jdk.internal.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 
  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 
  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      */
  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      */
 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      */
 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      */
 123     public final E get(int i) {
 124         return getRaw(checkedByteOffset(i));
 125     }
 126 
 127     @SuppressWarnings("unchecked")
 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      */
 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      */
 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")
 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      */
 176     public final boolean compareAndSet(int i, E expect, E update) {
 177         return compareAndSetRaw(checkedByteOffset(i), expect, update);
 178     }
 179 
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 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 }