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  * Other contributors include Andrew Wright, Jeffrey Hayes,
  33  * Pat Fisher, Mike Judd.
  34  */
  35 
  36 import static java.util.concurrent.TimeUnit.MILLISECONDS;
  37 
  38 import java.util.ArrayList;
  39 import java.util.Arrays;
  40 import java.util.Collection;
  41 import java.util.Iterator;
  42 import java.util.NoSuchElementException;
  43 import java.util.Queue;
  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.LinkedBlockingQueue;
  49 
  50 import junit.framework.Test;
  51 
  52 public class LinkedBlockingQueueTest extends JSR166TestCase {
  53 
  54     public static class Unbounded extends BlockingQueueTest {
  55         protected BlockingQueue emptyCollection() {
  56             return new LinkedBlockingQueue();
  57         }
  58     }
  59 
  60     public static class Bounded extends BlockingQueueTest {
  61         protected BlockingQueue emptyCollection() {
  62             return new LinkedBlockingQueue(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 LinkedBlockingQueue.class; }
  73             public Collection emptyCollection() { return new LinkedBlockingQueue(); }
  74             public Object makeElement(int i) { return i; }
  75             public boolean isConcurrent() { return true; }
  76             public boolean permitsNulls() { return false; }
  77         }
  78         return newTestSuite(LinkedBlockingQueueTest.class,
  79                             new Unbounded().testSuite(),
  80                             new Bounded().testSuite(),
  81                             CollectionTest.testSuite(new Implementation()));
  82     }
  83 
  84     /**
  85      * Returns a new queue of given size containing consecutive
  86      * Integers 0 ... n - 1.
  87      */
  88     private static LinkedBlockingQueue<Integer> populatedQueue(int n) {
  89         LinkedBlockingQueue<Integer> q = new LinkedBlockingQueue<>(n);
  90         assertTrue(q.isEmpty());
  91         for (int i = 0; i < n; i++)
  92             assertTrue(q.offer(new Integer(i)));
  93         assertFalse(q.isEmpty());
  94         assertEquals(0, q.remainingCapacity());
  95         assertEquals(n, q.size());
  96         assertEquals((Integer) 0, q.peek());
  97         return q;
  98     }
  99 
 100     /**
 101      * A new queue has the indicated capacity, or Integer.MAX_VALUE if
 102      * none given
 103      */
 104     public void testConstructor1() {
 105         assertEquals(SIZE, new LinkedBlockingQueue(SIZE).remainingCapacity());
 106         assertEquals(Integer.MAX_VALUE, new LinkedBlockingQueue().remainingCapacity());
 107     }
 108 
 109     /**
 110      * Constructor throws IllegalArgumentException if capacity argument nonpositive
 111      */
 112     public void testConstructor2() {
 113         try {
 114             new LinkedBlockingQueue(0);
 115             shouldThrow();
 116         } catch (IllegalArgumentException success) {}
 117     }
 118 
 119     /**
 120      * Initializing from null Collection throws NullPointerException
 121      */
 122     public void testConstructor3() {
 123         try {
 124             new LinkedBlockingQueue(null);
 125             shouldThrow();
 126         } catch (NullPointerException success) {}
 127     }
 128 
 129     /**
 130      * Initializing from Collection of null elements throws NullPointerException
 131      */
 132     public void testConstructor4() {
 133         Collection<Integer> elements = Arrays.asList(new Integer[SIZE]);
 134         try {
 135             new LinkedBlockingQueue(elements);
 136             shouldThrow();
 137         } catch (NullPointerException success) {}
 138     }
 139 
 140     /**
 141      * Initializing from Collection with some null elements throws
 142      * NullPointerException
 143      */
 144     public void testConstructor5() {
 145         Integer[] ints = new Integer[SIZE];
 146         for (int i = 0; i < SIZE - 1; ++i)
 147             ints[i] = new Integer(i);
 148         Collection<Integer> elements = Arrays.asList(ints);
 149         try {
 150             new LinkedBlockingQueue(elements);
 151             shouldThrow();
 152         } catch (NullPointerException success) {}
 153     }
 154 
 155     /**
 156      * Queue contains all elements of collection used to initialize
 157      */
 158     public void testConstructor6() {
 159         Integer[] ints = new Integer[SIZE];
 160         for (int i = 0; i < SIZE; ++i)
 161             ints[i] = new Integer(i);
 162         LinkedBlockingQueue q = new LinkedBlockingQueue(Arrays.asList(ints));
 163         for (int i = 0; i < SIZE; ++i)
 164             assertEquals(ints[i], q.poll());
 165     }
 166 
 167     /**
 168      * Queue transitions from empty to full when elements added
 169      */
 170     public void testEmptyFull() {
 171         LinkedBlockingQueue q = new LinkedBlockingQueue(2);
 172         assertTrue(q.isEmpty());
 173         assertEquals("should have room for 2", 2, q.remainingCapacity());
 174         q.add(one);
 175         assertFalse(q.isEmpty());
 176         q.add(two);
 177         assertFalse(q.isEmpty());
 178         assertEquals(0, q.remainingCapacity());
 179         assertFalse(q.offer(three));
 180     }
 181 
 182     /**
 183      * remainingCapacity decreases on add, increases on remove
 184      */
 185     public void testRemainingCapacity() {
 186         BlockingQueue q = populatedQueue(SIZE);
 187         for (int i = 0; i < SIZE; ++i) {
 188             assertEquals(i, q.remainingCapacity());
 189             assertEquals(SIZE, q.size() + q.remainingCapacity());
 190             assertEquals(i, q.remove());
 191         }
 192         for (int i = 0; i < SIZE; ++i) {
 193             assertEquals(SIZE - i, q.remainingCapacity());
 194             assertEquals(SIZE, q.size() + q.remainingCapacity());
 195             assertTrue(q.add(i));
 196         }
 197     }
 198 
 199     /**
 200      * Offer succeeds if not full; fails if full
 201      */
 202     public void testOffer() {
 203         LinkedBlockingQueue q = new LinkedBlockingQueue(1);
 204         assertTrue(q.offer(zero));
 205         assertFalse(q.offer(one));
 206     }
 207 
 208     /**
 209      * add succeeds if not full; throws IllegalStateException if full
 210      */
 211     public void testAdd() {
 212         LinkedBlockingQueue q = new LinkedBlockingQueue(SIZE);
 213         for (int i = 0; i < SIZE; ++i)
 214             assertTrue(q.add(new Integer(i)));
 215         assertEquals(0, q.remainingCapacity());
 216         try {
 217             q.add(new Integer(SIZE));
 218             shouldThrow();
 219         } catch (IllegalStateException success) {}
 220     }
 221 
 222     /**
 223      * addAll(this) throws IllegalArgumentException
 224      */
 225     public void testAddAllSelf() {
 226         LinkedBlockingQueue q = populatedQueue(SIZE);
 227         try {
 228             q.addAll(q);
 229             shouldThrow();
 230         } catch (IllegalArgumentException success) {}
 231     }
 232 
 233     /**
 234      * addAll of a collection with any null elements throws NPE after
 235      * possibly adding some elements
 236      */
 237     public void testAddAll3() {
 238         LinkedBlockingQueue q = new LinkedBlockingQueue(SIZE);
 239         Integer[] ints = new Integer[SIZE];
 240         for (int i = 0; i < SIZE - 1; ++i)
 241             ints[i] = new Integer(i);
 242         Collection<Integer> elements = Arrays.asList(ints);
 243         try {
 244             q.addAll(elements);
 245             shouldThrow();
 246         } catch (NullPointerException success) {}
 247     }
 248 
 249     /**
 250      * addAll throws IllegalStateException if not enough room
 251      */
 252     public void testAddAll4() {
 253         LinkedBlockingQueue q = new LinkedBlockingQueue(SIZE - 1);
 254         Integer[] ints = new Integer[SIZE];
 255         for (int i = 0; i < SIZE; ++i)
 256             ints[i] = new Integer(i);
 257         Collection<Integer> elements = Arrays.asList(ints);
 258         try {
 259             q.addAll(elements);
 260             shouldThrow();
 261         } catch (IllegalStateException success) {}
 262     }
 263 
 264     /**
 265      * Queue contains all elements, in traversal order, of successful addAll
 266      */
 267     public void testAddAll5() {
 268         Integer[] empty = new Integer[0];
 269         Integer[] ints = new Integer[SIZE];
 270         for (int i = 0; i < SIZE; ++i)
 271             ints[i] = new Integer(i);
 272         LinkedBlockingQueue q = new LinkedBlockingQueue(SIZE);
 273         assertFalse(q.addAll(Arrays.asList(empty)));
 274         assertTrue(q.addAll(Arrays.asList(ints)));
 275         for (int i = 0; i < SIZE; ++i)
 276             assertEquals(ints[i], q.poll());
 277     }
 278 
 279     /**
 280      * all elements successfully put are contained
 281      */
 282     public void testPut() throws InterruptedException {
 283         LinkedBlockingQueue q = new LinkedBlockingQueue(SIZE);
 284         for (int i = 0; i < SIZE; ++i) {
 285             Integer x = new Integer(i);
 286             q.put(x);
 287             assertTrue(q.contains(x));
 288         }
 289         assertEquals(0, q.remainingCapacity());
 290     }
 291 
 292     /**
 293      * put blocks interruptibly if full
 294      */
 295     public void testBlockingPut() throws InterruptedException {
 296         final LinkedBlockingQueue q = new LinkedBlockingQueue(SIZE);
 297         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
 298         Thread t = newStartedThread(new CheckedRunnable() {
 299             public void realRun() throws InterruptedException {
 300                 for (int i = 0; i < SIZE; ++i)
 301                     q.put(i);
 302                 assertEquals(SIZE, q.size());
 303                 assertEquals(0, q.remainingCapacity());
 304 
 305                 Thread.currentThread().interrupt();
 306                 try {
 307                     q.put(99);
 308                     shouldThrow();
 309                 } catch (InterruptedException success) {}
 310                 assertFalse(Thread.interrupted());
 311 
 312                 pleaseInterrupt.countDown();
 313                 try {
 314                     q.put(99);
 315                     shouldThrow();
 316                 } catch (InterruptedException success) {}
 317                 assertFalse(Thread.interrupted());
 318             }});
 319 
 320         await(pleaseInterrupt);
 321         if (randomBoolean()) assertThreadBlocks(t, Thread.State.WAITING);
 322         t.interrupt();
 323         awaitTermination(t);
 324         assertEquals(SIZE, q.size());
 325         assertEquals(0, q.remainingCapacity());
 326     }
 327 
 328     /**
 329      * put blocks interruptibly waiting for take when full
 330      */
 331     public void testPutWithTake() throws InterruptedException {
 332         final int capacity = 2;
 333         final LinkedBlockingQueue q = new LinkedBlockingQueue(2);
 334         final CountDownLatch pleaseTake = new CountDownLatch(1);
 335         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
 336         Thread t = newStartedThread(new CheckedRunnable() {
 337             public void realRun() throws InterruptedException {
 338                 for (int i = 0; i < capacity; i++)
 339                     q.put(i);
 340                 pleaseTake.countDown();
 341                 q.put(86);
 342 
 343                 Thread.currentThread().interrupt();
 344                 try {
 345                     q.put(99);
 346                     shouldThrow();
 347                 } catch (InterruptedException success) {}
 348                 assertFalse(Thread.interrupted());
 349 
 350                 pleaseInterrupt.countDown();
 351                 try {
 352                     q.put(99);
 353                     shouldThrow();
 354                 } catch (InterruptedException success) {}
 355                 assertFalse(Thread.interrupted());
 356             }});
 357 
 358         await(pleaseTake);
 359         assertEquals(0, q.remainingCapacity());
 360         assertEquals(0, q.take());
 361 
 362         await(pleaseInterrupt);
 363         if (randomBoolean()) assertThreadBlocks(t, Thread.State.WAITING);
 364         t.interrupt();
 365         awaitTermination(t);
 366         assertEquals(0, q.remainingCapacity());
 367     }
 368 
 369     /**
 370      * timed offer times out if full and elements not taken
 371      */
 372     public void testTimedOffer() {
 373         final LinkedBlockingQueue q = new LinkedBlockingQueue(2);
 374         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
 375         Thread t = newStartedThread(new CheckedRunnable() {
 376             public void realRun() throws InterruptedException {
 377                 q.put(new Object());
 378                 q.put(new Object());
 379                 long startTime = System.nanoTime();
 380 
 381                 assertFalse(q.offer(new Object(), timeoutMillis(), MILLISECONDS));
 382                 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
 383 
 384                 Thread.currentThread().interrupt();
 385                 try {
 386                     q.offer(new Object(), randomTimeout(), randomTimeUnit());
 387                     shouldThrow();
 388                 } catch (InterruptedException success) {}
 389                 assertFalse(Thread.interrupted());
 390 
 391                 pleaseInterrupt.countDown();
 392                 try {
 393                     q.offer(new Object(), LONGER_DELAY_MS, MILLISECONDS);
 394                     shouldThrow();
 395                 } catch (InterruptedException success) {}
 396                 assertFalse(Thread.interrupted());
 397             }});
 398 
 399         await(pleaseInterrupt);
 400         if (randomBoolean()) assertThreadBlocks(t, Thread.State.TIMED_WAITING);
 401         t.interrupt();
 402         awaitTermination(t);
 403     }
 404 
 405     /**
 406      * take retrieves elements in FIFO order
 407      */
 408     public void testTake() throws InterruptedException {
 409         LinkedBlockingQueue q = populatedQueue(SIZE);
 410         for (int i = 0; i < SIZE; ++i) {
 411             assertEquals(i, q.take());
 412         }
 413     }
 414 
 415     /**
 416      * Take removes existing elements until empty, then blocks interruptibly
 417      */
 418     public void testBlockingTake() throws InterruptedException {
 419         final BlockingQueue q = populatedQueue(SIZE);
 420         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
 421         Thread t = newStartedThread(new CheckedRunnable() {
 422             public void realRun() throws InterruptedException {
 423                 for (int i = 0; i < SIZE; i++) assertEquals(i, q.take());
 424 
 425                 Thread.currentThread().interrupt();
 426                 try {
 427                     q.take();
 428                     shouldThrow();
 429                 } catch (InterruptedException success) {}
 430                 assertFalse(Thread.interrupted());
 431 
 432                 pleaseInterrupt.countDown();
 433                 try {
 434                     q.take();
 435                     shouldThrow();
 436                 } catch (InterruptedException success) {}
 437                 assertFalse(Thread.interrupted());
 438             }});
 439 
 440         await(pleaseInterrupt);
 441         if (randomBoolean()) assertThreadBlocks(t, Thread.State.WAITING);
 442         t.interrupt();
 443         awaitTermination(t);
 444     }
 445 
 446     /**
 447      * poll succeeds unless empty
 448      */
 449     public void testPoll() {
 450         LinkedBlockingQueue q = populatedQueue(SIZE);
 451         for (int i = 0; i < SIZE; ++i) {
 452             assertEquals(i, q.poll());
 453         }
 454         assertNull(q.poll());
 455     }
 456 
 457     /**
 458      * timed poll with zero timeout succeeds when non-empty, else times out
 459      */
 460     public void testTimedPoll0() throws InterruptedException {
 461         LinkedBlockingQueue q = populatedQueue(SIZE);
 462         for (int i = 0; i < SIZE; ++i) {
 463             assertEquals(i, q.poll(0, MILLISECONDS));
 464         }
 465         assertNull(q.poll(0, MILLISECONDS));
 466     }
 467 
 468     /**
 469      * timed poll with nonzero timeout succeeds when non-empty, else times out
 470      */
 471     public void testTimedPoll() throws InterruptedException {
 472         LinkedBlockingQueue<Integer> q = populatedQueue(SIZE);
 473         for (int i = 0; i < SIZE; ++i) {
 474             long startTime = System.nanoTime();
 475             assertEquals(i, (int) q.poll(LONG_DELAY_MS, MILLISECONDS));
 476             assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);
 477         }
 478         long startTime = System.nanoTime();
 479         assertNull(q.poll(timeoutMillis(), MILLISECONDS));
 480         assertTrue(millisElapsedSince(startTime) >= timeoutMillis());
 481         checkEmpty(q);
 482     }
 483 
 484     /**
 485      * Interrupted timed poll throws InterruptedException instead of
 486      * returning timeout status
 487      */
 488     public void testInterruptedTimedPoll() throws InterruptedException {
 489         final BlockingQueue<Integer> q = populatedQueue(SIZE);
 490         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);
 491         Thread t = newStartedThread(new CheckedRunnable() {
 492             public void realRun() throws InterruptedException {
 493                 for (int i = 0; i < SIZE; i++)
 494                     assertEquals(i, (int) q.poll(LONG_DELAY_MS, MILLISECONDS));
 495 
 496                 Thread.currentThread().interrupt();
 497                 try {
 498                     q.poll(randomTimeout(), randomTimeUnit());
 499                     shouldThrow();
 500                 } catch (InterruptedException success) {}
 501                 assertFalse(Thread.interrupted());
 502 
 503                 pleaseInterrupt.countDown();
 504                 try {
 505                     q.poll(LONGER_DELAY_MS, MILLISECONDS);
 506                     shouldThrow();
 507                 } catch (InterruptedException success) {}
 508                 assertFalse(Thread.interrupted());
 509             }});
 510 
 511         await(pleaseInterrupt);
 512         if (randomBoolean()) assertThreadBlocks(t, Thread.State.TIMED_WAITING);
 513         t.interrupt();
 514         awaitTermination(t);
 515         checkEmpty(q);
 516     }
 517 
 518     /**
 519      * peek returns next element, or null if empty
 520      */
 521     public void testPeek() {
 522         LinkedBlockingQueue q = populatedQueue(SIZE);
 523         for (int i = 0; i < SIZE; ++i) {
 524             assertEquals(i, q.peek());
 525             assertEquals(i, q.poll());
 526             assertTrue(q.peek() == null ||
 527                        !q.peek().equals(i));
 528         }
 529         assertNull(q.peek());
 530     }
 531 
 532     /**
 533      * element returns next element, or throws NSEE if empty
 534      */
 535     public void testElement() {
 536         LinkedBlockingQueue q = populatedQueue(SIZE);
 537         for (int i = 0; i < SIZE; ++i) {
 538             assertEquals(i, q.element());
 539             assertEquals(i, q.poll());
 540         }
 541         try {
 542             q.element();
 543             shouldThrow();
 544         } catch (NoSuchElementException success) {}
 545     }
 546 
 547     /**
 548      * remove removes next element, or throws NSEE if empty
 549      */
 550     public void testRemove() {
 551         LinkedBlockingQueue q = populatedQueue(SIZE);
 552         for (int i = 0; i < SIZE; ++i) {
 553             assertEquals(i, q.remove());
 554         }
 555         try {
 556             q.remove();
 557             shouldThrow();
 558         } catch (NoSuchElementException success) {}
 559     }
 560 
 561     /**
 562      * An add following remove(x) succeeds
 563      */
 564     public void testRemoveElementAndAdd() throws InterruptedException {
 565         LinkedBlockingQueue q = new LinkedBlockingQueue();
 566         assertTrue(q.add(new Integer(1)));
 567         assertTrue(q.add(new Integer(2)));
 568         assertTrue(q.remove(new Integer(1)));
 569         assertTrue(q.remove(new Integer(2)));
 570         assertTrue(q.add(new Integer(3)));
 571         assertNotNull(q.take());
 572     }
 573 
 574     /**
 575      * contains(x) reports true when elements added but not yet removed
 576      */
 577     public void testContains() {
 578         LinkedBlockingQueue q = populatedQueue(SIZE);
 579         for (int i = 0; i < SIZE; ++i) {
 580             assertTrue(q.contains(new Integer(i)));
 581             q.poll();
 582             assertFalse(q.contains(new Integer(i)));
 583         }
 584     }
 585 
 586     /**
 587      * clear removes all elements
 588      */
 589     public void testClear() {
 590         LinkedBlockingQueue q = populatedQueue(SIZE);
 591         q.clear();
 592         assertTrue(q.isEmpty());
 593         assertEquals(0, q.size());
 594         assertEquals(SIZE, q.remainingCapacity());
 595         q.add(one);
 596         assertFalse(q.isEmpty());
 597         assertTrue(q.contains(one));
 598         q.clear();
 599         assertTrue(q.isEmpty());
 600     }
 601 
 602     /**
 603      * containsAll(c) is true when c contains a subset of elements
 604      */
 605     public void testContainsAll() {
 606         LinkedBlockingQueue q = populatedQueue(SIZE);
 607         LinkedBlockingQueue p = new LinkedBlockingQueue(SIZE);
 608         for (int i = 0; i < SIZE; ++i) {
 609             assertTrue(q.containsAll(p));
 610             assertFalse(p.containsAll(q));
 611             p.add(new Integer(i));
 612         }
 613         assertTrue(p.containsAll(q));
 614     }
 615 
 616     /**
 617      * retainAll(c) retains only those elements of c and reports true if changed
 618      */
 619     public void testRetainAll() {
 620         LinkedBlockingQueue q = populatedQueue(SIZE);
 621         LinkedBlockingQueue p = populatedQueue(SIZE);
 622         for (int i = 0; i < SIZE; ++i) {
 623             boolean changed = q.retainAll(p);
 624             if (i == 0)
 625                 assertFalse(changed);
 626             else
 627                 assertTrue(changed);
 628 
 629             assertTrue(q.containsAll(p));
 630             assertEquals(SIZE - i, q.size());
 631             p.remove();
 632         }
 633     }
 634 
 635     /**
 636      * removeAll(c) removes only those elements of c and reports true if changed
 637      */
 638     public void testRemoveAll() {
 639         for (int i = 1; i < SIZE; ++i) {
 640             LinkedBlockingQueue q = populatedQueue(SIZE);
 641             LinkedBlockingQueue p = populatedQueue(i);
 642             assertTrue(q.removeAll(p));
 643             assertEquals(SIZE - i, q.size());
 644             for (int j = 0; j < i; ++j) {
 645                 Integer x = (Integer)(p.remove());
 646                 assertFalse(q.contains(x));
 647             }
 648         }
 649     }
 650 
 651     /**
 652      * toArray contains all elements in FIFO order
 653      */
 654     public void testToArray() {
 655         LinkedBlockingQueue q = populatedQueue(SIZE);
 656         Object[] a = q.toArray();
 657         assertSame(Object[].class, a.getClass());
 658         for (Object o : a)
 659             assertSame(o, q.poll());
 660         assertTrue(q.isEmpty());
 661     }
 662 
 663     /**
 664      * toArray(a) contains all elements in FIFO order
 665      */
 666     public void testToArray2() throws InterruptedException {
 667         LinkedBlockingQueue<Integer> q = populatedQueue(SIZE);
 668         Integer[] ints = new Integer[SIZE];
 669         Integer[] array = q.toArray(ints);
 670         assertSame(ints, array);
 671         for (Integer o : ints)
 672             assertSame(o, q.poll());
 673         assertTrue(q.isEmpty());
 674     }
 675 
 676     /**
 677      * toArray(incompatible array type) throws ArrayStoreException
 678      */
 679     public void testToArray1_BadArg() {
 680         LinkedBlockingQueue q = populatedQueue(SIZE);
 681         try {
 682             q.toArray(new String[10]);
 683             shouldThrow();
 684         } catch (ArrayStoreException success) {}
 685     }
 686 
 687     /**
 688      * iterator iterates through all elements
 689      */
 690     public void testIterator() throws InterruptedException {
 691         LinkedBlockingQueue q = populatedQueue(SIZE);
 692         Iterator it = q.iterator();
 693         int i;
 694         for (i = 0; it.hasNext(); i++)
 695             assertTrue(q.contains(it.next()));
 696         assertEquals(i, SIZE);
 697         assertIteratorExhausted(it);
 698 
 699         it = q.iterator();
 700         for (i = 0; it.hasNext(); i++)
 701             assertEquals(it.next(), q.take());
 702         assertEquals(i, SIZE);
 703         assertIteratorExhausted(it);
 704     }
 705 
 706     /**
 707      * iterator of empty collection has no elements
 708      */
 709     public void testEmptyIterator() {
 710         assertIteratorExhausted(new LinkedBlockingQueue().iterator());
 711     }
 712 
 713     /**
 714      * iterator.remove removes current element
 715      */
 716     public void testIteratorRemove() {
 717         final LinkedBlockingQueue q = new LinkedBlockingQueue(3);
 718         q.add(two);
 719         q.add(one);
 720         q.add(three);
 721 
 722         Iterator it = q.iterator();
 723         it.next();
 724         it.remove();
 725 
 726         it = q.iterator();
 727         assertSame(it.next(), one);
 728         assertSame(it.next(), three);
 729         assertFalse(it.hasNext());
 730     }
 731 
 732     /**
 733      * iterator ordering is FIFO
 734      */
 735     public void testIteratorOrdering() {
 736         final LinkedBlockingQueue q = new LinkedBlockingQueue(3);
 737         q.add(one);
 738         q.add(two);
 739         q.add(three);
 740         assertEquals(0, q.remainingCapacity());
 741         int k = 0;
 742         for (Iterator it = q.iterator(); it.hasNext();) {
 743             assertEquals(++k, it.next());
 744         }
 745         assertEquals(3, k);
 746     }
 747 
 748     /**
 749      * Modifications do not cause iterators to fail
 750      */
 751     public void testWeaklyConsistentIteration() {
 752         final LinkedBlockingQueue q = new LinkedBlockingQueue(3);
 753         q.add(one);
 754         q.add(two);
 755         q.add(three);
 756         for (Iterator it = q.iterator(); it.hasNext();) {
 757             q.remove();
 758             it.next();
 759         }
 760         assertEquals(0, q.size());
 761     }
 762 
 763     /**
 764      * toString contains toStrings of elements
 765      */
 766     public void testToString() {
 767         LinkedBlockingQueue q = populatedQueue(SIZE);
 768         String s = q.toString();
 769         for (int i = 0; i < SIZE; ++i) {
 770             assertTrue(s.contains(String.valueOf(i)));
 771         }
 772     }
 773 
 774     /**
 775      * offer transfers elements across Executor tasks
 776      */
 777     public void testOfferInExecutor() {
 778         final LinkedBlockingQueue q = new LinkedBlockingQueue(2);
 779         q.add(one);
 780         q.add(two);
 781         final CheckedBarrier threadsStarted = new CheckedBarrier(2);
 782         final ExecutorService executor = Executors.newFixedThreadPool(2);
 783         try (PoolCleaner cleaner = cleaner(executor)) {
 784             executor.execute(new CheckedRunnable() {
 785                 public void realRun() throws InterruptedException {
 786                     assertFalse(q.offer(three));
 787                     threadsStarted.await();
 788                     assertTrue(q.offer(three, LONG_DELAY_MS, MILLISECONDS));
 789                     assertEquals(0, q.remainingCapacity());
 790                 }});
 791 
 792             executor.execute(new CheckedRunnable() {
 793                 public void realRun() throws InterruptedException {
 794                     threadsStarted.await();
 795                     assertSame(one, q.take());
 796                 }});
 797         }
 798     }
 799 
 800     /**
 801      * timed poll retrieves elements across Executor threads
 802      */
 803     public void testPollInExecutor() {
 804         final LinkedBlockingQueue q = new LinkedBlockingQueue(2);
 805         final CheckedBarrier threadsStarted = new CheckedBarrier(2);
 806         final ExecutorService executor = Executors.newFixedThreadPool(2);
 807         try (PoolCleaner cleaner = cleaner(executor)) {
 808             executor.execute(new CheckedRunnable() {
 809                 public void realRun() throws InterruptedException {
 810                     assertNull(q.poll());
 811                     threadsStarted.await();
 812                     assertSame(one, q.poll(LONG_DELAY_MS, MILLISECONDS));
 813                     checkEmpty(q);
 814                 }});
 815 
 816             executor.execute(new CheckedRunnable() {
 817                 public void realRun() throws InterruptedException {
 818                     threadsStarted.await();
 819                     q.put(one);
 820                 }});
 821         }
 822     }
 823 
 824     /**
 825      * A deserialized/reserialized queue has same elements in same order
 826      */
 827     public void testSerialization() throws Exception {
 828         Queue x = populatedQueue(SIZE);
 829         Queue y = serialClone(x);
 830 
 831         assertNotSame(x, y);
 832         assertEquals(x.size(), y.size());
 833         assertEquals(x.toString(), y.toString());
 834         assertTrue(Arrays.equals(x.toArray(), y.toArray()));
 835         while (!x.isEmpty()) {
 836             assertFalse(y.isEmpty());
 837             assertEquals(x.remove(), y.remove());
 838         }
 839         assertTrue(y.isEmpty());
 840     }
 841 
 842     /**
 843      * drainTo(c) empties queue into another collection c
 844      */
 845     public void testDrainTo() {
 846         LinkedBlockingQueue q = populatedQueue(SIZE);
 847         ArrayList l = new ArrayList();
 848         q.drainTo(l);
 849         assertEquals(0, q.size());
 850         assertEquals(SIZE, l.size());
 851         for (int i = 0; i < SIZE; ++i)
 852             assertEquals(l.get(i), new Integer(i));
 853         q.add(zero);
 854         q.add(one);
 855         assertFalse(q.isEmpty());
 856         assertTrue(q.contains(zero));
 857         assertTrue(q.contains(one));
 858         l.clear();
 859         q.drainTo(l);
 860         assertEquals(0, q.size());
 861         assertEquals(2, l.size());
 862         for (int i = 0; i < 2; ++i)
 863             assertEquals(l.get(i), new Integer(i));
 864     }
 865 
 866     /**
 867      * drainTo empties full queue, unblocking a waiting put.
 868      */
 869     public void testDrainToWithActivePut() throws InterruptedException {
 870         final LinkedBlockingQueue q = populatedQueue(SIZE);
 871         Thread t = new Thread(new CheckedRunnable() {
 872             public void realRun() throws InterruptedException {
 873                 q.put(new Integer(SIZE + 1));
 874             }});
 875 
 876         t.start();
 877         ArrayList l = new ArrayList();
 878         q.drainTo(l);
 879         assertTrue(l.size() >= SIZE);
 880         for (int i = 0; i < SIZE; ++i)
 881             assertEquals(l.get(i), new Integer(i));
 882         t.join();
 883         assertTrue(q.size() + l.size() >= SIZE);
 884     }
 885 
 886     /**
 887      * drainTo(c, n) empties first min(n, size) elements of queue into c
 888      */
 889     public void testDrainToN() {
 890         LinkedBlockingQueue q = new LinkedBlockingQueue();
 891         for (int i = 0; i < SIZE + 2; ++i) {
 892             for (int j = 0; j < SIZE; j++)
 893                 assertTrue(q.offer(new Integer(j)));
 894             ArrayList l = new ArrayList();
 895             q.drainTo(l, i);
 896             int k = (i < SIZE) ? i : SIZE;
 897             assertEquals(k, l.size());
 898             assertEquals(SIZE - k, q.size());
 899             for (int j = 0; j < k; ++j)
 900                 assertEquals(l.get(j), new Integer(j));
 901             do {} while (q.poll() != null);
 902         }
 903     }
 904 
 905     /**
 906      * remove(null), contains(null) always return false
 907      */
 908     public void testNeverContainsNull() {
 909         Collection<?>[] qs = {
 910             new LinkedBlockingQueue<Object>(),
 911             populatedQueue(2),
 912         };
 913 
 914         for (Collection<?> q : qs) {
 915             assertFalse(q.contains(null));
 916             assertFalse(q.remove(null));
 917         }
 918     }
 919 
 920 }