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.6 by dl, Wed Apr 19 15:10:54 2006 UTC

#	Line 247 | Line 247 | public class ConcurrentSkipListMapTest e
247		*/
248		public void testDescendingEntrySet() {
249		ConcurrentSkipListMap map = map5();
250	<	Set s = map.descendingEntrySet();
250	>	Set s = map.descendingMap().entrySet();
251		assertEquals(5, s.size());
252		Iterator it = s.iterator();
253		while (it.hasNext()) {
#	Line 280 | Line 280 | public class ConcurrentSkipListMapTest e
280		*/
281		public void testDescendingEntrySetToArray() {
282		ConcurrentSkipListMap map = map5();
283	<	Set s = map.descendingEntrySet();
283	>	Set s = map.descendingMap().entrySet();
284		Object[] ar = s.toArray();
285		assertEquals(5, ar.length);
286		for (int i = 0; i < 5; ++i) {
#	Line 798 | Line 798 | public class ConcurrentSkipListMapTest e
798		*/
799		public void testSubMapContents() {
800		ConcurrentSkipListMap map = map5();
801	<	NavigableMap sm = map.navigableSubMap(two, four);
801	>	NavigableMap sm = map.navigableSubMap(two, true, four, false);
802		assertEquals(two, sm.firstKey());
803		assertEquals(three, sm.lastKey());
804		assertEquals(2, sm.size());
#	Line 836 | Line 836 | public class ConcurrentSkipListMapTest e
836
837		public void testSubMapContents2() {
838		ConcurrentSkipListMap map = map5();
839	<	NavigableMap sm = map.navigableSubMap(two, three);
839	>	NavigableMap sm = map.navigableSubMap(two, true, three, false);
840		assertEquals(1, sm.size());
841		assertEquals(two, sm.firstKey());
842		assertEquals(two, sm.lastKey());
#	Line 871 | Line 871 | public class ConcurrentSkipListMapTest e
871		*/
872		public void testHeadMapContents() {
873		ConcurrentSkipListMap map = map5();
874	<	NavigableMap sm = map.navigableHeadMap(four);
874	>	NavigableMap sm = map.navigableHeadMap(four, false);
875		assertTrue(sm.containsKey(one));
876		assertTrue(sm.containsKey(two));
877		assertTrue(sm.containsKey(three));
#	Line 893 | Line 893 | public class ConcurrentSkipListMapTest e
893		}
894
895		/**
896	<	* headMap returns map with keys in requested range
896	>	* tailMap returns map with keys in requested range
897		*/
898		public void testTailMapContents() {
899		ConcurrentSkipListMap map = map5();
900	<	NavigableMap sm = map.navigableTailMap(two);
900	>	NavigableMap sm = map.navigableTailMap(two, true);
901		assertFalse(sm.containsKey(one));
902		assertTrue(sm.containsKey(two));
903		assertTrue(sm.containsKey(three));
#	Line 941 | Line 941 | public class ConcurrentSkipListMapTest e
941		assertEquals("E", e.getValue());
942		assertFalse(i.hasNext());
943
944	<	NavigableMap ssm = sm.navigableTailMap(four);
944	>	NavigableMap ssm = sm.navigableTailMap(four, true);
945		assertEquals(four, ssm.firstKey());
946		assertEquals(five, ssm.lastKey());
947		assertTrue(ssm.remove(four) != null);
#	Line 949 | Line 949 | public class ConcurrentSkipListMapTest e
949		assertEquals(3, sm.size());
950		assertEquals(4, map.size());
951		}
952	+
953	+	Random rnd = new Random(666);
954	+	BitSet bs;
955	+
956	+	/**
957	+	* Submaps of submaps subdivide correctly
958	+	*/
959	+	public void testRecursiveSubMaps() {
960	+	int mapSize = 1000;
961	+	Class cl = ConcurrentSkipListMap.class;
962	+	NavigableMap<Integer, Integer> map = newMap(cl);
963	+	bs = new BitSet(mapSize);
964	+
965	+	populate(map, mapSize);
966	+	check(map,                 0, mapSize - 1, true);
967	+	check(map.descendingMap(), 0, mapSize - 1, false);
968	+
969	+	mutateMap(map, 0, mapSize - 1);
970	+	check(map,                 0, mapSize - 1, true);
971	+	check(map.descendingMap(), 0, mapSize - 1, false);
972	+
973	+	bashSubMap(map.navigableSubMap(0, true, mapSize, false),
974	+	0, mapSize - 1, true);
975	+	}
976	+
977	+	static NavigableMap<Integer, Integer> newMap(Class cl) {
978	+	NavigableMap<Integer, Integer> result = null;
979	+	try {
980	+	result = (NavigableMap<Integer, Integer>) cl.newInstance();
981	+	} catch(Exception e) {
982	+	fail();
983	+	}
984	+	assertEquals(result.size(), 0);
985	+	assertFalse(result.keySet().iterator().hasNext());
986	+	return result;
987	+	}
988	+
989	+	void populate(NavigableMap<Integer, Integer> map, int limit) {
990	+	for (int i = 0, n = 2 * limit / 3; i < n; i++) {
991	+	int key = rnd.nextInt(limit);
992	+	put(map, key);
993	+	}
994	+	}
995	+
996	+	void mutateMap(NavigableMap<Integer, Integer> map, int min, int max) {
997	+	int size = map.size();
998	+	int rangeSize = max - min + 1;
999	+
1000	+	// Remove a bunch of entries directly
1001	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1002	+	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1003	+	}
1004	+
1005	+	// Remove a bunch of entries with iterator
1006	+	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1007	+	if (rnd.nextBoolean()) {
1008	+	bs.clear(it.next());
1009	+	it.remove();
1010	+	}
1011	+	}
1012	+
1013	+	// Add entries till we're back to original size
1014	+	while (map.size() < size) {
1015	+	int key = min + rnd.nextInt(rangeSize);
1016	+	assertTrue(key >= min && key<= max);
1017	+	put(map, key);
1018	+	}
1019	+	}
1020	+
1021	+	void mutateSubMap(NavigableMap<Integer, Integer> map, int min, int max) {
1022	+	int size = map.size();
1023	+	int rangeSize = max - min + 1;
1024	+
1025	+	// Remove a bunch of entries directly
1026	+	for (int i = 0, n = rangeSize / 2; i < n; i++) {
1027	+	remove(map, min - 5 + rnd.nextInt(rangeSize + 10));
1028	+	}
1029	+
1030	+	// Remove a bunch of entries with iterator
1031	+	for(Iterator<Integer> it = map.keySet().iterator(); it.hasNext(); ) {
1032	+	if (rnd.nextBoolean()) {
1033	+	bs.clear(it.next());
1034	+	it.remove();
1035	+	}
1036	+	}
1037	+
1038	+	// Add entries till we're back to original size
1039	+	while (map.size() < size) {
1040	+	int key = min - 5 + rnd.nextInt(rangeSize + 10);
1041	+	if (key >= min && key<= max) {
1042	+	put(map, key);
1043	+	} else {
1044	+	try {
1045	+	map.put(key, 2 * key);
1046	+	fail();
1047	+	} catch(IllegalArgumentException e) {
1048	+	// expected
1049	+	}
1050	+	}
1051	+	}
1052	+	}
1053	+
1054	+	void put(NavigableMap<Integer, Integer> map, int key) {
1055	+	if (map.put(key, 2 * key) == null)
1056	+	bs.set(key);
1057	+	}
1058	+
1059	+	void remove(NavigableMap<Integer, Integer> map, int key) {
1060	+	if (map.remove(key) != null)
1061	+	bs.clear(key);
1062	+	}
1063	+
1064	+	void bashSubMap(NavigableMap<Integer, Integer> map,
1065	+	int min, int max, boolean ascending) {
1066	+	check(map, min, max, ascending);
1067	+	check(map.descendingMap(), min, max, !ascending);
1068	+
1069	+	mutateSubMap(map, min, max);
1070	+	check(map, min, max, ascending);
1071	+	check(map.descendingMap(), min, max, !ascending);
1072	+
1073	+	// Recurse
1074	+	if (max - min < 2)
1075	+	return;
1076	+	int midPoint = (min + max) / 2;
1077	+
1078	+	// headMap - pick direction and endpoint inclusion randomly
1079	+	boolean incl = rnd.nextBoolean();
1080	+	NavigableMap<Integer,Integer> hm = map.navigableHeadMap(midPoint, incl);
1081	+	if (ascending) {
1082	+	if (rnd.nextBoolean())
1083	+	bashSubMap(hm, min, midPoint - (incl ? 0 : 1), true);
1084	+	else
1085	+	bashSubMap(hm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1086	+	false);
1087	+	} else {
1088	+	if (rnd.nextBoolean())
1089	+	bashSubMap(hm, midPoint + (incl ? 0 : 1), max, false);
1090	+	else
1091	+	bashSubMap(hm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1092	+	true);
1093	+	}
1094	+
1095	+	// tailMap - pick direction and endpoint inclusion randomly
1096	+	incl = rnd.nextBoolean();
1097	+	NavigableMap<Integer,Integer> tm = map.navigableTailMap(midPoint,incl);
1098	+	if (ascending) {
1099	+	if (rnd.nextBoolean())
1100	+	bashSubMap(tm, midPoint + (incl ? 0 : 1), max, true);
1101	+	else
1102	+	bashSubMap(tm.descendingMap(), midPoint + (incl ? 0 : 1), max,
1103	+	false);
1104	+	} else {
1105	+	if (rnd.nextBoolean()) {
1106	+	bashSubMap(tm, min, midPoint - (incl ? 0 : 1), false);
1107	+	} else {
1108	+	bashSubMap(tm.descendingMap(), min, midPoint - (incl ? 0 : 1),
1109	+	true);
1110	+	}
1111	+	}
1112	+
1113	+	// subMap - pick direction and endpoint inclusion randomly
1114	+	int rangeSize = max - min + 1;
1115	+	int[] endpoints = new int[2];
1116	+	endpoints[0] = min + rnd.nextInt(rangeSize);
1117	+	endpoints[1] = min + rnd.nextInt(rangeSize);
1118	+	Arrays.sort(endpoints);
1119	+	boolean lowIncl = rnd.nextBoolean();
1120	+	boolean highIncl = rnd.nextBoolean();
1121	+	if (ascending) {
1122	+	NavigableMap<Integer,Integer> sm = map.navigableSubMap(
1123	+	endpoints[0], lowIncl, endpoints[1], highIncl);
1124	+	if (rnd.nextBoolean())
1125	+	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1126	+	endpoints[1] - (highIncl ? 0 : 1), true);
1127	+	else
1128	+	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1129	+	endpoints[1] - (highIncl ? 0 : 1), false);
1130	+	} else {
1131	+	NavigableMap<Integer,Integer> sm = map.navigableSubMap(
1132	+	endpoints[1], highIncl, endpoints[0], lowIncl);
1133	+	if (rnd.nextBoolean())
1134	+	bashSubMap(sm, endpoints[0] + (lowIncl ? 0 : 1),
1135	+	endpoints[1] - (highIncl ? 0 : 1), false);
1136	+	else
1137	+	bashSubMap(sm.descendingMap(), endpoints[0] + (lowIncl ? 0 : 1),
1138	+	endpoints[1] - (highIncl ? 0 : 1), true);
1139	+	}
1140	+	}
1141	+
1142	+	/**
1143	+	* min and max are both inclusive.  If max < min, interval is empty.
1144	+	*/
1145	+	void check(NavigableMap<Integer, Integer> map,
1146	+	final int min, final int max, final boolean ascending) {
1147	+	class ReferenceSet {
1148	+	int lower(int key) {
1149	+	return ascending ? lowerAscending(key) : higherAscending(key);
1150	+	}
1151	+	int floor(int key) {
1152	+	return ascending ? floorAscending(key) : ceilingAscending(key);
1153	+	}
1154	+	int ceiling(int key) {
1155	+	return ascending ? ceilingAscending(key) : floorAscending(key);
1156	+	}
1157	+	int higher(int key) {
1158	+	return ascending ? higherAscending(key) : lowerAscending(key);
1159	+	}
1160	+	int first() {
1161	+	return ascending ? firstAscending() : lastAscending();
1162	+	}
1163	+	int last() {
1164	+	return ascending ? lastAscending() : firstAscending();
1165	+	}
1166	+	int lowerAscending(int key) {
1167	+	return floorAscending(key - 1);
1168	+	}
1169	+	int floorAscending(int key) {
1170	+	if (key < min)
1171	+	return -1;
1172	+	else if (key > max)
1173	+	key = max;
1174	+
1175	+	// BitSet should support this! Test would run much faster
1176	+	while (key >= min) {
1177	+	if (bs.get(key))
1178	+	return(key);
1179	+	key--;
1180	+	}
1181	+	return -1;
1182	+	}
1183	+	int ceilingAscending(int key) {
1184	+	if (key < min)
1185	+	key = min;
1186	+	else if (key > max)
1187	+	return -1;
1188	+	int result = bs.nextSetBit(key);
1189	+	return result > max ? -1 : result;
1190	+	}
1191	+	int higherAscending(int key) {
1192	+	return ceilingAscending(key + 1);
1193	+	}
1194	+	private int firstAscending() {
1195	+	int result = ceilingAscending(min);
1196	+	return result > max ? -1 : result;
1197	+	}
1198	+	private int lastAscending() {
1199	+	int result = floorAscending(max);
1200	+	return result < min ? -1 : result;
1201	+	}
1202	+	}
1203	+	ReferenceSet rs = new ReferenceSet();
1204	+
1205	+	// Test contents using containsKey
1206	+	int size = 0;
1207	+	for (int i = min; i <= max; i++) {
1208	+	boolean bsContainsI = bs.get(i);
1209	+	assertEquals(bsContainsI, map.containsKey(i));
1210	+	if (bsContainsI)
1211	+	size++;
1212	+	}
1213	+	assertEquals(map.size(), size);
1214	+
1215	+	// Test contents using contains keySet iterator
1216	+	int size2 = 0;
1217	+	int previousKey = -1;
1218	+	for (int key : map.keySet()) {
1219	+	assertTrue(bs.get(key));
1220	+	size2++;
1221	+	assertTrue(previousKey < 0 ||
1222	+	(ascending ? key - previousKey > 0 : key - previousKey < 0));
1223	+	previousKey = key;
1224	+	}
1225	+	assertEquals(size2, size);
1226	+
1227	+	// Test navigation ops
1228	+	for (int key = min - 1; key <= max + 1; key++) {
1229	+	assertEq(map.lowerKey(key), rs.lower(key));
1230	+	assertEq(map.floorKey(key), rs.floor(key));
1231	+	assertEq(map.higherKey(key), rs.higher(key));
1232	+	assertEq(map.ceilingKey(key), rs.ceiling(key));
1233	+	}
1234	+
1235	+	// Test extrema
1236	+	if (map.size() != 0) {
1237	+	assertEq(map.firstKey(), rs.first());
1238	+	assertEq(map.lastKey(), rs.last());
1239	+	} else {
1240	+	assertEq(rs.first(), -1);
1241	+	assertEq(rs.last(),  -1);
1242	+	try {
1243	+	map.firstKey();
1244	+	fail();
1245	+	} catch(NoSuchElementException e) {
1246	+	// expected
1247	+	}
1248	+	try {
1249	+	map.lastKey();
1250	+	fail();
1251	+	} catch(NoSuchElementException e) {
1252	+	// expected
1253	+	}
1254	+	}
1255	+	}
1256	+
1257	+	static void assertEq(Integer i, int j) {
1258	+	if (i == null)
1259	+	assertEquals(j, -1);
1260	+	else
1261	+	assertEquals((int) i, j);
1262	+	}
1263	+
1264	+	static boolean eq(Integer i, int j) {
1265	+	return i == null ? j == -1 : i == j;
1266	+	}
1267
1268		}

Diff Legend

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