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

Diff Legend

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