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.110 by dl, Thu Jul 4 18:34:49 2013 UTC vs.
Revision 1.113 by jsr166, Mon Jul 22 16:54:43 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 1359 | Line 1366 | public class ConcurrentHashMapV8<K,V>
1366		* Saves the state of the {@code ConcurrentHashMapV8} instance to a
1367		* stream (i.e., serializes it).
1368		* @param s the stream
1369	+	* @throws java.io.IOException if an I/O error occurs
1370		* @serialData
1371		* the key (Object) and value (Object)
1372		* for each key-value mapping, followed by a null pair.
#	Line 1401 | Line 1409 | public class ConcurrentHashMapV8<K,V>
1409		/**
1410		* Reconstitutes the instance from a stream (that is, deserializes it).
1411		* @param s the stream
1412	+	* @throws ClassNotFoundException if the class of a serialized object
1413	+	*         could not be found
1414	+	* @throws java.io.IOException if an I/O error occurs
1415		*/
1416		private void readObject(java.io.ObjectInputStream s)
1417		throws java.io.IOException, ClassNotFoundException {
#	Line 2101 | Line 2112 | public class ConcurrentHashMapV8<K,V>
2112		*
2113		* @param initialCapacity The implementation performs internal
2114		* sizing to accommodate this many elements.
2115	+	* @return the new set
2116		* @throws IllegalArgumentException if the initial capacity of
2117		* elements is negative
2106	–	* @return the new set
2118		* @since 1.8
2119		*/
2120		public static <K> KeySetView<K,Boolean> newKeySet(int initialCapacity) {
#	Line 2546 | Line 2557 | public class ConcurrentHashMapV8<K,V>
2557		p = pr;
2558		else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
2559		return p;
2560	<	else if (pl == null && pr == null)
2561	<	break;
2560	>	else if (pl == null)
2561	>	p = pr;
2562	>	else if (pr == null)
2563	>	p = pl;
2564		else if ((kc != null ||
2565		(kc = comparableClassFor(k)) != null) &&
2566		(dir = compareComparables(kc, k, pk)) != 0)
2567		p = (dir < 0) ? pl : pr;
2568	<	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
2568	>	else if ((q = pr.findTreeNode(h, k, kc)) != null)
2569		return q;
2570	+	else
2571	+	p = pl;
2572		} while (p != null);
2573		}
2574		return null;
#	Line 2585 | Line 2595 | public class ConcurrentHashMapV8<K,V>
2595		static final int READER = 4; // increment value for setting read lock
2596
2597		/**
2598	+	* Tie-breaking utility for ordering insertions when equal
2599	+	* hashCodes and non-comparable. We don't require a total
2600	+	* order, just a consistent insertion rule to maintain
2601	+	* equivalence across rebalancings. Tie-breaking further than
2602	+	* necessary simplifies testing a bit.
2603	+	*/
2604	+	static int tieBreakOrder(Object a, Object b) {
2605	+	int d;
2606	+	if (a == null || b == null ||
2607	+	(d = a.getClass().getName().
2608	+	compareTo(b.getClass().getName())) == 0)
2609	+	d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
2610	+	-1 : 1);
2611	+	return d;
2612	+	}
2613	+
2614	+	/**
2615		* Creates bin with initial set of nodes headed by b.
2616		*/
2617		TreeBin(TreeNode<K,V> b) {
#	Line 2600 | Line 2627 | public class ConcurrentHashMapV8<K,V>
2627		r = x;
2628		}
2629		else {
2630	<	Object key = x.key;
2631	<	int hash = x.hash;
2630	>	K k = x.key;
2631	>	int h = x.hash;
2632		Class<?> kc = null;
2633		for (TreeNode<K,V> p = r;;) {
2634		int dir, ph;
2635	<	if ((ph = p.hash) > hash)
2635	>	K pk = p.key;
2636	>	if ((ph = p.hash) > h)
2637		dir = -1;
2638	<	else if (ph < hash)
2638	>	else if (ph < h)
2639		dir = 1;
2640	<	else if ((kc != null ||
2641	<	(kc = comparableClassFor(key)) != null))
2642	<	dir = compareComparables(kc, key, p.key);
2643	<	else
2644	<	dir = 0;
2617	<	TreeNode<K,V> xp = p;
2640	>	else if ((kc == null &&
2641	>	(kc = comparableClassFor(k)) == null) ||
2642	>	(dir = compareComparables(kc, k, pk)) == 0)
2643	>	dir = tieBreakOrder(k, pk);
2644	>	TreeNode<K,V> xp = p;
2645		if ((p = (dir <= 0) ? p.left : p.right) == null) {
2646		x.parent = xp;
2647		if (dir <= 0)
#	Line 2628 | Line 2655 | public class ConcurrentHashMapV8<K,V>
2655		}
2656		}
2657		this.root = r;
2658	+	assert checkInvariants(root);
2659		}
2660
2661		/**
#	Line 2674 | Line 2702 | public class ConcurrentHashMapV8<K,V>
2702		* using tree comparisons from root, but continues linear
2703		* search when lock not available.
2704		*/
2705	<	final Node<K,V> find(int h, Object k) {
2705	>	final Node<K,V> find(int h, Object k) {
2706		if (k != null) {
2707		for (Node<K,V> e = first; e != null; e = e.next) {
2708		int s; K ek;
#	Line 2711 | Line 2739 | public class ConcurrentHashMapV8<K,V>
2739		*/
2740		final TreeNode<K,V> putTreeVal(int h, K k, V v) {
2741		Class<?> kc = null;
2742	+	boolean searched = false;
2743		for (TreeNode<K,V> p = root;;) {
2744	<	int dir, ph; K pk; TreeNode<K,V> q, pr;
2744	>	int dir, ph; K pk;
2745		if (p == null) {
2746		first = root = new TreeNode<K,V>(h, k, v, null, null);
2747		break;
#	Line 2726 | Line 2755 | public class ConcurrentHashMapV8<K,V>
2755		else if ((kc == null &&
2756		(kc = comparableClassFor(k)) == null) ||
2757		(dir = compareComparables(kc, k, pk)) == 0) {
2758	<	if (p.left == null)
2759	<	dir = 1;
2760	<	else if ((pr = p.right) == null ||
2761	<	(q = pr.findTreeNode(h, k, kc)) == null)
2762	<	dir = -1;
2763	<	else
2764	<	return q;
2758	>	if (!searched) {
2759	>	TreeNode<K,V> q, ch;
2760	>	searched = true;
2761	>	if (((ch = p.left) != null &&
2762	>	(q = ch.findTreeNode(h, k, kc)) != null) ||
2763	>	((ch = p.right) != null &&
2764	>	(q = ch.findTreeNode(h, k, kc)) != null))
2765	>	return q;
2766	>	}
2767	>	dir = tieBreakOrder(k, pk);
2768		}
2769	+
2770		TreeNode<K,V> xp = p;
2771	<	if ((p = (dir < 0) ? p.left : p.right) == null) {
2771	>	if ((p = (dir <= 0) ? p.left : p.right) == null) {
2772		TreeNode<K,V> x, f = first;
2773		first = x = new TreeNode<K,V>(h, k, v, f, xp);
2774		if (f != null)
2775		f.prev = x;
2776	<	if (dir < 0)
2776	>	if (dir <= 0)
2777		xp.left = x;
2778		else
2779		xp.right = x;

Diff Legend

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