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.24 by jsr166, Sun Oct 16 20:44:18 2016 UTC vs.
Revision 1.37 by dl, Tue Jan 26 13:33:05 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
#	Line 28 | Line 30 | public class ConcurrentLinkedDequeTest e
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; }
33	>	public Object makeElement(int i) { return JSR166TestCase.itemFor(i); }
34		public boolean isConcurrent() { return true; }
35		public boolean permitsNulls() { return false; }
36		}
#	Line 38 | Line 40 | public class ConcurrentLinkedDequeTest e
40
41		/**
42		* Returns a new deque of given size containing consecutive
43	<	* Integers 0 ... n - 1.
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());
52	<	assertEquals((Integer) 0, q.peekFirst());
53	<	assertEquals((Integer) (n - 1), q.peekLast());
51	>	mustEqual(n, q.size());
52	>	mustEqual(0, q.peekFirst());
53	>	mustEqual((n - 1), q.peekLast());
54		return q;
55		}
56
#	Line 56 | 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 65 | 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 75 | Line 77 | public class ConcurrentLinkedDequeTest e
77		*/
78		public void testConstructor4() {
79		try {
80	<	new ConcurrentLinkedDeque(Arrays.asList(new Integer[SIZE]));
80	>	new ConcurrentLinkedDeque<Item>(Arrays.asList(new Item[SIZE]));
81		shouldThrow();
82		} catch (NullPointerException success) {}
83		}
#	Line 84 | 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];
88	<	for (int i = 0; i < SIZE - 1; ++i)
89	<	ints[i] = new Integer(i);
89	>	Item[] items = new Item[2]; items[0] = zero;
90		try {
91	<	new ConcurrentLinkedDeque(Arrays.asList(ints));
91	>	new ConcurrentLinkedDeque<Item>(Arrays.asList(items));
92		shouldThrow();
93		} catch (NullPointerException success) {}
94		}
#	Line 97 | 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];
100	>	Item[] items = defaultItems;
101	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>(Arrays.asList(items));
102		for (int i = 0; i < SIZE; ++i)
103	<	ints[i] = new Integer(i);
103	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque(Arrays.asList(ints));
104	<	for (int i = 0; i < SIZE; ++i)
105	<	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<Item>();
111		assertTrue(q.isEmpty());
112		q.add(one);
113		assertFalse(q.isEmpty());
#	Line 123 | 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 138 | Line 136 | public class ConcurrentLinkedDequeTest e
136		* push(null) throws NPE
137		*/
138		public void testPushNull() {
139	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
139	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
140		try {
141		q.push(null);
142		shouldThrow();
#	Line 149 | 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 159 | 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 173 | Line 171 | public class ConcurrentLinkedDequeTest e
171		* offer(null) throws NPE
172		*/
173		public void testOfferNull() {
174	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
174	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
175		try {
176		q.offer(null);
177		shouldThrow();
#	Line 184 | Line 182 | public class ConcurrentLinkedDequeTest e
182		* offerFirst(null) throws NPE
183		*/
184		public void testOfferFirstNull() {
185	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
185	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
186		try {
187		q.offerFirst(null);
188		shouldThrow();
#	Line 195 | Line 193 | public class ConcurrentLinkedDequeTest e
193		* offerLast(null) throws NPE
194		*/
195		public void testOfferLastNull() {
196	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
196	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
197		try {
198		q.offerLast(null);
199		shouldThrow();
#	Line 206 | 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<Item>();
208		assertTrue(q.offer(zero));
209		assertTrue(q.offer(one));
210		assertSame(zero, q.peekFirst());
#	Line 217 | 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<Item>();
219		assertTrue(q.offerFirst(zero));
220		assertTrue(q.offerFirst(one));
221		assertSame(one, q.peekFirst());
#	Line 228 | 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<Item>();
230		assertTrue(q.offerLast(zero));
231		assertTrue(q.offerLast(one));
232		assertSame(zero, q.peekFirst());
#	Line 239 | Line 237 | public class ConcurrentLinkedDequeTest e
237		* add(null) throws NPE
238		*/
239		public void testAddNull() {
240	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
240	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
241		try {
242		q.add(null);
243		shouldThrow();
#	Line 250 | Line 248 | public class ConcurrentLinkedDequeTest e
248		* addFirst(null) throws NPE
249		*/
250		public void testAddFirstNull() {
251	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
251	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
252		try {
253		q.addFirst(null);
254		shouldThrow();
#	Line 261 | Line 259 | public class ConcurrentLinkedDequeTest e
259		* addLast(null) throws NPE
260		*/
261		public void testAddLastNull() {
262	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
262	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
263		try {
264		q.addLast(null);
265		shouldThrow();
#	Line 272 | 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<Item>();
274		assertTrue(q.add(zero));
275		assertTrue(q.add(one));
276		assertSame(zero, q.peekFirst());
#	Line 283 | 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<Item>();
285		q.addFirst(zero);
286		q.addFirst(one);
287		assertSame(one, q.peekFirst());
#	Line 294 | 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<Item>();
296		q.addLast(zero);
297		q.addLast(one);
298		assertSame(zero, q.peekFirst());
#	Line 305 | Line 303 | public class ConcurrentLinkedDequeTest e
303		* addAll(null) throws NPE
304		*/
305		public void testAddAll1() {
306	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
306	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
307		try {
308		q.addAll(null);
309		shouldThrow();
#	Line 313 | Line 311 | public class ConcurrentLinkedDequeTest e
311		}
312
313		/**
314	<	* addAll(this) throws IAE
314	>	* addAll(this) throws IllegalArgumentException
315		*/
316		public void testAddAllSelf() {
317	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
317	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
318		try {
319		q.addAll(q);
320		shouldThrow();
#	Line 327 | Line 325 | public class ConcurrentLinkedDequeTest e
325		* addAll of a collection with null elements throws NPE
326		*/
327		public void testAddAll2() {
328	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
328	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
329		try {
330	<	q.addAll(Arrays.asList(new Integer[SIZE]));
330	>	q.addAll(Arrays.asList(new Item[SIZE]));
331		shouldThrow();
332		} catch (NullPointerException success) {}
333		}
#	Line 339 | Line 337 | public class ConcurrentLinkedDequeTest e
337		* possibly adding some elements
338		*/
339		public void testAddAll3() {
340	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
341	<	Integer[] ints = new Integer[SIZE];
344	<	for (int i = 0; i < SIZE - 1; ++i)
345	<	ints[i] = new Integer(i);
340	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
341	>	Item[] items = new Item[2]; items[0] = zero;
342		try {
343	<	q.addAll(Arrays.asList(ints));
343	>	q.addAll(Arrays.asList(items));
344		shouldThrow();
345		} catch (NullPointerException success) {}
346		}
#	Line 353 | 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)
359	<	ints[i] = new Integer(i);
360	<	ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
352	>	Item[] empty = new Item[0];
353	>	Item[] items = defaultItems;
354	>	ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
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 379 | Line 373 | public class ConcurrentLinkedDequeTest e
373		* pollLast() succeeds unless empty
374		*/
375		public void testPollLast() {
376	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
376	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
377		for (int i = SIZE - 1; i >= 0; --i) {
378	<	assertEquals(i, q.pollLast());
378	>	mustEqual(i, q.pollLast());
379		}
380		assertNull(q.pollLast());
381		}
#	Line 390 | 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 401 | 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 415 | 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 430 | 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 444 | 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 465 | 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 479 | 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);
476	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
477		for (int i = SIZE - 1; i >= 0; --i) {
478	<	assertEquals(i, q.peekLast());
479	<	assertEquals(i, q.pollLast());
478	>	mustEqual(i, q.peekLast());
479	>	mustEqual(i, q.pollLast());
480		assertTrue(q.peekLast() == null ||
481		!q.peekLast().equals(i));
482		}
#	Line 493 | 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 508 | 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);
505	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
506		for (int i = SIZE - 1; i >= 0; --i) {
507	<	assertEquals(i, q.getLast());
508	<	assertEquals(i, q.pollLast());
507	>	mustEqual(i, q.getLast());
508	>	mustEqual(i, q.pollLast());
509		}
510		try {
511		q.getLast();
#	Line 524 | 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 539 | 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 554 | 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 569 | 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 584 | 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 596 | 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 610 | 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<Item>();
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 624 | 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 634 | 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 644 | 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());
653	<	assertFalse(q.contains(x));
646	>	mustNotContain(q, p.remove());
647		}
648		}
649		}
#	Line 659 | 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 692 | Line 688 | public class ConcurrentLinkedDequeTest e
688		* toArray(incompatible array type) throws ArrayStoreException
689		*/
690		public void testToArray1_BadArg() {
691	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
691	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
692		try {
693		q.toArray(new String[10]);
694		shouldThrow();
#	Line 703 | Line 699 | public class ConcurrentLinkedDequeTest e
699		* Iterator iterates through all elements
700		*/
701		public void testIterator() {
702	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
703	<	Iterator it = q.iterator();
702	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
703	>	Iterator<Item> it = q.iterator();
704		int i;
705		for (i = 0; it.hasNext(); i++)
706	<	assertTrue(q.contains(it.next()));
707	<	assertEquals(i, SIZE);
706	>	mustContain(q, it.next());
707	>	mustEqual(i, SIZE);
708		assertIteratorExhausted(it);
709		}
710
#	Line 716 | Line 712 | public class ConcurrentLinkedDequeTest e
712		* iterator of empty collection has no elements
713		*/
714		public void testEmptyIterator() {
715	<	Deque c = new ConcurrentLinkedDeque();
715	>	Deque<Item> c = new ConcurrentLinkedDeque<Item>();
716		assertIteratorExhausted(c.iterator());
717		assertIteratorExhausted(c.descendingIterator());
718		}
#	Line 725 | Line 721 | public class ConcurrentLinkedDequeTest e
721		* Iterator ordering is FIFO
722		*/
723		public void testIteratorOrdering() {
724	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
724	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
725		q.add(one);
726		q.add(two);
727		q.add(three);
728
729		int k = 0;
730	<	for (Iterator it = q.iterator(); it.hasNext();) {
731	<	assertEquals(++k, it.next());
730	>	for (Iterator<? extends Item> it = q.iterator(); it.hasNext();) {
731	>	mustEqual(++k, it.next());
732		}
733
734	<	assertEquals(3, k);
734	>	mustEqual(3, k);
735		}
736
737		/**
738		* Modifications do not cause iterators to fail
739		*/
740		public void testWeaklyConsistentIteration() {
741	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
741	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
742		q.add(one);
743		q.add(two);
744		q.add(three);
745
746	<	for (Iterator it = q.iterator(); it.hasNext();) {
746	>	for (Iterator<? extends Item> it = q.iterator(); it.hasNext();) {
747		q.remove();
748		it.next();
749		}
750
751	<	assertEquals("deque should be empty again", 0, q.size());
751	>	mustEqual(0, q.size());
752		}
753
754		/**
755		* iterator.remove() removes current element
756		*/
757		public void testIteratorRemove() {
758	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
758	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
759		final Random rng = new Random();
760		for (int iters = 0; iters < 100; ++iters) {
761		int max = rng.nextInt(5) + 2;
762		int split = rng.nextInt(max - 1) + 1;
763		for (int j = 1; j <= max; ++j)
764	<	q.add(new Integer(j));
765	<	Iterator it = q.iterator();
764	>	mustAdd(q, j);
765	>	Iterator<? extends Item> it = q.iterator();
766		for (int j = 1; j <= split; ++j)
767	<	assertEquals(it.next(), new Integer(j));
767	>	mustEqual(it.next(), j);
768		it.remove();
769	<	assertEquals(it.next(), new Integer(split + 1));
769	>	mustEqual(it.next(), itemFor(split + 1));
770		for (int j = 1; j <= split; ++j)
771	<	q.remove(new Integer(j));
771	>	q.remove(itemFor(j));
772		it = q.iterator();
773		for (int j = split + 1; j <= max; ++j) {
774	<	assertEquals(it.next(), new Integer(j));
774	>	mustEqual(it.next(), j);
775		it.remove();
776		}
777		assertFalse(it.hasNext());
#	Line 787 | Line 783 | public class ConcurrentLinkedDequeTest e
783		* Descending iterator iterates through all elements
784		*/
785		public void testDescendingIterator() {
786	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
786	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
787		int i = 0;
788	<	Iterator it = q.descendingIterator();
788	>	Iterator<? extends Item> it = q.descendingIterator();
789		while (it.hasNext()) {
790	<	assertTrue(q.contains(it.next()));
790	>	mustContain(q, it.next());
791		++i;
792		}
793	<	assertEquals(i, SIZE);
793	>	mustEqual(i, SIZE);
794		assertFalse(it.hasNext());
795		try {
796		it.next();
#	Line 806 | Line 802 | public class ConcurrentLinkedDequeTest e
802		* Descending iterator ordering is reverse FIFO
803		*/
804		public void testDescendingIteratorOrdering() {
805	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
805	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
806		for (int iters = 0; iters < 100; ++iters) {
807	<	q.add(new Integer(3));
808	<	q.add(new Integer(2));
809	<	q.add(new Integer(1));
807	>	mustAdd(q, three);
808	>	mustAdd(q, two);
809	>	mustAdd(q, one);
810		int k = 0;
811	<	for (Iterator it = q.descendingIterator(); it.hasNext();) {
812	<	assertEquals(++k, it.next());
811	>	for (Iterator<? extends Item> it = q.descendingIterator(); it.hasNext();) {
812	>	mustEqual(++k, it.next());
813		}
814
815	<	assertEquals(3, k);
815	>	mustEqual(3, k);
816		q.remove();
817		q.remove();
818		q.remove();
#	Line 827 | Line 823 | public class ConcurrentLinkedDequeTest e
823		* descendingIterator.remove() removes current element
824		*/
825		public void testDescendingIteratorRemove() {
826	<	final ConcurrentLinkedDeque q = new ConcurrentLinkedDeque();
826	>	final ConcurrentLinkedDeque<Item> q = new ConcurrentLinkedDeque<Item>();
827		final Random rng = new Random();
828		for (int iters = 0; iters < 100; ++iters) {
829		int max = rng.nextInt(5) + 2;
830		int split = rng.nextInt(max - 1) + 1;
831		for (int j = max; j >= 1; --j)
832	<	q.add(new Integer(j));
833	<	Iterator it = q.descendingIterator();
832	>	mustAdd(q, j);
833	>	Iterator<? extends Item> it = q.descendingIterator();
834		for (int j = 1; j <= split; ++j)
835	<	assertEquals(it.next(), new Integer(j));
835	>	mustEqual(it.next(), j);
836		it.remove();
837	<	assertEquals(it.next(), new Integer(split + 1));
837	>	mustEqual(it.next(), itemFor(split + 1));
838		for (int j = 1; j <= split; ++j)
839	<	q.remove(new Integer(j));
839	>	q.remove(itemFor(j));
840		it = q.descendingIterator();
841		for (int j = split + 1; j <= max; ++j) {
842	<	assertEquals(it.next(), new Integer(j));
842	>	mustEqual(it.next(), j);
843		it.remove();
844		}
845		assertFalse(it.hasNext());
#	Line 855 | Line 851 | public class ConcurrentLinkedDequeTest e
851		* toString() contains toStrings of elements
852		*/
853		public void testToString() {
854	<	ConcurrentLinkedDeque q = populatedDeque(SIZE);
854	>	ConcurrentLinkedDeque<Item> q = populatedDeque(SIZE);
855		String s = q.toString();
856		for (int i = 0; i < SIZE; ++i) {
857		assertTrue(s.contains(String.valueOf(i)));
#	Line 863 | Line 859 | public class ConcurrentLinkedDequeTest e
859		}
860
861		/**
862	<	* A deserialized serialized deque has same elements in same order
862	>	* A deserialized/reserialized deque has same elements in same order
863		*/
864		public void testSerialization() throws Exception {
865	<	Queue x = populatedDeque(SIZE);
866	<	Queue y = serialClone(x);
865	>	Queue<Item> x = populatedDeque(SIZE);
866	>	Queue<Item> y = serialClone(x);
867
868		assertNotSame(x, y);
869	<	assertEquals(x.size(), y.size());
870	<	assertEquals(x.toString(), y.toString());
869	>	mustEqual(x.size(), y.size());
870	>	mustEqual(x.toString(), y.toString());
871		assertTrue(Arrays.equals(x.toArray(), y.toArray()));
872		while (!x.isEmpty()) {
873		assertFalse(y.isEmpty());
874	<	assertEquals(x.remove(), y.remove());
874	>	mustEqual(x.remove(), y.remove());
875		}
876		assertTrue(y.isEmpty());
877		}
#	Line 906 | Line 902 | public class ConcurrentLinkedDequeTest e
902		} catch (NullPointerException success) {}
903		}
904		}
905	+
906	+	void runAsync(Runnable r1, Runnable r2) {
907	+	boolean b = randomBoolean();
908	+	CompletableFuture<Void> f1 = CompletableFuture.runAsync(b ? r1 : r2);
909	+	CompletableFuture<Void> f2 = CompletableFuture.runAsync(b ? r2 : r1);
910	+	f1.join();
911	+	f2.join();
912	+	}
913	+
914	+	/**
915	+	* Non-traversing Deque operations are linearizable.
916	+	* https://bugs.openjdk.java.net/browse/JDK-8188900
917	+	* ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8188900 tck
918	+	*/
919	+	public void testBug8188900() {
920	+	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
921	+	final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
922	+	for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
923	+	ConcurrentLinkedDeque<Item> d = new ConcurrentLinkedDeque<>();
924	+
925	+	boolean peek = rnd.nextBoolean();
926	+	Runnable getter = () -> {
927	+	Item x = peek ? d.peekFirst() : d.pollFirst();
928	+	if (x == null) nulls.increment();
929	+	else if (x.value == 0) zeros.increment();
930	+	else
931	+	throw new AssertionError(
932	+	String.format(
933	+	"unexpected value %d after %d nulls and %d zeros",
934	+	x, nulls.sum(), zeros.sum()));
935	+	};
936	+
937	+	Runnable adder = () -> { d.addFirst(zero); d.addLast(fortytwo); };
938	+
939	+	runAsync(getter, adder);
940	+	}
941	+	}
942	+
943	+	/**
944	+	* Reverse direction variant of testBug8188900
945	+	*/
946	+	public void testBug8188900_reverse() {
947	+	final ThreadLocalRandom rnd = ThreadLocalRandom.current();
948	+	final LongAdder nulls = new LongAdder(), zeros = new LongAdder();
949	+	for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
950	+	ConcurrentLinkedDeque<Item> d = new ConcurrentLinkedDeque<>();
951	+
952	+	boolean peek = rnd.nextBoolean();
953	+	Runnable getter = () -> {
954	+	Item x = peek ? d.peekLast() : d.pollLast();
955	+	if (x == null) nulls.increment();
956	+	else if (x.value == 0) zeros.increment();
957	+	else
958	+	throw new AssertionError(
959	+	String.format(
960	+	"unexpected value %d after %d nulls and %d zeros",
961	+	x, nulls.sum(), zeros.sum()));
962	+	};
963	+
964	+	Runnable adder = () -> { d.addLast(zero); d.addFirst(fortytwo); };
965	+
966	+	runAsync(getter, adder);
967	+	}
968	+	}
969	+
970	+	/**
971	+	* Non-traversing Deque operations (that return null) are linearizable.
972	+	* Don't return null when the deque is observably never empty.
973	+	* https://bugs.openjdk.java.net/browse/JDK-8189387
974	+	* ant -Djsr166.expensiveTests=true -Djsr166.tckTestClass=ConcurrentLinkedDequeTest -Djsr166.methodFilter=testBug8189387 tck
975	+	*/
976	+	public void testBug8189387() {
977	+	Object x = new Object();
978	+	for (int n = expensiveTests ? 100_000 : 10; n--> 0; ) {
979	+	ConcurrentLinkedDeque<Object> d = new ConcurrentLinkedDeque<>();
980	+	Runnable add = chooseRandomly(
981	+	() -> d.addFirst(x),
982	+	() -> d.offerFirst(x),
983	+	() -> d.addLast(x),
984	+	() -> d.offerLast(x));
985	+
986	+	Runnable get = chooseRandomly(
987	+	() -> assertFalse(d.isEmpty()),
988	+	() -> assertSame(x, d.peekFirst()),
989	+	() -> assertSame(x, d.peekLast()),
990	+	() -> assertSame(x, d.pollFirst()),
991	+	() -> assertSame(x, d.pollLast()));
992	+
993	+	Runnable addRemove = chooseRandomly(
994	+	() -> { d.addFirst(x); d.pollLast(); },
995	+	() -> { d.offerFirst(x); d.removeFirst(); },
996	+	() -> { d.offerLast(x); d.removeLast(); },
997	+	() -> { d.addLast(x); d.pollFirst(); });
998	+
999	+	add.run();
1000	+	runAsync(get, addRemove);
1001	+	}
1002	+	}
1003		}

Diff Legend

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