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.Deque; 39 import java.util.Iterator; 40 import java.util.NoSuchElementException; 41 import java.util.Queue; 42 import java.util.Random; 43 import java.util.concurrent.CompletableFuture; 44 import java.util.concurrent.ConcurrentLinkedDeque; 45 import java.util.concurrent.ThreadLocalRandom; 46 import java.util.concurrent.atomic.LongAdder; 47 48 import junit.framework.Test; 49 50 public class ConcurrentLinkedDequeTest extends JSR166TestCase { 51 52 public static void main(String[] args) { 53 main(suite(), args); 54 } 55 56 public static Test suite() { 57 class Implementation implements CollectionImplementation { 58 public Class<?> klazz() { return ConcurrentLinkedDeque.class; } 59 public Collection emptyCollection() { return new ConcurrentLinkedDeque(); } 60 public Object makeElement(int i) { return i; } 61 public boolean isConcurrent() { return true; } 62 public boolean permitsNulls() { return false; } 63 } 64 return newTestSuite(ConcurrentLinkedDequeTest.class, 65 CollectionTest.testSuite(new Implementation())); 66 } 67 68 /** 69 * Returns a new deque of given size containing consecutive 70 * Integers 0 ... n - 1. 71 */ 72 private static ConcurrentLinkedDeque<Integer> populatedDeque(int n) { 73 ConcurrentLinkedDeque<Integer> q = new ConcurrentLinkedDeque<>(); 74 assertTrue(q.isEmpty()); 75 for (int i = 0; i < n; ++i) 76 assertTrue(q.offer(new Integer(i))); 77 assertFalse(q.isEmpty()); 78 assertEquals(n, q.size()); 79 assertEquals((Integer) 0, q.peekFirst()); 80 assertEquals((Integer) (n - 1), q.peekLast()); 81 return q; 82 } 83 84 /** 85 * new deque is empty 86 */ 87 public void testConstructor1() { 88 assertTrue(new ConcurrentLinkedDeque().isEmpty()); 89 assertEquals(0, new ConcurrentLinkedDeque().size()); 90 } 91 92 /** 93 * Initializing from null Collection throws NPE 94 */ 95 public void testConstructor3() { 96 try { 97 new ConcurrentLinkedDeque((Collection)null); 98 shouldThrow(); 99 } catch (NullPointerException success) {} 100 } 101 102 /** 103 * Initializing from Collection of null elements throws NPE 104 */ 105 public void testConstructor4() { 106 try { 107 new ConcurrentLinkedDeque(Arrays.asList(new Integer[SIZE])); 108 shouldThrow(); 109 } catch (NullPointerException success) {} 110 } 111 112 /** 113 * Initializing from Collection with some null elements throws NPE 114 */ 115 public void testConstructor5() { 116 Integer[] ints = new Integer[SIZE]; 117 for (int i = 0; i < SIZE - 1; ++i) 118 ints[i] = new Integer(i); 119 try { 120 new ConcurrentLinkedDeque(Arrays.asList(ints)); 121 shouldThrow(); 122 } catch (NullPointerException success) {} 123 } 124 125 /** 126 * Deque contains all elements of collection used to initialize 127 */ 128 public void testConstructor6() { 129 Integer[] ints = new Integer[SIZE]; 130 for (int i = 0; i < SIZE; ++i) 131 ints[i] = new Integer(i); 132 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(Arrays.asList(ints)); 133 for (int i = 0; i < SIZE; ++i) 134 assertEquals(ints[i], q.poll()); 135 } 136 137 /** 138 * isEmpty is true before add, false after 139 */ 140 public void testEmpty() { 141 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 142 assertTrue(q.isEmpty()); 143 q.add(one); 144 assertFalse(q.isEmpty()); 145 q.add(two); 146 q.remove(); 147 q.remove(); 148 assertTrue(q.isEmpty()); 149 } 150 151 /** 152 * size() changes when elements added and removed 153 */ 154 public void testSize() { 155 ConcurrentLinkedDeque q = populatedDeque(SIZE); 156 for (int i = 0; i < SIZE; ++i) { 157 assertEquals(SIZE - i, q.size()); 158 q.remove(); 159 } 160 for (int i = 0; i < SIZE; ++i) { 161 assertEquals(i, q.size()); 162 q.add(new Integer(i)); 163 } 164 } 165 166 /** 167 * push(null) throws NPE 168 */ 169 public void testPushNull() { 170 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 171 try { 172 q.push(null); 173 shouldThrow(); 174 } catch (NullPointerException success) {} 175 } 176 177 /** 178 * peekFirst() returns element inserted with push 179 */ 180 public void testPush() { 181 ConcurrentLinkedDeque q = populatedDeque(3); 182 q.pollLast(); 183 q.push(four); 184 assertSame(four, q.peekFirst()); 185 } 186 187 /** 188 * pop() removes first element, or throws NSEE if empty 189 */ 190 public void testPop() { 191 ConcurrentLinkedDeque q = populatedDeque(SIZE); 192 for (int i = 0; i < SIZE; ++i) { 193 assertEquals(i, q.pop()); 194 } 195 try { 196 q.pop(); 197 shouldThrow(); 198 } catch (NoSuchElementException success) {} 199 } 200 201 /** 202 * offer(null) throws NPE 203 */ 204 public void testOfferNull() { 205 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 206 try { 207 q.offer(null); 208 shouldThrow(); 209 } catch (NullPointerException success) {} 210 } 211 212 /** 213 * offerFirst(null) throws NPE 214 */ 215 public void testOfferFirstNull() { 216 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 217 try { 218 q.offerFirst(null); 219 shouldThrow(); 220 } catch (NullPointerException success) {} 221 } 222 223 /** 224 * offerLast(null) throws NPE 225 */ 226 public void testOfferLastNull() { 227 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 228 try { 229 q.offerLast(null); 230 shouldThrow(); 231 } catch (NullPointerException success) {} 232 } 233 234 /** 235 * offer(x) succeeds 236 */ 237 public void testOffer() { 238 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 239 assertTrue(q.offer(zero)); 240 assertTrue(q.offer(one)); 241 assertSame(zero, q.peekFirst()); 242 assertSame(one, q.peekLast()); 243 } 244 245 /** 246 * offerFirst(x) succeeds 247 */ 248 public void testOfferFirst() { 249 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 250 assertTrue(q.offerFirst(zero)); 251 assertTrue(q.offerFirst(one)); 252 assertSame(one, q.peekFirst()); 253 assertSame(zero, q.peekLast()); 254 } 255 256 /** 257 * offerLast(x) succeeds 258 */ 259 public void testOfferLast() { 260 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 261 assertTrue(q.offerLast(zero)); 262 assertTrue(q.offerLast(one)); 263 assertSame(zero, q.peekFirst()); 264 assertSame(one, q.peekLast()); 265 } 266 267 /** 268 * add(null) throws NPE 269 */ 270 public void testAddNull() { 271 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 272 try { 273 q.add(null); 274 shouldThrow(); 275 } catch (NullPointerException success) {} 276 } 277 278 /** 279 * addFirst(null) throws NPE 280 */ 281 public void testAddFirstNull() { 282 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 283 try { 284 q.addFirst(null); 285 shouldThrow(); 286 } catch (NullPointerException success) {} 287 } 288 289 /** 290 * addLast(null) throws NPE 291 */ 292 public void testAddLastNull() { 293 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 294 try { 295 q.addLast(null); 296 shouldThrow(); 297 } catch (NullPointerException success) {} 298 } 299 300 /** 301 * add(x) succeeds 302 */ 303 public void testAdd() { 304 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 305 assertTrue(q.add(zero)); 306 assertTrue(q.add(one)); 307 assertSame(zero, q.peekFirst()); 308 assertSame(one, q.peekLast()); 309 } 310 311 /** 312 * addFirst(x) succeeds 313 */ 314 public void testAddFirst() { 315 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 316 q.addFirst(zero); 317 q.addFirst(one); 318 assertSame(one, q.peekFirst()); 319 assertSame(zero, q.peekLast()); 320 } 321 322 /** 323 * addLast(x) succeeds 324 */ 325 public void testAddLast() { 326 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 327 q.addLast(zero); 328 q.addLast(one); 329 assertSame(zero, q.peekFirst()); 330 assertSame(one, q.peekLast()); 331 } 332 333 /** 334 * addAll(null) throws NPE 335 */ 336 public void testAddAll1() { 337 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 338 try { 339 q.addAll(null); 340 shouldThrow(); 341 } catch (NullPointerException success) {} 342 } 343 344 /** 345 * addAll(this) throws IllegalArgumentException 346 */ 347 public void testAddAllSelf() { 348 ConcurrentLinkedDeque q = populatedDeque(SIZE); 349 try { 350 q.addAll(q); 351 shouldThrow(); 352 } catch (IllegalArgumentException success) {} 353 } 354 355 /** 356 * addAll of a collection with null elements throws NPE 357 */ 358 public void testAddAll2() { 359 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 360 try { 361 q.addAll(Arrays.asList(new Integer[SIZE])); 362 shouldThrow(); 363 } catch (NullPointerException success) {} 364 } 365 366 /** 367 * addAll of a collection with any null elements throws NPE after 368 * possibly adding some elements 369 */ 370 public void testAddAll3() { 371 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 372 Integer[] ints = new Integer[SIZE]; 373 for (int i = 0; i < SIZE - 1; ++i) 374 ints[i] = new Integer(i); 375 try { 376 q.addAll(Arrays.asList(ints)); 377 shouldThrow(); 378 } catch (NullPointerException success) {} 379 } 380 381 /** 382 * Deque contains all elements, in traversal order, of successful addAll 383 */ 384 public void testAddAll5() { 385 Integer[] empty = new Integer[0]; 386 Integer[] ints = new Integer[SIZE]; 387 for (int i = 0; i < SIZE; ++i) 388 ints[i] = new Integer(i); 389 ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 390 assertFalse(q.addAll(Arrays.asList(empty))); 391 assertTrue(q.addAll(Arrays.asList(ints))); 392 for (int i = 0; i < SIZE; ++i) 393 assertEquals(ints[i], q.poll()); 394 } 395 396 /** 397 * pollFirst() succeeds unless empty 398 */ 399 public void testPollFirst() { 400 ConcurrentLinkedDeque q = populatedDeque(SIZE); 401 for (int i = 0; i < SIZE; ++i) { 402 assertEquals(i, q.pollFirst()); 403 } 404 assertNull(q.pollFirst()); 405 } 406 407 /** 408 * pollLast() succeeds unless empty 409 */ 410 public void testPollLast() { 411 ConcurrentLinkedDeque q = populatedDeque(SIZE); 412 for (int i = SIZE - 1; i >= 0; --i) { 413 assertEquals(i, q.pollLast()); 414 } 415 assertNull(q.pollLast()); 416 } 417 418 /** 419 * poll() succeeds unless empty 420 */ 421 public void testPoll() { 422 ConcurrentLinkedDeque q = populatedDeque(SIZE); 423 for (int i = 0; i < SIZE; ++i) { 424 assertEquals(i, q.poll()); 425 } 426 assertNull(q.poll()); 427 } 428 429 /** 430 * peek() returns next element, or null if empty 431 */ 432 public void testPeek() { 433 ConcurrentLinkedDeque q = populatedDeque(SIZE); 434 for (int i = 0; i < SIZE; ++i) { 435 assertEquals(i, q.peek()); 436 assertEquals(i, q.poll()); 437 assertTrue(q.peek() == null || 438 !q.peek().equals(i)); 439 } 440 assertNull(q.peek()); 441 } 442 443 /** 444 * element() returns first element, or throws NSEE if empty 445 */ 446 public void testElement() { 447 ConcurrentLinkedDeque q = populatedDeque(SIZE); 448 for (int i = 0; i < SIZE; ++i) { 449 assertEquals(i, q.element()); 450 assertEquals(i, q.poll()); 451 } 452 try { 453 q.element(); 454 shouldThrow(); 455 } catch (NoSuchElementException success) {} 456 } 457 458 /** 459 * remove() removes next element, or throws NSEE if empty 460 */ 461 public void testRemove() { 462 ConcurrentLinkedDeque q = populatedDeque(SIZE); 463 for (int i = 0; i < SIZE; ++i) { 464 assertEquals(i, q.remove()); 465 } 466 try { 467 q.remove(); 468 shouldThrow(); 469 } catch (NoSuchElementException success) {} 470 } 471 472 /** 473 * remove(x) removes x and returns true if present 474 */ 475 public void testRemoveElement() { 476 ConcurrentLinkedDeque q = populatedDeque(SIZE); 477 for (int i = 1; i < SIZE; i += 2) { 478 assertTrue(q.contains(i)); 479 assertTrue(q.remove(i)); 480 assertFalse(q.contains(i)); 481 assertTrue(q.contains(i - 1)); 482 } 483 for (int i = 0; i < SIZE; i += 2) { 484 assertTrue(q.contains(i)); 485 assertTrue(q.remove(i)); 486 assertFalse(q.contains(i)); 487 assertFalse(q.remove(i + 1)); 488 assertFalse(q.contains(i + 1)); 489 } 490 assertTrue(q.isEmpty()); 491 } 492 493 /** 494 * peekFirst() returns next element, or null if empty 495 */ 496 public void testPeekFirst() { 497 ConcurrentLinkedDeque q = populatedDeque(SIZE); 498 for (int i = 0; i < SIZE; ++i) { 499 assertEquals(i, q.peekFirst()); 500 assertEquals(i, q.pollFirst()); 501 assertTrue(q.peekFirst() == null || 502 !q.peekFirst().equals(i)); 503 } 504 assertNull(q.peekFirst()); 505 } 506 507 /** 508 * peekLast() returns next element, or null if empty 509 */ 510 public void testPeekLast() { 511 ConcurrentLinkedDeque q = populatedDeque(SIZE); 512 for (int i = SIZE - 1; i >= 0; --i) { 513 assertEquals(i, q.peekLast()); 514 assertEquals(i, q.pollLast()); 515 assertTrue(q.peekLast() == null || 516 !q.peekLast().equals(i)); 517 } 518 assertNull(q.peekLast()); 519 } 520 521 /** 522 * getFirst() returns first element, or throws NSEE if empty 523 */ 524 public void testFirstElement() { 525 ConcurrentLinkedDeque q = populatedDeque(SIZE); 526 for (int i = 0; i < SIZE; ++i) { 527 assertEquals(i, q.getFirst()); 528 assertEquals(i, q.pollFirst()); 529 } 530 try { 531 q.getFirst(); 532 shouldThrow(); 533 } catch (NoSuchElementException success) {} 534 } 535 536 /** 537 * getLast() returns last element, or throws NSEE if empty 538 */ 539 public void testLastElement() { 540 ConcurrentLinkedDeque q = populatedDeque(SIZE); 541 for (int i = SIZE - 1; i >= 0; --i) { 542 assertEquals(i, q.getLast()); 543 assertEquals(i, q.pollLast()); 544 } 545 try { 546 q.getLast(); 547 shouldThrow(); 548 } catch (NoSuchElementException success) {} 549 assertNull(q.peekLast()); 550 } 551 552 /** 553 * removeFirst() removes first element, or throws NSEE if empty 554 */ 555 public void testRemoveFirst() { 556 ConcurrentLinkedDeque q = populatedDeque(SIZE); 557 for (int i = 0; i < SIZE; ++i) { 558 assertEquals(i, q.removeFirst()); 559 } 560 try { 561 q.removeFirst(); 562 shouldThrow(); 563 } catch (NoSuchElementException success) {} 564 assertNull(q.peekFirst()); 565 } 566 567 /** 568 * removeLast() removes last element, or throws NSEE if empty 569 */ 570 public void testRemoveLast() { 571 ConcurrentLinkedDeque q = populatedDeque(SIZE); 572 for (int i = SIZE - 1; i >= 0; --i) { 573 assertEquals(i, q.removeLast()); 574 } 575 try { 576 q.removeLast(); 577 shouldThrow(); 578 } catch (NoSuchElementException success) {} 579 assertNull(q.peekLast()); 580 } 581 582 /** 583 * removeFirstOccurrence(x) removes x and returns true if present 584 */ 585 public void testRemoveFirstOccurrence() { 586 ConcurrentLinkedDeque q = populatedDeque(SIZE); 587 for (int i = 1; i < SIZE; i += 2) { 588 assertTrue(q.removeFirstOccurrence(new Integer(i))); 589 } 590 for (int i = 0; i < SIZE; i += 2) { 591 assertTrue(q.removeFirstOccurrence(new Integer(i))); 592 assertFalse(q.removeFirstOccurrence(new Integer(i + 1))); 593 } 594 assertTrue(q.isEmpty()); 595 } 596 597 /** 598 * removeLastOccurrence(x) removes x and returns true if present 599 */ 600 public void testRemoveLastOccurrence() { 601 ConcurrentLinkedDeque q = populatedDeque(SIZE); 602 for (int i = 1; i < SIZE; i += 2) { 603 assertTrue(q.removeLastOccurrence(new Integer(i))); 604 } 605 for (int i = 0; i < SIZE; i += 2) { 606 assertTrue(q.removeLastOccurrence(new Integer(i))); 607 assertFalse(q.removeLastOccurrence(new Integer(i + 1))); 608 } 609 assertTrue(q.isEmpty()); 610 } 611 612 /** 613 * contains(x) reports true when elements added but not yet removed 614 */ 615 public void testContains() { 616 ConcurrentLinkedDeque q = populatedDeque(SIZE); 617 for (int i = 0; i < SIZE; ++i) { 618 assertTrue(q.contains(new Integer(i))); 619 q.poll(); 620 assertFalse(q.contains(new Integer(i))); 621 } 622 } 623 624 /** 625 * clear() removes all elements 626 */ 627 public void testClear() { 628 ConcurrentLinkedDeque q = populatedDeque(SIZE); 629 q.clear(); 630 assertTrue(q.isEmpty()); 631 assertEquals(0, q.size()); 632 q.add(one); 633 assertFalse(q.isEmpty()); 634 q.clear(); 635 assertTrue(q.isEmpty()); 636 } 637 638 /** 639 * containsAll(c) is true when c contains a subset of elements 640 */ 641 public void testContainsAll() { 642 ConcurrentLinkedDeque q = populatedDeque(SIZE); 643 ConcurrentLinkedDeque p = new ConcurrentLinkedDeque(); 644 for (int i = 0; i < SIZE; ++i) { 645 assertTrue(q.containsAll(p)); 646 assertFalse(p.containsAll(q)); 647 p.add(new Integer(i)); 648 } 649 assertTrue(p.containsAll(q)); 650 } 651 652 /** 653 * retainAll(c) retains only those elements of c and reports true if change 654 */ 655 public void testRetainAll() { 656 ConcurrentLinkedDeque q = populatedDeque(SIZE); 657 ConcurrentLinkedDeque p = populatedDeque(SIZE); 658 for (int i = 0; i < SIZE; ++i) { 659 boolean changed = q.retainAll(p); 660 if (i == 0) 661 assertFalse(changed); 662 else 663 assertTrue(changed); 664 665 assertTrue(q.containsAll(p)); 666 assertEquals(SIZE - i, q.size()); 667 p.remove(); 668 } 669 } 670 671 /** 672 * removeAll(c) removes only those elements of c and reports true if changed 673 */ 674 public void testRemoveAll() { 675 for (int i = 1; i < SIZE; ++i) { 676 ConcurrentLinkedDeque q = populatedDeque(SIZE); 677 ConcurrentLinkedDeque p = populatedDeque(i); 678 assertTrue(q.removeAll(p)); 679 assertEquals(SIZE - i, q.size()); 680 for (int j = 0; j < i; ++j) { 681 Integer x = (Integer)(p.remove()); 682 assertFalse(q.contains(x)); 683 } 684 } 685 } 686 687 /** 688 * toArray() contains all elements in FIFO order 689 */ 690 public void testToArray() { 691 ConcurrentLinkedDeque q = populatedDeque(SIZE); 692 Object[] a = q.toArray(); 693 assertSame(Object[].class, a.getClass()); 694 for (Object o : a) 695 assertSame(o, q.poll()); 696 assertTrue(q.isEmpty()); 697 } 698 699 /** 700 * toArray(a) contains all elements in FIFO order 701 */ 702 public void testToArray2() { 703 ConcurrentLinkedDeque<Integer> q = populatedDeque(SIZE); 704 Integer[] ints = new Integer[SIZE]; 705 Integer[] array = q.toArray(ints); 706 assertSame(ints, array); 707 for (Integer o : ints) 708 assertSame(o, q.poll()); 709 assertTrue(q.isEmpty()); 710 } 711 712 /** 713 * toArray(null) throws NullPointerException 714 */ 715 public void testToArray_NullArg() { 716 ConcurrentLinkedDeque q = populatedDeque(SIZE); 717 try { 718 q.toArray((Object[])null); 719 shouldThrow(); 720 } catch (NullPointerException success) {} 721 } 722 723 /** 724 * toArray(incompatible array type) throws ArrayStoreException 725 */ 726 public void testToArray1_BadArg() { 727 ConcurrentLinkedDeque q = populatedDeque(SIZE); 728 try { 729 q.toArray(new String[10]); 730 shouldThrow(); 731 } catch (ArrayStoreException success) {} 732 } 733 734 /** 735 * Iterator iterates through all elements 736 */ 737 public void testIterator() { 738 ConcurrentLinkedDeque q = populatedDeque(SIZE); 739 Iterator it = q.iterator(); 740 int i; 741 for (i = 0; it.hasNext(); i++) 742 assertTrue(q.contains(it.next())); 743 assertEquals(i, SIZE); 744 assertIteratorExhausted(it); 745 } 746 747 /** 748 * iterator of empty collection has no elements 749 */ 750 public void testEmptyIterator() { 751 Deque c = new ConcurrentLinkedDeque(); 752 assertIteratorExhausted(c.iterator()); 753 assertIteratorExhausted(c.descendingIterator()); 754 } 755 756 /** 757 * Iterator ordering is FIFO 758 */ 759 public void testIteratorOrdering() { 760 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 761 q.add(one); 762 q.add(two); 763 q.add(three); 764 765 int k = 0; 766 for (Iterator it = q.iterator(); it.hasNext();) { 767 assertEquals(++k, it.next()); 768 } 769 770 assertEquals(3, k); 771 } 772 773 /** 774 * Modifications do not cause iterators to fail 775 */ 776 public void testWeaklyConsistentIteration() { 777 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 778 q.add(one); 779 q.add(two); 780 q.add(three); 781 782 for (Iterator it = q.iterator(); it.hasNext();) { 783 q.remove(); 784 it.next(); 785 } 786 787 assertEquals("deque should be empty again", 0, q.size()); 788 } 789 790 /** 791 * iterator.remove() removes current element 792 */ 793 public void testIteratorRemove() { 794 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 795 final Random rng = new Random(); 796 for (int iters = 0; iters < 100; ++iters) { 797 int max = rng.nextInt(5) + 2; 798 int split = rng.nextInt(max - 1) + 1; 799 for (int j = 1; j <= max; ++j) 800 q.add(new Integer(j)); 801 Iterator it = q.iterator(); 802 for (int j = 1; j <= split; ++j) 803 assertEquals(it.next(), new Integer(j)); 804 it.remove(); 805 assertEquals(it.next(), new Integer(split + 1)); 806 for (int j = 1; j <= split; ++j) 807 q.remove(new Integer(j)); 808 it = q.iterator(); 809 for (int j = split + 1; j <= max; ++j) { 810 assertEquals(it.next(), new Integer(j)); 811 it.remove(); 812 } 813 assertFalse(it.hasNext()); 814 assertTrue(q.isEmpty()); 815 } 816 } 817 818 /** 819 * Descending iterator iterates through all elements 820 */ 821 public void testDescendingIterator() { 822 ConcurrentLinkedDeque q = populatedDeque(SIZE); 823 int i = 0; 824 Iterator it = q.descendingIterator(); 825 while (it.hasNext()) { 826 assertTrue(q.contains(it.next())); 827 ++i; 828 } 829 assertEquals(i, SIZE); 830 assertFalse(it.hasNext()); 831 try { 832 it.next(); 833 shouldThrow(); 834 } catch (NoSuchElementException success) {} 835 } 836 837 /** 838 * Descending iterator ordering is reverse FIFO 839 */ 840 public void testDescendingIteratorOrdering() { 841 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 842 for (int iters = 0; iters < 100; ++iters) { 843 q.add(new Integer(3)); 844 q.add(new Integer(2)); 845 q.add(new Integer(1)); 846 int k = 0; 847 for (Iterator it = q.descendingIterator(); it.hasNext();) { 848 assertEquals(++k, it.next()); 849 } 850 851 assertEquals(3, k); 852 q.remove(); 853 q.remove(); 854 q.remove(); 855 } 856 } 857 858 /** 859 * descendingIterator.remove() removes current element 860 */ 861 public void testDescendingIteratorRemove() { 862 final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(); 863 final Random rng = new Random(); 864 for (int iters = 0; iters < 100; ++iters) { 865 int max = rng.nextInt(5) + 2; 866 int split = rng.nextInt(max - 1) + 1; 867 for (int j = max; j >= 1; --j) 868 q.add(new Integer(j)); 869 Iterator it = q.descendingIterator(); 870 for (int j = 1; j <= split; ++j) 871 assertEquals(it.next(), new Integer(j)); 872 it.remove(); 873 assertEquals(it.next(), new Integer(split + 1)); 874 for (int j = 1; j <= split; ++j) 875 q.remove(new Integer(j)); 876 it = q.descendingIterator(); 877 for (int j = split + 1; j <= max; ++j) { 878 assertEquals(it.next(), new Integer(j)); 879 it.remove(); 880 } 881 assertFalse(it.hasNext()); 882 assertTrue(q.isEmpty()); 883 } 884 } 885 886 /** 887 * toString() contains toStrings of elements 888 */ 889 public void testToString() { 890 ConcurrentLinkedDeque q = populatedDeque(SIZE); 891 String s = q.toString(); 892 for (int i = 0; i < SIZE; ++i) { 893 assertTrue(s.contains(String.valueOf(i))); 894 } 895 } 896 897 /** 898 * A deserialized/reserialized deque has same elements in same order 899 */ 900 public void testSerialization() throws Exception { 901 Queue x = populatedDeque(SIZE); 902 Queue y = serialClone(x); 903 904 assertNotSame(x, y); 905 assertEquals(x.size(), y.size()); 906 assertEquals(x.toString(), y.toString()); 907 assertTrue(Arrays.equals(x.toArray(), y.toArray())); 908 while (!x.isEmpty()) { 909 assertFalse(y.isEmpty()); 910 assertEquals(x.remove(), y.remove()); 911 } 912 assertTrue(y.isEmpty()); 913 } 914 915 /** 916 * contains(null) always return false. 917 * remove(null) always throws NullPointerException. 918 */ 919 public void testNeverContainsNull() { 920 Deque<?>[] qs = { 921 new ConcurrentLinkedDeque<Object>(), 922 populatedDeque(2), 923 }; 924 925 for (Deque<?> q : qs) { 926 assertFalse(q.contains(null)); 927 try { 928 assertFalse(q.remove(null)); 929 shouldThrow(); 930 } catch (NullPointerException success) {} 931 try { 932 assertFalse(q.removeFirstOccurrence(null)); 933 shouldThrow(); 934 } catch (NullPointerException success) {} 935 try { 936 assertFalse(q.removeLastOccurrence(null)); 937 shouldThrow(); 938 } catch (NullPointerException success) {} 939 } 940 } 941 942 void runAsync(Runnable r1, Runnable r2) { 943 boolean b = randomBoolean(); 944 CompletableFuture<Void> f1 = CompletableFuture.runAsync(b ? r1 : r2); 945 CompletableFuture<Void> f2 = CompletableFuture.runAsync(b ? r2 : r1); 946 f1.join(); 947 f2.join(); 948 } 949 950 /** 951 * Non-traversing Deque operations are linearizable. 952 * https://bugs.openjdk.java.net/browse/JDK-8188900 953 * ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8188900 tck 954 */ 955 public void testBug8188900() { 956 final ThreadLocalRandom rnd = ThreadLocalRandom.current(); 957 final LongAdder nulls = new LongAdder(), zeros = new LongAdder(); 958 for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) { 959 ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>(); 960 961 boolean peek = rnd.nextBoolean(); 962 Runnable getter = () -> { 963 Integer x = peek ? d.peekFirst() : d.pollFirst(); 964 if (x == null) nulls.increment(); 965 else if (x == 0) zeros.increment(); 966 else 967 throw new AssertionError( 968 String.format( 969 "unexpected value %d after %d nulls and %d zeros", 970 x, nulls.sum(), zeros.sum())); 971 }; 972 973 Runnable adder = () -> { d.addFirst(0); d.addLast(42); }; 974 975 runAsync(getter, adder); 976 } 977 } 978 979 /** 980 * Reverse direction variant of testBug8188900 981 */ 982 public void testBug8188900_reverse() { 983 final ThreadLocalRandom rnd = ThreadLocalRandom.current(); 984 final LongAdder nulls = new LongAdder(), zeros = new LongAdder(); 985 for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) { 986 ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>(); 987 988 boolean peek = rnd.nextBoolean(); 989 Runnable getter = () -> { 990 Integer x = peek ? d.peekLast() : d.pollLast(); 991 if (x == null) nulls.increment(); 992 else if (x == 0) zeros.increment(); 993 else 994 throw new AssertionError( 995 String.format( 996 "unexpected value %d after %d nulls and %d zeros", 997 x, nulls.sum(), zeros.sum())); 998 }; 999 1000 Runnable adder = () -> { d.addLast(0); d.addFirst(42); }; 1001 1002 runAsync(getter, adder); 1003 } 1004 } 1005 1006 /** 1007 * Non-traversing Deque operations (that return null) are linearizable. 1008 * Don't return null when the deque is observably never empty. 1009 * https://bugs.openjdk.java.net/browse/JDK-8189387 1010 * ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8189387 tck 1011 */ 1012 public void testBug8189387() { 1013 Object x = new Object(); 1014 for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) { 1015 ConcurrentLinkedDeque<Object> d = new ConcurrentLinkedDeque<>(); 1016 Runnable add = chooseRandomly( 1017 () -> d.addFirst(x), 1018 () -> d.offerFirst(x), 1019 () -> d.addLast(x), 1020 () -> d.offerLast(x)); 1021 1022 Runnable get = chooseRandomly( 1023 () -> assertFalse(d.isEmpty()), 1024 () -> assertSame(x, d.peekFirst()), 1025 () -> assertSame(x, d.peekLast()), 1026 () -> assertSame(x, d.pollFirst()), 1027 () -> assertSame(x, d.pollLast())); 1028 1029 Runnable addRemove = chooseRandomly( 1030 () -> { d.addFirst(x); d.pollLast(); }, 1031 () -> { d.offerFirst(x); d.removeFirst(); }, 1032 () -> { d.offerLast(x); d.removeLast(); }, 1033 () -> { d.addLast(x); d.pollFirst(); }); 1034 1035 add.run(); 1036 runAsync(get, addRemove); 1037 } 1038 } 1039 }