1 |
jsr166 |
1.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 |
jsr166 |
1.3 |
action.accept(a, ai::addAndGet); |
124 |
jsr166 |
1.1 |
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 |
|
|
} |