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 }