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