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 java.util.Arrays;
37 import java.util.Collection;
38 import java.util.Iterator;
39 import java.util.NoSuchElementException;
40 import java.util.Queue;
41 import java.util.concurrent.ConcurrentLinkedQueue;
42
43 import junit.framework.Test;
44
45 public class ConcurrentLinkedQueueTest extends JSR166TestCase {
46
47 public static void main(String[] args) {
48 main(suite(), args);
49 }
50
51 public static Test suite() {
52 class Implementation implements CollectionImplementation {
53 public Class<?> klazz() { return ConcurrentLinkedQueue.class; }
54 public Collection emptyCollection() { return new ConcurrentLinkedQueue(); }
55 public Object makeElement(int i) { return i; }
56 public boolean isConcurrent() { return true; }
57 public boolean permitsNulls() { return false; }
58 }
59 return newTestSuite(ConcurrentLinkedQueueTest.class,
60 CollectionTest.testSuite(new Implementation()));
61 }
62
63 /**
64 * Returns a new queue of given size containing consecutive
65 * Integers 0 ... n - 1.
66 */
67 private static ConcurrentLinkedQueue<Integer> populatedQueue(int n) {
68 ConcurrentLinkedQueue<Integer> q = new ConcurrentLinkedQueue<>();
69 assertTrue(q.isEmpty());
70 for (int i = 0; i < n; ++i)
71 assertTrue(q.offer(new Integer(i)));
72 assertFalse(q.isEmpty());
73 assertEquals(n, q.size());
74 assertEquals((Integer) 0, q.peek());
75 return q;
76 }
77
78 /**
79 * new queue is empty
80 */
81 public void testConstructor1() {
82 assertEquals(0, new ConcurrentLinkedQueue().size());
83 }
84
85 /**
86 * Initializing from null Collection throws NPE
87 */
88 public void testConstructor3() {
89 try {
90 new ConcurrentLinkedQueue((Collection)null);
91 shouldThrow();
92 } catch (NullPointerException success) {}
93 }
94
95 /**
96 * Initializing from Collection of null elements throws NPE
97 */
98 public void testConstructor4() {
99 try {
100 new ConcurrentLinkedQueue(Arrays.asList(new Integer[SIZE]));
101 shouldThrow();
102 } catch (NullPointerException success) {}
103 }
104
105 /**
106 * Initializing from Collection with some null elements throws NPE
107 */
108 public void testConstructor5() {
109 Integer[] ints = new Integer[SIZE];
110 for (int i = 0; i < SIZE - 1; ++i)
111 ints[i] = new Integer(i);
112 try {
113 new ConcurrentLinkedQueue(Arrays.asList(ints));
114 shouldThrow();
115 } catch (NullPointerException success) {}
116 }
117
118 /**
119 * Queue contains all elements of collection used to initialize
120 */
121 public void testConstructor6() {
122 Integer[] ints = new Integer[SIZE];
123 for (int i = 0; i < SIZE; ++i)
124 ints[i] = new Integer(i);
125 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue(Arrays.asList(ints));
126 for (int i = 0; i < SIZE; ++i)
127 assertEquals(ints[i], q.poll());
128 }
129
130 /**
131 * isEmpty is true before add, false after
132 */
133 public void testEmpty() {
134 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
135 assertTrue(q.isEmpty());
136 q.add(one);
137 assertFalse(q.isEmpty());
138 q.add(two);
139 q.remove();
140 q.remove();
141 assertTrue(q.isEmpty());
142 }
143
144 /**
145 * size changes when elements added and removed
146 */
147 public void testSize() {
148 ConcurrentLinkedQueue q = populatedQueue(SIZE);
149 for (int i = 0; i < SIZE; ++i) {
150 assertEquals(SIZE - i, q.size());
151 q.remove();
152 }
153 for (int i = 0; i < SIZE; ++i) {
154 assertEquals(i, q.size());
155 q.add(new Integer(i));
156 }
157 }
158
159 /**
160 * offer(null) throws NPE
161 */
162 public void testOfferNull() {
163 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
164 try {
165 q.offer(null);
166 shouldThrow();
167 } catch (NullPointerException success) {}
168 }
169
170 /**
171 * add(null) throws NPE
172 */
173 public void testAddNull() {
174 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
175 try {
176 q.add(null);
177 shouldThrow();
178 } catch (NullPointerException success) {}
179 }
180
181 /**
182 * Offer returns true
183 */
184 public void testOffer() {
185 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
186 assertTrue(q.offer(zero));
187 assertTrue(q.offer(one));
188 }
189
190 /**
191 * add returns true
192 */
193 public void testAdd() {
194 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
195 for (int i = 0; i < SIZE; ++i) {
196 assertEquals(i, q.size());
197 assertTrue(q.add(new Integer(i)));
198 }
199 }
200
201 /**
202 * addAll(null) throws NullPointerException
203 */
204 public void testAddAll1() {
205 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
206 try {
207 q.addAll(null);
208 shouldThrow();
209 } catch (NullPointerException success) {}
210 }
211
212 /**
213 * addAll(this) throws IllegalArgumentException
214 */
215 public void testAddAllSelf() {
216 ConcurrentLinkedQueue q = populatedQueue(SIZE);
217 try {
218 q.addAll(q);
219 shouldThrow();
220 } catch (IllegalArgumentException success) {}
221 }
222
223 /**
224 * addAll of a collection with null elements throws NullPointerException
225 */
226 public void testAddAll2() {
227 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
228 try {
229 q.addAll(Arrays.asList(new Integer[SIZE]));
230 shouldThrow();
231 } catch (NullPointerException success) {}
232 }
233
234 /**
235 * addAll of a collection with any null elements throws NPE after
236 * possibly adding some elements
237 */
238 public void testAddAll3() {
239 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
240 Integer[] ints = new Integer[SIZE];
241 for (int i = 0; i < SIZE - 1; ++i)
242 ints[i] = new Integer(i);
243 try {
244 q.addAll(Arrays.asList(ints));
245 shouldThrow();
246 } catch (NullPointerException success) {}
247 }
248
249 /**
250 * Queue contains all elements, in traversal order, of successful addAll
251 */
252 public void testAddAll5() {
253 Integer[] empty = new Integer[0];
254 Integer[] ints = new Integer[SIZE];
255 for (int i = 0; i < SIZE; ++i)
256 ints[i] = new Integer(i);
257 ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
258 assertFalse(q.addAll(Arrays.asList(empty)));
259 assertTrue(q.addAll(Arrays.asList(ints)));
260 for (int i = 0; i < SIZE; ++i)
261 assertEquals(ints[i], q.poll());
262 }
263
264 /**
265 * poll succeeds unless empty
266 */
267 public void testPoll() {
268 ConcurrentLinkedQueue q = populatedQueue(SIZE);
269 for (int i = 0; i < SIZE; ++i) {
270 assertEquals(i, q.poll());
271 }
272 assertNull(q.poll());
273 }
274
275 /**
276 * peek returns next element, or null if empty
277 */
278 public void testPeek() {
279 ConcurrentLinkedQueue q = populatedQueue(SIZE);
280 for (int i = 0; i < SIZE; ++i) {
281 assertEquals(i, q.peek());
282 assertEquals(i, q.poll());
283 assertTrue(q.peek() == null ||
284 !q.peek().equals(i));
285 }
286 assertNull(q.peek());
287 }
288
289 /**
290 * element returns next element, or throws NSEE if empty
291 */
292 public void testElement() {
293 ConcurrentLinkedQueue q = populatedQueue(SIZE);
294 for (int i = 0; i < SIZE; ++i) {
295 assertEquals(i, q.element());
296 assertEquals(i, q.poll());
297 }
298 try {
299 q.element();
300 shouldThrow();
301 } catch (NoSuchElementException success) {}
302 }
303
304 /**
305 * remove removes next element, or throws NSEE if empty
306 */
307 public void testRemove() {
308 ConcurrentLinkedQueue q = populatedQueue(SIZE);
309 for (int i = 0; i < SIZE; ++i) {
310 assertEquals(i, q.remove());
311 }
312 try {
313 q.remove();
314 shouldThrow();
315 } catch (NoSuchElementException success) {}
316 }
317
318 /**
319 * remove(x) removes x and returns true if present
320 */
321 public void testRemoveElement() {
322 ConcurrentLinkedQueue q = populatedQueue(SIZE);
323 for (int i = 1; i < SIZE; i += 2) {
324 assertTrue(q.contains(i));
325 assertTrue(q.remove(i));
326 assertFalse(q.contains(i));
327 assertTrue(q.contains(i - 1));
328 }
329 for (int i = 0; i < SIZE; i += 2) {
330 assertTrue(q.contains(i));
331 assertTrue(q.remove(i));
332 assertFalse(q.contains(i));
333 assertFalse(q.remove(i + 1));
334 assertFalse(q.contains(i + 1));
335 }
336 assertTrue(q.isEmpty());
337 }
338
339 /**
340 * contains(x) reports true when elements added but not yet removed
341 */
342 public void testContains() {
343 ConcurrentLinkedQueue q = populatedQueue(SIZE);
344 for (int i = 0; i < SIZE; ++i) {
345 assertTrue(q.contains(new Integer(i)));
346 q.poll();
347 assertFalse(q.contains(new Integer(i)));
348 }
349 }
350
351 /**
352 * clear removes all elements
353 */
354 public void testClear() {
355 ConcurrentLinkedQueue q = populatedQueue(SIZE);
356 q.clear();
357 assertTrue(q.isEmpty());
358 assertEquals(0, q.size());
359 q.add(one);
360 assertFalse(q.isEmpty());
361 q.clear();
362 assertTrue(q.isEmpty());
363 }
364
365 /**
366 * containsAll(c) is true when c contains a subset of elements
367 */
368 public void testContainsAll() {
369 ConcurrentLinkedQueue q = populatedQueue(SIZE);
370 ConcurrentLinkedQueue p = new ConcurrentLinkedQueue();
371 for (int i = 0; i < SIZE; ++i) {
372 assertTrue(q.containsAll(p));
373 assertFalse(p.containsAll(q));
374 p.add(new Integer(i));
375 }
376 assertTrue(p.containsAll(q));
377 }
378
379 /**
380 * retainAll(c) retains only those elements of c and reports true if change
381 */
382 public void testRetainAll() {
383 ConcurrentLinkedQueue q = populatedQueue(SIZE);
384 ConcurrentLinkedQueue p = populatedQueue(SIZE);
385 for (int i = 0; i < SIZE; ++i) {
386 boolean changed = q.retainAll(p);
387 if (i == 0)
388 assertFalse(changed);
389 else
390 assertTrue(changed);
391
392 assertTrue(q.containsAll(p));
393 assertEquals(SIZE - i, q.size());
394 p.remove();
395 }
396 }
397
398 /**
399 * removeAll(c) removes only those elements of c and reports true if changed
400 */
401 public void testRemoveAll() {
402 for (int i = 1; i < SIZE; ++i) {
403 ConcurrentLinkedQueue q = populatedQueue(SIZE);
404 ConcurrentLinkedQueue p = populatedQueue(i);
405 assertTrue(q.removeAll(p));
406 assertEquals(SIZE - i, q.size());
407 for (int j = 0; j < i; ++j) {
408 Integer x = (Integer)(p.remove());
409 assertFalse(q.contains(x));
410 }
411 }
412 }
413
414 /**
415 * toArray contains all elements in FIFO order
416 */
417 public void testToArray() {
418 ConcurrentLinkedQueue q = populatedQueue(SIZE);
419 Object[] o = q.toArray();
420 for (int i = 0; i < o.length; i++)
421 assertSame(o[i], q.poll());
422 }
423
424 /**
425 * toArray(a) contains all elements in FIFO order
426 */
427 public void testToArray2() {
428 ConcurrentLinkedQueue<Integer> q = populatedQueue(SIZE);
429 Integer[] ints = new Integer[SIZE];
430 Integer[] array = q.toArray(ints);
431 assertSame(ints, array);
432 for (int i = 0; i < ints.length; i++)
433 assertSame(ints[i], q.poll());
434 }
435
436 /**
437 * toArray(null) throws NullPointerException
438 */
439 public void testToArray_NullArg() {
440 ConcurrentLinkedQueue q = populatedQueue(SIZE);
441 try {
442 q.toArray(null);
443 shouldThrow();
444 } catch (NullPointerException success) {}
445 }
446
447 /**
448 * toArray(incompatible array type) throws ArrayStoreException
449 */
450 public void testToArray1_BadArg() {
451 ConcurrentLinkedQueue q = populatedQueue(SIZE);
452 try {
453 q.toArray(new String[10]);
454 shouldThrow();
455 } catch (ArrayStoreException success) {}
456 }
457
458 /**
459 * iterator iterates through all elements
460 */
461 public void testIterator() {
462 ConcurrentLinkedQueue q = populatedQueue(SIZE);
463 Iterator it = q.iterator();
464 int i;
465 for (i = 0; it.hasNext(); i++)
466 assertTrue(q.contains(it.next()));
467 assertEquals(i, SIZE);
468 assertIteratorExhausted(it);
469 }
470
471 /**
472 * iterator of empty collection has no elements
473 */
474 public void testEmptyIterator() {
475 assertIteratorExhausted(new ConcurrentLinkedQueue().iterator());
476 }
477
478 /**
479 * iterator ordering is FIFO
480 */
481 public void testIteratorOrdering() {
482 final ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
483 q.add(one);
484 q.add(two);
485 q.add(three);
486
487 int k = 0;
488 for (Iterator it = q.iterator(); it.hasNext();) {
489 assertEquals(++k, it.next());
490 }
491
492 assertEquals(3, k);
493 }
494
495 /**
496 * Modifications do not cause iterators to fail
497 */
498 public void testWeaklyConsistentIteration() {
499 final ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
500 q.add(one);
501 q.add(two);
502 q.add(three);
503
504 for (Iterator it = q.iterator(); it.hasNext();) {
505 q.remove();
506 it.next();
507 }
508
509 assertEquals("queue should be empty again", 0, q.size());
510 }
511
512 /**
513 * iterator.remove removes current element
514 */
515 public void testIteratorRemove() {
516 final ConcurrentLinkedQueue q = new ConcurrentLinkedQueue();
517 q.add(one);
518 q.add(two);
519 q.add(three);
520 Iterator it = q.iterator();
521 it.next();
522 it.remove();
523 it = q.iterator();
524 assertSame(it.next(), two);
525 assertSame(it.next(), three);
526 assertFalse(it.hasNext());
527 }
528
529 /**
530 * toString contains toStrings of elements
531 */
532 public void testToString() {
533 ConcurrentLinkedQueue q = populatedQueue(SIZE);
534 String s = q.toString();
535 for (int i = 0; i < SIZE; ++i) {
536 assertTrue(s.contains(String.valueOf(i)));
537 }
538 }
539
540 /**
541 * A deserialized/reserialized queue has same elements in same order
542 */
543 public void testSerialization() throws Exception {
544 Queue x = populatedQueue(SIZE);
545 Queue y = serialClone(x);
546
547 assertNotSame(x, y);
548 assertEquals(x.size(), y.size());
549 assertEquals(x.toString(), y.toString());
550 assertTrue(Arrays.equals(x.toArray(), y.toArray()));
551 while (!x.isEmpty()) {
552 assertFalse(y.isEmpty());
553 assertEquals(x.remove(), y.remove());
554 }
555 assertTrue(y.isEmpty());
556 }
557
558 /**
559 * remove(null), contains(null) always return false
560 */
561 public void testNeverContainsNull() {
562 Collection<?>[] qs = {
563 new ConcurrentLinkedQueue<Object>(),
564 populatedQueue(2),
565 };
566
567 for (Collection<?> q : qs) {
568 assertFalse(q.contains(null));
569 assertFalse(q.remove(null));
570 }
571 }
572 }