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.3 by dl, Sun May 22 10:56:03 2005 UTC vs.
Revision 1.8 by dl, Sat Apr 19 18:45:18 2008 UTC

#	Line 169 | Line 169 | public class ConcurrentSkipListMapTest e
169		Iterator i = s.iterator();
170		Integer last = (Integer)i.next();
171		assertEquals(last, one);
172	+	int count = 1;
173		while (i.hasNext()) {
174		Integer k = (Integer)i.next();
175		assertTrue(last.compareTo(k) < 0);
176		last = k;
177	+	++count;
178		}
179	+	assertEquals(count ,5);
180	+	}
181	+
182	+	/**
183	+	* descending iterator of key set is inverse ordered
184	+	*/
185	+	public void testKeySetDescendingIteratorOrder() {
186	+	ConcurrentSkipListMap map = map5();
187	+	NavigableSet s = map.navigableKeySet();
188	+	Iterator i = s.descendingIterator();
189	+	Integer last = (Integer)i.next();
190	+	assertEquals(last, five);
191	+	int count = 1;
192	+	while (i.hasNext()) {
193	+	Integer k = (Integer)i.next();
194	+	assertTrue(last.compareTo(k) > 0);
195	+	last = k;
196	+	++count;
197	+	}
198	+	assertEquals(count ,5);
199		}
200
201		/**
#	Line 185 | Line 207 | public class ConcurrentSkipListMapTest e
207		Iterator i = s.iterator();
208		Integer last = (Integer)i.next();
209		assertEquals(last, five);
210	+	int count = 1;
211		while (i.hasNext()) {
212		Integer k = (Integer)i.next();
213		assertTrue(last.compareTo(k) > 0);
214		last = k;
215	+	++count;
216		}
217	+	assertEquals(count, 5);
218	+	}
219	+
220	+	/**
221	+	*  descending iterator of descendingKeySet is ordered
222	+	*/
223	+	public void testDescendingKeySetDescendingIteratorOrder() {
224	+	ConcurrentSkipListMap map = map5();
225	+	NavigableSet s = map.descendingKeySet();
226	+	Iterator i = s.descendingIterator();
227	+	Integer last = (Integer)i.next();
228	+	assertEquals(last, one);
229	+	int count = 1;
230	+	while (i.hasNext()) {
231	+	Integer k = (Integer)i.next();
232	+	assertTrue(last.compareTo(k) < 0);
233	+	last = k;
234	+	++count;
235	+	}
236	+	assertEquals(count, 5);
237	+	}
238	+
239	+	/**
240	+	*  Values.toArray contains all values
241	+	*/
242	+	public void testValuesToArray() {
243	+	ConcurrentSkipListMap map = map5();
244	+	Collection v = map.values();
245	+	Object[] ar = v.toArray();
246	+	ArrayList s = new ArrayList(Arrays.asList(ar));
247	+	assertEquals(5, ar.length);
248	+	assertTrue(s.contains("A"));
249	+	assertTrue(s.contains("B"));
250	+	assertTrue(s.contains("C"));
251	+	assertTrue(s.contains("D"));
252	+	assertTrue(s.contains("E"));
253		}
254
255		/**
#	Line 230 | Line 290 | public class ConcurrentSkipListMapTest e
290		*/
291		public void testDescendingEntrySet() {
292		ConcurrentSkipListMap map = map5();
293	<	Set s = map.descendingEntrySet();
293	>	Set s = map.descendingMap().entrySet();
294		assertEquals(5, s.size());
295		Iterator it = s.iterator();
296		while (it.hasNext()) {
#	Line 263 | Line 323 | public class ConcurrentSkipListMapTest e
323		*/
324		public void testDescendingEntrySetToArray() {
325		ConcurrentSkipListMap map = map5();
326	<	Set s = map.descendingEntrySet();
326	>	Set s = map.descendingMap().entrySet();
327		Object[] ar = s.toArray();
328		assertEquals(5, ar.length);
329		for (int i = 0; i < 5; ++i) {
#	Line 446 | Line 506 | public class ConcurrentSkipListMapTest e
506
507		}
508
509	+	/**
510	+	* lowerEntry, higherEntry, ceilingEntry, and floorEntry return
511	+	* imutable entries
512	+	*/
513	+	public void testEntryImmutablity() {
514	+	ConcurrentSkipListMap map = map5();
515	+	Map.Entry e = map.lowerEntry(three);
516	+	assertEquals(two, e.getKey());
517	+	try {
518	+	e.setValue("X");
519	+	fail();
520	+	} catch(UnsupportedOperationException success) {}
521	+	e = map.higherEntry(zero);
522	+	assertEquals(one, e.getKey());
523	+	try {
524	+	e.setValue("X");
525	+	fail();
526	+	} catch(UnsupportedOperationException success) {}
527	+	e = map.floorEntry(one);
528	+	assertEquals(one, e.getKey());
529	+	try {
530	+	e.setValue("X");
531	+	fail();
532	+	} catch(UnsupportedOperationException success) {}
533	+	e = map.ceilingEntry(five);
534	+	assertEquals(five, e.getKey());
535	+	try {
536	+	e.setValue("X");
537	+	fail();
538	+	} catch(UnsupportedOperationException success) {}
539	+	}
540	+
541	+
542
543		/**
544		* lowerKey returns preceding element
#	Line 748 | Line 841 | public class ConcurrentSkipListMapTest e
841		*/
842		public void testSubMapContents() {
843		ConcurrentSkipListMap map = map5();
844	<	NavigableMap sm = map.navigableSubMap(two, four);
844	>	NavigableMap sm = map.subMap(two, true, four, false);
845		assertEquals(two, sm.firstKey());
846		assertEquals(three, sm.lastKey());
847		assertEquals(2, sm.size());
#	Line 786 | Line 879 | public class ConcurrentSkipListMapTest e
879
880		public void testSubMapContents2() {
881		ConcurrentSkipListMap map = map5();
882	<	NavigableMap sm = map.navigableSubMap(two, three);
882	>	NavigableMap sm = map.subMap(two, true, three, false);
883		assertEquals(1, sm.size());
884		assertEquals(two, sm.firstKey());
885		assertEquals(two, sm.lastKey());
#	Line 821 | Line 914 | public class ConcurrentSkipListMapTest e
914		*/
915		public void testHeadMapContents() {
916		ConcurrentSkipListMap map = map5();
917	<	NavigableMap sm = map.navigableHeadMap(four);
917	>	NavigableMap sm = map.headMap(four, false);
918		assertTrue(sm.containsKey(one));
919		assertTrue(sm.containsKey(two));
920		assertTrue(sm.containsKey(three));
#	Line 843 | Line 936 | public class ConcurrentSkipListMapTest e
936		}
937
938		/**
939	<	* headMap returns map with keys in requested range
939	>	* tailMap returns map with keys in requested range
940		*/
941		public void testTailMapContents() {
942		ConcurrentSkipListMap map = map5();
943	<	NavigableMap sm = map.navigableTailMap(two);
943	>	NavigableMap sm = map.tailMap(two, true);
944		assertFalse(sm.containsKey(one));
945		assertTrue(sm.containsKey(two));
946		assertTrue(sm.containsKey(three));
#	Line 891 | Line 984 | public class ConcurrentSkipListMapTest e
984		assertEquals("E", e.getValue());
985		assertFalse(i.hasNext());
986
987	<	NavigableMap ssm = sm.navigableTailMap(four);
987	>	NavigableMap ssm = sm.tailMap(four, true);
988		assertEquals(four, ssm.firstKey());
989		assertEquals(five, ssm.lastKey());
990		assertTrue(ssm.remove(four) != null);
#	Line 899 | Line 992 | public class ConcurrentSkipListMapTest e
992		assertEquals(3, sm.size());
993		assertEquals(4, map.size());
994		}
995	+
996	+	Random rnd = new Random(666);
997	+	BitSet bs;
998	+
999	+	/**
1000	+	* Submaps of submaps subdivide correctly
1001	+	*/
1002	+	public void testRecursiveSubMaps() {
1003	+	int mapSize = 1000;
1004	+	Class cl = ConcurrentSkipListMap.class;
1005	+	NavigableMap<Integer, Integer> map = newMap(cl);
1006	+	bs = new BitSet(mapSize);
1007	+
1008	+	populate(map, mapSize);
1009	+	check(map,                 0, mapSize - 1, true);
1010	+	check(map.descendingMap(), 0, mapSize - 1, false);
1011	+
1012	+	mutateMap(map, 0, mapSize - 1);
1013	+	check(map,                 0, mapSize - 1, true);
1014	+	check(map.descendingMap(), 0, mapSize - 1, false);
1015	+
1016	+	bashSubMap(map.subMap(0, true, mapSize, false),
1017	+	0, mapSize - 1, true);
1018	+	}
1019	+
1020	+	static NavigableMap<Integer, Integer> newMap(Class cl) {
1021	+	NavigableMap<Integer, Integer> result = null;
1022	+	try {
1023	+	result = (NavigableMap<Integer, Integer>) cl.newInstance();
1024	+	} catch(Exception e) {
1025	+	fail();
1026	+	}
1027	+	assertEquals(result.size(), 0);
1028	+	assertFalse(result.keySet().iterator().hasNext());
1029	+	return result;
1030	+	}
1031	+
1032	+	void populate(NavigableMap<Integer, Integer> map, int limit) {
1033	+	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
1034	+	int key = rnd.nextInt(limit);
1035	+	put(map, key);
1036	+	}
1037	+	}
1038	+
1039	+	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
1040	+	int size = map.size();
1041	+	int rangeSize = max - min + 1;
1042	+
1043	+	// Remove a bunch of entries directly
1044	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1045	+	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1046	+	}
1047	+
1048	+	// Remove a bunch of entries with iterator
1049	+	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1050	+	if (rnd.nextBoolean()) {
1051	+	bs.clear(it.next());
1052	+	it.remove();
1053	+	}
1054	+	}
1055	+
1056	+	// Add entries till we're back to original size
1057	+	while (map.size() < size) {
1058	+	int key = min + rnd.nextInt(rangeSize);
1059	+	assertTrue(key >= min && key<= max);
1060	+	put(map, key);
1061	+	}
1062	+	}
1063	+
1064	+	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
1065	+	int size = map.size();
1066	+	int rangeSize = max - min + 1;
1067	+
1068	+	// Remove a bunch of entries directly
1069	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1070	+	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1071	+	}
1072	+
1073	+	// Remove a bunch of entries with iterator
1074	+	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1075	+	if (rnd.nextBoolean()) {
1076	+	bs.clear(it.next());
1077	+	it.remove();
1078	+	}
1079	+	}
1080	+
1081	+	// Add entries till we're back to original size
1082	+	while (map.size() < size) {
1083	+	int key = min - 5 + rnd.nextInt(rangeSize + 10);
1084	+	if (key >= min && key<= max) {
1085	+	put(map, key);
1086	+	} else {
1087	+	try {
1088	+	map.put(key, 2 * key);
1089	+	fail();
1090	+	} catch(IllegalArgumentException e) {
1091	+	// expected
1092	+	}
1093	+	}
1094	+	}
1095	+	}
1096	+
1097	+	void put(NavigableMap<Integer, Integer> map, int key) {
1098	+	if (map.put(key, 2 * key) == null)
1099	+	bs.set(key);
1100	+	}
1101	+
1102	+	void remove(NavigableMap<Integer, Integer> map, int key) {
1103	+	if (map.remove(key) != null)
1104	+	bs.clear(key);
1105	+	}
1106	+
1107	+	void bashSubMap(NavigableMap<Integer, Integer> map,
1108	+	int min, int max, boolean ascending) {
1109	+	check(map, min, max, ascending);
1110	+	check(map.descendingMap(), min, max, !ascending);
1111	+
1112	+	mutateSubMap(map, min, max);
1113	+	check(map, min, max, ascending);
1114	+	check(map.descendingMap(), min, max, !ascending);
1115	+
1116	+	// Recurse
1117	+	if (max - min < 2)
1118	+	return;
1119	+	int midPoint = (min + max) / 2;
1120	+
1121	+	// headMap - pick direction and endpoint inclusion randomly
1122	+	boolean incl = rnd.nextBoolean();
1123	+	NavigableMap<Integer,Integer> hm = map.headMap(midPoint, incl);
1124	+	if (ascending) {
1125	+	if (rnd.nextBoolean())
1126	+	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
1127	+	else
1128	+	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1129	+	false);
1130	+	} else {
1131	+	if (rnd.nextBoolean())
1132	+	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
1133	+	else
1134	+	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1135	+	true);
1136	+	}
1137	+
1138	+	// tailMap - pick direction and endpoint inclusion randomly
1139	+	incl = rnd.nextBoolean();
1140	+	NavigableMap<Integer,Integer> tm = map.tailMap(midPoint,incl);
1141	+	if (ascending) {
1142	+	if (rnd.nextBoolean())
1143	+	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
1144	+	else
1145	+	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1146	+	false);
1147	+	} else {
1148	+	if (rnd.nextBoolean()) {
1149	+	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
1150	+	} else {
1151	+	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1152	+	true);
1153	+	}
1154	+	}
1155	+
1156	+	// subMap - pick direction and endpoint inclusion randomly
1157	+	int rangeSize = max - min + 1;
1158	+	int[] endpoints = new int[2];
1159	+	endpoints[0] = min + rnd.nextInt(rangeSize);
1160	+	endpoints[1] = min + rnd.nextInt(rangeSize);
1161	+	Arrays.sort(endpoints);
1162	+	boolean lowIncl = rnd.nextBoolean();
1163	+	boolean highIncl = rnd.nextBoolean();
1164	+	if (ascending) {
1165	+	NavigableMap<Integer,Integer> sm = map.subMap(
1166	+	endpoints[0], lowIncl, endpoints[1], highIncl);
1167	+	if (rnd.nextBoolean())
1168	+	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1169	+	endpoints[1] - (highIncl ? 0 : 1), true);
1170	+	else
1171	+	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1172	+	endpoints[1] - (highIncl ? 0 : 1), false);
1173	+	} else {
1174	+	NavigableMap<Integer,Integer> sm = map.subMap(
1175	+	endpoints[1], highIncl, endpoints[0], lowIncl);
1176	+	if (rnd.nextBoolean())
1177	+	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1178	+	endpoints[1] - (highIncl ? 0 : 1), false);
1179	+	else
1180	+	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1181	+	endpoints[1] - (highIncl ? 0 : 1), true);
1182	+	}
1183	+	}
1184	+
1185	+	/**
1186	+	* min and max are both inclusive.  If max < min, interval is empty.
1187	+	*/
1188	+	void check(NavigableMap<Integer, Integer> map,
1189	+	final int min, final int max, final boolean ascending) {
1190	+	class ReferenceSet {
1191	+	int lower(int key) {
1192	+	return ascending ? lowerAscending(key) : higherAscending(key);
1193	+	}
1194	+	int floor(int key) {
1195	+	return ascending ? floorAscending(key) : ceilingAscending(key);
1196	+	}
1197	+	int ceiling(int key) {
1198	+	return ascending ? ceilingAscending(key) : floorAscending(key);
1199	+	}
1200	+	int higher(int key) {
1201	+	return ascending ? higherAscending(key) : lowerAscending(key);
1202	+	}
1203	+	int first() {
1204	+	return ascending ? firstAscending() : lastAscending();
1205	+	}
1206	+	int last() {
1207	+	return ascending ? lastAscending() : firstAscending();
1208	+	}
1209	+	int lowerAscending(int key) {
1210	+	return floorAscending(key - 1);
1211	+	}
1212	+	int floorAscending(int key) {
1213	+	if (key < min)
1214	+	return -1;
1215	+	else if (key > max)
1216	+	key = max;
1217	+
1218	+	// BitSet should support this! Test would run much faster
1219	+	while (key >= min) {
1220	+	if (bs.get(key))
1221	+	return(key);
1222	+	key--;
1223	+	}
1224	+	return -1;
1225	+	}
1226	+	int ceilingAscending(int key) {
1227	+	if (key < min)
1228	+	key = min;
1229	+	else if (key > max)
1230	+	return -1;
1231	+	int result = bs.nextSetBit(key);
1232	+	return result > max ? -1 : result;
1233	+	}
1234	+	int higherAscending(int key) {
1235	+	return ceilingAscending(key + 1);
1236	+	}
1237	+	private int firstAscending() {
1238	+	int result = ceilingAscending(min);
1239	+	return result > max ? -1 : result;
1240	+	}
1241	+	private int lastAscending() {
1242	+	int result = floorAscending(max);
1243	+	return result < min ? -1 : result;
1244	+	}
1245	+	}
1246	+	ReferenceSet rs = new ReferenceSet();
1247	+
1248	+	// Test contents using containsKey
1249	+	int size = 0;
1250	+	for (int i = min; i <= max; i++) {
1251	+	boolean bsContainsI = bs.get(i);
1252	+	assertEquals(bsContainsI, map.containsKey(i));
1253	+	if (bsContainsI)
1254	+	size++;
1255	+	}
1256	+	assertEquals(map.size(), size);
1257	+
1258	+	// Test contents using contains keySet iterator
1259	+	int size2 = 0;
1260	+	int previousKey = -1;
1261	+	for (int key : map.keySet()) {
1262	+	assertTrue(bs.get(key));
1263	+	size2++;
1264	+	assertTrue(previousKey < 0 ||
1265	+	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1266	+	previousKey = key;
1267	+	}
1268	+	assertEquals(size2, size);
1269	+
1270	+	// Test navigation ops
1271	+	for (int key = min - 1; key <= max + 1; key++) {
1272	+	assertEq(map.lowerKey(key), rs.lower(key));
1273	+	assertEq(map.floorKey(key), rs.floor(key));
1274	+	assertEq(map.higherKey(key), rs.higher(key));
1275	+	assertEq(map.ceilingKey(key), rs.ceiling(key));
1276	+	}
1277	+
1278	+	// Test extrema
1279	+	if (map.size() != 0) {
1280	+	assertEq(map.firstKey(), rs.first());
1281	+	assertEq(map.lastKey(), rs.last());
1282	+	} else {
1283	+	assertEq(rs.first(), -1);
1284	+	assertEq(rs.last(),  -1);
1285	+	try {
1286	+	map.firstKey();
1287	+	fail();
1288	+	} catch(NoSuchElementException e) {
1289	+	// expected
1290	+	}
1291	+	try {
1292	+	map.lastKey();
1293	+	fail();
1294	+	} catch(NoSuchElementException e) {
1295	+	// expected
1296	+	}
1297	+	}
1298	+	}
1299	+
1300	+	static void assertEq(Integer i, int j) {
1301	+	if (i == null)
1302	+	assertEquals(j, -1);
1303	+	else
1304	+	assertEquals((int) i, j);
1305	+	}
1306	+
1307	+	static boolean eq(Integer i, int j) {
1308	+	return i == null ? j == -1 : i == j;
1309	+	}
1310
1311		}

Diff Legend

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