ViewVC Help

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

root/jsr166/jsr166/src/main/java/util/concurrent/ConcurrentSkipListMap.java

Comparing jsr166/src/main/java/util/concurrent/ConcurrentSkipListMap.java (file contents):
Revision 1.87 by jsr166, Wed Jan 16 22:10:06 2013 UTC vs.
Revision 1.88 by dl, Tue Jan 22 18:25:32 2013 UTC

#	Line 277 | Line 277 | public class ConcurrentSkipListMap<K,V>
277		* there is a fair amount of near-duplication of code to handle
278		* variants.
279		*
280	+	* A previous version of this class wrapped non-comparable keys
281	+	* with their comparators to emulate Comparables when using
282	+	* comparators vs Comparables.  This saved the need to choose
283	+	* among the unpleasant options of either possibly re-reading a
284	+	* comparator on each comparison (which suffers when among all of
285	+	* the volatile read snapshots) versus code duplication, at the
286	+	* cost of usually requiring an object construction per operation
287	+	* when not naturally ordered. However, as usage evolves, use of
288	+	* comparators has become more common, so we have to settle for
289	+	* code duplication as the lesser evil. Thus, there are "xxxCmp"
290	+	* versions of many of the xxx methods, all bundled later in this
291	+	* file.
292	+	*
293		* For explanation of algorithms sharing at least a couple of
294		* features with this one, see Mikhail Fomitchev's thesis
295		* (http://www.cs.yorku.ca/~mikhail/), Keir Fraser's thesis
#	Line 597 | Line 610 | public class ConcurrentSkipListMap<K,V>
610		/* ---------------- Comparison utilities -------------- */
611
612		/**
613	<	* Represents a key with a comparator as a Comparable.
614	<	*
602	<	* Because most sorted collections seem to use natural ordering on
603	<	* Comparables (Strings, Integers, etc), most internal methods are
604	<	* geared to use them. This is generally faster than checking
605	<	* per-comparison whether to use comparator or comparable because
606	<	* it doesn't require a (Comparable) cast for each comparison.
607	<	* (Optimizers can only sometimes remove such redundant checks
608	<	* themselves.) When Comparators are used,
609	<	* ComparableUsingComparators are created so that they act in the
610	<	* same way as natural orderings. This penalizes use of
611	<	* Comparators vs Comparables, which seems like the right
612	<	* tradeoff.
613	<	*/
614	<	static final class ComparableUsingComparator<K> implements Comparable<K> {
615	<	final K actualKey;
616	<	final Comparator<? super K> cmp;
617	<	ComparableUsingComparator(K key, Comparator<? super K> cmp) {
618	<	this.actualKey = key;
619	<	this.cmp = cmp;
620	<	}
621	<	public int compareTo(K k2) {
622	<	return cmp.compare(actualKey, k2);
623	<	}
624	<	}
625	<
626	<	/**
627	<	* If using comparator, return a ComparableUsingComparator, else
628	<	* cast key as Comparable, which may cause ClassCastException,
629	<	* which is propagated back to caller.
630	<	*/
631	<	private Comparable<? super K> comparable(Object key)
632	<	throws ClassCastException {
633	<	if (key == null)
634	<	throw new NullPointerException();
635	<	if (comparator != null)
636	<	return new ComparableUsingComparator<K>((K)key, comparator);
637	<	else
638	<	return (Comparable<? super K>)key;
639	<	}
640	<
641	<	/**
642	<	* Compares using comparator or natural ordering. Used when the
643	<	* ComparableUsingComparator approach doesn't apply.
613	>	* Compares using comparator or natural ordering. Used in cases
614	>	* where it isn't worthwhile to use multiple code paths.
615		*/
616		int compare(K k1, K k2) throws ClassCastException {
617		Comparator<? super K> cmp = comparator;
#	Line 760 | Line 731 | public class ConcurrentSkipListMap<K,V>
731		* @return node holding key, or null if no such
732		*/
733		private Node<K,V> findNode(Comparable<? super K> key) {
734	+	if (key == null)
735	+	throw new NullPointerException(); // don't postpone errors
736		for (;;) {
737		Node<K,V> b = findPredecessor(key);
738		Node<K,V> n = b.next;
#	Line 788 | Line 761 | public class ConcurrentSkipListMap<K,V>
761		}
762
763		/**
764	<	* Gets value for key using findNode.
764	>	* Gets value for key. Almost the same as findNode, but returns
765	>	* the found value (to avoid retries during re-reads)
766	>	*
767		* @param okey the key
768		* @return the value, or null if absent
769		*/
770		private V doGet(Object okey) {
771	<	Comparable<? super K> key = comparable(okey);
772	<	/*
773	<	* Loop needed here and elsewhere in case value field goes
774	<	* null just as it is about to be returned, in which case we
800	<	* lost a race with a deletion, so must retry.
801	<	*/
771	>	if (okey == null)
772	>	throw new NullPointerException();
773	>	@SuppressWarnings("unchecked") Comparable<? super K> key =
774	>	(Comparable<? super K>)okey;
775		for (;;) {
776	<	Node<K,V> n = findNode(key);
777	<	if (n == null)
778	<	return null;
779	<	Object v = n.value;
780	<	if (v != null)
781	<	return (V)v;
776	>	Node<K,V> b = findPredecessor(key);
777	>	Node<K,V> n = b.next;
778	>	for (;;) {
779	>	if (n == null)
780	>	return null;
781	>	Node<K,V> f = n.next;
782	>	if (n != b.next)                // inconsistent read
783	>	break;
784	>	Object v = n.value;
785	>	if (v == null) {                // n is deleted
786	>	n.helpDelete(b, f);
787	>	break;
788	>	}
789	>	if (v == n || b.value == null)  // b is deleted
790	>	break;
791	>	int c = key.compareTo(n.key);
792	>	if (c == 0)
793	>	return (V)v;
794	>	if (c < 0)
795	>	return null;
796	>	b = n;
797	>	n = f;
798	>	}
799		}
800		}
801
802	+
803		/* ---------------- Insertion -------------- */
804
805		/**
#	Line 820 | Line 811 | public class ConcurrentSkipListMap<K,V>
811		* @return the old value, or null if newly inserted
812		*/
813		private V doPut(K kkey, V value, boolean onlyIfAbsent) {
814	<	Comparable<? super K> key = comparable(kkey);
814	>	if (kkey == null)
815	>	throw new NullPointerException();
816	>	@SuppressWarnings("unchecked") Comparable<? super K> key =
817	>	(Comparable<? super K>)kkey;
818		for (;;) {
819		Node<K,V> b = findPredecessor(key);
820		Node<K,V> n = b.next;
#	Line 869 | Line 863 | public class ConcurrentSkipListMap<K,V>
863		*/
864		private int randomLevel() {
865		int x = ThreadLocalRandom.nextSecondarySeed();
866	<	if ((x & 0x80000001) != 0) // test highest and lowest bits
867	<	return 0;
868	<	int level = 1;
869	<	while (((x >>>= 1) & 1) != 0) ++level;
866	>	int level = 0;
867	>	if ((x & 0x80000001) == 0) { // test highest and lowest bits
868	>	do { ++level; }
869	>	while (((x >>>= 1) & 1) != 0);
870	>	}
871		return level;
872		}
873
#	Line 935 | Line 930 | public class ConcurrentSkipListMap<K,V>
930		* snapshotted by callers to provide correct insertion level
931		* @param indexLevel the level of the index
932		*/
933	+	@SuppressWarnings("unchecked")
934		private void addIndex(Index<K,V> idx, HeadIndex<K,V> h, int indexLevel) {
935		// Track next level to insert in case of retries
936		int insertionLevel = indexLevel;
937	<	Comparable<? super K> key = comparable(idx.node.key);
937	>	K key = idx.node.key;
938		if (key == null) throw new NullPointerException();
939	<
939	>	Comparator<? super K> cmp = comparator;
940		// Similar to findPredecessor, but adding index nodes along
941		// path to key.
942		for (;;) {
#	Line 952 | Line 948 | public class ConcurrentSkipListMap<K,V>
948		if (r != null) {
949		Node<K,V> n = r.node;
950		// compare before deletion check avoids needing recheck
951	<	int c = key.compareTo(n.key);
951	>	int c = (cmp == null?
952	>	((Comparable<? super K>)key).compareTo(n.key) :
953	>	cmp.compare(key, n.key));
954		if (n.value == null) {
955		if (!q.unlink(r))
956		break;
#	Line 969 | Line 967 | public class ConcurrentSkipListMap<K,V>
967		if (j == insertionLevel) {
968		// Don't insert index if node already deleted
969		if (t.indexesDeletedNode()) {
970	<	findNode(key); // cleans up
970	>	if (cmp == null)
971	>	findNode((Comparable<? super K>)key); // cleans up
972	>	else
973	>	findNodeCmp(cmp, key);
974		return;
975		}
976		if (!q.link(r, t))
977		break; // restart
978		if (--insertionLevel == 0) {
979		// need final deletion check before return
980	<	if (t.indexesDeletedNode())
981	<	findNode(key);
980	>	if (t.indexesDeletedNode()) {
981	>	if (cmp == null)
982	>	findNode((Comparable<? super K>)key);
983	>	else
984	>	findNodeCmp(cmp, key);
985	>	}
986		return;
987		}
988		}
#	Line 1012 | Line 1017 | public class ConcurrentSkipListMap<K,V>
1017		* @return the node, or null if not found
1018		*/
1019		final V doRemove(Object okey, Object value) {
1020	<	Comparable<? super K> key = comparable(okey);
1020	>	if (okey == null)
1021	>	throw new NullPointerException();
1022	>	@SuppressWarnings("unchecked") Comparable<? super K> key =
1023	>	(Comparable<? super K>)okey;
1024		for (;;) {
1025		Node<K,V> b = findPredecessor(key);
1026		Node<K,V> n = b.next;
#	Line 1152 | Line 1160 | public class ConcurrentSkipListMap<K,V>
1160		}
1161		}
1162
1163	+	/**
1164	+	* Removes last entry; returns its snapshot.
1165	+	* Specialized variant of doRemove.
1166	+	* @return null if empty, else snapshot of last entry
1167	+	*/
1168	+	Map.Entry<K,V> doRemoveLastEntry() {
1169	+	for (;;) {
1170	+	Node<K,V> b = findPredecessorOfLast();
1171	+	Node<K,V> n = b.next;
1172	+	if (n == null) {
1173	+	if (b.isBaseHeader())               // empty
1174	+	return null;
1175	+	else
1176	+	continue; // all b's successors are deleted; retry
1177	+	}
1178	+	for (;;) {
1179	+	Node<K,V> f = n.next;
1180	+	if (n != b.next)                    // inconsistent read
1181	+	break;
1182	+	Object v = n.value;
1183	+	if (v == null) {                    // n is deleted
1184	+	n.helpDelete(b, f);
1185	+	break;
1186	+	}
1187	+	if (v == n || b.value == null)      // b is deleted
1188	+	break;
1189	+	if (f != null) {
1190	+	b = n;
1191	+	n = f;
1192	+	continue;
1193	+	}
1194	+	if (!n.casValue(v, null))
1195	+	break;
1196	+	K key = n.key;
1197	+	Comparator<? super K> cmp = comparator;
1198	+	if (!n.appendMarker(f) || !b.casNext(n, f)) {
1199	+	if (cmp == null)                // Retry via findNode
1200	+	findNode((Comparable<? super K>)key);
1201	+	else
1202	+	findNodeCmp(cmp, key);
1203	+	}
1204	+	else {                              // Clean index
1205	+	if (cmp == null)
1206	+	findPredecessor((Comparable<? super K>)key);
1207	+	else
1208	+	findPredecessorCmp(cmp, key);
1209	+	if (head.right == null)
1210	+	tryReduceLevel();
1211	+	}
1212	+	return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
1213	+	}
1214	+	}
1215	+	}
1216
1217		/* ---------------- Finding and removing last element -------------- */
1218
#	Line 1232 | Line 1293 | public class ConcurrentSkipListMap<K,V>
1293		}
1294		}
1295
1296	+	/* ---------------- Relational operations -------------- */
1297	+
1298	+	// Control values OR'ed as arguments to findNear
1299	+
1300	+	private static final int EQ = 1;
1301	+	private static final int LT = 2;
1302	+	private static final int GT = 0; // Actually checked as !LT
1303	+
1304		/**
1305	<	* Removes last entry; returns its snapshot.
1306	<	* Specialized variant of doRemove.
1307	<	* @return null if empty, else snapshot of last entry
1305	>	* Utility for ceiling, floor, lower, higher methods.
1306	>	* @param kkey the key
1307	>	* @param rel the relation -- OR'ed combination of EQ, LT, GT
1308	>	* @return nearest node fitting relation, or null if no such
1309		*/
1310	<	Map.Entry<K,V> doRemoveLastEntry() {
1310	>	Node<K,V> doFindNear(K kkey, int rel) {
1311	>	@SuppressWarnings("unchecked") Comparable<? super K> key =
1312	>	(Comparable<? super K>)kkey;
1313		for (;;) {
1314	<	Node<K,V> b = findPredecessorOfLast();
1314	>	Node<K,V> b = findPredecessor(key);
1315		Node<K,V> n = b.next;
1316	<	if (n == null) {
1317	<	if (b.isBaseHeader())               // empty
1316	>	for (;;) {
1317	>	if (n == null)
1318	>	return ((rel & LT) == 0 || b.isBaseHeader()) ? null : b;
1319	>	Node<K,V> f = n.next;
1320	>	if (n != b.next)                  // inconsistent read
1321	>	break;
1322	>	Object v = n.value;
1323	>	if (v == null) {                  // n is deleted
1324	>	n.helpDelete(b, f);
1325	>	break;
1326	>	}
1327	>	if (v == n || b.value == null)    // b is deleted
1328	>	break;
1329	>	int c = key.compareTo(n.key);
1330	>	if ((c == 0 && (rel & EQ) != 0) ||
1331	>	(c <  0 && (rel & LT) == 0))
1332	>	return n;
1333	>	if ( c <= 0 && (rel & LT) != 0)
1334	>	return b.isBaseHeader() ? null : b;
1335	>	b = n;
1336	>	n = f;
1337	>	}
1338	>	}
1339	>	}
1340	>
1341	>	/* ---------------- cmp versions -------------- */
1342	>
1343	>	// Boringly almost the same as natural-Comparable ones
1344	>
1345	>	private Node<K,V> findPredecessorCmp(Comparator<? super K> cmp, Object okey) {
1346	>	if (cmp == null)
1347	>	throw new NullPointerException(); // don't postpone errors
1348	>	@SuppressWarnings("unchecked") K key = (K) okey;
1349	>	for (;;) {
1350	>	Index<K,V> q = head;
1351	>	Index<K,V> r = q.right;
1352	>	for (;;) {
1353	>	if (r != null) {
1354	>	Node<K,V> n = r.node;
1355	>	K k = n.key;
1356	>	if (n.value == null) {
1357	>	if (!q.unlink(r))
1358	>	break;           // restart
1359	>	r = q.right;         // reread r
1360	>	continue;
1361	>	}
1362	>	if (cmp.compare(key, k) > 0) {
1363	>	q = r;
1364	>	r = r.right;
1365	>	continue;
1366	>	}
1367	>	}
1368	>	Index<K,V> d = q.down;
1369	>	if (d != null) {
1370	>	q = d;
1371	>	r = d.right;
1372	>	} else
1373	>	return q.node;
1374	>	}
1375	>	}
1376	>	}
1377	>
1378	>	private Node<K,V> findNodeCmp(Comparator<? super K> cmp, Object okey) {
1379	>	if (cmp == null)
1380	>	throw new NullPointerException(); // don't postpone errors
1381	>	@SuppressWarnings("unchecked") K key = (K) okey;
1382	>	for (;;) {
1383	>	Node<K,V> b = findPredecessorCmp(cmp, key);
1384	>	Node<K,V> n = b.next;
1385	>	for (;;) {
1386	>	if (n == null)
1387		return null;
1388	<	else
1389	<	continue; // all b's successors are deleted; retry
1388	>	Node<K,V> f = n.next;
1389	>	if (n != b.next)                // inconsistent read
1390	>	break;
1391	>	Object v = n.value;
1392	>	if (v == null) {                // n is deleted
1393	>	n.helpDelete(b, f);
1394	>	break;
1395	>	}
1396	>	if (v == n || b.value == null)  // b is deleted
1397	>	break;
1398	>	int c = cmp.compare(key, n.key);
1399	>	if (c == 0)
1400	>	return n;
1401	>	if (c < 0)
1402	>	return null;
1403	>	b = n;
1404	>	n = f;
1405		}
1406	+	}
1407	+	}
1408	+
1409	+	private V doGetCmp(Comparator<? super K> cmp, Object okey) {
1410	+	if (cmp == null)
1411	+	throw new NullPointerException(); // don't postpone errors
1412	+	@SuppressWarnings("unchecked") K key = (K) okey;
1413	+	for (;;) {
1414	+	Node<K,V> b = findPredecessorCmp(cmp, key);
1415	+	Node<K,V> n = b.next;
1416		for (;;) {
1417	+	if (n == null)
1418	+	return null;
1419	+	Node<K,V> f = n.next;
1420	+	if (n != b.next)                // inconsistent read
1421	+	break;
1422	+	Object v = n.value;
1423	+	if (v == null) {                // n is deleted
1424	+	n.helpDelete(b, f);
1425	+	break;
1426	+	}
1427	+	if (v == n || b.value == null)  // b is deleted
1428	+	break;
1429	+	int c = cmp.compare(key, n.key);
1430	+	if (c == 0)
1431	+	return (V)v;
1432	+	if (c < 0)
1433	+	return null;
1434	+	b = n;
1435	+	n = f;
1436	+	}
1437	+	}
1438	+	}
1439	+
1440	+	private V doPutCmp(Comparator<? super K> cmp, K key, V value, boolean onlyIfAbsent) {
1441	+	if (cmp == null)
1442	+	throw new NullPointerException(); // don't postpone errors
1443	+	for (;;) {
1444	+	Node<K,V> b = findPredecessorCmp(cmp, key);
1445	+	Node<K,V> n = b.next;
1446	+	for (;;) {
1447	+	if (n != null) {
1448	+	Node<K,V> f = n.next;
1449	+	if (n != b.next)               // inconsistent read
1450	+	break;
1451	+	Object v = n.value;
1452	+	if (v == null) {               // n is deleted
1453	+	n.helpDelete(b, f);
1454	+	break;
1455	+	}
1456	+	if (v == n || b.value == null) // b is deleted
1457	+	break;
1458	+	int c = cmp.compare(key, n.key);
1459	+	if (c > 0) {
1460	+	b = n;
1461	+	n = f;
1462	+	continue;
1463	+	}
1464	+	if (c == 0) {
1465	+	if (onlyIfAbsent || n.casValue(v, value))
1466	+	return (V)v;
1467	+	else
1468	+	break; // restart if lost race to replace value
1469	+	}
1470	+	// else c < 0; fall through
1471	+	}
1472	+
1473	+	Node<K,V> z = new Node<K,V>(key, value, n);
1474	+	if (!b.casNext(n, z))
1475	+	break;         // restart if lost race to append to b
1476	+	int level = randomLevel();
1477	+	if (level > 0)
1478	+	insertIndex(z, level);
1479	+	return null;
1480	+	}
1481	+	}
1482	+	}
1483	+
1484	+	final V doRemoveCmp(Comparator<? super K> cmp, Object okey, Object value) {
1485	+	if (cmp == null)
1486	+	throw new NullPointerException(); // don't postpone errors
1487	+	@SuppressWarnings("unchecked") K key = (K) okey;
1488	+	for (;;) {
1489	+	Node<K,V> b = findPredecessorCmp(cmp, key);
1490	+	Node<K,V> n = b.next;
1491	+	for (;;) {
1492	+	if (n == null)
1493	+	return null;
1494		Node<K,V> f = n.next;
1495		if (n != b.next)                    // inconsistent read
1496		break;
#	Line 1258 | Line 1501 | public class ConcurrentSkipListMap<K,V>
1501		}
1502		if (v == n || b.value == null)      // b is deleted
1503		break;
1504	<	if (f != null) {
1504	>	int c = cmp.compare(key, n.key);
1505	>	if (c < 0)
1506	>	return null;
1507	>	if (c > 0) {
1508		b = n;
1509		n = f;
1510		continue;
1511		}
1512	+	if (value != null && !value.equals(v))
1513	+	return null;
1514		if (!n.casValue(v, null))
1515		break;
1268	–	K key = n.key;
1269	–	Comparable<? super K> ck = comparable(key);
1516		if (!n.appendMarker(f) || !b.casNext(n, f))
1517	<	findNode(ck);                  // Retry via findNode
1517	>	findNodeCmp(cmp, key);          // Retry via findNode
1518		else {
1519	<	findPredecessor(ck);           // Clean index
1519	>	findPredecessorCmp(cmp, key);   // Clean index
1520		if (head.right == null)
1521		tryReduceLevel();
1522		}
1523	<	return new AbstractMap.SimpleImmutableEntry<K,V>(key, (V)v);
1523	>	return (V)v;
1524		}
1525		}
1526		}
1527
1528	<	/* ---------------- Relational operations -------------- */
1529	<
1530	<	// Control values OR'ed as arguments to findNear
1285	<
1286	<	private static final int EQ = 1;
1287	<	private static final int LT = 2;
1288	<	private static final int GT = 0; // Actually checked as !LT
1289	<
1290	<	/**
1291	<	* Utility for ceiling, floor, lower, higher methods.
1292	<	* @param kkey the key
1293	<	* @param rel the relation -- OR'ed combination of EQ, LT, GT
1294	<	* @return nearest node fitting relation, or null if no such
1295	<	*/
1296	<	Node<K,V> findNear(K kkey, int rel) {
1297	<	Comparable<? super K> key = comparable(kkey);
1528	>	Node<K,V> doFindNearCmp(Comparator<? super K> cmp, K key, int rel) {
1529	>	if (cmp == null)
1530	>	throw new NullPointerException(); // don't postpone errors
1531		for (;;) {
1532	<	Node<K,V> b = findPredecessor(key);
1532	>	Node<K,V> b = findPredecessorCmp(cmp, key);
1533		Node<K,V> n = b.next;
1534		for (;;) {
1535		if (n == null)
#	Line 1311 | Line 1544 | public class ConcurrentSkipListMap<K,V>
1544		}
1545		if (v == n || b.value == null)    // b is deleted
1546		break;
1547	<	int c = key.compareTo(n.key);
1547	>	int c = cmp.compare(key, n.key);
1548		if ((c == 0 && (rel & EQ) != 0) ||
1549		(c <  0 && (rel & LT) == 0))
1550		return n;
#	Line 1323 | Line 1556 | public class ConcurrentSkipListMap<K,V>
1556		}
1557		}
1558
1559	+	/* ---------------- Relays to natural vs cmp methods -------------- */
1560	+
1561	+	Node<K,V> findNear(K key, int rel) {
1562	+	Comparator<? super K> cmp;
1563	+	return (cmp = comparator) == null ? doFindNear(key, rel) :
1564	+	doFindNearCmp(cmp, key, rel);
1565	+	}
1566	+
1567		/**
1568		* Returns SimpleImmutableEntry for results of findNear.
1569		* @param key the key
#	Line 1340 | Line 1581 | public class ConcurrentSkipListMap<K,V>
1581		}
1582		}
1583
1343	–
1584		/* ---------------- Constructors -------------- */
1585
1586		/**
#	Line 1600 | Line 1840 | public class ConcurrentSkipListMap<K,V>
1840		* @throws NullPointerException if the specified key is null
1841		*/
1842		public boolean containsKey(Object key) {
1843	<	return doGet(key) != null;
1843	>	Comparator<? super K> cmp;
1844	>	Object v  = ((cmp = comparator) == null ? doGet(key) :
1845	>	doGetCmp(cmp, key));
1846	>	return v != null;
1847		}
1848
1849		/**
#	Line 1618 | Line 1861 | public class ConcurrentSkipListMap<K,V>
1861		* @throws NullPointerException if the specified key is null
1862		*/
1863		public V get(Object key) {
1864	<	return doGet(key);
1864	>	Comparator<? super K> cmp;
1865	>	return ((cmp = comparator) == null) ? doGet(key) : doGetCmp(cmp, key);
1866		}
1867
1868		/**
#	Line 1635 | Line 1879 | public class ConcurrentSkipListMap<K,V>
1879		* @throws NullPointerException if the specified key or value is null
1880		*/
1881		public V put(K key, V value) {
1882	+	Comparator<? super K> cmp;
1883		if (value == null)
1884		throw new NullPointerException();
1885	<	return doPut(key, value, false);
1885	>	return ((cmp = comparator) == null) ?
1886	>	doPut(key, value, false) : doPutCmp(cmp, key, value, false);
1887		}
1888
1889		/**
#	Line 1651 | Line 1897 | public class ConcurrentSkipListMap<K,V>
1897		* @throws NullPointerException if the specified key is null
1898		*/
1899		public V remove(Object key) {
1900	<	return doRemove(key, null);
1900	>	Comparator<? super K> cmp;
1901	>	return ((cmp = comparator) == null) ? doRemove(key, null) :
1902	>	doRemoveCmp(cmp, key, null);
1903		}
1904
1905		/**
#	Line 1889 | Line 2137 | public class ConcurrentSkipListMap<K,V>
2137		* @throws NullPointerException if the specified key or value is null
2138		*/
2139		public V putIfAbsent(K key, V value) {
2140	+	Comparator<? super K> cmp;
2141		if (value == null)
2142		throw new NullPointerException();
2143	<	return doPut(key, value, true);
2143	>	return ((cmp = comparator) == null) ?
2144	>	doPut(key, value, true) : doPutCmp(cmp, key, value, true);
2145		}
2146
2147		/**
#	Line 1906 | Line 2156 | public class ConcurrentSkipListMap<K,V>
2156		throw new NullPointerException();
2157		if (value == null)
2158		return false;
2159	<	return doRemove(key, value) != null;
2159	>	Comparator<? super K> cmp;
2160	>	Object v = ((cmp = comparator) == null) ? doRemove(key, value) :
2161	>	doRemoveCmp(cmp, key, value);
2162	>	return v != null;
2163		}
2164
2165		/**
#	Line 1919 | Line 2172 | public class ConcurrentSkipListMap<K,V>
2172		public boolean replace(K key, V oldValue, V newValue) {
2173		if (oldValue == null || newValue == null)
2174		throw new NullPointerException();
2175	<	Comparable<? super K> k = comparable(key);
2175	>	Comparator<? super K> cmp = comparator;
2176		for (;;) {
2177	<	Node<K,V> n = findNode(k);
2177	>	Node<K,V> n = (cmp == null)? findNode((Comparable<? super K>)key) :
2178	>	findNodeCmp(cmp, key);
2179		if (n == null)
2180		return false;
2181		Object v = n.value;
#	Line 1946 | Line 2200 | public class ConcurrentSkipListMap<K,V>
2200		public V replace(K key, V value) {
2201		if (value == null)
2202		throw new NullPointerException();
2203	<	Comparable<? super K> k = comparable(key);
2203	>	Comparator<? super K> cmp = comparator;
2204		for (;;) {
2205	<	Node<K,V> n = findNode(k);
2205	>	Node<K,V> n = (cmp == null)? findNode((Comparable<? super K>)key) :
2206	>	findNodeCmp(cmp, key);
2207		if (n == null)
2208		return null;
2209		Object v = n.value;
#	Line 2071 | Line 2326 | public class ConcurrentSkipListMap<K,V>
2326		* @throws NullPointerException if the specified key is null
2327		*/
2328		public K lowerKey(K key) {
2329	+	Comparator<? super K> cmp;
2330		Node<K,V> n = findNear(key, LT);
2331		return (n == null) ? null : n.key;
2332		}
#	Line 2722 | Line 2978 | public class ConcurrentSkipListMap<K,V>
2978		K k = n.key;
2979		if (!inBounds(k))
2980		return null;
2981	<	V v = m.doRemove(k, null);
2981	>	V v = (m.comparator == null) ? m.doRemove(k, null) :
2982	>	m.doRemoveCmp(m.comparator, k, null);
2983		if (v != null)
2984		return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
2985		}
#	Line 2736 | Line 2993 | public class ConcurrentSkipListMap<K,V>
2993		K k = n.key;
2994		if (!inBounds(k))
2995		return null;
2996	<	V v = m.doRemove(k, null);
2996	>	V v = (m.comparator == null) ? m.doRemove(k, null) :
2997	>	m.doRemoveCmp(m.comparator, k, null);
2998		if (v != null)
2999		return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
3000		}
#	Line 3134 | Line 3392 | public class ConcurrentSkipListMap<K,V>
3392		}
3393
3394		private void descend() {
3395	+	Comparator<? super K> cmp = m.comparator;
3396		for (;;) {
3397	<	next = m.findNear(lastReturned.key, LT);
3397	>	next = (cmp == null) ? m.doFindNear(lastReturned.key, LT) :
3398	>	m.doFindNearCmp(cmp, lastReturned.key, LT);
3399		if (next == null)
3400		break;
3401		Object x = next.value;
#	Line 3351 | Line 3611 | public class ConcurrentSkipListMap<K,V>
3611		final K fence;     // exclusive upper bound for keys, or null if to end
3612		Index<K,V> row;    // the level to split out
3613		Node<K,V> current; // current traversal node; initialize at origin
3354	–	V nextValue;       // cached value field of next
3614		int est;           // pseudo-size estimate
3615
3616		CSLMSpliterator(Comparator<? super K> comparator, Index<K,V> row,
#	Line 3374 | Line 3633 | public class ConcurrentSkipListMap<K,V>
3633		public final long estimateSize() { return (long)est; }
3634		public final boolean hasExactSize() { return est == 0; }
3635		public final boolean hasExactSplits() { return false; }
3377	–
3378	–	// iterator support
3379	–	public final boolean hasNext() {
3380	–	return current != null && compareBounds(current.key) < 0;
3381	–	}
3382	–
3383	–	final void ascend(Node<K,V> e) {
3384	–	if (e != null) {
3385	–	while ((e = e.next) != null) {
3386	–	Object x = e.value;
3387	–	if (x != null && x != e) {
3388	–	if (compareBounds(e.key) >= 0)
3389	–	e = null;
3390	–	else
3391	–	nextValue = (V) x;
3392	–	break;
3393	–	}
3394	–	}
3395	–	current = e;
3396	–	}
3397	–	}
3398	–
3399	–	public final void remove() { throw new UnsupportedOperationException(); }
3636		}
3637
3638		// factory methods
#	Line 3452 | Line 3688 | public class ConcurrentSkipListMap<K,V>
3688		}
3689
3690		static final class KeySpliterator<K,V> extends CSLMSpliterator<K,V>
3691	<	implements Spliterator<K>, Iterator<K> {
3691	>	implements Spliterator<K> {
3692		KeySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3693		Node<K,V> origin, K fence, int est) {
3694		super(comparator, row, origin, fence, est);
#	Line 3525 | Line 3761 | public class ConcurrentSkipListMap<K,V>
3761		current = e;
3762		return false;
3763		}
3528	–
3529	–	public Iterator<K> iterator() { return this; }
3530	–
3531	–	public K next() {
3532	–	Node<K,V> e = current;
3533	–	if (e == null)
3534	–	throw new NoSuchElementException();
3535	–	ascend(e);
3536	–	return e.key;
3537	–	}
3764		}
3765
3766		static final class ValueSpliterator<K,V> extends CSLMSpliterator<K,V>
3767	<	implements Spliterator<V>, Iterator<V> {
3767	>	implements Spliterator<V> {
3768		ValueSpliterator(Comparator<? super K> comparator, Index<K,V> row,
3769		Node<K,V> origin, K fence, int est) {
3770		super(comparator, row, origin, fence, est);
#	Line 3612 | Line 3838 | public class ConcurrentSkipListMap<K,V>
3838		current = e;
3839		return false;
3840		}
3615	–
3616	–	public Iterator<V> iterator() { return this; }
3617	–
3618	–	public V next() {
3619	–	V v = nextValue;
3620	–	Node<K,V> e = current;
3621	–	if (e == null)
3622	–	throw new NoSuchElementException();
3623	–	ascend(e);
3624	–	return v;
3625	–	}
3841		}
3842
3843		static final class EntrySpliterator<K,V> extends CSLMSpliterator<K,V>
3844	<	implements Spliterator<Map.Entry<K,V>>, Iterator<Map.Entry<K,V>> {
3844	>	implements Spliterator<Map.Entry<K,V>> {
3845		EntrySpliterator(Comparator<? super K> comparator, Index<K,V> row,
3846		Node<K,V> origin, K fence, int est) {
3847		super(comparator, row, origin, fence, est);
#	Line 3703 | Line 3918 | public class ConcurrentSkipListMap<K,V>
3918		current = e;
3919		return false;
3920		}
3706	–
3707	–	public Iterator<Map.Entry<K,V>> iterator() { return this; }
3708	–
3709	–	public Map.Entry<K,V> next() {
3710	–	Node<K,V> e = current;
3711	–	if (e == null)
3712	–	throw new NoSuchElementException();
3713	–	K k = e.key;
3714	–	V v = nextValue;
3715	–	ascend(e);
3716	–	return new AbstractMap.SimpleImmutableEntry<K,V>(k, v);
3717	–	}
3921		}
3922
3923		// Unsafe mechanics

Diff Legend

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