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