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 }