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.200 by jsr166, Sun Apr 7 15:04:14 2013 UTC vs.
Revision 1.201 by dl, Thu Apr 11 17:41:10 2013 UTC

#	Line 34 | Line 34 | import java.util.concurrent.locks.Abstra
34		import java.util.concurrent.atomic.AtomicInteger;
35		import java.util.concurrent.atomic.AtomicReference;
36		import java.io.Serializable;
37	+	import java.lang.reflect.Type;
38	+	import java.lang.reflect.ParameterizedType;
39
40		/**
41		* A hash table supporting full concurrency of retrievals and
#	Line 449 | Line 451 | public class ConcurrentHashMap<K,V>
451		* bin.  The value reflects the approximate break-even point for
452		* using tree-based operations.
453		*/
454	<	private static final int TREE_THRESHOLD = 8;
454	>	private static final int TREE_THRESHOLD = 16;
455
456		/**
457		* Minimum number of rebinnings per transfer step. Ranges are
#	Line 613 | Line 615 | public class ConcurrentHashMap<K,V>
615		}
616		}
617
618	+
619	+	/**
620	+	* Returns a Class for the given object of the form "class C
621	+	* implements Comparable<C>", if one exists, else null.  See below
622	+	* for explanation.
623	+	*/
624	+	static Class<?> comparableClassFor(Object x) {
625	+	Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;
626	+	if ((c = x.getClass()) == String.class) // bypass checks
627	+	return c;
628	+	if ((cmpc = Comparable.class).isAssignableFrom(c)) {
629	+	while (cmpc.isAssignableFrom(s = c.getSuperclass()))
630	+	c = s; // find topmost comparable class
631	+	if ((ts  = c.getGenericInterfaces()) != null) {
632	+	for (int i = 0; i < ts.length; ++i) {
633	+	if (((t = ts[i]) instanceof ParameterizedType) &&
634	+	((p = (ParameterizedType)t).getRawType() == cmpc) &&
635	+	(as = p.getActualTypeArguments()) != null &&
636	+	as.length == 1 && as[0] == c) // type arg is c
637	+	return c;
638	+	}
639	+	}
640	+	}
641	+	return null;
642	+	}
643	+
644		/**
645		* A specialized form of red-black tree for use in bins
646		* whose size exceeds a threshold.
#	Line 624 | Line 652 | public class ConcurrentHashMap<K,V>
652		* elements that are Comparable but not necessarily Comparable<T>
653		* for the same T, so we cannot invoke compareTo among them. To
654		* handle this, the tree is ordered primarily by hash value, then
655	<	* by getClass().getName() order, and then by Comparator order
656	<	* among elements of the same class.  On lookup at a node, if
657	<	* elements are not comparable or compare as 0, both left and
658	<	* right children may need to be searched in the case of tied hash
659	<	* values. (This corresponds to the full list search that would be
660	<	* necessary if all elements were non-Comparable and had tied
661	<	* hashes.)  The red-black balancing code is updated from
655	>	* by Comparable.compareTo order if applicable, else by class
656	>	* names if both comparable but not to each other.  On lookup at a
657	>	* node, if elements are not comparable or compare as 0 then both
658	>	* left and right children may need to be searched in the case of
659	>	* tied hash values. (This corresponds to the full list search
660	>	* that would be necessary if all elements were non-Comparable and
661	>	* had tied hashes.)  The red-black balancing code is updated from
662		* pre-jdk-collections
663		* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
664		* based in turn on Cormen, Leiserson, and Rivest "Introduction to
#	Line 724 | Line 752 | public class ConcurrentHashMap<K,V>
752		}
753
754		/**
755	+	* Compares k and x: if k's comparable class (cc) matches x's,
756	+	* uses Comparable.compareTo. Otherwise compares on comparable
757	+	* class name if either exist, else 0.
758	+	*/
759	+	@SuppressWarnings("unchecked")
760	+	static int cccompare(Class<?> cc, Object k, Object x) {
761	+	Class<?> cx = comparableClassFor(x);
762	+	return ((cc == null)? ((cx == null)? 0 : 1) :
763	+	(cx == null) ? -1 :
764	+	(cx == cc) ? ((Comparable<Object>)k).compareTo(x) :
765	+	cc.getName().compareTo(cx.getName()));
766	+	}
767	+
768	+	/**
769	+	* Returns the TreeNode (or null if not found) for the given
770	+	* key.  A front-end for recursive version.
771	+	*/
772	+	final TreeNode<V> getTreeNode(int h, Object k) {
773	+	return getTreeNode(h, k, root, comparableClassFor(k));
774	+	}
775	+
776	+	/**
777	+	* Finds or adds a node. A front-end for recursive version
778	+	* @return null if added
779	+	*/
780	+	final TreeNode<V> putTreeNode(int h, Object k, V v) {
781	+	return putTreeNode(h, k, v, comparableClassFor(k));
782	+	}
783	+
784	+	/**
785		* Returns the TreeNode (or null if not found) for the given key
786		* starting at given root.
787		*/
788		@SuppressWarnings("unchecked") final TreeNode<V> getTreeNode
789	<	(int h, Object k, TreeNode<V> p) {
732	<	Class<?> c = k.getClass();
789	>	(int h, Object k, TreeNode<V> p, Class<?> cc) {
790		while (p != null) {
791	<	int dir, ph;  Object pk; Class<?> pc;
792	<	if ((ph = p.hash) == h) {
736	<	if ((pk = p.key) == k || k.equals(pk))
737	<	return p;
738	<	if (c != (pc = pk.getClass()) ||
739	<	!(k instanceof Comparable) ||
740	<	(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
741	<	if ((dir = (c == pc) ? 0 :
742	<	c.getName().compareTo(pc.getName())) == 0) {
743	<	TreeNode<V> r = null, pl, pr; // check both sides
744	<	if ((pr = p.right) != null && h >= pr.hash &&
745	<	(r = getTreeNode(h, k, pr)) != null)
746	<	return r;
747	<	else if ((pl = p.left) != null && h <= pl.hash)
748	<	dir = -1;
749	<	else // nothing there
750	<	return null;
751	<	}
752	<	}
753	<	}
754	<	else
791	>	int dir, ph;  Object pk;
792	>	if ((ph = p.hash) != h)
793		dir = (h < ph) ? -1 : 1;
794	+	else if ((pk = p.key) == k || k.equals(pk))
795	+	return p;
796	+	else if ((dir = cccompare(cc, k, pk)) == 0) {
797	+	TreeNode<V> r, pl, pr; // check both sides
798	+	if ((pr = p.right) != null && h >= pr.hash &&
799	+	(r = getTreeNode(h, k, pr, cc)) != null)
800	+	return r;
801	+	else if ((pl = p.left) != null && h <= pl.hash)
802	+	dir = -1;
803	+	else // nothing there
804	+	break;
805	+	}
806		p = (dir > 0) ? p.right : p.left;
807		}
808		return null;
#	Line 769 | Line 819 | public class ConcurrentHashMap<K,V>
819		for (Node<V> e = first; e != null; e = e.next) {
820		if (c <= 0 && compareAndSetState(c, c - 1)) {
821		try {
822	<	r = getTreeNode(h, k, root);
822	>	r = getTreeNode(h, k, root, comparableClassFor(k));
823		} finally {
824		releaseShared(0);
825		}
#	Line 785 | Line 835 | public class ConcurrentHashMap<K,V>
835		return r == null ? null : r.val;
836		}
837
838	+
839		/**
840	<	* Finds or adds a node.
840	>	* recursive add.
841		* @return null if added
842		*/
843		@SuppressWarnings("unchecked") final TreeNode<V> putTreeNode
844	<	(int h, Object k, V v) {
794	<	Class<?> c = k.getClass();
844	>	(int h, Object k, V v, Class<?> cc) {
845		TreeNode<V> pp = root, p = null;
846		int dir = 0;
847		while (pp != null) { // find existing node or leaf to insert at
848	<	int ph;  Object pk; Class<?> pc;
848	>	int ph;  Object pk;
849		p = pp;
850	<	if ((ph = p.hash) == h) {
801	<	if ((pk = p.key) == k || k.equals(pk))
802	<	return p;
803	<	if (c != (pc = pk.getClass()) ||
804	<	!(k instanceof Comparable) ||
805	<	(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
806	<	TreeNode<V> s = null, r = null, pr;
807	<	if ((dir = (c == pc) ? 0 :
808	<	c.getName().compareTo(pc.getName())) == 0) {
809	<	if ((pr = p.right) != null && h >= pr.hash &&
810	<	(r = getTreeNode(h, k, pr)) != null)
811	<	return r;
812	<	else // continue left
813	<	dir = -1;
814	<	}
815	<	else if ((pr = p.right) != null && h >= pr.hash)
816	<	s = pr;
817	<	if (s != null && (r = getTreeNode(h, k, s)) != null)
818	<	return r;
819	<	}
820	<	}
821	<	else
850	>	if ((ph = p.hash) != h)
851		dir = (h < ph) ? -1 : 1;
852	+	else if ((pk = p.key) == k || k.equals(pk))
853	+	return p;
854	+	else if ((dir = cccompare(cc, k, pk)) == 0) {
855	+	TreeNode<V> r, pr;
856	+	if ((pr = p.right) != null && h >= pr.hash &&
857	+	(r = getTreeNode(h, k, pr, cc)) != null)
858	+	return r;
859	+	else // continue left
860	+	dir = -1;
861	+	}
862		pp = (dir > 0) ? p.right : p.left;
863		}
864
#	Line 1089 | Line 1128 | public class ConcurrentHashMap<K,V>
1128		* only when locked.
1129		*/
1130		private final void replaceWithTreeBin(Node<V>[] tab, int index, Object key) {
1131	<	if (key instanceof Comparable) {
1131	>	if (comparableClassFor(key) != null) {
1132		TreeBin<V> t = new TreeBin<V>();
1133		for (Node<V> e = tabAt(tab, index); e != null; e = e.next)
1134		t.putTreeNode(e.hash, e.key, e.val);
#	Line 1145 | Line 1184 | public class ConcurrentHashMap<K,V>
1184		try {
1185		if (tabAt(tab, i) == f) {
1186		validated = true;
1187	<	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1187	>	TreeNode<V> p = t.getTreeNode(h, k);
1188		if (p != null) {
1189		V pv = p.val;
1190		if (cv == null || cv == pv || cv.equals(pv)) {
#	Line 1346 | Line 1385 | public class ConcurrentHashMap<K,V>
1385		try {
1386		if (tabAt(tab, i) == f) {
1387		len = 1;
1388	<	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1388	>	TreeNode<V> p = t.getTreeNode(h, k);
1389		if (p != null)
1390		val = p.val;
1391		else if ((val = mf.apply(k)) != null) {
#	Line 1453 | Line 1492 | public class ConcurrentHashMap<K,V>
1492		try {
1493		if (tabAt(tab, i) == f) {
1494		len = 1;
1495	<	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1495	>	TreeNode<V> p = t.getTreeNode(h, k);
1496		if (p == null && onlyIfPresent)
1497		break;
1498		V pv = (p == null) ? null : p.val;
#	Line 1552 | Line 1591 | public class ConcurrentHashMap<K,V>
1591		try {
1592		if (tabAt(tab, i) == f) {
1593		len = 1;
1594	<	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1594	>	TreeNode<V> p = t.getTreeNode(h, k);
1595		val = (p == null) ? v : mf.apply(p.val, v);
1596		if (val != null) {
1597		if (p != null)
#	Line 1653 | Line 1692 | public class ConcurrentHashMap<K,V>
1692		try {
1693		if (tabAt(tab, i) == f) {
1694		validated = true;
1695	<	TreeNode<V> p = t.getTreeNode(h, k, t.root);
1695	>	TreeNode<V> p = t.getTreeNode(h, k);
1696		if (p != null)
1697		p.val = v;
1698		else {

Diff Legend

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