ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166y/forkjoin/PAS.java
Revision: 1.7
Committed: Fri Jul 25 18:29:00 2008 UTC (15 years, 11 months ago) by jsr166
Branch: MAIN
Changes since 1.6: +42 -42 lines
Log Message: 
whitespace

File Contents

# User Rev Content
1 dl 1.1 /*
2     * Written by Doug Lea with assistance from members of JCP JSR-166
3     * Expert Group and released to the public domain, as explained at
4     * http://creativecommons.org/licenses/publicdomain
5     */
6    
7     package jsr166y.forkjoin;
8     import static jsr166y.forkjoin.Ops.*;
9     import java.util.*;
10     import java.util.concurrent.atomic.*;
11     import java.lang.reflect.Array;
12    
13     /**
14 dl 1.4 * Shared internal execution support for ParallelArray and
15     * specializations.
16 dl 1.1 */
17     class PAS {
18     private PAS() {} // all-static, non-instantiable
19    
20     /** Global default executor */
21 dl 1.3 private static volatile ForkJoinPool defaultExecutor;
22 dl 1.1 /** Lock for on-demand initialization of defaultExecutor */
23     private static final Object poolLock = new Object();
24 jsr166 1.7
25 dl 1.1 static ForkJoinExecutor defaultExecutor() {
26 dl 1.3 ForkJoinPool p = defaultExecutor; // double-check
27     if (p == null) {
28     synchronized(poolLock) {
29     p = defaultExecutor;
30     if (p == null) {
31     // use ceil(7/8 * ncpus)
32     int nprocs = Runtime.getRuntime().availableProcessors();
33     int nthreads = nprocs - (nprocs >>> 3);
34     defaultExecutor = p = new ForkJoinPool(nthreads);
35     }
36 dl 1.1 }
37     }
38 dl 1.3 return p;
39 dl 1.1 }
40    
41     /**
42     * Base for most divide-and-conquer tasks used for computing
43     * ParallelArray operations. Rather than pure recursion, it links
44     * right-hand-sides and then joins up the tree, exploiting cases
45     * where tasks aren't stolen. This generates and joins tasks with
46     * a bit less overhead than pure recursive style -- there are only
47     * as many tasks as leaves (no strictly internal nodes).
48     *
49 dl 1.4 * Split control relies on pap.getThreshold(), which is
50 dl 1.3 * expected to err on the side of generating too many tasks. To
51 dl 1.6 * counterbalance, if a task pops off its own smallest subtask, it
52     * directly runs its leaf action rather than possibly resplitting.
53 dl 1.1 *
54     * There are, with a few exceptions, three flavors of each FJBase
55 dl 1.2 * subclass, prefixed FJO (object reference), FJD (double) and FJL
56 jsr166 1.7 * (long).
57 dl 1.1 */
58     static abstract class FJBase extends RecursiveAction {
59 dl 1.4 final AbstractParallelAnyArray pap;
60 dl 1.1 final int lo;
61     final int hi;
62     final FJBase next; // the next task that creator should join
63 dl 1.4 FJBase(AbstractParallelAnyArray pap, int lo, int hi, FJBase next) {
64     this.pap = pap;
65 dl 1.1 this.lo = lo;
66     this.hi = hi;
67     this.next = next;
68     }
69    
70     public final void compute() {
71 dl 1.4 int g = pap.getThreshold();
72 dl 1.1 int l = lo;
73     int h = hi;
74 jsr166 1.7 if (h - l > g)
75 dl 1.3 internalCompute(l, h, g);
76     else
77     atLeaf(l, h);
78     }
79    
80     final void internalCompute(int l, int h, int g) {
81     FJBase r = null;
82     do {
83 dl 1.1 int rh = h;
84     h = (l + h) >>> 1;
85     (r = newSubtask(h, rh, r)).fork();
86 dl 1.3 } while (h - l > g);
87 dl 1.1 atLeaf(l, h);
88 dl 1.3 do {
89 dl 1.1 if (ForkJoinWorkerThread.removeIfNextLocalTask(r))
90     r.atLeaf(r.lo, r.hi);
91     else
92     r.join();
93     onReduce(r);
94     r = r.next;
95 dl 1.3 } while (r != null);
96 dl 1.1 }
97    
98     /** Leaf computation */
99     abstract void atLeaf(int l, int h);
100     /** Operation performed after joining right subtask -- default noop */
101     void onReduce(FJBase right) {}
102     /** Factory method to create new subtask, normally of current type */
103     abstract FJBase newSubtask(int l, int h, FJBase r);
104     }
105    
106     // apply
107    
108 dl 1.2 static final class FJOApply extends FJBase {
109 dl 1.1 final Procedure procedure;
110 dl 1.4 FJOApply(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
111 dl 1.1 Procedure procedure) {
112 dl 1.4 super(pap, lo, hi, next);
113 dl 1.1 this.procedure = procedure;
114     }
115     FJBase newSubtask(int l, int h, FJBase r) {
116 dl 1.4 return new FJOApply(pap, l, h, r, procedure);
117 dl 1.1 }
118     void atLeaf(int l, int h) {
119 dl 1.4 pap.leafApply(l, h, procedure);
120 dl 1.1 }
121     }
122    
123     static final class FJDApply extends FJBase {
124     final DoubleProcedure procedure;
125 dl 1.4 FJDApply(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
126 dl 1.1 DoubleProcedure procedure) {
127 dl 1.4 super(pap, lo, hi, next);
128 dl 1.1 this.procedure = procedure;
129     }
130     FJBase newSubtask(int l, int h, FJBase r) {
131 dl 1.4 return new FJDApply(pap, l, h, r, procedure);
132 dl 1.1 }
133     void atLeaf(int l, int h) {
134 dl 1.4 pap.leafApply(l, h, procedure);
135 dl 1.1 }
136     }
137    
138     static final class FJLApply extends FJBase {
139     final LongProcedure procedure;
140 dl 1.4 FJLApply(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
141 dl 1.1 LongProcedure procedure) {
142 dl 1.4 super(pap, lo, hi, next);
143 dl 1.1 this.procedure = procedure;
144     }
145     FJBase newSubtask(int l, int h, FJBase r) {
146 dl 1.4 return new FJLApply(pap, l, h, r, procedure);
147 dl 1.1 }
148     void atLeaf(int l, int h) {
149 dl 1.4 pap.leafApply(l, h, procedure);
150 dl 1.1 }
151     }
152    
153     // reduce
154    
155 dl 1.2 static final class FJOReduce extends FJBase {
156 dl 1.1 final Reducer reducer;
157     Object result;
158 dl 1.4 FJOReduce(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
159 dl 1.1 Reducer reducer, Object base) {
160 dl 1.4 super(pap, lo, hi, next);
161 dl 1.1 this.reducer = reducer;
162     this.result = base;
163     }
164     FJBase newSubtask(int l, int h, FJBase r) {
165 dl 1.4 return new FJOReduce(pap, l, h, r, reducer, result);
166 dl 1.1 }
167     void atLeaf(int l, int h) {
168 dl 1.4 result = pap.leafReduce(l, h, reducer, result);
169 dl 1.1 }
170     void onReduce(FJBase right) {
171 dl 1.2 result = reducer.op(result, ((FJOReduce)right).result);
172 dl 1.1 }
173     }
174    
175     static final class FJDReduce extends FJBase {
176     final DoubleReducer reducer;
177     double result;
178 dl 1.4 FJDReduce(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
179 dl 1.1 DoubleReducer reducer, double base) {
180 dl 1.4 super(pap, lo, hi, next);
181 dl 1.1 this.reducer = reducer;
182     this.result = base;
183     }
184     FJBase newSubtask(int l, int h, FJBase r) {
185 dl 1.4 return new FJDReduce(pap, l, h, r, reducer, result);
186 dl 1.1 }
187     void atLeaf(int l, int h) {
188 dl 1.4 result = pap.leafReduce(l, h, reducer, result);
189 dl 1.1 }
190     void onReduce(FJBase right) {
191 dl 1.2 result = reducer.op(result, ((FJDReduce)right).result);
192 dl 1.1 }
193     }
194    
195     static final class FJLReduce extends FJBase {
196     final LongReducer reducer;
197     long result;
198 dl 1.4 FJLReduce(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
199 dl 1.1 LongReducer reducer, long base) {
200 dl 1.4 super(pap, lo, hi, next);
201 dl 1.1 this.reducer = reducer;
202     this.result = base;
203     }
204     FJBase newSubtask(int l, int h, FJBase r) {
205 dl 1.4 return new FJLReduce(pap, l, h, r, reducer, result);
206 dl 1.1 }
207     void atLeaf(int l, int h) {
208 dl 1.4 result = pap.leafReduce(l, h, reducer, result);
209 dl 1.1 }
210     void onReduce(FJBase right) {
211 dl 1.2 result = reducer.op(result, ((FJLReduce)right).result);
212 dl 1.1 }
213     }
214    
215     // map
216    
217 dl 1.2 static final class FJOMap extends FJBase {
218 dl 1.1 final Object[] dest;
219     final int offset;
220 dl 1.4 FJOMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
221     Object[] dest, int offset) {
222     super(pap, lo, hi, next);
223 dl 1.1 this.dest = dest;
224     this.offset = offset;
225     }
226     FJBase newSubtask(int l, int h, FJBase r) {
227 dl 1.4 return new FJOMap(pap, l, h, r, dest, offset);
228 dl 1.1 }
229     void atLeaf(int l, int h) {
230 dl 1.5 pap.leafTransfer(l, h, dest, l + offset);
231 dl 1.1 }
232     }
233    
234     static final class FJDMap extends FJBase {
235     final double[] dest;
236     final int offset;
237 jsr166 1.7 FJDMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
238 dl 1.4 double[] dest, int offset) {
239     super(pap, lo, hi, next);
240 dl 1.1 this.dest = dest;
241     this.offset = offset;
242     }
243     FJBase newSubtask(int l, int h, FJBase r) {
244 dl 1.4 return new FJDMap(pap, l, h, r, dest, offset);
245 dl 1.1 }
246     void atLeaf(int l, int h) {
247 dl 1.5 pap.leafTransfer(l, h, dest, l + offset);
248 dl 1.1 }
249     }
250    
251     static final class FJLMap extends FJBase {
252     final long[] dest;
253     final int offset;
254 jsr166 1.7 FJLMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
255 dl 1.4 long[] dest, int offset) {
256     super(pap, lo, hi, next);
257 dl 1.1 this.dest = dest;
258     this.offset = offset;
259     }
260     FJBase newSubtask(int l, int h, FJBase r) {
261 dl 1.4 return new FJLMap(pap, l, h, r, dest, offset);
262 dl 1.1 }
263     void atLeaf(int l, int h) {
264 dl 1.5 pap.leafTransfer(l, h, dest, l + offset);
265 dl 1.1 }
266     }
267    
268     // transform
269    
270 dl 1.2 static final class FJOTransform extends FJBase {
271     final Op op;
272 dl 1.4 FJOTransform(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
273 dl 1.2 Op op) {
274 dl 1.4 super(pap, lo, hi, next);
275 dl 1.2 this.op = op;
276 dl 1.1 }
277     FJBase newSubtask(int l, int h, FJBase r) {
278 dl 1.4 return new FJOTransform(pap, l, h, r, op);
279 dl 1.1 }
280     void atLeaf(int l, int h) {
281 dl 1.4 pap.leafTransform(l, h, op);
282 dl 1.1 }
283     }
284    
285     static final class FJDTransform extends FJBase {
286 dl 1.2 final DoubleOp op;
287 dl 1.4 FJDTransform(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
288 dl 1.2 DoubleOp op) {
289 dl 1.4 super(pap, lo, hi, next);
290 dl 1.2 this.op = op;
291 dl 1.1 }
292     FJBase newSubtask(int l, int h, FJBase r) {
293 dl 1.4 return new FJDTransform(pap, l, h, r, op);
294 dl 1.1 }
295     void atLeaf(int l, int h) {
296 dl 1.4 pap.leafTransform(l, h, op);
297 dl 1.1 }
298     }
299    
300     static final class FJLTransform extends FJBase {
301 dl 1.2 final LongOp op;
302 dl 1.4 FJLTransform(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
303 dl 1.2 LongOp op) {
304 dl 1.4 super(pap, lo, hi, next);
305 dl 1.2 this.op = op;
306 dl 1.1 }
307     FJBase newSubtask(int l, int h, FJBase r) {
308 dl 1.4 return new FJLTransform(pap, l, h, r, op);
309 dl 1.1 }
310     void atLeaf(int l, int h) {
311 dl 1.4 pap.leafTransform(l, h, op);
312 dl 1.1 }
313     }
314    
315     // index map
316    
317 dl 1.2 static final class FJOIndexMap extends FJBase {
318     final IntToObject op;
319 dl 1.4 FJOIndexMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
320 dl 1.2 IntToObject op) {
321 dl 1.4 super(pap, lo, hi, next);
322 dl 1.2 this.op = op;
323 dl 1.1 }
324     FJBase newSubtask(int l, int h, FJBase r) {
325 dl 1.4 return new FJOIndexMap(pap, l, h, r, op);
326 dl 1.1 }
327     void atLeaf(int l, int h) {
328 dl 1.4 pap.leafIndexMap(l, h, op);
329 dl 1.1 }
330     }
331    
332     static final class FJDIndexMap extends FJBase {
333 dl 1.2 final IntToDouble op;
334 dl 1.4 FJDIndexMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
335 dl 1.2 IntToDouble op) {
336 dl 1.4 super(pap, lo, hi, next);
337 dl 1.2 this.op = op;
338 dl 1.1 }
339     FJBase newSubtask(int l, int h, FJBase r) {
340 dl 1.4 return new FJDIndexMap(pap, l, h, r, op);
341 dl 1.1 }
342     void atLeaf(int l, int h) {
343 dl 1.4 pap.leafIndexMap(l, h, op);
344 dl 1.1 }
345     }
346    
347     static final class FJLIndexMap extends FJBase {
348 dl 1.2 final IntToLong op;
349 dl 1.4 FJLIndexMap(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
350 dl 1.2 IntToLong op) {
351 dl 1.4 super(pap, lo, hi, next);
352 dl 1.2 this.op = op;
353 dl 1.1 }
354     FJBase newSubtask(int l, int h, FJBase r) {
355 dl 1.4 return new FJLIndexMap(pap, l, h, r, op);
356 dl 1.1 }
357     void atLeaf(int l, int h) {
358 dl 1.4 pap.leafIndexMap(l, h, op);
359 dl 1.1 }
360     }
361    
362 dl 1.3 // binary index map
363    
364     static final class FJOBinaryIndexMap extends FJBase {
365     final IntAndObjectToObject op;
366 jsr166 1.7 FJOBinaryIndexMap(AbstractParallelAnyArray pap, int lo, int hi,
367 dl 1.4 FJBase next, IntAndObjectToObject op) {
368     super(pap, lo, hi, next);
369 dl 1.3 this.op = op;
370     }
371     FJBase newSubtask(int l, int h, FJBase r) {
372 dl 1.4 return new FJOBinaryIndexMap(pap, l, h, r, op);
373 dl 1.3 }
374     void atLeaf(int l, int h) {
375 dl 1.4 pap.leafBinaryIndexMap(l, h, op);
376 dl 1.3 }
377     }
378    
379     static final class FJDBinaryIndexMap extends FJBase {
380     final IntAndDoubleToDouble op;
381 jsr166 1.7 FJDBinaryIndexMap(AbstractParallelAnyArray pap, int lo, int hi,
382 dl 1.4 FJBase next, IntAndDoubleToDouble op) {
383     super(pap, lo, hi, next);
384 dl 1.3 this.op = op;
385     }
386     FJBase newSubtask(int l, int h, FJBase r) {
387 dl 1.4 return new FJDBinaryIndexMap(pap, l, h, r, op);
388 dl 1.3 }
389     void atLeaf(int l, int h) {
390 dl 1.4 pap.leafBinaryIndexMap(l, h, op);
391 dl 1.3 }
392     }
393    
394     static final class FJLBinaryIndexMap extends FJBase {
395     final IntAndLongToLong op;
396 jsr166 1.7 FJLBinaryIndexMap(AbstractParallelAnyArray pap, int lo, int hi,
397 dl 1.4 FJBase next, IntAndLongToLong op) {
398     super(pap, lo, hi, next);
399 dl 1.3 this.op = op;
400     }
401     FJBase newSubtask(int l, int h, FJBase r) {
402 dl 1.4 return new FJLBinaryIndexMap(pap, l, h, r, op);
403 dl 1.3 }
404     void atLeaf(int l, int h) {
405 dl 1.4 pap.leafBinaryIndexMap(l, h, op);
406 dl 1.3 }
407     }
408    
409    
410 dl 1.1 // generate
411    
412 dl 1.2 static final class FJOGenerate extends FJBase {
413 dl 1.1 final Generator generator;
414 dl 1.4 FJOGenerate(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
415 dl 1.1 Generator generator) {
416 dl 1.4 super(pap, lo, hi, next);
417 dl 1.1 this.generator = generator;
418     }
419     FJBase newSubtask(int l, int h, FJBase r) {
420 dl 1.4 return new FJOGenerate(pap, l, h, r, generator);
421 dl 1.1 }
422     void atLeaf(int l, int h) {
423 dl 1.4 pap.leafGenerate(l, h, generator);
424 dl 1.1 }
425     }
426    
427     static final class FJDGenerate extends FJBase {
428     final DoubleGenerator generator;
429 dl 1.4 FJDGenerate(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
430 dl 1.1 DoubleGenerator generator) {
431 dl 1.4 super(pap, lo, hi, next);
432 dl 1.1 this.generator = generator;
433     }
434     FJBase newSubtask(int l, int h, FJBase r) {
435 dl 1.4 return new FJDGenerate(pap, l, h, r, generator);
436 dl 1.1 }
437     void atLeaf(int l, int h) {
438 dl 1.4 pap.leafGenerate(l, h, generator);
439 dl 1.1 }
440     }
441    
442     static final class FJLGenerate extends FJBase {
443     final LongGenerator generator;
444 dl 1.4 FJLGenerate(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
445 dl 1.1 LongGenerator generator) {
446 dl 1.4 super(pap, lo, hi, next);
447 dl 1.1 this.generator = generator;
448     }
449     FJBase newSubtask(int l, int h, FJBase r) {
450 dl 1.4 return new FJLGenerate(pap, l, h, r, generator);
451 dl 1.1 }
452     void atLeaf(int l, int h) {
453 dl 1.4 pap.leafGenerate(l, h, generator);
454 dl 1.1 }
455     }
456    
457     // fill
458    
459 dl 1.2 static final class FJOFill extends FJBase {
460 dl 1.1 final Object value;
461 jsr166 1.7 FJOFill(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
462 dl 1.4 Object value) {
463     super(pap, lo, hi, next);
464 dl 1.1 this.value = value;
465     }
466     FJBase newSubtask(int l, int h, FJBase r) {
467 dl 1.4 return new FJOFill(pap, l, h, r, value);
468 dl 1.1 }
469     void atLeaf(int l, int h) {
470 dl 1.4 pap.leafFill(l, h, value);
471 dl 1.1 }
472     }
473    
474     static final class FJDFill extends FJBase {
475     final double value;
476 jsr166 1.7 FJDFill(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
477 dl 1.4 double value) {
478     super(pap, lo, hi, next);
479 dl 1.1 this.value = value;
480     }
481     FJBase newSubtask(int l, int h, FJBase r) {
482 dl 1.4 return new FJDFill(pap, l, h, r, value);
483 dl 1.1 }
484     void atLeaf(int l, int h) {
485 dl 1.4 pap.leafFill(l, h, value);
486 dl 1.1 }
487     }
488    
489     static final class FJLFill extends FJBase {
490     final long value;
491 jsr166 1.7 FJLFill(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
492 dl 1.4 long value) {
493     super(pap, lo, hi, next);
494 dl 1.1 this.value = value;
495     }
496     FJBase newSubtask(int l, int h, FJBase r) {
497 dl 1.4 return new FJLFill(pap, l, h, r, value);
498 dl 1.1 }
499     void atLeaf(int l, int h) {
500 dl 1.4 pap.leafFill(l, h, value);
501 dl 1.1 }
502     }
503    
504     // combine in place
505    
506 dl 1.2 static final class FJOCombineInPlace extends FJBase {
507 dl 1.1 final Object[] other;
508     final int otherOffset;
509 dl 1.2 final BinaryOp combiner;
510 jsr166 1.7 FJOCombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
511 dl 1.4 FJBase next, Object[] other, int otherOffset,
512 dl 1.2 BinaryOp combiner) {
513 dl 1.4 super(pap, lo, hi, next);
514 dl 1.1 this.other = other;
515     this.otherOffset = otherOffset;
516     this.combiner = combiner;
517     }
518     FJBase newSubtask(int l, int h, FJBase r) {
519 dl 1.2 return new FJOCombineInPlace
520 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
521 dl 1.1 }
522     void atLeaf(int l, int h) {
523 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
524 dl 1.1 }
525     }
526    
527     static final class FJDCombineInPlace extends FJBase {
528     final double[] other;
529     final int otherOffset;
530 dl 1.2 final BinaryDoubleOp combiner;
531 jsr166 1.7 FJDCombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
532 dl 1.4 FJBase next, double[] other, int otherOffset,
533 dl 1.2 BinaryDoubleOp combiner) {
534 dl 1.4 super(pap, lo, hi, next);
535 dl 1.1 this.other = other;
536     this.otherOffset = otherOffset;
537     this.combiner = combiner;
538     }
539     FJBase newSubtask(int l, int h, FJBase r) {
540     return new FJDCombineInPlace
541 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
542 dl 1.1 }
543     void atLeaf(int l, int h) {
544 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
545 dl 1.1 }
546     }
547    
548     static final class FJLCombineInPlace extends FJBase {
549     final long[] other;
550     final int otherOffset;
551 dl 1.2 final BinaryLongOp combiner;
552 jsr166 1.7 FJLCombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
553 dl 1.4 FJBase next, long[] other, int otherOffset,
554 dl 1.2 BinaryLongOp combiner) {
555 dl 1.4 super(pap, lo, hi, next);
556 dl 1.1 this.other = other;
557     this.otherOffset = otherOffset;
558     this.combiner = combiner;
559     }
560     FJBase newSubtask(int l, int h, FJBase r) {
561     return new FJLCombineInPlace
562 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
563 dl 1.1 }
564     void atLeaf(int l, int h) {
565 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
566 dl 1.1 }
567     }
568    
569 dl 1.3 static final class FJOPACombineInPlace extends FJBase {
570 dl 1.4 final ParallelArrayWithMapping other;
571 dl 1.3 final int otherOffset;
572     final BinaryOp combiner;
573 jsr166 1.7 FJOPACombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
574 dl 1.4 FJBase next,
575     ParallelArrayWithMapping other, int otherOffset,
576     BinaryOp combiner) {
577     super(pap, lo, hi, next);
578 dl 1.3 this.other = other;
579     this.otherOffset = otherOffset;
580     this.combiner = combiner;
581     }
582     FJBase newSubtask(int l, int h, FJBase r) {
583     return new FJOPACombineInPlace
584 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
585 dl 1.3 }
586     void atLeaf(int l, int h) {
587 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
588 dl 1.3 }
589     }
590    
591     static final class FJDPACombineInPlace extends FJBase {
592 dl 1.4 final ParallelDoubleArrayWithDoubleMapping other;
593 dl 1.3 final int otherOffset;
594     final BinaryDoubleOp combiner;
595 jsr166 1.7 FJDPACombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
596     FJBase next,
597     ParallelDoubleArrayWithDoubleMapping other,
598 dl 1.4 int otherOffset, BinaryDoubleOp combiner) {
599     super(pap, lo, hi, next);
600 dl 1.3 this.other = other;
601     this.otherOffset = otherOffset;
602     this.combiner = combiner;
603     }
604     FJBase newSubtask(int l, int h, FJBase r) {
605     return new FJDPACombineInPlace
606 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
607 dl 1.3 }
608     void atLeaf(int l, int h) {
609 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
610 dl 1.3 }
611     }
612    
613     static final class FJLPACombineInPlace extends FJBase {
614 dl 1.4 final ParallelLongArrayWithLongMapping other;
615 dl 1.3 final int otherOffset;
616     final BinaryLongOp combiner;
617 jsr166 1.7 FJLPACombineInPlace(AbstractParallelAnyArray pap, int lo, int hi,
618 dl 1.4 FJBase next,
619 jsr166 1.7 ParallelLongArrayWithLongMapping other,
620 dl 1.4 int otherOffset, BinaryLongOp combiner) {
621     super(pap, lo, hi, next);
622 dl 1.3 this.other = other;
623     this.otherOffset = otherOffset;
624     this.combiner = combiner;
625     }
626     FJBase newSubtask(int l, int h, FJBase r) {
627     return new FJLPACombineInPlace
628 dl 1.4 (pap, l, h, r, other, otherOffset, combiner);
629 dl 1.3 }
630     void atLeaf(int l, int h) {
631 dl 1.4 pap.leafCombineInPlace(l, h, other, otherOffset, combiner);
632 dl 1.3 }
633     }
634    
635 dl 1.1 // stats
636    
637 dl 1.2 static final class FJOStats extends FJBase
638 dl 1.1 implements ParallelArray.SummaryStatistics {
639     final Comparator comparator;
640     public int size() { return size; }
641     public Object min() { return min; }
642     public Object max() { return max; }
643     public int indexOfMin() { return indexOfMin; }
644     public int indexOfMax() { return indexOfMax; }
645     int size;
646     Object min;
647     Object max;
648     int indexOfMin;
649     int indexOfMax;
650 dl 1.4 FJOStats(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
651 dl 1.1 Comparator comparator) {
652 dl 1.4 super(pap, lo, hi, next);
653 dl 1.1 this.comparator = comparator;
654     this.indexOfMin = -1;
655     this.indexOfMax = -1;
656     }
657     FJBase newSubtask(int l, int h, FJBase r) {
658 dl 1.4 return new FJOStats(pap, l, h, r, comparator);
659 dl 1.1 }
660     void onReduce(FJBase right) {
661 dl 1.2 FJOStats r = (FJOStats)right;
662 dl 1.1 size += r.size;
663     updateMin(r.indexOfMin, r.min);
664     updateMax(r.indexOfMax, r.max);
665     }
666     void updateMin(int i, Object x) {
667     if (i >= 0 &&
668     (indexOfMin < 0 || comparator.compare(min, x) > 0)) {
669     min = x;
670     indexOfMin = i;
671     }
672     }
673     void updateMax(int i, Object x) {
674     if (i >= 0 &&
675     (indexOfMax < 0 || comparator.compare(max, x) < 0)) {
676     max = x;
677     indexOfMax = i;
678     }
679     }
680    
681 dl 1.2 void atLeaf(int l, int h) {
682 jsr166 1.7 if (pap.hasFilter())
683 dl 1.2 filteredAtLeaf(l, h);
684 dl 1.4 else {
685     size = h - l;
686     for (int i = l; i < h; ++i) {
687     Object x = pap.oget(i);
688     updateMin(i, x);
689     updateMax(i, x);
690     }
691 dl 1.2 }
692     }
693    
694     void filteredAtLeaf(int l, int h) {
695     for (int i = l; i < h; ++i) {
696 dl 1.4 if (pap.isSelected(i)) {
697     Object x = pap.oget(i);
698 dl 1.2 ++size;
699     updateMin(i, x);
700     updateMax(i, x);
701     }
702     }
703     }
704    
705 dl 1.1 public String toString() {
706     return
707     "size: " + size +
708     " min: " + min + " (index " + indexOfMin +
709     ") max: " + max + " (index " + indexOfMax + ")";
710     }
711    
712     }
713    
714     static final class FJDStats extends FJBase
715     implements ParallelDoubleArray.SummaryStatistics {
716     final DoubleComparator comparator;
717     public int size() { return size; }
718     public double min() { return min; }
719     public double max() { return max; }
720     public double sum() { return sum; }
721     public double average() { return sum / size; }
722     public int indexOfMin() { return indexOfMin; }
723     public int indexOfMax() { return indexOfMax; }
724     int size;
725     double min;
726     double max;
727     double sum;
728     int indexOfMin;
729     int indexOfMax;
730 dl 1.4 FJDStats(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
731 dl 1.1 DoubleComparator comparator) {
732 dl 1.4 super(pap, lo, hi, next);
733 dl 1.1 this.comparator = comparator;
734     this.indexOfMin = -1;
735     this.indexOfMax = -1;
736     this.min = Double.MAX_VALUE;
737     this.max = -Double.MAX_VALUE;
738     }
739     FJBase newSubtask(int l, int h, FJBase r) {
740 dl 1.4 return new FJDStats(pap, l, h, r, comparator);
741 dl 1.1 }
742     void onReduce(FJBase right) {
743     FJDStats r = (FJDStats)right;
744     size += r.size;
745     sum += r.sum;
746     updateMin(r.indexOfMin, r.min);
747     updateMax(r.indexOfMax, r.max);
748     }
749     void updateMin(int i, double x) {
750     if (i >= 0 &&
751     (indexOfMin < 0 || comparator.compare(min, x) > 0)) {
752     min = x;
753     indexOfMin = i;
754     }
755     }
756     void updateMax(int i, double x) {
757     if (i >= 0 &&
758     (indexOfMax < 0 || comparator.compare(max, x) < 0)) {
759     max = x;
760     indexOfMax = i;
761     }
762     }
763 dl 1.4 void atLeaf(int l, int h) {
764 jsr166 1.7 if (pap.hasFilter())
765 dl 1.2 filteredAtLeaf(l, h);
766 dl 1.4 else {
767     size = h - l;
768     for (int i = l; i < h; ++i) {
769     double x = pap.dget(i);
770     sum += x;
771     updateMin(i, x);
772     updateMax(i, x);
773     }
774 dl 1.2 }
775     }
776    
777     void filteredAtLeaf(int l, int h) {
778     for (int i = l; i < h; ++i) {
779 dl 1.4 if (pap.isSelected(i)) {
780     double x = pap.dget(i);
781 dl 1.2 ++size;
782     sum += x;
783     updateMin(i, x);
784     updateMax(i, x);
785     }
786     }
787     }
788    
789 dl 1.1 public String toString() {
790     return
791     "size: " + size +
792     " min: " + min + " (index " + indexOfMin +
793     ") max: " + max + " (index " + indexOfMax +
794     ") sum: " + sum;
795     }
796     }
797    
798     static final class FJLStats extends FJBase
799     implements ParallelLongArray.SummaryStatistics {
800     final LongComparator comparator;
801     public int size() { return size; }
802     public long min() { return min; }
803     public long max() { return max; }
804     public long sum() { return sum; }
805     public double average() { return (double)sum / size; }
806     public int indexOfMin() { return indexOfMin; }
807     public int indexOfMax() { return indexOfMax; }
808     int size;
809     long min;
810     long max;
811     long sum;
812     int indexOfMin;
813     int indexOfMax;
814 dl 1.4 FJLStats(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
815 dl 1.1 LongComparator comparator) {
816 dl 1.4 super(pap, lo, hi, next);
817 dl 1.1 this.comparator = comparator;
818     this.indexOfMin = -1;
819     this.indexOfMax = -1;
820     this.min = Long.MAX_VALUE;
821     this.max = Long.MIN_VALUE;
822     }
823     FJBase newSubtask(int l, int h, FJBase r) {
824 dl 1.4 return new FJLStats(pap, l, h, r, comparator);
825 dl 1.1 }
826     void onReduce(FJBase right) {
827     FJLStats r = (FJLStats)right;
828     size += r.size;
829     sum += r.sum;
830     updateMin(r.indexOfMin, r.min);
831     updateMax(r.indexOfMax, r.max);
832     }
833     void updateMin(int i, long x) {
834     if (i >= 0 &&
835     (indexOfMin < 0 || comparator.compare(min, x) > 0)) {
836     min = x;
837     indexOfMin = i;
838     }
839     }
840     void updateMax(int i, long x) {
841     if (i >= 0 &&
842     (indexOfMax < 0 || comparator.compare(max, x) < 0)) {
843     max = x;
844     indexOfMax = i;
845     }
846     }
847    
848 dl 1.2 void atLeaf(int l, int h) {
849 jsr166 1.7 if (pap.hasFilter())
850 dl 1.2 filteredAtLeaf(l, h);
851 dl 1.4 else {
852     size = h - l;
853     for (int i = l; i < h; ++i) {
854     long x = pap.lget(i);
855     sum += x;
856     updateMin(i, x);
857     updateMax(i, x);
858     }
859 dl 1.2 }
860     }
861    
862     void filteredAtLeaf(int l, int h) {
863     for (int i = l; i < h; ++i) {
864 dl 1.4 if (pap.isSelected(i)) {
865     long x = pap.lget(i);
866 dl 1.2 ++size;
867     sum += x;
868     updateMin(i, x);
869     updateMax(i, x);
870     }
871     }
872     }
873    
874 dl 1.1 public String toString() {
875     return
876     "size: " + size +
877     " min: " + min + " (index " + indexOfMin +
878     ") max: " + max + " (index " + indexOfMax +
879     ") sum: " + sum;
880     }
881     }
882    
883     // count
884    
885 dl 1.4 static final class FJCountSelected extends FJBase {
886 dl 1.1 int count;
887 jsr166 1.7 FJCountSelected(AbstractParallelAnyArray pap, int lo, int hi,
888 dl 1.4 FJBase next) {
889     super(pap, lo, hi, next);
890 dl 1.1 }
891     FJBase newSubtask(int l, int h, FJBase r) {
892 dl 1.4 return new FJCountSelected(pap, l, h, r);
893 dl 1.1 }
894     void onReduce(FJBase right) {
895 dl 1.4 count += ((FJCountSelected)right).count;
896 dl 1.1 }
897     void atLeaf(int l, int h) {
898 dl 1.4 int n = 0;
899     for (int i = l; i < h; ++i) {
900     if (pap.isSelected(i))
901     ++n;
902 dl 1.1 }
903 dl 1.4 count = n;
904 dl 1.1 }
905     }
906    
907     /**
908     * Base for cancellable search tasks. Same idea as FJBase
909     * but cancels tasks when result nonnegative.
910     */
911     static abstract class FJSearchBase extends RecursiveAction {
912 dl 1.4 final AbstractParallelAnyArray pap;
913 dl 1.1 final int lo;
914     final int hi;
915     final FJSearchBase next;
916     final AtomicInteger result;
917    
918 dl 1.4 FJSearchBase(AbstractParallelAnyArray pap, int lo, int hi,
919 dl 1.1 FJSearchBase next,
920     AtomicInteger result) {
921 dl 1.4 this.pap = pap;
922 dl 1.1 this.lo = lo;
923     this.hi = hi;
924     this.next = next;
925     this.result = result;
926     }
927    
928     public void compute() {
929     if (result.get() >= 0)
930     return;
931     FJSearchBase r = null;
932     int l = lo;
933     int h = hi;
934 dl 1.4 int g = pap.getThreshold();
935 dl 1.3 while (h - l > g) {
936 dl 1.1 int rh = h;
937     h = (l + h) >>> 1;
938     (r = newSubtask(h, rh, r)).fork();
939     }
940     atLeaf(l, h);
941     boolean stopping = false;
942     while (r != null) {
943     stopping |= result.get() >= 0;
944     if (ForkJoinWorkerThread.removeIfNextLocalTask(r)) {
945     if (!stopping)
946     r.atLeaf(r.lo, r.hi);
947     }
948     else if (stopping)
949     r.cancel();
950     else
951     r.join();
952     r = r.next;
953     }
954     }
955     abstract FJSearchBase newSubtask(int l, int h, FJSearchBase r);
956     abstract void atLeaf(int l, int h);
957     }
958    
959     // select any
960    
961 dl 1.4 static final class FJSelectAny extends FJSearchBase {
962 jsr166 1.7 FJSelectAny(AbstractParallelAnyArray pap, int lo, int hi,
963 dl 1.4 FJSearchBase next, AtomicInteger result) {
964     super(pap, lo, hi, next, result);
965 dl 1.1 }
966     FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
967 dl 1.4 return new FJSelectAny(pap, l, h, r, result);
968 dl 1.1 }
969     void atLeaf(int l, int h) {
970     for (int i = l; i < h; ++i) {
971 dl 1.4 if (pap.isSelected(i)) {
972 dl 1.1 result.compareAndSet(-1, i);
973     break;
974     }
975     else if (result.get() >= 0)
976     break;
977     }
978     }
979     }
980    
981     // index of
982    
983 dl 1.2 static final class FJOIndexOf extends FJSearchBase {
984 dl 1.1 final Object target;
985 jsr166 1.7 FJOIndexOf(AbstractParallelAnyArray pap, int lo, int hi,
986 dl 1.4 FJSearchBase next, AtomicInteger result, Object target) {
987     super(pap, lo, hi, next, result);
988 dl 1.1 this.target = target;
989     }
990     FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
991 dl 1.4 return new FJOIndexOf(pap, l, h, r, result, target);
992 dl 1.1 }
993     void atLeaf(int l, int h) {
994 dl 1.4 final Object[] array = pap.ogetArray();
995 dl 1.1 if (array == null) return;
996     for (int i = l; i < h; ++i) {
997     if (target.equals(array[i])) {
998     result.compareAndSet(-1, i);
999     break;
1000     }
1001     else if (result.get() >= 0)
1002     break;
1003     }
1004     }
1005     }
1006    
1007     static final class FJDIndexOf extends FJSearchBase {
1008     final double target;
1009 jsr166 1.7 FJDIndexOf(AbstractParallelAnyArray pap, int lo, int hi,
1010 dl 1.4 FJSearchBase next, AtomicInteger result, double target) {
1011     super(pap, lo, hi, next, result);
1012 dl 1.1 this.target = target;
1013     }
1014     FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
1015 dl 1.4 return new FJDIndexOf(pap, l, h, r, result, target);
1016 dl 1.1 }
1017     void atLeaf(int l, int h) {
1018 dl 1.4 final double[] array = pap.dgetArray();
1019 dl 1.1 if (array == null) return;
1020     for (int i = l; i < h; ++i) {
1021     if (target == (array[i])) {
1022     result.compareAndSet(-1, i);
1023     break;
1024     }
1025     else if (result.get() >= 0)
1026     break;
1027     }
1028     }
1029     }
1030    
1031     static final class FJLIndexOf extends FJSearchBase {
1032     final long target;
1033 jsr166 1.7 FJLIndexOf(AbstractParallelAnyArray pap, int lo, int hi,
1034 dl 1.4 FJSearchBase next, AtomicInteger result, long target) {
1035     super(pap, lo, hi, next, result);
1036 dl 1.1 this.target = target;
1037     }
1038     FJSearchBase newSubtask(int l, int h, FJSearchBase r) {
1039 dl 1.4 return new FJLIndexOf(pap, l, h, r, result, target);
1040 dl 1.1 }
1041     void atLeaf(int l, int h) {
1042 dl 1.4 final long[] array = pap.lgetArray();
1043 dl 1.1 if (array == null) return;
1044     for (int i = l; i < h; ++i) {
1045     if (target == (array[i])) {
1046     result.compareAndSet(-1, i);
1047     break;
1048     }
1049     else if (result.get() >= 0)
1050     break;
1051     }
1052     }
1053     }
1054    
1055     // select all
1056    
1057     /**
1058 dl 1.2 * SelectAll proceeds in two passes. In the first phase, indices
1059     * of matching elements are recorded in indices array. In second
1060     * pass, once the size of results is known and result array is
1061 dl 1.1 * constructed in driver, the matching elements are placed into
1062     * corresponding result positions.
1063     */
1064     static final class FJSelectAll extends RecursiveAction {
1065     final FJSelectAllDriver driver;
1066     FJSelectAll left, right;
1067     final int lo;
1068     final int hi;
1069     int count; // number of matching elements
1070     int offset;
1071     boolean isInternal; // true if this is a non-leaf node
1072    
1073     FJSelectAll(FJSelectAllDriver driver, int lo, int hi) {
1074     this.driver = driver;
1075     this.lo = lo;
1076     this.hi = hi;
1077     }
1078    
1079     public void compute() {
1080 dl 1.3 int l = lo;
1081     int h = hi;
1082 dl 1.1 FJSelectAllDriver d = driver;
1083     if (d.phase == 0) {
1084 dl 1.4 AbstractParallelAnyArray p = d.pap;
1085 dl 1.3 if (isInternal = (h - l > p.getThreshold()))
1086 dl 1.1 internalPhase0();
1087     else
1088 dl 1.3 count = p.leafIndexSelected(l, h, true, d.indices);
1089 dl 1.1 }
1090     else if (count != 0) {
1091     if (isInternal)
1092     internalPhase1();
1093     else
1094 dl 1.3 d.leafPhase1(l, l+count, offset);
1095 dl 1.1 }
1096     }
1097    
1098     void internalPhase0() {
1099     int mid = (lo + hi) >>> 1;
1100     FJSelectAll l = new FJSelectAll(driver, lo, mid);
1101     FJSelectAll r = new FJSelectAll(driver, mid, hi);
1102     forkJoin(l, r);
1103     int ln = l.count;
1104     if (ln != 0)
1105     left = l;
1106     int rn = r.count;
1107     if (rn != 0)
1108     right = r;
1109     count = ln + rn;
1110     }
1111    
1112     void internalPhase1() {
1113     int k = offset;
1114     if (left != null) {
1115     int ln = left.count;
1116     left.offset = k;
1117     left.reinitialize();
1118     if (right != null) {
1119     right.offset = k + ln;
1120     right.reinitialize();
1121     forkJoin(left, right);
1122     }
1123     else
1124     left.compute();
1125     }
1126     else if (right != null) {
1127     right.offset = k;
1128     right.compute();
1129     }
1130     }
1131     }
1132    
1133     static abstract class FJSelectAllDriver extends RecursiveAction {
1134     final int[] indices;
1135 dl 1.4 final AbstractParallelAnyArray pap;
1136     final int initialOffset;
1137 dl 1.1 int phase;
1138 dl 1.4 int resultSize;
1139     FJSelectAllDriver(AbstractParallelAnyArray pap, int initialOffset) {
1140     this.pap = pap;
1141     this.initialOffset = initialOffset;
1142     int n = pap.fence - pap.origin;
1143 dl 1.1 indices = new int[n];
1144     }
1145     public final void compute() {
1146 dl 1.4 FJSelectAll r = new FJSelectAll(this, pap.origin, pap.fence);
1147     r.offset = initialOffset;
1148 dl 1.1 r.compute();
1149 dl 1.4 createResults(resultSize = r.count);
1150 dl 1.1 phase = 1;
1151     r.compute();
1152     }
1153     abstract void createResults(int size);
1154     abstract void leafPhase1(int loIdx, int hiIdx, int offset);
1155     }
1156    
1157 dl 1.2 static final class FJOSelectAllDriver extends FJSelectAllDriver {
1158 dl 1.1 final Class elementType;
1159     Object[] results;
1160 dl 1.4 FJOSelectAllDriver(AbstractParallelAnyArray pap, Class elementType) {
1161     super(pap, 0);
1162 dl 1.1 this.elementType = elementType;
1163     }
1164     void createResults(int size) {
1165     results = (Object[])Array.newInstance(elementType, size);
1166     }
1167     void leafPhase1(int loIdx, int hiIdx, int offset) {
1168 dl 1.4 pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1169 dl 1.1 }
1170     }
1171    
1172     static final class FJDSelectAllDriver extends FJSelectAllDriver {
1173     double[] results;
1174 dl 1.4 FJDSelectAllDriver(AbstractParallelAnyArray pap) {
1175     super(pap, 0);
1176 dl 1.1 }
1177     void createResults(int size) {
1178     results = new double[size];
1179     }
1180     void leafPhase1(int loIdx, int hiIdx, int offset) {
1181 dl 1.4 pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1182 dl 1.1 }
1183     }
1184    
1185     static final class FJLSelectAllDriver extends FJSelectAllDriver {
1186     long[] results;
1187 dl 1.4 FJLSelectAllDriver(AbstractParallelAnyArray pap) {
1188     super(pap, 0);
1189 dl 1.1 }
1190     void createResults(int size) {
1191     results = new long[size];
1192     }
1193     void leafPhase1(int loIdx, int hiIdx, int offset) {
1194 dl 1.4 pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1195     }
1196     }
1197    
1198     static final class FJOAppendAllDriver extends FJSelectAllDriver {
1199     Object[] results;
1200 jsr166 1.7 FJOAppendAllDriver(AbstractParallelAnyArray pap, int initialOffset,
1201 dl 1.4 Object[] results) {
1202     super(pap, 0);
1203     this.results = results;
1204     }
1205     void createResults(int size) {
1206     int newSize = initialOffset + size;
1207     int oldLength = results.length;
1208     if (newSize > oldLength) {
1209     Class elementType = results.getClass().getComponentType();
1210     Object[] r = (Object[])Array.newInstance(elementType, newSize);
1211     System.arraycopy(results, 0, r, 0, oldLength);
1212     results = r;
1213     }
1214     }
1215     void leafPhase1(int loIdx, int hiIdx, int offset) {
1216     pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1217     }
1218     }
1219    
1220     static final class FJDAppendAllDriver extends FJSelectAllDriver {
1221     double[] results;
1222 jsr166 1.7 FJDAppendAllDriver(AbstractParallelAnyArray pap, int initialOffset,
1223 dl 1.4 double[] results) {
1224     super(pap, initialOffset);
1225     this.results = results;
1226     }
1227     void createResults(int size) {
1228     int newSize = initialOffset + size;
1229     int oldLength = results.length;
1230     if (newSize > oldLength) {
1231     double[] r = new double[newSize];
1232     System.arraycopy(results, 0, r, 0, oldLength);
1233     results = r;
1234     }
1235     }
1236     void leafPhase1(int loIdx, int hiIdx, int offset) {
1237     pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1238     }
1239     }
1240    
1241     static final class FJLAppendAllDriver extends FJSelectAllDriver {
1242     long[] results;
1243 jsr166 1.7 FJLAppendAllDriver(AbstractParallelAnyArray pap, int initialOffset,
1244 dl 1.4 long[] results) {
1245     super(pap, initialOffset);
1246     this.results = results;
1247     }
1248     void createResults(int size) {
1249     int newSize = initialOffset + size;
1250     int oldLength = results.length;
1251     if (newSize > oldLength) {
1252     long[] r = new long[newSize];
1253     System.arraycopy(results, 0, r, 0, oldLength);
1254     results = r;
1255     }
1256     }
1257     void leafPhase1(int loIdx, int hiIdx, int offset) {
1258     pap.leafTransferByIndex(indices, loIdx, hiIdx, results, offset);
1259 dl 1.1 }
1260     }
1261    
1262 dl 1.4
1263 dl 1.1 /**
1264     * Root node for FJRemoveAll. Spawns subtasks and shifts elements
1265     * as indices become available, bypassing index array creation
1266     * when offsets are known. This differs from SelectAll mainly in
1267     * that data movement is all done by the driver rather than in a
1268     * second parallel pass.
1269     */
1270     static final class FJRemoveAllDriver extends RecursiveAction {
1271 dl 1.4 final AbstractParallelAnyArray pap;
1272 dl 1.1 final int lo;
1273     final int hi;
1274     final int[] indices;
1275     int offset;
1276 dl 1.4 FJRemoveAllDriver(AbstractParallelAnyArray pap, int lo, int hi) {
1277     this.pap = pap;
1278 dl 1.1 this.lo = lo;
1279     this.hi = hi;
1280     this.indices = new int[hi - lo];
1281     }
1282    
1283     public void compute() {
1284     FJRemoveAll r = null;
1285     int l = lo;
1286     int h = hi;
1287 dl 1.4 int g = pap.getThreshold();
1288 dl 1.3 while (h - l > g) {
1289 dl 1.1 int rh = h;
1290     h = (l + h) >>> 1;
1291 dl 1.4 (r = new FJRemoveAll(pap, h, rh, r, indices)).fork();
1292 dl 1.1 }
1293 dl 1.4 int k = pap.leafMoveSelected(l, h, l, false);
1294 dl 1.1 while (r != null) {
1295     if (ForkJoinWorkerThread.removeIfNextLocalTask(r))
1296 dl 1.4 k = pap.leafMoveSelected(r.lo, r.hi, k, false);
1297 dl 1.1 else {
1298     r.join();
1299     int n = r.count;
1300     if (n != 0)
1301 dl 1.4 pap.leafMoveByIndex(indices, r.lo, r.lo+n, k);
1302 dl 1.1 k += n;
1303     FJRemoveAll rr = r.right;
1304     if (rr != null)
1305     k = inorderMove(rr, k);
1306     }
1307     r = r.next;
1308     }
1309     offset = k;
1310     }
1311    
1312     /**
1313     * Inorder traversal to move indexed elements across reachable
1314     * nodes. This guarantees that element shifts don't overwrite
1315     * those still being used by active subtasks.
1316     */
1317     static int inorderMove(FJRemoveAll t, int index) {
1318     while (t != null) {
1319     int n = t.count;
1320     if (n != 0)
1321 dl 1.4 t.pap.leafMoveByIndex(t.indices, t.lo, t.lo+n, index);
1322 dl 1.1 index += n;
1323     FJRemoveAll p = t.next;
1324     if (p != null)
1325     index = inorderMove(p, index);
1326     t = t.right;
1327     }
1328     return index;
1329     }
1330     }
1331    
1332     /**
1333 dl 1.3 * Basic FJ tssk for non-root FJRemoveAll nodes. Differs from
1334     * FJBase because it requires maintaing explicit right pointers so
1335     * FJRemoveAllDriver can traverse them
1336 dl 1.1 */
1337     static final class FJRemoveAll extends RecursiveAction {
1338 dl 1.4 final AbstractParallelAnyArray pap;
1339 dl 1.1 final int lo;
1340     final int hi;
1341     final FJRemoveAll next;
1342     final int[] indices;
1343     int count;
1344     FJRemoveAll right;
1345 jsr166 1.7 FJRemoveAll(AbstractParallelAnyArray pap, int lo, int hi,
1346 dl 1.4 FJRemoveAll next, int[] indices) {
1347     this.pap = pap;
1348 dl 1.1 this.lo = lo;
1349     this.hi = hi;
1350     this.next = next;
1351     this.indices = indices;
1352     }
1353    
1354     public void compute() {
1355     FJRemoveAll r = null;
1356     int l = lo;
1357     int h = hi;
1358 dl 1.4 int g = pap.getThreshold();
1359 dl 1.3 while (h - l > g) {
1360 dl 1.1 int rh = h;
1361     h = (l + h) >>> 1;
1362 dl 1.4 (r = new FJRemoveAll(pap, h, rh, r, indices)).fork();
1363 dl 1.1 }
1364     right = r;
1365 dl 1.4 count = pap.leafIndexSelected(l, h, false, indices);
1366 dl 1.1 while (r != null) {
1367     if (ForkJoinWorkerThread.removeIfNextLocalTask(r))
1368 dl 1.4 r.count = pap.leafIndexSelected
1369 dl 1.1 (r.lo, r.hi, false, indices);
1370     else
1371     r.join();
1372     r = r.next;
1373     }
1374     }
1375     }
1376    
1377     // unique elements
1378    
1379 dl 1.4 static final class FJOUniquifier extends FJBase {
1380     final UniquifierTable table;
1381     int count;
1382     FJOUniquifier(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
1383     UniquifierTable table) {
1384     super(pap, lo, hi, next);
1385     this.table = table;
1386     }
1387     FJBase newSubtask(int l, int h, FJBase r) {
1388     return new FJOUniquifier(pap, l, h, r, table);
1389     }
1390     void atLeaf(int l, int h) {
1391     count = table.addObjects(l, h);
1392     }
1393     void onReduce(FJBase right) {
1394     count += ((FJOUniquifier)right).count;
1395     }
1396     }
1397    
1398     static final class FJDUniquifier extends FJBase {
1399 dl 1.1 final UniquifierTable table;
1400     int count;
1401 dl 1.4 FJDUniquifier(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
1402 dl 1.1 UniquifierTable table) {
1403 dl 1.4 super(pap, lo, hi, next);
1404     this.table = table;
1405     }
1406     FJBase newSubtask(int l, int h, FJBase r) {
1407     return new FJDUniquifier(pap, l, h, r, table);
1408     }
1409     void atLeaf(int l, int h) {
1410     count = table.addDoubles(l, h);
1411     }
1412     void onReduce(FJBase right) {
1413     count += ((FJDUniquifier)right).count;
1414     }
1415     }
1416    
1417     static final class FJLUniquifier extends FJBase {
1418     final UniquifierTable table;
1419     int count;
1420     FJLUniquifier(AbstractParallelAnyArray pap, int lo, int hi, FJBase next,
1421     UniquifierTable table) {
1422     super(pap, lo, hi, next);
1423 dl 1.1 this.table = table;
1424     }
1425     FJBase newSubtask(int l, int h, FJBase r) {
1426 dl 1.4 return new FJLUniquifier(pap, l, h, r, table);
1427 dl 1.1 }
1428     void atLeaf(int l, int h) {
1429 dl 1.4 count = table.addLongs(l, h);
1430 dl 1.1 }
1431     void onReduce(FJBase right) {
1432 dl 1.4 count += ((FJLUniquifier)right).count;
1433 dl 1.1 }
1434     }
1435    
1436     /**
1437     * Base class of fixed-size hash tables for
1438     * uniquification. Opportunistically subclasses
1439     * AtomicLongArray. The high word of each slot is the cached
1440     * massaged hash of an element, and the low word contains its
1441     * index, plus one, to ensure that a zero tab entry means
1442     * empty. The mechanics for this are just folded into the
1443     * main addElements method.
1444     * Each leaf step places source array elements into table,
1445     * Even though this table undergoes a lot of contention when
1446     * elements are concurrently inserted by parallel threads, it is
1447     * generally faster to do this than to have separate tables and
1448     * then merge them.
1449     */
1450 dl 1.4 static final class UniquifierTable extends AtomicLongArray {
1451     final AbstractParallelAnyArray pap;
1452     final boolean byIdentity;
1453 jsr166 1.7 UniquifierTable(int size, AbstractParallelAnyArray pap,
1454 dl 1.4 boolean byIdentity) {
1455 dl 1.1 super(tableSizeFor(size));
1456 dl 1.4 this.pap = pap;
1457     this.byIdentity = byIdentity;
1458 dl 1.1 }
1459    
1460     /** Returns a good size for table */
1461     static int tableSizeFor(int n) {
1462     int padded = n + (n >>> 1) + 1;
1463     if (padded < n) // int overflow
1464     throw new OutOfMemoryError();
1465     int s = 8;
1466     while (s < padded) s <<= 1;
1467     return s;
1468     }
1469    
1470     // Same hashcode conditioning as HashMap
1471     static int hash(int h) {
1472     h ^= (h >>> 20) ^ (h >>> 12);
1473     return h ^ (h >>> 7) ^ (h >>> 4);
1474     }
1475    
1476 dl 1.4 int addObjects(int lo, int hi) {
1477     boolean filtered = pap.hasFilter();
1478     Object[] src = pap.ogetArray();
1479 dl 1.1 final int mask = length() - 1;
1480     int count = 0;
1481     for (int k = lo; k < hi; ++k) {
1482 dl 1.4 Object x;
1483     if ((filtered && !pap.isSelected(k)) ||
1484     (x = src[k]) == null)
1485 dl 1.1 continue;
1486     int hc = byIdentity? System.identityHashCode(x): x.hashCode();
1487     int hash = hash(hc);
1488     long entry = (((long)hash) << 32) + (k + 1);
1489     int idx = hash & mask;
1490     for (;;) {
1491     long d = get(idx);
1492     if (d != 0) {
1493     if ((int)(d >>> 32) == hash) {
1494 dl 1.4 Object y = src[(int)((d-1) & 0x7fffffffL)];
1495 dl 1.6 if (x == y || (!byIdentity && x.equals(y)))
1496 dl 1.1 break;
1497     }
1498     idx = (idx + 1) & mask;
1499     }
1500     else if (compareAndSet(idx, 0, entry)) {
1501     ++count;
1502     break;
1503     }
1504     }
1505     }
1506     return count;
1507     }
1508    
1509 dl 1.4 int addDoubles(int lo, int hi) {
1510     boolean filtered = pap.hasFilter();
1511     double[] src = pap.dgetArray();
1512 dl 1.1 final int mask = length() - 1;
1513     int count = 0;
1514     for (int k = lo; k < hi; ++k) {
1515 dl 1.4 if (filtered && !pap.isSelected(k))
1516     continue;
1517 dl 1.1 double x = src[k];
1518     long bits = Double.doubleToLongBits(x);
1519     int hash = hash((int)(bits ^ (bits >>> 32)));;
1520     long entry = (((long)hash) << 32) + (k + 1);
1521     int idx = hash & mask;
1522     for (;;) {
1523     long d = get(idx);
1524     if (d != 0) {
1525     if ((int)(d >>> 32) == hash &&
1526 dl 1.4 x == src[(int)((d - 1) & 0x7fffffffL)])
1527 dl 1.1 break;
1528     idx = (idx + 1) & mask;
1529     }
1530     else if (compareAndSet(idx, 0, entry)) {
1531     ++count;
1532     break;
1533     }
1534     }
1535     }
1536     return count;
1537     }
1538    
1539 dl 1.4 int addLongs(int lo, int hi) {
1540     boolean filtered = pap.hasFilter();
1541     long[] src = pap.lgetArray();
1542 dl 1.1 final int mask = length() - 1;
1543     int count = 0;
1544     for (int k = lo; k < hi; ++k) {
1545 dl 1.4 if (filtered && !pap.isSelected(k))
1546     continue;
1547 dl 1.1 long x = src[k];
1548     int hash = hash((int)(x ^ (x >>> 32)));
1549     long entry = (((long)hash) << 32) + (k + 1);
1550     int idx = hash & mask;
1551     for (;;) {
1552     long d = get(idx);
1553     if (d != 0) {
1554     if ((int)(d >>> 32) == hash &&
1555 dl 1.4 x == src[(int)((d - 1) & 0x7fffffffL)])
1556 dl 1.1 break;
1557     idx = (idx + 1) & mask;
1558     }
1559     else if (compareAndSet(idx, 0, entry)) {
1560     ++count;
1561     break;
1562     }
1563     }
1564     }
1565     return count;
1566     }
1567    
1568 dl 1.4 /**
1569     * Return new array holding all elements.
1570     */
1571     Object[] uniqueObjects(int size) {
1572     Object[] src = pap.ogetArray();
1573     Class sclass = src.getClass().getComponentType();
1574     Object[] res = (Object[])Array.newInstance(sclass, size);
1575     int k = 0;
1576     int n = length();
1577     for (int i = 0; i < n && k < size; ++i) {
1578     long d = get(i);
1579     if (d != 0)
1580     res[k++] = src[((int)((d - 1) & 0x7fffffffL))];
1581     }
1582     return res;
1583     }
1584    
1585     double[] uniqueDoubles(int size) {
1586     double[] src = pap.dgetArray();
1587     double[] res = new double[size];
1588     int k = 0;
1589     int n = length();
1590     for (int i = 0; i < n && k < size; ++i) {
1591     long d = get(i);
1592     if (d != 0)
1593     res[k++] = src[((int)((d - 1) & 0x7fffffffL))];
1594     }
1595     return res;
1596     }
1597    
1598     long[] uniqueLongs(int size) {
1599     long[] src = pap.lgetArray();
1600 dl 1.1 long[] res = new long[size];
1601     int k = 0;
1602     int n = length();
1603     for (int i = 0; i < n && k < size; ++i) {
1604     long d = get(i);
1605     if (d != 0)
1606     res[k++] = src[((int)((d - 1) & 0x7fffffffL))];
1607     }
1608     return res;
1609     }
1610     }
1611    
1612     /**
1613     * Sorter classes based mainly on CilkSort
1614     * <A href="http://supertech.lcs.mit.edu/cilk/"> Cilk</A>:
1615     * Basic algorithm:
1616     * if array size is small, just use a sequential quicksort
1617     * Otherwise:
1618     * 1. Break array in half.
1619     * 2. For each half,
1620     * a. break the half in half (i.e., quarters),
1621     * b. sort the quarters
1622     * c. merge them together
1623     * 3. merge together the two halves.
1624     *
1625     * One reason for splitting in quarters is that this guarantees
1626     * that the final sort is in the main array, not the workspace
1627     * array. (workspace and main swap roles on each subsort step.)
1628     * Leaf-level sorts use a Sequential quicksort, that in turn uses
1629     * insertion sort if under threshold. Otherwise it uses median of
1630     * three to pick pivot, and loops rather than recurses along left
1631     * path.
1632     *
1633     * It is sad but true that sort and merge performance are
1634     * sensitive enough to inner comparison overhead to warrant
1635     * creating 6 versions (not just 3) -- one each for natural
1636     * comparisons vs supplied comparators.
1637     */
1638 dl 1.2 static final class FJOSorter extends RecursiveAction {
1639 dl 1.1 final Comparator cmp;
1640     final Object[] a; // array to be sorted.
1641     final Object[] w; // workspace for merge
1642     final int origin; // origin of the part of array we deal with
1643     final int n; // Number of elements in (sub)arrays.
1644     final int gran; // split control
1645 dl 1.2 FJOSorter(Comparator cmp,
1646 dl 1.1 Object[] a, Object[] w, int origin, int n, int gran) {
1647     this.cmp = cmp;
1648     this.a = a; this.w = w; this.origin = origin; this.n = n;
1649     this.gran = gran;
1650     }
1651    
1652     public void compute() {
1653     int l = origin;
1654     int g = gran;
1655     if (n > g) {
1656     int h = n >>> 1; // half
1657     int q = n >>> 2; // lower quarter index
1658     int u = h + q; // upper quarter
1659     forkJoin(new FJSubSorter
1660 dl 1.2 (new FJOSorter(cmp, a, w, l, q, g),
1661     new FJOSorter(cmp, a, w, l+q, h-q, g),
1662     new FJOMerger(cmp, a, w, l, q,
1663 dl 1.1 l+q, h-q, l, g, null)),
1664     new FJSubSorter
1665 dl 1.2 (new FJOSorter(cmp, a, w, l+h, q, g),
1666     new FJOSorter(cmp, a, w, l+u, n-u, g),
1667     new FJOMerger(cmp, a, w, l+h, q,
1668 dl 1.1 l+u, n-u, l+h, g, null)));
1669 dl 1.2 new FJOMerger(cmp, w, a, l, h,
1670 dl 1.1 l+h, n-h, l, g, null).compute();
1671     }
1672     else
1673 dl 1.2 oquickSort(a, cmp, l, l+n-1);
1674 dl 1.1 }
1675     }
1676    
1677 dl 1.2 static final class FJOCSorter extends RecursiveAction {
1678 dl 1.1 final Comparable[] a; final Comparable[] w;
1679     final int origin; final int n; final int gran;
1680 dl 1.2 FJOCSorter(Comparable[] a, Comparable[] w,
1681 dl 1.1 int origin, int n, int gran) {
1682     this.a = a; this.w = w; this.origin = origin; this.n = n;
1683     this.gran = gran;
1684     }
1685     public void compute() {
1686     int l = origin;
1687     int g = gran;
1688     if (n > g) {
1689     int h = n >>> 1;
1690     int q = n >>> 2;
1691     int u = h + q;
1692     forkJoin(new FJSubSorter
1693 dl 1.2 (new FJOCSorter(a, w, l, q, g),
1694     new FJOCSorter(a, w, l+q, h-q, g),
1695     new FJOCMerger(a, w, l, q,
1696 dl 1.1 l+q, h-q, l, g, null)),
1697     new FJSubSorter
1698 dl 1.2 (new FJOCSorter(a, w, l+h, q, g),
1699     new FJOCSorter(a, w, l+u, n-u, g),
1700     new FJOCMerger(a, w, l+h, q,
1701 dl 1.1 l+u, n-u, l+h, g, null)));
1702 dl 1.2 new FJOCMerger(w, a, l, h,
1703 dl 1.1 l+h, n-h, l, g, null).compute();
1704     }
1705     else
1706 dl 1.2 ocquickSort(a, l, l+n-1);
1707 dl 1.1 }
1708     }
1709    
1710     static final class FJDSorter extends RecursiveAction {
1711     final DoubleComparator cmp; final double[] a; final double[] w;
1712     final int origin; final int n; final int gran;
1713     FJDSorter(DoubleComparator cmp,
1714     double[] a, double[] w, int origin, int n, int gran) {
1715     this.cmp = cmp;
1716     this.a = a; this.w = w; this.origin = origin; this.n = n;
1717     this.gran = gran;
1718     }
1719     public void compute() {
1720     int l = origin;
1721     int g = gran;
1722     if (n > g) {
1723     int h = n >>> 1;
1724     int q = n >>> 2;
1725     int u = h + q;
1726     forkJoin(new FJSubSorter
1727     (new FJDSorter(cmp, a, w, l, q, g),
1728     new FJDSorter(cmp, a, w, l+q, h-q, g),
1729     new FJDMerger(cmp, a, w, l, q,
1730     l+q, h-q, l, g, null)),
1731     new FJSubSorter
1732     (new FJDSorter(cmp, a, w, l+h, q, g),
1733     new FJDSorter(cmp, a, w, l+u, n-u, g),
1734     new FJDMerger(cmp, a, w, l+h, q,
1735     l+u, n-u, l+h, g, null)));
1736     new FJDMerger(cmp, w, a, l, h,
1737     l+h, n-h, l, g, null).compute();
1738     }
1739     else
1740     dquickSort(a, cmp, l, l+n-1);
1741     }
1742     }
1743    
1744     static final class FJDCSorter extends RecursiveAction {
1745     final double[] a; final double[] w;
1746     final int origin; final int n; final int gran;
1747     FJDCSorter(double[] a, double[] w, int origin,
1748     int n, int gran) {
1749     this.a = a; this.w = w; this.origin = origin; this.n = n;
1750     this.gran = gran;
1751     }
1752     public void compute() {
1753     int l = origin;
1754     int g = gran;
1755     if (n > g) {
1756     int h = n >>> 1;
1757     int q = n >>> 2;
1758     int u = h + q;
1759     forkJoin(new FJSubSorter
1760     (new FJDCSorter(a, w, l, q, g),
1761     new FJDCSorter(a, w, l+q, h-q, g),
1762     new FJDCMerger(a, w, l, q,
1763     l+q, h-q, l, g, null)),
1764     new FJSubSorter
1765     (new FJDCSorter(a, w, l+h, q, g),
1766     new FJDCSorter(a, w, l+u, n-u, g),
1767     new FJDCMerger(a, w, l+h, q,
1768     l+u, n-u, l+h, g, null)));
1769     new FJDCMerger(w, a, l, h,
1770     l+h, n-h, l, g, null).compute();
1771     }
1772     else
1773     dcquickSort(a, l, l+n-1);
1774     }
1775     }
1776    
1777     static final class FJLSorter extends RecursiveAction {
1778     final LongComparator cmp; final long[] a; final long[] w;
1779     final int origin; final int n; final int gran;
1780     FJLSorter(LongComparator cmp,
1781     long[] a, long[] w, int origin, int n, int gran) {
1782     this.cmp = cmp;
1783     this.a = a; this.w = w; this.origin = origin; this.n = n;
1784     this.gran = gran;
1785     }
1786    
1787     public void compute() {
1788     int l = origin;
1789     int g = gran;
1790     if (n > g) {
1791     int h = n >>> 1;
1792     int q = n >>> 2;
1793     int u = h + q;
1794     forkJoin(new FJSubSorter
1795     (new FJLSorter(cmp, a, w, l, q, g),
1796     new FJLSorter(cmp, a, w, l+q, h-q, g),
1797     new FJLMerger(cmp, a, w, l, q,
1798     l+q, h-q, l, g, null)),
1799     new FJSubSorter
1800     (new FJLSorter(cmp, a, w, l+h, q, g),
1801     new FJLSorter(cmp, a, w, l+u, n-u, g),
1802     new FJLMerger(cmp, a, w, l+h, q,
1803     l+u, n-u, l+h, g, null)));
1804     new FJLMerger(cmp, w, a, l, h,
1805     l+h, n-h, l, g, null).compute();
1806     }
1807     else
1808     lquickSort(a, cmp, l, l+n-1);
1809     }
1810     }
1811    
1812     static final class FJLCSorter extends RecursiveAction {
1813     final long[] a; final long[] w;
1814     final int origin; final int n; final int gran;
1815     FJLCSorter(long[] a, long[] w, int origin,
1816     int n, int gran) {
1817     this.a = a; this.w = w; this.origin = origin; this.n = n;
1818     this.gran = gran;
1819     }
1820     public void compute() {
1821     int l = origin;
1822     int g = gran;
1823     if (n > g) {
1824     int h = n >>> 1;
1825     int q = n >>> 2;
1826     int u = h + q;
1827     forkJoin(new FJSubSorter
1828     (new FJLCSorter(a, w, l, q, g),
1829     new FJLCSorter(a, w, l+q, h-q, g),
1830     new FJLCMerger(a, w, l, q,
1831     l+q, h-q, l, g, null)),
1832     new FJSubSorter
1833     (new FJLCSorter(a, w, l+h, q, g),
1834     new FJLCSorter(a, w, l+u, n-u, g),
1835     new FJLCMerger(a, w, l+h, q,
1836     l+u, n-u, l+h, g, null)));
1837     new FJLCMerger(w, a, l, h,
1838     l+h, n-h, l, g, null).compute();
1839     }
1840     else
1841     lcquickSort(a, l, l+n-1);
1842     }
1843     }
1844    
1845     /** Utility class to sort half a partitioned array */
1846     static final class FJSubSorter extends RecursiveAction {
1847     final RecursiveAction left;
1848     final RecursiveAction right;
1849     final RecursiveAction merger;
1850     FJSubSorter(RecursiveAction left, RecursiveAction right,
1851     RecursiveAction merger){
1852     this.left = left; this.right = right; this.merger = merger;
1853     }
1854     public void compute() {
1855     forkJoin(left, right);
1856     merger.compute();
1857     }
1858     }
1859    
1860     /**
1861     * Perform merging for FJSorter. If big enough, splits Left
1862     * partition in half; finds the greatest point in Right partition
1863     * less than the beginning of the second half of Left via binary
1864     * search; and then, in parallel, merges left half of Left with
1865     * elements of Right up to split point, and merges right half of
1866     * Left with elements of R past split point. At leaf, it just
1867     * sequentially merges. This is all messy to code; sadly we need
1868     * six versions.
1869     */
1870 dl 1.2 static final class FJOMerger extends RecursiveAction {
1871 dl 1.1 final Comparator cmp;
1872     final Object[] a; // partitioned array.
1873     final Object[] w; // Output array.
1874     final int lo; // relative origin of left side of a
1875     final int ln; // number of elements on left of a
1876     final int ro; // relative origin of right side of a
1877     final int rn; // number of elements on right of a
1878     final int wo; // origin for output
1879     final int gran;
1880 dl 1.2 final FJOMerger next;
1881 dl 1.1
1882 dl 1.2 FJOMerger(Comparator cmp, Object[] a, Object[] w,
1883 dl 1.1 int lo, int ln, int ro, int rn, int wo,
1884 dl 1.2 int gran, FJOMerger next) {
1885 dl 1.1 this.cmp = cmp;
1886     this.a = a; this.w = w;
1887     this.lo = lo; this.ln = ln;
1888     this.ro = ro; this.rn = rn;
1889     this.wo = wo;
1890     this.gran = gran;
1891     this.next = next;
1892     }
1893    
1894     public void compute() {
1895     // spawn right subtasks
1896 dl 1.2 FJOMerger rights = null;
1897 dl 1.1 int nleft = ln;
1898     int nright = rn;
1899     while (nleft > gran) {
1900     int lh = nleft >>> 1;
1901     int splitIndex = lo + lh;
1902     Object split = a[splitIndex];
1903     // binary search r for split
1904     int rl = 0;
1905     int rh = nright;
1906     while (rl < rh) {
1907     int mid = (rl + rh) >>> 1;
1908     if (cmp.compare(split, a[ro + mid]) <= 0)
1909     rh = mid;
1910     else
1911     rl = mid + 1;
1912     }
1913 dl 1.2 (rights = new FJOMerger
1914 dl 1.1 (cmp, a, w, splitIndex, nleft-lh, ro+rh,
1915     nright-rh, wo+lh+rh, gran, rights)).fork();
1916     nleft = lh;
1917     nright = rh;
1918     }
1919    
1920     // sequentially merge
1921     int l = lo;
1922     int lFence = lo + nleft;
1923     int r = ro;
1924     int rFence = ro + nright;
1925     int k = wo;
1926     while (l < lFence && r < rFence) {
1927     Object al = a[l];
1928     Object ar = a[r];
1929     Object t;
1930     if (cmp.compare(al, ar) <= 0) {++l; t=al;} else {++r; t=ar;}
1931     w[k++] = t;
1932     }
1933     while (l < lFence)
1934     w[k++] = a[l++];
1935     while (r < rFence)
1936     w[k++] = a[r++];
1937    
1938     // join subtasks
1939     while (rights != null) {
1940     if (ForkJoinWorkerThread.removeIfNextLocalTask(rights))
1941     rights.compute();
1942     else
1943     rights.join();
1944     rights = rights.next;
1945     }
1946     }
1947     }
1948    
1949 dl 1.2 static final class FJOCMerger extends RecursiveAction {
1950 dl 1.1 final Comparable[] a; final Comparable[] w;
1951     final int lo; final int ln; final int ro; final int rn; final int wo;
1952     final int gran;
1953 dl 1.2 final FJOCMerger next;
1954     FJOCMerger(Comparable[] a, Comparable[] w, int lo,
1955 dl 1.1 int ln, int ro, int rn, int wo,
1956 dl 1.2 int gran, FJOCMerger next) {
1957 dl 1.1 this.a = a; this.w = w;
1958     this.lo = lo; this.ln = ln; this.ro = ro; this.rn = rn;
1959     this.wo = wo;
1960     this.gran = gran;
1961     this.next = next;
1962     }
1963    
1964     public void compute() {
1965 dl 1.2 FJOCMerger rights = null;
1966 dl 1.1 int nleft = ln;
1967     int nright = rn;
1968     while (nleft > gran) {
1969     int lh = nleft >>> 1;
1970     int splitIndex = lo + lh;
1971     Comparable split = a[splitIndex];
1972     int rl = 0;
1973     int rh = nright;
1974     while (rl < rh) {
1975     int mid = (rl + rh) >>> 1;
1976     if (split.compareTo(a[ro + mid]) <= 0)
1977     rh = mid;
1978     else
1979     rl = mid + 1;
1980     }
1981 dl 1.2 (rights = new FJOCMerger
1982 dl 1.1 (a, w, splitIndex, nleft-lh, ro+rh,
1983     nright-rh, wo+lh+rh, gran, rights)).fork();
1984     nleft = lh;
1985     nright = rh;
1986     }
1987    
1988     int l = lo;
1989     int lFence = lo + nleft;
1990     int r = ro;
1991     int rFence = ro + nright;
1992     int k = wo;
1993     while (l < lFence && r < rFence) {
1994     Comparable al = a[l];
1995     Comparable ar = a[r];
1996     Comparable t;
1997     if (al.compareTo(ar) <= 0) {++l; t=al;} else {++r; t=ar; }
1998     w[k++] = t;
1999     }
2000     while (l < lFence)
2001     w[k++] = a[l++];
2002     while (r < rFence)
2003     w[k++] = a[r++];
2004    
2005     while (rights != null) {
2006     if (ForkJoinWorkerThread.removeIfNextLocalTask(rights))
2007     rights.compute();
2008     else
2009     rights.join();
2010     rights = rights.next;
2011     }
2012     }
2013     }
2014    
2015     static final class FJDMerger extends RecursiveAction {
2016     final DoubleComparator cmp; final double[] a; final double[] w;
2017     final int lo; final int ln; final int ro; final int rn; final int wo;
2018     final int gran;
2019     final FJDMerger next;
2020     FJDMerger(DoubleComparator cmp, double[] a, double[] w,
2021     int lo, int ln, int ro, int rn, int wo,
2022     int gran, FJDMerger next) {
2023     this.cmp = cmp;
2024     this.a = a; this.w = w;
2025     this.lo = lo; this.ln = ln;
2026     this.ro = ro; this.rn = rn;
2027     this.wo = wo;
2028     this.gran = gran;
2029     this.next = next;
2030     }
2031     public void compute() {
2032     FJDMerger rights = null;
2033     int nleft = ln;
2034     int nright = rn;
2035     while (nleft > gran) {
2036     int lh = nleft >>> 1;
2037     int splitIndex = lo + lh;
2038     double split = a[splitIndex];
2039     int rl = 0;
2040     int rh = nright;
2041     while (rl < rh) {
2042     int mid = (rl + rh) >>> 1;
2043     if (cmp.compare(split, a[ro + mid]) <= 0)
2044     rh = mid;
2045     else
2046     rl = mid + 1;
2047     }
2048     (rights = new FJDMerger
2049     (cmp, a, w, splitIndex, nleft-lh, ro+rh,
2050     nright-rh, wo+lh+rh, gran, rights)).fork();
2051     nleft = lh;
2052     nright = rh;
2053     }
2054    
2055     int l = lo;
2056     int lFence = lo + nleft;
2057     int r = ro;
2058     int rFence = ro + nright;
2059     int k = wo;
2060     while (l < lFence && r < rFence) {
2061     double al = a[l];
2062     double ar = a[r];
2063     double t;
2064     if (cmp.compare(al, ar) <= 0) {++l; t=al;} else {++r; t=ar; }
2065     w[k++] = t;
2066     }
2067     while (l < lFence)
2068     w[k++] = a[l++];
2069     while (r < rFence)
2070     w[k++] = a[r++];
2071    
2072     while (rights != null) {
2073     if (ForkJoinWorkerThread.removeIfNextLocalTask(rights))
2074     rights.compute();
2075     else
2076     rights.join();
2077     rights = rights.next;
2078     }
2079     }
2080     }
2081    
2082     static final class FJDCMerger extends RecursiveAction {
2083     final double[] a; final double[] w;
2084     final int lo; final int ln; final int ro; final int rn; final int wo;
2085     final int gran;
2086     final FJDCMerger next;
2087     FJDCMerger(double[] a, double[] w, int lo,
2088     int ln, int ro, int rn, int wo,
2089     int gran, FJDCMerger next) {
2090     this.a = a; this.w = w;
2091     this.lo = lo; this.ln = ln;
2092     this.ro = ro; this.rn = rn;
2093     this.wo = wo;
2094     this.gran = gran;
2095     this.next = next;
2096     }
2097     public void compute() {
2098     FJDCMerger rights = null;
2099     int nleft = ln;
2100     int nright = rn;
2101     while (nleft > gran) {
2102     int lh = nleft >>> 1;
2103     int splitIndex = lo + lh;
2104     double split = a[splitIndex];
2105     int rl = 0;
2106     int rh = nright;
2107     while (rl < rh) {
2108     int mid = (rl + rh) >>> 1;
2109     if (split <= a[ro + mid])
2110     rh = mid;
2111     else
2112     rl = mid + 1;
2113     }
2114     (rights = new FJDCMerger
2115     (a, w, splitIndex, nleft-lh, ro+rh,
2116     nright-rh, wo+lh+rh, gran, rights)).fork();
2117     nleft = lh;
2118     nright = rh;
2119     }
2120    
2121     int l = lo;
2122     int lFence = lo + nleft;
2123     int r = ro;
2124     int rFence = ro + nright;
2125     int k = wo;
2126     while (l < lFence && r < rFence) {
2127     double al = a[l];
2128     double ar = a[r];
2129     double t;
2130     if (al <= ar) {++l; t=al;} else {++r; t=ar; }
2131     w[k++] = t;
2132     }
2133     while (l < lFence)
2134     w[k++] = a[l++];
2135     while (r < rFence)
2136     w[k++] = a[r++];
2137    
2138     while (rights != null) {
2139     if (ForkJoinWorkerThread.removeIfNextLocalTask(rights))
2140     rights.compute();
2141     else
2142     rights.join();
2143     rights = rights.next;
2144     }
2145     }
2146     }
2147    
2148     static final class FJLMerger extends RecursiveAction {
2149     final LongComparator cmp; final long[] a; final long[] w;
2150     final int lo; final int ln; final int ro; final int rn; final int wo;
2151     final int gran;
2152     final FJLMerger next;
2153     FJLMerger(LongComparator cmp, long[] a, long[] w,
2154     int lo, int ln, int ro, int rn, int wo,
2155     int gran, FJLMerger next) {
2156     this.cmp = cmp;
2157     this.a = a; this.w = w;
2158     this.lo = lo; this.ln = ln;
2159     this.ro = ro; this.rn = rn;
2160     this.wo = wo;
2161     this.gran = gran;
2162     this.next = next;
2163     }
2164     public void compute() {
2165     FJLMerger rights = null;
2166     int nleft = ln;
2167     int nright = rn;
2168     while (nleft > gran) {
2169     int lh = nleft >>> 1;
2170     int splitIndex = lo + lh;
2171     long split = a[splitIndex];
2172     int rl = 0;
2173     int rh = nright;
2174     while (rl < rh) {
2175     int mid = (rl + rh) >>> 1;
2176     if (cmp.compare(split, a[ro + mid]) <= 0)
2177     rh = mid;
2178     else
2179     rl = mid + 1;
2180     }
2181     (rights = new FJLMerger
2182     (cmp, a, w, splitIndex, nleft-lh, ro+rh,
2183     nright-rh, wo+lh+rh, gran, rights)).fork();
2184     nleft = lh;
2185     nright = rh;
2186     }
2187    
2188     int l = lo;
2189     int lFence = lo + nleft;
2190     int r = ro;
2191     int rFence = ro + nright;
2192     int k = wo;
2193     while (l < lFence && r < rFence) {
2194     long al = a[l];
2195     long ar = a[r];
2196     long t;
2197     if (cmp.compare(al, ar) <= 0) {++l; t=al;} else {++r; t=ar;}
2198     w[k++] = t;
2199     }
2200     while (l < lFence)
2201     w[k++] = a[l++];
2202     while (r < rFence)
2203     w[k++] = a[r++];
2204    
2205     while (rights != null) {
2206     if (ForkJoinWorkerThread.removeIfNextLocalTask(rights))
2207     rights.compute();
2208     else
2209     rights.join();
2210     rights = rights.next;
2211     }
2212     }
2213     }
2214    
2215     static final class FJLCMerger extends RecursiveAction {
2216     final long[] a; final long[] w;
2217     final int lo; final int ln; final int ro; final int rn; final int wo;
2218     final int gran;
2219     final FJLCMerger next;
2220     FJLCMerger(long[] a, long[] w, int lo,
2221     int ln, int ro, int rn, int wo,
2222     int gran, FJLCMerger next) {
2223     this.a = a; this.w = w;
2224     this.lo = lo; this.ln = ln;
2225     this.ro = ro; this.rn = rn;
2226     this.wo = wo;
2227     this.gran = gran;
2228     this.next = next;
2229     }
2230     public void compute() {
2231     FJLCMerger rights = null;
2232     int nleft = ln;
2233     int nright = rn;
2234     while (nleft > gran) {
2235     int lh = nleft >>> 1;
2236     int splitIndex = lo + lh;
2237     long split = a[splitIndex];
2238     int rl = 0;
2239     int rh = nright;
2240     while (rl < rh) {
2241     int mid = (rl + rh) >>> 1;
2242     if (split <= a[ro + mid])
2243     rh = mid;
2244     else
2245     rl = mid + 1;
2246     }
2247     (rights = new FJLCMerger
2248     (a, w, splitIndex, nleft-lh, ro+rh,
2249     nright-rh, wo+lh+rh, gran, rights)).fork();
2250     nleft = lh;
2251     nright = rh;
2252     }
2253    
2254     int l = lo;
2255     int lFence = lo + nleft;
2256     int r = ro;
2257     int rFence = ro + nright;
2258     int k = wo;
2259     while (l < lFence && r < rFence) {
2260     long al = a[l];
2261     long ar = a[r];
2262     long t;
2263     if (al <= ar) {++l; t=al;} else {++r; t = ar;}
2264     w[k++] = t;
2265     }
2266     while (l < lFence)
2267     w[k++] = a[l++];
2268     while (r < rFence)
2269     w[k++] = a[r++];
2270    
2271     while (rights != null) {
2272     if (ForkJoinWorkerThread.removeIfNextLocalTask(rights))
2273     rights.compute();
2274     else
2275     rights.join();
2276     rights = rights.next;
2277     }
2278     }
2279     }
2280    
2281     /** Cutoff for when to use insertion-sort instead of quicksort */
2282     static final int INSERTION_SORT_THRESHOLD = 8;
2283    
2284     // Six nearly identical versions of quicksort
2285    
2286 dl 1.2 static void oquickSort(Object[] a, Comparator cmp, int lo, int hi) {
2287 dl 1.1 for (;;) {
2288     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2289     for (int i = lo + 1; i <= hi; i++) {
2290     Object t = a[i];
2291     int j = i - 1;
2292     while (j >= lo && cmp.compare(t, a[j]) < 0) {
2293     a[j+1] = a[j];
2294     --j;
2295     }
2296     a[j+1] = t;
2297     }
2298     return;
2299     }
2300    
2301     int mid = (lo + hi) >>> 1;
2302     if (cmp.compare(a[lo], a[mid]) > 0) {
2303     Object t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2304     }
2305     if (cmp.compare(a[mid], a[hi]) > 0) {
2306     Object t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2307     if (cmp.compare(a[lo], a[mid]) > 0) {
2308     Object u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2309     }
2310     }
2311    
2312     Object pivot = a[mid];
2313     int left = lo+1;
2314     int right = hi-1;
2315     for (;;) {
2316     while (cmp.compare(pivot, a[right]) < 0)
2317     --right;
2318     while (left < right && cmp.compare(pivot, a[left]) >= 0)
2319     ++left;
2320     if (left < right) {
2321     Object t = a[left]; a[left] = a[right]; a[right] = t;
2322     --right;
2323     }
2324     else break;
2325     }
2326    
2327 dl 1.2 oquickSort(a, cmp, lo, left);
2328 dl 1.1 lo = left + 1;
2329     }
2330     }
2331    
2332 dl 1.2 static void ocquickSort(Comparable[] a, int lo, int hi) {
2333 dl 1.1 for (;;) {
2334     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2335     for (int i = lo + 1; i <= hi; i++) {
2336     Comparable t = a[i];
2337     int j = i - 1;
2338     while (j >= lo && t.compareTo(a[j]) < 0) {
2339     a[j+1] = a[j];
2340     --j;
2341     }
2342     a[j+1] = t;
2343     }
2344     return;
2345     }
2346    
2347     int mid = (lo + hi) >>> 1;
2348     if (a[lo].compareTo(a[mid]) > 0) {
2349     Comparable t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2350     }
2351     if (a[mid].compareTo(a[hi]) > 0) {
2352     Comparable t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2353     if (a[lo].compareTo(a[mid]) > 0) {
2354     Comparable u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2355     }
2356     }
2357    
2358     Comparable pivot = a[mid];
2359     int left = lo+1;
2360     int right = hi-1;
2361     for (;;) {
2362     while (pivot.compareTo(a[right]) < 0)
2363     --right;
2364     while (left < right && pivot.compareTo(a[left]) >= 0)
2365     ++left;
2366     if (left < right) {
2367     Comparable t = a[left]; a[left] = a[right]; a[right] = t;
2368     --right;
2369     }
2370     else break;
2371     }
2372    
2373 dl 1.2 ocquickSort(a, lo, left);
2374 dl 1.1 lo = left + 1;
2375     }
2376     }
2377    
2378     static void dquickSort(double[] a, DoubleComparator cmp, int lo, int hi) {
2379     for (;;) {
2380     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2381     for (int i = lo + 1; i <= hi; i++) {
2382     double t = a[i];
2383     int j = i - 1;
2384     while (j >= lo && cmp.compare(t, a[j]) < 0) {
2385     a[j+1] = a[j];
2386     --j;
2387     }
2388     a[j+1] = t;
2389     }
2390     return;
2391     }
2392    
2393     int mid = (lo + hi) >>> 1;
2394     if (cmp.compare(a[lo], a[mid]) > 0) {
2395     double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2396     }
2397     if (cmp.compare(a[mid], a[hi]) > 0) {
2398     double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2399     if (cmp.compare(a[lo], a[mid]) > 0) {
2400     double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2401     }
2402     }
2403    
2404     double pivot = a[mid];
2405     int left = lo+1;
2406     int right = hi-1;
2407     for (;;) {
2408     while (cmp.compare(pivot, a[right]) < 0)
2409     --right;
2410     while (left < right && cmp.compare(pivot, a[left]) >= 0)
2411     ++left;
2412     if (left < right) {
2413     double t = a[left]; a[left] = a[right]; a[right] = t;
2414     --right;
2415     }
2416     else break;
2417     }
2418    
2419     dquickSort(a, cmp, lo, left);
2420     lo = left + 1;
2421     }
2422     }
2423    
2424     static void dcquickSort(double[] a, int lo, int hi) {
2425     for (;;) {
2426     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2427     for (int i = lo + 1; i <= hi; i++) {
2428     double t = a[i];
2429     int j = i - 1;
2430     while (j >= lo && t < a[j]) {
2431     a[j+1] = a[j];
2432     --j;
2433     }
2434     a[j+1] = t;
2435     }
2436     return;
2437     }
2438    
2439     int mid = (lo + hi) >>> 1;
2440     if (a[lo] > a[mid]) {
2441     double t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2442     }
2443     if (a[mid] > a[hi]) {
2444     double t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2445     if (a[lo] > a[mid]) {
2446     double u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2447     }
2448     }
2449    
2450     double pivot = a[mid];
2451     int left = lo+1;
2452     int right = hi-1;
2453     for (;;) {
2454     while (pivot < a[right])
2455     --right;
2456     while (left < right && pivot >= a[left])
2457     ++left;
2458     if (left < right) {
2459     double t = a[left]; a[left] = a[right]; a[right] = t;
2460     --right;
2461     }
2462     else break;
2463     }
2464    
2465     dcquickSort(a, lo, left);
2466     lo = left + 1;
2467     }
2468     }
2469    
2470     static void lquickSort(long[] a, LongComparator cmp, int lo, int hi) {
2471     for (;;) {
2472     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2473     for (int i = lo + 1; i <= hi; i++) {
2474     long t = a[i];
2475     int j = i - 1;
2476     while (j >= lo && cmp.compare(t, a[j]) < 0) {
2477     a[j+1] = a[j];
2478     --j;
2479     }
2480     a[j+1] = t;
2481     }
2482     return;
2483     }
2484    
2485     int mid = (lo + hi) >>> 1;
2486     if (cmp.compare(a[lo], a[mid]) > 0) {
2487     long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2488     }
2489     if (cmp.compare(a[mid], a[hi]) > 0) {
2490     long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2491     if (cmp.compare(a[lo], a[mid]) > 0) {
2492     long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2493     }
2494     }
2495    
2496     long pivot = a[mid];
2497     int left = lo+1;
2498     int right = hi-1;
2499     for (;;) {
2500     while (cmp.compare(pivot, a[right]) < 0)
2501     --right;
2502     while (left < right && cmp.compare(pivot, a[left]) >= 0)
2503     ++left;
2504     if (left < right) {
2505     long t = a[left]; a[left] = a[right]; a[right] = t;
2506     --right;
2507     }
2508     else break;
2509     }
2510    
2511     lquickSort(a, cmp, lo, left);
2512     lo = left + 1;
2513     }
2514     }
2515    
2516     static void lcquickSort(long[] a, int lo, int hi) {
2517     for (;;) {
2518     if (hi - lo <= INSERTION_SORT_THRESHOLD) {
2519     for (int i = lo + 1; i <= hi; i++) {
2520     long t = a[i];
2521     int j = i - 1;
2522     while (j >= lo && t < a[j]) {
2523     a[j+1] = a[j];
2524     --j;
2525     }
2526     a[j+1] = t;
2527     }
2528     return;
2529     }
2530    
2531     int mid = (lo + hi) >>> 1;
2532     if (a[lo] > a[mid]) {
2533     long t = a[lo]; a[lo] = a[mid]; a[mid] = t;
2534     }
2535     if (a[mid] > a[hi]) {
2536     long t = a[mid]; a[mid] = a[hi]; a[hi] = t;
2537     if (a[lo] > a[mid]) {
2538     long u = a[lo]; a[lo] = a[mid]; a[mid] = u;
2539     }
2540     }
2541    
2542     long pivot = a[mid];
2543     int left = lo+1;
2544     int right = hi-1;
2545     for (;;) {
2546     while (pivot < a[right])
2547     --right;
2548     while (left < right && pivot >= a[left])
2549     ++left;
2550     if (left < right) {
2551     long t = a[left]; a[left] = a[right]; a[right] = t;
2552     --right;
2553     }
2554     else break;
2555     }
2556    
2557     lcquickSort(a, lo, left);
2558     lo = left + 1;
2559     }
2560     }
2561    
2562     /**
2563     * Cumulative scan
2564     *
2565     * A basic version of scan is straightforward.
2566     * Keep dividing by two to threshold segment size, and then:
2567     * Pass 1: Create tree of partial sums for each segment
2568     * Pass 2: For each segment, cumulate with offset of left sibling
2569     * See G. Blelloch's http://www.cs.cmu.edu/~scandal/alg/scan.html
2570     *
2571     * This version improves performance within FJ framework mainly by
2572     * allowing second pass of ready left-hand sides to proceed even
2573     * if some right-hand side first passes are still executing. It
2574     * also combines first and second pass for leftmost segment, and
2575     * for cumulate (not precumulate) also skips first pass for
2576     * rightmost segment (whose result is not needed for second pass).
2577     *
2578     * To manage this, it relies on "phase" phase/state control field
2579     * maintaining bits CUMULATE, SUMMED, and FINISHED. CUMULATE is
2580     * main phase bit. When false, segments compute only their sum.
2581     * When true, they cumulate array elements. CUMULATE is set at
2582     * root at beginning of second pass and then propagated down. But
2583 dl 1.4 * it may also be set earlier for subtrees with lo==origin (the
2584 dl 1.1 * left spine of tree). SUMMED is a one bit join count. For leafs,
2585     * set when summed. For internal nodes, becomes true when one
2586     * child is summed. When second child finishes summing, it then
2587     * moves up tree to trigger cumulate phase. FINISHED is also a one
2588     * bit join count. For leafs, it is set when cumulated. For
2589     * internal nodes, it becomes true when one child is cumulated.
2590     * When second child finishes cumulating, it then moves up tree,
2591     * excecuting finish() at the root.
2592     *
2593     * This class maintains only the basic control logic. Subclasses
2594     * maintain the "in" and "out" fields, and *Ops classes perform
2595     * computations
2596     */
2597     static abstract class FJScan extends AsyncAction {
2598     static final int CUMULATE = 1;
2599     static final int SUMMED = 2;
2600     static final int FINISHED = 4;
2601    
2602     final FJScan parent;
2603     final FJScanOp op;
2604     FJScan left, right;
2605     volatile int phase; // phase/state
2606     final int lo;
2607     final int hi;
2608    
2609     static final AtomicIntegerFieldUpdater<FJScan> phaseUpdater =
2610     AtomicIntegerFieldUpdater.newUpdater(FJScan.class, "phase");
2611    
2612     FJScan(FJScan parent, FJScanOp op, int lo, int hi) {
2613     this.parent = parent;
2614     this.op = op;
2615     this.lo = lo;
2616     this.hi = hi;
2617     }
2618    
2619     /** Returns true if can CAS CUMULATE bit true */
2620     final boolean transitionToCumulate() {
2621     int c;
2622     while (((c = phase) & CUMULATE) == 0)
2623     if (phaseUpdater.compareAndSet(this, c, c | CUMULATE))
2624     return true;
2625     return false;
2626     }
2627    
2628     public final void compute() {
2629     if (hi - lo > op.threshold) {
2630     if (left == null) { // first pass
2631     int mid = (lo + hi) >>> 1;
2632     left = op.newSubtask(this, lo, mid);
2633     right = op.newSubtask(this, mid, hi);
2634     }
2635    
2636     boolean cumulate = (phase & CUMULATE) != 0;
2637     if (cumulate)
2638     op.pushDown(this, left, right);
2639    
2640     if (!cumulate || right.transitionToCumulate())
2641     right.fork();
2642     if (!cumulate || left.transitionToCumulate())
2643     left.compute();
2644     }
2645     else {
2646     int cb;
2647     for (;;) { // Establish action: sum, cumulate, or both
2648     int b = phase;
2649     if ((b & FINISHED) != 0) // already done
2650     return;
2651     if ((b & CUMULATE) != 0)
2652     cb = FINISHED;
2653 dl 1.4 else if (lo == op.origin) // combine leftmost
2654 dl 1.1 cb = (SUMMED|FINISHED);
2655     else
2656     cb = SUMMED;
2657     if (phaseUpdater.compareAndSet(this, b, b|cb))
2658     break;
2659     }
2660    
2661     if (cb == SUMMED)
2662     op.sumLeaf(lo, hi, this);
2663     else if (cb == FINISHED)
2664     op.cumulateLeaf(lo, hi, this);
2665     else if (cb == (SUMMED|FINISHED))
2666     op.sumAndCumulateLeaf(lo, hi, this);
2667    
2668     // propagate up
2669     FJScan ch = this;
2670     FJScan par = parent;
2671     for (;;) {
2672     if (par == null) {
2673     if ((cb & FINISHED) != 0)
2674     ch.finish();
2675     break;
2676     }
2677     int pb = par.phase;
2678     if ((pb & cb & FINISHED) != 0) { // both finished
2679     ch = par;
2680     par = par.parent;
2681     }
2682     else if ((pb & cb & SUMMED) != 0) { // both summed
2683     op.pushUp(par, par.left, par.right);
2684     int refork =
2685     ((pb & CUMULATE) == 0 &&
2686 dl 1.4 par.lo == op.origin)? CUMULATE : 0;
2687 dl 1.1 int nextPhase = pb|cb|refork;
2688     if (pb == nextPhase ||
2689     phaseUpdater.compareAndSet(par, pb, nextPhase)) {
2690     if (refork != 0)
2691     par.fork();
2692     cb = SUMMED; // drop finished bit
2693     ch = par;
2694     par = par.parent;
2695     }
2696     }
2697     else if (phaseUpdater.compareAndSet(par, pb, pb|cb))
2698     break;
2699     }
2700     }
2701     }
2702    
2703     // no-op versions of methods to get/set in/out, overridden as
2704     // appropriate in subclasses
2705 dl 1.2 Object ogetIn() { return null; }
2706     Object ogetOut() { return null; }
2707 dl 1.1 void rsetIn(Object x) { }
2708     void rsetOut(Object x) { }
2709    
2710     double dgetIn() { return 0; }
2711     double dgetOut() { return 0; }
2712     void dsetIn(double x) { }
2713     void dsetOut(double x) { }
2714    
2715     long lgetIn() { return 0; }
2716     long lgetOut() { return 0; }
2717     void lsetIn(long x) { }
2718     void lsetOut(long x) { }
2719     }
2720    
2721     // Subclasses adding in/out fields of the appropriate type
2722 dl 1.2 static final class FJOScan extends FJScan {
2723 dl 1.1 Object in;
2724     Object out;
2725 dl 1.2 FJOScan(FJScan parent, FJScanOp op, int lo, int hi) {
2726 dl 1.1 super(parent, op, lo, hi);
2727     }
2728 dl 1.2 Object ogetIn() { return in; }
2729     Object ogetOut() { return out; }
2730 dl 1.1 void rsetIn(Object x) { in = x; }
2731     void rsetOut(Object x) { out = x; }
2732     }
2733    
2734     static final class FJDScan extends FJScan {
2735     double in;
2736     double out;
2737     FJDScan(FJScan parent, FJScanOp op, int lo, int hi) {
2738     super(parent, op, lo, hi);
2739     }
2740     double dgetIn() { return in; }
2741     double dgetOut() { return out; }
2742     void dsetIn(double x) { in = x; }
2743     void dsetOut(double x) { out = x; }
2744    
2745     }
2746    
2747     static final class FJLScan extends FJScan {
2748     long in;
2749     long out;
2750     FJLScan(FJScan parent, FJScanOp op, int lo, int hi) {
2751     super(parent, op, lo, hi);
2752     }
2753     long lgetIn() { return in; }
2754     long lgetOut() { return out; }
2755     void lsetIn(long x) { in = x; }
2756     void lsetOut(long x) { out = x; }
2757     }
2758    
2759     /**
2760     * Computational operations for FJSCan
2761     */
2762     static abstract class FJScanOp {
2763     final int threshold;
2764 dl 1.4 final int origin;
2765     final int fence;
2766     FJScanOp(AbstractParallelAnyArray pap) {
2767     this.origin = pap.origin;
2768     this.fence = pap.fence;
2769     this.threshold = pap.getThreshold();
2770 dl 1.1 }
2771     abstract void pushDown(FJScan parent, FJScan left, FJScan right);
2772     abstract void pushUp(FJScan parent, FJScan left, FJScan right);
2773     abstract void sumLeaf(int lo, int hi, FJScan f);
2774     abstract void cumulateLeaf(int lo, int hi, FJScan f);
2775     abstract void sumAndCumulateLeaf(int lo, int hi, FJScan f);
2776     abstract FJScan newSubtask(FJScan parent, int lo, int hi);
2777     }
2778    
2779 dl 1.2 static abstract class FJOScanOp extends FJScanOp {
2780 dl 1.1 final Object[] array;
2781     final Reducer reducer;
2782     final Object base;
2783 jsr166 1.7 FJOScanOp(AbstractParallelAnyArray.OPap pap,
2784 dl 1.4 Reducer reducer, Object base) {
2785     super(pap);
2786     this.array = pap.array;
2787 dl 1.1 this.reducer = reducer;
2788     this.base = base;
2789     }
2790     final void pushDown(FJScan parent, FJScan left, FJScan right) {
2791 dl 1.2 Object pin = parent.ogetIn();
2792 dl 1.1 left.rsetIn(pin);
2793 dl 1.2 right.rsetIn(reducer.op(pin, left.ogetOut()));
2794 dl 1.1 }
2795     final void pushUp(FJScan parent, FJScan left, FJScan right) {
2796 dl 1.2 parent.rsetOut(reducer.op(left.ogetOut(),
2797     right.ogetOut()));
2798 dl 1.1 }
2799     final FJScan newSubtask(FJScan parent, int lo, int hi) {
2800 dl 1.2 FJOScan f = new FJOScan(parent, this, lo, hi);
2801 dl 1.1 f.in = base;
2802     f.out = base;
2803     return f;
2804     }
2805     }
2806    
2807 dl 1.2 static final class FJOCumulateOp extends FJOScanOp {
2808 jsr166 1.7 FJOCumulateOp(AbstractParallelAnyArray.OPap pap,
2809 dl 1.4 Reducer reducer, Object base) {
2810     super(pap, reducer, base);
2811 dl 1.1 }
2812     void sumLeaf(int lo, int hi, FJScan f) {
2813     Object sum = base;
2814 dl 1.4 if (hi != fence) {
2815 dl 1.1 Object[] arr = array;
2816     for (int i = lo; i < hi; ++i)
2817 dl 1.2 sum = reducer.op(sum, arr[i]);
2818 dl 1.1 }
2819     f.rsetOut(sum);
2820     }
2821     void cumulateLeaf(int lo, int hi, FJScan f) {
2822     Object[] arr = array;
2823 dl 1.2 Object sum = f.ogetIn();
2824 dl 1.1 for (int i = lo; i < hi; ++i)
2825 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
2826 dl 1.1 }
2827     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
2828     Object[] arr = array;
2829     Object sum = base;
2830     for (int i = lo; i < hi; ++i)
2831 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
2832 dl 1.1 f.rsetOut(sum);
2833     }
2834     }
2835    
2836 dl 1.2 static final class FJOPrecumulateOp extends FJOScanOp {
2837 jsr166 1.7 FJOPrecumulateOp(AbstractParallelAnyArray.OPap pap,
2838 dl 1.4 Reducer reducer, Object base) {
2839     super(pap, reducer, base);
2840 dl 1.1 }
2841     void sumLeaf(int lo, int hi, FJScan f) {
2842     Object[] arr = array;
2843     Object sum = base;
2844     for (int i = lo; i < hi; ++i)
2845 dl 1.2 sum = reducer.op(sum, arr[i]);
2846 dl 1.1 f.rsetOut(sum);
2847     }
2848     void cumulateLeaf(int lo, int hi, FJScan f) {
2849     Object[] arr = array;
2850 dl 1.2 Object sum = f.ogetIn();
2851 dl 1.1 for (int i = lo; i < hi; ++i) {
2852     Object x = arr[i];
2853     arr[i] = sum;
2854 dl 1.2 sum = reducer.op(sum, x);
2855 dl 1.1 }
2856     }
2857     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
2858     Object[] arr = array;
2859     Object sum = base;
2860     for (int i = lo; i < hi; ++i) {
2861     Object x = arr[i];
2862     arr[i] = sum;
2863 dl 1.2 sum = reducer.op(sum, x);
2864 dl 1.1 }
2865     f.rsetOut(sum);
2866     }
2867     }
2868    
2869     static abstract class FJDScanOp extends FJScanOp {
2870     final double[] array;
2871     final DoubleReducer reducer;
2872     final double base;
2873 jsr166 1.7 FJDScanOp(AbstractParallelAnyArray.DPap pap,
2874 dl 1.4 DoubleReducer reducer, double base) {
2875     super(pap);
2876     this.array = pap.array;
2877 dl 1.1 this.reducer = reducer;
2878     this.base = base;
2879     }
2880     final void pushDown(FJScan parent, FJScan left, FJScan right) {
2881     double pin = parent.dgetIn();
2882     left.dsetIn(pin);
2883 dl 1.2 right.dsetIn(reducer.op(pin, left.dgetOut()));
2884 dl 1.1 }
2885     final void pushUp(FJScan parent, FJScan left, FJScan right) {
2886 dl 1.2 parent.dsetOut(reducer.op(left.dgetOut(),
2887 dl 1.1 right.dgetOut()));
2888     }
2889     final FJScan newSubtask(FJScan parent, int lo, int hi) {
2890     FJDScan f = new FJDScan(parent, this, lo, hi);
2891     f.in = base;
2892     f.out = base;
2893     return f;
2894     }
2895     }
2896    
2897     static final class FJDCumulateOp extends FJDScanOp {
2898 jsr166 1.7 FJDCumulateOp(AbstractParallelAnyArray.DPap pap,
2899 dl 1.4 DoubleReducer reducer, double base) {
2900     super(pap, reducer, base);
2901 dl 1.1 }
2902     void sumLeaf(int lo, int hi, FJScan f) {
2903     double sum = base;
2904 dl 1.4 if (hi != fence) {
2905 dl 1.1 double[] arr = array;
2906     for (int i = lo; i < hi; ++i)
2907 dl 1.2 sum = reducer.op(sum, arr[i]);
2908 dl 1.1 }
2909     f.dsetOut(sum);
2910     }
2911     void cumulateLeaf(int lo, int hi, FJScan f) {
2912     double[] arr = array;
2913     double sum = f.dgetIn();
2914     for (int i = lo; i < hi; ++i)
2915 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
2916 dl 1.1 }
2917     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
2918     double[] arr = array;
2919     double sum = base;
2920     for (int i = lo; i < hi; ++i)
2921 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
2922 dl 1.1 f.dsetOut(sum);
2923     }
2924     }
2925    
2926     static final class FJDPrecumulateOp extends FJDScanOp {
2927 jsr166 1.7 FJDPrecumulateOp(AbstractParallelAnyArray.DPap pap,
2928 dl 1.4 DoubleReducer reducer, double base) {
2929     super(pap, reducer, base);
2930 dl 1.1 }
2931     void sumLeaf(int lo, int hi, FJScan f) {
2932     double[] arr = array;
2933     double sum = base;
2934     for (int i = lo; i < hi; ++i)
2935 dl 1.2 sum = reducer.op(sum, arr[i]);
2936 dl 1.1 f.dsetOut(sum);
2937     }
2938     void cumulateLeaf(int lo, int hi, FJScan f) {
2939     double[] arr = array;
2940     double sum = f.dgetIn();
2941     for (int i = lo; i < hi; ++i) {
2942     double x = arr[i];
2943     arr[i] = sum;
2944 dl 1.2 sum = reducer.op(sum, x);
2945 dl 1.1 }
2946     }
2947     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
2948     double[] arr = array;
2949     double sum = base;
2950     for (int i = lo; i < hi; ++i) {
2951     double x = arr[i];
2952     arr[i] = sum;
2953 dl 1.2 sum = reducer.op(sum, x);
2954 dl 1.1 }
2955     f.dsetOut(sum);
2956     }
2957     }
2958    
2959     static abstract class FJLScanOp extends FJScanOp {
2960     final long[] array;
2961     final LongReducer reducer;
2962     final long base;
2963 jsr166 1.7 FJLScanOp(AbstractParallelAnyArray.LPap pap,
2964 dl 1.4 LongReducer reducer, long base) {
2965     super(pap);
2966     this.array = pap.array;
2967 dl 1.1 this.reducer = reducer;
2968     this.base = base;
2969     }
2970     final void pushDown(FJScan parent, FJScan left, FJScan right) {
2971     long pin = parent.lgetIn();
2972     left.lsetIn(pin);
2973 dl 1.2 right.lsetIn(reducer.op(pin, left.lgetOut()));
2974 dl 1.1 }
2975     final void pushUp(FJScan parent, FJScan left, FJScan right) {
2976 dl 1.2 parent.lsetOut(reducer.op(left.lgetOut(),
2977 dl 1.1 right.lgetOut()));
2978     }
2979     final FJScan newSubtask(FJScan parent, int lo, int hi) {
2980     FJLScan f = new FJLScan(parent, this, lo, hi);
2981     f.in = base;
2982     f.out = base;
2983     return f;
2984     }
2985     }
2986    
2987     static final class FJLCumulateOp extends FJLScanOp {
2988 jsr166 1.7 FJLCumulateOp(AbstractParallelAnyArray.LPap pap,
2989 dl 1.4 LongReducer reducer, long base) {
2990     super(pap, reducer, base);
2991 dl 1.1 }
2992     void sumLeaf(int lo, int hi, FJScan f) {
2993     long sum = base;
2994 dl 1.4 if (hi != fence) {
2995 dl 1.1 long[] arr = array;
2996     for (int i = lo; i < hi; ++i)
2997 dl 1.2 sum = reducer.op(sum, arr[i]);
2998 dl 1.1 }
2999     f.lsetOut(sum);
3000     }
3001     void cumulateLeaf(int lo, int hi, FJScan f) {
3002     long[] arr = array;
3003     long sum = f.lgetIn();
3004     for (int i = lo; i < hi; ++i)
3005 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
3006 dl 1.1 }
3007     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3008     long[] arr = array;
3009     long sum = base;
3010     for (int i = lo; i < hi; ++i)
3011 dl 1.2 arr[i] = sum = reducer.op(sum, arr[i]);
3012 dl 1.1 f.lsetOut(sum);
3013     }
3014     }
3015    
3016     static final class FJLPrecumulateOp extends FJLScanOp {
3017 jsr166 1.7 FJLPrecumulateOp(AbstractParallelAnyArray.LPap pap,
3018 dl 1.4 LongReducer reducer, long base) {
3019     super(pap, reducer, base);
3020 dl 1.1 }
3021     void sumLeaf(int lo, int hi, FJScan f) {
3022     long[] arr = array;
3023     long sum = base;
3024     for (int i = lo; i < hi; ++i)
3025 dl 1.2 sum = reducer.op(sum, arr[i]);
3026 dl 1.1 f.lsetOut(sum);
3027     }
3028     void cumulateLeaf(int lo, int hi, FJScan f) {
3029     long[] arr = array;
3030     long sum = f.lgetIn();
3031     for (int i = lo; i < hi; ++i) {
3032     long x = arr[i];
3033     arr[i] = sum;
3034 dl 1.2 sum = reducer.op(sum, x);
3035 dl 1.1 }
3036     }
3037     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3038     long[] arr = array;
3039     long sum = base;
3040     for (int i = lo; i < hi; ++i) {
3041     long x = arr[i];
3042     arr[i] = sum;
3043 dl 1.2 sum = reducer.op(sum, x);
3044 dl 1.1 }
3045     f.lsetOut(sum);
3046     }
3047     }
3048    
3049     // specialized versions for plus
3050    
3051     static abstract class FJDScanPlusOp extends FJScanOp {
3052     final double[] array;
3053 dl 1.4 FJDScanPlusOp(AbstractParallelAnyArray.DPap pap) {
3054     super(pap);
3055     this.array = pap.array;
3056 dl 1.1 }
3057     final void pushDown(FJScan parent, FJScan left, FJScan right) {
3058     double pin = parent.dgetIn();
3059     left.dsetIn(pin);
3060     right.dsetIn(pin + left.dgetOut());
3061     }
3062     final void pushUp(FJScan parent, FJScan left, FJScan right) {
3063     parent.dsetOut(left.dgetOut() + right.dgetOut());
3064     }
3065     final FJScan newSubtask(FJScan parent, int lo, int hi) {
3066     FJDScan f = new FJDScan(parent, this, lo, hi);
3067     f.in = 0.0;
3068     f.out = 0.0;
3069     return f;
3070     }
3071     }
3072    
3073     static final class FJDCumulatePlusOp extends FJDScanPlusOp {
3074 dl 1.4 FJDCumulatePlusOp(AbstractParallelAnyArray.DPap pap) {
3075     super(pap);
3076 dl 1.1 }
3077     void sumLeaf(int lo, int hi, FJScan f) {
3078     double sum = 0.0;
3079 dl 1.4 if (hi != fence) {
3080 dl 1.1 double[] arr = array;
3081     for (int i = lo; i < hi; ++i)
3082     sum += arr[i];
3083     }
3084     f.dsetOut(sum);
3085     }
3086     void cumulateLeaf(int lo, int hi, FJScan f) {
3087     double[] arr = array;
3088     double sum = f.dgetIn();
3089     for (int i = lo; i < hi; ++i)
3090     arr[i] = sum += arr[i];
3091     }
3092     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3093     double[] arr = array;
3094     double sum = 0.0;
3095     for (int i = lo; i < hi; ++i)
3096     arr[i] = sum += arr[i];
3097     f.dsetOut(sum);
3098     }
3099     }
3100    
3101     static final class FJDPrecumulatePlusOp extends FJDScanPlusOp {
3102 dl 1.4 FJDPrecumulatePlusOp(AbstractParallelAnyArray.DPap pap) {
3103     super(pap);
3104 dl 1.1 }
3105     void sumLeaf(int lo, int hi, FJScan f) {
3106     double[] arr = array;
3107     double sum = 0.0;
3108     for (int i = lo; i < hi; ++i)
3109     sum += arr[i];
3110     f.dsetOut(sum);
3111     }
3112     void cumulateLeaf(int lo, int hi, FJScan f) {
3113     double[] arr = array;
3114     double sum = f.dgetIn();
3115     for (int i = lo; i < hi; ++i) {
3116     double x = arr[i];
3117     arr[i] = sum;
3118     sum += x;
3119     }
3120     }
3121     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3122     double[] arr = array;
3123     double sum = 0.0;
3124     for (int i = lo; i < hi; ++i) {
3125     double x = arr[i];
3126     arr[i] = sum;
3127     sum += x;
3128     }
3129     f.dsetOut(sum);
3130     }
3131     }
3132    
3133     static abstract class FJLScanPlusOp extends FJScanOp {
3134     final long[] array;
3135 dl 1.4 FJLScanPlusOp(AbstractParallelAnyArray.LPap pap) {
3136     super(pap);
3137     this.array = pap.array;
3138 dl 1.1 }
3139     final void pushDown(FJScan parent, FJScan left, FJScan right) {
3140     long pin = parent.lgetIn();
3141     left.lsetIn(pin);
3142     right.lsetIn(pin + left.lgetOut());
3143     }
3144    
3145     final void pushUp(FJScan parent, FJScan left, FJScan right) {
3146     parent.lsetOut(left.lgetOut() + right.lgetOut());
3147     }
3148    
3149     final FJScan newSubtask(FJScan parent, int lo, int hi) {
3150     FJLScan f = new FJLScan(parent, this, lo, hi);
3151     f.in = 0L;
3152     f.out = 0L;
3153     return f;
3154     }
3155     }
3156    
3157     static final class FJLCumulatePlusOp extends FJLScanPlusOp {
3158 dl 1.4 FJLCumulatePlusOp(AbstractParallelAnyArray.LPap pap) {
3159     super(pap);
3160 dl 1.1 }
3161     void sumLeaf(int lo, int hi, FJScan f) {
3162     long sum = 0L;
3163 dl 1.4 if (hi != fence) {
3164 dl 1.1 long[] arr = array;
3165     for (int i = lo; i < hi; ++i)
3166     sum += arr[i];
3167     }
3168     f.lsetOut(sum);
3169     }
3170     void cumulateLeaf(int lo, int hi, FJScan f) {
3171     long[] arr = array;
3172     long sum = f.lgetIn();
3173     for (int i = lo; i < hi; ++i)
3174     arr[i] = sum += arr[i];
3175     }
3176     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3177     long[] arr = array;
3178     long sum = 0L;
3179     for (int i = lo; i < hi; ++i)
3180     arr[i] = sum += arr[i];
3181     f.lsetOut(sum);
3182     }
3183     }
3184    
3185     static final class FJLPrecumulatePlusOp extends FJLScanPlusOp {
3186 dl 1.4 FJLPrecumulatePlusOp(AbstractParallelAnyArray.LPap pap) {
3187     super(pap);
3188 dl 1.1 }
3189     void sumLeaf(int lo, int hi, FJScan f) {
3190     long[] arr = array;
3191     long sum = 0L;
3192     for (int i = lo; i < hi; ++i)
3193     sum += arr[i];
3194     f.lsetOut(sum);
3195     }
3196     void cumulateLeaf(int lo, int hi, FJScan f) {
3197     long[] arr = array;
3198     long sum = f.lgetIn();
3199     for (int i = lo; i < hi; ++i) {
3200     long x = arr[i];
3201     arr[i] = sum;
3202     sum += x;
3203     }
3204     }
3205     void sumAndCumulateLeaf(int lo, int hi, FJScan f) {
3206     long[] arr = array;
3207     long sum = 0L;
3208     for (int i = lo; i < hi; ++i) {
3209     long x = arr[i];
3210     arr[i] = sum;
3211     sum += x;
3212     }
3213     f.lsetOut(sum);
3214     }
3215     }
3216 dl 1.2
3217 dl 1.1 }