View Javadoc
1   //******************************************************************************
2   //
3   // File:    SharedObjectArray.java
4   // Package: edu.rit.pj.reduction
5   // Unit:    Class edu.rit.pj.reduction.SharedObjectArray
6   //
7   // This Java source file is copyright (C) 2007 by Alan Kaminsky. All rights
8   // reserved. For further information, contact the author, Alan Kaminsky, at
9   // ark@cs.rit.edu.
10  //
11  // This Java source file is part of the Parallel Java Library ("PJ"). PJ is free
12  // software; you can redistribute it and/or modify it under the terms of the GNU
13  // General Public License as published by the Free Software Foundation; either
14  // version 3 of the License, or (at your option) any later version.
15  //
16  // PJ is distributed in the hope that it will be useful, but WITHOUT ANY
17  // WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
18  // A PARTICULAR PURPOSE. See the GNU General Public License for more details.
19  //
20  // Linking this library statically or dynamically with other modules is making a
21  // combined work based on this library. Thus, the terms and conditions of the GNU
22  // General Public License cover the whole combination.
23  //
24  // As a special exception, the copyright holders of this library give you
25  // permission to link this library with independent modules to produce an
26  // executable, regardless of the license terms of these independent modules, and
27  // to copy and distribute the resulting executable under terms of your choice,
28  // provided that you also meet, for each linked independent module, the terms
29  // and conditions of the license of that module. An independent module is a module
30  // which is not derived from or based on this library. If you modify this library,
31  // you may extend this exception to your version of the library, but you are not
32  // obligated to do so. If you do not wish to do so, delete this exception
33  // statement from your version.
34  //
35  // A copy of the GNU General Public License is provided in the file gpl.txt. You
36  // may also obtain a copy of the GNU General Public License on the World Wide
37  // Web at http://www.gnu.org/licenses/gpl.html.
38  //
39  //******************************************************************************
40  package edu.rit.pj.reduction;
41  
42  import java.util.concurrent.atomic.AtomicReferenceArray;
43  
44  /**
45   * Class SharedObjectArray provides an array reduction variable with elements of
46   * an object type.
47   * <P>
48   * Class SharedObjectArray is multiple thread safe. The methods use lock-free
49   * atomic compare-and-set.
50   * <P>
51   * <I>Note:</I> Class SharedObjectArray is implemented using class
52   * java.util.concurrent.atomic.AtomicReferenceArray.
53   *
54   * @param <T> Object data type.
55   * @author Alan Kaminsky
56   * @version 24-Aug-2007
57   */
58  public class SharedObjectArray<T> {
59  
60  // Hidden data members.
61      private AtomicReferenceArray<T> myArray;
62  
63  // Exported constructors.
64      /**
65       * Construct a new object array reduction variable with the given length.
66       * Each array element is initially null.
67       *
68       * @param len Length.
69       * @exception NegativeArraySizeException (unchecked exception) Thrown if
70       * <code>len</code> &lt; 0.
71       */
72      public SharedObjectArray(int len) {
73          myArray = new AtomicReferenceArray<T>(len);
74      }
75  
76      /**
77       * Construct a new object array reduction variable whose elements are copied
78       * from the given array.
79       *
80       * @param array Array to copy.
81       * @exception NullPointerException (unchecked exception) Thrown if
82       * <code>array</code> is null.
83       */
84      public SharedObjectArray(T[] array) {
85          myArray = new AtomicReferenceArray<T>(array);
86      }
87  
88  // Exported operations.
89      /**
90       * Returns this array reduction variable's length.
91       *
92       * @return Length.
93       */
94      public int length() {
95          return myArray.length();
96      }
97  
98      /**
99       * Returns this array reduction variable's current value at the given index.
100      *
101      * @param i Index.
102      * @return Current value.
103      */
104     public T get(int i) {
105         return myArray.get(i);
106     }
107 
108     /**
109      * Set this array reduction variable at the given index to the given value.
110      *
111      * @param i Index.
112      * @param value New value.
113      */
114     public void set(int i,
115             T value) {
116         myArray.set(i, value);
117     }
118 
119     /**
120      * Set this array reduction variable at the given index to the given value
121      * and return the previous value.
122      *
123      * @param i Index.
124      * @param value New value.
125      * @return Previous value.
126      */
127     public T getAndSet(int i,
128             T value) {
129         return myArray.getAndSet(i, value);
130     }
131 
132     /**
133      * Atomically set this array reduction variable at the given index to the
134      * given updated value if the current value equals the expected value.
135      *
136      * @param i Index.
137      * @param expect Expected value.
138      * @param update Updated value.
139      * @return True if the update happened, false otherwise.
140      */
141     public boolean compareAndSet(int i,
142             T expect,
143             T update) {
144         return myArray.compareAndSet(i, expect, update);
145     }
146 
147     /**
148      * Atomically set this array reduction variable at the given index to the
149      * given updated value if the current value equals the expected value. May
150      * fail spuriously.
151      *
152      * @param i Index.
153      * @param expect Expected value.
154      * @param update Updated value.
155      * @return True if the update happened, false otherwise.
156      */
157     @SuppressWarnings("deprecation")
158     public boolean weakCompareAndSet(int i,
159             T expect,
160             T update) {
161         return myArray.weakCompareAndSet(i, expect, update);
162     }
163 
164     /**
165      * Combine this array reduction variable at the given index with the given
166      * value using the given operation. (This array <code>[i]</code>) is set to
167      * (this array <code>[i]</code>) <I>op</I> (<code>value</code>), then (this array
168      * <code>[i]</code>) is returned.
169      *
170      * @param i Index.
171      * @param value Value.
172      * @param op Binary operation.
173      * @return (This array <code>[i]</code>) <I>op</I> (<code>value</code>).
174      */
175     public T reduce(int i,
176             T value,
177             ObjectOp<T> op) {
178         for (;;) {
179             T oldvalue = myArray.get(i);
180             T newvalue = op.op(oldvalue, value);
181             if (myArray.compareAndSet(i, oldvalue, newvalue)) {
182                 return newvalue;
183             }
184         }
185     }
186 
187     /**
188      * Combine this array reduction variable with the given array using the
189      * given operation. For each index <code>i</code> from 0 to this array's
190      * length-1, (this array <code>[i]</code>) is set to (this array <code>[i]</code>)
191      * <I>op</I> (<code>src[i]</code>).
192      * <P>
193      * The <code>reduce()</code> method is multiple thread safe <I>on a per-element
194      * basis.</I> Each individual array element is updated atomically, but the
195      * array as a whole is not updated atomically.
196      *
197      * @param src Source array.
198      * @param op Binary operation.
199      * @exception NullPointerException (unchecked exception) Thrown if
200      * <code>src</code> is null. Thrown if
201      * <code>op</code> is null.
202      * @exception IndexOutOfBoundsException (unchecked exception) Thrown if any
203      * array index would be out of bounds.
204      */
205     public void reduce(T[] src,
206             ObjectOp<T> op) {
207         reduce(0, src, 0, myArray.length(), op);
208     }
209 
210     /**
211      * Combine a portion of this array reduction variable with a portion of the
212      * given array using the given operation. For each index <code>i</code> from 0
213      * to <code>len</code>-1, (this array <code>[dstoff+i]</code>) is set to (this array
214      * <code>[dstoff+i]</code>) <I>op</I> (<code>src[srcoff+i]</code>).
215      * <P>
216      * The <code>reduce()</code> method is multiple thread safe <I>on a per-element
217      * basis.</I> Each individual array element is updated atomically, but the
218      * array as a whole is not updated atomically.
219      *
220      * @param dstoff Index of first element to update in this array.
221      * @param src Source array.
222      * @param srcoff Index of first element to update from in the source array.
223      * @param len Number of array elements to update.
224      * @param op Binary operation.
225      * @exception NullPointerException (unchecked exception) Thrown if
226      * <code>src</code> is null. Thrown if
227      * <code>op</code> is null.
228      * @exception IndexOutOfBoundsException (unchecked exception) Thrown if
229      * <code>len</code> &lt; 0. Thrown if any array index would be out of bounds.
230      */
231     public void reduce(int dstoff,
232             T[] src,
233             int srcoff,
234             int len,
235             ObjectOp<T> op) {
236         if (len < 0
237                 || dstoff < 0 || dstoff + len > myArray.length()
238                 || srcoff < 0 || srcoff + len > src.length) {
239             throw new IndexOutOfBoundsException();
240         }
241         while (len > 0) {
242             updateLoop:
243             for (;;) {
244                 T oldvalue = myArray.get(dstoff);
245                 T newvalue = op.op(oldvalue, src[srcoff]);
246                 if (myArray.compareAndSet(dstoff, oldvalue, newvalue)) {
247                     break updateLoop;
248                 }
249             }
250             ++dstoff;
251             ++srcoff;
252             --len;
253         }
254     }
255 
256     /**
257      * Returns a string version of this array reduction variable.
258      *
259      * @return String version.
260      */
261     public String toString() {
262         return myArray.toString();
263     }
264 
265 }