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