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.24 by jsr166, Fri May 27 19:21:27 2011 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.*;
#	Line 11 | Line 11 | import java.io.*;
11
12		public class ConcurrentSkipListMapTest extends JSR166TestCase {
13		public static void main(String[] args) {
14	<	junit.textui.TestRunner.run (suite());
14	>	junit.textui.TestRunner.run(suite());
15		}
16		public static Test suite() {
17	<	return new TestSuite(ConcurrentSkipListMapTest.class);
17	>	return new TestSuite(ConcurrentSkipListMapTest.class);
18		}
19
20		/**
21		* Create a map from Integers 1-5 to Strings "A"-"E".
22		*/
23	<	private static ConcurrentSkipListMap map5() {
24	<	ConcurrentSkipListMap map = new ConcurrentSkipListMap();
23	>	private static ConcurrentSkipListMap map5() {
24	>	ConcurrentSkipListMap map = new ConcurrentSkipListMap();
25		assertTrue(map.isEmpty());
26	<	map.put(one, "A");
27	<	map.put(five, "E");
28	<	map.put(three, "C");
29	<	map.put(two, "B");
30	<	map.put(four, "D");
26	>	map.put(one, "A");
27	>	map.put(five, "E");
28	>	map.put(three, "C");
29	>	map.put(two, "B");
30	>	map.put(four, "D");
31		assertFalse(map.isEmpty());
32		assertEquals(5, map.size());
33	<	return map;
33	>	return map;
34		}
35
36		/**
37	<	*  clear removes all pairs
37	>	* clear removes all pairs
38		*/
39		public void testClear() {
40		ConcurrentSkipListMap map = map5();
41	<	map.clear();
42	<	assertEquals(map.size(), 0);
41	>	map.clear();
42	>	assertEquals(map.size(), 0);
43		}
44
45		/**
46	<	*
46	>	*
47		*/
48		public void testConstructFromSorted() {
49		ConcurrentSkipListMap map = map5();
#	Line 52 | Line 52 | public class ConcurrentSkipListMapTest e
52		}
53
54		/**
55	<	*  Maps with same contents are equal
55	>	* Maps with same contents are equal
56		*/
57		public void testEquals() {
58		ConcurrentSkipListMap map1 = map5();
59		ConcurrentSkipListMap map2 = map5();
60		assertEquals(map1, map2);
61		assertEquals(map2, map1);
62	<	map1.clear();
62	>	map1.clear();
63		assertFalse(map1.equals(map2));
64		assertFalse(map2.equals(map1));
65		}
66
67		/**
68	<	*  containsKey returns true for contained key
68	>	* containsKey returns true for contained key
69		*/
70		public void testContainsKey() {
71		ConcurrentSkipListMap map = map5();
72	<	assertTrue(map.containsKey(one));
72	>	assertTrue(map.containsKey(one));
73		assertFalse(map.containsKey(zero));
74		}
75
76		/**
77	<	*  containsValue returns true for held values
77	>	* containsValue returns true for held values
78		*/
79		public void testContainsValue() {
80		ConcurrentSkipListMap map = map5();
81	<	assertTrue(map.containsValue("A"));
81	>	assertTrue(map.containsValue("A"));
82		assertFalse(map.containsValue("Z"));
83		}
84
85		/**
86	<	*  get returns the correct element at the given key,
87	<	*  or null if not present
86	>	* get returns the correct element at the given key,
87	>	* or null if not present
88		*/
89		public void testGet() {
90		ConcurrentSkipListMap map = map5();
91	<	assertEquals("A", (String)map.get(one));
91	>	assertEquals("A", (String)map.get(one));
92		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
93		assertNull(empty.get(one));
94		}
95
96		/**
97	<	*  isEmpty is true of empty map and false for non-empty
97	>	* isEmpty is true of empty map and false for non-empty
98		*/
99		public void testIsEmpty() {
100		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
101		ConcurrentSkipListMap map = map5();
102	<	assertTrue(empty.isEmpty());
102	>	assertTrue(empty.isEmpty());
103		assertFalse(map.isEmpty());
104		}
105
106		/**
107	<	*   firstKey returns first key
107	>	* firstKey returns first key
108		*/
109		public void testFirstKey() {
110		ConcurrentSkipListMap map = map5();
111	<	assertEquals(one, map.firstKey());
111	>	assertEquals(one, map.firstKey());
112		}
113
114		/**
115	<	*   lastKey returns last key
115	>	* lastKey returns last key
116		*/
117		public void testLastKey() {
118		ConcurrentSkipListMap map = map5();
119	<	assertEquals(five, map.lastKey());
119	>	assertEquals(five, map.lastKey());
120		}
121
122	–
122		/**
123	<	*  keySet.toArray returns contains all keys
123	>	* keySet.toArray returns contains all keys
124		*/
125		public void testKeySetToArray() {
126		ConcurrentSkipListMap map = map5();
127	<	Set s = map.keySet();
127	>	Set s = map.keySet();
128		Object[] ar = s.toArray();
129		assertTrue(s.containsAll(Arrays.asList(ar)));
130	<	assertEquals(5, ar.length);
130	>	assertEquals(5, ar.length);
131		ar[0] = m10;
132		assertFalse(s.containsAll(Arrays.asList(ar)));
133		}
134
135		/**
136	<	*  descendingkeySet.toArray returns contains all keys
136	>	* descendingkeySet.toArray returns contains all keys
137		*/
138		public void testDescendingKeySetToArray() {
139		ConcurrentSkipListMap map = map5();
140	<	Set s = map.descendingKeySet();
140	>	Set s = map.descendingKeySet();
141		Object[] ar = s.toArray();
142	<	assertEquals(5, ar.length);
142	>	assertEquals(5, ar.length);
143		assertTrue(s.containsAll(Arrays.asList(ar)));
144		ar[0] = m10;
145		assertFalse(s.containsAll(Arrays.asList(ar)));
146		}
147
148		/**
149	<	*   keySet returns a Set containing all the keys
149	>	* keySet returns a Set containing all the keys
150		*/
151		public void testKeySet() {
152		ConcurrentSkipListMap map = map5();
153	<	Set s = map.keySet();
154	<	assertEquals(5, s.size());
155	<	assertTrue(s.contains(one));
156	<	assertTrue(s.contains(two));
157	<	assertTrue(s.contains(three));
158	<	assertTrue(s.contains(four));
159	<	assertTrue(s.contains(five));
153	>	Set s = map.keySet();
154	>	assertEquals(5, s.size());
155	>	assertTrue(s.contains(one));
156	>	assertTrue(s.contains(two));
157	>	assertTrue(s.contains(three));
158	>	assertTrue(s.contains(four));
159	>	assertTrue(s.contains(five));
160		}
161
162		/**
163	<	*   keySet is ordered
163	>	* keySet is ordered
164		*/
165		public void testKeySetOrder() {
166		ConcurrentSkipListMap map = map5();
167	<	Set s = map.keySet();
167	>	Set s = map.keySet();
168		Iterator i = s.iterator();
169		Integer last = (Integer)i.next();
170		assertEquals(last, one);
171	+	int count = 1;
172		while (i.hasNext()) {
173		Integer k = (Integer)i.next();
174		assertTrue(last.compareTo(k) < 0);
175		last = k;
176	+	++count;
177		}
178	+	assertEquals(count ,5);
179		}
180
181		/**
182	<	*   descendingKeySet is ordered
182	>	* descending iterator of key set is inverse ordered
183	>	*/
184	>	public void testKeySetDescendingIteratorOrder() {
185	>	ConcurrentSkipListMap map = map5();
186	>	NavigableSet s = map.navigableKeySet();
187	>	Iterator i = s.descendingIterator();
188	>	Integer last = (Integer)i.next();
189	>	assertEquals(last, five);
190	>	int count = 1;
191	>	while (i.hasNext()) {
192	>	Integer k = (Integer)i.next();
193	>	assertTrue(last.compareTo(k) > 0);
194	>	last = k;
195	>	++count;
196	>	}
197	>	assertEquals(count ,5);
198	>	}
199	>
200	>	/**
201	>	* descendingKeySet is ordered
202		*/
203		public void testDescendingKeySetOrder() {
204		ConcurrentSkipListMap map = map5();
205	<	Set s = map.descendingKeySet();
205	>	Set s = map.descendingKeySet();
206		Iterator i = s.iterator();
207		Integer last = (Integer)i.next();
208		assertEquals(last, five);
209	+	int count = 1;
210		while (i.hasNext()) {
211		Integer k = (Integer)i.next();
212		assertTrue(last.compareTo(k) > 0);
213		last = k;
214	+	++count;
215		}
216	+	assertEquals(count, 5);
217		}
218
219	+	/**
220	+	* descending iterator of descendingKeySet is ordered
221	+	*/
222	+	public void testDescendingKeySetDescendingIteratorOrder() {
223	+	ConcurrentSkipListMap map = map5();
224	+	NavigableSet s = map.descendingKeySet();
225	+	Iterator i = s.descendingIterator();
226	+	Integer last = (Integer)i.next();
227	+	assertEquals(last, one);
228	+	int count = 1;
229	+	while (i.hasNext()) {
230	+	Integer k = (Integer)i.next();
231	+	assertTrue(last.compareTo(k) < 0);
232	+	last = k;
233	+	++count;
234	+	}
235	+	assertEquals(count, 5);
236	+	}
237
238		/**
239	<	*  Values.toArray contains all values
239	>	* Values.toArray contains all values
240		*/
241		public void testValuesToArray() {
242		ConcurrentSkipListMap map = map5();
243	<	Collection v = map.values();
243	>	Collection v = map.values();
244		Object[] ar = v.toArray();
245		ArrayList s = new ArrayList(Arrays.asList(ar));
246	<	assertEquals(5, ar.length);
247	<	assertTrue(s.contains("A"));
248	<	assertTrue(s.contains("B"));
249	<	assertTrue(s.contains("C"));
250	<	assertTrue(s.contains("D"));
251	<	assertTrue(s.contains("E"));
246	>	assertEquals(5, ar.length);
247	>	assertTrue(s.contains("A"));
248	>	assertTrue(s.contains("B"));
249	>	assertTrue(s.contains("C"));
250	>	assertTrue(s.contains("D"));
251	>	assertTrue(s.contains("E"));
252		}
253
254		/**
#	Line 214 | Line 256 | public class ConcurrentSkipListMapTest e
256		*/
257		public void testValues() {
258		ConcurrentSkipListMap map = map5();
259	<	Collection s = map.values();
260	<	assertEquals(5, s.size());
261	<	assertTrue(s.contains("A"));
262	<	assertTrue(s.contains("B"));
263	<	assertTrue(s.contains("C"));
264	<	assertTrue(s.contains("D"));
265	<	assertTrue(s.contains("E"));
259	>	Collection s = map.values();
260	>	assertEquals(5, s.size());
261	>	assertTrue(s.contains("A"));
262	>	assertTrue(s.contains("B"));
263	>	assertTrue(s.contains("C"));
264	>	assertTrue(s.contains("D"));
265	>	assertTrue(s.contains("E"));
266		}
267
268		/**
#	Line 228 | Line 270 | public class ConcurrentSkipListMapTest e
270		*/
271		public void testEntrySet() {
272		ConcurrentSkipListMap map = map5();
273	<	Set s = map.entrySet();
274	<	assertEquals(5, s.size());
273	>	Set s = map.entrySet();
274	>	assertEquals(5, s.size());
275		Iterator it = s.iterator();
276		while (it.hasNext()) {
277		Map.Entry e = (Map.Entry) it.next();
278	<	assertTrue(
278	>	assertTrue(
279		(e.getKey().equals(one) && e.getValue().equals("A")) ||
280		(e.getKey().equals(two) && e.getValue().equals("B")) ||
281		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 247 | Line 289 | public class ConcurrentSkipListMapTest e
289		*/
290		public void testDescendingEntrySet() {
291		ConcurrentSkipListMap map = map5();
292	<	Set s = map.descendingEntrySet();
293	<	assertEquals(5, s.size());
292	>	Set s = map.descendingMap().entrySet();
293	>	assertEquals(5, s.size());
294		Iterator it = s.iterator();
295		while (it.hasNext()) {
296		Map.Entry e = (Map.Entry) it.next();
297	<	assertTrue(
297	>	assertTrue(
298		(e.getKey().equals(one) && e.getValue().equals("A")) ||
299		(e.getKey().equals(two) && e.getValue().equals("B")) ||
300		(e.getKey().equals(three) && e.getValue().equals("C")) ||
#	Line 262 | Line 304 | public class ConcurrentSkipListMapTest e
304		}
305
306		/**
307	<	*  entrySet.toArray contains all entries
307	>	* entrySet.toArray contains all entries
308		*/
309		public void testEntrySetToArray() {
310		ConcurrentSkipListMap map = map5();
311	<	Set s = map.entrySet();
311	>	Set s = map.entrySet();
312		Object[] ar = s.toArray();
313		assertEquals(5, ar.length);
314		for (int i = 0; i < 5; ++i) {
#	Line 276 | Line 318 | public class ConcurrentSkipListMapTest e
318		}
319
320		/**
321	<	*  descendingEntrySet.toArray contains all entries
321	>	* descendingEntrySet.toArray contains all entries
322		*/
323		public void testDescendingEntrySetToArray() {
324		ConcurrentSkipListMap map = map5();
325	<	Set s = map.descendingEntrySet();
325	>	Set s = map.descendingMap().entrySet();
326		Object[] ar = s.toArray();
327		assertEquals(5, ar.length);
328		for (int i = 0; i < 5; ++i) {
#	Line 290 | Line 332 | public class ConcurrentSkipListMapTest e
332		}
333
334		/**
335	<	*   putAll  adds all key-value pairs from the given map
335	>	* putAll adds all key-value pairs from the given map
336		*/
337		public void testPutAll() {
338		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
339		ConcurrentSkipListMap map = map5();
340	<	empty.putAll(map);
341	<	assertEquals(5, empty.size());
342	<	assertTrue(empty.containsKey(one));
343	<	assertTrue(empty.containsKey(two));
344	<	assertTrue(empty.containsKey(three));
345	<	assertTrue(empty.containsKey(four));
346	<	assertTrue(empty.containsKey(five));
340	>	empty.putAll(map);
341	>	assertEquals(5, empty.size());
342	>	assertTrue(empty.containsKey(one));
343	>	assertTrue(empty.containsKey(two));
344	>	assertTrue(empty.containsKey(three));
345	>	assertTrue(empty.containsKey(four));
346	>	assertTrue(empty.containsKey(five));
347		}
348
349		/**
350	<	*   putIfAbsent works when the given key is not present
350	>	* putIfAbsent works when the given key is not present
351		*/
352		public void testPutIfAbsent() {
353		ConcurrentSkipListMap map = map5();
354	<	map.putIfAbsent(six, "Z");
354	>	map.putIfAbsent(six, "Z");
355		assertTrue(map.containsKey(six));
356		}
357
358		/**
359	<	*   putIfAbsent does not add the pair if the key is already present
359	>	* putIfAbsent does not add the pair if the key is already present
360		*/
361		public void testPutIfAbsent2() {
362		ConcurrentSkipListMap map = map5();
#	Line 322 | Line 364 | public class ConcurrentSkipListMapTest e
364		}
365
366		/**
367	<	*   replace fails when the given key is not present
367	>	* replace fails when the given key is not present
368		*/
369		public void testReplace() {
370		ConcurrentSkipListMap map = map5();
371	<	assertNull(map.replace(six, "Z"));
371	>	assertNull(map.replace(six, "Z"));
372		assertFalse(map.containsKey(six));
373		}
374
375		/**
376	<	*   replace succeeds if the key is already present
376	>	* replace succeeds if the key is already present
377		*/
378		public void testReplace2() {
379		ConcurrentSkipListMap map = map5();
#	Line 339 | Line 381 | public class ConcurrentSkipListMapTest e
381		assertEquals("Z", map.get(one));
382		}
383
342	–
384		/**
385		* replace value fails when the given key not mapped to expected value
386		*/
387		public void testReplaceValue() {
388		ConcurrentSkipListMap map = map5();
389		assertEquals("A", map.get(one));
390	<	assertFalse(map.replace(one, "Z", "Z"));
390	>	assertFalse(map.replace(one, "Z", "Z"));
391		assertEquals("A", map.get(one));
392		}
393
#	Line 356 | Line 397 | public class ConcurrentSkipListMapTest e
397		public void testReplaceValue2() {
398		ConcurrentSkipListMap map = map5();
399		assertEquals("A", map.get(one));
400	<	assertTrue(map.replace(one, "A", "Z"));
400	>	assertTrue(map.replace(one, "A", "Z"));
401		assertEquals("Z", map.get(one));
402		}
403
363	–
404		/**
405	<	*   remove removes the correct key-value pair from the map
405	>	* remove removes the correct key-value pair from the map
406		*/
407		public void testRemove() {
408		ConcurrentSkipListMap map = map5();
409	<	map.remove(five);
410	<	assertEquals(4, map.size());
411	<	assertFalse(map.containsKey(five));
409	>	map.remove(five);
410	>	assertEquals(4, map.size());
411	>	assertFalse(map.containsKey(five));
412		}
413
414		/**
#	Line 376 | Line 416 | public class ConcurrentSkipListMapTest e
416		*/
417		public void testRemove2() {
418		ConcurrentSkipListMap map = map5();
419	<	assertTrue(map.containsKey(five));
419	>	assertTrue(map.containsKey(five));
420		assertEquals("E", map.get(five));
421	<	map.remove(five, "E");
422	<	assertEquals(4, map.size());
423	<	assertFalse(map.containsKey(five));
424	<	map.remove(four, "A");
425	<	assertEquals(4, map.size());
426	<	assertTrue(map.containsKey(four));
387	<
421	>	map.remove(five, "E");
422	>	assertEquals(4, map.size());
423	>	assertFalse(map.containsKey(five));
424	>	map.remove(four, "A");
425	>	assertEquals(4, map.size());
426	>	assertTrue(map.containsKey(four));
427		}
428
429		/**
#	Line 403 | Line 442 | public class ConcurrentSkipListMapTest e
442
443		Map.Entry e4 = map.lowerEntry(zero);
444		assertNull(e4);
406	–
445		}
446
447		/**
#	Line 422 | Line 460 | public class ConcurrentSkipListMapTest e
460
461		Map.Entry e4 = map.higherEntry(six);
462		assertNull(e4);
425	–
463		}
464
465		/**
#	Line 441 | Line 478 | public class ConcurrentSkipListMapTest e
478
479		Map.Entry e4 = map.floorEntry(zero);
480		assertNull(e4);
444	–
481		}
482
483		/**
#	Line 460 | Line 496 | public class ConcurrentSkipListMapTest e
496
497		Map.Entry e4 = map.ceilingEntry(six);
498		assertNull(e4);
463	–
499		}
500
501		/**
502		* lowerEntry, higherEntry, ceilingEntry, and floorEntry return
503	<	* imutable entries
503	>	* immutable entries
504		*/
505		public void testEntryImmutablity() {
506		ConcurrentSkipListMap map = map5();
#	Line 473 | Line 508 | public class ConcurrentSkipListMapTest e
508		assertEquals(two, e.getKey());
509		try {
510		e.setValue("X");
511	<	fail();
512	<	} catch(UnsupportedOperationException success) {}
511	>	shouldThrow();
512	>	} catch (UnsupportedOperationException success) {}
513		e = map.higherEntry(zero);
514		assertEquals(one, e.getKey());
515		try {
516		e.setValue("X");
517	<	fail();
518	<	} catch(UnsupportedOperationException success) {}
517	>	shouldThrow();
518	>	} catch (UnsupportedOperationException success) {}
519		e = map.floorEntry(one);
520		assertEquals(one, e.getKey());
521		try {
522		e.setValue("X");
523	<	fail();
524	<	} catch(UnsupportedOperationException success) {}
523	>	shouldThrow();
524	>	} catch (UnsupportedOperationException success) {}
525		e = map.ceilingEntry(five);
526		assertEquals(five, e.getKey());
527		try {
528		e.setValue("X");
529	<	fail();
530	<	} catch(UnsupportedOperationException success) {}
529	>	shouldThrow();
530	>	} catch (UnsupportedOperationException success) {}
531		}
532
533
499	–
534		/**
535		* lowerKey returns preceding element
536		*/
#	Line 513 | Line 547 | public class ConcurrentSkipListMapTest e
547
548		Object e4 = q.lowerKey(zero);
549		assertNull(e4);
516	–
550		}
551
552		/**
#	Line 532 | Line 565 | public class ConcurrentSkipListMapTest e
565
566		Object e4 = q.higherKey(six);
567		assertNull(e4);
535	–
568		}
569
570		/**
#	Line 551 | Line 583 | public class ConcurrentSkipListMapTest e
583
584		Object e4 = q.floorKey(zero);
585		assertNull(e4);
554	–
586		}
587
588		/**
#	Line 570 | Line 601 | public class ConcurrentSkipListMapTest e
601
602		Object e4 = q.ceilingKey(six);
603		assertNull(e4);
573	–
604		}
605
606		/**
#	Line 595 | Line 625 | public class ConcurrentSkipListMapTest e
625		try {
626		e.setValue("A");
627		shouldThrow();
628	<	} catch (Exception ok) {
599	<	}
628	>	} catch (UnsupportedOperationException success) {}
629		e = map.pollFirstEntry();
630		assertNull(e);
631		}
#	Line 623 | Line 652 | public class ConcurrentSkipListMapTest e
652		try {
653		e.setValue("E");
654		shouldThrow();
655	<	} catch (Exception ok) {
627	<	}
655	>	} catch (UnsupportedOperationException success) {}
656		e = map.pollLastEntry();
657		assertNull(e);
658		}
659
660		/**
661	<	*   size returns the correct values
661	>	* size returns the correct values
662		*/
663		public void testSize() {
664		ConcurrentSkipListMap map = map5();
665		ConcurrentSkipListMap empty = new ConcurrentSkipListMap();
666	<	assertEquals(0, empty.size());
667	<	assertEquals(5, map.size());
666	>	assertEquals(0, empty.size());
667	>	assertEquals(5, map.size());
668		}
669
670		/**
#	Line 646 | Line 674 | public class ConcurrentSkipListMapTest e
674		ConcurrentSkipListMap map = map5();
675		String s = map.toString();
676		for (int i = 1; i <= 5; ++i) {
677	<	assertTrue(s.indexOf(String.valueOf(i)) >= 0);
677	>	assertTrue(s.contains(String.valueOf(i)));
678		}
679	<	}
679	>	}
680
681		// Exception tests
682
#	Line 660 | Line 688 | public class ConcurrentSkipListMapTest e
688		ConcurrentSkipListMap c = map5();
689		c.get(null);
690		shouldThrow();
691	<	} catch(NullPointerException e){}
691	>	} catch (NullPointerException success) {}
692		}
693
694		/**
#	Line 671 | Line 699 | public class ConcurrentSkipListMapTest e
699		ConcurrentSkipListMap c = map5();
700		c.containsKey(null);
701		shouldThrow();
702	<	} catch(NullPointerException e){}
702	>	} catch (NullPointerException success) {}
703		}
704
705		/**
#	Line 682 | Line 710 | public class ConcurrentSkipListMapTest e
710		ConcurrentSkipListMap c = new ConcurrentSkipListMap();
711		c.containsValue(null);
712		shouldThrow();
713	<	} catch(NullPointerException e){}
713	>	} catch (NullPointerException success) {}
714		}
715
688	–
716		/**
717		* put(null,x) throws NPE
718		*/
#	Line 694 | Line 721 | public class ConcurrentSkipListMapTest e
721		ConcurrentSkipListMap c = map5();
722		c.put(null, "whatever");
723		shouldThrow();
724	<	} catch(NullPointerException e){}
724	>	} catch (NullPointerException success) {}
725		}
726
727		/**
#	Line 705 | Line 732 | public class ConcurrentSkipListMapTest e
732		ConcurrentSkipListMap c = map5();
733		c.putIfAbsent(null, "whatever");
734		shouldThrow();
735	<	} catch(NullPointerException e){}
735	>	} catch (NullPointerException success) {}
736		}
737
738		/**
#	Line 716 | Line 743 | public class ConcurrentSkipListMapTest e
743		ConcurrentSkipListMap c = map5();
744		c.replace(null, "whatever");
745		shouldThrow();
746	<	} catch(NullPointerException e){}
746	>	} catch (NullPointerException success) {}
747		}
748
749		/**
#	Line 727 | Line 754 | public class ConcurrentSkipListMapTest e
754		ConcurrentSkipListMap c = map5();
755		c.replace(null, one, "whatever");
756		shouldThrow();
757	<	} catch(NullPointerException e){}
757	>	} catch (NullPointerException success) {}
758		}
759
760		/**
#	Line 739 | Line 766 | public class ConcurrentSkipListMapTest e
766		c.put("sadsdf", "asdads");
767		c.remove(null);
768		shouldThrow();
769	<	} catch(NullPointerException e){}
769	>	} catch (NullPointerException success) {}
770		}
771
772		/**
#	Line 751 | Line 778 | public class ConcurrentSkipListMapTest e
778		c.put("sadsdf", "asdads");
779		c.remove(null, "whatever");
780		shouldThrow();
781	<	} catch(NullPointerException e){}
781	>	} catch (NullPointerException success) {}
782		}
783
784		/**
785		* remove(x, null) returns false
786		*/
787		public void testRemove3() {
788	<	try {
789	<	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
790	<	c.put("sadsdf", "asdads");
764	<	assertFalse(c.remove("sadsdf", null));
765	<	} catch(NullPointerException e){
766	<	fail();
767	<	}
788	>	ConcurrentSkipListMap c = new ConcurrentSkipListMap();
789	>	c.put("sadsdf", "asdads");
790	>	assertFalse(c.remove("sadsdf", null));
791		}
792
793		/**
794		* A deserialized map equals original
795		*/
796	<	public void testSerialization() {
796	>	public void testSerialization() throws Exception {
797		ConcurrentSkipListMap q = map5();
798
799	<	try {
800	<	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
801	<	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
802	<	out.writeObject(q);
803	<	out.close();
804	<
805	<	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
806	<	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
807	<	ConcurrentSkipListMap r = (ConcurrentSkipListMap)in.readObject();
808	<	assertEquals(q.size(), r.size());
809	<	assertTrue(q.equals(r));
787	<	assertTrue(r.equals(q));
788	<	} catch(Exception e){
789	<	e.printStackTrace();
790	<	unexpectedException();
791	<	}
799	>	ByteArrayOutputStream bout = new ByteArrayOutputStream(10000);
800	>	ObjectOutputStream out = new ObjectOutputStream(new BufferedOutputStream(bout));
801	>	out.writeObject(q);
802	>	out.close();
803	>
804	>	ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
805	>	ObjectInputStream in = new ObjectInputStream(new BufferedInputStream(bin));
806	>	ConcurrentSkipListMap r = (ConcurrentSkipListMap)in.readObject();
807	>	assertEquals(q.size(), r.size());
808	>	assertTrue(q.equals(r));
809	>	assertTrue(r.equals(q));
810		}
811
794	–
795	–
812		/**
813		* subMap returns map with keys in requested range
814		*/
815		public void testSubMapContents() {
816		ConcurrentSkipListMap map = map5();
817	<	NavigableMap sm = map.navigableSubMap(two, four);
817	>	NavigableMap sm = map.subMap(two, true, four, false);
818		assertEquals(two, sm.firstKey());
819		assertEquals(three, sm.lastKey());
820		assertEquals(2, sm.size());
#	Line 820 | Line 836 | public class ConcurrentSkipListMapTest e
836		k = (Integer)(r.next());
837		assertEquals(two, k);
838		assertFalse(r.hasNext());
839	<
839	>
840		Iterator j = sm.keySet().iterator();
841		j.next();
842		j.remove();
#	Line 829 | Line 845 | public class ConcurrentSkipListMapTest e
845		assertEquals(1, sm.size());
846		assertEquals(three, sm.firstKey());
847		assertEquals(three, sm.lastKey());
848	<	assertTrue(sm.remove(three) != null);
848	>	assertEquals("C", sm.remove(three));
849		assertTrue(sm.isEmpty());
850		assertEquals(3, map.size());
851		}
852
853		public void testSubMapContents2() {
854		ConcurrentSkipListMap map = map5();
855	<	NavigableMap sm = map.navigableSubMap(two, three);
855	>	NavigableMap sm = map.subMap(two, true, three, false);
856		assertEquals(1, sm.size());
857		assertEquals(two, sm.firstKey());
858		assertEquals(two, sm.lastKey());
#	Line 854 | Line 870 | public class ConcurrentSkipListMapTest e
870		k = (Integer)(r.next());
871		assertEquals(two, k);
872		assertFalse(r.hasNext());
873	<
873	>
874		Iterator j = sm.keySet().iterator();
875		j.next();
876		j.remove();
#	Line 862 | Line 878 | public class ConcurrentSkipListMapTest e
878		assertEquals(4, map.size());
879		assertEquals(0, sm.size());
880		assertTrue(sm.isEmpty());
881	<	assertTrue(sm.remove(three) == null);
881	>	assertSame(sm.remove(three), null);
882		assertEquals(4, map.size());
883		}
884
#	Line 871 | Line 887 | public class ConcurrentSkipListMapTest e
887		*/
888		public void testHeadMapContents() {
889		ConcurrentSkipListMap map = map5();
890	<	NavigableMap sm = map.navigableHeadMap(four);
890	>	NavigableMap sm = map.headMap(four, false);
891		assertTrue(sm.containsKey(one));
892		assertTrue(sm.containsKey(two));
893		assertTrue(sm.containsKey(three));
#	Line 893 | Line 909 | public class ConcurrentSkipListMapTest e
909		}
910
911		/**
912	<	* headMap returns map with keys in requested range
912	>	* tailMap returns map with keys in requested range
913		*/
914		public void testTailMapContents() {
915		ConcurrentSkipListMap map = map5();
916	<	NavigableMap sm = map.navigableTailMap(two);
916	>	NavigableMap sm = map.tailMap(two, true);
917		assertFalse(sm.containsKey(one));
918		assertTrue(sm.containsKey(two));
919		assertTrue(sm.containsKey(three));
#	Line 941 | Line 957 | public class ConcurrentSkipListMapTest e
957		assertEquals("E", e.getValue());
958		assertFalse(i.hasNext());
959
960	<	NavigableMap ssm = sm.navigableTailMap(four);
960	>	NavigableMap ssm = sm.tailMap(four, true);
961		assertEquals(four, ssm.firstKey());
962		assertEquals(five, ssm.lastKey());
963	<	assertTrue(ssm.remove(four) != null);
963	>	assertEquals("D", ssm.remove(four));
964		assertEquals(1, ssm.size());
965		assertEquals(3, sm.size());
966		assertEquals(4, map.size());
967		}
968	<
968	>
969	>	Random rnd = new Random(666);
970	>	BitSet bs;
971	>
972	>	/**
973	>	* Submaps of submaps subdivide correctly
974	>	*/
975	>	public void testRecursiveSubMaps() throws Exception {
976	>	int mapSize = expensiveTests ? 1000 : 100;
977	>	Class cl = ConcurrentSkipListMap.class;
978	>	NavigableMap<Integer, Integer> map = newMap(cl);
979	>	bs = new BitSet(mapSize);
980	>
981	>	populate(map, mapSize);
982	>	check(map,                 0, mapSize - 1, true);
983	>	check(map.descendingMap(), 0, mapSize - 1, false);
984	>
985	>	mutateMap(map, 0, mapSize - 1);
986	>	check(map,                 0, mapSize - 1, true);
987	>	check(map.descendingMap(), 0, mapSize - 1, false);
988	>
989	>	bashSubMap(map.subMap(0, true, mapSize, false),
990	>	0, mapSize - 1, true);
991	>	}
992	>
993	>	static NavigableMap<Integer, Integer> newMap(Class cl) throws Exception {
994	>	NavigableMap<Integer, Integer> result =
995	>	(NavigableMap<Integer, Integer>) cl.newInstance();
996	>	assertEquals(result.size(), 0);
997	>	assertFalse(result.keySet().iterator().hasNext());
998	>	return result;
999	>	}
1000	>
1001	>	void populate(NavigableMap<Integer, Integer> map, int limit) {
1002	>	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
1003	>	int key = rnd.nextInt(limit);
1004	>	put(map, key);
1005	>	}
1006	>	}
1007	>
1008	>	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
1009	>	int size = map.size();
1010	>	int rangeSize = max - min + 1;
1011	>
1012	>	// Remove a bunch of entries directly
1013	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1014	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1015	>	}
1016	>
1017	>	// Remove a bunch of entries with iterator
1018	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1019	>	if (rnd.nextBoolean()) {
1020	>	bs.clear(it.next());
1021	>	it.remove();
1022	>	}
1023	>	}
1024	>
1025	>	// Add entries till we're back to original size
1026	>	while (map.size() < size) {
1027	>	int key = min + rnd.nextInt(rangeSize);
1028	>	assertTrue(key >= min && key<= max);
1029	>	put(map, key);
1030	>	}
1031	>	}
1032	>
1033	>	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
1034	>	int size = map.size();
1035	>	int rangeSize = max - min + 1;
1036	>
1037	>	// Remove a bunch of entries directly
1038	>	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1039	>	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1040	>	}
1041	>
1042	>	// Remove a bunch of entries with iterator
1043	>	for (Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1044	>	if (rnd.nextBoolean()) {
1045	>	bs.clear(it.next());
1046	>	it.remove();
1047	>	}
1048	>	}
1049	>
1050	>	// Add entries till we're back to original size
1051	>	while (map.size() < size) {
1052	>	int key = min - 5 + rnd.nextInt(rangeSize + 10);
1053	>	if (key >= min && key<= max) {
1054	>	put(map, key);
1055	>	} else {
1056	>	try {
1057	>	map.put(key, 2 * key);
1058	>	shouldThrow();
1059	>	} catch (IllegalArgumentException success) {}
1060	>	}
1061	>	}
1062	>	}
1063	>
1064	>	void put(NavigableMap<Integer, Integer> map, int key) {
1065	>	if (map.put(key, 2 * key) == null)
1066	>	bs.set(key);
1067	>	}
1068	>
1069	>	void remove(NavigableMap<Integer, Integer> map, int key) {
1070	>	if (map.remove(key) != null)
1071	>	bs.clear(key);
1072	>	}
1073	>
1074	>	void bashSubMap(NavigableMap<Integer, Integer> map,
1075	>	int min, int max, boolean ascending) {
1076	>	check(map, min, max, ascending);
1077	>	check(map.descendingMap(), min, max, !ascending);
1078	>
1079	>	mutateSubMap(map, min, max);
1080	>	check(map, min, max, ascending);
1081	>	check(map.descendingMap(), min, max, !ascending);
1082	>
1083	>	// Recurse
1084	>	if (max - min < 2)
1085	>	return;
1086	>	int midPoint = (min + max) / 2;
1087	>
1088	>	// headMap - pick direction and endpoint inclusion randomly
1089	>	boolean incl = rnd.nextBoolean();
1090	>	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
1091	>	if (ascending) {
1092	>	if (rnd.nextBoolean())
1093	>	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
1094	>	else
1095	>	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1096	>	false);
1097	>	} else {
1098	>	if (rnd.nextBoolean())
1099	>	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
1100	>	else
1101	>	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1102	>	true);
1103	>	}
1104	>
1105	>	// tailMap - pick direction and endpoint inclusion randomly
1106	>	incl = rnd.nextBoolean();
1107	>	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
1108	>	if (ascending) {
1109	>	if (rnd.nextBoolean())
1110	>	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
1111	>	else
1112	>	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1113	>	false);
1114	>	} else {
1115	>	if (rnd.nextBoolean()) {
1116	>	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
1117	>	} else {
1118	>	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1119	>	true);
1120	>	}
1121	>	}
1122	>
1123	>	// subMap - pick direction and endpoint inclusion randomly
1124	>	int rangeSize = max - min + 1;
1125	>	int[] endpoints = new int[2];
1126	>	endpoints[0] = min + rnd.nextInt(rangeSize);
1127	>	endpoints[1] = min + rnd.nextInt(rangeSize);
1128	>	Arrays.sort(endpoints);
1129	>	boolean lowIncl = rnd.nextBoolean();
1130	>	boolean highIncl = rnd.nextBoolean();
1131	>	if (ascending) {
1132	>	NavigableMap<Integer,Integer> sm = map.subMap(
1133	>	endpoints[0], lowIncl, endpoints[1], highIncl);
1134	>	if (rnd.nextBoolean())
1135	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1136	>	endpoints[1] - (highIncl ? 0 : 1), true);
1137	>	else
1138	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1139	>	endpoints[1] - (highIncl ? 0 : 1), false);
1140	>	} else {
1141	>	NavigableMap<Integer,Integer> sm = map.subMap(
1142	>	endpoints[1], highIncl, endpoints[0], lowIncl);
1143	>	if (rnd.nextBoolean())
1144	>	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1145	>	endpoints[1] - (highIncl ? 0 : 1), false);
1146	>	else
1147	>	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1148	>	endpoints[1] - (highIncl ? 0 : 1), true);
1149	>	}
1150	>	}
1151	>
1152	>	/**
1153	>	* min and max are both inclusive.  If max < min, interval is empty.
1154	>	*/
1155	>	void check(NavigableMap<Integer, Integer> map,
1156	>	final int min, final int max, final boolean ascending) {
1157	>	class ReferenceSet {
1158	>	int lower(int key) {
1159	>	return ascending ? lowerAscending(key) : higherAscending(key);
1160	>	}
1161	>	int floor(int key) {
1162	>	return ascending ? floorAscending(key) : ceilingAscending(key);
1163	>	}
1164	>	int ceiling(int key) {
1165	>	return ascending ? ceilingAscending(key) : floorAscending(key);
1166	>	}
1167	>	int higher(int key) {
1168	>	return ascending ? higherAscending(key) : lowerAscending(key);
1169	>	}
1170	>	int first() {
1171	>	return ascending ? firstAscending() : lastAscending();
1172	>	}
1173	>	int last() {
1174	>	return ascending ? lastAscending() : firstAscending();
1175	>	}
1176	>	int lowerAscending(int key) {
1177	>	return floorAscending(key - 1);
1178	>	}
1179	>	int floorAscending(int key) {
1180	>	if (key < min)
1181	>	return -1;
1182	>	else if (key > max)
1183	>	key = max;
1184	>
1185	>	// BitSet should support this! Test would run much faster
1186	>	while (key >= min) {
1187	>	if (bs.get(key))
1188	>	return key;
1189	>	key--;
1190	>	}
1191	>	return -1;
1192	>	}
1193	>	int ceilingAscending(int key) {
1194	>	if (key < min)
1195	>	key = min;
1196	>	else if (key > max)
1197	>	return -1;
1198	>	int result = bs.nextSetBit(key);
1199	>	return result > max ? -1 : result;
1200	>	}
1201	>	int higherAscending(int key) {
1202	>	return ceilingAscending(key + 1);
1203	>	}
1204	>	private int firstAscending() {
1205	>	int result = ceilingAscending(min);
1206	>	return result > max ? -1 : result;
1207	>	}
1208	>	private int lastAscending() {
1209	>	int result = floorAscending(max);
1210	>	return result < min ? -1 : result;
1211	>	}
1212	>	}
1213	>	ReferenceSet rs = new ReferenceSet();
1214	>
1215	>	// Test contents using containsKey
1216	>	int size = 0;
1217	>	for (int i = min; i <= max; i++) {
1218	>	boolean bsContainsI = bs.get(i);
1219	>	assertEquals(bsContainsI, map.containsKey(i));
1220	>	if (bsContainsI)
1221	>	size++;
1222	>	}
1223	>	assertEquals(map.size(), size);
1224	>
1225	>	// Test contents using contains keySet iterator
1226	>	int size2 = 0;
1227	>	int previousKey = -1;
1228	>	for (int key : map.keySet()) {
1229	>	assertTrue(bs.get(key));
1230	>	size2++;
1231	>	assertTrue(previousKey < 0 ||
1232	>	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1233	>	previousKey = key;
1234	>	}
1235	>	assertEquals(size2, size);
1236	>
1237	>	// Test navigation ops
1238	>	for (int key = min - 1; key <= max + 1; key++) {
1239	>	assertEq(map.lowerKey(key), rs.lower(key));
1240	>	assertEq(map.floorKey(key), rs.floor(key));
1241	>	assertEq(map.higherKey(key), rs.higher(key));
1242	>	assertEq(map.ceilingKey(key), rs.ceiling(key));
1243	>	}
1244	>
1245	>	// Test extrema
1246	>	if (map.size() != 0) {
1247	>	assertEq(map.firstKey(), rs.first());
1248	>	assertEq(map.lastKey(), rs.last());
1249	>	} else {
1250	>	assertEq(rs.first(), -1);
1251	>	assertEq(rs.last(),  -1);
1252	>	try {
1253	>	map.firstKey();
1254	>	shouldThrow();
1255	>	} catch (NoSuchElementException success) {}
1256	>	try {
1257	>	map.lastKey();
1258	>	shouldThrow();
1259	>	} catch (NoSuchElementException success) {}
1260	>	}
1261	>	}
1262	>
1263	>	static void assertEq(Integer i, int j) {
1264	>	if (i == null)
1265	>	assertEquals(j, -1);
1266	>	else
1267	>	assertEquals((int) i, j);
1268	>	}
1269	>
1270	>	static boolean eq(Integer i, int j) {
1271	>	return i == null ? j == -1 : i == j;
1272	>	}
1273	>
1274		}

Diff Legend

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