1 /* 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 7 package jsr166; 8 9 import static java.util.concurrent.TimeUnit.MILLISECONDS; 10 11 import java.util.ArrayList; 12 import java.util.Arrays; 13 import java.util.Collection; 14 import java.util.Deque; 15 import java.util.Iterator; 16 import java.util.NoSuchElementException; 17 import java.util.Queue; 18 import java.util.concurrent.BlockingDeque; 19 import java.util.concurrent.BlockingQueue; 20 import java.util.concurrent.CountDownLatch; 21 import java.util.concurrent.Executors; 22 import java.util.concurrent.ExecutorService; 23 import java.util.concurrent.LinkedBlockingDeque; 24 25 import junit.framework.Test; 26 27 public class LinkedBlockingDequeTest extends JSR166TestCase { 28 29 public static class Unbounded extends BlockingQueueTest { emptyCollection()30 protected BlockingQueue emptyCollection() { 31 return new LinkedBlockingDeque(); 32 } 33 } 34 35 public static class Bounded extends BlockingQueueTest { emptyCollection()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. 43 // 44 // public static void main(String[] args) { 45 // main(suite(), args); 46 // } 47 // public static Test suite() { 48 // return newTestSuite(LinkedBlockingDequeTest.class, 49 // new Unbounded().testSuite(), 50 // new Bounded().testSuite()); 51 // } 52 53 /** 54 * Returns a new deque of given size containing consecutive 55 * Integers 0 ... n. 56 */ populatedDeque(int n)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 */ testEmpty()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 */ testSize()86 public void testSize() { 87 LinkedBlockingDeque q = populatedDeque(SIZE); 88 for (int i = 0; i < SIZE; ++i) { 89 assertEquals(SIZE - i, q.size()); 90 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 */ testOfferFirstNull()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 */ testOfferLastNull()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 */ testOfferFirst()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 */ testOfferLast()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 */ testPollFirst()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 */ testPollLast()152 public void testPollLast() { 153 LinkedBlockingDeque q = populatedDeque(SIZE); 154 for (int i = SIZE - 1; i >= 0; --i) { 155 assertEquals(i, q.pollLast()); 156 } 157 assertNull(q.pollLast()); 158 } 159 160 /** 161 * peekFirst returns next element, or null if empty 162 */ testPeekFirst()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 */ testPeek()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 */ testPeekLast()191 public void testPeekLast() { 192 LinkedBlockingDeque q = populatedDeque(SIZE); 193 for (int i = SIZE - 1; i >= 0; --i) { 194 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 */ testFirstElement()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 */ testLastElement()221 public void testLastElement() { 222 LinkedBlockingDeque q = populatedDeque(SIZE); 223 for (int i = SIZE - 1; i >= 0; --i) { 224 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 */ testRemoveFirst()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 */ testRemoveLast()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 */ testRemove()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 */ testRemoveFirstOccurrence()281 public void testRemoveFirstOccurrence() { 282 LinkedBlockingDeque q = populatedDeque(SIZE); 283 for (int i = 1; i < SIZE; i += 2) { 284 assertTrue(q.removeFirstOccurrence(new Integer(i))); 285 } 286 for (int i = 0; i < SIZE; i += 2) { 287 assertTrue(q.removeFirstOccurrence(new Integer(i))); 288 assertFalse(q.removeFirstOccurrence(new Integer(i + 1))); 289 } 290 assertTrue(q.isEmpty()); 291 } 292 293 /** 294 * removeLastOccurrence(x) removes x and returns true if present 295 */ testRemoveLastOccurrence()296 public void testRemoveLastOccurrence() { 297 LinkedBlockingDeque q = populatedDeque(SIZE); 298 for (int i = 1; i < SIZE; i += 2) { 299 assertTrue(q.removeLastOccurrence(new Integer(i))); 300 } 301 for (int i = 0; i < SIZE; i += 2) { 302 assertTrue(q.removeLastOccurrence(new Integer(i))); 303 assertFalse(q.removeLastOccurrence(new Integer(i + 1))); 304 } 305 assertTrue(q.isEmpty()); 306 } 307 308 /** 309 * peekFirst returns element inserted with addFirst 310 */ testAddFirst()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 */ testAddLast()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 */ testConstructor1()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 */ testConstructor2()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 */ testConstructor3()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 */ testConstructor4()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 */ testConstructor5()372 public void testConstructor5() { 373 Integer[] ints = new Integer[SIZE]; 374 for (int i = 0; i < SIZE - 1; ++i) 375 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 */ testConstructor6()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 */ testEmptyFull()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 */ testRemainingCapacity()413 public void testRemainingCapacity() { 414 BlockingQueue q = populatedDeque(SIZE); 415 for (int i = 0; i < SIZE; ++i) { 416 assertEquals(i, q.remainingCapacity()); 417 assertEquals(SIZE, q.size() + q.remainingCapacity()); 418 assertEquals(i, q.remove()); 419 } 420 for (int i = 0; i < SIZE; ++i) { 421 assertEquals(SIZE - i, q.remainingCapacity()); 422 assertEquals(SIZE, q.size() + q.remainingCapacity()); 423 assertTrue(q.add(i)); 424 } 425 } 426 427 /** 428 * push(null) throws NPE 429 */ testPushNull()430 public void testPushNull() { 431 LinkedBlockingDeque q = new LinkedBlockingDeque(1); 432 try { 433 q.push(null); 434 shouldThrow(); 435 } catch (NullPointerException success) {} 436 } 437 438 /** 439 * push succeeds if not full; throws ISE if full 440 */ testPush()441 public void testPush() { 442 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()); 449 try { 450 q.push(new Integer(SIZE)); 451 shouldThrow(); 452 } catch (IllegalStateException success) {} 453 } 454 455 /** 456 * peekFirst returns element inserted with push 457 */ testPushWithPeek()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 */ testPop()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 */ testOffer()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 */ testAdd()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 */ testAddAllSelf()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 */ testAddAll3()517 public void testAddAll3() { 518 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE); 519 Integer[] ints = new Integer[SIZE]; 520 for (int i = 0; i < SIZE - 1; ++i) 521 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 */ testAddAll4()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 */ testAddAll5()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 */ testPut()562 public void testPut() throws InterruptedException { 563 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE); 564 for (int i = 0; i < SIZE; ++i) { 565 Integer x = new Integer(i); 566 q.put(x); 567 assertTrue(q.contains(x)); 568 } 569 assertEquals(0, q.remainingCapacity()); 570 } 571 572 /** 573 * put blocks interruptibly if full 574 */ testBlockingPut()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 */ testPutWithTake()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 */ testTimedOffer()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 */ testTake()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 */ testBlockingTake()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 */ testPoll()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 */ testTimedPoll0()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 */ testTimedPoll()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 */ testInterruptedTimedPoll()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 { 758 long startTime = System.nanoTime(); 759 for (int i = 0; i < SIZE; ++i) { 760 assertEquals(i, (int) q.poll(LONG_DELAY_MS, MILLISECONDS)); 761 } 762 aboutToWait.countDown(); 763 try { 764 q.poll(LONG_DELAY_MS, MILLISECONDS); 765 shouldThrow(); 766 } catch (InterruptedException success) { 767 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS); 768 } 769 }}); 770 771 aboutToWait.await(); 772 waitForThreadToEnterWaitState(t, LONG_DELAY_MS); 773 t.interrupt(); 774 awaitTermination(t); 775 checkEmpty(q); 776 } 777 778 /** 779 * putFirst(null) throws NPE 780 */ testPutFirstNull()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 */ testPutFirst()792 public void testPutFirst() throws InterruptedException { 793 LinkedBlockingDeque q = new LinkedBlockingDeque(SIZE); 794 for (int i = 0; i < SIZE; ++i) { 795 Integer x = new Integer(i); 796 q.putFirst(x); 797 assertTrue(q.contains(x)); 798 } 799 assertEquals(0, q.remainingCapacity()); 800 } 801 802 /** 803 * putFirst blocks interruptibly if full 804 */ testBlockingPutFirst()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 */ testPutFirstWithTake()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 */ testTimedOfferFirst()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 */ testTakeFirst()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 */ testTakeFirstFromEmptyBlocksInterruptibly()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 */ testTakeFirstFromEmptyAfterInterrupt()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 */ testTakeLastFromEmptyBlocksInterruptibly()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 */ testTakeLastFromEmptyAfterInterrupt()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 */ testBlockingTakeFirst()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 */ testTimedPollFirst0()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 */ testTimedPollFirst()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 */ testInterruptedTimedPollFirst()1054 public void testInterruptedTimedPollFirst() throws InterruptedException { 1055 final LinkedBlockingDeque q = populatedDeque(SIZE); 1056 final CountDownLatch pleaseInterrupt = new CountDownLatch(1); 1057 Thread t = newStartedThread(new CheckedRunnable() { 1058 public void realRun() throws InterruptedException { 1059 long startTime = System.nanoTime(); 1060 for (int i = 0; i < SIZE; ++i) { 1061 assertEquals(i, q.pollFirst(LONG_DELAY_MS, MILLISECONDS)); 1062 } 1063 1064 Thread.currentThread().interrupt(); 1065 try { 1066 q.pollFirst(LONG_DELAY_MS, MILLISECONDS); 1067 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()); 1077 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS); 1078 }}); 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 */ testTimedPollFirstWithOfferFirst()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) { 1144 Integer x = new Integer(i); 1145 q.putLast(x); 1146 assertTrue(q.contains(x)); 1147 } 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) { 1253 assertEquals(SIZE - i - 1, q.takeLast()); 1254 } 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) { 1266 assertEquals(SIZE - i - 1, q.takeLast()); 1267 } 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) { 1296 assertEquals(SIZE - i - 1, q.pollLast(0, MILLISECONDS)); 1297 } 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(); 1308 assertEquals(SIZE - i - 1, q.pollLast(LONG_DELAY_MS, MILLISECONDS)); 1309 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 { 1322 final LinkedBlockingDeque q = populatedDeque(SIZE); 1323 final CountDownLatch pleaseInterrupt = new CountDownLatch(1); 1324 Thread t = newStartedThread(new CheckedRunnable() { 1325 public void realRun() throws InterruptedException { 1326 long startTime = System.nanoTime(); 1327 for (int i = 0; i < SIZE; ++i) { 1328 assertEquals(SIZE - i - 1, 1329 q.pollLast(LONG_DELAY_MS, MILLISECONDS)); 1330 } 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()); 1345 1346 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS); 1347 }}); 1348 1349 await(pleaseInterrupt); 1350 assertThreadStaysAlive(t); 1351 t.interrupt(); 1352 awaitTermination(t); 1353 checkEmpty(q); 1354 } 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()); 1386 1387 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS); 1388 }}); 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)); 1472 assertEquals(SIZE - i, q.size()); 1473 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)); 1485 assertEquals(SIZE - i, q.size()); 1486 for (int j = 0; j < i; ++j) { 1487 Integer x = (Integer)(p.remove()); 1488 assertFalse(q.contains(x)); 1489 } 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(); 1532 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++) 1540 assertEquals(it.next(), q.take()); 1541 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()); 1552 } 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); 1684 final CheckedBarrier threadsStarted = new CheckedBarrier(2); 1685 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 }}); 1694 1695 executor.execute(new CheckedRunnable() { 1696 public void realRun() throws InterruptedException { 1697 threadsStarted.await(); 1698 assertSame(one, q.take()); 1699 }}); 1700 } 1701 } 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); 1709 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 }}); 1718 1719 executor.execute(new CheckedRunnable() { 1720 public void realRun() throws InterruptedException { 1721 threadsStarted.await(); 1722 q.put(one); 1723 }}); 1724 } 1725 } 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 { 1776 q.put(new Integer(SIZE + 1)); 1777 }}); 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()); 1801 assertEquals(SIZE - k, q.size()); 1802 for (int j = 0; j < k; ++j) 1803 assertEquals(l.get(j), new Integer(j)); 1804 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)); 1822 } 1823 } 1824 1825 } 1826