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