6865582: jsr166y - jsr166 maintenance update
6865571: Add a lightweight task framework known as ForkJoin
6445158: Phaser - an improved CyclicBarrier
6865579: Add TransferQueue/LinkedTransferQueue
Reviewed-by: martin, chegar, dice
diff --git a/test/java/util/Collection/BiggernYours.java b/test/java/util/Collection/BiggernYours.java
index a9cb59c..c059f9a 100644
--- a/test/java/util/Collection/BiggernYours.java
+++ b/test/java/util/Collection/BiggernYours.java
@@ -178,10 +178,10 @@
new ConcurrentLinkedQueue() {
public int size() {return randomize(super.size());}});
-// testCollections(
-// new LinkedTransferQueue(),
-// new LinkedTransferQueue() {
-// public int size() {return randomize(super.size());}});
+ testCollections(
+ new LinkedTransferQueue(),
+ new LinkedTransferQueue() {
+ public int size() {return randomize(super.size());}});
testCollections(
new LinkedBlockingQueue(),
diff --git a/test/java/util/Collection/IteratorAtEnd.java b/test/java/util/Collection/IteratorAtEnd.java
index ff8ae97..b759d7e 100644
--- a/test/java/util/Collection/IteratorAtEnd.java
+++ b/test/java/util/Collection/IteratorAtEnd.java
@@ -49,7 +49,7 @@
testCollection(new LinkedBlockingQueue());
testCollection(new ArrayBlockingQueue(100));
testCollection(new ConcurrentLinkedQueue());
-// testCollection(new LinkedTransferQueue());
+ testCollection(new LinkedTransferQueue());
testMap(new HashMap());
testMap(new Hashtable());
diff --git a/test/java/util/Collection/MOAT.java b/test/java/util/Collection/MOAT.java
index 0b4fc6a..3f61f9b 100644
--- a/test/java/util/Collection/MOAT.java
+++ b/test/java/util/Collection/MOAT.java
@@ -76,7 +76,7 @@
testCollection(new LinkedBlockingQueue<Integer>(20));
testCollection(new LinkedBlockingDeque<Integer>(20));
testCollection(new ConcurrentLinkedQueue<Integer>());
-// testCollection(new LinkedTransferQueue<Integer>());
+ testCollection(new LinkedTransferQueue<Integer>());
testCollection(new ConcurrentSkipListSet<Integer>());
testCollection(Arrays.asList(new Integer(42)));
testCollection(Arrays.asList(1,2,3));
diff --git a/test/java/util/Collections/CheckedNull.java b/test/java/util/Collections/CheckedNull.java
index 6bb19e7..ddd0205 100644
--- a/test/java/util/Collections/CheckedNull.java
+++ b/test/java/util/Collections/CheckedNull.java
@@ -52,7 +52,7 @@
testMap(Collections.checkedMap(
new HashMap<String, String>(),
- String.class, String.class));;
+ String.class, String.class));
}
ClassCastException cce(F f) {
diff --git a/test/java/util/Collections/RacingCollections.java b/test/java/util/Collections/RacingCollections.java
index 32e41cf..23dc897 100644
--- a/test/java/util/Collections/RacingCollections.java
+++ b/test/java/util/Collections/RacingCollections.java
@@ -234,7 +234,7 @@
List<Queue<Integer>> list =
new ArrayList<Queue<Integer>>(newConcurrentDeques());
list.add(new LinkedBlockingQueue<Integer>(10));
-// list.add(new LinkedTransferQueue<Integer>());
+ list.add(new LinkedTransferQueue<Integer>());
return list;
}
diff --git a/test/java/util/PriorityQueue/RemoveContains.java b/test/java/util/PriorityQueue/RemoveContains.java
index 85c9d21..6e52709 100644
--- a/test/java/util/PriorityQueue/RemoveContains.java
+++ b/test/java/util/PriorityQueue/RemoveContains.java
@@ -69,7 +69,7 @@
test(new ArrayBlockingQueue<String>(10));
test(new LinkedBlockingQueue<String>(10));
test(new LinkedBlockingDeque<String>(10));
-// test(new LinkedTransferQueue<String>());
+ test(new LinkedTransferQueue<String>());
test(new ArrayDeque<String>(10));
System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
diff --git a/test/java/util/concurrent/BlockingQueue/CancelledProducerConsumerLoops.java b/test/java/util/concurrent/BlockingQueue/CancelledProducerConsumerLoops.java
index 210f43c..98ac5d7 100644
--- a/test/java/util/concurrent/BlockingQueue/CancelledProducerConsumerLoops.java
+++ b/test/java/util/concurrent/BlockingQueue/CancelledProducerConsumerLoops.java
@@ -119,12 +119,36 @@
}
}
+ static final class LTQasSQ<T> extends LinkedTransferQueue<T> {
+ LTQasSQ() { super(); }
+ public void put(T x) {
+ try { super.transfer(x); }
+ catch (InterruptedException ex) { throw new Error(); }
+ }
+ private final static long serialVersionUID = 42;
+ }
+
+ static final class HalfSyncLTQ<T> extends LinkedTransferQueue<T> {
+ HalfSyncLTQ() { super(); }
+ public void put(T x) {
+ if (ThreadLocalRandom.current().nextBoolean())
+ super.put(x);
+ else {
+ try { super.transfer(x); }
+ catch (InterruptedException ex) { throw new Error(); }
+ }
+ }
+ private final static long serialVersionUID = 42;
+ }
+
static void oneTest(int pairs, int iters) throws Exception {
oneRun(new ArrayBlockingQueue<Integer>(CAPACITY), pairs, iters);
oneRun(new LinkedBlockingQueue<Integer>(CAPACITY), pairs, iters);
oneRun(new LinkedBlockingDeque<Integer>(CAPACITY), pairs, iters);
-// oneRun(new LinkedTransferQueue<Integer>(), pairs, iters);
+ oneRun(new LinkedTransferQueue<Integer>(), pairs, iters);
+ oneRun(new LTQasSQ<Integer>(), pairs, iters);
+ oneRun(new HalfSyncLTQ<Integer>(), pairs, iters);
oneRun(new SynchronousQueue<Integer>(), pairs, iters / 8);
/* PriorityBlockingQueue is unbounded
diff --git a/test/java/util/concurrent/BlockingQueue/LastElement.java b/test/java/util/concurrent/BlockingQueue/LastElement.java
index a4c2787..e7dd155 100644
--- a/test/java/util/concurrent/BlockingQueue/LastElement.java
+++ b/test/java/util/concurrent/BlockingQueue/LastElement.java
@@ -37,7 +37,7 @@
testQueue(new LinkedBlockingDeque<Integer>());
testQueue(new ArrayBlockingQueue<Integer>(10, true));
testQueue(new ArrayBlockingQueue<Integer>(10, false));
-// testQueue(new LinkedTransferQueue<Integer>());
+ testQueue(new LinkedTransferQueue<Integer>());
System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
if (failed > 0) throw new Exception("Some tests failed");
diff --git a/test/java/util/concurrent/BlockingQueue/MultipleProducersSingleConsumerLoops.java b/test/java/util/concurrent/BlockingQueue/MultipleProducersSingleConsumerLoops.java
index 0e0fd82..8b7db5a 100644
--- a/test/java/util/concurrent/BlockingQueue/MultipleProducersSingleConsumerLoops.java
+++ b/test/java/util/concurrent/BlockingQueue/MultipleProducersSingleConsumerLoops.java
@@ -87,11 +87,35 @@
throw new Error();
}
+ static final class LTQasSQ<T> extends LinkedTransferQueue<T> {
+ LTQasSQ() { super(); }
+ public void put(T x) {
+ try { super.transfer(x); }
+ catch (InterruptedException ex) { throw new Error(); }
+ }
+ private final static long serialVersionUID = 42;
+ }
+
+ static final class HalfSyncLTQ<T> extends LinkedTransferQueue<T> {
+ HalfSyncLTQ() { super(); }
+ public void put(T x) {
+ if (ThreadLocalRandom.current().nextBoolean())
+ super.put(x);
+ else {
+ try { super.transfer(x); }
+ catch (InterruptedException ex) { throw new Error(); }
+ }
+ }
+ private final static long serialVersionUID = 42;
+ }
+
static void oneTest(int producers, int iters) throws Exception {
oneRun(new ArrayBlockingQueue<Integer>(CAPACITY), producers, iters);
oneRun(new LinkedBlockingQueue<Integer>(CAPACITY), producers, iters);
oneRun(new LinkedBlockingDeque<Integer>(CAPACITY), producers, iters);
-// oneRun(new LinkedTransferQueue<Integer>(), producers, iters);
+ oneRun(new LinkedTransferQueue<Integer>(), producers, iters);
+ oneRun(new LTQasSQ<Integer>(), producers, iters);
+ oneRun(new HalfSyncLTQ<Integer>(), producers, iters);
// Don't run PBQ since can legitimately run out of memory
// if (print)
diff --git a/test/java/util/concurrent/BlockingQueue/OfferDrainToLoops.java b/test/java/util/concurrent/BlockingQueue/OfferDrainToLoops.java
index 1721b91..94d3e9a 100644
--- a/test/java/util/concurrent/BlockingQueue/OfferDrainToLoops.java
+++ b/test/java/util/concurrent/BlockingQueue/OfferDrainToLoops.java
@@ -63,12 +63,11 @@
test(new LinkedBlockingDeque());
test(new LinkedBlockingDeque(2000));
test(new ArrayBlockingQueue(2000));
-// test(new LinkedTransferQueue());
+ test(new LinkedTransferQueue());
}
Random getRandom() {
- return new Random();
- // return ThreadLocalRandom.current();
+ return ThreadLocalRandom.current();
}
void test(final BlockingQueue q) throws Throwable {
diff --git a/test/java/util/concurrent/BlockingQueue/PollMemoryLeak.java b/test/java/util/concurrent/BlockingQueue/PollMemoryLeak.java
index 9e47162..df9049d 100644
--- a/test/java/util/concurrent/BlockingQueue/PollMemoryLeak.java
+++ b/test/java/util/concurrent/BlockingQueue/PollMemoryLeak.java
@@ -46,7 +46,7 @@
public static void main(String[] args) throws InterruptedException {
final BlockingQueue[] qs = {
new LinkedBlockingQueue(10),
-// new LinkedTransferQueue(),
+ new LinkedTransferQueue(),
new ArrayBlockingQueue(10),
new SynchronousQueue(),
new SynchronousQueue(true),
diff --git a/test/java/util/concurrent/BlockingQueue/ProducerConsumerLoops.java b/test/java/util/concurrent/BlockingQueue/ProducerConsumerLoops.java
index b40c49f..761990d 100644
--- a/test/java/util/concurrent/BlockingQueue/ProducerConsumerLoops.java
+++ b/test/java/util/concurrent/BlockingQueue/ProducerConsumerLoops.java
@@ -87,11 +87,35 @@
throw new Error();
}
+ static final class LTQasSQ<T> extends LinkedTransferQueue<T> {
+ LTQasSQ() { super(); }
+ public void put(T x) {
+ try { super.transfer(x); }
+ catch (InterruptedException ex) { throw new Error(); }
+ }
+ private final static long serialVersionUID = 42;
+ }
+
+ static final class HalfSyncLTQ<T> extends LinkedTransferQueue<T> {
+ HalfSyncLTQ() { super(); }
+ public void put(T x) {
+ if (ThreadLocalRandom.current().nextBoolean())
+ super.put(x);
+ else {
+ try { super.transfer(x); }
+ catch (InterruptedException ex) { throw new Error(); }
+ }
+ }
+ private final static long serialVersionUID = 42;
+ }
+
static void oneTest(int pairs, int iters) throws Exception {
oneRun(new ArrayBlockingQueue<Integer>(CAPACITY), pairs, iters);
oneRun(new LinkedBlockingQueue<Integer>(CAPACITY), pairs, iters);
oneRun(new LinkedBlockingDeque<Integer>(CAPACITY), pairs, iters);
-// oneRun(new LinkedTransferQueue<Integer>(), pairs, iters);
+ oneRun(new LinkedTransferQueue<Integer>(), pairs, iters);
+ oneRun(new LTQasSQ<Integer>(), pairs, iters);
+ oneRun(new HalfSyncLTQ<Integer>(), pairs, iters);
oneRun(new PriorityBlockingQueue<Integer>(), pairs, iters);
oneRun(new SynchronousQueue<Integer>(), pairs, iters);
diff --git a/test/java/util/concurrent/BlockingQueue/SingleProducerMultipleConsumerLoops.java b/test/java/util/concurrent/BlockingQueue/SingleProducerMultipleConsumerLoops.java
index 8c718b9..c99a664 100644
--- a/test/java/util/concurrent/BlockingQueue/SingleProducerMultipleConsumerLoops.java
+++ b/test/java/util/concurrent/BlockingQueue/SingleProducerMultipleConsumerLoops.java
@@ -73,11 +73,35 @@
throw new Error();
}
+ static final class LTQasSQ<T> extends LinkedTransferQueue<T> {
+ LTQasSQ() { super(); }
+ public void put(T x) {
+ try { super.transfer(x); }
+ catch (InterruptedException ex) { throw new Error(); }
+ }
+ private final static long serialVersionUID = 42;
+ }
+
+ static final class HalfSyncLTQ<T> extends LinkedTransferQueue<T> {
+ HalfSyncLTQ() { super(); }
+ public void put(T x) {
+ if (ThreadLocalRandom.current().nextBoolean())
+ super.put(x);
+ else {
+ try { super.transfer(x); }
+ catch (InterruptedException ex) { throw new Error(); }
+ }
+ }
+ private final static long serialVersionUID = 42;
+ }
+
static void oneTest(int consumers, int iters) throws Exception {
oneRun(new ArrayBlockingQueue<Integer>(CAPACITY), consumers, iters);
oneRun(new LinkedBlockingQueue<Integer>(CAPACITY), consumers, iters);
oneRun(new LinkedBlockingDeque<Integer>(CAPACITY), consumers, iters);
-// oneRun(new LinkedTransferQueue<Integer>(), consumers, iters);
+ oneRun(new LinkedTransferQueue<Integer>(), consumers, iters);
+ oneRun(new LTQasSQ<Integer>(), consumers, iters);
+ oneRun(new HalfSyncLTQ<Integer>(), consumers, iters);
oneRun(new PriorityBlockingQueue<Integer>(), consumers, iters);
oneRun(new SynchronousQueue<Integer>(), consumers, iters);
if (print)
diff --git a/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java b/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java
index 9586d3d..eea3929 100644
--- a/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java
+++ b/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java
@@ -60,7 +60,7 @@
//queues.add(new ArrayBlockingQueue<Integer>(count, true));
queues.add(new LinkedBlockingQueue<Integer>());
queues.add(new LinkedBlockingDeque<Integer>());
-// queues.add(new LinkedTransferQueue<Integer>());
+ queues.add(new LinkedTransferQueue<Integer>());
// Following additional implementations are available from:
// http://gee.cs.oswego.edu/dl/concurrency-interest/index.html
diff --git a/test/java/util/concurrent/ConcurrentQueues/GCRetention.java b/test/java/util/concurrent/ConcurrentQueues/GCRetention.java
index c2ade90..5d53618 100644
--- a/test/java/util/concurrent/ConcurrentQueues/GCRetention.java
+++ b/test/java/util/concurrent/ConcurrentQueues/GCRetention.java
@@ -43,7 +43,7 @@
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
-// import java.util.concurrent.LinkedTransferQueue;
+import java.util.concurrent.LinkedTransferQueue;
import java.util.concurrent.PriorityBlockingQueue;
import java.util.LinkedList;
import java.util.PriorityQueue;
@@ -70,7 +70,7 @@
queues.add(new PriorityBlockingQueue<Boolean>());
queues.add(new PriorityQueue<Boolean>());
queues.add(new LinkedList<Boolean>());
-// queues.add(new LinkedTransferQueue<Boolean>());
+ queues.add(new LinkedTransferQueue<Boolean>());
// Following additional implementations are available from:
// http://gee.cs.oswego.edu/dl/concurrency-interest/index.html
diff --git a/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java b/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java
index c767fa4..a684af7 100644
--- a/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java
+++ b/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java
@@ -49,7 +49,7 @@
test(new LinkedBlockingDeque());
test(new LinkedBlockingDeque(20));
test(new ConcurrentLinkedQueue());
-// test(new LinkedTransferQueue());
+ test(new LinkedTransferQueue());
// Other concurrent queues (e.g. ArrayBlockingQueue) do not
// currently have weakly consistent iterators.
// test(new ArrayBlockingQueue(20));
diff --git a/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java b/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java
index 6051483..f1d9269 100644
--- a/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java
+++ b/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java
@@ -56,12 +56,11 @@
testQueue(new ArrayBlockingQueue(10));
testQueue(new PriorityBlockingQueue(10));
testQueue(new ConcurrentLinkedQueue());
-// testQueue(new LinkedTransferQueue());
+ testQueue(new LinkedTransferQueue());
}
Random getRandom() {
- return new Random();
- // return ThreadLocalRandom.current();
+ return ThreadLocalRandom.current();
}
void testQueue(final Queue q) throws Throwable {
diff --git a/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java b/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java
index 2019c65..e7bcce4 100644
--- a/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java
+++ b/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java
@@ -45,7 +45,7 @@
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
-// import java.util.concurrent.LinkedTransferQueue;
+import java.util.concurrent.LinkedTransferQueue;
import java.util.concurrent.atomic.AtomicLong;
import java.util.ArrayList;
import java.util.Collection;
@@ -67,7 +67,7 @@
queues.add(new ArrayBlockingQueue<Boolean>(count, true));
queues.add(new LinkedBlockingQueue<Boolean>());
queues.add(new LinkedBlockingDeque<Boolean>());
-// queues.add(new LinkedTransferQueue<Boolean>());
+ queues.add(new LinkedTransferQueue<Boolean>());
// Following additional implementations are available from:
// http://gee.cs.oswego.edu/dl/concurrency-interest/index.html
diff --git a/test/java/util/concurrent/Phaser/Arrive.java b/test/java/util/concurrent/Phaser/Arrive.java
new file mode 100644
index 0000000..8d743b5
--- /dev/null
+++ b/test/java/util/concurrent/Phaser/Arrive.java
@@ -0,0 +1,94 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+
+/*
+ * @test
+ * @bug 6445158
+ * @summary tests for Phaser.arrive()
+ */
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.concurrent.Phaser;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.concurrent.atomic.AtomicInteger;
+
+public class Arrive {
+ void test(String[] args) throws Throwable {
+ final int n = ThreadLocalRandom.current().nextInt(1, 10);
+ final int nthreads = n*3/2;
+ final Phaser startingGate = new Phaser(nthreads);
+ final Phaser phaser = new Phaser(n);
+ final List<Thread> threads = new ArrayList<Thread>();
+ final AtomicInteger count0 = new AtomicInteger(0);
+ final AtomicInteger count1 = new AtomicInteger(0);
+ final Runnable task = new Runnable() { public void run() {
+ equal(startingGate.getPhase(), 0);
+ startingGate.arriveAndAwaitAdvance();
+ equal(startingGate.getPhase(), 1);
+ int phase = phaser.arrive();
+ if (phase == 0)
+ count0.getAndIncrement();
+ else if (phase == 1)
+ count1.getAndIncrement();
+ else
+ fail();
+ }};
+ for (int i = 0; i < nthreads; i++)
+ threads.add(new Thread(task));
+ for (Thread thread : threads)
+ thread.start();
+ for (Thread thread : threads)
+ thread.join();
+ equal(count0.get(), n);
+ equal(count1.get(), nthreads-n);
+ equal(phaser.getPhase(), 1);
+ }
+
+ //--------------------- Infrastructure ---------------------------
+ volatile int passed = 0, failed = 0;
+ void pass() {passed++;}
+ void fail() {failed++; Thread.dumpStack();}
+ void fail(String msg) {System.err.println(msg); fail();}
+ void unexpected(Throwable t) {failed++; t.printStackTrace();}
+ void check(boolean cond) {if (cond) pass(); else fail();}
+ void equal(Object x, Object y) {
+ if (x == null ? y == null : x.equals(y)) pass();
+ else fail(x + " not equal to " + y);}
+ public static void main(String[] args) throws Throwable {
+ new Arrive().instanceMain(args);}
+ public void instanceMain(String[] args) throws Throwable {
+ try {test(args);} catch (Throwable t) {unexpected(t);}
+ System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
+ if (failed > 0) throw new AssertionError("Some tests failed");}
+}
diff --git a/test/java/util/concurrent/Phaser/Basic.java b/test/java/util/concurrent/Phaser/Basic.java
new file mode 100644
index 0000000..171a259
--- /dev/null
+++ b/test/java/util/concurrent/Phaser/Basic.java
@@ -0,0 +1,407 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+
+/*
+ * @test
+ * @bug 6445158
+ * @summary Basic tests for Phaser
+ * @author Chris Hegarty
+ */
+
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.concurrent.Phaser;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.TimeoutException;
+import java.util.concurrent.atomic.AtomicInteger;
+import static java.util.concurrent.TimeUnit.*;
+
+public class Basic {
+
+ private static void checkTerminated(final Phaser phaser) {
+ check(phaser.isTerminated());
+ int unarriverParties = phaser.getUnarrivedParties();
+ int registeredParties = phaser.getRegisteredParties();
+ equal(phaser.arrive(), -1);
+ equal(phaser.arriveAndDeregister(), -1);
+ equal(phaser.arriveAndAwaitAdvance(), -1);
+ equal(phaser.bulkRegister(10), -1);
+ equal(phaser.getPhase(), -1);
+ equal(phaser.register(), -1);
+ try {
+ equal(phaser.awaitAdvanceInterruptibly(0), -1);
+ equal(phaser.awaitAdvanceInterruptibly(0, 10, SECONDS), -1);
+ } catch (Exception ie) {
+ unexpected(ie);
+ }
+ equal(phaser.getUnarrivedParties(), unarriverParties);
+ equal(phaser.getRegisteredParties(), registeredParties);
+ }
+
+ private static void checkResult(Arriver a, Class<? extends Throwable> c) {
+ Throwable t = a.result();
+ if (! ((t == null && c == null) || (c != null && c.isInstance(t)))) {
+ // t.printStackTrace();
+ fail("Mismatch in thread " +
+ a.getName() + ": " +
+ t + ", " +
+ (c == null ? "<null>" : c.getName()));
+ } else {
+ pass();
+ }
+ }
+
+ //----------------------------------------------------------------
+ // Mechanism to get all test threads into "running" mode.
+ //----------------------------------------------------------------
+ private static Phaser atTheStartingGate = new Phaser(3);
+
+ private static void toTheStartingGate() {
+ try {
+ boolean expectNextPhase = false;
+ if (atTheStartingGate.getUnarrivedParties() == 1) {
+ expectNextPhase = true;
+ }
+ int phase = atTheStartingGate.getPhase();
+ equal(phase, atTheStartingGate.arrive());
+ int AwaitPhase = atTheStartingGate.awaitAdvanceInterruptibly(phase,
+ 10,
+ SECONDS);
+ if (expectNextPhase) check(AwaitPhase == (phase + 1));
+
+ pass();
+ } catch (Throwable t) {
+ unexpected(t);
+ // reset(atTheStartingGate);
+ throw new Error(t);
+ }
+ }
+
+ //----------------------------------------------------------------
+ // Convenience methods for creating threads that call arrive,
+ // awaitAdvance, arriveAndAwaitAdvance, awaitAdvanceInterruptibly
+ //----------------------------------------------------------------
+ private static abstract class Arriver extends Thread {
+ static AtomicInteger count = new AtomicInteger(1);
+
+ Arriver() {
+ this("Arriver");
+ }
+
+ Arriver(String name) {
+ this.setName(name + ":" + count.getAndIncrement());
+ this.setDaemon(true);
+ }
+
+ private volatile Throwable result;
+ private volatile int phase;
+ protected void result(Throwable result) { this.result = result; }
+ public Throwable result() { return this.result; }
+ protected void phase(int phase) { this.phase = phase; }
+ public int phase() { return this.phase; }
+ }
+
+ private static abstract class Awaiter extends Arriver {
+ Awaiter() { super("Awaiter"); }
+ Awaiter(String name) { super(name); }
+ }
+
+ private static Arriver arriver(final Phaser phaser) {
+ return new Arriver() { public void run() {
+ toTheStartingGate();
+
+ try { phase(phaser.arrive()); }
+ catch (Throwable result) { result(result); }}};
+ }
+
+ private static AtomicInteger cycleArriveAwaitAdvance = new AtomicInteger(1);
+
+ private static Awaiter awaiter(final Phaser phaser) {
+ return new Awaiter() { public void run() {
+ toTheStartingGate();
+
+ try {
+ if (cycleArriveAwaitAdvance.getAndIncrement() % 2 == 0)
+ phase(phaser.awaitAdvance(phaser.arrive()));
+ else
+ phase(phaser.arriveAndAwaitAdvance());
+ } catch (Throwable result) { result(result); }}};
+ }
+
+ private static Awaiter awaiter(final Phaser phaser,
+ final long timeout,
+ final TimeUnit unit) {
+ return new Awaiter("InterruptibleWaiter") { public void run() {
+ toTheStartingGate();
+
+ try {
+ if (timeout < 0)
+ phase(phaser.awaitAdvanceInterruptibly(phaser.arrive()));
+ else
+ phase(phaser.awaitAdvanceInterruptibly(phaser.arrive(),
+ timeout,
+ unit));
+ } catch (Throwable result) { result(result); }}};
+ }
+
+ // Returns an infinite lazy list of all possible arriver/awaiter combinations.
+ private static Iterator<Arriver> arriverIterator(final Phaser phaser) {
+ return new Iterator<Arriver>() {
+ int i = 0;
+ public boolean hasNext() { return true; }
+ public Arriver next() {
+ switch ((i++)&7) {
+ case 0: case 4:
+ return arriver(phaser);
+ case 1: case 5:
+ return awaiter(phaser);
+ case 2: case 6: case 7:
+ return awaiter(phaser, -1, SECONDS);
+ default:
+ return awaiter(phaser, 10, SECONDS); }}
+ public void remove() {throw new UnsupportedOperationException();}};
+ }
+
+ // Returns an infinite lazy list of all possible awaiter only combinations.
+ private static Iterator<Awaiter> awaiterIterator(final Phaser phaser) {
+ return new Iterator<Awaiter>() {
+ int i = 0;
+ public boolean hasNext() { return true; }
+ public Awaiter next() {
+ switch ((i++)&7) {
+ case 1: case 4: case 7:
+ return awaiter(phaser);
+ case 2: case 5:
+ return awaiter(phaser, -1, SECONDS);
+ default:
+ return awaiter(phaser, 10, SECONDS); }}
+ public void remove() {throw new UnsupportedOperationException();}};
+ }
+
+ private static void realMain(String[] args) throws Throwable {
+
+ Thread.currentThread().setName("mainThread");
+
+ //----------------------------------------------------------------
+ // Normal use
+ //----------------------------------------------------------------
+ try {
+ Phaser phaser = new Phaser(3);
+ equal(phaser.getRegisteredParties(), 3);
+ equal(phaser.getArrivedParties(), 0);
+ equal(phaser.getPhase(), 0);
+ check(phaser.getRoot().equals(phaser));
+ equal(phaser.getParent(), null);
+ check(!phaser.isTerminated());
+
+ Iterator<Arriver> arrivers = arriverIterator(phaser);
+ int phase = 0;
+ for (int i = 0; i < 10; i++) {
+ equal(phaser.getPhase(), phase++);
+ Arriver a1 = arrivers.next(); a1.start();
+ Arriver a2 = arrivers.next(); a2.start();
+ toTheStartingGate();
+ phaser.arriveAndAwaitAdvance();
+ a1.join();
+ a2.join();
+ checkResult(a1, null);
+ checkResult(a2, null);
+ check(!phaser.isTerminated());
+ equal(phaser.getRegisteredParties(), 3);
+ equal(phaser.getArrivedParties(), 0);
+ }
+ } catch (Throwable t) { unexpected(t); }
+
+ //----------------------------------------------------------------
+ // One thread interrupted
+ //----------------------------------------------------------------
+ try {
+ Phaser phaser = new Phaser(3);
+ Iterator<Arriver> arrivers = arriverIterator(phaser);
+ int phase = phaser.getPhase();
+ for (int i = 0; i < 4; i++) {
+ check(phaser.getPhase() == phase);
+ Awaiter a1 = awaiter(phaser, 10, SECONDS); a1.start();
+ Arriver a2 = arrivers.next(); a2.start();
+ toTheStartingGate();
+ a1.interrupt();
+ a1.join();
+ phaser.arriveAndAwaitAdvance();
+ a2.join();
+ checkResult(a1, InterruptedException.class);
+ checkResult(a2, null);
+ check(!phaser.isTerminated());
+ equal(phaser.getRegisteredParties(), 3);
+ equal(phaser.getArrivedParties(), 0);
+ phase++;
+ }
+ } catch (Throwable t) { unexpected(t); }
+
+ //----------------------------------------------------------------
+ // Phaser is terminated while threads are waiting
+ //----------------------------------------------------------------
+ try {
+ Phaser phaser = new Phaser(3);
+ Iterator<Awaiter> awaiters = awaiterIterator(phaser);
+ for (int i = 0; i < 4; i++) {
+ Arriver a1 = awaiters.next(); a1.start();
+ Arriver a2 = awaiters.next(); a2.start();
+ toTheStartingGate();
+ while (phaser.getArrivedParties() < 2) Thread.yield();
+ phaser.forceTermination();
+ a1.join();
+ a2.join();
+ check(a1.phase == -1);
+ check(a2.phase == -1);
+ int arrivedParties = phaser.getArrivedParties();
+ checkTerminated(phaser);
+ equal(phaser.getArrivedParties(), arrivedParties);
+ }
+ } catch (Throwable t) { unexpected(t); }
+
+ //----------------------------------------------------------------
+ // Adds new unarrived parties to this phaser
+ //----------------------------------------------------------------
+ try {
+ Phaser phaser = new Phaser(1);
+ Iterator<Arriver> arrivers = arriverIterator(phaser);
+ LinkedList<Arriver> arriverList = new LinkedList<Arriver>();
+ int phase = phaser.getPhase();
+ for (int i = 1; i < 5; i++) {
+ atTheStartingGate = new Phaser(1+(3*i));
+ check(phaser.getPhase() == phase);
+ // register 3 more
+ phaser.register(); phaser.register(); phaser.register();
+ for (int z=0; z<(3*i); z++) {
+ arriverList.add(arrivers.next());
+ }
+ for (Arriver arriver : arriverList)
+ arriver.start();
+
+ toTheStartingGate();
+ phaser.arriveAndAwaitAdvance();
+
+ for (Arriver arriver : arriverList) {
+ arriver.join();
+ checkResult(arriver, null);
+ }
+ equal(phaser.getRegisteredParties(), 1 + (3*i));
+ equal(phaser.getArrivedParties(), 0);
+ arriverList.clear();
+ phase++;
+ }
+ atTheStartingGate = new Phaser(3);
+ } catch (Throwable t) { unexpected(t); }
+
+ //----------------------------------------------------------------
+ // One thread timed out
+ //----------------------------------------------------------------
+ try {
+ Phaser phaser = new Phaser(3);
+ Iterator<Arriver> arrivers = arriverIterator(phaser);
+ for (long timeout : new long[] { 0L, 5L }) {
+ for (int i = 0; i < 2; i++) {
+ Awaiter a1 = awaiter(phaser, timeout, SECONDS); a1.start();
+ Arriver a2 = arrivers.next(); a2.start();
+ toTheStartingGate();
+ a1.join();
+ checkResult(a1, TimeoutException.class);
+ phaser.arrive();
+ a2.join();
+ checkResult(a2, null);
+ check(!phaser.isTerminated());
+ }
+ }
+ } catch (Throwable t) { unexpected(t); }
+
+ //----------------------------------------------------------------
+ // Barrier action completed normally
+ //----------------------------------------------------------------
+ try {
+ final AtomicInteger count = new AtomicInteger(0);
+ final Phaser[] kludge = new Phaser[1];
+ Phaser phaser = new Phaser(3) {
+ @Override
+ protected boolean onAdvance(int phase, int registeredParties) {
+ int countPhase = count.getAndIncrement();
+ equal(countPhase, phase);
+ equal(kludge[0].getPhase(), phase);
+ equal(kludge[0].getRegisteredParties(), registeredParties);
+ if (phase >= 3)
+ return true; // terminate
+
+ return false;
+ }
+ };
+ kludge[0] = phaser;
+ equal(phaser.getRegisteredParties(), 3);
+ Iterator<Awaiter> awaiters = awaiterIterator(phaser);
+ for (int i = 0; i < 4; i++) {
+ Awaiter a1 = awaiters.next(); a1.start();
+ Awaiter a2 = awaiters.next(); a2.start();
+ toTheStartingGate();
+ while (phaser.getArrivedParties() < 2) Thread.yield();
+ phaser.arrive();
+ a1.join();
+ a2.join();
+ checkResult(a1, null);
+ checkResult(a2, null);
+ equal(count.get(), i+1);
+ if (i < 3) {
+ check(!phaser.isTerminated());
+ equal(phaser.getRegisteredParties(), 3);
+ equal(phaser.getArrivedParties(), 0);
+ equal(phaser.getUnarrivedParties(), 3);
+ equal(phaser.getPhase(), count.get());
+ } else
+ checkTerminated(phaser);
+ }
+ } catch (Throwable t) { unexpected(t); }
+
+ }
+
+ //--------------------- Infrastructure ---------------------------
+ static volatile int passed = 0, failed = 0;
+ static void pass() {passed++;}
+ static void fail() {failed++; Thread.dumpStack();}
+ static void fail(String msg) {System.out.println(msg); fail();}
+ static void unexpected(Throwable t) {failed++; t.printStackTrace();}
+ static void check(boolean cond) {if (cond) pass(); else fail();}
+ static void equal(Object x, Object y) {
+ if (x == null ? y == null : x.equals(y)) pass();
+ else fail(x + " not equal to " + y);}
+ public static void main(String[] args) throws Throwable {
+ try {realMain(args);} catch (Throwable t) {unexpected(t);}
+ System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
+ if (failed > 0) throw new AssertionError("Some tests failed");}
+}
diff --git a/test/java/util/concurrent/ScheduledThreadPoolExecutor/DelayOverflow.java b/test/java/util/concurrent/ScheduledThreadPoolExecutor/DelayOverflow.java
index 9df0235..a89aa18 100644
--- a/test/java/util/concurrent/ScheduledThreadPoolExecutor/DelayOverflow.java
+++ b/test/java/util/concurrent/ScheduledThreadPoolExecutor/DelayOverflow.java
@@ -21,6 +21,17 @@
*/
/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+
+/*
* @test
* @bug 6725789
* @summary Check for long overflow in task time comparison.
diff --git a/test/java/util/concurrent/forkjoin/Integrate.java b/test/java/util/concurrent/forkjoin/Integrate.java
new file mode 100644
index 0000000..0adfeec
--- /dev/null
+++ b/test/java/util/concurrent/forkjoin/Integrate.java
@@ -0,0 +1,265 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+
+/*
+ * @test
+ * @bug 6865571
+ * @summary Numerical Integration using fork/join
+ * @run main Integrate reps=1 forkPolicy=dynamic
+ * @run main Integrate reps=1 forkPolicy=serial
+ * @run main Integrate reps=1 forkPolicy=fork
+ */
+
+import java.util.concurrent.ForkJoinPool;
+import java.util.concurrent.RecursiveAction;
+
+/**
+ * Sample program using Gaussian Quadrature for numerical integration.
+ * This version uses a simplified hardwired function. Inspired by a
+ * <A href="http://www.cs.uga.edu/~dkl/filaments/dist.html">
+ * Filaments</A> demo program.
+ */
+public final class Integrate {
+
+ static final double errorTolerance = 1.0e-11;
+ /** for time conversion */
+ static final long NPS = (1000L * 1000 * 1000);
+
+ static final int SERIAL = -1;
+ static final int DYNAMIC = 0;
+ static final int FORK = 1;
+
+ // the function to integrate
+ static double computeFunction(double x) {
+ return (x * x + 1.0) * x;
+ }
+
+ static final double start = 0.0;
+ static final double end = 1536.0;
+ /*
+ * The number of recursive calls for
+ * integrate from start to end.
+ * (Empirically determined)
+ */
+ static final int calls = 263479047;
+
+ static String keywordValue(String[] args, String keyword) {
+ for (String arg : args)
+ if (arg.startsWith(keyword))
+ return arg.substring(keyword.length() + 1);
+ return null;
+ }
+
+ static int intArg(String[] args, String keyword, int defaultValue) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? defaultValue : Integer.parseInt(val);
+ }
+
+ static int policyArg(String[] args, String keyword, int defaultPolicy) {
+ String val = keywordValue(args, keyword);
+ if (val == null) return defaultPolicy;
+ if (val.equals("dynamic")) return DYNAMIC;
+ if (val.equals("serial")) return SERIAL;
+ if (val.equals("fork")) return FORK;
+ throw new Error();
+ }
+
+ /**
+ * Usage: Integrate [procs=N] [reps=N] forkPolicy=serial|dynamic|fork
+ */
+ public static void main(String[] args) throws Exception {
+ final int procs = intArg(args, "procs",
+ Runtime.getRuntime().availableProcessors());
+ final int forkPolicy = policyArg(args, "forkPolicy", DYNAMIC);
+
+ ForkJoinPool g = new ForkJoinPool(procs);
+ System.out.println("Integrating from " + start + " to " + end +
+ " forkPolicy = " + forkPolicy);
+ long lastTime = System.nanoTime();
+
+ for (int reps = intArg(args, "reps", 10); reps > 0; reps--) {
+ double a;
+ if (forkPolicy == SERIAL)
+ a = SQuad.computeArea(g, start, end);
+ else if (forkPolicy == FORK)
+ a = FQuad.computeArea(g, start, end);
+ else
+ a = DQuad.computeArea(g, start, end);
+ long now = System.nanoTime();
+ double s = (double) (now - lastTime) / NPS;
+ lastTime = now;
+ System.out.printf("Calls/sec: %12d", (long) (calls / s));
+ System.out.printf(" Time: %7.3f", s);
+ System.out.printf(" Area: %12.1f", a);
+ System.out.println();
+ }
+ System.out.println(g);
+ g.shutdown();
+ }
+
+
+ // Sequential version
+ static final class SQuad extends RecursiveAction {
+ static double computeArea(ForkJoinPool pool, double l, double r) {
+ SQuad q = new SQuad(l, r, 0);
+ pool.invoke(q);
+ return q.area;
+ }
+
+ final double left; // lower bound
+ final double right; // upper bound
+ double area;
+
+ SQuad(double l, double r, double a) {
+ this.left = l; this.right = r; this.area = a;
+ }
+
+ public final void compute() {
+ double l = left;
+ double r = right;
+ area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
+ }
+
+ static final double recEval(double l, double r, double fl,
+ double fr, double a) {
+ double h = (r - l) * 0.5;
+ double c = l + h;
+ double fc = (c * c + 1.0) * c;
+ double hh = h * 0.5;
+ double al = (fl + fc) * hh;
+ double ar = (fr + fc) * hh;
+ double alr = al + ar;
+ if (Math.abs(alr - a) <= errorTolerance)
+ return alr;
+ else
+ return recEval(c, r, fc, fr, ar) + recEval(l, c, fl, fc, al);
+ }
+
+ }
+
+ //....................................
+
+ // ForkJoin version
+ static final class FQuad extends RecursiveAction {
+ static double computeArea(ForkJoinPool pool, double l, double r) {
+ FQuad q = new FQuad(l, r, 0);
+ pool.invoke(q);
+ return q.area;
+ }
+
+ final double left; // lower bound
+ final double right; // upper bound
+ double area;
+
+ FQuad(double l, double r, double a) {
+ this.left = l; this.right = r; this.area = a;
+ }
+
+ public final void compute() {
+ double l = left;
+ double r = right;
+ area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
+ }
+
+ static final double recEval(double l, double r, double fl,
+ double fr, double a) {
+ double h = (r - l) * 0.5;
+ double c = l + h;
+ double fc = (c * c + 1.0) * c;
+ double hh = h * 0.5;
+ double al = (fl + fc) * hh;
+ double ar = (fr + fc) * hh;
+ double alr = al + ar;
+ if (Math.abs(alr - a) <= errorTolerance)
+ return alr;
+ FQuad q = new FQuad(l, c, al);
+ q.fork();
+ ar = recEval(c, r, fc, fr, ar);
+ if (!q.tryUnfork()) {
+ q.quietlyHelpJoin();
+ return ar + q.area;
+ }
+ return ar + recEval(l, c, fl, fc, al);
+ }
+
+ }
+
+ // ...........................
+
+ // Version using on-demand Fork
+ static final class DQuad extends RecursiveAction {
+ static double computeArea(ForkJoinPool pool, double l, double r) {
+ DQuad q = new DQuad(l, r, 0);
+ pool.invoke(q);
+ return q.area;
+ }
+
+ final double left; // lower bound
+ final double right; // upper bound
+ double area;
+
+ DQuad(double l, double r, double a) {
+ this.left = l; this.right = r; this.area = a;
+ }
+
+ public final void compute() {
+ double l = left;
+ double r = right;
+ area = recEval(l, r, (l * l + 1.0) * l, (r * r + 1.0) * r, area);
+ }
+
+ static final double recEval(double l, double r, double fl,
+ double fr, double a) {
+ double h = (r - l) * 0.5;
+ double c = l + h;
+ double fc = (c * c + 1.0) * c;
+ double hh = h * 0.5;
+ double al = (fl + fc) * hh;
+ double ar = (fr + fc) * hh;
+ double alr = al + ar;
+ if (Math.abs(alr - a) <= errorTolerance)
+ return alr;
+ DQuad q = null;
+ if (getSurplusQueuedTaskCount() <= 3)
+ (q = new DQuad(l, c, al)).fork();
+ ar = recEval(c, r, fc, fr, ar);
+ if (q != null && !q.tryUnfork()) {
+ q.quietlyHelpJoin();
+ return ar + q.area;
+ }
+ return ar + recEval(l, c, fl, fc, al);
+ }
+
+ }
+
+}
diff --git a/test/java/util/concurrent/forkjoin/NQueensCS.java b/test/java/util/concurrent/forkjoin/NQueensCS.java
new file mode 100644
index 0000000..d36e581
--- /dev/null
+++ b/test/java/util/concurrent/forkjoin/NQueensCS.java
@@ -0,0 +1,174 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/licenses/publicdomain
+ */
+
+/*
+ * @test
+ * @bug 6865571
+ * @summary Solve NQueens using fork/join
+ * @run main NQueensCS maxBoardSize=11 reps=1
+ * @run main NQueensCS maxBoardSize=11 reps=1 procs=8
+ */
+
+import java.util.Arrays;
+import java.util.concurrent.ForkJoinPool;
+import java.util.concurrent.RecursiveAction;
+
+public class NQueensCS extends RecursiveAction {
+
+ static long lastStealCount;
+ static int boardSize;
+
+ static final int[] expectedSolutions = new int[] {
+ 0, 1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200,
+ 73712, 365596, 2279184, 14772512, 95815104, 666090624
+ }; // see http://www.durangobill.com/N_Queens.html
+
+ static String keywordValue(String[] args, String keyword) {
+ for (String arg : args)
+ if (arg.startsWith(keyword))
+ return arg.substring(keyword.length() + 1);
+ return null;
+ }
+
+ static int intArg(String[] args, String keyword, int defaultValue) {
+ String val = keywordValue(args, keyword);
+ return (val == null) ? defaultValue : Integer.parseInt(val);
+ }
+
+ /** for time conversion */
+ static final long NPS = (1000L * 1000L * 1000L);
+
+ /**
+ * Usage: NQueensCS [minBoardSize=N] [maxBoardSize=N] [procs=N] [reps=N]
+ */
+ public static void main(String[] args) throws Exception {
+ // Board sizes too small: hard to measure well.
+ // Board sizes too large: take too long to run.
+ final int minBoardSize = intArg(args, "minBoardSize", 8);
+ final int maxBoardSize = intArg(args, "maxBoardSize", 15);
+
+ final int procs = intArg(args, "procs", 0);
+
+ for (int reps = intArg(args, "reps", 10); reps > 0; reps--) {
+ ForkJoinPool g = (procs == 0) ?
+ new ForkJoinPool() :
+ new ForkJoinPool(procs);
+ lastStealCount = g.getStealCount();
+ for (int i = minBoardSize; i <= maxBoardSize; i++)
+ test(g, i);
+ System.out.println(g);
+ g.shutdown();
+ }
+ }
+
+ static void test(ForkJoinPool g, int i) throws Exception {
+ boardSize = i;
+ int ps = g.getParallelism();
+ long start = System.nanoTime();
+ NQueensCS task = new NQueensCS(new int[0]);
+ g.invoke(task);
+ int solutions = task.solutions;
+ long time = System.nanoTime() - start;
+ double secs = (double) time / NPS;
+ if (solutions != expectedSolutions[i])
+ throw new Error();
+ System.out.printf("NQueensCS %3d", i);
+ System.out.printf(" Time: %7.3f", secs);
+ long sc = g.getStealCount();
+ long ns = sc - lastStealCount;
+ lastStealCount = sc;
+ System.out.printf(" Steals/t: %5d", ns/ps);
+ System.out.println();
+ }
+
+ // Boards are represented as arrays where each cell
+ // holds the column number of the queen in that row
+
+ final int[] sofar;
+ NQueensCS nextSubtask; // to link subtasks
+ int solutions;
+ NQueensCS(int[] a) {
+ this.sofar = a;
+ }
+
+ public final void compute() {
+ NQueensCS subtasks;
+ int bs = boardSize;
+ if (sofar.length >= bs)
+ solutions = 1;
+ else if ((subtasks = explore(sofar, bs)) != null)
+ solutions = processSubtasks(subtasks);
+ }
+
+ private static NQueensCS explore(int[] array, int bs) {
+ int row = array.length;
+ NQueensCS s = null; // subtask list
+ outer:
+ for (int q = 0; q < bs; ++q) {
+ for (int i = 0; i < row; i++) {
+ int p = array[i];
+ if (q == p || q == p - (row - i) || q == p + (row - i))
+ continue outer; // attacked
+ }
+ NQueensCS first = s; // lag forks to ensure 1 kept
+ if (first != null)
+ first.fork();
+ int[] next = Arrays.copyOf(array, row+1);
+ next[row] = q;
+ NQueensCS subtask = new NQueensCS(next);
+ subtask.nextSubtask = first;
+ s = subtask;
+ }
+ return s;
+ }
+
+ private static int processSubtasks(NQueensCS s) {
+ // Always run first the task held instead of forked
+ s.compute();
+ int ns = s.solutions;
+ s = s.nextSubtask;
+ // Then the unstolen ones
+ while (s != null && s.tryUnfork()) {
+ s.compute();
+ ns += s.solutions;
+ s = s.nextSubtask;
+ }
+ // Then wait for the stolen ones
+ while (s != null) {
+ s.join();
+ ns += s.solutions;
+ s = s.nextSubtask;
+ }
+ return ns;
+ }
+}
diff --git a/test/java/util/concurrent/locks/ReentrantLock/CancelledLockLoops.java b/test/java/util/concurrent/locks/ReentrantLock/CancelledLockLoops.java
index 62ef499..fb1c7b5 100644
--- a/test/java/util/concurrent/locks/ReentrantLock/CancelledLockLoops.java
+++ b/test/java/util/concurrent/locks/ReentrantLock/CancelledLockLoops.java
@@ -115,7 +115,7 @@
finally {
lock.unlock();
}
- if (completed != 2)
+ if (c != 2)
throw new Error("Completed != 2");
int r = result;
if (r == 0) // avoid overoptimization
diff --git a/test/java/util/concurrent/locks/ReentrantReadWriteLock/RWMap.java b/test/java/util/concurrent/locks/ReentrantReadWriteLock/RWMap.java
index e81c676..6bcc71c 100644
--- a/test/java/util/concurrent/locks/ReentrantReadWriteLock/RWMap.java
+++ b/test/java/util/concurrent/locks/ReentrantReadWriteLock/RWMap.java
@@ -30,6 +30,7 @@
* Expert Group and released to the public domain, as explained at
* http://creativecommons.org/licenses/publicdomain
*/
+
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.*;