ViewVC Help

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

root/jsr166/jsr166/src/jsr166e/ConcurrentHashMapV8.java

Comparing jsr166/src/jsr166e/ConcurrentHashMapV8.java (file contents):
Revision 1.111 by jsr166, Fri Jul 19 19:34:43 2013 UTC vs.
Revision 1.112 by dl, Sat Jul 20 16:50:04 2013 UTC

#	Line 12 | Line 12 | import java.io.ObjectStreamField;
12		import java.io.Serializable;
13		import java.lang.reflect.ParameterizedType;
14		import java.lang.reflect.Type;
15	+	import java.util.AbstractMap;
16		import java.util.Arrays;
17		import java.util.Collection;
18		import java.util.Comparator;
#	Line 218 | Line 219 | import java.util.concurrent.locks.Reentr
219		* @param <K> the type of keys maintained by this map
220		* @param <V> the type of mapped values
221		*/
222	<	public class ConcurrentHashMapV8<K,V>
222	>	public class ConcurrentHashMapV8<K,V> extends AbstractMap<K,V>
223		implements ConcurrentMap<K,V>, Serializable {
224		private static final long serialVersionUID = 7249069246763182397L;
225
#	Line 446 | Line 447 | public class ConcurrentHashMapV8<K,V>
447		* related operations (which is the main reason we cannot use
448		* existing collections such as TreeMaps). TreeBins contain
449		* Comparable elements, but may contain others, as well as
450	<	* elements that are Comparable but not necessarily Comparable
451	<	* for the same T, so we cannot invoke compareTo among them. To
452	<	* handle this, the tree is ordered primarily by hash value, then
453	<	* by Comparable.compareTo order if applicable.  On lookup at a
454	<	* node, if elements are not comparable or compare as 0 then both
455	<	* left and right children may need to be searched in the case of
456	<	* tied hash values. (This corresponds to the full list search
457	<	* that would be necessary if all elements were non-Comparable and
458	<	* had tied hashes.)  The red-black balancing code is updated from
459	<	* pre-jdk-collections
450	>	* elements that are Comparable but not necessarily Comparable for
451	>	* the same T, so we cannot invoke compareTo among them. To handle
452	>	* this, the tree is ordered primarily by hash value, then by
453	>	* Comparable.compareTo order if applicable.  On lookup at a node,
454	>	* if elements are not comparable or compare as 0 then both left
455	>	* and right children may need to be searched in the case of tied
456	>	* hash values. (This corresponds to the full list search that
457	>	* would be necessary if all elements were non-Comparable and had
458	>	* tied hashes.) On insertion, to keep a total ordering (or as
459	>	* close as is required here) across rebalancings, we compare
460	>	* classes and identityHashCodes as tie-breakers. The red-black
461	>	* balancing code is updated from pre-jdk-collections
462		* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
463		* based in turn on Cormen, Leiserson, and Rivest "Introduction to
464		* Algorithms" (CLR).
#	Line 485 | Line 488 | public class ConcurrentHashMapV8<K,V>
488		* unused "Segment" class that is instantiated in minimal form
489		* only when serializing.
490		*
491	+	* Also, solely for compatibility with previous versions of this
492	+	* class, it extends AbstractMap, even though all of its methods
493	+	* are overridden, so it is just useless baggage.
494	+	*
495		* This file is organized to make things a little easier to follow
496		* while reading than they might otherwise: First the main static
497		* declarations and utilities, then fields, then main public
#	Line 2546 | Line 2553 | public class ConcurrentHashMapV8<K,V>
2553		p = pr;
2554		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2555		return p;
2556	<	else if (pl == null && pr == null)
2557	<	break;
2556	>	else if (pl == null)
2557	>	p = pr;
2558	>	else if (pr == null)
2559	>	p = pl;
2560		else if ((kc != null ||
2561		(kc = comparableClassFor(k)) != null) &&
2562		(dir = compareComparables(kc, k, pk)) != 0)
2563		p = (dir < 0) ? pl : pr;
2564	<	else if (pl == null)
2556	<	p = pr;
2557	<	else if (pr == null ||
2558	<	(q = pr.findTreeNode(h, k, kc)) == null)
2559	<	p = pl;
2560	<	else
2564	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2565		return q;
2566	+	else
2567	+	p = pl;
2568		} while (p != null);
2569		}
2570		return null;
#	Line 2585 | Line 2591 | public class ConcurrentHashMapV8<K,V>
2591		static final int READER = 4; // increment value for setting read lock
2592
2593		/**
2594	+	* Tie-breaking utility for ordering insertions when equal
2595	+	* hashCodes and non-comparable. We don't require a total
2596	+	* order, just a consistent insertion rule to maintain
2597	+	* equivalence across rebalancings. Tie-breaking further than
2598	+	* necessary simplifies testing a bit.
2599	+	*/
2600	+	static int tieBreakOrder(Object a, Object b) {
2601	+	int d;
2602	+	if (a == null || b == null ||
2603	+	(d = a.getClass().getName().
2604	+	compareTo(b.getClass().getName())) == 0)
2605	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2606	+	-1 : 1);
2607	+	return d;
2608	+	}
2609	+
2610	+	/**
2611		* Creates bin with initial set of nodes headed by b.
2612		*/
2613		TreeBin(TreeNode<K,V> b) {
#	Line 2600 | Line 2623 | public class ConcurrentHashMapV8<K,V>
2623		r = x;
2624		}
2625		else {
2626	<	Object key = x.key;
2627	<	int hash = x.hash;
2626	>	K k = x.key;
2627	>	int h = x.hash;
2628		Class<?> kc = null;
2629		for (TreeNode<K,V> p = r;;) {
2630		int dir, ph;
2631	<	if ((ph = p.hash) > hash)
2631	>	K pk = p.key;
2632	>	if ((ph = p.hash) > h)
2633		dir = -1;
2634	<	else if (ph < hash)
2634	>	else if (ph < h)
2635		dir = 1;
2636	<	else if ((kc != null ||
2637	<	(kc = comparableClassFor(key)) != null))
2638	<	dir = compareComparables(kc, key, p.key);
2639	<	else
2640	<	dir = 0;
2617	<	TreeNode<K,V> xp = p;
2636	>	else if ((kc == null &&
2637	>	(kc = comparableClassFor(k)) == null) ||
2638	>	(dir = compareComparables(kc, k, pk)) == 0)
2639	>	dir = tieBreakOrder(k, pk);
2640	>	TreeNode<K,V> xp = p;
2641		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2642		x.parent = xp;
2643		if (dir <= 0)
#	Line 2628 | Line 2651 | public class ConcurrentHashMapV8<K,V>
2651		}
2652		}
2653		this.root = r;
2654	+	assert checkInvariants(root);
2655		}
2656
2657		/**
#	Line 2674 | Line 2698 | public class ConcurrentHashMapV8<K,V>
2698		* using tree comparisons from root, but continues linear
2699		* search when lock not available.
2700		*/
2701	<	final Node<K,V> find(int h, Object k) {
2701	>	final Node<K,V> find(int h, Object k) {
2702		if (k != null) {
2703		for (Node<K,V> e = first; e != null; e = e.next) {
2704		int s; K ek;
#	Line 2711 | Line 2735 | public class ConcurrentHashMapV8<K,V>
2735		*/
2736		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2737		Class<?> kc = null;
2738	+	boolean searched = false;
2739		for (TreeNode<K,V> p = root;;) {
2740	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2740	>	int dir, ph; K pk;
2741		if (p == null) {
2742		first = root = new TreeNode<K,V>(h, k, v, null, null);
2743		break;
#	Line 2726 | Line 2751 | public class ConcurrentHashMapV8<K,V>
2751		else if ((kc == null &&
2752		(kc = comparableClassFor(k)) == null) ||
2753		(dir = compareComparables(kc, k, pk)) == 0) {
2754	<	if (p.left == null)
2755	<	dir = 1;
2756	<	else if ((pr = p.right) == null ||
2757	<	(q = pr.findTreeNode(h, k, kc)) == null)
2758	<	dir = -1;
2759	<	else
2760	<	return q;
2754	>	if (!searched) {
2755	>	TreeNode<K,V> q, ch;
2756	>	searched = true;
2757	>	if (((ch = p.left) != null &&
2758	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2759	>	((ch = p.right) != null &&
2760	>	(q = ch.findTreeNode(h, k, kc)) != null))
2761	>	return q;
2762	>	}
2763	>	dir = tieBreakOrder(k, pk);
2764		}
2765	+
2766		TreeNode<K,V> xp = p;
2767	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2767	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2768		TreeNode<K,V> x, f = first;
2769		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2770		if (f != null)
2771		f.prev = x;
2772	<	if (dir < 0)
2772	>	if (dir <= 0)
2773		xp.left = x;
2774		else
2775		xp.right = x;

Diff Legend

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