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