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.39 by jsr166, Sat Jun 9 16:54:12 2012 UTC vs.
Revision 1.50 by jsr166, Sat Jul 7 13:01:53 2012 UTC

#	Line 4 | Line 4
4		* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7	–	// Snapshot Tue Jun  5 14:56:09 2012  Doug Lea  (dl at altair)
8	–
7		package jsr166e;
8		import jsr166e.LongAdder;
9		import java.util.Arrays;
#	Line 107 | Line 105 | public class ConcurrentHashMapV8<K, V>
105		*/
106		public static interface MappingFunction<K, V> {
107		/**
108	<	* Returns a non-null value for the given key.
108	>	* Returns a value for the given key, or null if there is no mapping.
109		*
110		* @param key the (non-null) key
111	<	* @return a non-null value
111	>	* @return a value for the key, or null if none
112		*/
113		V map(K key);
114		}
#	Line 127 | Line 125 | public class ConcurrentHashMapV8<K, V>
125		*
126		* @param key the (non-null) key
127		* @param value the current value, or null if there is no mapping
128	<	* @return a non-null value
128	>	* @return a value for the key, or null if none
129		*/
130		V remap(K key, V value);
131		}
132
133	+	/**
134	+	* A partitionable iterator. A Spliterator can be traversed
135	+	* directly, but can also be partitioned (before traversal) by
136	+	* creating another Spliterator that covers a non-overlapping
137	+	* portion of the elements, and so may be amenable to parallel
138	+	* execution.
139	+	*
140	+	* <p> This interface exports a subset of expected JDK8
141	+	* functionality.
142	+	*
143	+	* <p>Sample usage: Here is one (of the several) ways to compute
144	+	* the sum of the values held in a map using the ForkJoin
145	+	* framework. As illustrated here, Spliterators are well suited to
146	+	* designs in which a task repeatedly splits off half its work
147	+	* into forked subtasks until small enough to process directly,
148	+	* and then joins these subtasks. Variants of this style can also
149	+	* be used in completion-based designs.
150	+	*
151	+	* <pre>
152	+	* {@code ConcurrentHashMapV8<String, Long> m = ...
153	+	* // Uses parallel depth of log2 of size / (parallelism * slack of 8).
154	+	* int depth = 32 - Integer.numberOfLeadingZeros(m.size() / (aForkJoinPool.getParallelism() * 8));
155	+	* long sum = aForkJoinPool.invoke(new SumValues(m.valueSpliterator(), depth, null));
156	+	* // ...
157	+	* static class SumValues extends RecursiveTask<Long> {
158	+	*   final Spliterator<Long> s;
159	+	*   final int depth;             // number of splits before processing
160	+	*   final SumValues nextJoin;    // records forked subtasks to join
161	+	*   SumValues(Spliterator<Long> s, int depth, SumValues nextJoin) {
162	+	*     this.s = s; this.depth = depth; this.nextJoin = nextJoin;
163	+	*   }
164	+	*   public Long compute() {
165	+	*     long sum = 0;
166	+	*     SumValues subtasks = null; // fork subtasks
167	+	*     for (int d = depth - 1; d >= 0; --d)
168	+	*       (subtasks = new SumValues(s.split(), d, subtasks)).fork();
169	+	*     while (s.hasNext())        // directly process remaining elements
170	+	*       sum += s.next();
171	+	*     for (SumValues t = subtasks; t != null; t = t.nextJoin)
172	+	*       sum += t.join();         // collect subtask results
173	+	*     return sum;
174	+	*   }
175	+	* }
176	+	* }</pre>
177	+	*/
178	+	public static interface Spliterator<T> extends Iterator<T> {
179	+	/**
180	+	* Returns a Spliterator covering approximately half of the
181	+	* elements, guaranteed not to overlap with those subsequently
182	+	* returned by this Spliterator.  After invoking this method,
183	+	* the current Spliterator will <em>not</em> produce any of
184	+	* the elements of the returned Spliterator, but the two
185	+	* Spliterators together will produce all of the elements that
186	+	* would have been produced by this Spliterator had this
187	+	* method not been called. The exact number of elements
188	+	* produced by the returned Spliterator is not guaranteed, and
189	+	* may be zero (i.e., with {@code hasNext()} reporting {@code
190	+	* false}) if this Spliterator cannot be further split.
191	+	*
192	+	* @return a Spliterator covering approximately half of the
193	+	* elements
194	+	* @throws IllegalStateException if this Spliterator has
195	+	* already commenced traversing elements
196	+	*/
197	+	Spliterator<T> split();
198	+	}
199	+
200		/*
201		* Overview:
202		*
#	Line 294 | Line 359 | public class ConcurrentHashMapV8<K, V>
359		*
360		* The traversal scheme also applies to partial traversals of
361		* ranges of bins (via an alternate InternalIterator constructor)
362	<	* to support partitioned aggregate operations (that are not
363	<	* otherwise implemented yet).  Also, read-only operations give up
364	<	* if ever forwarded to a null table, which provides support for
365	<	* shutdown-style clearing, which is also not currently
301	<	* implemented.
362	>	* to support partitioned aggregate operations.  Also, read-only
363	>	* operations give up if ever forwarded to a null table, which
364	>	* provides support for shutdown-style clearing, which is also not
365	>	* currently implemented.
366		*
367		* Lazy table initialization minimizes footprint until first use,
368		* and also avoids resizings when the first operation is from a
#	Line 452 | Line 516 | public class ConcurrentHashMapV8<K, V>
516
517		/**
518		* Key-value entry. Note that this is never exported out as a
519	<	* user-visible Map.Entry (see WriteThroughEntry and SnapshotEntry
520	<	* below). Nodes with a hash field of MOVED are special, and do
521	<	* not contain user keys or values.  Otherwise, keys are never
522	<	* null, and null val fields indicate that a node is in the
523	<	* process of being deleted or created. For purposes of read-only
524	<	* access, a key may be read before a val, but can only be used
525	<	* after checking val to be non-null.
519	>	* user-visible Map.Entry (see MapEntry below). Nodes with a hash
520	>	* field of MOVED are special, and do not contain user keys or
521	>	* values.  Otherwise, keys are never null, and null val fields
522	>	* indicate that a node is in the process of being deleted or
523	>	* created. For purposes of read-only access, a key may be read
524	>	* before a val, but can only be used after checking val to be
525	>	* non-null.
526		*/
527		static class Node {
528		volatile int hash;
#	Line 571 | Line 635 | public class ConcurrentHashMapV8<K, V>
635		* handle this, the tree is ordered primarily by hash value, then
636		* by getClass().getName() order, and then by Comparator order
637		* among elements of the same class.  On lookup at a node, if
638	<	* non-Comparable, both left and right children may need to be
639	<	* searched in the case of tied hash values. (This corresponds to
640	<	* the full list search that would be necessary if all elements
641	<	* were non-Comparable and had tied hashes.)
638	>	* elements are not comparable or compare as 0, both left and
639	>	* right children may need to be searched in the case of tied hash
640	>	* values. (This corresponds to the full list search that would be
641	>	* necessary if all elements were non-Comparable and had tied
642	>	* hashes.)  The red-black balancing code is updated from
643	>	* pre-jdk-collections
644	>	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
645	>	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
646	>	* Algorithms" (CLR).
647		*
648		* TreeBins also maintain a separate locking discipline than
649		* regular bins. Because they are forwarded via special MOVED
#	Line 598 | Line 667 | public class ConcurrentHashMapV8<K, V>
667		*/
668		static final class TreeBin extends AbstractQueuedSynchronizer {
669		private static final long serialVersionUID = 2249069246763182397L;
670	<	TreeNode root;  // root of tree
671	<	TreeNode first; // head of next-pointer list
670	>	transient TreeNode root;  // root of tree
671	>	transient TreeNode first; // head of next-pointer list
672
673		/* AQS overrides */
674		public final boolean isHeldExclusively() { return getState() > 0; }
#	Line 629 | Line 698 | public class ConcurrentHashMapV8<K, V>
698		return c == -1;
699		}
700
701	+	/** From CLR */
702	+	private void rotateLeft(TreeNode p) {
703	+	if (p != null) {
704	+	TreeNode r = p.right, pp, rl;
705	+	if ((rl = p.right = r.left) != null)
706	+	rl.parent = p;
707	+	if ((pp = r.parent = p.parent) == null)
708	+	root = r;
709	+	else if (pp.left == p)
710	+	pp.left = r;
711	+	else
712	+	pp.right = r;
713	+	r.left = p;
714	+	p.parent = r;
715	+	}
716	+	}
717	+
718	+	/** From CLR */
719	+	private void rotateRight(TreeNode p) {
720	+	if (p != null) {
721	+	TreeNode l = p.left, pp, lr;
722	+	if ((lr = p.left = l.right) != null)
723	+	lr.parent = p;
724	+	if ((pp = l.parent = p.parent) == null)
725	+	root = l;
726	+	else if (pp.right == p)
727	+	pp.right = l;
728	+	else
729	+	pp.left = l;
730	+	l.right = p;
731	+	p.parent = l;
732	+	}
733	+	}
734	+
735		/**
736		* Return the TreeNode (or null if not found) for the given key
737		* starting at given root.
#	Line 637 | Line 740 | public class ConcurrentHashMapV8<K, V>
740		final TreeNode getTreeNode(int h, Object k, TreeNode p) {
741		Class<?> c = k.getClass();
742		while (p != null) {
743	<	int dir, ph;  Object pk; Class<?> pc; TreeNode r;
744	<	if (h < (ph = p.hash))
745	<	dir = -1;
746	<	else if (h > ph)
747	<	dir = 1;
748	<	else if ((pk = p.key) == k || k.equals(pk))
749	<	return p;
750	<	else if (c != (pc = pk.getClass()))
751	<	dir = c.getName().compareTo(pc.getName());
752	<	else if (k instanceof Comparable)
753	<	dir = ((Comparable)k).compareTo((Comparable)pk);
754	<	else
755	<	dir = 0;
756	<	TreeNode pr = p.right;
757	<	if (dir > 0)
758	<	p = pr;
759	<	else if (dir == 0 && pr != null && h >= pr.hash &&
760	<	(r = getTreeNode(h, k, pr)) != null)
761	<	return r;
743	>	int dir, ph;  Object pk; Class<?> pc;
744	>	if ((ph = p.hash) == h) {
745	>	if ((pk = p.key) == k || k.equals(pk))
746	>	return p;
747	>	if (c != (pc = pk.getClass()) ||
748	>	!(k instanceof Comparable) ||
749	>	(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
750	>	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
751	>	TreeNode r = null, s = null, pl, pr;
752	>	if (dir >= 0) {
753	>	if ((pl = p.left) != null && h <= pl.hash)
754	>	s = pl;
755	>	}
756	>	else if ((pr = p.right) != null && h >= pr.hash)
757	>	s = pr;
758	>	if (s != null && (r = getTreeNode(h, k, s)) != null)
759	>	return r;
760	>	}
761	>	}
762		else
763	<	p = p.left;
763	>	dir = (h < ph) ? -1 : 1;
764	>	p = (dir > 0) ? p.right : p.left;
765		}
766		return null;
767		}
#	Line 690 | Line 794 | public class ConcurrentHashMapV8<K, V>
794		}
795
796		/**
797	<	* Find or add a node
797	>	* Finds or adds a node.
798		* @return null if added
799		*/
800		@SuppressWarnings("unchecked") // suppress Comparable cast warning
801		final TreeNode putTreeNode(int h, Object k, Object v) {
802		Class<?> c = k.getClass();
803	<	TreeNode p = root;
803	>	TreeNode pp = root, p = null;
804		int dir = 0;
805	<	if (p != null) {
806	<	for (;;) {
807	<	int ph;  Object pk; Class<?> pc; TreeNode r;
808	<	if (h < (ph = p.hash))
809	<	dir = -1;
706	<	else if (h > ph)
707	<	dir = 1;
708	<	else if ((pk = p.key) == k || k.equals(pk))
805	>	while (pp != null) { // find existing node or leaf to insert at
806	>	int ph;  Object pk; Class<?> pc;
807	>	p = pp;
808	>	if ((ph = p.hash) == h) {
809	>	if ((pk = p.key) == k || k.equals(pk))
810		return p;
811	<	else if (c != (pc = (pk = p.key).getClass()))
812	<	dir = c.getName().compareTo(pc.getName());
813	<	else if (k instanceof Comparable)
814	<	dir = ((Comparable)k).compareTo((Comparable)pk);
815	<	else
816	<	dir = 0;
817	<	TreeNode pr = p.right, pl;
818	<	if (dir > 0) {
819	<	if (pr == null)
820	<	break;
821	<	p = pr;
811	>	if (c != (pc = pk.getClass()) ||
812	>	!(k instanceof Comparable) ||
813	>	(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
814	>	dir = (c == pc) ? 0 : c.getName().compareTo(pc.getName());
815	>	TreeNode r = null, s = null, pl, pr;
816	>	if (dir >= 0) {
817	>	if ((pl = p.left) != null && h <= pl.hash)
818	>	s = pl;
819	>	}
820	>	else if ((pr = p.right) != null && h >= pr.hash)
821	>	s = pr;
822	>	if (s != null && (r = getTreeNode(h, k, s)) != null)
823	>	return r;
824		}
722	–	else if (dir == 0 && pr != null && h >= pr.hash &&
723	–	(r = getTreeNode(h, k, pr)) != null)
724	–	return r;
725	–	else if ((pl = p.left) == null)
726	–	break;
727	–	else
728	–	p = pl;
825		}
826	+	else
827	+	dir = (h < ph) ? -1 : 1;
828	+	pp = (dir > 0) ? p.right : p.left;
829		}
830	+
831		TreeNode f = first;
832	<	TreeNode r = first = new TreeNode(h, k, v, f, p);
832	>	TreeNode x = first = new TreeNode(h, k, v, f, p);
833		if (p == null)
834	<	root = r;
835	<	else {
834	>	root = x;
835	>	else { // attach and rebalance; adapted from CLR
836	>	TreeNode xp, xpp;
837	>	if (f != null)
838	>	f.prev = x;
839		if (dir <= 0)
840	<	p.left = r;
840	>	p.left = x;
841		else
842	<	p.right = r;
843	<	if (f != null)
844	<	f.prev = r;
845	<	fixAfterInsertion(r);
842	>	p.right = x;
843	>	x.red = true;
844	>	while (x != null && (xp = x.parent) != null && xp.red &&
845	>	(xpp = xp.parent) != null) {
846	>	TreeNode xppl = xpp.left;
847	>	if (xp == xppl) {
848	>	TreeNode y = xpp.right;
849	>	if (y != null && y.red) {
850	>	y.red = false;
851	>	xp.red = false;
852	>	xpp.red = true;
853	>	x = xpp;
854	>	}
855	>	else {
856	>	if (x == xp.right) {
857	>	rotateLeft(x = xp);
858	>	xpp = (xp = x.parent) == null ? null : xp.parent;
859	>	}
860	>	if (xp != null) {
861	>	xp.red = false;
862	>	if (xpp != null) {
863	>	xpp.red = true;
864	>	rotateRight(xpp);
865	>	}
866	>	}
867	>	}
868	>	}
869	>	else {
870	>	TreeNode y = xppl;
871	>	if (y != null && y.red) {
872	>	y.red = false;
873	>	xp.red = false;
874	>	xpp.red = true;
875	>	x = xpp;
876	>	}
877	>	else {
878	>	if (x == xp.left) {
879	>	rotateRight(x = xp);
880	>	xpp = (xp = x.parent) == null ? null : xp.parent;
881	>	}
882	>	if (xp != null) {
883	>	xp.red = false;
884	>	if (xpp != null) {
885	>	xpp.red = true;
886	>	rotateLeft(xpp);
887	>	}
888	>	}
889	>	}
890	>	}
891	>	}
892	>	TreeNode r = root;
893	>	if (r != null && r.red)
894	>	r.red = false;
895		}
896		return null;
897		}
#	Line 765 | Line 917 | public class ConcurrentHashMapV8<K, V>
917		TreeNode pl = p.left;
918		TreeNode pr = p.right;
919		if (pl != null && pr != null) {
920	<	TreeNode s = pr;
921	<	while (s.left != null) // find successor
922	<	s = s.left;
920	>	TreeNode s = pr, sl;
921	>	while ((sl = s.left) != null) // find successor
922	>	s = sl;
923		boolean c = s.red; s.red = p.red; p.red = c; // swap colors
924		TreeNode sr = s.right;
925		TreeNode pp = p.parent;
#	Line 819 | Line 971 | public class ConcurrentHashMapV8<K, V>
971		pp.right = replacement;
972		p.left = p.right = p.parent = null;
973		}
974	<	if (!p.red)
975	<	fixAfterDeletion(replacement);
976	<	if (p == replacement && (pp = p.parent) != null) {
977	<	if (p == pp.left) // detach pointers
978	<	pp.left = null;
979	<	else if (p == pp.right)
980	<	pp.right = null;
829	<	p.parent = null;
830	<	}
831	<	}
832	<
833	<	// CLR code updated from pre-jdk-collections version at
834	<	// http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java
835	<
836	<	/** From CLR */
837	<	private void rotateLeft(TreeNode p) {
838	<	if (p != null) {
839	<	TreeNode r = p.right, pp, rl;
840	<	if ((rl = p.right = r.left) != null)
841	<	rl.parent = p;
842	<	if ((pp = r.parent = p.parent) == null)
843	<	root = r;
844	<	else if (pp.left == p)
845	<	pp.left = r;
846	<	else
847	<	pp.right = r;
848	<	r.left = p;
849	<	p.parent = r;
850	<	}
851	<	}
852	<
853	<	/** From CLR */
854	<	private void rotateRight(TreeNode p) {
855	<	if (p != null) {
856	<	TreeNode l = p.left, pp, lr;
857	<	if ((lr = p.left = l.right) != null)
858	<	lr.parent = p;
859	<	if ((pp = l.parent = p.parent) == null)
860	<	root = l;
861	<	else if (pp.right == p)
862	<	pp.right = l;
863	<	else
864	<	pp.left = l;
865	<	l.right = p;
866	<	p.parent = l;
867	<	}
868	<	}
869	<
870	<	/** From CLR */
871	<	private void fixAfterInsertion(TreeNode x) {
872	<	x.red = true;
873	<	TreeNode xp, xpp;
874	<	while (x != null && (xp = x.parent) != null && xp.red &&
875	<	(xpp = xp.parent) != null) {
876	<	TreeNode xppl = xpp.left;
877	<	if (xp == xppl) {
878	<	TreeNode y = xpp.right;
879	<	if (y != null && y.red) {
880	<	y.red = false;
881	<	xp.red = false;
882	<	xpp.red = true;
883	<	x = xpp;
974	>	if (!p.red) { // rebalance, from CLR
975	>	TreeNode x = replacement;
976	>	while (x != null) {
977	>	TreeNode xp, xpl;
978	>	if (x.red || (xp = x.parent) == null) {
979	>	x.red = false;
980	>	break;
981		}
982	<	else {
983	<	if (x == xp.right) {
984	<	x = xp;
985	<	rotateLeft(x);
986	<	xpp = (xp = x.parent) == null ? null : xp.parent;
982	>	if (x == (xpl = xp.left)) {
983	>	TreeNode sib = xp.right;
984	>	if (sib != null && sib.red) {
985	>	sib.red = false;
986	>	xp.red = true;
987	>	rotateLeft(xp);
988	>	sib = (xp = x.parent) == null ? null : xp.right;
989		}
990	<	if (xp != null) {
892	<	xp.red = false;
893	<	if (xpp != null) {
894	<	xpp.red = true;
895	<	rotateRight(xpp);
896	<	}
897	<	}
898	<	}
899	<	}
900	<	else {
901	<	TreeNode y = xppl;
902	<	if (y != null && y.red) {
903	<	y.red = false;
904	<	xp.red = false;
905	<	xpp.red = true;
906	<	x = xpp;
907	<	}
908	<	else {
909	<	if (x == xp.left) {
990	>	if (sib == null)
991		x = xp;
911	–	rotateRight(x);
912	–	xpp = (xp = x.parent) == null ? null : xp.parent;
913	–	}
914	–	if (xp != null) {
915	–	xp.red = false;
916	–	if (xpp != null) {
917	–	xpp.red = true;
918	–	rotateLeft(xpp);
919	–	}
920	–	}
921	–	}
922	–	}
923	–	}
924	–	TreeNode r = root;
925	–	if (r != null && r.red)
926	–	r.red = false;
927	–	}
928	–
929	–	/** From CLR */
930	–	private void fixAfterDeletion(TreeNode x) {
931	–	while (x != null) {
932	–	TreeNode xp, xpl;
933	–	if (x.red || (xp = x.parent) == null) {
934	–	x.red = false;
935	–	break;
936	–	}
937	–	if (x == (xpl = xp.left)) {
938	–	TreeNode sib = xp.right;
939	–	if (sib != null && sib.red) {
940	–	sib.red = false;
941	–	xp.red = true;
942	–	rotateLeft(xp);
943	–	sib = (xp = x.parent) == null ? null : xp.right;
944	–	}
945	–	if (sib == null)
946	–	x = xp;
947	–	else {
948	–	TreeNode sl = sib.left, sr = sib.right;
949	–	if ((sr == null || !sr.red) &&
950	–	(sl == null || !sl.red)) {
951	–	sib.red = true;
952	–	x = xp;
953	–	}
992		else {
993	<	if (sr == null || !sr.red) {
994	<	if (sl != null)
995	<	sl.red = false;
993	>	TreeNode sl = sib.left, sr = sib.right;
994	>	if ((sr == null || !sr.red) &&
995	>	(sl == null || !sl.red)) {
996		sib.red = true;
997	<	rotateRight(sib);
960	<	sib = (xp = x.parent) == null ? null : xp.right;
961	<	}
962	<	if (sib != null) {
963	<	sib.red = (xp == null) ? false : xp.red;
964	<	if ((sr = sib.right) != null)
965	<	sr.red = false;
997	>	x = xp;
998		}
999	<	if (xp != null) {
1000	<	xp.red = false;
1001	<	rotateLeft(xp);
999	>	else {
1000	>	if (sr == null || !sr.red) {
1001	>	if (sl != null)
1002	>	sl.red = false;
1003	>	sib.red = true;
1004	>	rotateRight(sib);
1005	>	sib = (xp = x.parent) == null ? null : xp.right;
1006	>	}
1007	>	if (sib != null) {
1008	>	sib.red = (xp == null) ? false : xp.red;
1009	>	if ((sr = sib.right) != null)
1010	>	sr.red = false;
1011	>	}
1012	>	if (xp != null) {
1013	>	xp.red = false;
1014	>	rotateLeft(xp);
1015	>	}
1016	>	x = root;
1017		}
971	–	x = root;
1018		}
1019		}
1020	<	}
1021	<	else { // symmetric
1022	<	TreeNode sib = xpl;
1023	<	if (sib != null && sib.red) {
1024	<	sib.red = false;
1025	<	xp.red = true;
1026	<	rotateRight(xp);
981	<	sib = (xp = x.parent) == null ? null : xp.left;
982	<	}
983	<	if (sib == null)
984	<	x = xp;
985	<	else {
986	<	TreeNode sl = sib.left, sr = sib.right;
987	<	if ((sl == null || !sl.red) &&
988	<	(sr == null || !sr.red)) {
989	<	sib.red = true;
990	<	x = xp;
1020	>	else { // symmetric
1021	>	TreeNode sib = xpl;
1022	>	if (sib != null && sib.red) {
1023	>	sib.red = false;
1024	>	xp.red = true;
1025	>	rotateRight(xp);
1026	>	sib = (xp = x.parent) == null ? null : xp.left;
1027		}
1028	+	if (sib == null)
1029	+	x = xp;
1030		else {
1031	<	if (sl == null || !sl.red) {
1032	<	if (sr != null)
1033	<	sr.red = false;
1031	>	TreeNode sl = sib.left, sr = sib.right;
1032	>	if ((sl == null || !sl.red) &&
1033	>	(sr == null || !sr.red)) {
1034		sib.red = true;
1035	<	rotateLeft(sib);
998	<	sib = (xp = x.parent) == null ? null : xp.left;
1035	>	x = xp;
1036		}
1037	<	if (sib != null) {
1038	<	sib.red = (xp == null) ? false : xp.red;
1039	<	if ((sl = sib.left) != null)
1040	<	sl.red = false;
1041	<	}
1042	<	if (xp != null) {
1043	<	xp.red = false;
1044	<	rotateRight(xp);
1037	>	else {
1038	>	if (sl == null || !sl.red) {
1039	>	if (sr != null)
1040	>	sr.red = false;
1041	>	sib.red = true;
1042	>	rotateLeft(sib);
1043	>	sib = (xp = x.parent) == null ? null : xp.left;
1044	>	}
1045	>	if (sib != null) {
1046	>	sib.red = (xp == null) ? false : xp.red;
1047	>	if ((sl = sib.left) != null)
1048	>	sl.red = false;
1049	>	}
1050	>	if (xp != null) {
1051	>	xp.red = false;
1052	>	rotateRight(xp);
1053	>	}
1054	>	x = root;
1055		}
1009	–	x = root;
1056		}
1057		}
1058		}
1059		}
1060	+	if (p == replacement && (pp = p.parent) != null) {
1061	+	if (p == pp.left) // detach pointers
1062	+	pp.left = null;
1063	+	else if (p == pp.right)
1064	+	pp.right = null;
1065	+	p.parent = null;
1066	+	}
1067		}
1068		}
1069
#	Line 1025 | Line 1078 | public class ConcurrentHashMapV8<K, V>
1078		* we apply a transform that spreads the impact of higher bits
1079		* downward. There is a tradeoff between speed, utility, and
1080		* quality of bit-spreading. Because many common sets of hashes
1081	<	* are already reaonably distributed across bits (so don't benefit
1081	>	* are already reasonably distributed across bits (so don't benefit
1082		* from spreading), and because we use trees to handle large sets
1083		* of collisions in bins, we don't need excessively high quality.
1084		*/
#	Line 1504 | Line 1557 | public class ConcurrentHashMapV8<K, V>
1557		}
1558		}
1559		}
1560	<	if (val == null)
1561	<	throw new NullPointerException();
1562	<	counter.add(1L);
1563	<	if (count > 1)
1564	<	checkForResize();
1560	>	if (val != null) {
1561	>	counter.add(1L);
1562	>	if (count > 1)
1563	>	checkForResize();
1564	>	}
1565		return val;
1566		}
1567
#	Line 1518 | Line 1571 | public class ConcurrentHashMapV8<K, V>
1571		RemappingFunction<? super K, V> mf) {
1572		int h = spread(k.hashCode());
1573		Object val = null;
1574	<	boolean added = false;
1574	>	int delta = 0;
1575		int count = 0;
1576		for (Node[] tab = table;;) {
1577		Node f; int i, fh; Object fk;
#	Line 1531 | Line 1584 | public class ConcurrentHashMapV8<K, V>
1584		count = 1;
1585		if ((val = mf.remap(k, null)) != null) {
1586		node.val = val;
1587	<	added = true;
1587	>	delta = 1;
1588		}
1589		} finally {
1590	<	if (!added)
1590	>	if (delta == 0)
1591		setTabAt(tab, i, null);
1592		if (!node.casHash(fh, h)) {
1593		node.hash = h;
#	Line 1559 | Line 1612 | public class ConcurrentHashMapV8<K, V>
1612		p.val = val;
1613		else {
1614		count = 2;
1615	<	added = true;
1615	>	delta = 1;
1616		t.putTreeNode(h, k, val);
1617		}
1618		}
1619	+	else if (p != null) {
1620	+	delta = -1;
1621	+	t.deleteTreeNode(p);
1622	+	}
1623		}
1624		} finally {
1625		t.release(0);
#	Line 1581 | Line 1638 | public class ConcurrentHashMapV8<K, V>
1638		try {
1639		if (tabAt(tab, i) == f) {
1640		count = 1;
1641	<	for (Node e = f;; ++count) {
1641	>	for (Node e = f, pred = null;; ++count) {
1642		Object ek, ev;
1643		if ((e.hash & HASH_BITS) == h &&
1644		(ev = e.val) != null &&
#	Line 1589 | Line 1646 | public class ConcurrentHashMapV8<K, V>
1646		val = mf.remap(k, (V)ev);
1647		if (val != null)
1648		e.val = val;
1649	+	else {
1650	+	delta = -1;
1651	+	Node en = e.next;
1652	+	if (pred != null)
1653	+	pred.next = en;
1654	+	else
1655	+	setTabAt(tab, i, en);
1656	+	}
1657		break;
1658		}
1659	<	Node last = e;
1659	>	pred = e;
1660		if ((e = e.next) == null) {
1661		if ((val = mf.remap(k, null)) != null) {
1662	<	last.next = new Node(h, k, val, null);
1663	<	added = true;
1662	>	pred.next = new Node(h, k, val, null);
1663	>	delta = 1;
1664		if (count >= TREE_THRESHOLD)
1665		replaceWithTreeBin(tab, i, k);
1666		}
#	Line 1616 | Line 1681 | public class ConcurrentHashMapV8<K, V>
1681		}
1682		}
1683		}
1684	<	if (val == null)
1685	<	throw new NullPointerException();
1621	<	if (added) {
1622	<	counter.add(1L);
1684	>	if (delta != 0) {
1685	>	counter.add((long)delta);
1686		if (count > 1)
1687		checkForResize();
1688		}
#	Line 1937 | Line 2000 | public class ConcurrentHashMapV8<K, V>
2000		}
2001
2002		/**
2003	<	* Split a normal bin with list headed by e into lo and hi parts;
2004	<	* install in given table
2003	>	* Splits a normal bin with list headed by e into lo and hi parts;
2004	>	* installs in given table.
2005		*/
2006		private static void splitBin(Node[] nextTab, int i, Node e) {
2007		int bit = nextTab.length >>> 1; // bit to split on
#	Line 1968 | Line 2031 | public class ConcurrentHashMapV8<K, V>
2031		}
2032
2033		/**
2034	<	* Split a tree bin into lo and hi parts; install in given table
2034	>	* Splits a tree bin into lo and hi parts; installs in given table.
2035		*/
2036		private static void splitTreeBin(Node[] nextTab, int i, TreeBin t) {
2037		int bit = nextTab.length >>> 1;
#	Line 2082 | Line 2145 | public class ConcurrentHashMapV8<K, V>
2145		* valid.
2146		*
2147		* Internal traversals directly access these fields, as in:
2148	<	* {@code while (it.next != null) { process(it.nextKey); it.advance(); }}
2148	>	* {@code while (it.advance() != null) { process(it.nextKey); }}
2149		*
2150	<	* Exported iterators (subclasses of ViewIterator) extract key,
2151	<	* value, or key-value pairs as return values of Iterator.next(),
2152	<	* and encapsulate the it.next check as hasNext();
2150	>	* Exported iterators must track whether the iterator has advanced
2151	>	* (in hasNext vs next) (by setting/checking/nulling field
2152	>	* nextVal), and then extract key, value, or key-value pairs as
2153	>	* return values of next().
2154		*
2155		* The iterator visits once each still-valid node that was
2156		* reachable upon iterator construction. It might miss some that
#	Line 2104 | Line 2168 | public class ConcurrentHashMapV8<K, V>
2168		* paranoically cope with potential sharing by users of iterators
2169		* across threads, iteration terminates if a bounds checks fails
2170		* for a table read.
2107	–	*
2108	–	* The range-based constructor enables creation of parallel
2109	–	* range-splitting traversals. (Not yet implemented.)
2171		*/
2172	<	static class InternalIterator {
2172	>	static class InternalIterator<K,V> {
2173	>	final ConcurrentHashMapV8<K, V> map;
2174		Node next;           // the next entry to use
2175		Node last;           // the last entry used
2176		Object nextKey;      // cached key field of next
#	Line 2116 | Line 2178 | public class ConcurrentHashMapV8<K, V>
2178		Node[] tab;          // current table; updated if resized
2179		int index;           // index of bin to use next
2180		int baseIndex;       // current index of initial table
2181	<	final int baseLimit; // index bound for initial table
2181	>	int baseLimit;       // index bound for initial table
2182		final int baseSize;  // initial table size
2183
2184		/** Creates iterator for all entries in the table. */
2185	<	InternalIterator(Node[] tab) {
2186	<	this.tab = tab;
2185	>	InternalIterator(ConcurrentHashMapV8<K, V> map) {
2186	>	this.tab = (this.map = map).table;
2187		baseLimit = baseSize = (tab == null) ? 0 : tab.length;
2126	–	index = baseIndex = 0;
2127	–	next = null;
2128	–	advance();
2129	–	}
2130	–
2131	–	/** Creates iterator for the given range of the table */
2132	–	InternalIterator(Node[] tab, int lo, int hi) {
2133	–	this.tab = tab;
2134	–	baseSize = (tab == null) ? 0 : tab.length;
2135	–	baseLimit = (hi <= baseSize) ? hi : baseSize;
2136	–	index = baseIndex = (lo >= 0) ? lo : 0;
2137	–	next = null;
2138	–	advance();
2188		}
2189
2190	<	/** Advances next. See above for explanation. */
2191	<	final void advance() {
2190	>	/** Creates iterator for clone() and split() methods. */
2191	>	InternalIterator(InternalIterator<K,V> it, boolean split) {
2192	>	this.map = it.map;
2193	>	this.tab = it.tab;
2194	>	this.baseSize = it.baseSize;
2195	>	int lo = it.baseIndex;
2196	>	int hi = this.baseLimit = it.baseLimit;
2197	>	this.index = this.baseIndex =
2198	>	(split) ? (it.baseLimit = (lo + hi + 1) >>> 1) : lo;
2199	>	}
2200	>
2201	>	/**
2202	>	* Advances next; returns nextVal or null if terminated.
2203	>	* See above for explanation.
2204	>	*/
2205	>	final Object advance() {
2206		Node e = last = next;
2207	+	Object ev = null;
2208		outer: do {
2209		if (e != null)                  // advance past used/skipped node
2210		e = e.next;
#	Line 2160 | Line 2224 | public class ConcurrentHashMapV8<K, V>
2224		index = (i += baseSize) < n ? i : (baseIndex = b + 1);
2225		}
2226		nextKey = e.key;
2227	<	} while ((nextVal = e.val) == null);// skip deleted or special nodes
2227	>	} while ((ev = e.val) == null);    // skip deleted or special nodes
2228		next = e;
2229	+	return nextVal = ev;
2230	+	}
2231	+
2232	+	public final void remove() {
2233	+	if (nextVal == null)
2234	+	advance();
2235	+	Node e = last;
2236	+	if (e == null)
2237	+	throw new IllegalStateException();
2238	+	last = null;
2239	+	map.remove(e.key);
2240	+	}
2241	+
2242	+	public final boolean hasNext() {
2243	+	return nextVal != null || advance() != null;
2244		}
2245	+
2246	+	public final boolean hasMoreElements() { return hasNext(); }
2247		}
2248
2249		/* ---------------- Public operations -------------- */
2250
2251		/**
2252	<	* Creates a new, empty map with the default initial table size (16),
2252	>	* Creates a new, empty map with the default initial table size (16).
2253		*/
2254		public ConcurrentHashMapV8() {
2255		this.counter = new LongAdder();
#	Line 2249 | Line 2330 | public class ConcurrentHashMapV8<K, V>
2330		if (initialCapacity < concurrencyLevel)   // Use at least as many bins
2331		initialCapacity = concurrencyLevel;   // as estimated threads
2332		long size = (long)(1.0 + (long)initialCapacity / loadFactor);
2333	<	int cap = ((size >= (long)MAXIMUM_CAPACITY) ?
2334	<	MAXIMUM_CAPACITY: tableSizeFor((int)size));
2333	>	int cap = (size >= (long)MAXIMUM_CAPACITY) ?
2334	>	MAXIMUM_CAPACITY : tableSizeFor((int)size);
2335		this.counter = new LongAdder();
2336		this.sizeCtl = cap;
2337		}
#	Line 2324 | Line 2405 | public class ConcurrentHashMapV8<K, V>
2405		if (value == null)
2406		throw new NullPointerException();
2407		Object v;
2408	<	InternalIterator it = new InternalIterator(table);
2409	<	while (it.next != null) {
2410	<	if ((v = it.nextVal) == value || value.equals(v))
2408	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2409	>	while ((v = it.advance()) != null) {
2410	>	if (v == value || value.equals(v))
2411		return true;
2331	–	it.advance();
2412		}
2413		return false;
2414		}
#	Line 2399 | Line 2479 | public class ConcurrentHashMapV8<K, V>
2479
2480		/**
2481		* If the specified key is not already associated with a value,
2482	<	* computes its value using the given mappingFunction and
2483	<	* enters it into the map.  This is equivalent to
2482	>	* computes its value using the given mappingFunction and enters
2483	>	* it into the map unless null.  This is equivalent to
2484		* <pre> {@code
2485		* if (map.containsKey(key))
2486		*   return map.get(key);
2487		* value = mappingFunction.map(key);
2488	<	* map.put(key, value);
2488	>	* if (value != null)
2489	>	*   map.put(key, value);
2490		* return value;}</pre>
2491		*
2492		* except that the action is performed atomically.  If the
2493	<	* function returns {@code null} (in which case a {@code
2494	<	* NullPointerException} is thrown), or the function itself throws
2495	<	* an (unchecked) exception, the exception is rethrown to its
2496	<	* caller, and no mapping is recorded.  Some attempted update
2497	<	* operations on this map by other threads may be blocked while
2498	<	* computation is in progress, so the computation should be short
2499	<	* and simple, and must not attempt to update any other mappings
2500	<	* of this Map. The most appropriate usage is to construct a new
2501	<	* object serving as an initial mapped value, or memoized result,
2421	<	* as in:
2493	>	* function returns {@code null} no mapping is recorded. If the
2494	>	* function itself throws an (unchecked) exception, the exception
2495	>	* is rethrown to its caller, and no mapping is recorded.  Some
2496	>	* attempted update operations on this map by other threads may be
2497	>	* blocked while computation is in progress, so the computation
2498	>	* should be short and simple, and must not attempt to update any
2499	>	* other mappings of this Map. The most appropriate usage is to
2500	>	* construct a new object serving as an initial mapped value, or
2501	>	* memoized result, as in:
2502		*
2503		*  <pre> {@code
2504		* map.computeIfAbsent(key, new MappingFunction<K, V>() {
#	Line 2427 | Line 2507 | public class ConcurrentHashMapV8<K, V>
2507		* @param key key with which the specified value is to be associated
2508		* @param mappingFunction the function to compute a value
2509		* @return the current (existing or computed) value associated with
2510	<	*         the specified key.
2511	<	* @throws NullPointerException if the specified key, mappingFunction,
2512	<	*         or computed value is null
2510	>	*         the specified key, or null if the computed value is null.
2511	>	* @throws NullPointerException if the specified key or mappingFunction
2512	>	*         is null
2513		* @throws IllegalStateException if the computation detectably
2514		*         attempts a recursive update to this map that would
2515		*         otherwise never complete
#	Line 2444 | Line 2524 | public class ConcurrentHashMapV8<K, V>
2524		}
2525
2526		/**
2527	<	* Computes and enters a new mapping value given a key and
2527	>	* Computes a new mapping value given a key and
2528		* its current mapped value (or {@code null} if there is no current
2529		* mapping). This is equivalent to
2530		*  <pre> {@code
2531	<	*  map.put(key, remappingFunction.remap(key, map.get(key));
2531	>	*   value = remappingFunction.remap(key, map.get(key));
2532	>	*   if (value != null)
2533	>	*     map.put(key, value);
2534	>	*   else
2535	>	*     map.remove(key);
2536		* }</pre>
2537		*
2538		* except that the action is performed atomically.  If the
2539	<	* function returns {@code null} (in which case a {@code
2540	<	* NullPointerException} is thrown), or the function itself throws
2541	<	* an (unchecked) exception, the exception is rethrown to its
2542	<	* caller, and current mapping is left unchanged.  Some attempted
2543	<	* update operations on this map by other threads may be blocked
2544	<	* while computation is in progress, so the computation should be
2545	<	* short and simple, and must not attempt to update any other
2546	<	* mappings of this Map. For example, to either create or
2463	<	* append new messages to a value mapping:
2539	>	* function returns {@code null}, the mapping is removed.  If the
2540	>	* function itself throws an (unchecked) exception, the exception
2541	>	* is rethrown to its caller, and the current mapping is left
2542	>	* unchanged.  Some attempted update operations on this map by
2543	>	* other threads may be blocked while computation is in progress,
2544	>	* so the computation should be short and simple, and must not
2545	>	* attempt to update any other mappings of this Map. For example,
2546	>	* to either create or append new messages to a value mapping:
2547		*
2548		* <pre> {@code
2549		* Map<Key, String> map = ...;
#	Line 2472 | Line 2555 | public class ConcurrentHashMapV8<K, V>
2555		* @param key key with which the specified value is to be associated
2556		* @param remappingFunction the function to compute a value
2557		* @return the new value associated with
2558	<	*         the specified key.
2558	>	*         the specified key, or null if none.
2559		* @throws NullPointerException if the specified key or remappingFunction
2560	<	*         or computed value is null
2560	>	*         is null
2561		* @throws IllegalStateException if the computation detectably
2562		*         attempts a recursive update to this map that would
2563		*         otherwise never complete
#	Line 2633 | Line 2716 | public class ConcurrentHashMapV8<K, V>
2716		}
2717
2718		/**
2719	+	* Returns a partionable iterator of the keys in this map.
2720	+	*
2721	+	* @return a partionable iterator of the keys in this map
2722	+	*/
2723	+	public Spliterator<K> keySpliterator() {
2724	+	return new KeyIterator<K,V>(this);
2725	+	}
2726	+
2727	+	/**
2728	+	* Returns a partionable iterator of the values in this map.
2729	+	*
2730	+	* @return a partionable iterator of the values in this map
2731	+	*/
2732	+	public Spliterator<V> valueSpliterator() {
2733	+	return new ValueIterator<K,V>(this);
2734	+	}
2735	+
2736	+	/**
2737	+	* Returns a partionable iterator of the entries in this map.
2738	+	*
2739	+	* @return a partionable iterator of the entries in this map
2740	+	*/
2741	+	public Spliterator<Map.Entry<K,V>> entrySpliterator() {
2742	+	return new EntryIterator<K,V>(this);
2743	+	}
2744	+
2745	+	/**
2746		* Returns the hash code value for this {@link Map}, i.e.,
2747		* the sum of, for each key-value pair in the map,
2748		* {@code key.hashCode() ^ value.hashCode()}.
#	Line 2641 | Line 2751 | public class ConcurrentHashMapV8<K, V>
2751		*/
2752		public int hashCode() {
2753		int h = 0;
2754	<	InternalIterator it = new InternalIterator(table);
2755	<	while (it.next != null) {
2756	<	h += it.nextKey.hashCode() ^ it.nextVal.hashCode();
2757	<	it.advance();
2754	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2755	>	Object v;
2756	>	while ((v = it.advance()) != null) {
2757	>	h += it.nextKey.hashCode() ^ v.hashCode();
2758		}
2759		return h;
2760		}
#	Line 2661 | Line 2771 | public class ConcurrentHashMapV8<K, V>
2771		* @return a string representation of this map
2772		*/
2773		public String toString() {
2774	<	InternalIterator it = new InternalIterator(table);
2774	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2775		StringBuilder sb = new StringBuilder();
2776		sb.append('{');
2777	<	if (it.next != null) {
2777	>	Object v;
2778	>	if ((v = it.advance()) != null) {
2779		for (;;) {
2780	<	Object k = it.nextKey, v = it.nextVal;
2780	>	Object k = it.nextKey;
2781		sb.append(k == this ? "(this Map)" : k);
2782		sb.append('=');
2783		sb.append(v == this ? "(this Map)" : v);
2784	<	it.advance();
2674	<	if (it.next == null)
2784	>	if ((v = it.advance()) == null)
2785		break;
2786		sb.append(',').append(' ');
2787		}
#	Line 2694 | Line 2804 | public class ConcurrentHashMapV8<K, V>
2804		if (!(o instanceof Map))
2805		return false;
2806		Map<?,?> m = (Map<?,?>) o;
2807	<	InternalIterator it = new InternalIterator(table);
2808	<	while (it.next != null) {
2809	<	Object val = it.nextVal;
2807	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2808	>	Object val;
2809	>	while ((val = it.advance()) != null) {
2810		Object v = m.get(it.nextKey);
2811		if (v == null || (v != val && !v.equals(val)))
2812		return false;
2703	–	it.advance();
2813		}
2814		for (Map.Entry<?,?> e : m.entrySet()) {
2815		Object mk, mv, v;
#	Line 2716 | Line 2825 | public class ConcurrentHashMapV8<K, V>
2825
2826		/* ----------------Iterators -------------- */
2827
2828	<	/**
2829	<	* Base class for key, value, and entry iterators.  Adds a map
2830	<	* reference to InternalIterator to support Iterator.remove.
2831	<	*/
2832	<	static abstract class ViewIterator<K,V> extends InternalIterator {
2724	<	final ConcurrentHashMapV8<K, V> map;
2725	<	ViewIterator(ConcurrentHashMapV8<K, V> map) {
2726	<	super(map.table);
2727	<	this.map = map;
2828	>	static final class KeyIterator<K,V> extends InternalIterator<K,V>
2829	>	implements Spliterator<K>, Enumeration<K> {
2830	>	KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
2831	>	KeyIterator(InternalIterator<K,V> it, boolean split) {
2832	>	super(it, split);
2833		}
2834	<
2835	<	public final void remove() {
2731	<	if (last == null)
2834	>	public KeyIterator<K,V> split() {
2835	>	if (last != null || (next != null && nextVal == null))
2836		throw new IllegalStateException();
2837	<	map.remove(last.key);
2838	<	last = null;
2837	>	return new KeyIterator<K,V>(this, true);
2838	>	}
2839	>	public KeyIterator<K,V> clone() {
2840	>	if (last != null || (next != null && nextVal == null))
2841	>	throw new IllegalStateException();
2842	>	return new KeyIterator<K,V>(this, false);
2843		}
2736	–
2737	–	public final boolean hasNext()         { return next != null; }
2738	–	public final boolean hasMoreElements() { return next != null; }
2739	–	}
2740	–
2741	–	static final class KeyIterator<K,V> extends ViewIterator<K,V>
2742	–	implements Iterator<K>, Enumeration<K> {
2743	–	KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
2844
2845		@SuppressWarnings("unchecked")
2846		public final K next() {
2847	<	if (next == null)
2847	>	if (nextVal == null && advance() == null)
2848		throw new NoSuchElementException();
2849		Object k = nextKey;
2850	<	advance();
2851	<	return (K)k;
2850	>	nextVal = null;
2851	>	return (K) k;
2852		}
2853
2854		public final K nextElement() { return next(); }
2855		}
2856
2857	<	static final class ValueIterator<K,V> extends ViewIterator<K,V>
2858	<	implements Iterator<V>, Enumeration<V> {
2857	>	static final class ValueIterator<K,V> extends InternalIterator<K,V>
2858	>	implements Spliterator<V>, Enumeration<V> {
2859		ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
2860	+	ValueIterator(InternalIterator<K,V> it, boolean split) {
2861	+	super(it, split);
2862	+	}
2863	+	public ValueIterator<K,V> split() {
2864	+	if (last != null || (next != null && nextVal == null))
2865	+	throw new IllegalStateException();
2866	+	return new ValueIterator<K,V>(this, true);
2867	+	}
2868	+
2869	+	public ValueIterator<K,V> clone() {
2870	+	if (last != null || (next != null && nextVal == null))
2871	+	throw new IllegalStateException();
2872	+	return new ValueIterator<K,V>(this, false);
2873	+	}
2874
2875		@SuppressWarnings("unchecked")
2876		public final V next() {
2877	<	if (next == null)
2877	>	Object v;
2878	>	if ((v = nextVal) == null && (v = advance()) == null)
2879		throw new NoSuchElementException();
2880	<	Object v = nextVal;
2881	<	advance();
2767	<	return (V)v;
2880	>	nextVal = null;
2881	>	return (V) v;
2882		}
2883
2884		public final V nextElement() { return next(); }
2885		}
2886
2887	<	static final class EntryIterator<K,V> extends ViewIterator<K,V>
2888	<	implements Iterator<Map.Entry<K,V>> {
2887	>	static final class EntryIterator<K,V> extends InternalIterator<K,V>
2888	>	implements Spliterator<Map.Entry<K,V>> {
2889		EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
2890	<
2891	<	@SuppressWarnings("unchecked")
2892	<	public final Map.Entry<K,V> next() {
2893	<	if (next == null)
2894	<	throw new NoSuchElementException();
2895	<	Object k = nextKey;
2896	<	Object v = nextVal;
2897	<	advance();
2898	<	return new WriteThroughEntry<K,V>((K)k, (V)v, map);
2890	>	EntryIterator(InternalIterator<K,V> it, boolean split) {
2891	>	super(it, split);
2892	>	}
2893	>	public EntryIterator<K,V> split() {
2894	>	if (last != null || (next != null && nextVal == null))
2895	>	throw new IllegalStateException();
2896	>	return new EntryIterator<K,V>(this, true);
2897	>	}
2898	>	public EntryIterator<K,V> clone() {
2899	>	if (last != null || (next != null && nextVal == null))
2900	>	throw new IllegalStateException();
2901	>	return new EntryIterator<K,V>(this, false);
2902		}
2786	–	}
2787	–
2788	–	static final class SnapshotEntryIterator<K,V> extends ViewIterator<K,V>
2789	–	implements Iterator<Map.Entry<K,V>> {
2790	–	SnapshotEntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
2903
2904		@SuppressWarnings("unchecked")
2905		public final Map.Entry<K,V> next() {
2906	<	if (next == null)
2906	>	Object v;
2907	>	if ((v = nextVal) == null && (v = advance()) == null)
2908		throw new NoSuchElementException();
2909		Object k = nextKey;
2910	<	Object v = nextVal;
2911	<	advance();
2799	<	return new SnapshotEntry<K,V>((K)k, (V)v);
2910	>	nextVal = null;
2911	>	return new MapEntry<K,V>((K)k, (V)v, map);
2912		}
2913		}
2914
2915		/**
2916	<	* Base of writeThrough and Snapshot entry classes
2916	>	* Exported Entry for iterators
2917		*/
2918	<	static abstract class MapEntry<K,V> implements Map.Entry<K, V> {
2918	>	static final class MapEntry<K,V> implements Map.Entry<K, V> {
2919		final K key; // non-null
2920		V val;       // non-null
2921	<	MapEntry(K key, V val)        { this.key = key; this.val = val; }
2921	>	final ConcurrentHashMapV8<K, V> map;
2922	>	MapEntry(K key, V val, ConcurrentHashMapV8<K, V> map) {
2923	>	this.key = key;
2924	>	this.val = val;
2925	>	this.map = map;
2926	>	}
2927		public final K getKey()       { return key; }
2928		public final V getValue()     { return val; }
2929		public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
#	Line 2821 | Line 2938 | public class ConcurrentHashMapV8<K, V>
2938		(v == val || v.equals(val)));
2939		}
2940
2824	–	public abstract V setValue(V value);
2825	–	}
2826	–
2827	–	/**
2828	–	* Entry used by EntryIterator.next(), that relays setValue
2829	–	* changes to the underlying map.
2830	–	*/
2831	–	static final class WriteThroughEntry<K,V> extends MapEntry<K,V>
2832	–	implements Map.Entry<K, V> {
2833	–	final ConcurrentHashMapV8<K, V> map;
2834	–	WriteThroughEntry(K key, V val, ConcurrentHashMapV8<K, V> map) {
2835	–	super(key, val);
2836	–	this.map = map;
2837	–	}
2838	–
2941		/**
2942		* Sets our entry's value and writes through to the map. The
2943	<	* value to return is somewhat arbitrary here. Since a
2944	<	* WriteThroughEntry does not necessarily track asynchronous
2945	<	* changes, the most recent "previous" value could be
2946	<	* different from what we return (or could even have been
2947	<	* removed in which case the put will re-establish). We do not
2846	<	* and cannot guarantee more.
2943	>	* value to return is somewhat arbitrary here. Since we do not
2944	>	* necessarily track asynchronous changes, the most recent
2945	>	* "previous" value could be different from what we return (or
2946	>	* could even have been removed in which case the put will
2947	>	* re-establish). We do not and cannot guarantee more.
2948		*/
2949		public final V setValue(V value) {
2950		if (value == null) throw new NullPointerException();
#	Line 2854 | Line 2955 | public class ConcurrentHashMapV8<K, V>
2955		}
2956		}
2957
2857	–	/**
2858	–	* Internal version of entry, that doesn't write though changes
2859	–	*/
2860	–	static final class SnapshotEntry<K,V> extends MapEntry<K,V>
2861	–	implements Map.Entry<K, V> {
2862	–	SnapshotEntry(K key, V val) { super(key, val); }
2863	–	public final V setValue(V value) { // only locally update
2864	–	if (value == null) throw new NullPointerException();
2865	–	V v = val;
2866	–	val = value;
2867	–	return v;
2868	–	}
2869	–	}
2870	–
2958		/* ----------------Views -------------- */
2959
2960		/**
2961	<	* Base class for views. This is done mainly to allow adding
2875	<	* customized parallel traversals (not yet implemented.)
2961	>	* Base class for views.
2962		*/
2963		static abstract class MapView<K, V> {
2964		final ConcurrentHashMapV8<K, V> map;
#	Line 2882 | Line 2968 | public class ConcurrentHashMapV8<K, V>
2968		public final void clear()               { map.clear(); }
2969
2970		// implementations below rely on concrete classes supplying these
2971	<	abstract Iterator<?> iter();
2971	>	abstract public Iterator<?> iterator();
2972		abstract public boolean contains(Object o);
2973		abstract public boolean remove(Object o);
2974
#	Line 2895 | Line 2981 | public class ConcurrentHashMapV8<K, V>
2981		int n = (int)sz;
2982		Object[] r = new Object[n];
2983		int i = 0;
2984	<	Iterator<?> it = iter();
2984	>	Iterator<?> it = iterator();
2985		while (it.hasNext()) {
2986		if (i == n) {
2987		if (n >= MAX_ARRAY_SIZE)
#	Line 2922 | Line 3008 | public class ConcurrentHashMapV8<K, V>
3008		.newInstance(a.getClass().getComponentType(), m);
3009		int n = r.length;
3010		int i = 0;
3011	<	Iterator<?> it = iter();
3011	>	Iterator<?> it = iterator();
3012		while (it.hasNext()) {
3013		if (i == n) {
3014		if (n >= MAX_ARRAY_SIZE)
#	Line 2944 | Line 3030 | public class ConcurrentHashMapV8<K, V>
3030
3031		public final int hashCode() {
3032		int h = 0;
3033	<	for (Iterator<?> it = iter(); it.hasNext();)
3033	>	for (Iterator<?> it = iterator(); it.hasNext();)
3034		h += it.next().hashCode();
3035		return h;
3036		}
#	Line 2952 | Line 3038 | public class ConcurrentHashMapV8<K, V>
3038		public final String toString() {
3039		StringBuilder sb = new StringBuilder();
3040		sb.append('[');
3041	<	Iterator<?> it = iter();
3041	>	Iterator<?> it = iterator();
3042		if (it.hasNext()) {
3043		for (;;) {
3044		Object e = it.next();
#	Line 2978 | Line 3064 | public class ConcurrentHashMapV8<K, V>
3064
3065		public final boolean removeAll(Collection<?> c) {
3066		boolean modified = false;
3067	<	for (Iterator<?> it = iter(); it.hasNext();) {
3067	>	for (Iterator<?> it = iterator(); it.hasNext();) {
3068		if (c.contains(it.next())) {
3069		it.remove();
3070		modified = true;
#	Line 2989 | Line 3075 | public class ConcurrentHashMapV8<K, V>
3075
3076		public final boolean retainAll(Collection<?> c) {
3077		boolean modified = false;
3078	<	for (Iterator<?> it = iter(); it.hasNext();) {
3078	>	for (Iterator<?> it = iterator(); it.hasNext();) {
3079		if (!c.contains(it.next())) {
3080		it.remove();
3081		modified = true;
#	Line 3004 | Line 3090 | public class ConcurrentHashMapV8<K, V>
3090		KeySet(ConcurrentHashMapV8<K, V> map)   { super(map); }
3091		public final boolean contains(Object o) { return map.containsKey(o); }
3092		public final boolean remove(Object o)   { return map.remove(o) != null; }
3007	–
3093		public final Iterator<K> iterator() {
3094		return new KeyIterator<K,V>(map);
3095		}
3011	–	final Iterator<?> iter() {
3012	–	return new KeyIterator<K,V>(map);
3013	–	}
3096		public final boolean add(K e) {
3097		throw new UnsupportedOperationException();
3098		}
#	Line 3029 | Line 3111 | public class ConcurrentHashMapV8<K, V>
3111		implements Collection<V> {
3112		Values(ConcurrentHashMapV8<K, V> map)   { super(map); }
3113		public final boolean contains(Object o) { return map.containsValue(o); }
3032	–
3114		public final boolean remove(Object o) {
3115		if (o != null) {
3116		Iterator<V> it = new ValueIterator<K,V>(map);
#	Line 3045 | Line 3126 | public class ConcurrentHashMapV8<K, V>
3126		public final Iterator<V> iterator() {
3127		return new ValueIterator<K,V>(map);
3128		}
3048	–	final Iterator<?> iter() {
3049	–	return new ValueIterator<K,V>(map);
3050	–	}
3129		public final boolean add(V e) {
3130		throw new UnsupportedOperationException();
3131		}
#	Line 3059 | Line 3137 | public class ConcurrentHashMapV8<K, V>
3137		static final class EntrySet<K,V> extends MapView<K,V>
3138		implements Set<Map.Entry<K,V>> {
3139		EntrySet(ConcurrentHashMapV8<K, V> map) { super(map); }
3062	–
3140		public final boolean contains(Object o) {
3141		Object k, v, r; Map.Entry<?,?> e;
3142		return ((o instanceof Map.Entry) &&
#	Line 3068 | Line 3145 | public class ConcurrentHashMapV8<K, V>
3145		(v = e.getValue()) != null &&
3146		(v == r || v.equals(r)));
3147		}
3071	–
3148		public final boolean remove(Object o) {
3149		Object k, v; Map.Entry<?,?> e;
3150		return ((o instanceof Map.Entry) &&
#	Line 3076 | Line 3152 | public class ConcurrentHashMapV8<K, V>
3152		(v = e.getValue()) != null &&
3153		map.remove(k, v));
3154		}
3079	–
3155		public final Iterator<Map.Entry<K,V>> iterator() {
3156		return new EntryIterator<K,V>(map);
3157		}
3083	–	final Iterator<?> iter() {
3084	–	return new SnapshotEntryIterator<K,V>(map);
3085	–	}
3158		public final boolean add(Entry<K,V> e) {
3159		throw new UnsupportedOperationException();
3160		}
#	Line 3128 | Line 3200 | public class ConcurrentHashMapV8<K, V>
3200		segments[i] = new Segment<K,V>(LOAD_FACTOR);
3201		}
3202		s.defaultWriteObject();
3203	<	InternalIterator it = new InternalIterator(table);
3204	<	while (it.next != null) {
3203	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
3204	>	Object v;
3205	>	while ((v = it.advance()) != null) {
3206		s.writeObject(it.nextKey);
3207	<	s.writeObject(it.nextVal);
3135	<	it.advance();
3207	>	s.writeObject(v);
3208		}
3209		s.writeObject(null);
3210		s.writeObject(null);
#	Line 3219 | Line 3291 | public class ConcurrentHashMapV8<K, V>
3291		p = p.next;
3292		}
3293		}
3222	–
3294		}
3295		}
3296

Diff Legend

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