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.18 by jsr166, Sun Feb 22 04:34:44 2015 UTC vs.
Revision 1.40 by jsr166, Wed Jan 27 02:55:18 2021 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 JSR166TestCase.itemFor(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	>	* Items 0 ... n - 1.
44		*/
45	<	private ConcurrentLinkedDeque<Integer> populatedDeque(int n) {
46	<	ConcurrentLinkedDeque<Integer> q = new ConcurrentLinkedDeque<Integer>();
45	>	private static ConcurrentLinkedDeque<Item> populatedDeque(int n) {
46	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
47		assertTrue(q.isEmpty());
48		for (int i = 0; i < n; ++i)
49	<	assertTrue(q.offer(new Integer(i)));
49	>	mustOffer(q, i);
50		assertFalse(q.isEmpty());
51	<	assertEquals(n, q.size());
51	>	mustEqual(n, q.size());
52	>	mustEqual(0, q.peekFirst());
53	>	mustEqual((n - 1), q.peekLast());
54		return q;
55		}
56
#	Line 46 | Line 58 | public class ConcurrentLinkedDequeTest e
58		* new deque is empty
59		*/
60		public void testConstructor1() {
61	<	assertTrue(new ConcurrentLinkedDeque().isEmpty());
62	<	assertEquals(0, new ConcurrentLinkedDeque().size());
61	>	assertTrue(new ConcurrentLinkedDeque<Item>().isEmpty());
62	>	mustEqual(0, new ConcurrentLinkedDeque<Item>().size());
63		}
64
65		/**
#	Line 55 | Line 67 | public class ConcurrentLinkedDequeTest e
67		*/
68		public void testConstructor3() {
69		try {
70	<	new ConcurrentLinkedDeque((Collection)null);
70	>	new ConcurrentLinkedDeque<Item>((Collection<Item>)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	<	new ConcurrentLinkedDeque(Arrays.asList(ints));
80	>	new ConcurrentLinkedDeque<Item>(Arrays.asList(new Item[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	+	Item[] items = new Item[2]; items[0] = zero;
90		try {
91	<	Integer[] ints = new Integer[SIZE];
80	<	for (int i = 0; i < SIZE-1; ++i)
81	<	ints[i] = new Integer(i);
82	<	new ConcurrentLinkedDeque(Arrays.asList(ints));
91	>	new ConcurrentLinkedDeque<Item>(Arrays.asList(items));
92		shouldThrow();
93		} catch (NullPointerException success) {}
94		}
#	Line 88 | Line 97 | public class ConcurrentLinkedDequeTest e
97		* Deque contains all elements of collection used to initialize
98		*/
99		public void testConstructor6() {
100	<	Integer[] ints = new Integer[SIZE];
101	<	for (int i = 0; i < SIZE; ++i)
93	<	ints[i] = new Integer(i);
94	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(Arrays.asList(ints));
100	>	Item[] items = defaultItems;
101	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>(Arrays.asList(items));
102		for (int i = 0; i < SIZE; ++i)
103	<	assertEquals(ints[i], q.poll());
103	>	mustEqual(items[i], q.poll());
104		}
105
106		/**
107		* isEmpty is true before add, false after
108		*/
109		public void testEmpty() {
110	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
110	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
111		assertTrue(q.isEmpty());
112		q.add(one);
113		assertFalse(q.isEmpty());
#	Line 114 | Line 121 | public class ConcurrentLinkedDequeTest e
121		* size() changes when elements added and removed
122		*/
123		public void testSize() {
124	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
124	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
125		for (int i = 0; i < SIZE; ++i) {
126	<	assertEquals(SIZE-i, q.size());
126	>	mustEqual(SIZE - i, q.size());
127		q.remove();
128		}
129		for (int i = 0; i < SIZE; ++i) {
130	<	assertEquals(i, q.size());
131	<	q.add(new Integer(i));
130	>	mustEqual(i, q.size());
131	>	mustAdd(q, i);
132		}
133		}
134
#	Line 129 | Line 136 | public class ConcurrentLinkedDequeTest e
136		* push(null) throws NPE
137		*/
138		public void testPushNull() {
139	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
140		try {
133	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
141		q.push(null);
142		shouldThrow();
143		} catch (NullPointerException success) {}
#	Line 140 | Line 147 | public class ConcurrentLinkedDequeTest e
147		* peekFirst() returns element inserted with push
148		*/
149		public void testPush() {
150	<	ConcurrentLinkedDeque q = populatedDeque(3);
150	>	ConcurrentLinkedDeque<Item> q = populatedDeque(3);
151		q.pollLast();
152		q.push(four);
153		assertSame(four, q.peekFirst());
#	Line 150 | Line 157 | public class ConcurrentLinkedDequeTest e
157		* pop() removes first element, or throws NSEE if empty
158		*/
159		public void testPop() {
160	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
160	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
161		for (int i = 0; i < SIZE; ++i) {
162	<	assertEquals(i, q.pop());
162	>	mustEqual(i, q.pop());
163		}
164		try {
165		q.pop();
#	Line 164 | Line 171 | public class ConcurrentLinkedDequeTest e
171		* offer(null) throws NPE
172		*/
173		public void testOfferNull() {
174	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
175		try {
168	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
176		q.offer(null);
177		shouldThrow();
178		} catch (NullPointerException success) {}
#	Line 175 | Line 182 | public class ConcurrentLinkedDequeTest e
182		* offerFirst(null) throws NPE
183		*/
184		public void testOfferFirstNull() {
185	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
186		try {
179	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
187		q.offerFirst(null);
188		shouldThrow();
189		} catch (NullPointerException success) {}
#	Line 186 | Line 193 | public class ConcurrentLinkedDequeTest e
193		* offerLast(null) throws NPE
194		*/
195		public void testOfferLastNull() {
196	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
197		try {
190	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
198		q.offerLast(null);
199		shouldThrow();
200		} catch (NullPointerException success) {}
#	Line 197 | Line 204 | public class ConcurrentLinkedDequeTest e
204		* offer(x) succeeds
205		*/
206		public void testOffer() {
207	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
207	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
208		assertTrue(q.offer(zero));
209		assertTrue(q.offer(one));
210		assertSame(zero, q.peekFirst());
#	Line 208 | Line 215 | public class ConcurrentLinkedDequeTest e
215		* offerFirst(x) succeeds
216		*/
217		public void testOfferFirst() {
218	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
218	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
219		assertTrue(q.offerFirst(zero));
220		assertTrue(q.offerFirst(one));
221		assertSame(one, q.peekFirst());
#	Line 219 | Line 226 | public class ConcurrentLinkedDequeTest e
226		* offerLast(x) succeeds
227		*/
228		public void testOfferLast() {
229	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
229	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
230		assertTrue(q.offerLast(zero));
231		assertTrue(q.offerLast(one));
232		assertSame(zero, q.peekFirst());
#	Line 230 | Line 237 | public class ConcurrentLinkedDequeTest e
237		* add(null) throws NPE
238		*/
239		public void testAddNull() {
240	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
241		try {
234	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
242		q.add(null);
243		shouldThrow();
244		} catch (NullPointerException success) {}
#	Line 241 | Line 248 | public class ConcurrentLinkedDequeTest e
248		* addFirst(null) throws NPE
249		*/
250		public void testAddFirstNull() {
251	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
252		try {
245	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
253		q.addFirst(null);
254		shouldThrow();
255		} catch (NullPointerException success) {}
#	Line 252 | Line 259 | public class ConcurrentLinkedDequeTest e
259		* addLast(null) throws NPE
260		*/
261		public void testAddLastNull() {
262	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
263		try {
256	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
264		q.addLast(null);
265		shouldThrow();
266		} catch (NullPointerException success) {}
#	Line 263 | Line 270 | public class ConcurrentLinkedDequeTest e
270		* add(x) succeeds
271		*/
272		public void testAdd() {
273	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
273	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
274		assertTrue(q.add(zero));
275		assertTrue(q.add(one));
276		assertSame(zero, q.peekFirst());
#	Line 274 | Line 281 | public class ConcurrentLinkedDequeTest e
281		* addFirst(x) succeeds
282		*/
283		public void testAddFirst() {
284	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
284	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
285		q.addFirst(zero);
286		q.addFirst(one);
287		assertSame(one, q.peekFirst());
#	Line 285 | Line 292 | public class ConcurrentLinkedDequeTest e
292		* addLast(x) succeeds
293		*/
294		public void testAddLast() {
295	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
295	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
296		q.addLast(zero);
297		q.addLast(one);
298		assertSame(zero, q.peekFirst());
#	Line 296 | Line 303 | public class ConcurrentLinkedDequeTest e
303		* addAll(null) throws NPE
304		*/
305		public void testAddAll1() {
306	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
307		try {
300	–	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
308		q.addAll(null);
309		shouldThrow();
310		} catch (NullPointerException success) {}
311		}
312
313		/**
314	<	* addAll(this) throws IAE
314	>	* addAll(this) throws IllegalArgumentException
315		*/
316		public void testAddAllSelf() {
317	+	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
318		try {
311	–	ConcurrentLinkedDeque q = populatedDeque(SIZE);
319		q.addAll(q);
320		shouldThrow();
321		} catch (IllegalArgumentException success) {}
#	Line 318 | Line 325 | public class ConcurrentLinkedDequeTest e
325		* addAll of a collection with null elements throws NPE
326		*/
327		public void testAddAll2() {
328	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
329		try {
330	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
323	<	Integer[] ints = new Integer[SIZE];
324	<	q.addAll(Arrays.asList(ints));
330	>	q.addAll(Arrays.asList(new Item[SIZE]));
331		shouldThrow();
332		} catch (NullPointerException success) {}
333		}
#	Line 331 | Line 337 | public class ConcurrentLinkedDequeTest e
337		* possibly adding some elements
338		*/
339		public void testAddAll3() {
340	+	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
341	+	Item[] items = new Item[2]; items[0] = zero;
342		try {
343	<	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);
339	<	q.addAll(Arrays.asList(ints));
343	>	q.addAll(Arrays.asList(items));
344		shouldThrow();
345		} catch (NullPointerException success) {}
346		}
#	Line 345 | Line 349 | public class ConcurrentLinkedDequeTest e
349		* Deque contains all elements, in traversal order, of successful addAll
350		*/
351		public void testAddAll5() {
352	<	Integer[] empty = new Integer[0];
353	<	Integer[] ints = new Integer[SIZE];
354	<	for (int i = 0; i < SIZE; ++i)
351	<	ints[i] = new Integer(i);
352	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
352	>	Item[] empty = new Item[0];
353	>	Item[] items = defaultItems;
354	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
355		assertFalse(q.addAll(Arrays.asList(empty)));
356	<	assertTrue(q.addAll(Arrays.asList(ints)));
356	>	assertTrue(q.addAll(Arrays.asList(items)));
357		for (int i = 0; i < SIZE; ++i)
358	<	assertEquals(ints[i], q.poll());
358	>	mustEqual(items[i], q.poll());
359		}
360
361		/**
362		* pollFirst() succeeds unless empty
363		*/
364		public void testPollFirst() {
365	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
365	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
366		for (int i = 0; i < SIZE; ++i) {
367	<	assertEquals(i, q.pollFirst());
367	>	mustEqual(i, q.pollFirst());
368		}
369		assertNull(q.pollFirst());
370		}
#	Line 371 | Line 373 | public class ConcurrentLinkedDequeTest e
373		* pollLast() succeeds unless empty
374		*/
375		public void testPollLast() {
376	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
377	<	for (int i = SIZE-1; i >= 0; --i) {
378	<	assertEquals(i, q.pollLast());
376	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
377	>	for (int i = SIZE - 1; i >= 0; --i) {
378	>	mustEqual(i, q.pollLast());
379		}
380		assertNull(q.pollLast());
381		}
#	Line 382 | Line 384 | public class ConcurrentLinkedDequeTest e
384		* poll() succeeds unless empty
385		*/
386		public void testPoll() {
387	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
387	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
388		for (int i = 0; i < SIZE; ++i) {
389	<	assertEquals(i, q.poll());
389	>	mustEqual(i, q.poll());
390		}
391		assertNull(q.poll());
392		}
#	Line 393 | Line 395 | public class ConcurrentLinkedDequeTest e
395		* peek() returns next element, or null if empty
396		*/
397		public void testPeek() {
398	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
398	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
399		for (int i = 0; i < SIZE; ++i) {
400	<	assertEquals(i, q.peek());
401	<	assertEquals(i, q.poll());
400	>	mustEqual(i, q.peek());
401	>	mustEqual(i, q.poll());
402		assertTrue(q.peek() == null ||
403		!q.peek().equals(i));
404		}
#	Line 407 | Line 409 | public class ConcurrentLinkedDequeTest e
409		* element() returns first element, or throws NSEE if empty
410		*/
411		public void testElement() {
412	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
412	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
413		for (int i = 0; i < SIZE; ++i) {
414	<	assertEquals(i, q.element());
415	<	assertEquals(i, q.poll());
414	>	mustEqual(i, q.element());
415	>	mustEqual(i, q.poll());
416		}
417		try {
418		q.element();
#	Line 422 | Line 424 | public class ConcurrentLinkedDequeTest e
424		* remove() removes next element, or throws NSEE if empty
425		*/
426		public void testRemove() {
427	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
427	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
428		for (int i = 0; i < SIZE; ++i) {
429	<	assertEquals(i, q.remove());
429	>	mustEqual(i, q.remove());
430		}
431		try {
432		q.remove();
#	Line 436 | Line 438 | public class ConcurrentLinkedDequeTest e
438		* remove(x) removes x and returns true if present
439		*/
440		public void testRemoveElement() {
441	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
441	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
442		for (int i = 1; i < SIZE; i += 2) {
443	<	assertTrue(q.contains(i));
444	<	assertTrue(q.remove(i));
445	<	assertFalse(q.contains(i));
446	<	assertTrue(q.contains(i-1));
443	>	mustContain(q, i);
444	>	mustRemove(q, i);
445	>	mustNotContain(q, i);
446	>	mustContain(q, i - 1);
447		}
448		for (int i = 0; i < SIZE; i += 2) {
449	<	assertTrue(q.contains(i));
450	<	assertTrue(q.remove(i));
451	<	assertFalse(q.contains(i));
452	<	assertFalse(q.remove(i+1));
453	<	assertFalse(q.contains(i+1));
449	>	mustContain(q, i);
450	>	mustRemove(q, i);
451	>	mustNotContain(q, i);
452	>	mustNotRemove(q, i + 1);
453	>	mustNotContain(q, i + 1);
454		}
455		assertTrue(q.isEmpty());
456		}
#	Line 457 | Line 459 | public class ConcurrentLinkedDequeTest e
459		* peekFirst() returns next element, or null if empty
460		*/
461		public void testPeekFirst() {
462	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
462	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
463		for (int i = 0; i < SIZE; ++i) {
464	<	assertEquals(i, q.peekFirst());
465	<	assertEquals(i, q.pollFirst());
464	>	mustEqual(i, q.peekFirst());
465	>	mustEqual(i, q.pollFirst());
466		assertTrue(q.peekFirst() == null ||
467		!q.peekFirst().equals(i));
468		}
#	Line 471 | Line 473 | public class ConcurrentLinkedDequeTest e
473		* peekLast() returns next element, or null if empty
474		*/
475		public void testPeekLast() {
476	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
477	<	for (int i = SIZE-1; i >= 0; --i) {
478	<	assertEquals(i, q.peekLast());
479	<	assertEquals(i, q.pollLast());
476	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
477	>	for (int i = SIZE - 1; i >= 0; --i) {
478	>	mustEqual(i, q.peekLast());
479	>	mustEqual(i, q.pollLast());
480		assertTrue(q.peekLast() == null ||
481		!q.peekLast().equals(i));
482		}
#	Line 485 | Line 487 | public class ConcurrentLinkedDequeTest e
487		* getFirst() returns first element, or throws NSEE if empty
488		*/
489		public void testFirstElement() {
490	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
490	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
491		for (int i = 0; i < SIZE; ++i) {
492	<	assertEquals(i, q.getFirst());
493	<	assertEquals(i, q.pollFirst());
492	>	mustEqual(i, q.getFirst());
493	>	mustEqual(i, q.pollFirst());
494		}
495		try {
496		q.getFirst();
#	Line 500 | Line 502 | public class ConcurrentLinkedDequeTest e
502		* getLast() returns last element, or throws NSEE if empty
503		*/
504		public void testLastElement() {
505	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
506	<	for (int i = SIZE-1; i >= 0; --i) {
507	<	assertEquals(i, q.getLast());
508	<	assertEquals(i, q.pollLast());
505	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
506	>	for (int i = SIZE - 1; i >= 0; --i) {
507	>	mustEqual(i, q.getLast());
508	>	mustEqual(i, q.pollLast());
509		}
510		try {
511		q.getLast();
#	Line 516 | Line 518 | public class ConcurrentLinkedDequeTest e
518		* removeFirst() removes first element, or throws NSEE if empty
519		*/
520		public void testRemoveFirst() {
521	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
521	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
522		for (int i = 0; i < SIZE; ++i) {
523	<	assertEquals(i, q.removeFirst());
523	>	mustEqual(i, q.removeFirst());
524		}
525		try {
526		q.removeFirst();
#	Line 531 | Line 533 | public class ConcurrentLinkedDequeTest e
533		* removeLast() removes last element, or throws NSEE if empty
534		*/
535		public void testRemoveLast() {
536	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
536	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
537		for (int i = SIZE - 1; i >= 0; --i) {
538	<	assertEquals(i, q.removeLast());
538	>	mustEqual(i, q.removeLast());
539		}
540		try {
541		q.removeLast();
#	Line 546 | Line 548 | public class ConcurrentLinkedDequeTest e
548		* removeFirstOccurrence(x) removes x and returns true if present
549		*/
550		public void testRemoveFirstOccurrence() {
551	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
551	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
552		for (int i = 1; i < SIZE; i += 2) {
553	<	assertTrue(q.removeFirstOccurrence(new Integer(i)));
553	>	assertTrue(q.removeFirstOccurrence(itemFor(i)));
554		}
555		for (int i = 0; i < SIZE; i += 2) {
556	<	assertTrue(q.removeFirstOccurrence(new Integer(i)));
557	<	assertFalse(q.removeFirstOccurrence(new Integer(i+1)));
556	>	assertTrue(q.removeFirstOccurrence(itemFor(i)));
557	>	assertFalse(q.removeFirstOccurrence(itemFor(i + 1)));
558		}
559		assertTrue(q.isEmpty());
560		}
#	Line 561 | Line 563 | public class ConcurrentLinkedDequeTest e
563		* removeLastOccurrence(x) removes x and returns true if present
564		*/
565		public void testRemoveLastOccurrence() {
566	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
566	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
567		for (int i = 1; i < SIZE; i += 2) {
568	<	assertTrue(q.removeLastOccurrence(new Integer(i)));
568	>	assertTrue(q.removeLastOccurrence(itemFor(i)));
569		}
570		for (int i = 0; i < SIZE; i += 2) {
571	<	assertTrue(q.removeLastOccurrence(new Integer(i)));
572	<	assertFalse(q.removeLastOccurrence(new Integer(i+1)));
571	>	assertTrue(q.removeLastOccurrence(itemFor(i)));
572	>	assertFalse(q.removeLastOccurrence(itemFor(i + 1)));
573		}
574		assertTrue(q.isEmpty());
575		}
#	Line 576 | Line 578 | public class ConcurrentLinkedDequeTest e
578		* contains(x) reports true when elements added but not yet removed
579		*/
580		public void testContains() {
581	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
581	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
582		for (int i = 0; i < SIZE; ++i) {
583	<	assertTrue(q.contains(new Integer(i)));
583	>	mustContain(q, i);
584		q.poll();
585	<	assertFalse(q.contains(new Integer(i)));
585	>	mustNotContain(q, i);
586		}
587		}
588
#	Line 588 | Line 590 | public class ConcurrentLinkedDequeTest e
590		* clear() removes all elements
591		*/
592		public void testClear() {
593	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
593	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
594		q.clear();
595		assertTrue(q.isEmpty());
596	<	assertEquals(0, q.size());
596	>	mustEqual(0, q.size());
597		q.add(one);
598		assertFalse(q.isEmpty());
599		q.clear();
#	Line 602 | Line 604 | public class ConcurrentLinkedDequeTest e
604		* containsAll(c) is true when c contains a subset of elements
605		*/
606		public void testContainsAll() {
607	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
608	<	ConcurrentLinkedDeque p = new ConcurrentLinkedDeque();
607	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
608	>	ConcurrentLinkedDeque<Item> p = new ConcurrentLinkedDeque<>();
609		for (int i = 0; i < SIZE; ++i) {
610		assertTrue(q.containsAll(p));
611		assertFalse(p.containsAll(q));
612	<	p.add(new Integer(i));
612	>	mustAdd(p, i);
613		}
614		assertTrue(p.containsAll(q));
615		}
#	Line 616 | Line 618 | public class ConcurrentLinkedDequeTest e
618		* retainAll(c) retains only those elements of c and reports true if change
619		*/
620		public void testRetainAll() {
621	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
622	<	ConcurrentLinkedDeque p = populatedDeque(SIZE);
621	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
622	>	ConcurrentLinkedDeque<Item> p = populatedDeque(SIZE);
623		for (int i = 0; i < SIZE; ++i) {
624		boolean changed = q.retainAll(p);
625		if (i == 0)
#	Line 626 | Line 628 | public class ConcurrentLinkedDequeTest e
628		assertTrue(changed);
629
630		assertTrue(q.containsAll(p));
631	<	assertEquals(SIZE-i, q.size());
631	>	mustEqual(SIZE - i, q.size());
632		p.remove();
633		}
634		}
#	Line 636 | Line 638 | public class ConcurrentLinkedDequeTest e
638		*/
639		public void testRemoveAll() {
640		for (int i = 1; i < SIZE; ++i) {
641	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
642	<	ConcurrentLinkedDeque p = populatedDeque(i);
641	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
642	>	ConcurrentLinkedDeque<Item> p = populatedDeque(i);
643		assertTrue(q.removeAll(p));
644	<	assertEquals(SIZE-i, q.size());
644	>	mustEqual(SIZE - i, q.size());
645		for (int j = 0; j < i; ++j) {
646	<	Integer x = (Integer)(p.remove());
645	<	assertFalse(q.contains(x));
646	>	mustNotContain(q, p.remove());
647		}
648		}
649		}
#	Line 651 | Line 652 | public class ConcurrentLinkedDequeTest e
652		* toArray() contains all elements in FIFO order
653		*/
654		public void testToArray() {
655	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
656	<	Object[] o = q.toArray();
657	<	for (int i = 0; i < o.length; i++)
658	<	assertSame(o[i], q.poll());
655	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
656	>	Object[] a = q.toArray();
657	>	assertSame(Object[].class, a.getClass());
658	>	for (Object o : a)
659	>	assertSame(o, q.poll());
660	>	assertTrue(q.isEmpty());
661		}
662
663		/**
664		* toArray(a) contains all elements in FIFO order
665		*/
666		public void testToArray2() {
667	<	ConcurrentLinkedDeque<Integer> q = populatedDeque(SIZE);
668	<	Integer[] ints = new Integer[SIZE];
669	<	Integer[] array = q.toArray(ints);
670	<	assertSame(ints, array);
671	<	for (int i = 0; i < ints.length; i++)
672	<	assertSame(ints[i], q.poll());
667	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
668	>	Item[] items = new Item[SIZE];
669	>	Item[] array = q.toArray(items);
670	>	assertSame(items, array);
671	>	for (Item o : items)
672	>	assertSame(o, q.poll());
673	>	assertTrue(q.isEmpty());
674		}
675
676		/**
677		* toArray(null) throws NullPointerException
678		*/
679		public void testToArray_NullArg() {
680	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
680	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
681		try {
682	<	q.toArray(null);
682	>	q.toArray((Object[])null);
683		shouldThrow();
684		} catch (NullPointerException success) {}
685		}
#	Line 683 | Line 687 | public class ConcurrentLinkedDequeTest e
687		/**
688		* toArray(incompatible array type) throws ArrayStoreException
689		*/
690	<	public void testToArray1_BadArg() {
691	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
690	>	@SuppressWarnings("CollectionToArraySafeParameter")
691	>	public void testToArray_incompatibleArrayType() {
692	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
693		try {
694		q.toArray(new String[10]);
695		shouldThrow();
#	Line 695 | Line 700 | public class ConcurrentLinkedDequeTest e
700		* Iterator iterates through all elements
701		*/
702		public void testIterator() {
703	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
704	<	Iterator it = q.iterator();
703	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
704	>	Iterator<Item> it = q.iterator();
705		int i;
706		for (i = 0; it.hasNext(); i++)
707	<	assertTrue(q.contains(it.next()));
708	<	assertEquals(i, SIZE);
707	>	mustContain(q, it.next());
708	>	mustEqual(i, SIZE);
709		assertIteratorExhausted(it);
710		}
711
#	Line 708 | Line 713 | public class ConcurrentLinkedDequeTest e
713		* iterator of empty collection has no elements
714		*/
715		public void testEmptyIterator() {
716	<	Deque c = new ConcurrentLinkedDeque();
716	>	Deque<Item> c = new ConcurrentLinkedDeque<>();
717		assertIteratorExhausted(c.iterator());
718		assertIteratorExhausted(c.descendingIterator());
719		}
#	Line 717 | Line 722 | public class ConcurrentLinkedDequeTest e
722		* Iterator ordering is FIFO
723		*/
724		public void testIteratorOrdering() {
725	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
725	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
726		q.add(one);
727		q.add(two);
728		q.add(three);
729
730		int k = 0;
731	<	for (Iterator it = q.iterator(); it.hasNext();) {
732	<	assertEquals(++k, it.next());
731	>	for (Iterator<? extends Item> it = q.iterator(); it.hasNext();) {
732	>	mustEqual(++k, it.next());
733		}
734
735	<	assertEquals(3, k);
735	>	mustEqual(3, k);
736		}
737
738		/**
739		* Modifications do not cause iterators to fail
740		*/
741		public void testWeaklyConsistentIteration() {
742	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
742	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
743		q.add(one);
744		q.add(two);
745		q.add(three);
746
747	<	for (Iterator it = q.iterator(); it.hasNext();) {
747	>	for (Iterator<? extends Item> it = q.iterator(); it.hasNext();) {
748		q.remove();
749		it.next();
750		}
751
752	<	assertEquals("deque should be empty again", 0, q.size());
752	>	mustEqual(0, q.size());
753		}
754
755		/**
756		* iterator.remove() removes current element
757		*/
758		public void testIteratorRemove() {
759	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
759	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
760		final Random rng = new Random();
761		for (int iters = 0; iters < 100; ++iters) {
762		int max = rng.nextInt(5) + 2;
763	<	int split = rng.nextInt(max-1) + 1;
763	>	int split = rng.nextInt(max - 1) + 1;
764		for (int j = 1; j <= max; ++j)
765	<	q.add(new Integer(j));
766	<	Iterator it = q.iterator();
765	>	mustAdd(q, j);
766	>	Iterator<? extends Item> it = q.iterator();
767		for (int j = 1; j <= split; ++j)
768	<	assertEquals(it.next(), new Integer(j));
768	>	mustEqual(it.next(), j);
769		it.remove();
770	<	assertEquals(it.next(), new Integer(split+1));
770	>	mustEqual(it.next(), itemFor(split + 1));
771		for (int j = 1; j <= split; ++j)
772	<	q.remove(new Integer(j));
772	>	q.remove(itemFor(j));
773		it = q.iterator();
774	<	for (int j = split+1; j <= max; ++j) {
775	<	assertEquals(it.next(), new Integer(j));
774	>	for (int j = split + 1; j <= max; ++j) {
775	>	mustEqual(it.next(), j);
776		it.remove();
777		}
778		assertFalse(it.hasNext());
#	Line 779 | Line 784 | public class ConcurrentLinkedDequeTest e
784		* Descending iterator iterates through all elements
785		*/
786		public void testDescendingIterator() {
787	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
787	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
788		int i = 0;
789	<	Iterator it = q.descendingIterator();
789	>	Iterator<? extends Item> it = q.descendingIterator();
790		while (it.hasNext()) {
791	<	assertTrue(q.contains(it.next()));
791	>	mustContain(q, it.next());
792		++i;
793		}
794	<	assertEquals(i, SIZE);
794	>	mustEqual(i, SIZE);
795		assertFalse(it.hasNext());
796		try {
797		it.next();
#	Line 798 | Line 803 | public class ConcurrentLinkedDequeTest e
803		* Descending iterator ordering is reverse FIFO
804		*/
805		public void testDescendingIteratorOrdering() {
806	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
806	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
807		for (int iters = 0; iters < 100; ++iters) {
808	<	q.add(new Integer(3));
809	<	q.add(new Integer(2));
810	<	q.add(new Integer(1));
808	>	mustAdd(q, three);
809	>	mustAdd(q, two);
810	>	mustAdd(q, one);
811		int k = 0;
812	<	for (Iterator it = q.descendingIterator(); it.hasNext();) {
813	<	assertEquals(++k, it.next());
812	>	for (Iterator<? extends Item> it = q.descendingIterator(); it.hasNext();) {
813	>	mustEqual(++k, it.next());
814		}
815
816	<	assertEquals(3, k);
816	>	mustEqual(3, k);
817		q.remove();
818		q.remove();
819		q.remove();
#	Line 819 | Line 824 | public class ConcurrentLinkedDequeTest e
824		* descendingIterator.remove() removes current element
825		*/
826		public void testDescendingIteratorRemove() {
827	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
827	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<>();
828		final Random rng = new Random();
829		for (int iters = 0; iters < 100; ++iters) {
830		int max = rng.nextInt(5) + 2;
831	<	int split = rng.nextInt(max-1) + 1;
831	>	int split = rng.nextInt(max - 1) + 1;
832		for (int j = max; j >= 1; --j)
833	<	q.add(new Integer(j));
834	<	Iterator it = q.descendingIterator();
833	>	mustAdd(q, j);
834	>	Iterator<? extends Item> it = q.descendingIterator();
835		for (int j = 1; j <= split; ++j)
836	<	assertEquals(it.next(), new Integer(j));
836	>	mustEqual(it.next(), j);
837		it.remove();
838	<	assertEquals(it.next(), new Integer(split+1));
838	>	mustEqual(it.next(), itemFor(split + 1));
839		for (int j = 1; j <= split; ++j)
840	<	q.remove(new Integer(j));
840	>	q.remove(itemFor(j));
841		it = q.descendingIterator();
842	<	for (int j = split+1; j <= max; ++j) {
843	<	assertEquals(it.next(), new Integer(j));
842	>	for (int j = split + 1; j <= max; ++j) {
843	>	mustEqual(it.next(), j);
844		it.remove();
845		}
846		assertFalse(it.hasNext());
#	Line 847 | Line 852 | public class ConcurrentLinkedDequeTest e
852		* toString() contains toStrings of elements
853		*/
854		public void testToString() {
855	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
855	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
856		String s = q.toString();
857		for (int i = 0; i < SIZE; ++i) {
858		assertTrue(s.contains(String.valueOf(i)));
#	Line 855 | Line 860 | public class ConcurrentLinkedDequeTest e
860		}
861
862		/**
863	<	* A deserialized serialized deque has same elements in same order
863	>	* A deserialized/reserialized deque has same elements in same order
864		*/
865		public void testSerialization() throws Exception {
866	<	Queue x = populatedDeque(SIZE);
867	<	Queue y = serialClone(x);
866	>	Queue<Item> x = populatedDeque(SIZE);
867	>	Queue<Item> y = serialClone(x);
868
869		assertNotSame(x, y);
870	<	assertEquals(x.size(), y.size());
871	<	assertEquals(x.toString(), y.toString());
870	>	mustEqual(x.size(), y.size());
871	>	mustEqual(x.toString(), y.toString());
872		assertTrue(Arrays.equals(x.toArray(), y.toArray()));
873		while (!x.isEmpty()) {
874		assertFalse(y.isEmpty());
875	<	assertEquals(x.remove(), y.remove());
875	>	mustEqual(x.remove(), y.remove());
876		}
877		assertTrue(y.isEmpty());
878		}
#	Line 878 | Line 883 | public class ConcurrentLinkedDequeTest e
883		*/
884		public void testNeverContainsNull() {
885		Deque<?>[] qs = {
886	<	new ConcurrentLinkedDeque<Object>(),
886	>	new ConcurrentLinkedDeque<>(),
887		populatedDeque(2),
888		};
889
#	Line 898 | Line 903 | public class ConcurrentLinkedDequeTest e
903		} catch (NullPointerException success) {}
904		}
905		}
906	+
907	+	void runAsync(Runnable r1, Runnable r2) {
908	+	boolean b = randomBoolean();
909	+	CompletableFuture<Void> f1 = CompletableFuture.runAsync(b ? r1 : r2);
910	+	CompletableFuture<Void> f2 = CompletableFuture.runAsync(b ? r2 : r1);
911	+	f1.join();
912	+	f2.join();
913	+	}
914	+
915	+	/**
916	+	* Non-traversing Deque operations are linearizable.
917	+	* https://bugs.openjdk.java.net/browse/JDK-8188900
918	+	* ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8188900 tck
919	+	*/
920	+	public void testBug8188900() {
921	+	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
922	+	final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
923	+	for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
924	+	ConcurrentLinkedDeque<Item> d = new ConcurrentLinkedDeque<>();
925	+
926	+	boolean peek = rnd.nextBoolean();
927	+	Runnable getter = () -> {
928	+	Item x = peek ? d.peekFirst() : d.pollFirst();
929	+	if (x == null) nulls.increment();
930	+	else if (x.value == 0) zeros.increment();
931	+	else
932	+	throw new AssertionError(
933	+	String.format(
934	+	"unexpected value %s after %d nulls and %d zeros",
935	+	x, nulls.sum(), zeros.sum()));
936	+	};
937	+
938	+	Runnable adder = () -> { d.addFirst(zero); d.addLast(fortytwo); };
939	+
940	+	runAsync(getter, adder);
941	+	}
942	+	}
943	+
944	+	/**
945	+	* Reverse direction variant of testBug8188900
946	+	*/
947	+	public void testBug8188900_reverse() {
948	+	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
949	+	final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
950	+	for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
951	+	ConcurrentLinkedDeque<Item> d = new ConcurrentLinkedDeque<>();
952	+
953	+	boolean peek = rnd.nextBoolean();
954	+	Runnable getter = () -> {
955	+	Item x = peek ? d.peekLast() : d.pollLast();
956	+	if (x == null) nulls.increment();
957	+	else if (x.value == 0) zeros.increment();
958	+	else
959	+	throw new AssertionError(
960	+	String.format(
961	+	"unexpected value %s after %d nulls and %d zeros",
962	+	x, nulls.sum(), zeros.sum()));
963	+	};
964	+
965	+	Runnable adder = () -> { d.addLast(zero); d.addFirst(fortytwo); };
966	+
967	+	runAsync(getter, adder);
968	+	}
969	+	}
970	+
971	+	/**
972	+	* Non-traversing Deque operations (that return null) are linearizable.
973	+	* Don't return null when the deque is observably never empty.
974	+	* https://bugs.openjdk.java.net/browse/JDK-8189387
975	+	* ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8189387 tck
976	+	*/
977	+	public void testBug8189387() {
978	+	Object x = new Object();
979	+	for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
980	+	ConcurrentLinkedDeque<Object> d = new ConcurrentLinkedDeque<>();
981	+	Runnable add = chooseRandomly(
982	+	() -> d.addFirst(x),
983	+	() -> d.offerFirst(x),
984	+	() -> d.addLast(x),
985	+	() -> d.offerLast(x));
986	+
987	+	Runnable get = chooseRandomly(
988	+	() -> assertFalse(d.isEmpty()),
989	+	() -> assertSame(x, d.peekFirst()),
990	+	() -> assertSame(x, d.peekLast()),
991	+	() -> assertSame(x, d.pollFirst()),
992	+	() -> assertSame(x, d.pollLast()));
993	+
994	+	Runnable addRemove = chooseRandomly(
995	+	() -> { d.addFirst(x); d.pollLast(); },
996	+	() -> { d.offerFirst(x); d.removeFirst(); },
997	+	() -> { d.offerLast(x); d.removeLast(); },
998	+	() -> { d.addLast(x); d.pollFirst(); });
999	+
1000	+	add.run();
1001	+	runAsync(get, addRemove);
1002	+	}
1003	+	}
1004		}

Diff Legend

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