ViewVC Help

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

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

Comparing jsr166/src/test/tck/ConcurrentSkipListMapTest.java (file contents):
Revision 1.5 by dl, Sat Oct 1 17:05:38 2005 UTC vs.
Revision 1.41 by jsr166, Wed Aug 23 05:33:00 2017 UTC

#	Line 1 | Line 1
1		/*
2		* Written by Doug Lea with assistance from members of JCP JSR-166
3		* Expert Group and released to the public domain, as explained at
4	<	* http://creativecommons.org/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7	<	import junit.framework.*;
8	<	import java.util.*;
9	<	import java.util.concurrent.*;
10	<	import java.io.*;
7	>	import java.util.ArrayList;
8	>	import java.util.Arrays;
9	>	import java.util.BitSet;
10	>	import java.util.Collection;
11	>	import java.util.Iterator;
12	>	import java.util.Map;
13	>	import java.util.NavigableMap;
14	>	import java.util.NavigableSet;
15	>	import java.util.NoSuchElementException;
16	>	import java.util.Random;
17	>	import java.util.Set;
18	>	import java.util.concurrent.ConcurrentSkipListMap;
19	>
20	>	import junit.framework.Test;
21
22		public class ConcurrentSkipListMapTest extends JSR166TestCase {
23		public static void main(String[] args) {
24	<	junit.textui.TestRunner.run (suite());
24	>	main(suite(), args);
25		}
26		public static Test suite() {
27	<	return new TestSuite(ConcurrentSkipListMapTest.class);
27	>	class Implementation implements MapImplementation {
28	>	public Class<?> klazz() { return ConcurrentSkipListMap.class; }
29	>	public Map emptyMap() { return new ConcurrentSkipListMap(); }
30	>	public Object makeKey(int i) { return i; }
31	>	public Object makeValue(int i) { return i; }
32	>	public boolean isConcurrent() { return true; }
33	>	public boolean permitsNullKeys() { return false; }
34	>	public boolean permitsNullValues() { return false; }
35	>	public boolean supportsSetValue() { return false; }
36	>	}
37	>	return newTestSuite(
38	>	ConcurrentSkipListMapTest.class,
39	>	MapTest.testSuite(new Implementation()));
40		}
41
42		/**
43	<	* Create a map from Integers 1-5 to Strings "A"-"E".
43	>	* Returns a new map from Integers 1-5 to Strings "A"-"E".
44		*/
45	<	private static ConcurrentSkipListMap map5() {
46	<	ConcurrentSkipListMap map = new ConcurrentSkipListMap();
45	>	private static ConcurrentSkipListMap map5() {
46	>	ConcurrentSkipListMap map = new ConcurrentSkipListMap();
47		assertTrue(map.isEmpty());
48	<	map.put(one, "A");
49	<	map.put(five, "E");
50	<	map.put(three, "C");
51	<	map.put(two, "B");
52	<	map.put(four, "D");
48	>	map.put(one, "A");
49	>	map.put(five, "E");
50	>	map.put(three, "C");
51	>	map.put(two, "B");
52	>	map.put(four, "D");
53		assertFalse(map.isEmpty());
54		assertEquals(5, map.size());
55	<	return map;
55	>	return map;
56		}
57
58		/**
59	<	*  clear removes all pairs
59	>	* clear removes all pairs
60		*/
61		public void testClear() {
62		ConcurrentSkipListMap map = map5();
63	<	map.clear();
64	<	assertEquals(map.size(), 0);
63	>	map.clear();
64	>	assertEquals(0, map.size());
65		}
66
67		/**
68	<	*
68	>	* copy constructor creates map equal to source map
69		*/
70		public void testConstructFromSorted() {
71		ConcurrentSkipListMap map = map5();
#	Line 52 | Line 74 | public class ConcurrentSkipListMapTest e
74		}
75
76		/**
77	<	*  Maps with same contents are equal
77	>	* Maps with same contents are equal
78		*/
79		public void testEquals() {
80		ConcurrentSkipListMap map1 = map5();
81		ConcurrentSkipListMap map2 = map5();
82		assertEquals(map1, map2);
83		assertEquals(map2, map1);
84	<	map1.clear();
84	>	map1.clear();
85		assertFalse(map1.equals(map2));
86		assertFalse(map2.equals(map1));
87		}
88
89		/**
90	<	*  containsKey returns true for contained key
90	>	* containsKey returns true for contained key
91		*/
92		public void testContainsKey() {
93		ConcurrentSkipListMap map = map5();
94	<	assertTrue(map.containsKey(one));
94	>	assertTrue(map.containsKey(one));
95		assertFalse(map.containsKey(zero));
96		}
97
98		/**
99	<	*  containsValue returns true for held values
99	>	* containsValue returns true for held values
100		*/
101		public void testContainsValue() {
102		ConcurrentSkipListMap map = map5();
103	<	assertTrue(map.containsValue("A"));
103	>	assertTrue(map.containsValue("A"));
104		assertFalse(map.containsValue("Z"));
105		}
106
107		/**
108	<	*  get returns the correct element at the given key,
109	<	*  or null if not present
108	>	* get returns the correct element at the given key,
109	>	* or null if not present
110		*/
111		public void testGet() {
112		ConcurrentSkipListMap map = map5();
113	<	assertEquals("A", (String)map.get(one));
113	>	assertEquals("A", (String)map.get(one));
114		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
115		assertNull(empty.get(one));
116		}
117
118		/**
119	<	*  isEmpty is true of empty map and false for non-empty
119	>	* isEmpty is true of empty map and false for non-empty
120		*/
121		public void testIsEmpty() {
122		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
123		ConcurrentSkipListMap map = map5();
124	<	assertTrue(empty.isEmpty());
124	>	assertTrue(empty.isEmpty());
125		assertFalse(map.isEmpty());
126		}
127
128		/**
129	<	*   firstKey returns first key
129	>	* firstKey returns first key
130		*/
131		public void testFirstKey() {
132		ConcurrentSkipListMap map = map5();
133	<	assertEquals(one, map.firstKey());
133	>	assertEquals(one, map.firstKey());
134		}
135
136		/**
137	<	*   lastKey returns last key
137	>	* lastKey returns last key
138		*/
139		public void testLastKey() {
140		ConcurrentSkipListMap map = map5();
141	<	assertEquals(five, map.lastKey());
141	>	assertEquals(five, map.lastKey());
142		}
143
122	–
144		/**
145	<	*  keySet.toArray returns contains all keys
145	>	* keySet.toArray returns contains all keys
146		*/
147		public void testKeySetToArray() {
148		ConcurrentSkipListMap map = map5();
149	<	Set s = map.keySet();
149	>	Set s = map.keySet();
150		Object[] ar = s.toArray();
151		assertTrue(s.containsAll(Arrays.asList(ar)));
152	<	assertEquals(5, ar.length);
152	>	assertEquals(5, ar.length);
153		ar[0] = m10;
154		assertFalse(s.containsAll(Arrays.asList(ar)));
155		}
156
157		/**
158	<	*  descendingkeySet.toArray returns contains all keys
158	>	* descendingkeySet.toArray returns contains all keys
159		*/
160		public void testDescendingKeySetToArray() {
161		ConcurrentSkipListMap map = map5();
162	<	Set s = map.descendingKeySet();
162	>	Set s = map.descendingKeySet();
163		Object[] ar = s.toArray();
164	<	assertEquals(5, ar.length);
164	>	assertEquals(5, ar.length);
165		assertTrue(s.containsAll(Arrays.asList(ar)));
166		ar[0] = m10;
167		assertFalse(s.containsAll(Arrays.asList(ar)));
168		}
169
170		/**
171	<	*   keySet returns a Set containing all the keys
171	>	* keySet returns a Set containing all the keys
172		*/
173		public void testKeySet() {
174		ConcurrentSkipListMap map = map5();
175	<	Set s = map.keySet();
176	<	assertEquals(5, s.size());
177	<	assertTrue(s.contains(one));
178	<	assertTrue(s.contains(two));
179	<	assertTrue(s.contains(three));
180	<	assertTrue(s.contains(four));
181	<	assertTrue(s.contains(five));
175	>	Set s = map.keySet();
176	>	assertEquals(5, s.size());
177	>	assertTrue(s.contains(one));
178	>	assertTrue(s.contains(two));
179	>	assertTrue(s.contains(three));
180	>	assertTrue(s.contains(four));
181	>	assertTrue(s.contains(five));
182		}
183
184		/**
185	<	*   keySet is ordered
185	>	* keySet is ordered
186		*/
187		public void testKeySetOrder() {
188		ConcurrentSkipListMap map = map5();
189	<	Set s = map.keySet();
189	>	Set s = map.keySet();
190		Iterator i = s.iterator();
191		Integer last = (Integer)i.next();
192		assertEquals(last, one);
193	+	int count = 1;
194		while (i.hasNext()) {
195		Integer k = (Integer)i.next();
196		assertTrue(last.compareTo(k) < 0);
197		last = k;
198	+	++count;
199	+	}
200	+	assertEquals(5, count);
201	+	}
202	+
203	+	/**
204	+	* descending iterator of key set is inverse ordered
205	+	*/
206	+	public void testKeySetDescendingIteratorOrder() {
207	+	ConcurrentSkipListMap map = map5();
208	+	NavigableSet s = map.navigableKeySet();
209	+	Iterator i = s.descendingIterator();
210	+	Integer last = (Integer)i.next();
211	+	assertEquals(last, five);
212	+	int count = 1;
213	+	while (i.hasNext()) {
214	+	Integer k = (Integer)i.next();
215	+	assertTrue(last.compareTo(k) > 0);
216	+	last = k;
217	+	++count;
218		}
219	+	assertEquals(5, count);
220		}
221
222		/**
223	<	*   descendingKeySet is ordered
223	>	* descendingKeySet is ordered
224		*/
225		public void testDescendingKeySetOrder() {
226		ConcurrentSkipListMap map = map5();
227	<	Set s = map.descendingKeySet();
227	>	Set s = map.descendingKeySet();
228		Iterator i = s.iterator();
229		Integer last = (Integer)i.next();
230		assertEquals(last, five);
231	+	int count = 1;
232		while (i.hasNext()) {
233		Integer k = (Integer)i.next();
234		assertTrue(last.compareTo(k) > 0);
235		last = k;
236	+	++count;
237		}
238	+	assertEquals(5, count);
239		}
240
241	+	/**
242	+	* descending iterator of descendingKeySet is ordered
243	+	*/
244	+	public void testDescendingKeySetDescendingIteratorOrder() {
245	+	ConcurrentSkipListMap map = map5();
246	+	NavigableSet s = map.descendingKeySet();
247	+	Iterator i = s.descendingIterator();
248	+	Integer last = (Integer)i.next();
249	+	assertEquals(last, one);
250	+	int count = 1;
251	+	while (i.hasNext()) {
252	+	Integer k = (Integer)i.next();
253	+	assertTrue(last.compareTo(k) < 0);
254	+	last = k;
255	+	++count;
256	+	}
257	+	assertEquals(5, count);
258	+	}
259
260		/**
261	<	*  Values.toArray contains all values
261	>	* Values.toArray contains all values
262		*/
263		public void testValuesToArray() {
264		ConcurrentSkipListMap map = map5();
265	<	Collection v = map.values();
265	>	Collection v = map.values();
266		Object[] ar = v.toArray();
267		ArrayList s = new ArrayList(Arrays.asList(ar));
268	<	assertEquals(5, ar.length);
269	<	assertTrue(s.contains("A"));
270	<	assertTrue(s.contains("B"));
271	<	assertTrue(s.contains("C"));
272	<	assertTrue(s.contains("D"));
273	<	assertTrue(s.contains("E"));
268	>	assertEquals(5, ar.length);
269	>	assertTrue(s.contains("A"));
270	>	assertTrue(s.contains("B"));
271	>	assertTrue(s.contains("C"));
272	>	assertTrue(s.contains("D"));
273	>	assertTrue(s.contains("E"));
274		}
275
276		/**
#	Line 214 | Line 278 | public class ConcurrentSkipListMapTest e
278		*/
279		public void testValues() {
280		ConcurrentSkipListMap map = map5();
281	<	Collection s = map.values();
282	<	assertEquals(5, s.size());
283	<	assertTrue(s.contains("A"));
284	<	assertTrue(s.contains("B"));
285	<	assertTrue(s.contains("C"));
286	<	assertTrue(s.contains("D"));
287	<	assertTrue(s.contains("E"));
281	>	Collection s = map.values();
282	>	assertEquals(5, s.size());
283	>	assertTrue(s.contains("A"));
284	>	assertTrue(s.contains("B"));
285	>	assertTrue(s.contains("C"));
286	>	assertTrue(s.contains("D"));
287	>	assertTrue(s.contains("E"));
288		}
289
290		/**
#	Line 228 | Line 292 | public class ConcurrentSkipListMapTest e
292		*/
293		public void testEntrySet() {
294		ConcurrentSkipListMap map = map5();
295	<	Set s = map.entrySet();
296	<	assertEquals(5, s.size());
295	>	Set s = map.entrySet();
296	>	assertEquals(5, s.size());
297		Iterator it = s.iterator();
298		while (it.hasNext()) {
299		Map.Entry e = (Map.Entry) it.next();
300	<	assertTrue(
300	>	assertTrue(
301		(e.getKey().equals(one) && e.getValue().equals("A")) ||
302		(e.getKey().equals(two) && e.getValue().equals("B")) ||
303		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 247 | Line 311 | public class ConcurrentSkipListMapTest e
311		*/
312		public void testDescendingEntrySet() {
313		ConcurrentSkipListMap map = map5();
314	<	Set s = map.descendingEntrySet();
315	<	assertEquals(5, s.size());
314	>	Set s = map.descendingMap().entrySet();
315	>	assertEquals(5, s.size());
316		Iterator it = s.iterator();
317		while (it.hasNext()) {
318		Map.Entry e = (Map.Entry) it.next();
319	<	assertTrue(
319	>	assertTrue(
320		(e.getKey().equals(one) && e.getValue().equals("A")) ||
321		(e.getKey().equals(two) && e.getValue().equals("B")) ||
322		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 262 | Line 326 | public class ConcurrentSkipListMapTest e
326		}
327
328		/**
329	<	*  entrySet.toArray contains all entries
329	>	* entrySet.toArray contains all entries
330		*/
331		public void testEntrySetToArray() {
332		ConcurrentSkipListMap map = map5();
333	<	Set s = map.entrySet();
333	>	Set s = map.entrySet();
334		Object[] ar = s.toArray();
335		assertEquals(5, ar.length);
336		for (int i = 0; i < 5; ++i) {
#	Line 276 | Line 340 | public class ConcurrentSkipListMapTest e
340		}
341
342		/**
343	<	*  descendingEntrySet.toArray contains all entries
343	>	* descendingEntrySet.toArray contains all entries
344		*/
345		public void testDescendingEntrySetToArray() {
346		ConcurrentSkipListMap map = map5();
347	<	Set s = map.descendingEntrySet();
347	>	Set s = map.descendingMap().entrySet();
348		Object[] ar = s.toArray();
349		assertEquals(5, ar.length);
350		for (int i = 0; i < 5; ++i) {
#	Line 290 | Line 354 | public class ConcurrentSkipListMapTest e
354		}
355
356		/**
357	<	*   putAll  adds all key-value pairs from the given map
357	>	* putAll adds all key-value pairs from the given map
358		*/
359		public void testPutAll() {
360		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
361		ConcurrentSkipListMap map = map5();
362	<	empty.putAll(map);
363	<	assertEquals(5, empty.size());
364	<	assertTrue(empty.containsKey(one));
365	<	assertTrue(empty.containsKey(two));
366	<	assertTrue(empty.containsKey(three));
367	<	assertTrue(empty.containsKey(four));
368	<	assertTrue(empty.containsKey(five));
362	>	empty.putAll(map);
363	>	assertEquals(5, empty.size());
364	>	assertTrue(empty.containsKey(one));
365	>	assertTrue(empty.containsKey(two));
366	>	assertTrue(empty.containsKey(three));
367	>	assertTrue(empty.containsKey(four));
368	>	assertTrue(empty.containsKey(five));
369		}
370
371		/**
372	<	*   putIfAbsent works when the given key is not present
372	>	* putIfAbsent works when the given key is not present
373		*/
374		public void testPutIfAbsent() {
375		ConcurrentSkipListMap map = map5();
376	<	map.putIfAbsent(six, "Z");
376	>	map.putIfAbsent(six, "Z");
377		assertTrue(map.containsKey(six));
378		}
379
380		/**
381	<	*   putIfAbsent does not add the pair if the key is already present
381	>	* putIfAbsent does not add the pair if the key is already present
382		*/
383		public void testPutIfAbsent2() {
384		ConcurrentSkipListMap map = map5();
#	Line 322 | Line 386 | public class ConcurrentSkipListMapTest e
386		}
387
388		/**
389	<	*   replace fails when the given key is not present
389	>	* replace fails when the given key is not present
390		*/
391		public void testReplace() {
392		ConcurrentSkipListMap map = map5();
393	<	assertNull(map.replace(six, "Z"));
393	>	assertNull(map.replace(six, "Z"));
394		assertFalse(map.containsKey(six));
395		}
396
397		/**
398	<	*   replace succeeds if the key is already present
398	>	* replace succeeds if the key is already present
399		*/
400		public void testReplace2() {
401		ConcurrentSkipListMap map = map5();
#	Line 339 | Line 403 | public class ConcurrentSkipListMapTest e
403		assertEquals("Z", map.get(one));
404		}
405
342	–
406		/**
407		* replace value fails when the given key not mapped to expected value
408		*/
409		public void testReplaceValue() {
410		ConcurrentSkipListMap map = map5();
411		assertEquals("A", map.get(one));
412	<	assertFalse(map.replace(one, "Z", "Z"));
412	>	assertFalse(map.replace(one, "Z", "Z"));
413		assertEquals("A", map.get(one));
414		}
415
#	Line 356 | Line 419 | public class ConcurrentSkipListMapTest e
419		public void testReplaceValue2() {
420		ConcurrentSkipListMap map = map5();
421		assertEquals("A", map.get(one));
422	<	assertTrue(map.replace(one, "A", "Z"));
422	>	assertTrue(map.replace(one, "A", "Z"));
423		assertEquals("Z", map.get(one));
424		}
425
363	–
426		/**
427	<	*   remove removes the correct key-value pair from the map
427	>	* remove removes the correct key-value pair from the map
428		*/
429		public void testRemove() {
430		ConcurrentSkipListMap map = map5();
431	<	map.remove(five);
432	<	assertEquals(4, map.size());
433	<	assertFalse(map.containsKey(five));
431	>	map.remove(five);
432	>	assertEquals(4, map.size());
433	>	assertFalse(map.containsKey(five));
434		}
435
436		/**
#	Line 376 | Line 438 | public class ConcurrentSkipListMapTest e
438		*/
439		public void testRemove2() {
440		ConcurrentSkipListMap map = map5();
441	<	assertTrue(map.containsKey(five));
441	>	assertTrue(map.containsKey(five));
442		assertEquals("E", map.get(five));
443	<	map.remove(five, "E");
444	<	assertEquals(4, map.size());
445	<	assertFalse(map.containsKey(five));
446	<	map.remove(four, "A");
447	<	assertEquals(4, map.size());
448	<	assertTrue(map.containsKey(four));
387	<
443	>	map.remove(five, "E");
444	>	assertEquals(4, map.size());
445	>	assertFalse(map.containsKey(five));
446	>	map.remove(four, "A");
447	>	assertEquals(4, map.size());
448	>	assertTrue(map.containsKey(four));
449		}
450
451		/**
#	Line 403 | Line 464 | public class ConcurrentSkipListMapTest e
464
465		Map.Entry e4 = map.lowerEntry(zero);
466		assertNull(e4);
406	–
467		}
468
469		/**
#	Line 422 | Line 482 | public class ConcurrentSkipListMapTest e
482
483		Map.Entry e4 = map.higherEntry(six);
484		assertNull(e4);
425	–
485		}
486
487		/**
#	Line 441 | Line 500 | public class ConcurrentSkipListMapTest e
500
501		Map.Entry e4 = map.floorEntry(zero);
502		assertNull(e4);
444	–
503		}
504
505		/**
#	Line 460 | Line 518 | public class ConcurrentSkipListMapTest e
518
519		Map.Entry e4 = map.ceilingEntry(six);
520		assertNull(e4);
463	–
521		}
522
523		/**
524		* lowerEntry, higherEntry, ceilingEntry, and floorEntry return
525	<	* imutable entries
525	>	* immutable entries
526		*/
527	<	public void testEntryImmutablity() {
527	>	public void testEntryImmutability() {
528		ConcurrentSkipListMap map = map5();
529		Map.Entry e = map.lowerEntry(three);
530		assertEquals(two, e.getKey());
531		try {
532		e.setValue("X");
533	<	fail();
534	<	} catch(UnsupportedOperationException success) {}
533	>	shouldThrow();
534	>	} catch (UnsupportedOperationException success) {}
535		e = map.higherEntry(zero);
536		assertEquals(one, e.getKey());
537		try {
538		e.setValue("X");
539	<	fail();
540	<	} catch(UnsupportedOperationException success) {}
539	>	shouldThrow();
540	>	} catch (UnsupportedOperationException success) {}
541		e = map.floorEntry(one);
542		assertEquals(one, e.getKey());
543		try {
544		e.setValue("X");
545	<	fail();
546	<	} catch(UnsupportedOperationException success) {}
545	>	shouldThrow();
546	>	} catch (UnsupportedOperationException success) {}
547		e = map.ceilingEntry(five);
548		assertEquals(five, e.getKey());
549		try {
550		e.setValue("X");
551	<	fail();
552	<	} catch(UnsupportedOperationException success) {}
551	>	shouldThrow();
552	>	} catch (UnsupportedOperationException success) {}
553		}
554
498	–
499	–
555		/**
556		* lowerKey returns preceding element
557		*/
#	Line 513 | Line 568 | public class ConcurrentSkipListMapTest e
568
569		Object e4 = q.lowerKey(zero);
570		assertNull(e4);
516	–
571		}
572
573		/**
#	Line 532 | Line 586 | public class ConcurrentSkipListMapTest e
586
587		Object e4 = q.higherKey(six);
588		assertNull(e4);
535	–
589		}
590
591		/**
#	Line 551 | Line 604 | public class ConcurrentSkipListMapTest e
604
605		Object e4 = q.floorKey(zero);
606		assertNull(e4);
554	–
607		}
608
609		/**
#	Line 570 | Line 622 | public class ConcurrentSkipListMapTest e
622
623		Object e4 = q.ceilingKey(six);
624		assertNull(e4);
573	–
625		}
626
627		/**
#	Line 595 | Line 646 | public class ConcurrentSkipListMapTest e
646		try {
647		e.setValue("A");
648		shouldThrow();
649	<	} catch (Exception ok) {
599	<	}
649	>	} catch (UnsupportedOperationException success) {}
650		e = map.pollFirstEntry();
651		assertNull(e);
652		}
#	Line 623 | Line 673 | public class ConcurrentSkipListMapTest e
673		try {
674		e.setValue("E");
675		shouldThrow();
676	<	} catch (Exception ok) {
627	<	}
676	>	} catch (UnsupportedOperationException success) {}
677		e = map.pollLastEntry();
678		assertNull(e);
679		}
680
681		/**
682	<	*   size returns the correct values
682	>	* size returns the correct values
683		*/
684		public void testSize() {
685		ConcurrentSkipListMap map = map5();
686		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
687	<	assertEquals(0, empty.size());
688	<	assertEquals(5, map.size());
687	>	assertEquals(0, empty.size());
688	>	assertEquals(5, map.size());
689		}
690
691		/**
#	Line 646 | Line 695 | public class ConcurrentSkipListMapTest e
695		ConcurrentSkipListMap map = map5();
696		String s = map.toString();
697		for (int i = 1; i <= 5; ++i) {
698	<	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
698	>	assertTrue(s.contains(String.valueOf(i)));
699		}
700	<	}
700	>	}
701
702		// Exception tests
703
#	Line 656 | Line 705 | public class ConcurrentSkipListMapTest e
705		* get(null) of nonempty map throws NPE
706		*/
707		public void testGet_NullPointerException() {
708	+	ConcurrentSkipListMap c = map5();
709		try {
660	–	ConcurrentSkipListMap c = map5();
710		c.get(null);
711		shouldThrow();
712	<	} catch(NullPointerException e){}
712	>	} catch (NullPointerException success) {}
713		}
714
715		/**
716		* containsKey(null) of nonempty map throws NPE
717		*/
718		public void testContainsKey_NullPointerException() {
719	+	ConcurrentSkipListMap c = map5();
720		try {
671	–	ConcurrentSkipListMap c = map5();
721		c.containsKey(null);
722		shouldThrow();
723	<	} catch(NullPointerException e){}
723	>	} catch (NullPointerException success) {}
724		}
725
726		/**
727		* containsValue(null) throws NPE
728		*/
729		public void testContainsValue_NullPointerException() {
730	+	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
731		try {
682	–	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
732		c.containsValue(null);
733		shouldThrow();
734	<	} catch(NullPointerException e){}
734	>	} catch (NullPointerException success) {}
735		}
736
688	–
737		/**
738		* put(null,x) throws NPE
739		*/
740		public void testPut1_NullPointerException() {
741	+	ConcurrentSkipListMap c = map5();
742		try {
694	–	ConcurrentSkipListMap c = map5();
743		c.put(null, "whatever");
744		shouldThrow();
745	<	} catch(NullPointerException e){}
745	>	} catch (NullPointerException success) {}
746		}
747
748		/**
749		* putIfAbsent(null, x) throws NPE
750		*/
751		public void testPutIfAbsent1_NullPointerException() {
752	+	ConcurrentSkipListMap c = map5();
753		try {
705	–	ConcurrentSkipListMap c = map5();
754		c.putIfAbsent(null, "whatever");
755		shouldThrow();
756	<	} catch(NullPointerException e){}
756	>	} catch (NullPointerException success) {}
757		}
758
759		/**
760		* replace(null, x) throws NPE
761		*/
762		public void testReplace_NullPointerException() {
763	+	ConcurrentSkipListMap c = map5();
764		try {
716	–	ConcurrentSkipListMap c = map5();
765		c.replace(null, "whatever");
766		shouldThrow();
767	<	} catch(NullPointerException e){}
767	>	} catch (NullPointerException success) {}
768		}
769
770		/**
771		* replace(null, x, y) throws NPE
772		*/
773		public void testReplaceValue_NullPointerException() {
774	+	ConcurrentSkipListMap c = map5();
775		try {
727	–	ConcurrentSkipListMap c = map5();
776		c.replace(null, one, "whatever");
777		shouldThrow();
778	<	} catch(NullPointerException e){}
778	>	} catch (NullPointerException success) {}
779		}
780
781		/**
782		* remove(null) throws NPE
783		*/
784		public void testRemove1_NullPointerException() {
785	+	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
786	+	c.put("sadsdf", "asdads");
787		try {
738	–	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
739	–	c.put("sadsdf", "asdads");
788		c.remove(null);
789		shouldThrow();
790	<	} catch(NullPointerException e){}
790	>	} catch (NullPointerException success) {}
791		}
792
793		/**
794		* remove(null, x) throws NPE
795		*/
796		public void testRemove2_NullPointerException() {
797	+	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
798	+	c.put("sadsdf", "asdads");
799		try {
750	–	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
751	–	c.put("sadsdf", "asdads");
800		c.remove(null, "whatever");
801		shouldThrow();
802	<	} catch(NullPointerException e){}
802	>	} catch (NullPointerException success) {}
803		}
804
805		/**
806		* remove(x, null) returns false
807		*/
808		public void testRemove3() {
809	<	try {
810	<	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
811	<	c.put("sadsdf", "asdads");
764	<	assertFalse(c.remove("sadsdf", null));
765	<	} catch(NullPointerException e){
766	<	fail();
767	<	}
809	>	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
810	>	c.put("sadsdf", "asdads");
811	>	assertFalse(c.remove("sadsdf", null));
812		}
813
814		/**
815	<	* A deserialized map equals original
815	>	* A cloned map equals original
816		*/
817	<	public void testSerialization() {
818	<	ConcurrentSkipListMap q = map5();
817	>	public void testClone() {
818	>	ConcurrentSkipListMap x = map5();
819	>	ConcurrentSkipListMap y = x.clone();
820
821	<	try {
822	<	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
823	<	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
824	<	out.writeObject(q);
825	<	out.close();
826	<
827	<	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
828	<	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
784	<	ConcurrentSkipListMap r = (ConcurrentSkipListMap)in.readObject();
785	<	assertEquals(q.size(), r.size());
786	<	assertTrue(q.equals(r));
787	<	assertTrue(r.equals(q));
788	<	} catch(Exception e){
789	<	e.printStackTrace();
790	<	unexpectedException();
791	<	}
821	>	assertNotSame(x, y);
822	>	assertEquals(x.size(), y.size());
823	>	assertEquals(x.toString(), y.toString());
824	>	assertEquals(x, y);
825	>	assertEquals(y, x);
826	>	y.clear();
827	>	assertTrue(y.isEmpty());
828	>	assertFalse(x.equals(y));
829		}
830
831	+	/**
832	+	* A deserialized/reserialized map equals original
833	+	*/
834	+	public void testSerialization() throws Exception {
835	+	NavigableMap x = map5();
836	+	NavigableMap y = serialClone(x);
837
838	+	assertNotSame(x, y);
839	+	assertEquals(x.size(), y.size());
840	+	assertEquals(x.toString(), y.toString());
841	+	assertEquals(x, y);
842	+	assertEquals(y, x);
843	+	y.clear();
844	+	assertTrue(y.isEmpty());
845	+	assertFalse(x.equals(y));
846	+	}
847
848		/**
849		* subMap returns map with keys in requested range
850		*/
851		public void testSubMapContents() {
852		ConcurrentSkipListMap map = map5();
853	<	NavigableMap sm = map.navigableSubMap(two, four);
853	>	NavigableMap sm = map.subMap(two, true, four, false);
854		assertEquals(two, sm.firstKey());
855		assertEquals(three, sm.lastKey());
856		assertEquals(2, sm.size());
#	Line 820 | Line 872 | public class ConcurrentSkipListMapTest e
872		k = (Integer)(r.next());
873		assertEquals(two, k);
874		assertFalse(r.hasNext());
875	<
875	>
876		Iterator j = sm.keySet().iterator();
877		j.next();
878		j.remove();
#	Line 829 | Line 881 | public class ConcurrentSkipListMapTest e
881		assertEquals(1, sm.size());
882		assertEquals(three, sm.firstKey());
883		assertEquals(three, sm.lastKey());
884	<	assertTrue(sm.remove(three) != null);
884	>	assertEquals("C", sm.remove(three));
885		assertTrue(sm.isEmpty());
886		assertEquals(3, map.size());
887		}
888
889		public void testSubMapContents2() {
890		ConcurrentSkipListMap map = map5();
891	<	NavigableMap sm = map.navigableSubMap(two, three);
891	>	NavigableMap sm = map.subMap(two, true, three, false);
892		assertEquals(1, sm.size());
893		assertEquals(two, sm.firstKey());
894		assertEquals(two, sm.lastKey());
#	Line 854 | Line 906 | public class ConcurrentSkipListMapTest e
906		k = (Integer)(r.next());
907		assertEquals(two, k);
908		assertFalse(r.hasNext());
909	<
909	>
910		Iterator j = sm.keySet().iterator();
911		j.next();
912		j.remove();
#	Line 862 | Line 914 | public class ConcurrentSkipListMapTest e
914		assertEquals(4, map.size());
915		assertEquals(0, sm.size());
916		assertTrue(sm.isEmpty());
917	<	assertTrue(sm.remove(three) == null);
917	>	assertSame(sm.remove(three), null);
918		assertEquals(4, map.size());
919		}
920
#	Line 871 | Line 923 | public class ConcurrentSkipListMapTest e
923		*/
924		public void testHeadMapContents() {
925		ConcurrentSkipListMap map = map5();
926	<	NavigableMap sm = map.navigableHeadMap(four);
926	>	NavigableMap sm = map.headMap(four, false);
927		assertTrue(sm.containsKey(one));
928		assertTrue(sm.containsKey(two));
929		assertTrue(sm.containsKey(three));
#	Line 893 | Line 945 | public class ConcurrentSkipListMapTest e
945		}
946
947		/**
948	<	* headMap returns map with keys in requested range
948	>	* tailMap returns map with keys in requested range
949		*/
950		public void testTailMapContents() {
951		ConcurrentSkipListMap map = map5();
952	<	NavigableMap sm = map.navigableTailMap(two);
952	>	NavigableMap sm = map.tailMap(two, true);
953		assertFalse(sm.containsKey(one));
954		assertTrue(sm.containsKey(two));
955		assertTrue(sm.containsKey(three));
#	Line 941 | Line 993 | public class ConcurrentSkipListMapTest e
993		assertEquals("E", e.getValue());
994		assertFalse(i.hasNext());
995
996	<	NavigableMap ssm = sm.navigableTailMap(four);
996	>	NavigableMap ssm = sm.tailMap(four, true);
997		assertEquals(four, ssm.firstKey());
998		assertEquals(five, ssm.lastKey());
999	<	assertTrue(ssm.remove(four) != null);
999	>	assertEquals("D", ssm.remove(four));
1000		assertEquals(1, ssm.size());
1001		assertEquals(3, sm.size());
1002		assertEquals(4, map.size());
1003		}
1004	<
1004	>
1005	>	Random rnd = new Random(666);
1006	>	BitSet bs;
1007	>
1008	>	/**
1009	>	* Submaps of submaps subdivide correctly
1010	>	*/
1011	>	public void testRecursiveSubMaps() throws Exception {
1012	>	int mapSize = expensiveTests ? 1000 : 100;
1013	>	Class cl = ConcurrentSkipListMap.class;
1014	>	NavigableMap<Integer, Integer> map = newMap(cl);
1015	>	bs = new BitSet(mapSize);
1016	>
1017	>	populate(map, mapSize);
1018	>	check(map,                 0, mapSize - 1, true);
1019	>	check(map.descendingMap(), 0, mapSize - 1, false);
1020	>
1021	>	mutateMap(map, 0, mapSize - 1);
1022	>	check(map,                 0, mapSize - 1, true);
1023	>	check(map.descendingMap(), 0, mapSize - 1, false);
1024	>
1025	>	bashSubMap(map.subMap(0, true, mapSize, false),
1026	>	0, mapSize - 1, true);
1027	>	}
1028	>
1029	>	static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception {
1030	>	NavigableMap<Integer, Integer> result =
1031	>	(NavigableMap<Integer, Integer>) cl.getConstructor().newInstance();
1032	>	assertEquals(0, result.size());
1033	>	assertFalse(result.keySet().iterator().hasNext());
1034	>	return result;
1035	>	}
1036	>
1037	>	void populate(NavigableMap<Integer, Integer> map, int limit) {
1038	>	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
1039	>	int key = rnd.nextInt(limit);
1040	>	put(map, key);
1041	>	}
1042	>	}
1043	>
1044	>	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
1045	>	int size = map.size();
1046	>	int rangeSize = max - min + 1;
1047	>
1048	>	// Remove a bunch of entries directly
1049	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1050	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1051	>	}
1052	>
1053	>	// Remove a bunch of entries with iterator
1054	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1055	>	if (rnd.nextBoolean()) {
1056	>	bs.clear(it.next());
1057	>	it.remove();
1058	>	}
1059	>	}
1060	>
1061	>	// Add entries till we're back to original size
1062	>	while (map.size() < size) {
1063	>	int key = min + rnd.nextInt(rangeSize);
1064	>	assertTrue(key >= min && key <= max);
1065	>	put(map, key);
1066	>	}
1067	>	}
1068	>
1069	>	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
1070	>	int size = map.size();
1071	>	int rangeSize = max - min + 1;
1072	>
1073	>	// Remove a bunch of entries directly
1074	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1075	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1076	>	}
1077	>
1078	>	// Remove a bunch of entries with iterator
1079	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1080	>	if (rnd.nextBoolean()) {
1081	>	bs.clear(it.next());
1082	>	it.remove();
1083	>	}
1084	>	}
1085	>
1086	>	// Add entries till we're back to original size
1087	>	while (map.size() < size) {
1088	>	int key = min - 5 + rnd.nextInt(rangeSize + 10);
1089	>	if (key >= min && key <= max) {
1090	>	put(map, key);
1091	>	} else {
1092	>	try {
1093	>	map.put(key, 2 * key);
1094	>	shouldThrow();
1095	>	} catch (IllegalArgumentException success) {}
1096	>	}
1097	>	}
1098	>	}
1099	>
1100	>	void put(NavigableMap<Integer, Integer> map, int key) {
1101	>	if (map.put(key, 2 * key) == null)
1102	>	bs.set(key);
1103	>	}
1104	>
1105	>	void remove(NavigableMap<Integer, Integer> map, int key) {
1106	>	if (map.remove(key) != null)
1107	>	bs.clear(key);
1108	>	}
1109	>
1110	>	void bashSubMap(NavigableMap<Integer, Integer> map,
1111	>	int min, int max, boolean ascending) {
1112	>	check(map, min, max, ascending);
1113	>	check(map.descendingMap(), min, max, !ascending);
1114	>
1115	>	mutateSubMap(map, min, max);
1116	>	check(map, min, max, ascending);
1117	>	check(map.descendingMap(), min, max, !ascending);
1118	>
1119	>	// Recurse
1120	>	if (max - min < 2)
1121	>	return;
1122	>	int midPoint = (min + max) / 2;
1123	>
1124	>	// headMap - pick direction and endpoint inclusion randomly
1125	>	boolean incl = rnd.nextBoolean();
1126	>	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
1127	>	if (ascending) {
1128	>	if (rnd.nextBoolean())
1129	>	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
1130	>	else
1131	>	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1132	>	false);
1133	>	} else {
1134	>	if (rnd.nextBoolean())
1135	>	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
1136	>	else
1137	>	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1138	>	true);
1139	>	}
1140	>
1141	>	// tailMap - pick direction and endpoint inclusion randomly
1142	>	incl = rnd.nextBoolean();
1143	>	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
1144	>	if (ascending) {
1145	>	if (rnd.nextBoolean())
1146	>	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
1147	>	else
1148	>	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1149	>	false);
1150	>	} else {
1151	>	if (rnd.nextBoolean()) {
1152	>	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
1153	>	} else {
1154	>	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1155	>	true);
1156	>	}
1157	>	}
1158	>
1159	>	// subMap - pick direction and endpoint inclusion randomly
1160	>	int rangeSize = max - min + 1;
1161	>	int[] endpoints = new int[2];
1162	>	endpoints[0] = min + rnd.nextInt(rangeSize);
1163	>	endpoints[1] = min + rnd.nextInt(rangeSize);
1164	>	Arrays.sort(endpoints);
1165	>	boolean lowIncl = rnd.nextBoolean();
1166	>	boolean highIncl = rnd.nextBoolean();
1167	>	if (ascending) {
1168	>	NavigableMap<Integer,Integer> sm = map.subMap(
1169	>	endpoints[0], lowIncl, endpoints[1], highIncl);
1170	>	if (rnd.nextBoolean())
1171	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1172	>	endpoints[1] - (highIncl ? 0 : 1), true);
1173	>	else
1174	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1175	>	endpoints[1] - (highIncl ? 0 : 1), false);
1176	>	} else {
1177	>	NavigableMap<Integer,Integer> sm = map.subMap(
1178	>	endpoints[1], highIncl, endpoints[0], lowIncl);
1179	>	if (rnd.nextBoolean())
1180	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1181	>	endpoints[1] - (highIncl ? 0 : 1), false);
1182	>	else
1183	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1184	>	endpoints[1] - (highIncl ? 0 : 1), true);
1185	>	}
1186	>	}
1187	>
1188	>	/**
1189	>	* min and max are both inclusive.  If max < min, interval is empty.
1190	>	*/
1191	>	void check(NavigableMap<Integer, Integer> map,
1192	>	final int min, final int max, final boolean ascending) {
1193	>	class ReferenceSet {
1194	>	int lower(int key) {
1195	>	return ascending ? lowerAscending(key) : higherAscending(key);
1196	>	}
1197	>	int floor(int key) {
1198	>	return ascending ? floorAscending(key) : ceilingAscending(key);
1199	>	}
1200	>	int ceiling(int key) {
1201	>	return ascending ? ceilingAscending(key) : floorAscending(key);
1202	>	}
1203	>	int higher(int key) {
1204	>	return ascending ? higherAscending(key) : lowerAscending(key);
1205	>	}
1206	>	int first() {
1207	>	return ascending ? firstAscending() : lastAscending();
1208	>	}
1209	>	int last() {
1210	>	return ascending ? lastAscending() : firstAscending();
1211	>	}
1212	>	int lowerAscending(int key) {
1213	>	return floorAscending(key - 1);
1214	>	}
1215	>	int floorAscending(int key) {
1216	>	if (key < min)
1217	>	return -1;
1218	>	else if (key > max)
1219	>	key = max;
1220	>
1221	>	// BitSet should support this! Test would run much faster
1222	>	while (key >= min) {
1223	>	if (bs.get(key))
1224	>	return key;
1225	>	key--;
1226	>	}
1227	>	return -1;
1228	>	}
1229	>	int ceilingAscending(int key) {
1230	>	if (key < min)
1231	>	key = min;
1232	>	else if (key > max)
1233	>	return -1;
1234	>	int result = bs.nextSetBit(key);
1235	>	return result > max ? -1 : result;
1236	>	}
1237	>	int higherAscending(int key) {
1238	>	return ceilingAscending(key + 1);
1239	>	}
1240	>	private int firstAscending() {
1241	>	int result = ceilingAscending(min);
1242	>	return result > max ? -1 : result;
1243	>	}
1244	>	private int lastAscending() {
1245	>	int result = floorAscending(max);
1246	>	return result < min ? -1 : result;
1247	>	}
1248	>	}
1249	>	ReferenceSet rs = new ReferenceSet();
1250	>
1251	>	// Test contents using containsKey
1252	>	int size = 0;
1253	>	for (int i = min; i <= max; i++) {
1254	>	boolean bsContainsI = bs.get(i);
1255	>	assertEquals(bsContainsI, map.containsKey(i));
1256	>	if (bsContainsI)
1257	>	size++;
1258	>	}
1259	>	assertEquals(size, map.size());
1260	>
1261	>	// Test contents using contains keySet iterator
1262	>	int size2 = 0;
1263	>	int previousKey = -1;
1264	>	for (int key : map.keySet()) {
1265	>	assertTrue(bs.get(key));
1266	>	size2++;
1267	>	assertTrue(previousKey < 0 ||
1268	>	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1269	>	previousKey = key;
1270	>	}
1271	>	assertEquals(size2, size);
1272	>
1273	>	// Test navigation ops
1274	>	for (int key = min - 1; key <= max + 1; key++) {
1275	>	assertEq(map.lowerKey(key), rs.lower(key));
1276	>	assertEq(map.floorKey(key), rs.floor(key));
1277	>	assertEq(map.higherKey(key), rs.higher(key));
1278	>	assertEq(map.ceilingKey(key), rs.ceiling(key));
1279	>	}
1280	>
1281	>	// Test extrema
1282	>	if (map.size() != 0) {
1283	>	assertEq(map.firstKey(), rs.first());
1284	>	assertEq(map.lastKey(), rs.last());
1285	>	} else {
1286	>	assertEq(rs.first(), -1);
1287	>	assertEq(rs.last(),  -1);
1288	>	try {
1289	>	map.firstKey();
1290	>	shouldThrow();
1291	>	} catch (NoSuchElementException success) {}
1292	>	try {
1293	>	map.lastKey();
1294	>	shouldThrow();
1295	>	} catch (NoSuchElementException success) {}
1296	>	}
1297	>	}
1298	>
1299	>	static void assertEq(Integer i, int j) {
1300	>	if (i == null)
1301	>	assertEquals(j, -1);
1302	>	else
1303	>	assertEquals((int) i, j);
1304	>	}
1305	>
1306	>	static boolean eq(Integer i, int j) {
1307	>	return (i == null) ? j == -1 : i == j;
1308	>	}
1309	>
1310		}

Diff Legend

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