ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/test/tck/ConcurrentLinkedDequeTest.java
(Generate patch)

Comparing jsr166/src/test/tck/ConcurrentLinkedDequeTest.java (file contents):
Revision 1.20 by jsr166, Fri May 15 18:21:19 2015 UTC vs.
Revision 1.34 by jsr166, Tue Aug 13 00:54:51 2019 UTC

# Line 13 | Line 13 | import java.util.Iterator;
13   import java.util.NoSuchElementException;
14   import java.util.Queue;
15   import java.util.Random;
16 + import java.util.concurrent.CompletableFuture;
17   import java.util.concurrent.ConcurrentLinkedDeque;
18 + import java.util.concurrent.ThreadLocalRandom;
19 + import java.util.concurrent.atomic.LongAdder;
20  
21   import junit.framework.Test;
19 – import junit.framework.TestSuite;
22  
23   public class ConcurrentLinkedDequeTest extends JSR166TestCase {
24  
# Line 25 | Line 27 | public class ConcurrentLinkedDequeTest e
27      }
28  
29      public static Test suite() {
30 <        return new TestSuite(ConcurrentLinkedDequeTest.class);
30 >        class Implementation implements CollectionImplementation {
31 >            public Class<?> klazz() { return ConcurrentLinkedDeque.class; }
32 >            public Collection emptyCollection() { return new ConcurrentLinkedDeque(); }
33 >            public Object makeElement(int i) { return i; }
34 >            public boolean isConcurrent() { return true; }
35 >            public boolean permitsNulls() { return false; }
36 >        }
37 >        return newTestSuite(ConcurrentLinkedDequeTest.class,
38 >                            CollectionTest.testSuite(new Implementation()));
39      }
40  
41      /**
42       * Returns a new deque of given size containing consecutive
43 <     * Integers 0 ... n.
43 >     * Integers 0 ... n - 1.
44       */
45 <    private ConcurrentLinkedDeque<Integer> populatedDeque(int n) {
46 <        ConcurrentLinkedDeque<Integer> q = new ConcurrentLinkedDeque<Integer>();
45 >    private static ConcurrentLinkedDeque<Integer> populatedDeque(int n) {
46 >        ConcurrentLinkedDeque<Integer> q = new ConcurrentLinkedDeque<>();
47          assertTrue(q.isEmpty());
48          for (int i = 0; i < n; ++i)
49              assertTrue(q.offer(new Integer(i)));
50          assertFalse(q.isEmpty());
51          assertEquals(n, q.size());
52 +        assertEquals((Integer) 0, q.peekFirst());
53 +        assertEquals((Integer) (n - 1), q.peekLast());
54          return q;
55      }
56  
# Line 75 | Line 87 | public class ConcurrentLinkedDequeTest e
87       */
88      public void testConstructor5() {
89          Integer[] ints = new Integer[SIZE];
90 <        for (int i = 0; i < SIZE-1; ++i)
90 >        for (int i = 0; i < SIZE - 1; ++i)
91              ints[i] = new Integer(i);
92          try {
93              new ConcurrentLinkedDeque(Arrays.asList(ints));
# Line 115 | Line 127 | public class ConcurrentLinkedDequeTest e
127      public void testSize() {
128          ConcurrentLinkedDeque q = populatedDeque(SIZE);
129          for (int i = 0; i < SIZE; ++i) {
130 <            assertEquals(SIZE-i, q.size());
130 >            assertEquals(SIZE - i, q.size());
131              q.remove();
132          }
133          for (int i = 0; i < SIZE; ++i) {
# Line 303 | Line 315 | public class ConcurrentLinkedDequeTest e
315      }
316  
317      /**
318 <     * addAll(this) throws IAE
318 >     * addAll(this) throws IllegalArgumentException
319       */
320      public void testAddAllSelf() {
321          ConcurrentLinkedDeque q = populatedDeque(SIZE);
# Line 331 | Line 343 | public class ConcurrentLinkedDequeTest e
343      public void testAddAll3() {
344          ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
345          Integer[] ints = new Integer[SIZE];
346 <        for (int i = 0; i < SIZE-1; ++i)
346 >        for (int i = 0; i < SIZE - 1; ++i)
347              ints[i] = new Integer(i);
348          try {
349              q.addAll(Arrays.asList(ints));
# Line 370 | Line 382 | public class ConcurrentLinkedDequeTest e
382       */
383      public void testPollLast() {
384          ConcurrentLinkedDeque q = populatedDeque(SIZE);
385 <        for (int i = SIZE-1; i >= 0; --i) {
385 >        for (int i = SIZE - 1; i >= 0; --i) {
386              assertEquals(i, q.pollLast());
387          }
388          assertNull(q.pollLast());
# Line 439 | Line 451 | public class ConcurrentLinkedDequeTest e
451              assertTrue(q.contains(i));
452              assertTrue(q.remove(i));
453              assertFalse(q.contains(i));
454 <            assertTrue(q.contains(i-1));
454 >            assertTrue(q.contains(i - 1));
455          }
456          for (int i = 0; i < SIZE; i += 2) {
457              assertTrue(q.contains(i));
458              assertTrue(q.remove(i));
459              assertFalse(q.contains(i));
460 <            assertFalse(q.remove(i+1));
461 <            assertFalse(q.contains(i+1));
460 >            assertFalse(q.remove(i + 1));
461 >            assertFalse(q.contains(i + 1));
462          }
463          assertTrue(q.isEmpty());
464      }
# Line 470 | Line 482 | public class ConcurrentLinkedDequeTest e
482       */
483      public void testPeekLast() {
484          ConcurrentLinkedDeque q = populatedDeque(SIZE);
485 <        for (int i = SIZE-1; i >= 0; --i) {
485 >        for (int i = SIZE - 1; i >= 0; --i) {
486              assertEquals(i, q.peekLast());
487              assertEquals(i, q.pollLast());
488              assertTrue(q.peekLast() == null ||
# Line 499 | Line 511 | public class ConcurrentLinkedDequeTest e
511       */
512      public void testLastElement() {
513          ConcurrentLinkedDeque q = populatedDeque(SIZE);
514 <        for (int i = SIZE-1; i >= 0; --i) {
514 >        for (int i = SIZE - 1; i >= 0; --i) {
515              assertEquals(i, q.getLast());
516              assertEquals(i, q.pollLast());
517          }
# Line 550 | Line 562 | public class ConcurrentLinkedDequeTest e
562          }
563          for (int i = 0; i < SIZE; i += 2) {
564              assertTrue(q.removeFirstOccurrence(new Integer(i)));
565 <            assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
565 >            assertFalse(q.removeFirstOccurrence(new Integer(i + 1)));
566          }
567          assertTrue(q.isEmpty());
568      }
# Line 565 | Line 577 | public class ConcurrentLinkedDequeTest e
577          }
578          for (int i = 0; i < SIZE; i += 2) {
579              assertTrue(q.removeLastOccurrence(new Integer(i)));
580 <            assertFalse(q.removeLastOccurrence(new Integer(i+1)));
580 >            assertFalse(q.removeLastOccurrence(new Integer(i + 1)));
581          }
582          assertTrue(q.isEmpty());
583      }
# Line 624 | Line 636 | public class ConcurrentLinkedDequeTest e
636                  assertTrue(changed);
637  
638              assertTrue(q.containsAll(p));
639 <            assertEquals(SIZE-i, q.size());
639 >            assertEquals(SIZE - i, q.size());
640              p.remove();
641          }
642      }
# Line 637 | Line 649 | public class ConcurrentLinkedDequeTest e
649              ConcurrentLinkedDeque q = populatedDeque(SIZE);
650              ConcurrentLinkedDeque p = populatedDeque(i);
651              assertTrue(q.removeAll(p));
652 <            assertEquals(SIZE-i, q.size());
652 >            assertEquals(SIZE - i, q.size());
653              for (int j = 0; j < i; ++j) {
654                  Integer x = (Integer)(p.remove());
655                  assertFalse(q.contains(x));
# Line 650 | Line 662 | public class ConcurrentLinkedDequeTest e
662       */
663      public void testToArray() {
664          ConcurrentLinkedDeque q = populatedDeque(SIZE);
665 <        Object[] o = q.toArray();
666 <        for (int i = 0; i < o.length; i++)
667 <            assertSame(o[i], q.poll());
665 >        Object[] a = q.toArray();
666 >        assertSame(Object[].class, a.getClass());
667 >        for (Object o : a)
668 >            assertSame(o, q.poll());
669 >        assertTrue(q.isEmpty());
670      }
671  
672      /**
# Line 663 | Line 677 | public class ConcurrentLinkedDequeTest e
677          Integer[] ints = new Integer[SIZE];
678          Integer[] array = q.toArray(ints);
679          assertSame(ints, array);
680 <        for (int i = 0; i < ints.length; i++)
681 <            assertSame(ints[i], q.poll());
680 >        for (Integer o : ints)
681 >            assertSame(o, q.poll());
682 >        assertTrue(q.isEmpty());
683      }
684  
685      /**
# Line 673 | Line 688 | public class ConcurrentLinkedDequeTest e
688      public void testToArray_NullArg() {
689          ConcurrentLinkedDeque q = populatedDeque(SIZE);
690          try {
691 <            q.toArray(null);
691 >            q.toArray((Object[])null);
692              shouldThrow();
693          } catch (NullPointerException success) {}
694      }
# Line 753 | Line 768 | public class ConcurrentLinkedDequeTest e
768          final Random rng = new Random();
769          for (int iters = 0; iters < 100; ++iters) {
770              int max = rng.nextInt(5) + 2;
771 <            int split = rng.nextInt(max-1) + 1;
771 >            int split = rng.nextInt(max - 1) + 1;
772              for (int j = 1; j <= max; ++j)
773                  q.add(new Integer(j));
774              Iterator it = q.iterator();
775              for (int j = 1; j <= split; ++j)
776                  assertEquals(it.next(), new Integer(j));
777              it.remove();
778 <            assertEquals(it.next(), new Integer(split+1));
778 >            assertEquals(it.next(), new Integer(split + 1));
779              for (int j = 1; j <= split; ++j)
780                  q.remove(new Integer(j));
781              it = q.iterator();
782 <            for (int j = split+1; j <= max; ++j) {
782 >            for (int j = split + 1; j <= max; ++j) {
783                  assertEquals(it.next(), new Integer(j));
784                  it.remove();
785              }
# Line 821 | Line 836 | public class ConcurrentLinkedDequeTest e
836          final Random rng = new Random();
837          for (int iters = 0; iters < 100; ++iters) {
838              int max = rng.nextInt(5) + 2;
839 <            int split = rng.nextInt(max-1) + 1;
839 >            int split = rng.nextInt(max - 1) + 1;
840              for (int j = max; j >= 1; --j)
841                  q.add(new Integer(j));
842              Iterator it = q.descendingIterator();
843              for (int j = 1; j <= split; ++j)
844                  assertEquals(it.next(), new Integer(j));
845              it.remove();
846 <            assertEquals(it.next(), new Integer(split+1));
846 >            assertEquals(it.next(), new Integer(split + 1));
847              for (int j = 1; j <= split; ++j)
848                  q.remove(new Integer(j));
849              it = q.descendingIterator();
850 <            for (int j = split+1; j <= max; ++j) {
850 >            for (int j = split + 1; j <= max; ++j) {
851                  assertEquals(it.next(), new Integer(j));
852                  it.remove();
853              }
# Line 853 | Line 868 | public class ConcurrentLinkedDequeTest e
868      }
869  
870      /**
871 <     * A deserialized serialized deque has same elements in same order
871 >     * A deserialized/reserialized deque has same elements in same order
872       */
873      public void testSerialization() throws Exception {
874          Queue x = populatedDeque(SIZE);
# Line 896 | Line 911 | public class ConcurrentLinkedDequeTest e
911              } catch (NullPointerException success) {}
912          }
913      }
914 +
915 +    void runAsync(Runnable r1, Runnable r2) {
916 +        boolean b = randomBoolean();
917 +        CompletableFuture<Void> f1 = CompletableFuture.runAsync(b ? r1 : r2);
918 +        CompletableFuture<Void> f2 = CompletableFuture.runAsync(b ? r2 : r1);
919 +        f1.join();
920 +        f2.join();
921 +    }
922 +
923 +    /**
924 +     * Non-traversing Deque operations are linearizable.
925 +     * https://bugs.openjdk.java.net/browse/JDK-8188900
926 +     * ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8188900 tck
927 +     */
928 +    public void testBug8188900() {
929 +        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
930 +        final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
931 +        for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
932 +            ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>();
933 +
934 +            boolean peek = rnd.nextBoolean();
935 +            Runnable getter = () -> {
936 +                Integer x = peek ? d.peekFirst() : d.pollFirst();
937 +                if (x == null) nulls.increment();
938 +                else if (x == 0) zeros.increment();
939 +                else
940 +                    throw new AssertionError(
941 +                        String.format(
942 +                            "unexpected value %d after %d nulls and %d zeros",
943 +                            x, nulls.sum(), zeros.sum()));
944 +            };
945 +
946 +            Runnable adder = () -> { d.addFirst(0); d.addLast(42); };
947 +
948 +            runAsync(getter, adder);
949 +        }
950 +    }
951 +
952 +    /**
953 +     * Reverse direction variant of testBug8188900
954 +     */
955 +    public void testBug8188900_reverse() {
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.peekLast() : d.pollLast();
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.addLast(0); d.addFirst(42); };
974 +
975 +            runAsync(getter, adder);
976 +        }
977 +    }
978 +
979 +    <T> T chooseRandomly(T... choices) {
980 +        return choices[ThreadLocalRandom.current().nextInt(choices.length)];
981 +    }
982 +
983 +    /**
984 +     * Non-traversing Deque operations (that return null) are linearizable.
985 +     * Don't return null when the deque is observably never empty.
986 +     * https://bugs.openjdk.java.net/browse/JDK-8189387
987 +     * ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8189387 tck
988 +     */
989 +    public void testBug8189387() {
990 +        final ThreadLocalRandom rnd = ThreadLocalRandom.current();
991 +        Object x = new Object();
992 +        for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
993 +            ConcurrentLinkedDeque<Object> d = new ConcurrentLinkedDeque<>();
994 +            Runnable add = chooseRandomly(
995 +                () -> d.addFirst(x),
996 +                () -> d.offerFirst(x),
997 +                () -> d.addLast(x),
998 +                () -> d.offerLast(x));
999 +
1000 +            Runnable get = chooseRandomly(
1001 +                () -> assertFalse(d.isEmpty()),
1002 +                () -> assertSame(x, d.peekFirst()),
1003 +                () -> assertSame(x, d.peekLast()),
1004 +                () -> assertSame(x, d.pollFirst()),
1005 +                () -> assertSame(x, d.pollLast()));
1006 +
1007 +            Runnable addRemove = chooseRandomly(
1008 +                () -> { d.addFirst(x); d.pollLast(); },
1009 +                () -> { d.offerFirst(x); d.removeFirst(); },
1010 +                () -> { d.offerLast(x); d.removeLast(); },
1011 +                () -> { d.addLast(x); d.pollFirst(); });
1012 +
1013 +            add.run();
1014 +            runAsync(get, addRemove);
1015 +        }
1016 +    }
1017   }

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines