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