ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/tck/ConcurrentLinkedDequeTest.java

Comparing jsr166/src/test/tck/ConcurrentLinkedDequeTest.java (file contents):
Revision 1.16 by jsr166, Wed Dec 31 20:17:39 2014 UTC vs.
Revision 1.31 by jsr166, Sun Oct 22 21:52:58 2017 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
25		public static void main(String[] args) {
26	<	junit.textui.TestRunner.run(suite());
26	>	main(suite(), args);
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 55 | Line 67 | public class ConcurrentLinkedDequeTest e
67		*/
68		public void testConstructor3() {
69		try {
70	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque((Collection)null);
70	>	new ConcurrentLinkedDeque((Collection)null);
71		shouldThrow();
72		} catch (NullPointerException success) {}
73		}
#	Line 65 | Line 77 | public class ConcurrentLinkedDequeTest e
77		*/
78		public void testConstructor4() {
79		try {
80	<	Integer[] ints = new Integer[SIZE];
69	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(Arrays.asList(ints));
80	>	new ConcurrentLinkedDeque(Arrays.asList(new Integer[SIZE]));
81		shouldThrow();
82		} catch (NullPointerException success) {}
83		}
#	Line 75 | Line 86 | public class ConcurrentLinkedDequeTest e
86		* Initializing from Collection with some null elements throws NPE
87		*/
88		public void testConstructor5() {
89	+	Integer[] ints = new Integer[SIZE];
90	+	for (int i = 0; i < SIZE - 1; ++i)
91	+	ints[i] = new Integer(i);
92		try {
93	<	Integer[] ints = new Integer[SIZE];
80	<	for (int i = 0; i < SIZE-1; ++i)
81	<	ints[i] = new Integer(i);
82	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(Arrays.asList(ints));
93	>	new ConcurrentLinkedDeque(Arrays.asList(ints));
94		shouldThrow();
95		} catch (NullPointerException success) {}
96		}
#	Line 116 | 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 129 | Line 140 | public class ConcurrentLinkedDequeTest e
140		* push(null) throws NPE
141		*/
142		public void testPushNull() {
143	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
144		try {
133	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
145		q.push(null);
146		shouldThrow();
147		} catch (NullPointerException success) {}
#	Line 164 | Line 175 | public class ConcurrentLinkedDequeTest e
175		* offer(null) throws NPE
176		*/
177		public void testOfferNull() {
178	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
179		try {
168	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
180		q.offer(null);
181		shouldThrow();
182		} catch (NullPointerException success) {}
#	Line 175 | Line 186 | public class ConcurrentLinkedDequeTest e
186		* offerFirst(null) throws NPE
187		*/
188		public void testOfferFirstNull() {
189	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
190		try {
179	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
191		q.offerFirst(null);
192		shouldThrow();
193		} catch (NullPointerException success) {}
#	Line 186 | Line 197 | public class ConcurrentLinkedDequeTest e
197		* offerLast(null) throws NPE
198		*/
199		public void testOfferLastNull() {
200	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
201		try {
190	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
202		q.offerLast(null);
203		shouldThrow();
204		} catch (NullPointerException success) {}
#	Line 230 | Line 241 | public class ConcurrentLinkedDequeTest e
241		* add(null) throws NPE
242		*/
243		public void testAddNull() {
244	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
245		try {
234	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
246		q.add(null);
247		shouldThrow();
248		} catch (NullPointerException success) {}
#	Line 241 | Line 252 | public class ConcurrentLinkedDequeTest e
252		* addFirst(null) throws NPE
253		*/
254		public void testAddFirstNull() {
255	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
256		try {
245	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
257		q.addFirst(null);
258		shouldThrow();
259		} catch (NullPointerException success) {}
#	Line 252 | Line 263 | public class ConcurrentLinkedDequeTest e
263		* addLast(null) throws NPE
264		*/
265		public void testAddLastNull() {
266	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
267		try {
256	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
268		q.addLast(null);
269		shouldThrow();
270		} catch (NullPointerException success) {}
#	Line 296 | Line 307 | public class ConcurrentLinkedDequeTest e
307		* addAll(null) throws NPE
308		*/
309		public void testAddAll1() {
310	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
311		try {
300	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
312		q.addAll(null);
313		shouldThrow();
314		} catch (NullPointerException success) {}
315		}
316
317		/**
318	<	* addAll(this) throws IAE
318	>	* addAll(this) throws IllegalArgumentException
319		*/
320		public void testAddAllSelf() {
321	+	ConcurrentLinkedDeque q = populatedDeque(SIZE);
322		try {
311	–	ConcurrentLinkedDeque q = populatedDeque(SIZE);
323		q.addAll(q);
324		shouldThrow();
325		} catch (IllegalArgumentException success) {}
#	Line 318 | Line 329 | public class ConcurrentLinkedDequeTest e
329		* addAll of a collection with null elements throws NPE
330		*/
331		public void testAddAll2() {
332	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
333		try {
334	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
323	<	Integer[] ints = new Integer[SIZE];
324	<	q.addAll(Arrays.asList(ints));
334	>	q.addAll(Arrays.asList(new Integer[SIZE]));
335		shouldThrow();
336		} catch (NullPointerException success) {}
337		}
#	Line 331 | Line 341 | public class ConcurrentLinkedDequeTest e
341		* possibly adding some elements
342		*/
343		public void testAddAll3() {
344	+	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
345	+	Integer[] ints = new Integer[SIZE];
346	+	for (int i = 0; i < SIZE - 1; ++i)
347	+	ints[i] = new Integer(i);
348		try {
335	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
336	–	Integer[] ints = new Integer[SIZE];
337	–	for (int i = 0; i < SIZE-1; ++i)
338	–	ints[i] = new Integer(i);
349		q.addAll(Arrays.asList(ints));
350		shouldThrow();
351		} catch (NullPointerException success) {}
#	Line 372 | 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 441 | 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 472 | 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 501 | 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 552 | 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 567 | 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 626 | 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 639 | 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 696 | Line 706 | public class ConcurrentLinkedDequeTest e
706		*/
707		public void testIterator() {
708		ConcurrentLinkedDeque q = populatedDeque(SIZE);
699	–	int i = 0;
709		Iterator it = q.iterator();
710	<	while (it.hasNext()) {
710	>	int i;
711	>	for (i = 0; it.hasNext(); i++)
712		assertTrue(q.contains(it.next()));
703	–	++i;
704	–	}
713		assertEquals(i, SIZE);
714	+	assertIteratorExhausted(it);
715	+	}
716	+
717	+	/**
718	+	* iterator of empty collection has no elements
719	+	*/
720	+	public void testEmptyIterator() {
721	+	Deque c = new ConcurrentLinkedDeque();
722	+	assertIteratorExhausted(c.iterator());
723	+	assertIteratorExhausted(c.descendingIterator());
724		}
725
726		/**
#	Line 747 | Line 765 | public class ConcurrentLinkedDequeTest e
765		final Random rng = new Random();
766		for (int iters = 0; iters < 100; ++iters) {
767		int max = rng.nextInt(5) + 2;
768	<	int split = rng.nextInt(max-1) + 1;
768	>	int split = rng.nextInt(max - 1) + 1;
769		for (int j = 1; j <= max; ++j)
770		q.add(new Integer(j));
771		Iterator it = q.iterator();
772		for (int j = 1; j <= split; ++j)
773		assertEquals(it.next(), new Integer(j));
774		it.remove();
775	<	assertEquals(it.next(), new Integer(split+1));
775	>	assertEquals(it.next(), new Integer(split + 1));
776		for (int j = 1; j <= split; ++j)
777		q.remove(new Integer(j));
778		it = q.iterator();
779	<	for (int j = split+1; j <= max; ++j) {
779	>	for (int j = split + 1; j <= max; ++j) {
780		assertEquals(it.next(), new Integer(j));
781		it.remove();
782		}
#	Line 815 | Line 833 | public class ConcurrentLinkedDequeTest e
833		final Random rng = new Random();
834		for (int iters = 0; iters < 100; ++iters) {
835		int max = rng.nextInt(5) + 2;
836	<	int split = rng.nextInt(max-1) + 1;
836	>	int split = rng.nextInt(max - 1) + 1;
837		for (int j = max; j >= 1; --j)
838		q.add(new Integer(j));
839		Iterator it = q.descendingIterator();
840		for (int j = 1; j <= split; ++j)
841		assertEquals(it.next(), new Integer(j));
842		it.remove();
843	<	assertEquals(it.next(), new Integer(split+1));
843	>	assertEquals(it.next(), new Integer(split + 1));
844		for (int j = 1; j <= split; ++j)
845		q.remove(new Integer(j));
846		it = q.descendingIterator();
847	<	for (int j = split+1; j <= max; ++j) {
847	>	for (int j = split + 1; j <= max; ++j) {
848		assertEquals(it.next(), new Integer(j));
849		it.remove();
850		}
#	Line 847 | Line 865 | public class ConcurrentLinkedDequeTest e
865		}
866
867		/**
868	<	* A deserialized serialized deque has same elements in same order
868	>	* A deserialized/reserialized deque has same elements in same order
869		*/
870		public void testSerialization() throws Exception {
871		Queue x = populatedDeque(SIZE);
#	Line 890 | Line 908 | public class ConcurrentLinkedDequeTest e
908		} catch (NullPointerException success) {}
909		}
910		}
911	+
912	+	void runAsync(Runnable r1, Runnable r2) {
913	+	boolean b = ThreadLocalRandom.current().nextBoolean();
914	+	CompletableFuture<Void> f1 = CompletableFuture.runAsync(b ? r1 : r2);
915	+	CompletableFuture<Void> f2 = CompletableFuture.runAsync(b ? r2 : r1);
916	+	f1.join();
917	+	f2.join();
918	+	}
919	+
920	+	/**
921	+	* Non-traversing Deque operations are linearizable.
922	+	* https://bugs.openjdk.java.net/browse/JDK-8188900
923	+	* ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8188900 tck
924	+	*/
925	+	public void testBug8188900() {
926	+	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
927	+	final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
928	+	for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
929	+	ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>();
930	+
931	+	boolean peek = rnd.nextBoolean();
932	+	Runnable getter = () -> {
933	+	Integer x = peek ? d.peekFirst() : d.pollFirst();
934	+	if (x == null) nulls.increment();
935	+	else if (x == 0) zeros.increment();
936	+	else
937	+	throw new AssertionError(
938	+	String.format(
939	+	"unexpected value %d after %d nulls and %d zeros",
940	+	x, nulls.sum(), zeros.sum()));
941	+	};
942	+
943	+	Runnable adder = () -> { d.addFirst(0); d.addLast(42); };
944	+
945	+	runAsync(getter, adder);
946	+	}
947	+	}
948	+
949	+	/**
950	+	* Reverse direction variant of testBug8188900
951	+	*/
952	+	public void testBug8188900_reverse() {
953	+	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
954	+	final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
955	+	for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
956	+	ConcurrentLinkedDeque<Integer> d = new ConcurrentLinkedDeque<>();
957	+
958	+	boolean peek = rnd.nextBoolean();
959	+	Runnable getter = () -> {
960	+	Integer x = peek ? d.peekLast() : d.pollLast();
961	+	if (x == null) nulls.increment();
962	+	else if (x == 0) zeros.increment();
963	+	else
964	+	throw new AssertionError(
965	+	String.format(
966	+	"unexpected value %d after %d nulls and %d zeros",
967	+	x, nulls.sum(), zeros.sum()));
968	+	};
969	+
970	+	Runnable adder = () -> { d.addLast(0); d.addFirst(42); };
971	+
972	+	runAsync(getter, adder);
973	+	}
974	+	}
975	+
976	+	<T> T chooseRandomly(T... choices) {
977	+	return choices[ThreadLocalRandom.current().nextInt(choices.length)];
978	+	}
979	+
980	+	/**
981	+	* Non-traversing Deque operations (that return null) are linearizable.
982	+	* Don't return null when the deque is observably never empty.
983	+	* https://bugs.openjdk.java.net/browse/JDK-8189387
984	+	* ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8189387 tck
985	+	*/
986	+	public void testBug8189387() {
987	+	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
988	+	Object x = new Object();
989	+	for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
990	+	ConcurrentLinkedDeque<Object> d = new ConcurrentLinkedDeque<>();
991	+	Runnable add = chooseRandomly(
992	+	() -> d.addFirst(x),
993	+	() -> d.offerFirst(x),
994	+	() -> d.addLast(x),
995	+	() -> d.offerLast(x));
996	+
997	+	Runnable get = chooseRandomly(
998	+	() -> assertFalse(d.isEmpty()),
999	+	() -> assertSame(x, d.peekFirst()),
1000	+	() -> assertSame(x, d.peekLast()),
1001	+	() -> assertSame(x, d.pollFirst()),
1002	+	() -> assertSame(x, d.pollLast()));
1003	+
1004	+	Runnable addRemove = chooseRandomly(
1005	+	() -> { d.addFirst(x); d.pollLast(); },
1006	+	() -> { d.offerFirst(x); d.removeFirst(); },
1007	+	() -> { d.offerLast(x); d.removeLast(); },
1008	+	() -> { d.addLast(x); d.pollFirst(); });
1009	+
1010	+	add.run();
1011	+	runAsync(get, addRemove);
1012	+	}
1013	+	}
1014		}

Diff Legend

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