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