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> < 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> < 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 }