6981113: Add ConcurrentLinkedDeque
Summary: Extend techniques developed for ConcurrentLinkedQueue and LinkedTransferQueue to implement a non-blocking concurrent Deque with interior removes.
Reviewed-by: martin, dholmes, chegar
diff --git a/test/java/util/Collection/BiggernYours.java b/test/java/util/Collection/BiggernYours.java
index 8a0e2d1..d1e1e61 100644
--- a/test/java/util/Collection/BiggernYours.java
+++ b/test/java/util/Collection/BiggernYours.java
@@ -174,6 +174,11 @@
public int size() {return randomize(super.size());}});
testCollections(
+ new ConcurrentLinkedDeque(),
+ new ConcurrentLinkedDeque() {
+ public int size() {return randomize(super.size());}});
+
+ testCollections(
new ConcurrentLinkedQueue(),
new ConcurrentLinkedQueue() {
public int size() {return randomize(super.size());}});
diff --git a/test/java/util/Collection/IteratorAtEnd.java b/test/java/util/Collection/IteratorAtEnd.java
index 4f9cd0a..9d10f33 100644
--- a/test/java/util/Collection/IteratorAtEnd.java
+++ b/test/java/util/Collection/IteratorAtEnd.java
@@ -48,6 +48,7 @@
testCollection(new PriorityQueue());
testCollection(new LinkedBlockingQueue());
testCollection(new ArrayBlockingQueue(100));
+ testCollection(new ConcurrentLinkedDeque());
testCollection(new ConcurrentLinkedQueue());
testCollection(new LinkedTransferQueue());
diff --git a/test/java/util/Collection/MOAT.java b/test/java/util/Collection/MOAT.java
index 1334474..4de8ca6 100644
--- a/test/java/util/Collection/MOAT.java
+++ b/test/java/util/Collection/MOAT.java
@@ -75,6 +75,7 @@
testCollection(new ArrayBlockingQueue<Integer>(20));
testCollection(new LinkedBlockingQueue<Integer>(20));
testCollection(new LinkedBlockingDeque<Integer>(20));
+ testCollection(new ConcurrentLinkedDeque<Integer>());
testCollection(new ConcurrentLinkedQueue<Integer>());
testCollection(new LinkedTransferQueue<Integer>());
testCollection(new ConcurrentSkipListSet<Integer>());
@@ -431,8 +432,9 @@
q.poll();
equal(q.size(), 4);
checkFunctionalInvariants(q);
- if ((q instanceof LinkedBlockingQueue) ||
- (q instanceof LinkedBlockingDeque) ||
+ if ((q instanceof LinkedBlockingQueue) ||
+ (q instanceof LinkedBlockingDeque) ||
+ (q instanceof ConcurrentLinkedDeque) ||
(q instanceof ConcurrentLinkedQueue)) {
testQueueIteratorRemove(q);
}
diff --git a/test/java/util/Collections/RacingCollections.java b/test/java/util/Collections/RacingCollections.java
index ae3abbe..1bc513e 100644
--- a/test/java/util/Collections/RacingCollections.java
+++ b/test/java/util/Collections/RacingCollections.java
@@ -235,6 +235,7 @@
new ArrayList<Queue<Integer>>(newConcurrentDeques());
list.add(new LinkedBlockingQueue<Integer>(10));
list.add(new LinkedTransferQueue<Integer>());
+ list.add(new ConcurrentLinkedQueue<Integer>());
return list;
}
@@ -248,6 +249,7 @@
private static List<Deque<Integer>> newConcurrentDeques() {
List<Deque<Integer>> list = new ArrayList<Deque<Integer>>();
list.add(new LinkedBlockingDeque<Integer>(10));
+ list.add(new ConcurrentLinkedDeque<Integer>());
return list;
}
diff --git a/test/java/util/Deque/ChorusLine.java b/test/java/util/Deque/ChorusLine.java
index d8711f6..5dbb523 100644
--- a/test/java/util/Deque/ChorusLine.java
+++ b/test/java/util/Deque/ChorusLine.java
@@ -129,6 +129,7 @@
deqs.add(new ArrayDeque<Integer>());
deqs.add(new LinkedList<Integer>());
deqs.add(new LinkedBlockingDeque<Integer>());
+ deqs.add(new ConcurrentLinkedDeque<Integer>());
equal(deqs);
diff --git a/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java b/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java
index ee9cb3e..b993628 100644
--- a/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java
+++ b/test/java/util/concurrent/ConcurrentQueues/ConcurrentQueueLoops.java
@@ -55,6 +55,7 @@
Collection<Queue<Integer>> concurrentQueues() {
List<Queue<Integer>> queues = new ArrayList<Queue<Integer>>();
+ queues.add(new ConcurrentLinkedDeque<Integer>());
queues.add(new ConcurrentLinkedQueue<Integer>());
queues.add(new ArrayBlockingQueue<Integer>(items, false));
//queues.add(new ArrayBlockingQueue<Integer>(count, true));
@@ -105,7 +106,7 @@
final Queue<Integer> queue;
final CyclicBarrier barrier;
int items;
- Stage (Queue<Integer> q, CyclicBarrier b, int items) {
+ Stage(Queue<Integer> q, CyclicBarrier b, int items) {
queue = q;
barrier = b;
this.items = items;
diff --git a/test/java/util/concurrent/ConcurrentQueues/GCRetention.java b/test/java/util/concurrent/ConcurrentQueues/GCRetention.java
index 3376f31..1786ed3 100644
--- a/test/java/util/concurrent/ConcurrentQueues/GCRetention.java
+++ b/test/java/util/concurrent/ConcurrentQueues/GCRetention.java
@@ -40,6 +40,7 @@
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;
@@ -62,6 +63,7 @@
Collection<Queue<Boolean>> queues() {
List<Queue<Boolean>> queues = new ArrayList<Queue<Boolean>>();
+ queues.add(new ConcurrentLinkedDeque<Boolean>());
queues.add(new ConcurrentLinkedQueue<Boolean>());
queues.add(new ArrayBlockingQueue<Boolean>(count, false));
queues.add(new ArrayBlockingQueue<Boolean>(count, true));
diff --git a/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java b/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java
index af34b0c..36411ad 100644
--- a/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java
+++ b/test/java/util/concurrent/ConcurrentQueues/IteratorWeakConsistency.java
@@ -48,6 +48,7 @@
test(new LinkedBlockingQueue(20));
test(new LinkedBlockingDeque());
test(new LinkedBlockingDeque(20));
+ test(new ConcurrentLinkedDeque());
test(new ConcurrentLinkedQueue());
test(new LinkedTransferQueue());
// Other concurrent queues (e.g. ArrayBlockingQueue) do not
diff --git a/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java b/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java
index a3a5fbd..798a148 100644
--- a/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java
+++ b/test/java/util/concurrent/ConcurrentQueues/OfferRemoveLoops.java
@@ -55,6 +55,7 @@
testQueue(new LinkedBlockingDeque());
testQueue(new ArrayBlockingQueue(10));
testQueue(new PriorityBlockingQueue(10));
+ testQueue(new ConcurrentLinkedDeque());
testQueue(new ConcurrentLinkedQueue());
testQueue(new LinkedTransferQueue());
}
diff --git a/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java b/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java
index a646eee..1bccb53 100644
--- a/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java
+++ b/test/java/util/concurrent/ConcurrentQueues/RemovePollRace.java
@@ -41,6 +41,7 @@
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentLinkedDeque;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.LinkedBlockingDeque;
@@ -62,6 +63,7 @@
Collection<Queue<Boolean>> concurrentQueues() {
List<Queue<Boolean>> queues = new ArrayList<Queue<Boolean>>();
+ queues.add(new ConcurrentLinkedDeque<Boolean>());
queues.add(new ConcurrentLinkedQueue<Boolean>());
queues.add(new ArrayBlockingQueue<Boolean>(count, false));
queues.add(new ArrayBlockingQueue<Boolean>(count, true));