1 //******************************************************************************
2 //
3 // File: SharedDoubleArray.java
4 // Package: edu.rit.pj.reduction
5 // Unit: Class edu.rit.pj.reduction.SharedDoubleArray
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.AtomicLongArray;
43
44 /**
45 * Class SharedDoubleArray provides an array reduction variable with elements of
46 * type <code>double</code>.
47 * <P>
48 * Class SharedDoubleArray is multiple thread safe. The methods use lock-free
49 * atomic compare-and-set.
50 * <P>
51 * <I>Note:</I> Class SharedDoubleArray is implemented using class
52 * java.util.concurrent.atomic.AtomicLongArray. Each double array element is
53 * stored as a <code>long</code> whose bit pattern is the same as the double value.
54 *
55 * @author Alan Kaminsky
56 * @version 24-Aug-2007
57 */
58 public class SharedDoubleArray {
59
60 // Hidden data members.
61 private AtomicLongArray myArray;
62
63 // Exported constructors.
64 /**
65 * Construct a new double array reduction variable with the given length.
66 * Each array element is initially 0.
67 *
68 * @param len Length.
69 * @exception NegativeArraySizeException (unchecked exception) Thrown if
70 * <code>len</code> < 0.
71 */
72 public SharedDoubleArray(int len) {
73 myArray = new AtomicLongArray(len);
74 }
75
76 /**
77 * Construct a new double 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 SharedDoubleArray(double[] array) {
85 int n = array.length;
86 long[] longarray = new long[n];
87 for (int i = 0; i < n; ++i) {
88 longarray[i] = Double.doubleToLongBits(array[i]);
89 }
90 myArray = new AtomicLongArray(longarray);
91 }
92
93 // Exported operations.
94 /**
95 * Returns this array reduction variable's length.
96 *
97 * @return Length.
98 */
99 public int length() {
100 return myArray.length();
101 }
102
103 /**
104 * Returns this array reduction variable's current value at the given index.
105 *
106 * @param i Index.
107 * @return Current value.
108 */
109 public double get(int i) {
110 return Double.longBitsToDouble(myArray.get(i));
111 }
112
113 /**
114 * Set this array reduction variable at the given index to the given value.
115 *
116 * @param i Index.
117 * @param value New value.
118 */
119 public void set(int i,
120 double value) {
121 myArray.set(i, Double.doubleToLongBits(value));
122 }
123
124 /**
125 * Set this array reduction variable at the given index to the given value
126 * and return the previous value.
127 *
128 * @param i Index.
129 * @param value New value.
130 * @return Previous value.
131 */
132 public double getAndSet(int i,
133 double value) {
134 return Double.longBitsToDouble(myArray.getAndSet(i, Double.doubleToLongBits(value)));
135 }
136
137 /**
138 * Atomically set this array reduction variable at the given index to the
139 * given updated value if the current value equals the expected value.
140 *
141 * @param i Index.
142 * @param expect Expected value.
143 * @param update Updated value.
144 * @return True if the update happened, false otherwise.
145 */
146 public boolean compareAndSet(int i,
147 double expect,
148 double update) {
149 return myArray.compareAndSet(i,
150 Double.doubleToLongBits(expect),
151 Double.doubleToLongBits(update));
152 }
153
154 /**
155 * Atomically set this array reduction variable at the given index to the
156 * given updated value if the current value equals the expected value. May
157 * fail spuriously.
158 *
159 * @param i Index.
160 * @param expect Expected value.
161 * @param update Updated value.
162 * @return True if the update happened, false otherwise.
163 */
164 @SuppressWarnings("deprecation")
165 public boolean weakCompareAndSet(int i,
166 double expect,
167 double update) {
168 return myArray.weakCompareAndSet(i,
169 Double.doubleToLongBits(expect),
170 Double.doubleToLongBits(update));
171 }
172
173 /**
174 * Add one to this array reduction variable at the given index and return
175 * the previous value.
176 *
177 * @param i Index.
178 * @return Previous value.
179 */
180 public double getAndIncrement(int i) {
181 for (;;) {
182 long oldvalueLong = myArray.get(i);
183 double oldvalue = Double.longBitsToDouble(oldvalueLong);
184 double newvalue = oldvalue + 1.0;
185 long newvalueLong = Double.doubleToLongBits(newvalue);
186 if (myArray.compareAndSet(i, oldvalueLong, newvalueLong)) {
187 return oldvalue;
188 }
189 }
190 }
191
192 /**
193 * Subtract one from this array reduction variable at the given index and
194 * return the previous value.
195 *
196 * @param i Index.
197 * @return Previous value.
198 */
199 public double getAndDecrement(int i) {
200 for (;;) {
201 long oldvalueLong = myArray.get(i);
202 double oldvalue = Double.longBitsToDouble(oldvalueLong);
203 double newvalue = oldvalue - 1.0;
204 long newvalueLong = Double.doubleToLongBits(newvalue);
205 if (myArray.compareAndSet(i, oldvalueLong, newvalueLong)) {
206 return oldvalue;
207 }
208 }
209 }
210
211 /**
212 * Add the given value to this array reduction variable at the given index
213 * and return the previous value.
214 *
215 * @param i Index.
216 * @param value Value to add.
217 * @return Previous value.
218 */
219 public double getAndAdd(int i,
220 double value) {
221 for (;;) {
222 long oldvalueLong = myArray.get(i);
223 double oldvalue = Double.longBitsToDouble(oldvalueLong);
224 double newvalue = oldvalue + value;
225 long newvalueLong = Double.doubleToLongBits(newvalue);
226 if (myArray.compareAndSet(i, oldvalueLong, newvalueLong)) {
227 return oldvalue;
228 }
229 }
230 }
231
232 /**
233 * Add one to this array reduction variable at the given index and return
234 * the new value.
235 *
236 * @param i Index.
237 * @return New value.
238 */
239 public double incrementAndGet(int i) {
240 for (;;) {
241 long oldvalueLong = myArray.get(i);
242 double oldvalue = Double.longBitsToDouble(oldvalueLong);
243 double newvalue = oldvalue + 1.0;
244 long newvalueLong = Double.doubleToLongBits(newvalue);
245 if (myArray.compareAndSet(i, oldvalueLong, newvalueLong)) {
246 return newvalue;
247 }
248 }
249 }
250
251 /**
252 * Subtract one from this array reduction variable at the given index and
253 * return the new value.
254 *
255 * @param i Index.
256 * @return New value.
257 */
258 public double decrementAndGet(int i) {
259 for (;;) {
260 long oldvalueLong = myArray.get(i);
261 double oldvalue = Double.longBitsToDouble(oldvalueLong);
262 double newvalue = oldvalue - 1.0;
263 long newvalueLong = Double.doubleToLongBits(newvalue);
264 if (myArray.compareAndSet(i, oldvalueLong, newvalueLong)) {
265 return newvalue;
266 }
267 }
268 }
269
270 /**
271 * Add the given value to this array reduction variable at the given index
272 * and return the new value.
273 *
274 * @param i Index.
275 * @param value Value to add.
276 * @return New value.
277 */
278 public double addAndGet(int i,
279 double value) {
280 for (;;) {
281 long oldvalueLong = myArray.get(i);
282 double oldvalue = Double.longBitsToDouble(oldvalueLong);
283 double newvalue = oldvalue + value;
284 long newvalueLong = Double.doubleToLongBits(newvalue);
285 if (myArray.compareAndSet(i, oldvalueLong, newvalueLong)) {
286 return newvalue;
287 }
288 }
289 }
290
291 /**
292 * Combine this array reduction variable at the given index with the given
293 * value using the given operation. (This array <code>[i]</code>) is set to
294 * (this array <code>[i]</code>) <I>op</I> (<code>value</code>), then (this array
295 * <code>[i]</code>) is returned.
296 *
297 * @param i Index.
298 * @param value Value.
299 * @param op Binary operation.
300 * @return (This array <code>[i]</code>) <I>op</I> (<code>value</code>).
301 */
302 public double reduce(int i,
303 double value,
304 DoubleOp op) {
305 for (;;) {
306 long oldvalueLong = myArray.get(i);
307 double oldvalue = Double.longBitsToDouble(oldvalueLong);
308 double newvalue = op.op(oldvalue, value);
309 long newvalueLong = Double.doubleToLongBits(newvalue);
310 if (myArray.compareAndSet(i, oldvalueLong, newvalueLong)) {
311 return newvalue;
312 }
313 }
314 }
315
316 /**
317 * Combine this array reduction variable with the given array using the
318 * given operation. For each index <code>i</code> from 0 to this array's
319 * length-1, (this array <code>[i]</code>) is set to (this array <code>[i]</code>)
320 * <I>op</I> (<code>src[i]</code>).
321 * <P>
322 * The <code>reduce()</code> method is multiple thread safe <I>on a per-element
323 * basis.</I> Each individual array element is updated atomically, but the
324 * array as a whole is not updated atomically.
325 *
326 * @param src Source array.
327 * @param op Binary operation.
328 * @exception NullPointerException (unchecked exception) Thrown if
329 * <code>src</code> is null. Thrown if
330 * <code>op</code> is null.
331 * @exception IndexOutOfBoundsException (unchecked exception) Thrown if any
332 * array index would be out of bounds.
333 */
334 public void reduce(double[] src,
335 DoubleOp op) {
336 reduce(0, src, 0, myArray.length(), op);
337 }
338
339 /**
340 * Combine a portion of this array reduction variable with a portion of the
341 * given array using the given operation. For each index <code>i</code> from 0
342 * to <code>len</code>-1, (this array <code>[dstoff+i]</code>) is set to (this array
343 * <code>[dstoff+i]</code>) <I>op</I> (<code>src[srcoff+i]</code>).
344 * <P>
345 * The <code>reduce()</code> method is multiple thread safe <I>on a per-element
346 * basis.</I> Each individual array element is updated atomically, but the
347 * array as a whole is not updated atomically.
348 *
349 * @param dstoff Index of first element to update in this array.
350 * @param src Source array.
351 * @param srcoff Index of first element to update from in the source array.
352 * @param len Number of array elements to update.
353 * @param op Binary operation.
354 * @exception NullPointerException (unchecked exception) Thrown if
355 * <code>src</code> is null. Thrown if
356 * <code>op</code> is null.
357 * @exception IndexOutOfBoundsException (unchecked exception) Thrown if
358 * <code>len</code> < 0. Thrown if any array index would be out of bounds.
359 */
360 public void reduce(int dstoff,
361 double[] src,
362 int srcoff,
363 int len,
364 DoubleOp op) {
365 if (len < 0
366 || dstoff < 0 || dstoff + len > myArray.length()
367 || srcoff < 0 || srcoff + len > src.length) {
368 throw new IndexOutOfBoundsException();
369 }
370 while (len > 0) {
371 updateLoop:
372 for (;;) {
373 long oldvalueLong = myArray.get(dstoff);
374 double oldvalue = Double.longBitsToDouble(oldvalueLong);
375 double newvalue = op.op(oldvalue, src[srcoff]);
376 long newvalueLong = Double.doubleToLongBits(newvalue);
377 if (myArray.compareAndSet(dstoff, oldvalueLong, newvalueLong)) {
378 break updateLoop;
379 }
380 }
381 ++dstoff;
382 ++srcoff;
383 --len;
384 }
385 }
386
387 /**
388 * Returns a string version of this array reduction variable.
389 *
390 * @return String version.
391 */
392 public String toString() {
393 StringBuilder b = new StringBuilder();
394 b.append('[');
395 int n = myArray.length();
396 for (int i = 0; i < n; ++i) {
397 if (i > 0) {
398 b.append(", ");
399 }
400 b.append(get(i));
401 }
402 b.append(']');
403 return b.toString();
404 }
405
406 }