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 = randomBoolean();
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 if (randomBoolean()) 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 if (randomBoolean()) 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(), randomTimeout(), randomTimeUnit());
435 shouldThrow();
436 } catch (InterruptedException success) {}
437 assertFalse(Thread.interrupted());
438
439 pleaseInterrupt.countDown();
440 try {
441 q.offer(new Object(), LONGER_DELAY_MS, MILLISECONDS);
442 shouldThrow();
443 } catch (InterruptedException success) {}
444 assertFalse(Thread.interrupted());
445 }});
446
447 await(pleaseInterrupt);
448 if (randomBoolean()) 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 if (randomBoolean()) 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 for (int i = 0; i < SIZE; i++)
543 assertEquals(i, (int) q.poll(LONG_DELAY_MS, MILLISECONDS));
544
545 Thread.currentThread().interrupt();
546 try {
547 q.poll(randomTimeout(), randomTimeUnit());
548 shouldThrow();
549 } catch (InterruptedException success) {}
550 assertFalse(Thread.interrupted());
551
552 pleaseInterrupt.countDown();
553 try {
554 q.poll(LONGER_DELAY_MS, MILLISECONDS);
555 shouldThrow();
556 } catch (InterruptedException success) {}
557 assertFalse(Thread.interrupted());
558 }});
559
560 await(pleaseInterrupt);
561 if (randomBoolean()) assertThreadBlocks(t, Thread.State.TIMED_WAITING);
562 t.interrupt();
563 awaitTermination(t);
564 checkEmpty(q);
565 }
566
567 /**
568 * peek returns next element, or null if empty
569 */
570 public void testPeek() {
571 ArrayBlockingQueue q = populatedQueue(SIZE);
572 for (int i = 0; i < SIZE; ++i) {
573 assertEquals(i, q.peek());
574 assertEquals(i, q.poll());
575 assertTrue(q.peek() == null ||
576 !q.peek().equals(i));
577 }
578 assertNull(q.peek());
579 }
580
581 /**
582 * element returns next element, or throws NSEE if empty
583 */
584 public void testElement() {
585 ArrayBlockingQueue q = populatedQueue(SIZE);
586 for (int i = 0; i < SIZE; ++i) {
587 assertEquals(i, q.element());
588 assertEquals(i, q.poll());
589 }
590 try {
591 q.element();
592 shouldThrow();
593 } catch (NoSuchElementException success) {}
594 }
595
596 /**
597 * remove removes next element, or throws NSEE if empty
598 */
599 public void testRemove() {
600 ArrayBlockingQueue q = populatedQueue(SIZE);
601 for (int i = 0; i < SIZE; ++i) {
602 assertEquals(i, q.remove());
603 }
604 try {
605 q.remove();
606 shouldThrow();
607 } catch (NoSuchElementException success) {}
608 }
609
610 /**
611 * contains(x) reports true when elements added but not yet removed
612 */
613 public void testContains() {
614 int size = ThreadLocalRandom.current().nextInt(1, SIZE);
615 ArrayBlockingQueue q = populatedQueue(size, size, 2 * size, false);
616 assertFalse(q.contains(null));
617 for (int i = 0; i < size; ++i) {
618 assertTrue(q.contains(new Integer(i)));
619 assertEquals(i, q.poll());
620 assertFalse(q.contains(new Integer(i)));
621 }
622 }
623
624 /**
625 * clear removes all elements
626 */
627 public void testClear() {
628 int size = ThreadLocalRandom.current().nextInt(1, 5);
629 ArrayBlockingQueue q = populatedQueue(size, size, 2 * size, false);
630 int capacity = size + q.remainingCapacity();
631 q.clear();
632 assertTrue(q.isEmpty());
633 assertEquals(0, q.size());
634 assertEquals(capacity, q.remainingCapacity());
635 q.add(one);
636 assertFalse(q.isEmpty());
637 assertTrue(q.contains(one));
638 q.clear();
639 assertTrue(q.isEmpty());
640 }
641
642 /**
643 * containsAll(c) is true when c contains a subset of elements
644 */
645 public void testContainsAll() {
646 ArrayBlockingQueue q = populatedQueue(SIZE);
647 ArrayBlockingQueue p = new ArrayBlockingQueue(SIZE);
648 for (int i = 0; i < SIZE; ++i) {
649 assertTrue(q.containsAll(p));
650 assertFalse(p.containsAll(q));
651 p.add(new Integer(i));
652 }
653 assertTrue(p.containsAll(q));
654 }
655
656 /**
657 * retainAll(c) retains only those elements of c and reports true if changed
658 */
659 public void testRetainAll() {
660 ArrayBlockingQueue q = populatedQueue(SIZE);
661 ArrayBlockingQueue p = populatedQueue(SIZE);
662 for (int i = 0; i < SIZE; ++i) {
663 boolean changed = q.retainAll(p);
664 if (i == 0)
665 assertFalse(changed);
666 else
667 assertTrue(changed);
668
669 assertTrue(q.containsAll(p));
670 assertEquals(SIZE - i, q.size());
671 p.remove();
672 }
673 }
674
675 /**
676 * removeAll(c) removes only those elements of c and reports true if changed
677 */
678 public void testRemoveAll() {
679 for (int i = 1; i < SIZE; ++i) {
680 ArrayBlockingQueue q = populatedQueue(SIZE);
681 ArrayBlockingQueue p = populatedQueue(i);
682 assertTrue(q.removeAll(p));
683 assertEquals(SIZE - i, q.size());
684 for (int j = 0; j < i; ++j) {
685 Integer x = (Integer)(p.remove());
686 assertFalse(q.contains(x));
687 }
688 }
689 }
690
691 void checkToArray(ArrayBlockingQueue<Integer> q) {
692 int size = q.size();
693 Object[] a1 = q.toArray();
694 assertEquals(size, a1.length);
695 Integer[] a2 = q.toArray(new Integer[0]);
696 assertEquals(size, a2.length);
697 Integer[] a3 = q.toArray(new Integer[Math.max(0, size - 1)]);
698 assertEquals(size, a3.length);
699 Integer[] a4 = new Integer[size];
700 assertSame(a4, q.toArray(a4));
701 Integer[] a5 = new Integer[size + 1];
702 Arrays.fill(a5, 42);
703 assertSame(a5, q.toArray(a5));
704 Integer[] a6 = new Integer[size + 2];
705 Arrays.fill(a6, 42);
706 assertSame(a6, q.toArray(a6));
707 Object[][] as = { a1, a2, a3, a4, a5, a6 };
708 for (Object[] a : as) {
709 if (a.length > size) assertNull(a[size]);
710 if (a.length > size + 1) assertEquals(42, a[size + 1]);
711 }
712 Iterator it = q.iterator();
713 Integer s = q.peek();
714 for (int i = 0; i < size; i++) {
715 Integer x = (Integer) it.next();
716 assertEquals(s + i, (int) x);
717 for (Object[] a : as)
718 assertSame(a1[i], x);
719 }
720 }
721
722 /**
723 * toArray() and toArray(a) contain all elements in FIFO order
724 */
725 public void testToArray() {
726 final ThreadLocalRandom rnd = ThreadLocalRandom.current();
727 final int size = rnd.nextInt(6);
728 final int capacity = Math.max(1, size + rnd.nextInt(size + 1));
729 ArrayBlockingQueue<Integer> q = new ArrayBlockingQueue<>(capacity);
730 for (int i = 0; i < size; i++) {
731 checkToArray(q);
732 q.add(i);
733 }
734 // Provoke wraparound
735 int added = size * 2;
736 for (int i = 0; i < added; i++) {
737 checkToArray(q);
738 assertEquals((Integer) i, q.poll());
739 q.add(size + i);
740 }
741 for (int i = 0; i < size; i++) {
742 checkToArray(q);
743 assertEquals((Integer) (added + i), q.poll());
744 }
745 }
746
747 /**
748 * toArray(incompatible array type) throws ArrayStoreException
749 */
750 public void testToArray_incompatibleArrayType() {
751 ArrayBlockingQueue q = populatedQueue(SIZE);
752 try {
753 q.toArray(new String[10]);
754 shouldThrow();
755 } catch (ArrayStoreException success) {}
756 try {
757 q.toArray(new String[0]);
758 shouldThrow();
759 } catch (ArrayStoreException success) {}
760 }
761
762 /**
763 * iterator iterates through all elements
764 */
765 public void testIterator() throws InterruptedException {
766 ArrayBlockingQueue q = populatedQueue(SIZE);
767 Iterator it = q.iterator();
768 int i;
769 for (i = 0; it.hasNext(); i++)
770 assertTrue(q.contains(it.next()));
771 assertEquals(i, SIZE);
772 assertIteratorExhausted(it);
773
774 it = q.iterator();
775 for (i = 0; it.hasNext(); i++)
776 assertEquals(it.next(), q.take());
777 assertEquals(i, SIZE);
778 assertIteratorExhausted(it);
779 }
780
781 /**
782 * iterator of empty collection has no elements
783 */
784 public void testEmptyIterator() {
785 assertIteratorExhausted(new ArrayBlockingQueue(SIZE).iterator());
786 }
787
788 /**
789 * iterator.remove removes current element
790 */
791 public void testIteratorRemove() {
792 final ArrayBlockingQueue q = new ArrayBlockingQueue(3);
793 q.add(two);
794 q.add(one);
795 q.add(three);
796
797 Iterator it = q.iterator();
798 it.next();
799 it.remove();
800
801 it = q.iterator();
802 assertSame(it.next(), one);
803 assertSame(it.next(), three);
804 assertFalse(it.hasNext());
805 }
806
807 /**
808 * iterator ordering is FIFO
809 */
810 public void testIteratorOrdering() {
811 final ArrayBlockingQueue q = new ArrayBlockingQueue(3);
812 q.add(one);
813 q.add(two);
814 q.add(three);
815
816 assertEquals("queue should be full", 0, q.remainingCapacity());
817
818 int k = 0;
819 for (Iterator it = q.iterator(); it.hasNext();) {
820 assertEquals(++k, it.next());
821 }
822 assertEquals(3, k);
823 }
824
825 /**
826 * Modifications do not cause iterators to fail
827 */
828 public void testWeaklyConsistentIteration() {
829 final ArrayBlockingQueue q = new ArrayBlockingQueue(3);
830 q.add(one);
831 q.add(two);
832 q.add(three);
833 for (Iterator it = q.iterator(); it.hasNext();) {
834 q.remove();
835 it.next();
836 }
837 assertEquals(0, q.size());
838 }
839
840 /**
841 * toString contains toStrings of elements
842 */
843 public void testToString() {
844 ArrayBlockingQueue q = populatedQueue(SIZE);
845 String s = q.toString();
846 for (int i = 0; i < SIZE; ++i) {
847 assertTrue(s.contains(String.valueOf(i)));
848 }
849 }
850
851 /**
852 * offer transfers elements across Executor tasks
853 */
854 public void testOfferInExecutor() {
855 final ArrayBlockingQueue q = new ArrayBlockingQueue(2);
856 q.add(one);
857 q.add(two);
858 final CheckedBarrier threadsStarted = new CheckedBarrier(2);
859 final ExecutorService executor = Executors.newFixedThreadPool(2);
860 try (PoolCleaner cleaner = cleaner(executor)) {
861 executor.execute(new CheckedRunnable() {
862 public void realRun() throws InterruptedException {
863 assertFalse(q.offer(three));
864 threadsStarted.await();
865 assertTrue(q.offer(three, LONG_DELAY_MS, MILLISECONDS));
866 assertEquals(0, q.remainingCapacity());
867 }});
868
869 executor.execute(new CheckedRunnable() {
870 public void realRun() throws InterruptedException {
871 threadsStarted.await();
872 assertEquals(0, q.remainingCapacity());
873 assertSame(one, q.take());
874 }});
875 }
876 }
877
878 /**
879 * timed poll retrieves elements across Executor threads
880 */
881 public void testPollInExecutor() {
882 final ArrayBlockingQueue q = new ArrayBlockingQueue(2);
883 final CheckedBarrier threadsStarted = new CheckedBarrier(2);
884 final ExecutorService executor = Executors.newFixedThreadPool(2);
885 try (PoolCleaner cleaner = cleaner(executor)) {
886 executor.execute(new CheckedRunnable() {
887 public void realRun() throws InterruptedException {
888 assertNull(q.poll());
889 threadsStarted.await();
890 assertSame(one, q.poll(LONG_DELAY_MS, MILLISECONDS));
891 checkEmpty(q);
892 }});
893
894 executor.execute(new CheckedRunnable() {
895 public void realRun() throws InterruptedException {
896 threadsStarted.await();
897 q.put(one);
898 }});
899 }
900 }
901
902 /**
903 * A deserialized/reserialized queue has same elements in same order
904 */
905 public void testSerialization() throws Exception {
906 Queue x = populatedQueue(SIZE);
907 Queue y = serialClone(x);
908
909 assertNotSame(x, y);
910 assertEquals(x.size(), y.size());
911 assertEquals(x.toString(), y.toString());
912 assertTrue(Arrays.equals(x.toArray(), y.toArray()));
913 while (!x.isEmpty()) {
914 assertFalse(y.isEmpty());
915 assertEquals(x.remove(), y.remove());
916 }
917 assertTrue(y.isEmpty());
918 }
919
920 /**
921 * drainTo(c) empties queue into another collection c
922 */
923 public void testDrainTo() {
924 ArrayBlockingQueue q = populatedQueue(SIZE);
925 ArrayList l = new ArrayList();
926 q.drainTo(l);
927 assertEquals(0, q.size());
928 assertEquals(SIZE, l.size());
929 for (int i = 0; i < SIZE; ++i)
930 assertEquals(l.get(i), new Integer(i));
931 q.add(zero);
932 q.add(one);
933 assertFalse(q.isEmpty());
934 assertTrue(q.contains(zero));
935 assertTrue(q.contains(one));
936 l.clear();
937 q.drainTo(l);
938 assertEquals(0, q.size());
939 assertEquals(2, l.size());
940 for (int i = 0; i < 2; ++i)
941 assertEquals(l.get(i), new Integer(i));
942 }
943
944 /**
945 * drainTo empties full queue, unblocking a waiting put.
946 */
947 public void testDrainToWithActivePut() throws InterruptedException {
948 final ArrayBlockingQueue q = populatedQueue(SIZE);
949 Thread t = new Thread(new CheckedRunnable() {
950 public void realRun() throws InterruptedException {
951 q.put(new Integer(SIZE + 1));
952 }});
953
954 t.start();
955 ArrayList l = new ArrayList();
956 q.drainTo(l);
957 assertTrue(l.size() >= SIZE);
958 for (int i = 0; i < SIZE; ++i)
959 assertEquals(l.get(i), new Integer(i));
960 t.join();
961 assertTrue(q.size() + l.size() >= SIZE);
962 }
963
964 /**
965 * drainTo(c, n) empties first min(n, size) elements of queue into c
966 */
967 public void testDrainToN() {
968 ArrayBlockingQueue q = new ArrayBlockingQueue(SIZE * 2);
969 for (int i = 0; i < SIZE + 2; ++i) {
970 for (int j = 0; j < SIZE; j++)
971 assertTrue(q.offer(new Integer(j)));
972 ArrayList l = new ArrayList();
973 q.drainTo(l, i);
974 int k = (i < SIZE) ? i : SIZE;
975 assertEquals(k, l.size());
976 assertEquals(SIZE - k, q.size());
977 for (int j = 0; j < k; ++j)
978 assertEquals(l.get(j), new Integer(j));
979 do {} while (q.poll() != null);
980 }
981 }
982
983 /**
984 * remove(null), contains(null) always return false
985 */
986 public void testNeverContainsNull() {
987 Collection<?>[] qs = {
988 populatedQueue(0, 1, 10, false),
989 populatedQueue(2, 2, 10, true),
990 };
991
992 for (Collection<?> q : qs) {
993 assertFalse(q.contains(null));
994 assertFalse(q.remove(null));
995 }
996 }
997 }