ViewVC Help

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

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

Comparing jsr166/src/main/java/util/concurrent/ConcurrentHashMap.java (file contents):
Revision 1.216 by jsr166, Fri May 24 03:27:47 2013 UTC vs.
Revision 1.217 by dl, Wed May 29 14:38:26 2013 UTC

#	Line 166 | Line 166 | import java.util.stream.Stream;
166		* argument. Methods proceed sequentially if the current map size is
167		* estimated to be less than the given threshold. Using a value of
168		* {@code Long.MAX_VALUE} suppresses all parallelism.  Using a value
169	<	* of {@code 1} results in maximal parallelism.  In-between values can
170	<	* be used to trade off overhead versus throughput. Parallel forms use
171	<	* the {@link ForkJoinPool#commonPool()}.
169	>	* of {@code 1} results in maximal parallelism by partitioning into
170	>	* enough subtasks to utilize all processors. Normally, you would
171	>	* initially choose one of these extreme values, and then measure
172	>	* performance of using in-between values that trade off overhead
173	>	* versus throughput. Parallel forms use the {@link
174	>	* ForkJoinPool#commonPool()}.
175		*
176		* <p>The concurrency properties of bulk operations follow
177		* from those of ConcurrentHashMap: Any non-null result returned
#	Line 795 | Line 798 | public class ConcurrentHashMap<K,V> impl
798		else if (cc == null || comparableClassFor(pk) != cc ||
799		(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
800		TreeNode<K,V> r, pr; // check both sides
801	<	if ((pr = p.right) != null && h >= pr.hash &&
801	>	if ((pr = p.right) != null &&
802		(r = getTreeNode(h, k, pr, cc)) != null)
803		return r;
804		else // continue left
#	Line 850 | Line 853 | public class ConcurrentHashMap<K,V> impl
853		else if (cc == null || comparableClassFor(pk) != cc ||
854		(dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {
855		TreeNode<K,V> r, pr;
856	<	if ((pr = p.right) != null && h >= pr.hash &&
856	>	if ((pr = p.right) != null &&
857		(r = getTreeNode(h, k, pr, cc)) != null)
858		return r;
859		else // continue left
#	Line 864 | Line 867 | public class ConcurrentHashMap<K,V> impl
867		if (p == null)
868		root = x;
869		else { // attach and rebalance; adapted from CLR
867	–	TreeNode<K,V> xp, xpp;
870		if (f != null)
871		f.prev = x;
872		if (dir <= 0)
#	Line 872 | Line 874 | public class ConcurrentHashMap<K,V> impl
874		else
875		p.right = x;
876		x.red = true;
877	<	while (x != null && (xp = x.parent) != null && xp.red &&
878	<	(xpp = xp.parent) != null) {
879	<	TreeNode<K,V> xppl = xpp.left;
880	<	if (xp == xppl) {
881	<	TreeNode<K,V> y = xpp.right;
882	<	if (y != null && y.red) {
883	<	y.red = false;
877	>	for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
878	>	if ((xp = x.parent) == null) {
879	>	(root = x).red = false;
880	>	break;
881	>	}
882	>	else if (!xp.red || (xpp = xp.parent) == null) {
883	>	TreeNode<K,V> r = root;
884	>	if (r != null && r.red)
885	>	r.red = false;
886	>	break;
887	>	}
888	>	else if ((xppl = xpp.left) == xp) {
889	>	if ((xppr = xpp.right) != null && xppr.red) {
890	>	xppr.red = false;
891		xp.red = false;
892		xpp.red = true;
893		x = xpp;
#	Line 898 | Line 907 | public class ConcurrentHashMap<K,V> impl
907		}
908		}
909		else {
910	<	TreeNode<K,V> y = xppl;
911	<	if (y != null && y.red) {
903	<	y.red = false;
910	>	if (xppl != null && xppl.red) {
911	>	xppl.red = false;
912		xp.red = false;
913		xpp.red = true;
914		x = xpp;
#	Line 920 | Line 928 | public class ConcurrentHashMap<K,V> impl
928		}
929		}
930		}
923	–	TreeNode<K,V> r = root;
924	–	if (r != null && r.red)
925	–	r.red = false;
931		}
932	+	assert checkInvariants();
933		return null;
934		}
935
#	Line 944 | Line 950 | public class ConcurrentHashMap<K,V> impl
950		pred.next = next;
951		if (next != null)
952		next.prev = pred;
953	+	else if (pred == null) {
954	+	root = null;
955	+	return;
956	+	}
957		TreeNode<K,V> replacement;
958		TreeNode<K,V> pl = p.left;
959		TreeNode<K,V> pr = p.right;
#	Line 980 | Line 990 | public class ConcurrentHashMap<K,V> impl
990		pp.left = s;
991		else
992		pp.right = s;
993	<	replacement = sr;
993	>	if (sr != null)
994	>	replacement = sr;
995	>	else
996	>	replacement = p;
997		}
998	+	else if (pl != null)
999	+	replacement = pl;
1000	+	else if (pr != null)
1001	+	replacement = pr;
1002		else
986	–	replacement = (pl != null) ? pl : pr;
987	–	TreeNode<K,V> pp = p.parent;
988	–	if (replacement == null) {
989	–	if (pp == null) {
990	–	root = null;
991	–	return;
992	–	}
1003		replacement = p;
1004	<	}
1005	<	else {
996	<	replacement.parent = pp;
1004	>	if (replacement != p) {
1005	>	TreeNode<K,V> pp = replacement.parent = p.parent;
1006		if (pp == null)
1007		root = replacement;
1008		else if (p == pp.left)
#	Line 1003 | Line 1012 | public class ConcurrentHashMap<K,V> impl
1012		p.left = p.right = p.parent = null;
1013		}
1014		if (!p.red) { // rebalance, from CLR
1015	<	TreeNode<K,V> x = replacement;
1016	<	while (x != null) {
1008	<	TreeNode<K,V> xp, xpl;
1015	>	for (TreeNode<K,V> x = replacement; x != null; ) {
1016	>	TreeNode<K,V> xp, xpl, xpr;
1017		if (x.red || (xp = x.parent) == null) {
1018		x.red = false;
1019		break;
1020		}
1021	<	if (x == (xpl = xp.left)) {
1022	<	TreeNode<K,V> sib = xp.right;
1023	<	if (sib != null && sib.red) {
1016	<	sib.red = false;
1021	>	else if ((xpl = xp.left) == x) {
1022	>	if ((xpr = xp.right) != null && xpr.red) {
1023	>	xpr.red = false;
1024		xp.red = true;
1025		rotateLeft(xp);
1026	<	sib = (xp = x.parent) == null ? null : xp.right;
1026	>	xpr = (xp = x.parent) == null ? null : xp.right;
1027		}
1028	<	if (sib == null)
1028	>	if (xpr == null)
1029		x = xp;
1030		else {
1031	<	TreeNode<K,V> sl = sib.left, sr = sib.right;
1031	>	TreeNode<K,V> sl = xpr.left, sr = xpr.right;
1032		if ((sr == null || !sr.red) &&
1033		(sl == null || !sl.red)) {
1034	<	sib.red = true;
1034	>	xpr.red = true;
1035		x = xp;
1036		}
1037		else {
1038		if (sr == null || !sr.red) {
1039		if (sl != null)
1040		sl.red = false;
1041	<	sib.red = true;
1042	<	rotateRight(sib);
1043	<	sib = (xp = x.parent) == null ?
1041	>	xpr.red = true;
1042	>	rotateRight(xpr);
1043	>	xpr = (xp = x.parent) == null ?
1044		null : xp.right;
1045		}
1046	<	if (sib != null) {
1047	<	sib.red = (xp == null) ? false : xp.red;
1048	<	if ((sr = sib.right) != null)
1046	>	if (xpr != null) {
1047	>	xpr.red = (xp == null) ? false : xp.red;
1048	>	if ((sr = xpr.right) != null)
1049		sr.red = false;
1050		}
1051		if (xp != null) {
#	Line 1050 | Line 1057 | public class ConcurrentHashMap<K,V> impl
1057		}
1058		}
1059		else { // symmetric
1060	<	TreeNode<K,V> sib = xpl;
1061	<	if (sib != null && sib.red) {
1055	<	sib.red = false;
1060	>	if (xpl != null && xpl.red) {
1061	>	xpl.red = false;
1062		xp.red = true;
1063		rotateRight(xp);
1064	<	sib = (xp = x.parent) == null ? null : xp.left;
1064	>	xpl = (xp = x.parent) == null ? null : xp.left;
1065		}
1066	<	if (sib == null)
1066	>	if (xpl == null)
1067		x = xp;
1068		else {
1069	<	TreeNode<K,V> sl = sib.left, sr = sib.right;
1069	>	TreeNode<K,V> sl = xpl.left, sr = xpl.right;
1070		if ((sl == null || !sl.red) &&
1071		(sr == null || !sr.red)) {
1072	<	sib.red = true;
1072	>	xpl.red = true;
1073		x = xp;
1074		}
1075		else {
1076		if (sl == null || !sl.red) {
1077		if (sr != null)
1078		sr.red = false;
1079	<	sib.red = true;
1080	<	rotateLeft(sib);
1081	<	sib = (xp = x.parent) == null ?
1079	>	xpl.red = true;
1080	>	rotateLeft(xpl);
1081	>	xpl = (xp = x.parent) == null ?
1082		null : xp.left;
1083		}
1084	<	if (sib != null) {
1085	<	sib.red = (xp == null) ? false : xp.red;
1086	<	if ((sl = sib.left) != null)
1084	>	if (xpl != null) {
1085	>	xpl.red = (xp == null) ? false : xp.red;
1086	>	if ((sl = xpl.left) != null)
1087		sl.red = false;
1088		}
1089		if (xp != null) {
#	Line 1090 | Line 1096 | public class ConcurrentHashMap<K,V> impl
1096		}
1097		}
1098		}
1099	<	if (p == replacement && (pp = p.parent) != null) {
1100	<	if (p == pp.left) // detach pointers
1101	<	pp.left = null;
1102	<	else if (p == pp.right)
1103	<	pp.right = null;
1104	<	p.parent = null;
1099	>	if (p == replacement) {  // detach pointers
1100	>	TreeNode<K,V> pp;
1101	>	if ((pp = p.parent) != null) {
1102	>	if (p == pp.left)
1103	>	pp.left = null;
1104	>	else if (p == pp.right)
1105	>	pp.right = null;
1106	>	p.parent = null;
1107	>	}
1108		}
1109	+	assert checkInvariants();
1110	+	}
1111	+
1112	+	/**
1113	+	* Checks linkage and balance invariants at root
1114	+	*/
1115	+	final boolean checkInvariants() {
1116	+	TreeNode<K,V> r = root;
1117	+	if (r == null)
1118	+	return (first == null);
1119	+	else
1120	+	return (first != null) && checkTreeNode(r);
1121	+	}
1122	+
1123	+	/**
1124	+	* Recursive invariant check
1125	+	*/
1126	+	final boolean checkTreeNode(TreeNode<K,V> t) {
1127	+	TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
1128	+	tb = t.prev, tn = (TreeNode<K,V>)t.next;
1129	+	if (tb != null && tb.next != t)
1130	+	return false;
1131	+	if (tn != null && tn.prev != t)
1132	+	return false;
1133	+	if (tp != null && t != tp.left && t != tp.right)
1134	+	return false;
1135	+	if (tl != null && (tl.parent != t || tl.hash > t.hash))
1136	+	return false;
1137	+	if (tr != null && (tr.parent != t || tr.hash < t.hash))
1138	+	return false;
1139	+	if (t.red && tl != null && tl.red && tr != null && tr.red)
1140	+	return false;
1141	+	if (tl != null && !checkTreeNode(tl))
1142	+	return false;
1143	+	if (tr != null && !checkTreeNode(tr))
1144	+	return false;
1145	+	return true;
1146		}
1147		}
1148
#	Line 2596 | Line 2642 | public class ConcurrentHashMap<K,V> impl
2642		}
2643
2644		/**
2645	<	* Returns the value to which the specified key is mapped,
2646	<	* or the given defaultValue if this map contains no mapping for the key.
2645	>	* Returns the value to which the specified key is mapped, or the
2646	>	* given default value if this map contains no mapping for the
2647	>	* key.
2648		*
2649	<	* @param key the key
2649	>	* @param @param key the key whose associated value is to be returned
2650		* @param defaultValue the value to return if this map contains
2651		* no mapping for the given key
2652	<	* @return the mapping for the key, if present; else the defaultValue
2652	>	* @return the mapping for the key, if present; else the default value
2653		* @throws NullPointerException if the specified key is null
2654		*/
2655		public V getOrDefault(Object key, V defaultValue) {

Diff Legend

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