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