View Javadoc
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> &lt; 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> &lt; 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 }