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.Collections;

    42 import java.util.Iterator;

    43 import java.util.NoSuchElementException;

    44 import java.util.Queue;

    45 import java.util.concurrent.ArrayBlockingQueue;

    46 import java.util.concurrent.BlockingQueue;

    47 import java.util.concurrent.CountDownLatch;

    48 import java.util.concurrent.Executors;

    49 import java.util.concurrent.ExecutorService;

    50 import java.util.concurrent.ThreadLocalRandom;

    51 

    52 import junit.framework.Test;

    53 

    54 public class ArrayBlockingQueueTest extends JSR166TestCase {

    55 

    56     public static void main(String[] args) {

    57         main(suite(), args);

    58     }

    59 

    60     public static Test suite() {

    61         class Implementation implements CollectionImplementation {

    62             public Class<?> klazz() { return ArrayBlockingQueue.class; }

    63             public Collection emptyCollection() {

    64                 boolean fair = ThreadLocalRandom.current().nextBoolean();

    65                 return populatedQueue(0, SIZE, 2 * SIZE, fair);

    66             }

    67             public Object makeElement(int i) { return i; }

    68             public boolean isConcurrent() { return true; }

    69             public boolean permitsNulls() { return false; }

    70         }

    71 

    72         return newTestSuite(

    73             ArrayBlockingQueueTest.class,

    74             new Fair().testSuite(),

    75             new NonFair().testSuite(),

    76             CollectionTest.testSuite(new Implementation()));

    77     }

    78 

    79     public static class Fair extends BlockingQueueTest {

    80         protected BlockingQueue emptyCollection() {

    81             return populatedQueue(0, SIZE, 2 * SIZE, true);

    82         }

    83     }

    84 

    85     public static class NonFair extends BlockingQueueTest {

    86         protected BlockingQueue emptyCollection() {

    87             return populatedQueue(0, SIZE, 2 * SIZE, false);

    88         }

    89     }

    90 

    91     /**

    92      * Returns a new queue of given size containing consecutive

    93      * Integers 0 ... n - 1.

    94      */

    95     static ArrayBlockingQueue<Integer> populatedQueue(int n) {

    96         return populatedQueue(n, n, n, false);

    97     }

    98 

    99     /**

   100      * Returns a new queue of given size containing consecutive

   101      * Integers 0 ... n - 1, with given capacity range and fairness.

   102      */

   103     static ArrayBlockingQueue<Integer> populatedQueue(

   104         int size, int minCapacity, int maxCapacity, boolean fair) {

   105         ThreadLocalRandom rnd = ThreadLocalRandom.current();

   106         int capacity = rnd.nextInt(minCapacity, maxCapacity + 1);

   107         ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(capacity);

   108         assertTrue(q.isEmpty());

   109         // shuffle circular array elements so they wrap

   110         {

   111             int n = rnd.nextInt(capacity);

   112             for (int i = 0; i < n; i++) q.add(42);

   113             for (int i = 0; i < n; i++) q.remove();

   114         }

   115         for (int i = 0; i < size; i++)

   116             assertTrue(q.offer((Integer) i));

   117         assertEquals(size == 0, q.isEmpty());

   118         assertEquals(capacity - size, q.remainingCapacity());

   119         assertEquals(size, q.size());

   120         if (size > 0)

   121             assertEquals((Integer) 0, q.peek());

   122         return q;

   123     }

   124 

   125     /**

   126      * A new queue has the indicated capacity

   127      */

   128     public void testConstructor1() {

   129         assertEquals(SIZE, new ArrayBlockingQueue(SIZE).remainingCapacity());

   130     }

   131 

   132     /**

   133      * Constructor throws IllegalArgumentException if capacity argument nonpositive

   134      */

   135     public void testConstructor_nonPositiveCapacity() {

   136         for (int i : new int[] { 0, -1, Integer.MIN_VALUE }) {

   137             try {

   138                 new ArrayBlockingQueue(i);

   139                 shouldThrow();

   140             } catch (IllegalArgumentException success) {}

   141             for (boolean fair : new boolean[] { true, false }) {

   142                 try {

   143                     new ArrayBlockingQueue(i, fair);

   144                     shouldThrow();

   145                 } catch (IllegalArgumentException success) {}

   146             }

   147         }

   148     }

   149 

   150     /**

   151      * Initializing from null Collection throws NPE

   152      */

   153     public void testConstructor_nullCollection() {

   154         try {

   155             new ArrayBlockingQueue(1, true, null);

   156             shouldThrow();

   157         } catch (NullPointerException success) {}

   158     }

   159 

   160     /**

   161      * Initializing from Collection of null elements throws NPE

   162      */

   163     public void testConstructor4() {

   164         Collection<Integer> elements = Arrays.asList(new Integer[SIZE]);

   165         try {

   166             new ArrayBlockingQueue(SIZE, false, elements);

   167             shouldThrow();

   168         } catch (NullPointerException success) {}

   169     }

   170 

   171     /**

   172      * Initializing from Collection with some null elements throws NPE

   173      */

   174     public void testConstructor5() {

   175         Integer[] ints = new Integer[SIZE];

   176         for (int i = 0; i < SIZE - 1; ++i)

   177             ints[i] = i;

   178         Collection<Integer> elements = Arrays.asList(ints);

   179         try {

   180             new ArrayBlockingQueue(SIZE, false, elements);

   181             shouldThrow();

   182         } catch (NullPointerException success) {}

   183     }

   184 

   185     /**

   186      * Initializing from too large collection throws IllegalArgumentException

   187      */

   188     public void testConstructor_collectionTooLarge() {

   189         // just barely fits - succeeds

   190         new ArrayBlockingQueue(SIZE, false,

   191                                Collections.nCopies(SIZE, ""));

   192         try {

   193             new ArrayBlockingQueue(SIZE - 1, false,

   194                                    Collections.nCopies(SIZE, ""));

   195             shouldThrow();

   196         } catch (IllegalArgumentException success) {}

   197     }

   198 

   199     /**

   200      * Queue contains all elements of collection used to initialize

   201      */

   202     public void testConstructor7() {

   203         Integer[] ints = new Integer[SIZE];

   204         for (int i = 0; i < SIZE; ++i)

   205             ints[i] = i;

   206         Collection<Integer> elements = Arrays.asList(ints);

   207         ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE, true, elements);

   208         for (int i = 0; i < SIZE; ++i)

   209             assertEquals(ints[i], q.poll());

   210     }

   211 

   212     /**

   213      * Queue transitions from empty to full when elements added

   214      */

   215     public void testEmptyFull() {

   216         BlockingQueue q = populatedQueue(0, 2, 2, false);

   217         assertTrue(q.isEmpty());

   218         assertEquals(2, q.remainingCapacity());

   219         q.add(one);

   220         assertFalse(q.isEmpty());

   221         assertTrue(q.offer(two));

   222         assertFalse(q.isEmpty());

   223         assertEquals(0, q.remainingCapacity());

   224         assertFalse(q.offer(three));

   225     }

   226 

   227     /**

   228      * remainingCapacity decreases on add, increases on remove

   229      */

   230     public void testRemainingCapacity() {

   231         int size = ThreadLocalRandom.current().nextInt(1, SIZE);

   232         BlockingQueue q = populatedQueue(size, size, 2 * size, false);

   233         int spare = q.remainingCapacity();

   234         int capacity = spare + size;

   235         for (int i = 0; i < size; i++) {

   236             assertEquals(spare + i, q.remainingCapacity());

   237             assertEquals(capacity, q.size() + q.remainingCapacity());

   238             assertEquals(i, q.remove());

   239         }

   240         for (int i = 0; i < size; i++) {

   241             assertEquals(capacity - i, q.remainingCapacity());

   242             assertEquals(capacity, q.size() + q.remainingCapacity());

   243             assertTrue(q.add(i));

   244         }

   245     }

   246 

   247     /**

   248      * Offer succeeds if not full; fails if full

   249      */

   250     public void testOffer() {

   251         ArrayBlockingQueue q = new ArrayBlockingQueue(1);

   252         assertTrue(q.offer(zero));

   253         assertFalse(q.offer(one));

   254     }

   255 

   256     /**

   257      * add succeeds if not full; throws IllegalStateException if full

   258      */

   259     public void testAdd() {

   260         ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);

   261         for (int i = 0; i < SIZE; i++) assertTrue(q.add((Integer) i));

   262         assertEquals(0, q.remainingCapacity());

   263         try {

   264             q.add((Integer) SIZE);

   265             shouldThrow();

   266         } catch (IllegalStateException success) {}

   267     }

   268 

   269     /**

   270      * addAll(this) throws IllegalArgumentException

   271      */

   272     public void testAddAllSelf() {

   273         ArrayBlockingQueue q = populatedQueue(SIZE);

   274         try {

   275             q.addAll(q);

   276             shouldThrow();

   277         } catch (IllegalArgumentException success) {}

   278     }

   279 

   280     /**

   281      * addAll of a collection with any null elements throws NPE after

   282      * possibly adding some elements

   283      */

   284     public void testAddAll3() {

   285         ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);

   286         Integer[] ints = new Integer[SIZE];

   287         for (int i = 0; i < SIZE - 1; ++i)

   288             ints[i] = new Integer(i);

   289         try {

   290             q.addAll(Arrays.asList(ints));

   291             shouldThrow();

   292         } catch (NullPointerException success) {}

   293     }

   294 

   295     /**

   296      * addAll throws IllegalStateException if not enough room

   297      */

   298     public void testAddAll_insufficientSpace() {

   299         int size = ThreadLocalRandom.current().nextInt(1, SIZE);

   300         ArrayBlockingQueue q = populatedQueue(0, size, size, false);

   301         // Just fits:

   302         q.addAll(populatedQueue(size, size, 2 * size, false));

   303         assertEquals(0, q.remainingCapacity());

   304         assertEquals(size, q.size());

   305         assertEquals(0, q.peek());

   306         try {

   307             q = populatedQueue(0, size, size, false);

   308             q.addAll(Collections.nCopies(size + 1, 42));

   309             shouldThrow();

   310         } catch (IllegalStateException success) {}

   311     }

   312 

   313     /**

   314      * Queue contains all elements, in traversal order, of successful addAll

   315      */

   316     public void testAddAll5() {

   317         Integer[] empty = new Integer[0];

   318         Integer[] ints = new Integer[SIZE];

   319         for (int i = 0; i < SIZE; ++i)

   320             ints[i] = new Integer(i);

   321         ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);

   322         assertFalse(q.addAll(Arrays.asList(empty)));

   323         assertTrue(q.addAll(Arrays.asList(ints)));

   324         for (int i = 0; i < SIZE; ++i)

   325             assertEquals(ints[i], q.poll());

   326     }

   327 

   328     /**

   329      * all elements successfully put are contained

   330      */

   331     public void testPut() throws InterruptedException {

   332         ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);

   333         for (int i = 0; i < SIZE; ++i) {

   334             Integer x = new Integer(i);

   335             q.put(x);

   336             assertTrue(q.contains(x));

   337         }

   338         assertEquals(0, q.remainingCapacity());

   339     }

   340 

   341     /**

   342      * put blocks interruptibly if full

   343      */

   344     public void testBlockingPut() throws InterruptedException {

   345         final ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE);

   346         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);

   347         Thread t = newStartedThread(new CheckedRunnable() {

   348             public void realRun() throws InterruptedException {

   349                 for (int i = 0; i < SIZE; ++i)

   350                     q.put(i);

   351                 assertEquals(SIZE, q.size());

   352                 assertEquals(0, q.remainingCapacity());

   353 

   354                 Thread.currentThread().interrupt();

   355                 try {

   356                     q.put(99);

   357                     shouldThrow();

   358                 } catch (InterruptedException success) {}

   359                 assertFalse(Thread.interrupted());

   360 

   361                 pleaseInterrupt.countDown();

   362                 try {

   363                     q.put(99);

   364                     shouldThrow();

   365                 } catch (InterruptedException success) {}

   366                 assertFalse(Thread.interrupted());

   367             }});

   368 

   369         await(pleaseInterrupt);

   370         assertThreadBlocks(t, Thread.State.WAITING);

   371         t.interrupt();

   372         awaitTermination(t);

   373         assertEquals(SIZE, q.size());

   374         assertEquals(0, q.remainingCapacity());

   375     }

   376 

   377     /**

   378      * put blocks interruptibly waiting for take when full

   379      */

   380     public void testPutWithTake() throws InterruptedException {

   381         final int capacity = 2;

   382         final ArrayBlockingQueue q = new ArrayBlockingQueue(capacity);

   383         final CountDownLatch pleaseTake = new CountDownLatch(1);

   384         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);

   385         Thread t = newStartedThread(new CheckedRunnable() {

   386             public void realRun() throws InterruptedException {

   387                 for (int i = 0; i < capacity; i++)

   388                     q.put(i);

   389                 pleaseTake.countDown();

   390                 q.put(86);

   391 

   392                 Thread.currentThread().interrupt();

   393                 try {

   394                     q.put(99);

   395                     shouldThrow();

   396                 } catch (InterruptedException success) {}

   397                 assertFalse(Thread.interrupted());

   398 

   399                 pleaseInterrupt.countDown();

   400                 try {

   401                     q.put(99);

   402                     shouldThrow();

   403                 } catch (InterruptedException success) {}

   404                 assertFalse(Thread.interrupted());

   405             }});

   406 

   407         await(pleaseTake);

   408         assertEquals(0, q.remainingCapacity());

   409         assertEquals(0, q.take());

   410 

   411         await(pleaseInterrupt);

   412         assertThreadBlocks(t, Thread.State.WAITING);

   413         t.interrupt();

   414         awaitTermination(t);

   415         assertEquals(0, q.remainingCapacity());

   416     }

   417 

   418     /**

   419      * timed offer times out if full and elements not taken

   420      */

   421     public void testTimedOffer() {

   422         final ArrayBlockingQueue q = new ArrayBlockingQueue(2);

   423         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);

   424         Thread t = newStartedThread(new CheckedRunnable() {

   425             public void realRun() throws InterruptedException {

   426                 q.put(new Object());

   427                 q.put(new Object());

   428                 long startTime = System.nanoTime();

   429                 assertFalse(q.offer(new Object(), timeoutMillis(), MILLISECONDS));

   430                 assertTrue(millisElapsedSince(startTime) >= timeoutMillis());

   431 

   432                 Thread.currentThread().interrupt();

   433                 try {

   434                     q.offer(new Object(), 2 * LONG_DELAY_MS, MILLISECONDS);

   435                     shouldThrow();

   436                 } catch (InterruptedException success) {}

   437                 assertFalse(Thread.interrupted());

   438 

   439                 pleaseInterrupt.countDown();

   440                 try {

   441                     q.offer(new Object(), 2 * LONG_DELAY_MS, MILLISECONDS);

   442                     shouldThrow();

   443                 } catch (InterruptedException success) {}

   444                 assertFalse(Thread.interrupted());

   445             }});

   446 

   447         await(pleaseInterrupt);

   448         assertThreadBlocks(t, Thread.State.TIMED_WAITING);

   449         t.interrupt();

   450         awaitTermination(t);

   451     }

   452 

   453     /**

   454      * take retrieves elements in FIFO order

   455      */

   456     public void testTake() throws InterruptedException {

   457         ArrayBlockingQueue q = populatedQueue(SIZE);

   458         for (int i = 0; i < SIZE; ++i) {

   459             assertEquals(i, q.take());

   460         }

   461     }

   462 

   463     /**

   464      * Take removes existing elements until empty, then blocks interruptibly

   465      */

   466     public void testBlockingTake() throws InterruptedException {

   467         final ArrayBlockingQueue q = populatedQueue(SIZE);

   468         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);

   469         Thread t = newStartedThread(new CheckedRunnable() {

   470             public void realRun() throws InterruptedException {

   471                 for (int i = 0; i < SIZE; i++) assertEquals(i, q.take());

   472 

   473                 Thread.currentThread().interrupt();

   474                 try {

   475                     q.take();

   476                     shouldThrow();

   477                 } catch (InterruptedException success) {}

   478                 assertFalse(Thread.interrupted());

   479 

   480                 pleaseInterrupt.countDown();

   481                 try {

   482                     q.take();

   483                     shouldThrow();

   484                 } catch (InterruptedException success) {}

   485                 assertFalse(Thread.interrupted());

   486             }});

   487 

   488         await(pleaseInterrupt);

   489         assertThreadBlocks(t, Thread.State.WAITING);

   490         t.interrupt();

   491         awaitTermination(t);

   492     }

   493 

   494     /**

   495      * poll succeeds unless empty

   496      */

   497     public void testPoll() {

   498         ArrayBlockingQueue q = populatedQueue(SIZE);

   499         for (int i = 0; i < SIZE; ++i) {

   500             assertEquals(i, q.poll());

   501         }

   502         assertNull(q.poll());

   503     }

   504 

   505     /**

   506      * timed poll with zero timeout succeeds when non-empty, else times out

   507      */

   508     public void testTimedPoll0() throws InterruptedException {

   509         ArrayBlockingQueue q = populatedQueue(SIZE);

   510         for (int i = 0; i < SIZE; ++i) {

   511             assertEquals(i, q.poll(0, MILLISECONDS));

   512         }

   513         assertNull(q.poll(0, MILLISECONDS));

   514         checkEmpty(q);

   515     }

   516 

   517     /**

   518      * timed poll with nonzero timeout succeeds when non-empty, else times out

   519      */

   520     public void testTimedPoll() throws InterruptedException {

   521         ArrayBlockingQueue q = populatedQueue(SIZE);

   522         for (int i = 0; i < SIZE; ++i) {

   523             long startTime = System.nanoTime();

   524             assertEquals(i, q.poll(LONG_DELAY_MS, MILLISECONDS));

   525             assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);

   526         }

   527         long startTime = System.nanoTime();

   528         assertNull(q.poll(timeoutMillis(), MILLISECONDS));

   529         assertTrue(millisElapsedSince(startTime) >= timeoutMillis());

   530         checkEmpty(q);

   531     }

   532 

   533     /**

   534      * Interrupted timed poll throws InterruptedException instead of

   535      * returning timeout status

   536      */

   537     public void testInterruptedTimedPoll() throws InterruptedException {

   538         final BlockingQueue<Integer> q = populatedQueue(SIZE);

   539         final CountDownLatch pleaseInterrupt = new CountDownLatch(1);

   540         Thread t = newStartedThread(new CheckedRunnable() {

   541             public void realRun() throws InterruptedException {

   542                 long startTime = System.nanoTime();

   543                 for (int i = 0; i < SIZE; i++)

   544                     assertEquals(i, (int) q.poll(LONG_DELAY_MS, MILLISECONDS));

   545 

   546                 Thread.currentThread().interrupt();

   547                 try {

   548                     q.poll(LONG_DELAY_MS, MILLISECONDS);

   549                     shouldThrow();

   550                 } catch (InterruptedException success) {}

   551                 assertFalse(Thread.interrupted());

   552 

   553                 pleaseInterrupt.countDown();

   554                 try {

   555                     q.poll(LONG_DELAY_MS, MILLISECONDS);

   556                     shouldThrow();

   557                 } catch (InterruptedException success) {}

   558                 assertFalse(Thread.interrupted());

   559 

   560                 assertTrue(millisElapsedSince(startTime) < LONG_DELAY_MS);

   561             }});

   562 

   563         await(pleaseInterrupt);

   564         assertThreadBlocks(t, Thread.State.TIMED_WAITING);

   565         t.interrupt();

   566         awaitTermination(t);

   567         checkEmpty(q);

   568     }

   569 

   570     /**

   571      * peek returns next element, or null if empty

   572      */

   573     public void testPeek() {

   574         ArrayBlockingQueue q = populatedQueue(SIZE);

   575         for (int i = 0; i < SIZE; ++i) {

   576             assertEquals(i, q.peek());

   577             assertEquals(i, q.poll());

   578             assertTrue(q.peek() == null ||

   579                        !q.peek().equals(i));

   580         }

   581         assertNull(q.peek());

   582     }

   583 

   584     /**

   585      * element returns next element, or throws NSEE if empty

   586      */

   587     public void testElement() {

   588         ArrayBlockingQueue q = populatedQueue(SIZE);

   589         for (int i = 0; i < SIZE; ++i) {

   590             assertEquals(i, q.element());

   591             assertEquals(i, q.poll());

   592         }

   593         try {

   594             q.element();

   595             shouldThrow();

   596         } catch (NoSuchElementException success) {}

   597     }

   598 

   599     /**

   600      * remove removes next element, or throws NSEE if empty

   601      */

   602     public void testRemove() {

   603         ArrayBlockingQueue q = populatedQueue(SIZE);

   604         for (int i = 0; i < SIZE; ++i) {

   605             assertEquals(i, q.remove());

   606         }

   607         try {

   608             q.remove();

   609             shouldThrow();

   610         } catch (NoSuchElementException success) {}

   611     }

   612 

   613     /**

   614      * contains(x) reports true when elements added but not yet removed

   615      */

   616     public void testContains() {

   617         int size = ThreadLocalRandom.current().nextInt(1, SIZE);

   618         ArrayBlockingQueue q = populatedQueue(size, size, 2 * size, false);

   619         assertFalse(q.contains(null));

   620         for (int i = 0; i < size; ++i) {

   621             assertTrue(q.contains(new Integer(i)));

   622             assertEquals(i, q.poll());

   623             assertFalse(q.contains(new Integer(i)));

   624         }

   625     }

   626 

   627     /**

   628      * clear removes all elements

   629      */

   630     public void testClear() {

   631         int size = ThreadLocalRandom.current().nextInt(1, 5);

   632         ArrayBlockingQueue q = populatedQueue(size, size, 2 * size, false);

   633         int capacity = size + q.remainingCapacity();

   634         q.clear();

   635         assertTrue(q.isEmpty());

   636         assertEquals(0, q.size());

   637         assertEquals(capacity, q.remainingCapacity());

   638         q.add(one);

   639         assertFalse(q.isEmpty());

   640         assertTrue(q.contains(one));

   641         q.clear();

   642         assertTrue(q.isEmpty());

   643     }

   644 

   645     /**

   646      * containsAll(c) is true when c contains a subset of elements

   647      */

   648     public void testContainsAll() {

   649         ArrayBlockingQueue q = populatedQueue(SIZE);

   650         ArrayBlockingQueue p = new ArrayBlockingQueue(SIZE);

   651         for (int i = 0; i < SIZE; ++i) {

   652             assertTrue(q.containsAll(p));

   653             assertFalse(p.containsAll(q));

   654             p.add(new Integer(i));

   655         }

   656         assertTrue(p.containsAll(q));

   657     }

   658 

   659     /**

   660      * retainAll(c) retains only those elements of c and reports true if changed

   661      */

   662     public void testRetainAll() {

   663         ArrayBlockingQueue q = populatedQueue(SIZE);

   664         ArrayBlockingQueue p = populatedQueue(SIZE);

   665         for (int i = 0; i < SIZE; ++i) {

   666             boolean changed = q.retainAll(p);

   667             if (i == 0)

   668                 assertFalse(changed);

   669             else

   670                 assertTrue(changed);

   671 

   672             assertTrue(q.containsAll(p));

   673             assertEquals(SIZE - i, q.size());

   674             p.remove();

   675         }

   676     }

   677 

   678     /**

   679      * removeAll(c) removes only those elements of c and reports true if changed

   680      */

   681     public void testRemoveAll() {

   682         for (int i = 1; i < SIZE; ++i) {

   683             ArrayBlockingQueue q = populatedQueue(SIZE);

   684             ArrayBlockingQueue p = populatedQueue(i);

   685             assertTrue(q.removeAll(p));

   686             assertEquals(SIZE - i, q.size());

   687             for (int j = 0; j < i; ++j) {

   688                 Integer x = (Integer)(p.remove());

   689                 assertFalse(q.contains(x));

   690             }

   691         }

   692     }

   693 

   694     void checkToArray(ArrayBlockingQueue<Integer> q) {

   695         int size = q.size();

   696         Object[] a1 = q.toArray();

   697         assertEquals(size, a1.length);

   698         Integer[] a2 = q.toArray(new Integer[0]);

   699         assertEquals(size, a2.length);

   700         Integer[] a3 = q.toArray(new Integer[Math.max(0, size - 1)]);

   701         assertEquals(size, a3.length);

   702         Integer[] a4 = new Integer[size];

   703         assertSame(a4, q.toArray(a4));

   704         Integer[] a5 = new Integer[size + 1];

   705         Arrays.fill(a5, 42);

   706         assertSame(a5, q.toArray(a5));

   707         Integer[] a6 = new Integer[size + 2];

   708         Arrays.fill(a6, 42);

   709         assertSame(a6, q.toArray(a6));

   710         Object[][] as = { a1, a2, a3, a4, a5, a6 };

   711         for (Object[] a : as) {

   712             if (a.length > size) assertNull(a[size]);

   713             if (a.length > size + 1) assertEquals(42, a[size + 1]);

   714         }

   715         Iterator it = q.iterator();

   716         Integer s = q.peek();

   717         for (int i = 0; i < size; i++) {

   718             Integer x = (Integer) it.next();

   719             assertEquals(s + i, (int) x);

   720             for (Object[] a : as)

   721                 assertSame(a1[i], x);

   722         }

   723     }

   724 

   725     /**

   726      * toArray() and toArray(a) contain all elements in FIFO order

   727      */

   728     public void testToArray() {

   729         final ThreadLocalRandom rnd = ThreadLocalRandom.current();

   730         final int size = rnd.nextInt(6);

   731         final int capacity = Math.max(1, size + rnd.nextInt(size + 1));

   732         ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(capacity);

   733         for (int i = 0; i < size; i++) {

   734             checkToArray(q);

   735             q.add(i);

   736         }

   737         // Provoke wraparound

   738         int added = size * 2;

   739         for (int i = 0; i < added; i++) {

   740             checkToArray(q);

   741             assertEquals((Integer) i, q.poll());

   742             q.add(size + i);

   743         }

   744         for (int i = 0; i < size; i++) {

   745             checkToArray(q);

   746             assertEquals((Integer) (added + i), q.poll());

   747         }

   748     }

   749 

   750     /**

   751      * toArray(incompatible array type) throws ArrayStoreException

   752      */

   753     public void testToArray_incompatibleArrayType() {

   754         ArrayBlockingQueue q = populatedQueue(SIZE);

   755         try {

   756             q.toArray(new String[10]);

   757             shouldThrow();

   758         } catch (ArrayStoreException success) {}

   759         try {

   760             q.toArray(new String[0]);

   761             shouldThrow();

   762         } catch (ArrayStoreException success) {}

   763     }

   764 

   765     /**

   766      * iterator iterates through all elements

   767      */

   768     public void testIterator() throws InterruptedException {

   769         ArrayBlockingQueue q = populatedQueue(SIZE);

   770         Iterator it = q.iterator();

   771         int i;

   772         for (i = 0; it.hasNext(); i++)

   773             assertTrue(q.contains(it.next()));

   774         assertEquals(i, SIZE);

   775         assertIteratorExhausted(it);

   776 

   777         it = q.iterator();

   778         for (i = 0; it.hasNext(); i++)

   779             assertEquals(it.next(), q.take());

   780         assertEquals(i, SIZE);

   781         assertIteratorExhausted(it);

   782     }

   783 

   784     /**

   785      * iterator of empty collection has no elements

   786      */

   787     public void testEmptyIterator() {

   788         assertIteratorExhausted(new ArrayBlockingQueue(SIZE).iterator());

   789     }

   790 

   791     /**

   792      * iterator.remove removes current element

   793      */

   794     public void testIteratorRemove() {

   795         final ArrayBlockingQueue q = new ArrayBlockingQueue(3);

   796         q.add(two);

   797         q.add(one);

   798         q.add(three);

   799 

   800         Iterator it = q.iterator();

   801         it.next();

   802         it.remove();

   803 

   804         it = q.iterator();

   805         assertSame(it.next(), one);

   806         assertSame(it.next(), three);

   807         assertFalse(it.hasNext());

   808     }

   809 

   810     /**

   811      * iterator ordering is FIFO

   812      */

   813     public void testIteratorOrdering() {

   814         final ArrayBlockingQueue q = new ArrayBlockingQueue(3);

   815         q.add(one);

   816         q.add(two);

   817         q.add(three);

   818 

   819         assertEquals("queue should be full", 0, q.remainingCapacity());

   820 

   821         int k = 0;

   822         for (Iterator it = q.iterator(); it.hasNext();) {

   823             assertEquals(++k, it.next());

   824         }

   825         assertEquals(3, k);

   826     }

   827 

   828     /**

   829      * Modifications do not cause iterators to fail

   830      */

   831     public void testWeaklyConsistentIteration() {

   832         final ArrayBlockingQueue q = new ArrayBlockingQueue(3);

   833         q.add(one);

   834         q.add(two);

   835         q.add(three);

   836         for (Iterator it = q.iterator(); it.hasNext();) {

   837             q.remove();

   838             it.next();

   839         }

   840         assertEquals(0, q.size());

   841     }

   842 

   843     /**

   844      * toString contains toStrings of elements

   845      */

   846     public void testToString() {

   847         ArrayBlockingQueue q = populatedQueue(SIZE);

   848         String s = q.toString();

   849         for (int i = 0; i < SIZE; ++i) {

   850             assertTrue(s.contains(String.valueOf(i)));

   851         }

   852     }

   853 

   854     /**

   855      * offer transfers elements across Executor tasks

   856      */

   857     public void testOfferInExecutor() {

   858         final ArrayBlockingQueue q = new ArrayBlockingQueue(2);

   859         q.add(one);

   860         q.add(two);

   861         final CheckedBarrier threadsStarted = new CheckedBarrier(2);

   862         final ExecutorService executor = Executors.newFixedThreadPool(2);

   863         try (PoolCleaner cleaner = cleaner(executor)) {

   864             executor.execute(new CheckedRunnable() {

   865                 public void realRun() throws InterruptedException {

   866                     assertFalse(q.offer(three));

   867                     threadsStarted.await();

   868                     assertTrue(q.offer(three, LONG_DELAY_MS, MILLISECONDS));

   869                     assertEquals(0, q.remainingCapacity());

   870                 }});

   871 

   872             executor.execute(new CheckedRunnable() {

   873                 public void realRun() throws InterruptedException {

   874                     threadsStarted.await();

   875                     assertEquals(0, q.remainingCapacity());

   876                     assertSame(one, q.take());

   877                 }});

   878         }

   879     }

   880 

   881     /**

   882      * timed poll retrieves elements across Executor threads

   883      */

   884     public void testPollInExecutor() {

   885         final ArrayBlockingQueue q = new ArrayBlockingQueue(2);

   886         final CheckedBarrier threadsStarted = new CheckedBarrier(2);

   887         final ExecutorService executor = Executors.newFixedThreadPool(2);

   888         try (PoolCleaner cleaner = cleaner(executor)) {

   889             executor.execute(new CheckedRunnable() {

   890                 public void realRun() throws InterruptedException {

   891                     assertNull(q.poll());

   892                     threadsStarted.await();

   893                     assertSame(one, q.poll(LONG_DELAY_MS, MILLISECONDS));

   894                     checkEmpty(q);

   895                 }});

   896 

   897             executor.execute(new CheckedRunnable() {

   898                 public void realRun() throws InterruptedException {

   899                     threadsStarted.await();

   900                     q.put(one);

   901                 }});

   902         }

   903     }

   904 

   905     /**

   906      * A deserialized/reserialized queue has same elements in same order

   907      */

   908     public void testSerialization() throws Exception {

   909         Queue x = populatedQueue(SIZE);

   910         Queue y = serialClone(x);

   911 

   912         assertNotSame(x, y);

   913         assertEquals(x.size(), y.size());

   914         assertEquals(x.toString(), y.toString());

   915         assertTrue(Arrays.equals(x.toArray(), y.toArray()));

   916         while (!x.isEmpty()) {

   917             assertFalse(y.isEmpty());

   918             assertEquals(x.remove(), y.remove());

   919         }

   920         assertTrue(y.isEmpty());

   921     }

   922 

   923     /**

   924      * drainTo(c) empties queue into another collection c

   925      */

   926     public void testDrainTo() {

   927         ArrayBlockingQueue q = populatedQueue(SIZE);

   928         ArrayList l = new ArrayList();

   929         q.drainTo(l);

   930         assertEquals(0, q.size());

   931         assertEquals(SIZE, l.size());

   932         for (int i = 0; i < SIZE; ++i)

   933             assertEquals(l.get(i), new Integer(i));

   934         q.add(zero);

   935         q.add(one);

   936         assertFalse(q.isEmpty());

   937         assertTrue(q.contains(zero));

   938         assertTrue(q.contains(one));

   939         l.clear();

   940         q.drainTo(l);

   941         assertEquals(0, q.size());

   942         assertEquals(2, l.size());

   943         for (int i = 0; i < 2; ++i)

   944             assertEquals(l.get(i), new Integer(i));

   945     }

   946 

   947     /**

   948      * drainTo empties full queue, unblocking a waiting put.

   949      */

   950     public void testDrainToWithActivePut() throws InterruptedException {

   951         final ArrayBlockingQueue q = populatedQueue(SIZE);

   952         Thread t = new Thread(new CheckedRunnable() {

   953             public void realRun() throws InterruptedException {

   954                 q.put(new Integer(SIZE + 1));

   955             }});

   956 

   957         t.start();

   958         ArrayList l = new ArrayList();

   959         q.drainTo(l);

   960         assertTrue(l.size() >= SIZE);

   961         for (int i = 0; i < SIZE; ++i)

   962             assertEquals(l.get(i), new Integer(i));

   963         t.join();

   964         assertTrue(q.size() + l.size() >= SIZE);

   965     }

   966 

   967     /**

   968      * drainTo(c, n) empties first min(n, size) elements of queue into c

   969      */

   970     public void testDrainToN() {

   971         ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE * 2);

   972         for (int i = 0; i < SIZE + 2; ++i) {

   973             for (int j = 0; j < SIZE; j++)

   974                 assertTrue(q.offer(new Integer(j)));

   975             ArrayList l = new ArrayList();

   976             q.drainTo(l, i);

   977             int k = (i < SIZE) ? i : SIZE;

   978             assertEquals(k, l.size());

   979             assertEquals(SIZE - k, q.size());

   980             for (int j = 0; j < k; ++j)

   981                 assertEquals(l.get(j), new Integer(j));

   982             do {} while (q.poll() != null);

   983         }

   984     }

   985 

   986     /**

   987      * remove(null), contains(null) always return false

   988      */

   989     public void testNeverContainsNull() {

   990         Collection<?>[] qs = {

   991             populatedQueue(0, 1, 10, false),

   992             populatedQueue(2, 2, 10, true),

   993         };

   994 

   995         for (Collection<?> q : qs) {

   996             assertFalse(q.contains(null));

   997             assertFalse(q.remove(null));

   998         }

   999     }

  1000 }