blob: 789373d3b2e98b69789e894e6d26777b1ffe9710 [file] [log] [blame]
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001/*
2 * Written by Doug Lea with assistance from members of JCP JSR-166
3 * Expert Group and released to the public domain, as explained at
4 * http://creativecommons.org/publicdomain/zero/1.0/
5 */
6
7package jsr166;
8
Narayan Kamath8e9a0e92015-04-28 11:40:00 +01009import static java.util.concurrent.TimeUnit.MILLISECONDS;
10
Calin Juravle8f0d92b2013-08-01 17:26:00 +010011import java.util.ArrayList;
Narayan Kamath8e9a0e92015-04-28 11:40:00 +010012import java.util.Arrays;
Calin Juravle8f0d92b2013-08-01 17:26:00 +010013import java.util.Collection;
Narayan Kamath8e9a0e92015-04-28 11:40:00 +010014import java.util.Deque;
Calin Juravle8f0d92b2013-08-01 17:26:00 +010015import java.util.Iterator;
16import java.util.NoSuchElementException;
17import java.util.Queue;
18import java.util.concurrent.BlockingDeque;
19import java.util.concurrent.BlockingQueue;
20import java.util.concurrent.CountDownLatch;
21import java.util.concurrent.Executors;
22import java.util.concurrent.ExecutorService;
23import java.util.concurrent.LinkedBlockingDeque;
Narayan Kamath8e9a0e92015-04-28 11:40:00 +010024
25import junit.framework.Test;
Calin Juravle8f0d92b2013-08-01 17:26:00 +010026
27public class LinkedBlockingDequeTest extends JSR166TestCase {
28
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +000029 public static class Unbounded extends BlockingQueueTest {
30 protected BlockingQueue emptyCollection() {
31 return new LinkedBlockingDeque();
32 }
33 }
34
35 public static class Bounded extends BlockingQueueTest {
36 protected BlockingQueue emptyCollection() {
37 return new LinkedBlockingDeque(SIZE);
38 }
39 }
40
41 // android-note: Removed because the CTS runner does a bad job of
42 // retrying tests that have suite() declarations.
Narayan Kamath8e9a0e92015-04-28 11:40:00 +010043 //
44 // public static void main(String[] args) {
45 // main(suite(), args);
46 // }
Narayan Kamath8e9a0e92015-04-28 11:40:00 +010047 // public static Test suite() {
48 // return newTestSuite(LinkedBlockingDequeTest.class,
49 // new Unbounded().testSuite(),
50 // new Bounded().testSuite());
51 // }
52
Calin Juravle8f0d92b2013-08-01 17:26:00 +010053 /**
54 * Returns a new deque of given size containing consecutive
55 * Integers 0 ... n.
56 */
57 private LinkedBlockingDeque<Integer> populatedDeque(int n) {
58 LinkedBlockingDeque<Integer> q =
59 new LinkedBlockingDeque<Integer>(n);
60 assertTrue(q.isEmpty());
61 for (int i = 0; i < n; i++)
62 assertTrue(q.offer(new Integer(i)));
63 assertFalse(q.isEmpty());
64 assertEquals(0, q.remainingCapacity());
65 assertEquals(n, q.size());
66 return q;
67 }
68
69 /**
70 * isEmpty is true before add, false after
71 */
72 public void testEmpty() {
73 LinkedBlockingDeque q = new LinkedBlockingDeque();
74 assertTrue(q.isEmpty());
75 q.add(new Integer(1));
76 assertFalse(q.isEmpty());
77 q.add(new Integer(2));
78 q.removeFirst();
79 q.removeFirst();
80 assertTrue(q.isEmpty());
81 }
82
83 /**
84 * size changes when elements added and removed
85 */
86 public void testSize() {
87 LinkedBlockingDeque q = populatedDeque(SIZE);
88 for (int i = 0; i < SIZE; ++i) {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +000089 assertEquals(SIZE - i, q.size());
Calin Juravle8f0d92b2013-08-01 17:26:00 +010090 q.removeFirst();
91 }
92 for (int i = 0; i < SIZE; ++i) {
93 assertEquals(i, q.size());
94 q.add(new Integer(i));
95 }
96 }
97
98 /**
99 * offerFirst(null) throws NullPointerException
100 */
101 public void testOfferFirstNull() {
102 LinkedBlockingDeque q = new LinkedBlockingDeque();
103 try {
104 q.offerFirst(null);
105 shouldThrow();
106 } catch (NullPointerException success) {}
107 }
108
109 /**
110 * offerLast(null) throws NullPointerException
111 */
112 public void testOfferLastNull() {
113 LinkedBlockingDeque q = new LinkedBlockingDeque();
114 try {
115 q.offerLast(null);
116 shouldThrow();
117 } catch (NullPointerException success) {}
118 }
119
120 /**
121 * OfferFirst succeeds
122 */
123 public void testOfferFirst() {
124 LinkedBlockingDeque q = new LinkedBlockingDeque();
125 assertTrue(q.offerFirst(new Integer(0)));
126 assertTrue(q.offerFirst(new Integer(1)));
127 }
128
129 /**
130 * OfferLast succeeds
131 */
132 public void testOfferLast() {
133 LinkedBlockingDeque q = new LinkedBlockingDeque();
134 assertTrue(q.offerLast(new Integer(0)));
135 assertTrue(q.offerLast(new Integer(1)));
136 }
137
138 /**
139 * pollFirst succeeds unless empty
140 */
141 public void testPollFirst() {
142 LinkedBlockingDeque q = populatedDeque(SIZE);
143 for (int i = 0; i < SIZE; ++i) {
144 assertEquals(i, q.pollFirst());
145 }
146 assertNull(q.pollFirst());
147 }
148
149 /**
150 * pollLast succeeds unless empty
151 */
152 public void testPollLast() {
153 LinkedBlockingDeque q = populatedDeque(SIZE);
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000154 for (int i = SIZE - 1; i >= 0; --i) {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100155 assertEquals(i, q.pollLast());
156 }
157 assertNull(q.pollLast());
158 }
159
160 /**
161 * peekFirst returns next element, or null if empty
162 */
163 public void testPeekFirst() {
164 LinkedBlockingDeque q = populatedDeque(SIZE);
165 for (int i = 0; i < SIZE; ++i) {
166 assertEquals(i, q.peekFirst());
167 assertEquals(i, q.pollFirst());
168 assertTrue(q.peekFirst() == null ||
169 !q.peekFirst().equals(i));
170 }
171 assertNull(q.peekFirst());
172 }
173
174 /**
175 * peek returns next element, or null if empty
176 */
177 public void testPeek() {
178 LinkedBlockingDeque q = populatedDeque(SIZE);
179 for (int i = 0; i < SIZE; ++i) {
180 assertEquals(i, q.peek());
181 assertEquals(i, q.pollFirst());
182 assertTrue(q.peek() == null ||
183 !q.peek().equals(i));
184 }
185 assertNull(q.peek());
186 }
187
188 /**
189 * peekLast returns next element, or null if empty
190 */
191 public void testPeekLast() {
192 LinkedBlockingDeque q = populatedDeque(SIZE);
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000193 for (int i = SIZE - 1; i >= 0; --i) {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100194 assertEquals(i, q.peekLast());
195 assertEquals(i, q.pollLast());
196 assertTrue(q.peekLast() == null ||
197 !q.peekLast().equals(i));
198 }
199 assertNull(q.peekLast());
200 }
201
202 /**
203 * getFirst() returns first element, or throws NSEE if empty
204 */
205 public void testFirstElement() {
206 LinkedBlockingDeque q = populatedDeque(SIZE);
207 for (int i = 0; i < SIZE; ++i) {
208 assertEquals(i, q.getFirst());
209 assertEquals(i, q.pollFirst());
210 }
211 try {
212 q.getFirst();
213 shouldThrow();
214 } catch (NoSuchElementException success) {}
215 assertNull(q.peekFirst());
216 }
217
218 /**
219 * getLast() returns last element, or throws NSEE if empty
220 */
221 public void testLastElement() {
222 LinkedBlockingDeque q = populatedDeque(SIZE);
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000223 for (int i = SIZE - 1; i >= 0; --i) {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100224 assertEquals(i, q.getLast());
225 assertEquals(i, q.pollLast());
226 }
227 try {
228 q.getLast();
229 shouldThrow();
230 } catch (NoSuchElementException success) {}
231 assertNull(q.peekLast());
232 }
233
234 /**
235 * removeFirst() removes first element, or throws NSEE if empty
236 */
237 public void testRemoveFirst() {
238 LinkedBlockingDeque q = populatedDeque(SIZE);
239 for (int i = 0; i < SIZE; ++i) {
240 assertEquals(i, q.removeFirst());
241 }
242 try {
243 q.removeFirst();
244 shouldThrow();
245 } catch (NoSuchElementException success) {}
246 assertNull(q.peekFirst());
247 }
248
249 /**
250 * removeLast() removes last element, or throws NSEE if empty
251 */
252 public void testRemoveLast() {
253 LinkedBlockingDeque q = populatedDeque(SIZE);
254 for (int i = SIZE - 1; i >= 0; --i) {
255 assertEquals(i, q.removeLast());
256 }
257 try {
258 q.removeLast();
259 shouldThrow();
260 } catch (NoSuchElementException success) {}
261 assertNull(q.peekLast());
262 }
263
264 /**
265 * remove removes next element, or throws NSEE if empty
266 */
267 public void testRemove() {
268 LinkedBlockingDeque q = populatedDeque(SIZE);
269 for (int i = 0; i < SIZE; ++i) {
270 assertEquals(i, q.remove());
271 }
272 try {
273 q.remove();
274 shouldThrow();
275 } catch (NoSuchElementException success) {}
276 }
277
278 /**
279 * removeFirstOccurrence(x) removes x and returns true if present
280 */
281 public void testRemoveFirstOccurrence() {
282 LinkedBlockingDeque q = populatedDeque(SIZE);
Narayan Kamath8e9a0e92015-04-28 11:40:00 +0100283 for (int i = 1; i < SIZE; i += 2) {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100284 assertTrue(q.removeFirstOccurrence(new Integer(i)));
285 }
Narayan Kamath8e9a0e92015-04-28 11:40:00 +0100286 for (int i = 0; i < SIZE; i += 2) {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100287 assertTrue(q.removeFirstOccurrence(new Integer(i)));
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000288 assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100289 }
290 assertTrue(q.isEmpty());
291 }
292
293 /**
294 * removeLastOccurrence(x) removes x and returns true if present
295 */
296 public void testRemoveLastOccurrence() {
297 LinkedBlockingDeque q = populatedDeque(SIZE);
Narayan Kamath8e9a0e92015-04-28 11:40:00 +0100298 for (int i = 1; i < SIZE; i += 2) {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100299 assertTrue(q.removeLastOccurrence(new Integer(i)));
300 }
Narayan Kamath8e9a0e92015-04-28 11:40:00 +0100301 for (int i = 0; i < SIZE; i += 2) {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100302 assertTrue(q.removeLastOccurrence(new Integer(i)));
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000303 assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100304 }
305 assertTrue(q.isEmpty());
306 }
307
308 /**
309 * peekFirst returns element inserted with addFirst
310 */
311 public void testAddFirst() {
312 LinkedBlockingDeque q = populatedDeque(3);
313 q.pollLast();
314 q.addFirst(four);
315 assertSame(four, q.peekFirst());
316 }
317
318 /**
319 * peekLast returns element inserted with addLast
320 */
321 public void testAddLast() {
322 LinkedBlockingDeque q = populatedDeque(3);
323 q.pollLast();
324 q.addLast(four);
325 assertSame(four, q.peekLast());
326 }
327
328 /**
329 * A new deque has the indicated capacity, or Integer.MAX_VALUE if
330 * none given
331 */
332 public void testConstructor1() {
333 assertEquals(SIZE, new LinkedBlockingDeque(SIZE).remainingCapacity());
334 assertEquals(Integer.MAX_VALUE, new LinkedBlockingDeque().remainingCapacity());
335 }
336
337 /**
338 * Constructor throws IllegalArgumentException if capacity argument nonpositive
339 */
340 public void testConstructor2() {
341 try {
342 new LinkedBlockingDeque(0);
343 shouldThrow();
344 } catch (IllegalArgumentException success) {}
345 }
346
347 /**
348 * Initializing from null Collection throws NullPointerException
349 */
350 public void testConstructor3() {
351 try {
352 new LinkedBlockingDeque(null);
353 shouldThrow();
354 } catch (NullPointerException success) {}
355 }
356
357 /**
358 * Initializing from Collection of null elements throws NullPointerException
359 */
360 public void testConstructor4() {
361 Collection<Integer> elements = Arrays.asList(new Integer[SIZE]);
362 try {
363 new LinkedBlockingDeque(elements);
364 shouldThrow();
365 } catch (NullPointerException success) {}
366 }
367
368 /**
369 * Initializing from Collection with some null elements throws
370 * NullPointerException
371 */
372 public void testConstructor5() {
373 Integer[] ints = new Integer[SIZE];
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000374 for (int i = 0; i < SIZE - 1; ++i)
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100375 ints[i] = i;
376 Collection<Integer> elements = Arrays.asList(ints);
377 try {
378 new LinkedBlockingDeque(elements);
379 shouldThrow();
380 } catch (NullPointerException success) {}
381 }
382
383 /**
384 * Deque contains all elements of collection used to initialize
385 */
386 public void testConstructor6() {
387 Integer[] ints = new Integer[SIZE];
388 for (int i = 0; i < SIZE; ++i)
389 ints[i] = i;
390 LinkedBlockingDeque q = new LinkedBlockingDeque(Arrays.asList(ints));
391 for (int i = 0; i < SIZE; ++i)
392 assertEquals(ints[i], q.poll());
393 }
394
395 /**
396 * Deque transitions from empty to full when elements added
397 */
398 public void testEmptyFull() {
399 LinkedBlockingDeque q = new LinkedBlockingDeque(2);
400 assertTrue(q.isEmpty());
401 assertEquals("should have room for 2", 2, q.remainingCapacity());
402 q.add(one);
403 assertFalse(q.isEmpty());
404 q.add(two);
405 assertFalse(q.isEmpty());
406 assertEquals(0, q.remainingCapacity());
407 assertFalse(q.offer(three));
408 }
409
410 /**
411 * remainingCapacity decreases on add, increases on remove
412 */
413 public void testRemainingCapacity() {
Narayan Kamath8e9a0e92015-04-28 11:40:00 +0100414 BlockingQueue q = populatedDeque(SIZE);
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100415 for (int i = 0; i < SIZE; ++i) {
416 assertEquals(i, q.remainingCapacity());
Narayan Kamath8e9a0e92015-04-28 11:40:00 +0100417 assertEquals(SIZE, q.size() + q.remainingCapacity());
418 assertEquals(i, q.remove());
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100419 }
420 for (int i = 0; i < SIZE; ++i) {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000421 assertEquals(SIZE - i, q.remainingCapacity());
Narayan Kamath8e9a0e92015-04-28 11:40:00 +0100422 assertEquals(SIZE, q.size() + q.remainingCapacity());
423 assertTrue(q.add(i));
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100424 }
425 }
426
427 /**
428 * push(null) throws NPE
429 */
430 public void testPushNull() {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000431 LinkedBlockingDeque q = new LinkedBlockingDeque(1);
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100432 try {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100433 q.push(null);
434 shouldThrow();
435 } catch (NullPointerException success) {}
436 }
437
438 /**
439 * push succeeds if not full; throws ISE if full
440 */
441 public void testPush() {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000442 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
443 for (int i = 0; i < SIZE; ++i) {
444 Integer x = new Integer(i);
445 q.push(x);
446 assertEquals(x, q.peek());
447 }
448 assertEquals(0, q.remainingCapacity());
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100449 try {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100450 q.push(new Integer(SIZE));
451 shouldThrow();
452 } catch (IllegalStateException success) {}
453 }
454
455 /**
456 * peekFirst returns element inserted with push
457 */
458 public void testPushWithPeek() {
459 LinkedBlockingDeque q = populatedDeque(3);
460 q.pollLast();
461 q.push(four);
462 assertSame(four, q.peekFirst());
463 }
464
465 /**
466 * pop removes next element, or throws NSEE if empty
467 */
468 public void testPop() {
469 LinkedBlockingDeque q = populatedDeque(SIZE);
470 for (int i = 0; i < SIZE; ++i) {
471 assertEquals(i, q.pop());
472 }
473 try {
474 q.pop();
475 shouldThrow();
476 } catch (NoSuchElementException success) {}
477 }
478
479 /**
480 * Offer succeeds if not full; fails if full
481 */
482 public void testOffer() {
483 LinkedBlockingDeque q = new LinkedBlockingDeque(1);
484 assertTrue(q.offer(zero));
485 assertFalse(q.offer(one));
486 }
487
488 /**
489 * add succeeds if not full; throws ISE if full
490 */
491 public void testAdd() {
492 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
493 for (int i = 0; i < SIZE; ++i)
494 assertTrue(q.add(new Integer(i)));
495 assertEquals(0, q.remainingCapacity());
496 try {
497 q.add(new Integer(SIZE));
498 shouldThrow();
499 } catch (IllegalStateException success) {}
500 }
501
502 /**
503 * addAll(this) throws IAE
504 */
505 public void testAddAllSelf() {
506 LinkedBlockingDeque q = populatedDeque(SIZE);
507 try {
508 q.addAll(q);
509 shouldThrow();
510 } catch (IllegalArgumentException success) {}
511 }
512
513 /**
514 * addAll of a collection with any null elements throws NPE after
515 * possibly adding some elements
516 */
517 public void testAddAll3() {
518 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
519 Integer[] ints = new Integer[SIZE];
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000520 for (int i = 0; i < SIZE - 1; ++i)
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100521 ints[i] = new Integer(i);
522 Collection<Integer> elements = Arrays.asList(ints);
523 try {
524 q.addAll(elements);
525 shouldThrow();
526 } catch (NullPointerException success) {}
527 }
528
529 /**
530 * addAll throws IllegalStateException if not enough room
531 */
532 public void testAddAll4() {
533 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE - 1);
534 Integer[] ints = new Integer[SIZE];
535 for (int i = 0; i < SIZE; ++i)
536 ints[i] = new Integer(i);
537 Collection<Integer> elements = Arrays.asList(ints);
538 try {
539 q.addAll(elements);
540 shouldThrow();
541 } catch (IllegalStateException success) {}
542 }
543
544 /**
545 * Deque contains all elements, in traversal order, of successful addAll
546 */
547 public void testAddAll5() {
548 Integer[] empty = new Integer[0];
549 Integer[] ints = new Integer[SIZE];
550 for (int i = 0; i < SIZE; ++i)
551 ints[i] = new Integer(i);
552 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
553 assertFalse(q.addAll(Arrays.asList(empty)));
554 assertTrue(q.addAll(Arrays.asList(ints)));
555 for (int i = 0; i < SIZE; ++i)
556 assertEquals(ints[i], q.poll());
557 }
558
559 /**
560 * all elements successfully put are contained
561 */
562 public void testPut() throws InterruptedException {
563 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
564 for (int i = 0; i < SIZE; ++i) {
Narayan Kamath8e9a0e92015-04-28 11:40:00 +0100565 Integer x = new Integer(i);
566 q.put(x);
567 assertTrue(q.contains(x));
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100568 }
569 assertEquals(0, q.remainingCapacity());
570 }
571
572 /**
573 * put blocks interruptibly if full
574 */
575 public void testBlockingPut() throws InterruptedException {
576 final LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
577 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
578 Thread t = newStartedThread(new CheckedRunnable() {
579 public void realRun() throws InterruptedException {
580 for (int i = 0; i < SIZE; ++i)
581 q.put(i);
582 assertEquals(SIZE, q.size());
583 assertEquals(0, q.remainingCapacity());
584
585 Thread.currentThread().interrupt();
586 try {
587 q.put(99);
588 shouldThrow();
589 } catch (InterruptedException success) {}
590 assertFalse(Thread.interrupted());
591
592 pleaseInterrupt.countDown();
593 try {
594 q.put(99);
595 shouldThrow();
596 } catch (InterruptedException success) {}
597 assertFalse(Thread.interrupted());
598 }});
599
600 await(pleaseInterrupt);
601 assertThreadStaysAlive(t);
602 t.interrupt();
603 awaitTermination(t);
604 assertEquals(SIZE, q.size());
605 assertEquals(0, q.remainingCapacity());
606 }
607
608 /**
609 * put blocks interruptibly waiting for take when full
610 */
611 public void testPutWithTake() throws InterruptedException {
612 final int capacity = 2;
613 final LinkedBlockingDeque q = new LinkedBlockingDeque(capacity);
614 final CountDownLatch pleaseTake = new CountDownLatch(1);
615 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
616 Thread t = newStartedThread(new CheckedRunnable() {
617 public void realRun() throws InterruptedException {
618 for (int i = 0; i < capacity; i++)
619 q.put(i);
620 pleaseTake.countDown();
621 q.put(86);
622
623 pleaseInterrupt.countDown();
624 try {
625 q.put(99);
626 shouldThrow();
627 } catch (InterruptedException success) {}
628 assertFalse(Thread.interrupted());
629 }});
630
631 await(pleaseTake);
632 assertEquals(0, q.remainingCapacity());
633 assertEquals(0, q.take());
634
635 await(pleaseInterrupt);
636 assertThreadStaysAlive(t);
637 t.interrupt();
638 awaitTermination(t);
639 assertEquals(0, q.remainingCapacity());
640 }
641
642 /**
643 * timed offer times out if full and elements not taken
644 */
645 public void testTimedOffer() throws InterruptedException {
646 final LinkedBlockingDeque q = new LinkedBlockingDeque(2);
647 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
648 Thread t = newStartedThread(new CheckedRunnable() {
649 public void realRun() throws InterruptedException {
650 q.put(new Object());
651 q.put(new Object());
652 long startTime = System.nanoTime();
653 assertFalse(q.offer(new Object(), timeoutMillis(), MILLISECONDS));
654 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
655 pleaseInterrupt.countDown();
656 try {
657 q.offer(new Object(), 2 * LONG_DELAY_MS, MILLISECONDS);
658 shouldThrow();
659 } catch (InterruptedException success) {}
660 }});
661
662 await(pleaseInterrupt);
663 assertThreadStaysAlive(t);
664 t.interrupt();
665 awaitTermination(t);
666 }
667
668 /**
669 * take retrieves elements in FIFO order
670 */
671 public void testTake() throws InterruptedException {
672 LinkedBlockingDeque q = populatedDeque(SIZE);
673 for (int i = 0; i < SIZE; ++i) {
674 assertEquals(i, q.take());
675 }
676 }
677
678 /**
679 * take removes existing elements until empty, then blocks interruptibly
680 */
681 public void testBlockingTake() throws InterruptedException {
682 final LinkedBlockingDeque q = populatedDeque(SIZE);
683 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
684 Thread t = newStartedThread(new CheckedRunnable() {
685 public void realRun() throws InterruptedException {
686 for (int i = 0; i < SIZE; ++i) {
687 assertEquals(i, q.take());
688 }
689
690 Thread.currentThread().interrupt();
691 try {
692 q.take();
693 shouldThrow();
694 } catch (InterruptedException success) {}
695 assertFalse(Thread.interrupted());
696
697 pleaseInterrupt.countDown();
698 try {
699 q.take();
700 shouldThrow();
701 } catch (InterruptedException success) {}
702 assertFalse(Thread.interrupted());
703 }});
704
705 await(pleaseInterrupt);
706 assertThreadStaysAlive(t);
707 t.interrupt();
708 awaitTermination(t);
709 }
710
711 /**
712 * poll succeeds unless empty
713 */
714 public void testPoll() {
715 LinkedBlockingDeque q = populatedDeque(SIZE);
716 for (int i = 0; i < SIZE; ++i) {
717 assertEquals(i, q.poll());
718 }
719 assertNull(q.poll());
720 }
721
722 /**
723 * timed poll with zero timeout succeeds when non-empty, else times out
724 */
725 public void testTimedPoll0() throws InterruptedException {
726 LinkedBlockingDeque q = populatedDeque(SIZE);
727 for (int i = 0; i < SIZE; ++i) {
728 assertEquals(i, q.poll(0, MILLISECONDS));
729 }
730 assertNull(q.poll(0, MILLISECONDS));
731 }
732
733 /**
734 * timed poll with nonzero timeout succeeds when non-empty, else times out
735 */
736 public void testTimedPoll() throws InterruptedException {
737 LinkedBlockingDeque q = populatedDeque(SIZE);
738 for (int i = 0; i < SIZE; ++i) {
739 long startTime = System.nanoTime();
740 assertEquals(i, q.poll(LONG_DELAY_MS, MILLISECONDS));
741 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
742 }
743 long startTime = System.nanoTime();
744 assertNull(q.poll(timeoutMillis(), MILLISECONDS));
745 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
746 checkEmpty(q);
747 }
748
749 /**
750 * Interrupted timed poll throws InterruptedException instead of
751 * returning timeout status
752 */
753 public void testInterruptedTimedPoll() throws InterruptedException {
754 final BlockingQueue<Integer> q = populatedDeque(SIZE);
755 final CountDownLatch aboutToWait = new CountDownLatch(1);
756 Thread t = newStartedThread(new CheckedRunnable() {
757 public void realRun() throws InterruptedException {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000758 long startTime = System.nanoTime();
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100759 for (int i = 0; i < SIZE; ++i) {
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100760 assertEquals(i, (int) q.poll(LONG_DELAY_MS, MILLISECONDS));
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100761 }
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100762 aboutToWait.countDown();
763 try {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000764 q.poll(LONG_DELAY_MS, MILLISECONDS);
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100765 shouldThrow();
766 } catch (InterruptedException success) {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000767 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100768 }
769 }});
770
771 aboutToWait.await();
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000772 waitForThreadToEnterWaitState(t, LONG_DELAY_MS);
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100773 t.interrupt();
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +0000774 awaitTermination(t);
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100775 checkEmpty(q);
776 }
777
778 /**
779 * putFirst(null) throws NPE
780 */
781 public void testPutFirstNull() throws InterruptedException {
782 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
783 try {
784 q.putFirst(null);
785 shouldThrow();
786 } catch (NullPointerException success) {}
787 }
788
789 /**
790 * all elements successfully putFirst are contained
791 */
792 public void testPutFirst() throws InterruptedException {
793 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
794 for (int i = 0; i < SIZE; ++i) {
Narayan Kamath8e9a0e92015-04-28 11:40:00 +0100795 Integer x = new Integer(i);
796 q.putFirst(x);
797 assertTrue(q.contains(x));
Calin Juravle8f0d92b2013-08-01 17:26:00 +0100798 }
799 assertEquals(0, q.remainingCapacity());
800 }
801
802 /**
803 * putFirst blocks interruptibly if full
804 */
805 public void testBlockingPutFirst() throws InterruptedException {
806 final LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
807 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
808 Thread t = newStartedThread(new CheckedRunnable() {
809 public void realRun() throws InterruptedException {
810 for (int i = 0; i < SIZE; ++i)
811 q.putFirst(i);
812 assertEquals(SIZE, q.size());
813 assertEquals(0, q.remainingCapacity());
814
815 Thread.currentThread().interrupt();
816 try {
817 q.putFirst(99);
818 shouldThrow();
819 } catch (InterruptedException success) {}
820 assertFalse(Thread.interrupted());
821
822 pleaseInterrupt.countDown();
823 try {
824 q.putFirst(99);
825 shouldThrow();
826 } catch (InterruptedException success) {}
827 assertFalse(Thread.interrupted());
828 }});
829
830 await(pleaseInterrupt);
831 assertThreadStaysAlive(t);
832 t.interrupt();
833 awaitTermination(t);
834 assertEquals(SIZE, q.size());
835 assertEquals(0, q.remainingCapacity());
836 }
837
838 /**
839 * putFirst blocks interruptibly waiting for take when full
840 */
841 public void testPutFirstWithTake() throws InterruptedException {
842 final int capacity = 2;
843 final LinkedBlockingDeque q = new LinkedBlockingDeque(capacity);
844 final CountDownLatch pleaseTake = new CountDownLatch(1);
845 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
846 Thread t = newStartedThread(new CheckedRunnable() {
847 public void realRun() throws InterruptedException {
848 for (int i = 0; i < capacity; i++)
849 q.putFirst(i);
850 pleaseTake.countDown();
851 q.putFirst(86);
852
853 pleaseInterrupt.countDown();
854 try {
855 q.putFirst(99);
856 shouldThrow();
857 } catch (InterruptedException success) {}
858 assertFalse(Thread.interrupted());
859 }});
860
861 await(pleaseTake);
862 assertEquals(0, q.remainingCapacity());
863 assertEquals(capacity - 1, q.take());
864
865 await(pleaseInterrupt);
866 assertThreadStaysAlive(t);
867 t.interrupt();
868 awaitTermination(t);
869 assertEquals(0, q.remainingCapacity());
870 }
871
872 /**
873 * timed offerFirst times out if full and elements not taken
874 */
875 public void testTimedOfferFirst() throws InterruptedException {
876 final LinkedBlockingDeque q = new LinkedBlockingDeque(2);
877 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
878 Thread t = newStartedThread(new CheckedRunnable() {
879 public void realRun() throws InterruptedException {
880 q.putFirst(new Object());
881 q.putFirst(new Object());
882 long startTime = System.nanoTime();
883 assertFalse(q.offerFirst(new Object(), timeoutMillis(), MILLISECONDS));
884 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
885 pleaseInterrupt.countDown();
886 try {
887 q.offerFirst(new Object(), 2 * LONG_DELAY_MS, MILLISECONDS);
888 shouldThrow();
889 } catch (InterruptedException success) {}
890 }});
891
892 await(pleaseInterrupt);
893 assertThreadStaysAlive(t);
894 t.interrupt();
895 awaitTermination(t);
896 }
897
898 /**
899 * take retrieves elements in FIFO order
900 */
901 public void testTakeFirst() throws InterruptedException {
902 LinkedBlockingDeque q = populatedDeque(SIZE);
903 for (int i = 0; i < SIZE; ++i) {
904 assertEquals(i, q.takeFirst());
905 }
906 }
907
908 /**
909 * takeFirst() blocks interruptibly when empty
910 */
911 public void testTakeFirstFromEmptyBlocksInterruptibly() {
912 final BlockingDeque q = new LinkedBlockingDeque();
913 final CountDownLatch threadStarted = new CountDownLatch(1);
914 Thread t = newStartedThread(new CheckedRunnable() {
915 public void realRun() {
916 threadStarted.countDown();
917 try {
918 q.takeFirst();
919 shouldThrow();
920 } catch (InterruptedException success) {}
921 assertFalse(Thread.interrupted());
922 }});
923
924 await(threadStarted);
925 assertThreadStaysAlive(t);
926 t.interrupt();
927 awaitTermination(t);
928 }
929
930 /**
931 * takeFirst() throws InterruptedException immediately if interrupted
932 * before waiting
933 */
934 public void testTakeFirstFromEmptyAfterInterrupt() {
935 final BlockingDeque q = new LinkedBlockingDeque();
936 Thread t = newStartedThread(new CheckedRunnable() {
937 public void realRun() {
938 Thread.currentThread().interrupt();
939 try {
940 q.takeFirst();
941 shouldThrow();
942 } catch (InterruptedException success) {}
943 assertFalse(Thread.interrupted());
944 }});
945
946 awaitTermination(t);
947 }
948
949 /**
950 * takeLast() blocks interruptibly when empty
951 */
952 public void testTakeLastFromEmptyBlocksInterruptibly() {
953 final BlockingDeque q = new LinkedBlockingDeque();
954 final CountDownLatch threadStarted = new CountDownLatch(1);
955 Thread t = newStartedThread(new CheckedRunnable() {
956 public void realRun() {
957 threadStarted.countDown();
958 try {
959 q.takeLast();
960 shouldThrow();
961 } catch (InterruptedException success) {}
962 assertFalse(Thread.interrupted());
963 }});
964
965 await(threadStarted);
966 assertThreadStaysAlive(t);
967 t.interrupt();
968 awaitTermination(t);
969 }
970
971 /**
972 * takeLast() throws InterruptedException immediately if interrupted
973 * before waiting
974 */
975 public void testTakeLastFromEmptyAfterInterrupt() {
976 final BlockingDeque q = new LinkedBlockingDeque();
977 Thread t = newStartedThread(new CheckedRunnable() {
978 public void realRun() {
979 Thread.currentThread().interrupt();
980 try {
981 q.takeLast();
982 shouldThrow();
983 } catch (InterruptedException success) {}
984 assertFalse(Thread.interrupted());
985 }});
986
987 awaitTermination(t);
988 }
989
990 /**
991 * takeFirst removes existing elements until empty, then blocks interruptibly
992 */
993 public void testBlockingTakeFirst() throws InterruptedException {
994 final LinkedBlockingDeque q = populatedDeque(SIZE);
995 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
996 Thread t = newStartedThread(new CheckedRunnable() {
997 public void realRun() throws InterruptedException {
998 for (int i = 0; i < SIZE; ++i) {
999 assertEquals(i, q.takeFirst());
1000 }
1001
1002 Thread.currentThread().interrupt();
1003 try {
1004 q.takeFirst();
1005 shouldThrow();
1006 } catch (InterruptedException success) {}
1007 assertFalse(Thread.interrupted());
1008
1009 pleaseInterrupt.countDown();
1010 try {
1011 q.takeFirst();
1012 shouldThrow();
1013 } catch (InterruptedException success) {}
1014 assertFalse(Thread.interrupted());
1015 }});
1016
1017 await(pleaseInterrupt);
1018 assertThreadStaysAlive(t);
1019 t.interrupt();
1020 awaitTermination(t);
1021 }
1022
1023 /**
1024 * timed pollFirst with zero timeout succeeds when non-empty, else times out
1025 */
1026 public void testTimedPollFirst0() throws InterruptedException {
1027 LinkedBlockingDeque q = populatedDeque(SIZE);
1028 for (int i = 0; i < SIZE; ++i) {
1029 assertEquals(i, q.pollFirst(0, MILLISECONDS));
1030 }
1031 assertNull(q.pollFirst(0, MILLISECONDS));
1032 }
1033
1034 /**
1035 * timed pollFirst with nonzero timeout succeeds when non-empty, else times out
1036 */
1037 public void testTimedPollFirst() throws InterruptedException {
1038 LinkedBlockingDeque q = populatedDeque(SIZE);
1039 for (int i = 0; i < SIZE; ++i) {
1040 long startTime = System.nanoTime();
1041 assertEquals(i, q.pollFirst(LONG_DELAY_MS, MILLISECONDS));
1042 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
1043 }
1044 long startTime = System.nanoTime();
1045 assertNull(q.pollFirst(timeoutMillis(), MILLISECONDS));
1046 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
1047 checkEmpty(q);
1048 }
1049
1050 /**
1051 * Interrupted timed pollFirst throws InterruptedException instead of
1052 * returning timeout status
1053 */
1054 public void testInterruptedTimedPollFirst() throws InterruptedException {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001055 final LinkedBlockingDeque q = populatedDeque(SIZE);
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001056 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
1057 Thread t = newStartedThread(new CheckedRunnable() {
1058 public void realRun() throws InterruptedException {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001059 long startTime = System.nanoTime();
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001060 for (int i = 0; i < SIZE; ++i) {
1061 assertEquals(i, q.pollFirst(LONG_DELAY_MS, MILLISECONDS));
1062 }
1063
1064 Thread.currentThread().interrupt();
1065 try {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001066 q.pollFirst(LONG_DELAY_MS, MILLISECONDS);
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001067 shouldThrow();
1068 } catch (InterruptedException success) {}
1069 assertFalse(Thread.interrupted());
1070
1071 pleaseInterrupt.countDown();
1072 try {
1073 q.pollFirst(LONG_DELAY_MS, MILLISECONDS);
1074 shouldThrow();
1075 } catch (InterruptedException success) {}
1076 assertFalse(Thread.interrupted());
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001077 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001078 }});
1079
1080 await(pleaseInterrupt);
1081 assertThreadStaysAlive(t);
1082 t.interrupt();
1083 awaitTermination(t);
1084 }
1085
1086 /**
1087 * timed pollFirst before a delayed offerFirst fails; after offerFirst succeeds;
1088 * on interruption throws
1089 */
1090 public void testTimedPollFirstWithOfferFirst() throws InterruptedException {
1091 final LinkedBlockingDeque q = new LinkedBlockingDeque(2);
1092 final CheckedBarrier barrier = new CheckedBarrier(2);
1093 Thread t = newStartedThread(new CheckedRunnable() {
1094 public void realRun() throws InterruptedException {
1095 long startTime = System.nanoTime();
1096 assertNull(q.pollFirst(timeoutMillis(), MILLISECONDS));
1097 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
1098
1099 barrier.await();
1100
1101 assertSame(zero, q.pollFirst(LONG_DELAY_MS, MILLISECONDS));
1102
1103 Thread.currentThread().interrupt();
1104 try {
1105 q.pollFirst(LONG_DELAY_MS, MILLISECONDS);
1106 shouldThrow();
1107 } catch (InterruptedException success) {}
1108
1109 barrier.await();
1110 try {
1111 q.pollFirst(LONG_DELAY_MS, MILLISECONDS);
1112 shouldThrow();
1113 } catch (InterruptedException success) {}
1114 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
1115 }});
1116
1117 barrier.await();
1118 long startTime = System.nanoTime();
1119 assertTrue(q.offerFirst(zero, LONG_DELAY_MS, MILLISECONDS));
1120 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
1121 barrier.await();
1122 assertThreadStaysAlive(t);
1123 t.interrupt();
1124 awaitTermination(t);
1125 }
1126
1127 /**
1128 * putLast(null) throws NPE
1129 */
1130 public void testPutLastNull() throws InterruptedException {
1131 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
1132 try {
1133 q.putLast(null);
1134 shouldThrow();
1135 } catch (NullPointerException success) {}
1136 }
1137
1138 /**
1139 * all elements successfully putLast are contained
1140 */
1141 public void testPutLast() throws InterruptedException {
1142 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
1143 for (int i = 0; i < SIZE; ++i) {
Narayan Kamath8e9a0e92015-04-28 11:40:00 +01001144 Integer x = new Integer(i);
1145 q.putLast(x);
1146 assertTrue(q.contains(x));
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001147 }
1148 assertEquals(0, q.remainingCapacity());
1149 }
1150
1151 /**
1152 * putLast blocks interruptibly if full
1153 */
1154 public void testBlockingPutLast() throws InterruptedException {
1155 final LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE);
1156 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
1157 Thread t = newStartedThread(new CheckedRunnable() {
1158 public void realRun() throws InterruptedException {
1159 for (int i = 0; i < SIZE; ++i)
1160 q.putLast(i);
1161 assertEquals(SIZE, q.size());
1162 assertEquals(0, q.remainingCapacity());
1163
1164 Thread.currentThread().interrupt();
1165 try {
1166 q.putLast(99);
1167 shouldThrow();
1168 } catch (InterruptedException success) {}
1169 assertFalse(Thread.interrupted());
1170
1171 pleaseInterrupt.countDown();
1172 try {
1173 q.putLast(99);
1174 shouldThrow();
1175 } catch (InterruptedException success) {}
1176 assertFalse(Thread.interrupted());
1177 }});
1178
1179 await(pleaseInterrupt);
1180 assertThreadStaysAlive(t);
1181 t.interrupt();
1182 awaitTermination(t);
1183 assertEquals(SIZE, q.size());
1184 assertEquals(0, q.remainingCapacity());
1185 }
1186
1187 /**
1188 * putLast blocks interruptibly waiting for take when full
1189 */
1190 public void testPutLastWithTake() throws InterruptedException {
1191 final int capacity = 2;
1192 final LinkedBlockingDeque q = new LinkedBlockingDeque(capacity);
1193 final CountDownLatch pleaseTake = new CountDownLatch(1);
1194 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
1195 Thread t = newStartedThread(new CheckedRunnable() {
1196 public void realRun() throws InterruptedException {
1197 for (int i = 0; i < capacity; i++)
1198 q.putLast(i);
1199 pleaseTake.countDown();
1200 q.putLast(86);
1201
1202 pleaseInterrupt.countDown();
1203 try {
1204 q.putLast(99);
1205 shouldThrow();
1206 } catch (InterruptedException success) {}
1207 assertFalse(Thread.interrupted());
1208 }});
1209
1210 await(pleaseTake);
1211 assertEquals(0, q.remainingCapacity());
1212 assertEquals(0, q.take());
1213
1214 await(pleaseInterrupt);
1215 assertThreadStaysAlive(t);
1216 t.interrupt();
1217 awaitTermination(t);
1218 assertEquals(0, q.remainingCapacity());
1219 }
1220
1221 /**
1222 * timed offerLast times out if full and elements not taken
1223 */
1224 public void testTimedOfferLast() throws InterruptedException {
1225 final LinkedBlockingDeque q = new LinkedBlockingDeque(2);
1226 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
1227 Thread t = newStartedThread(new CheckedRunnable() {
1228 public void realRun() throws InterruptedException {
1229 q.putLast(new Object());
1230 q.putLast(new Object());
1231 long startTime = System.nanoTime();
1232 assertFalse(q.offerLast(new Object(), timeoutMillis(), MILLISECONDS));
1233 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
1234 pleaseInterrupt.countDown();
1235 try {
1236 q.offerLast(new Object(), 2 * LONG_DELAY_MS, MILLISECONDS);
1237 shouldThrow();
1238 } catch (InterruptedException success) {}
1239 }});
1240
1241 await(pleaseInterrupt);
1242 assertThreadStaysAlive(t);
1243 t.interrupt();
1244 awaitTermination(t);
1245 }
1246
1247 /**
1248 * takeLast retrieves elements in FIFO order
1249 */
1250 public void testTakeLast() throws InterruptedException {
1251 LinkedBlockingDeque q = populatedDeque(SIZE);
1252 for (int i = 0; i < SIZE; ++i) {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001253 assertEquals(SIZE - i - 1, q.takeLast());
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001254 }
1255 }
1256
1257 /**
1258 * takeLast removes existing elements until empty, then blocks interruptibly
1259 */
1260 public void testBlockingTakeLast() throws InterruptedException {
1261 final LinkedBlockingDeque q = populatedDeque(SIZE);
1262 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
1263 Thread t = newStartedThread(new CheckedRunnable() {
1264 public void realRun() throws InterruptedException {
1265 for (int i = 0; i < SIZE; ++i) {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001266 assertEquals(SIZE - i - 1, q.takeLast());
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001267 }
1268
1269 Thread.currentThread().interrupt();
1270 try {
1271 q.takeLast();
1272 shouldThrow();
1273 } catch (InterruptedException success) {}
1274 assertFalse(Thread.interrupted());
1275
1276 pleaseInterrupt.countDown();
1277 try {
1278 q.takeLast();
1279 shouldThrow();
1280 } catch (InterruptedException success) {}
1281 assertFalse(Thread.interrupted());
1282 }});
1283
1284 await(pleaseInterrupt);
1285 assertThreadStaysAlive(t);
1286 t.interrupt();
1287 awaitTermination(t);
1288 }
1289
1290 /**
1291 * timed pollLast with zero timeout succeeds when non-empty, else times out
1292 */
1293 public void testTimedPollLast0() throws InterruptedException {
1294 LinkedBlockingDeque q = populatedDeque(SIZE);
1295 for (int i = 0; i < SIZE; ++i) {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001296 assertEquals(SIZE - i - 1, q.pollLast(0, MILLISECONDS));
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001297 }
1298 assertNull(q.pollLast(0, MILLISECONDS));
1299 }
1300
1301 /**
1302 * timed pollLast with nonzero timeout succeeds when non-empty, else times out
1303 */
1304 public void testTimedPollLast() throws InterruptedException {
1305 LinkedBlockingDeque q = populatedDeque(SIZE);
1306 for (int i = 0; i < SIZE; ++i) {
1307 long startTime = System.nanoTime();
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001308 assertEquals(SIZE - i - 1, q.pollLast(LONG_DELAY_MS, MILLISECONDS));
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001309 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
1310 }
1311 long startTime = System.nanoTime();
1312 assertNull(q.pollLast(timeoutMillis(), MILLISECONDS));
1313 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
1314 checkEmpty(q);
1315 }
1316
1317 /**
1318 * Interrupted timed pollLast throws InterruptedException instead of
1319 * returning timeout status
1320 */
1321 public void testInterruptedTimedPollLast() throws InterruptedException {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001322 final LinkedBlockingDeque q = populatedDeque(SIZE);
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001323 final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
1324 Thread t = newStartedThread(new CheckedRunnable() {
1325 public void realRun() throws InterruptedException {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001326 long startTime = System.nanoTime();
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001327 for (int i = 0; i < SIZE; ++i) {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001328 assertEquals(SIZE - i - 1,
1329 q.pollLast(LONG_DELAY_MS, MILLISECONDS));
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001330 }
1331
1332 Thread.currentThread().interrupt();
1333 try {
1334 q.pollLast(LONG_DELAY_MS, MILLISECONDS);
1335 shouldThrow();
1336 } catch (InterruptedException success) {}
1337 assertFalse(Thread.interrupted());
1338
1339 pleaseInterrupt.countDown();
1340 try {
1341 q.pollLast(LONG_DELAY_MS, MILLISECONDS);
1342 shouldThrow();
1343 } catch (InterruptedException success) {}
1344 assertFalse(Thread.interrupted());
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001345
1346 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001347 }});
1348
1349 await(pleaseInterrupt);
1350 assertThreadStaysAlive(t);
1351 t.interrupt();
1352 awaitTermination(t);
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001353 checkEmpty(q);
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001354 }
1355
1356 /**
1357 * timed poll before a delayed offerLast fails; after offerLast succeeds;
1358 * on interruption throws
1359 */
1360 public void testTimedPollWithOfferLast() throws InterruptedException {
1361 final LinkedBlockingDeque q = new LinkedBlockingDeque(2);
1362 final CheckedBarrier barrier = new CheckedBarrier(2);
1363 Thread t = newStartedThread(new CheckedRunnable() {
1364 public void realRun() throws InterruptedException {
1365 long startTime = System.nanoTime();
1366 assertNull(q.poll(timeoutMillis(), MILLISECONDS));
1367 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
1368
1369 barrier.await();
1370
1371 assertSame(zero, q.poll(LONG_DELAY_MS, MILLISECONDS));
1372
1373 Thread.currentThread().interrupt();
1374 try {
1375 q.poll(LONG_DELAY_MS, MILLISECONDS);
1376 shouldThrow();
1377 } catch (InterruptedException success) {}
1378 assertFalse(Thread.interrupted());
1379
1380 barrier.await();
1381 try {
1382 q.poll(LONG_DELAY_MS, MILLISECONDS);
1383 shouldThrow();
1384 } catch (InterruptedException success) {}
1385 assertFalse(Thread.interrupted());
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001386
1387 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001388 }});
1389
1390 barrier.await();
1391 long startTime = System.nanoTime();
1392 assertTrue(q.offerLast(zero, LONG_DELAY_MS, MILLISECONDS));
1393 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
1394
1395 barrier.await();
1396 assertThreadStaysAlive(t);
1397 t.interrupt();
1398 awaitTermination(t);
1399 }
1400
1401 /**
1402 * element returns next element, or throws NSEE if empty
1403 */
1404 public void testElement() {
1405 LinkedBlockingDeque q = populatedDeque(SIZE);
1406 for (int i = 0; i < SIZE; ++i) {
1407 assertEquals(i, q.element());
1408 q.poll();
1409 }
1410 try {
1411 q.element();
1412 shouldThrow();
1413 } catch (NoSuchElementException success) {}
1414 }
1415
1416 /**
1417 * contains(x) reports true when elements added but not yet removed
1418 */
1419 public void testContains() {
1420 LinkedBlockingDeque q = populatedDeque(SIZE);
1421 for (int i = 0; i < SIZE; ++i) {
1422 assertTrue(q.contains(new Integer(i)));
1423 q.poll();
1424 assertFalse(q.contains(new Integer(i)));
1425 }
1426 }
1427
1428 /**
1429 * clear removes all elements
1430 */
1431 public void testClear() {
1432 LinkedBlockingDeque q = populatedDeque(SIZE);
1433 q.clear();
1434 assertTrue(q.isEmpty());
1435 assertEquals(0, q.size());
1436 assertEquals(SIZE, q.remainingCapacity());
1437 q.add(one);
1438 assertFalse(q.isEmpty());
1439 assertTrue(q.contains(one));
1440 q.clear();
1441 assertTrue(q.isEmpty());
1442 }
1443
1444 /**
1445 * containsAll(c) is true when c contains a subset of elements
1446 */
1447 public void testContainsAll() {
1448 LinkedBlockingDeque q = populatedDeque(SIZE);
1449 LinkedBlockingDeque p = new LinkedBlockingDeque(SIZE);
1450 for (int i = 0; i < SIZE; ++i) {
1451 assertTrue(q.containsAll(p));
1452 assertFalse(p.containsAll(q));
1453 p.add(new Integer(i));
1454 }
1455 assertTrue(p.containsAll(q));
1456 }
1457
1458 /**
1459 * retainAll(c) retains only those elements of c and reports true if changed
1460 */
1461 public void testRetainAll() {
1462 LinkedBlockingDeque q = populatedDeque(SIZE);
1463 LinkedBlockingDeque p = populatedDeque(SIZE);
1464 for (int i = 0; i < SIZE; ++i) {
1465 boolean changed = q.retainAll(p);
1466 if (i == 0)
1467 assertFalse(changed);
1468 else
1469 assertTrue(changed);
1470
1471 assertTrue(q.containsAll(p));
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001472 assertEquals(SIZE - i, q.size());
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001473 p.remove();
1474 }
1475 }
1476
1477 /**
1478 * removeAll(c) removes only those elements of c and reports true if changed
1479 */
1480 public void testRemoveAll() {
1481 for (int i = 1; i < SIZE; ++i) {
1482 LinkedBlockingDeque q = populatedDeque(SIZE);
1483 LinkedBlockingDeque p = populatedDeque(i);
1484 assertTrue(q.removeAll(p));
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001485 assertEquals(SIZE - i, q.size());
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001486 for (int j = 0; j < i; ++j) {
Narayan Kamath8e9a0e92015-04-28 11:40:00 +01001487 Integer x = (Integer)(p.remove());
1488 assertFalse(q.contains(x));
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001489 }
1490 }
1491 }
1492
1493 /**
1494 * toArray contains all elements in FIFO order
1495 */
1496 public void testToArray() throws InterruptedException {
1497 LinkedBlockingDeque q = populatedDeque(SIZE);
1498 Object[] o = q.toArray();
1499 for (int i = 0; i < o.length; i++)
1500 assertSame(o[i], q.poll());
1501 }
1502
1503 /**
1504 * toArray(a) contains all elements in FIFO order
1505 */
1506 public void testToArray2() {
1507 LinkedBlockingDeque<Integer> q = populatedDeque(SIZE);
1508 Integer[] ints = new Integer[SIZE];
1509 Integer[] array = q.toArray(ints);
1510 assertSame(ints, array);
1511 for (int i = 0; i < ints.length; i++)
1512 assertSame(ints[i], q.remove());
1513 }
1514
1515 /**
1516 * toArray(incompatible array type) throws ArrayStoreException
1517 */
1518 public void testToArray1_BadArg() {
1519 LinkedBlockingDeque q = populatedDeque(SIZE);
1520 try {
1521 q.toArray(new String[10]);
1522 shouldThrow();
1523 } catch (ArrayStoreException success) {}
1524 }
1525
1526 /**
1527 * iterator iterates through all elements
1528 */
1529 public void testIterator() throws InterruptedException {
1530 LinkedBlockingDeque q = populatedDeque(SIZE);
1531 Iterator it = q.iterator();
Narayan Kamath8e9a0e92015-04-28 11:40:00 +01001532 int i;
1533 for (i = 0; it.hasNext(); i++)
1534 assertTrue(q.contains(it.next()));
1535 assertEquals(i, SIZE);
1536 assertIteratorExhausted(it);
1537
1538 it = q.iterator();
1539 for (i = 0; it.hasNext(); i++)
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001540 assertEquals(it.next(), q.take());
Narayan Kamath8e9a0e92015-04-28 11:40:00 +01001541 assertEquals(i, SIZE);
1542 assertIteratorExhausted(it);
1543 }
1544
1545 /**
1546 * iterator of empty collection has no elements
1547 */
1548 public void testEmptyIterator() {
1549 Deque c = new LinkedBlockingDeque();
1550 assertIteratorExhausted(c.iterator());
1551 assertIteratorExhausted(c.descendingIterator());
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001552 }
1553
1554 /**
1555 * iterator.remove removes current element
1556 */
1557 public void testIteratorRemove() {
1558 final LinkedBlockingDeque q = new LinkedBlockingDeque(3);
1559 q.add(two);
1560 q.add(one);
1561 q.add(three);
1562
1563 Iterator it = q.iterator();
1564 it.next();
1565 it.remove();
1566
1567 it = q.iterator();
1568 assertSame(it.next(), one);
1569 assertSame(it.next(), three);
1570 assertFalse(it.hasNext());
1571 }
1572
1573 /**
1574 * iterator ordering is FIFO
1575 */
1576 public void testIteratorOrdering() {
1577 final LinkedBlockingDeque q = new LinkedBlockingDeque(3);
1578 q.add(one);
1579 q.add(two);
1580 q.add(three);
1581 assertEquals(0, q.remainingCapacity());
1582 int k = 0;
1583 for (Iterator it = q.iterator(); it.hasNext();) {
1584 assertEquals(++k, it.next());
1585 }
1586 assertEquals(3, k);
1587 }
1588
1589 /**
1590 * Modifications do not cause iterators to fail
1591 */
1592 public void testWeaklyConsistentIteration() {
1593 final LinkedBlockingDeque q = new LinkedBlockingDeque(3);
1594 q.add(one);
1595 q.add(two);
1596 q.add(three);
1597 for (Iterator it = q.iterator(); it.hasNext();) {
1598 q.remove();
1599 it.next();
1600 }
1601 assertEquals(0, q.size());
1602 }
1603
1604 /**
1605 * Descending iterator iterates through all elements
1606 */
1607 public void testDescendingIterator() {
1608 LinkedBlockingDeque q = populatedDeque(SIZE);
1609 int i = 0;
1610 Iterator it = q.descendingIterator();
1611 while (it.hasNext()) {
1612 assertTrue(q.contains(it.next()));
1613 ++i;
1614 }
1615 assertEquals(i, SIZE);
1616 assertFalse(it.hasNext());
1617 try {
1618 it.next();
1619 shouldThrow();
1620 } catch (NoSuchElementException success) {}
1621 }
1622
1623 /**
1624 * Descending iterator ordering is reverse FIFO
1625 */
1626 public void testDescendingIteratorOrdering() {
1627 final LinkedBlockingDeque q = new LinkedBlockingDeque();
1628 for (int iters = 0; iters < 100; ++iters) {
1629 q.add(new Integer(3));
1630 q.add(new Integer(2));
1631 q.add(new Integer(1));
1632 int k = 0;
1633 for (Iterator it = q.descendingIterator(); it.hasNext();) {
1634 assertEquals(++k, it.next());
1635 }
1636
1637 assertEquals(3, k);
1638 q.remove();
1639 q.remove();
1640 q.remove();
1641 }
1642 }
1643
1644 /**
1645 * descendingIterator.remove removes current element
1646 */
1647 public void testDescendingIteratorRemove() {
1648 final LinkedBlockingDeque q = new LinkedBlockingDeque();
1649 for (int iters = 0; iters < 100; ++iters) {
1650 q.add(new Integer(3));
1651 q.add(new Integer(2));
1652 q.add(new Integer(1));
1653 Iterator it = q.descendingIterator();
1654 assertEquals(it.next(), new Integer(1));
1655 it.remove();
1656 assertEquals(it.next(), new Integer(2));
1657 it = q.descendingIterator();
1658 assertEquals(it.next(), new Integer(2));
1659 assertEquals(it.next(), new Integer(3));
1660 it.remove();
1661 assertFalse(it.hasNext());
1662 q.remove();
1663 }
1664 }
1665
1666 /**
1667 * toString contains toStrings of elements
1668 */
1669 public void testToString() {
1670 LinkedBlockingDeque q = populatedDeque(SIZE);
1671 String s = q.toString();
1672 for (int i = 0; i < SIZE; ++i) {
1673 assertTrue(s.contains(String.valueOf(i)));
1674 }
1675 }
1676
1677 /**
1678 * offer transfers elements across Executor tasks
1679 */
1680 public void testOfferInExecutor() {
1681 final LinkedBlockingDeque q = new LinkedBlockingDeque(2);
1682 q.add(one);
1683 q.add(two);
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001684 final CheckedBarrier threadsStarted = new CheckedBarrier(2);
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001685 final ExecutorService executor = Executors.newFixedThreadPool(2);
1686 try (PoolCleaner cleaner = cleaner(executor)) {
1687 executor.execute(new CheckedRunnable() {
1688 public void realRun() throws InterruptedException {
1689 assertFalse(q.offer(three));
1690 threadsStarted.await();
1691 assertTrue(q.offer(three, LONG_DELAY_MS, MILLISECONDS));
1692 assertEquals(0, q.remainingCapacity());
1693 }});
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001694
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001695 executor.execute(new CheckedRunnable() {
1696 public void realRun() throws InterruptedException {
1697 threadsStarted.await();
1698 assertSame(one, q.take());
1699 }});
1700 }
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001701 }
1702
1703 /**
1704 * timed poll retrieves elements across Executor threads
1705 */
1706 public void testPollInExecutor() {
1707 final LinkedBlockingDeque q = new LinkedBlockingDeque(2);
1708 final CheckedBarrier threadsStarted = new CheckedBarrier(2);
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001709 final ExecutorService executor = Executors.newFixedThreadPool(2);
1710 try (PoolCleaner cleaner = cleaner(executor)) {
1711 executor.execute(new CheckedRunnable() {
1712 public void realRun() throws InterruptedException {
1713 assertNull(q.poll());
1714 threadsStarted.await();
1715 assertSame(one, q.poll(LONG_DELAY_MS, MILLISECONDS));
1716 checkEmpty(q);
1717 }});
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001718
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001719 executor.execute(new CheckedRunnable() {
1720 public void realRun() throws InterruptedException {
1721 threadsStarted.await();
1722 q.put(one);
1723 }});
1724 }
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001725 }
1726
1727 /**
1728 * A deserialized serialized deque has same elements in same order
1729 */
1730 public void testSerialization() throws Exception {
1731 Queue x = populatedDeque(SIZE);
1732 Queue y = serialClone(x);
1733
1734 assertNotSame(y, x);
1735 assertEquals(x.size(), y.size());
1736 assertEquals(x.toString(), y.toString());
1737 assertTrue(Arrays.equals(x.toArray(), y.toArray()));
1738 while (!x.isEmpty()) {
1739 assertFalse(y.isEmpty());
1740 assertEquals(x.remove(), y.remove());
1741 }
1742 assertTrue(y.isEmpty());
1743 }
1744
1745 /**
1746 * drainTo(c) empties deque into another collection c
1747 */
1748 public void testDrainTo() {
1749 LinkedBlockingDeque q = populatedDeque(SIZE);
1750 ArrayList l = new ArrayList();
1751 q.drainTo(l);
1752 assertEquals(0, q.size());
1753 assertEquals(SIZE, l.size());
1754 for (int i = 0; i < SIZE; ++i)
1755 assertEquals(l.get(i), new Integer(i));
1756 q.add(zero);
1757 q.add(one);
1758 assertFalse(q.isEmpty());
1759 assertTrue(q.contains(zero));
1760 assertTrue(q.contains(one));
1761 l.clear();
1762 q.drainTo(l);
1763 assertEquals(0, q.size());
1764 assertEquals(2, l.size());
1765 for (int i = 0; i < 2; ++i)
1766 assertEquals(l.get(i), new Integer(i));
1767 }
1768
1769 /**
1770 * drainTo empties full deque, unblocking a waiting put.
1771 */
1772 public void testDrainToWithActivePut() throws InterruptedException {
1773 final LinkedBlockingDeque q = populatedDeque(SIZE);
1774 Thread t = new Thread(new CheckedRunnable() {
1775 public void realRun() throws InterruptedException {
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001776 q.put(new Integer(SIZE + 1));
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001777 }});
1778
1779 t.start();
1780 ArrayList l = new ArrayList();
1781 q.drainTo(l);
1782 assertTrue(l.size() >= SIZE);
1783 for (int i = 0; i < SIZE; ++i)
1784 assertEquals(l.get(i), new Integer(i));
1785 t.join();
1786 assertTrue(q.size() + l.size() >= SIZE);
1787 }
1788
1789 /**
1790 * drainTo(c, n) empties first min(n, size) elements of queue into c
1791 */
1792 public void testDrainToN() {
1793 LinkedBlockingDeque q = new LinkedBlockingDeque();
1794 for (int i = 0; i < SIZE + 2; ++i) {
1795 for (int j = 0; j < SIZE; j++)
1796 assertTrue(q.offer(new Integer(j)));
1797 ArrayList l = new ArrayList();
1798 q.drainTo(l, i);
1799 int k = (i < SIZE) ? i : SIZE;
1800 assertEquals(k, l.size());
Przemyslaw Szczepaniakb8b75112016-03-11 15:59:10 +00001801 assertEquals(SIZE - k, q.size());
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001802 for (int j = 0; j < k; ++j)
1803 assertEquals(l.get(j), new Integer(j));
Narayan Kamath8e9a0e92015-04-28 11:40:00 +01001804 do {} while (q.poll() != null);
1805 }
1806 }
1807
1808 /**
1809 * remove(null), contains(null) always return false
1810 */
1811 public void testNeverContainsNull() {
1812 Deque<?>[] qs = {
1813 new LinkedBlockingDeque<Object>(),
1814 populatedDeque(2),
1815 };
1816
1817 for (Deque<?> q : qs) {
1818 assertFalse(q.contains(null));
1819 assertFalse(q.remove(null));
1820 assertFalse(q.removeFirstOccurrence(null));
1821 assertFalse(q.removeLastOccurrence(null));
Calin Juravle8f0d92b2013-08-01 17:26:00 +01001822 }
1823 }
1824
1825}