1 |
/* |
2 |
* Written by Doug Lea and Martin Buchholz with assistance from |
3 |
* members of JCP JSR-166 Expert Group and released to the public |
4 |
* domain, as explained at |
5 |
* http://creativecommons.org/publicdomain/zero/1.0/ |
6 |
*/ |
7 |
|
8 |
import java.util.concurrent.CountedCompleter; |
9 |
import java.util.concurrent.ThreadLocalRandom; |
10 |
import java.util.concurrent.atomic.AtomicInteger; |
11 |
import java.util.function.BiConsumer; |
12 |
import java.util.function.Consumer; |
13 |
|
14 |
import junit.framework.Test; |
15 |
import junit.framework.TestSuite; |
16 |
|
17 |
public class CountedCompleter8Test extends JSR166TestCase { |
18 |
|
19 |
public static void main(String[] args) { |
20 |
main(suite(), args); |
21 |
} |
22 |
|
23 |
public static Test suite() { |
24 |
return new TestSuite(CountedCompleter8Test.class); |
25 |
} |
26 |
|
27 |
/** CountedCompleter class javadoc code sample, version 1. */ |
28 |
public static <E> void forEach1(E[] array, Consumer<E> action) { |
29 |
class Task extends CountedCompleter<Void> { |
30 |
final int lo, hi; |
31 |
Task(Task parent, int lo, int hi) { |
32 |
super(parent); this.lo = lo; this.hi = hi; |
33 |
} |
34 |
|
35 |
public void compute() { |
36 |
if (hi - lo >= 2) { |
37 |
int mid = (lo + hi) >>> 1; |
38 |
// must set pending count before fork |
39 |
setPendingCount(2); |
40 |
new Task(this, mid, hi).fork(); // right child |
41 |
new Task(this, lo, mid).fork(); // left child |
42 |
} |
43 |
else if (hi > lo) |
44 |
action.accept(array[lo]); |
45 |
tryComplete(); |
46 |
} |
47 |
} |
48 |
new Task(null, 0, array.length).invoke(); |
49 |
} |
50 |
|
51 |
/** CountedCompleter class javadoc code sample, version 2. */ |
52 |
public static <E> void forEach2(E[] array, Consumer<E> action) { |
53 |
class Task extends CountedCompleter<Void> { |
54 |
final int lo, hi; |
55 |
Task(Task parent, int lo, int hi) { |
56 |
super(parent); this.lo = lo; this.hi = hi; |
57 |
} |
58 |
|
59 |
public void compute() { |
60 |
if (hi - lo >= 2) { |
61 |
int mid = (lo + hi) >>> 1; |
62 |
setPendingCount(1); // looks off by one, but correct! |
63 |
new Task(this, mid, hi).fork(); // right child |
64 |
new Task(this, lo, mid).compute(); // direct invoke |
65 |
} else { |
66 |
if (hi > lo) |
67 |
action.accept(array[lo]); |
68 |
tryComplete(); |
69 |
} |
70 |
} |
71 |
} |
72 |
new Task(null, 0, array.length).invoke(); |
73 |
} |
74 |
|
75 |
/** CountedCompleter class javadoc code sample, version 3. */ |
76 |
public static <E> void forEach3(E[] array, Consumer<E> action) { |
77 |
class Task extends CountedCompleter<Void> { |
78 |
final int lo, hi; |
79 |
Task(Task parent, int lo, int hi) { |
80 |
super(parent); this.lo = lo; this.hi = hi; |
81 |
} |
82 |
|
83 |
public void compute() { |
84 |
int n = hi - lo; |
85 |
for (; n >= 2; n /= 2) { |
86 |
addToPendingCount(1); |
87 |
new Task(this, lo + n/2, lo + n).fork(); |
88 |
} |
89 |
if (n > 0) |
90 |
action.accept(array[lo]); |
91 |
propagateCompletion(); |
92 |
} |
93 |
} |
94 |
new Task(null, 0, array.length).invoke(); |
95 |
} |
96 |
|
97 |
/** CountedCompleter class javadoc code sample, version 4. */ |
98 |
public static <E> void forEach4(E[] array, Consumer<E> action) { |
99 |
class Task extends CountedCompleter<Void> { |
100 |
final int lo, hi; |
101 |
Task(Task parent, int lo, int hi) { |
102 |
super(parent, 31 - Integer.numberOfLeadingZeros(hi - lo)); |
103 |
this.lo = lo; this.hi = hi; |
104 |
} |
105 |
|
106 |
public void compute() { |
107 |
for (int n = hi - lo; n >= 2; n /= 2) |
108 |
new Task(this, lo + n/2, lo + n).fork(); |
109 |
action.accept(array[lo]); |
110 |
propagateCompletion(); |
111 |
} |
112 |
} |
113 |
if (array.length > 0) |
114 |
new Task(null, 0, array.length).invoke(); |
115 |
} |
116 |
|
117 |
void testRecursiveDecomposition( |
118 |
BiConsumer<Integer[], Consumer<Integer>> action) { |
119 |
int n = ThreadLocalRandom.current().nextInt(8); |
120 |
Integer[] a = new Integer[n]; |
121 |
for (int i = 0; i < n; i++) a[i] = i + 1; |
122 |
AtomicInteger ai = new AtomicInteger(0); |
123 |
action.accept(a, ai::addAndGet); |
124 |
assertEquals(n * (n + 1) / 2, ai.get()); |
125 |
} |
126 |
|
127 |
/** |
128 |
* Variants of divide-by-two recursive decomposition into leaf tasks, |
129 |
* as described in the CountedCompleter class javadoc code samples |
130 |
*/ |
131 |
public void testRecursiveDecomposition() { |
132 |
testRecursiveDecomposition(CountedCompleter8Test::forEach1); |
133 |
testRecursiveDecomposition(CountedCompleter8Test::forEach2); |
134 |
testRecursiveDecomposition(CountedCompleter8Test::forEach3); |
135 |
testRecursiveDecomposition(CountedCompleter8Test::forEach4); |
136 |
} |
137 |
|
138 |
} |