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.40 by jsr166, Sat Jun 9 17:02:07 2012 UTC vs.
Revision 1.41 by dl, Tue Jul 3 23:25:57 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 be
149	+	* also 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	+	* Returns a Spliterator producing the same elements as this
201	+	* Spliterator. This method may be used for example to create
202	+	* a second Spliterator before a traversal, in order to later
203	+	* perform a second traversal.
204	+	*
205	+	* @return a Spliterator covering the same range as this Spliterator.
206	+	* @throws IllegalStateException if this Spliterator has
207	+	* already commenced traversing elements.
208	+	*/
209	+	Spliterator<T> clone();
210	+	}
211	+
212		/*
213		* Overview:
214		*
#	Line 294 | Line 371 | public class ConcurrentHashMapV8<K, V>
371		*
372		* The traversal scheme also applies to partial traversals of
373		* ranges of bins (via an alternate InternalIterator constructor)
374	<	* to support partitioned aggregate operations (that are not
375	<	* otherwise implemented yet).  Also, read-only operations give up
376	<	* if ever forwarded to a null table, which provides support for
377	<	* shutdown-style clearing, which is also not currently
301	<	* implemented.
374	>	* to support partitioned aggregate operations.  Also, read-only
375	>	* operations give up if ever forwarded to a null table, which
376	>	* provides support for shutdown-style clearing, which is also not
377	>	* currently implemented.
378		*
379		* Lazy table initialization minimizes footprint until first use,
380		* and also avoids resizings when the first operation is from a
#	Line 452 | Line 528 | public class ConcurrentHashMapV8<K, V>
528
529		/**
530		* Key-value entry. Note that this is never exported out as a
531	<	* user-visible Map.Entry (see WriteThroughEntry and SnapshotEntry
532	<	* below). Nodes with a hash field of MOVED are special, and do
533	<	* not contain user keys or values.  Otherwise, keys are never
534	<	* null, and null val fields indicate that a node is in the
535	<	* process of being deleted or created. For purposes of read-only
536	<	* access, a key may be read before a val, but can only be used
537	<	* after checking val to be non-null.
531	>	* user-visible Map.Entry (see MapEntry below). Nodes with a hash
532	>	* field of MOVED are special, and do not contain user keys or
533	>	* values.  Otherwise, keys are never null, and null val fields
534	>	* indicate that a node is in the process of being deleted or
535	>	* created. For purposes of read-only access, a key may be read
536	>	* before a val, but can only be used after checking val to be
537	>	* non-null.
538		*/
539		static class Node {
540		volatile int hash;
#	Line 571 | Line 647 | public class ConcurrentHashMapV8<K, V>
647		* handle this, the tree is ordered primarily by hash value, then
648		* by getClass().getName() order, and then by Comparator order
649		* among elements of the same class.  On lookup at a node, if
650	<	* non-Comparable, both left and right children may need to be
651	<	* searched in the case of tied hash values. (This corresponds to
652	<	* the full list search that would be necessary if all elements
653	<	* were non-Comparable and had tied hashes.)
650	>	* elements are not comparable or compare as 0, both left and
651	>	* right children may need to be searched in the case of tied hash
652	>	* values. (This corresponds to the full list search that would be
653	>	* necessary if all elements were non-Comparable and had tied
654	>	* hashes.)  The red-black balancing code is updated from
655	>	* pre-jdk-collections
656	>	* (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)
657	>	* based in turn on Cormen, Leiserson, and Rivest "Introduction to
658	>	* Algorithms" (CLR).
659		*
660		* TreeBins also maintain a separate locking discipline than
661		* regular bins. Because they are forwarded via special MOVED
#	Line 598 | Line 679 | public class ConcurrentHashMapV8<K, V>
679		*/
680		static final class TreeBin extends AbstractQueuedSynchronizer {
681		private static final long serialVersionUID = 2249069246763182397L;
682	<	TreeNode root;  // root of tree
683	<	TreeNode first; // head of next-pointer list
682	>	transient TreeNode root;  // root of tree
683	>	transient TreeNode first; // head of next-pointer list
684
685		/* AQS overrides */
686		public final boolean isHeldExclusively() { return getState() > 0; }
#	Line 629 | Line 710 | public class ConcurrentHashMapV8<K, V>
710		return c == -1;
711		}
712
713	+	/** From CLR */
714	+	private void rotateLeft(TreeNode p) {
715	+	if (p != null) {
716	+	TreeNode r = p.right, pp, rl;
717	+	if ((rl = p.right = r.left) != null)
718	+	rl.parent = p;
719	+	if ((pp = r.parent = p.parent) == null)
720	+	root = r;
721	+	else if (pp.left == p)
722	+	pp.left = r;
723	+	else
724	+	pp.right = r;
725	+	r.left = p;
726	+	p.parent = r;
727	+	}
728	+	}
729	+
730	+	/** From CLR */
731	+	private void rotateRight(TreeNode p) {
732	+	if (p != null) {
733	+	TreeNode l = p.left, pp, lr;
734	+	if ((lr = p.left = l.right) != null)
735	+	lr.parent = p;
736	+	if ((pp = l.parent = p.parent) == null)
737	+	root = l;
738	+	else if (pp.right == p)
739	+	pp.right = l;
740	+	else
741	+	pp.left = l;
742	+	l.right = p;
743	+	p.parent = l;
744	+	}
745	+	}
746	+
747		/**
748		* Return the TreeNode (or null if not found) for the given key
749		* starting at given root.
#	Line 637 | Line 752 | public class ConcurrentHashMapV8<K, V>
752		final TreeNode getTreeNode(int h, Object k, TreeNode p) {
753		Class<?> c = k.getClass();
754		while (p != null) {
755	<	int dir, ph;  Object pk; Class<?> pc; TreeNode r;
756	<	if (h < (ph = p.hash))
757	<	dir = -1;
758	<	else if (h > ph)
759	<	dir = 1;
760	<	else if ((pk = p.key) == k || k.equals(pk))
761	<	return p;
762	<	else if (c != (pc = pk.getClass()))
763	<	dir = c.getName().compareTo(pc.getName());
764	<	else if (k instanceof Comparable)
765	<	dir = ((Comparable)k).compareTo((Comparable)pk);
766	<	else
767	<	dir = 0;
768	<	TreeNode pr = p.right;
769	<	if (dir > 0)
770	<	p = pr;
771	<	else if (dir == 0 && pr != null && h >= pr.hash &&
772	<	(r = getTreeNode(h, k, pr)) != null)
773	<	return r;
755	>	int dir, ph;  Object pk; Class<?> pc;
756	>	if ((ph = p.hash) == h) {
757	>	if ((pk = p.key) == k || k.equals(pk))
758	>	return p;
759	>	if (c != (pc = pk.getClass()) ||
760	>	!(k instanceof Comparable) ||
761	>	(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
762	>	dir = (c == pc)? 0 : c.getName().compareTo(pc.getName());
763	>	TreeNode r = null, s = null, pl, pr;
764	>	if (dir >= 0) {
765	>	if ((pl = p.left) != null && h <= pl.hash)
766	>	s = pl;
767	>	}
768	>	else if ((pr = p.right) != null && h >= pr.hash)
769	>	s = pr;
770	>	if (s != null && (r = getTreeNode(h, k, s)) != null)
771	>	return r;
772	>	}
773	>	}
774		else
775	<	p = p.left;
775	>	dir = (h < ph) ? -1 : 1;
776	>	p = (dir > 0) ? p.right : p.left;
777		}
778		return null;
779		}
#	Line 696 | Line 812 | public class ConcurrentHashMapV8<K, V>
812		@SuppressWarnings("unchecked") // suppress Comparable cast warning
813		final TreeNode putTreeNode(int h, Object k, Object v) {
814		Class<?> c = k.getClass();
815	<	TreeNode p = root;
815	>	TreeNode pp = root, p = null;
816		int dir = 0;
817	<	if (p != null) {
818	<	for (;;) {
819	<	int ph;  Object pk; Class<?> pc; TreeNode r;
820	<	if (h < (ph = p.hash))
821	<	dir = -1;
706	<	else if (h > ph)
707	<	dir = 1;
708	<	else if ((pk = p.key) == k || k.equals(pk))
817	>	while (pp != null) { // find existing node or leaf to insert at
818	>	int ph;  Object pk; Class<?> pc;
819	>	p = pp;
820	>	if ((ph = p.hash) == h) {
821	>	if ((pk = p.key) == k || k.equals(pk))
822		return p;
823	<	else if (c != (pc = (pk = p.key).getClass()))
824	<	dir = c.getName().compareTo(pc.getName());
825	<	else if (k instanceof Comparable)
826	<	dir = ((Comparable)k).compareTo((Comparable)pk);
827	<	else
828	<	dir = 0;
829	<	TreeNode pr = p.right, pl;
830	<	if (dir > 0) {
831	<	if (pr == null)
832	<	break;
833	<	p = pr;
823	>	if (c != (pc = pk.getClass()) ||
824	>	!(k instanceof Comparable) ||
825	>	(dir = ((Comparable)k).compareTo((Comparable)pk)) == 0) {
826	>	dir = (c == pc)? 0 : c.getName().compareTo(pc.getName());
827	>	TreeNode r = null, s = null, pl, pr;
828	>	if (dir >= 0) {
829	>	if ((pl = p.left) != null && h <= pl.hash)
830	>	s = pl;
831	>	}
832	>	else if ((pr = p.right) != null && h >= pr.hash)
833	>	s = pr;
834	>	if (s != null && (r = getTreeNode(h, k, s)) != null)
835	>	return r;
836		}
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;
837		}
838	+	else
839	+	dir = (h < ph) ? -1 : 1;
840	+	pp = (dir > 0) ? p.right : p.left;
841		}
842	+
843		TreeNode f = first;
844	<	TreeNode r = first = new TreeNode(h, k, v, f, p);
844	>	TreeNode x = first = new TreeNode(h, k, v, f, p);
845		if (p == null)
846	<	root = r;
847	<	else {
846	>	root = x;
847	>	else { // attach and rebalance; adapted from CLR
848	>	TreeNode xp, xpp;
849	>	if (f != null)
850	>	f.prev = x;
851		if (dir <= 0)
852	<	p.left = r;
852	>	p.left = x;
853		else
854	<	p.right = r;
855	<	if (f != null)
856	<	f.prev = r;
857	<	fixAfterInsertion(r);
854	>	p.right = x;
855	>	x.red = true;
856	>	while (x != null && (xp = x.parent) != null && xp.red &&
857	>	(xpp = xp.parent) != null) {
858	>	TreeNode xppl = xpp.left;
859	>	if (xp == xppl) {
860	>	TreeNode y = xpp.right;
861	>	if (y != null && y.red) {
862	>	y.red = false;
863	>	xp.red = false;
864	>	xpp.red = true;
865	>	x = xpp;
866	>	}
867	>	else {
868	>	if (x == xp.right) {
869	>	rotateLeft(x = xp);
870	>	xpp = (xp = x.parent) == null ? null : xp.parent;
871	>	}
872	>	if (xp != null) {
873	>	xp.red = false;
874	>	if (xpp != null) {
875	>	xpp.red = true;
876	>	rotateRight(xpp);
877	>	}
878	>	}
879	>	}
880	>	}
881	>	else {
882	>	TreeNode y = xppl;
883	>	if (y != null && y.red) {
884	>	y.red = false;
885	>	xp.red = false;
886	>	xpp.red = true;
887	>	x = xpp;
888	>	}
889	>	else {
890	>	if (x == xp.left) {
891	>	rotateRight(x = xp);
892	>	xpp = (xp = x.parent) == null ? null : xp.parent;
893	>	}
894	>	if (xp != null) {
895	>	xp.red = false;
896	>	if (xpp != null) {
897	>	xpp.red = true;
898	>	rotateLeft(xpp);
899	>	}
900	>	}
901	>	}
902	>	}
903	>	}
904	>	TreeNode r = root;
905	>	if (r != null && r.red)
906	>	r.red = false;
907		}
908		return null;
909		}
#	Line 765 | Line 929 | public class ConcurrentHashMapV8<K, V>
929		TreeNode pl = p.left;
930		TreeNode pr = p.right;
931		if (pl != null && pr != null) {
932	<	TreeNode s = pr;
933	<	while (s.left != null) // find successor
934	<	s = s.left;
932	>	TreeNode s = pr, sl;
933	>	while ((sl = s.left) != null) // find successor
934	>	s = sl;
935		boolean c = s.red; s.red = p.red; p.red = c; // swap colors
936		TreeNode sr = s.right;
937		TreeNode pp = p.parent;
#	Line 819 | Line 983 | public class ConcurrentHashMapV8<K, V>
983		pp.right = replacement;
984		p.left = p.right = p.parent = null;
985		}
986	<	if (!p.red)
987	<	fixAfterDeletion(replacement);
988	<	if (p == replacement && (pp = p.parent) != null) {
989	<	if (p == pp.left) // detach pointers
990	<	pp.left = null;
991	<	else if (p == pp.right)
992	<	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;
986	>	if (!p.red) { // rebalance, from CLR
987	>	TreeNode x = replacement;
988	>	while (x != null) {
989	>	TreeNode xp, xpl;
990	>	if (x.red || (xp = x.parent) == null) {
991	>	x.red = false;
992	>	break;
993		}
994	<	else {
995	<	if (x == xp.right) {
996	<	x = xp;
997	<	rotateLeft(x);
998	<	xpp = (xp = x.parent) == null ? null : xp.parent;
999	<	}
1000	<	if (xp != null) {
892	<	xp.red = false;
893	<	if (xpp != null) {
894	<	xpp.red = true;
895	<	rotateRight(xpp);
896	<	}
994	>	if (x == (xpl = xp.left)) {
995	>	TreeNode sib = xp.right;
996	>	if (sib != null && sib.red) {
997	>	sib.red = false;
998	>	xp.red = true;
999	>	rotateLeft(xp);
1000	>	sib = (xp = x.parent) == null ? null : xp.right;
1001		}
1002	<	}
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) {
1002	>	if (sib == null)
1003		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	–	}
1004		else {
1005	<	if (sr == null || !sr.red) {
1006	<	if (sl != null)
1007	<	sl.red = false;
1005	>	TreeNode sl = sib.left, sr = sib.right;
1006	>	if ((sr == null || !sr.red) &&
1007	>	(sl == null || !sl.red)) {
1008		sib.red = true;
1009	<	rotateRight(sib);
960	<	sib = (xp = x.parent) == null ? null : xp.right;
1009	>	x = xp;
1010		}
1011	<	if (sib != null) {
1012	<	sib.red = (xp == null) ? false : xp.red;
1013	<	if ((sr = sib.right) != null)
1014	<	sr.red = false;
1015	<	}
1016	<	if (xp != null) {
1017	<	xp.red = false;
1018	<	rotateLeft(xp);
1011	>	else {
1012	>	if (sr == null || !sr.red) {
1013	>	if (sl != null)
1014	>	sl.red = false;
1015	>	sib.red = true;
1016	>	rotateRight(sib);
1017	>	sib = (xp = x.parent) == null ? null : xp.right;
1018	>	}
1019	>	if (sib != null) {
1020	>	sib.red = (xp == null)? false : xp.red;
1021	>	if ((sr = sib.right) != null)
1022	>	sr.red = false;
1023	>	}
1024	>	if (xp != null) {
1025	>	xp.red = false;
1026	>	rotateLeft(xp);
1027	>	}
1028	>	x = root;
1029		}
971	–	x = root;
1030		}
1031		}
1032	<	}
1033	<	else { // symmetric
1034	<	TreeNode sib = xpl;
1035	<	if (sib != null && sib.red) {
1036	<	sib.red = false;
1037	<	xp.red = true;
1038	<	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;
1032	>	else { // symmetric
1033	>	TreeNode sib = xpl;
1034	>	if (sib != null && sib.red) {
1035	>	sib.red = false;
1036	>	xp.red = true;
1037	>	rotateRight(xp);
1038	>	sib = (xp = x.parent) == null ? null : xp.left;
1039		}
1040	+	if (sib == null)
1041	+	x = xp;
1042		else {
1043	<	if (sl == null || !sl.red) {
1044	<	if (sr != null)
1045	<	sr.red = false;
1043	>	TreeNode sl = sib.left, sr = sib.right;
1044	>	if ((sl == null || !sl.red) &&
1045	>	(sr == null || !sr.red)) {
1046		sib.red = true;
1047	<	rotateLeft(sib);
998	<	sib = (xp = x.parent) == null ? null : xp.left;
1047	>	x = xp;
1048		}
1049	<	if (sib != null) {
1050	<	sib.red = (xp == null) ? false : xp.red;
1051	<	if ((sl = sib.left) != null)
1052	<	sl.red = false;
1053	<	}
1054	<	if (xp != null) {
1055	<	xp.red = false;
1056	<	rotateRight(xp);
1049	>	else {
1050	>	if (sl == null || !sl.red) {
1051	>	if (sr != null)
1052	>	sr.red = false;
1053	>	sib.red = true;
1054	>	rotateLeft(sib);
1055	>	sib = (xp = x.parent) == null ? null : xp.left;
1056	>	}
1057	>	if (sib != null) {
1058	>	sib.red = (xp == null)? false : xp.red;
1059	>	if ((sl = sib.left) != null)
1060	>	sl.red = false;
1061	>	}
1062	>	if (xp != null) {
1063	>	xp.red = false;
1064	>	rotateRight(xp);
1065	>	}
1066	>	x = root;
1067		}
1009	–	x = root;
1068		}
1069		}
1070		}
1071		}
1072	+	if (p == replacement && (pp = p.parent) != null) {
1073	+	if (p == pp.left) // detach pointers
1074	+	pp.left = null;
1075	+	else if (p == pp.right)
1076	+	pp.right = null;
1077	+	p.parent = null;
1078	+	}
1079		}
1080		}
1081
#	Line 1504 | Line 1569 | public class ConcurrentHashMapV8<K, V>
1569		}
1570		}
1571		}
1572	<	if (val == null)
1573	<	throw new NullPointerException();
1574	<	counter.add(1L);
1575	<	if (count > 1)
1576	<	checkForResize();
1572	>	if (val != null) {
1573	>	counter.add(1L);
1574	>	if (count > 1)
1575	>	checkForResize();
1576	>	}
1577		return val;
1578		}
1579
#	Line 1518 | Line 1583 | public class ConcurrentHashMapV8<K, V>
1583		RemappingFunction<? super K, V> mf) {
1584		int h = spread(k.hashCode());
1585		Object val = null;
1586	<	boolean added = false;
1586	>	int delta = 0;
1587		int count = 0;
1588		for (Node[] tab = table;;) {
1589		Node f; int i, fh; Object fk;
#	Line 1531 | Line 1596 | public class ConcurrentHashMapV8<K, V>
1596		count = 1;
1597		if ((val = mf.remap(k, null)) != null) {
1598		node.val = val;
1599	<	added = true;
1599	>	delta = 1;
1600		}
1601		} finally {
1602	<	if (!added)
1602	>	if (delta == 0)
1603		setTabAt(tab, i, null);
1604		if (!node.casHash(fh, h)) {
1605		node.hash = h;
#	Line 1559 | Line 1624 | public class ConcurrentHashMapV8<K, V>
1624		p.val = val;
1625		else {
1626		count = 2;
1627	<	added = true;
1627	>	delta = 1;
1628		t.putTreeNode(h, k, val);
1629		}
1630		}
1631	+	else if (p != null) {
1632	+	delta = -1;
1633	+	t.deleteTreeNode(p);
1634	+	}
1635		}
1636		} finally {
1637		t.release(0);
#	Line 1581 | Line 1650 | public class ConcurrentHashMapV8<K, V>
1650		try {
1651		if (tabAt(tab, i) == f) {
1652		count = 1;
1653	<	for (Node e = f;; ++count) {
1653	>	for (Node e = f, pred = null;; ++count) {
1654		Object ek, ev;
1655		if ((e.hash & HASH_BITS) == h &&
1656		(ev = e.val) != null &&
#	Line 1589 | Line 1658 | public class ConcurrentHashMapV8<K, V>
1658		val = mf.remap(k, (V)ev);
1659		if (val != null)
1660		e.val = val;
1661	+	else {
1662	+	delta = -1;
1663	+	Node en = e.next;
1664	+	if (pred != null)
1665	+	pred.next = en;
1666	+	else
1667	+	setTabAt(tab, i, en);
1668	+	}
1669		break;
1670		}
1671	<	Node last = e;
1671	>	pred = e;
1672		if ((e = e.next) == null) {
1673		if ((val = mf.remap(k, null)) != null) {
1674	<	last.next = new Node(h, k, val, null);
1675	<	added = true;
1674	>	pred.next = new Node(h, k, val, null);
1675	>	delta = 1;
1676		if (count >= TREE_THRESHOLD)
1677		replaceWithTreeBin(tab, i, k);
1678		}
#	Line 1616 | Line 1693 | public class ConcurrentHashMapV8<K, V>
1693		}
1694		}
1695		}
1696	<	if (val == null)
1697	<	throw new NullPointerException();
1621	<	if (added) {
1622	<	counter.add(1L);
1696	>	if (delta != 0) {
1697	>	counter.add((long)delta);
1698		if (count > 1)
1699		checkForResize();
1700		}
#	Line 2082 | Line 2157 | public class ConcurrentHashMapV8<K, V>
2157		* valid.
2158		*
2159		* Internal traversals directly access these fields, as in:
2160	<	* {@code while (it.next != null) { process(it.nextKey); it.advance(); }}
2160	>	* {@code while (it.advance() != null) { process(it.nextKey); }}
2161		*
2162	<	* Exported iterators (subclasses of ViewIterator) extract key,
2163	<	* value, or key-value pairs as return values of Iterator.next(),
2164	<	* and encapsulate the it.next check as hasNext();
2162	>	* Exported iterators must track whether the iterator has advanced
2163	>	* (in hasNext vs next) (by setting/checking/nulling field
2164	>	* nextVal), and then extract key, value, or key-value pairs as
2165	>	* return values of next().
2166		*
2167		* The iterator visits once each still-valid node that was
2168		* reachable upon iterator construction. It might miss some that
#	Line 2104 | Line 2180 | public class ConcurrentHashMapV8<K, V>
2180		* paranoically cope with potential sharing by users of iterators
2181		* across threads, iteration terminates if a bounds checks fails
2182		* for a table read.
2107	–	*
2108	–	* The range-based constructor enables creation of parallel
2109	–	* range-splitting traversals. (Not yet implemented.)
2183		*/
2184	<	static class InternalIterator {
2184	>	static class InternalIterator<K,V> {
2185	>	final ConcurrentHashMapV8<K, V> map;
2186		Node next;           // the next entry to use
2187		Node last;           // the last entry used
2188		Object nextKey;      // cached key field of next
#	Line 2116 | Line 2190 | public class ConcurrentHashMapV8<K, V>
2190		Node[] tab;          // current table; updated if resized
2191		int index;           // index of bin to use next
2192		int baseIndex;       // current index of initial table
2193	<	final int baseLimit; // index bound for initial table
2193	>	int baseLimit;       // index bound for initial table
2194		final int baseSize;  // initial table size
2195
2196		/** Creates iterator for all entries in the table. */
2197	<	InternalIterator(Node[] tab) {
2198	<	this.tab = tab;
2197	>	InternalIterator(ConcurrentHashMapV8<K, V> map) {
2198	>	this.tab = (this.map = map).table;
2199		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();
2200		}
2201
2202	<	/** Advances next. See above for explanation. */
2203	<	final void advance() {
2202	>	/** Creates iterator for clone() and split() methods */
2203	>	InternalIterator(InternalIterator<K,V> it, boolean split) {
2204	>	this.map = it.map;
2205	>	this.tab = it.tab;
2206	>	this.baseSize = it.baseSize;
2207	>	int lo = it.baseIndex;
2208	>	int hi = this.baseLimit = it.baseLimit;
2209	>	this.index = this.baseIndex =
2210	>	(split) ? (it.baseLimit = (lo + hi + 1) >>> 1) : lo;
2211	>	}
2212	>
2213	>	/**
2214	>	* Advances next; returns nextVal or null if terminated
2215	>	* See above for explanation.
2216	>	*/
2217	>	final Object advance() {
2218		Node e = last = next;
2219	+	Object ev = null;
2220		outer: do {
2221		if (e != null)                  // advance past used/skipped node
2222		e = e.next;
#	Line 2160 | Line 2236 | public class ConcurrentHashMapV8<K, V>
2236		index = (i += baseSize) < n ? i : (baseIndex = b + 1);
2237		}
2238		nextKey = e.key;
2239	<	} while ((nextVal = e.val) == null);// skip deleted or special nodes
2239	>	} while ((ev = e.val) == null);    // skip deleted or special nodes
2240		next = e;
2241	+	return nextVal = ev;
2242		}
2243	+
2244	+	public final void remove() {
2245	+	if (nextVal == null)
2246	+	advance();
2247	+	Node e = last;
2248	+	if (e == null)
2249	+	throw new IllegalStateException();
2250	+	last = null;
2251	+	map.remove(e.key);
2252	+	}
2253	+
2254	+	public final boolean hasNext() {
2255	+	return nextVal != null || advance() != null;
2256	+	}
2257	+
2258	+	public final boolean hasMoreElements() { return hasNext(); }
2259		}
2260
2261		/* ---------------- Public operations -------------- */
#	Line 2324 | Line 2417 | public class ConcurrentHashMapV8<K, V>
2417		if (value == null)
2418		throw new NullPointerException();
2419		Object v;
2420	<	InternalIterator it = new InternalIterator(table);
2421	<	while (it.next != null) {
2422	<	if ((v = it.nextVal) == value || value.equals(v))
2420	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2421	>	while ((v = it.advance()) != null) {
2422	>	if (v == value || value.equals(v))
2423		return true;
2331	–	it.advance();
2424		}
2425		return false;
2426		}
#	Line 2399 | Line 2491 | public class ConcurrentHashMapV8<K, V>
2491
2492		/**
2493		* If the specified key is not already associated with a value,
2494	<	* computes its value using the given mappingFunction and
2495	<	* enters it into the map.  This is equivalent to
2494	>	* computes its value using the given mappingFunction and enters
2495	>	* it into the map unless null.  This is equivalent to
2496		* <pre> {@code
2497		* if (map.containsKey(key))
2498		*   return map.get(key);
2499		* value = mappingFunction.map(key);
2500	<	* map.put(key, value);
2500	>	* if (value != null)
2501	>	*   map.put(key, value);
2502		* return value;}</pre>
2503		*
2504		* except that the action is performed atomically.  If the
2505	<	* function returns {@code null} (in which case a {@code
2506	<	* NullPointerException} is thrown), or the function itself throws
2507	<	* an (unchecked) exception, the exception is rethrown to its
2508	<	* caller, and no mapping is recorded.  Some attempted update
2509	<	* operations on this map by other threads may be blocked while
2510	<	* computation is in progress, so the computation should be short
2511	<	* and simple, and must not attempt to update any other mappings
2512	<	* of this Map. The most appropriate usage is to construct a new
2513	<	* object serving as an initial mapped value, or memoized result,
2421	<	* as in:
2505	>	* function returns {@code null} no mapping is recorded. If the
2506	>	* function itself throws an (unchecked) exception, the exception
2507	>	* is rethrown to its caller, and no mapping is recorded.  Some
2508	>	* attempted update operations on this map by other threads may be
2509	>	* blocked while computation is in progress, so the computation
2510	>	* should be short and simple, and must not attempt to update any
2511	>	* other mappings of this Map. The most appropriate usage is to
2512	>	* construct a new object serving as an initial mapped value, or
2513	>	* memoized result, as in:
2514		*
2515		*  <pre> {@code
2516		* map.computeIfAbsent(key, new MappingFunction<K, V>() {
#	Line 2427 | Line 2519 | public class ConcurrentHashMapV8<K, V>
2519		* @param key key with which the specified value is to be associated
2520		* @param mappingFunction the function to compute a value
2521		* @return the current (existing or computed) value associated with
2522	<	*         the specified key.
2523	<	* @throws NullPointerException if the specified key, mappingFunction,
2524	<	*         or computed value is null
2522	>	*         the specified key, or null if the computed value is null.
2523	>	* @throws NullPointerException if the specified key or mappingFunction
2524	>	*         is null
2525		* @throws IllegalStateException if the computation detectably
2526		*         attempts a recursive update to this map that would
2527		*         otherwise never complete
#	Line 2444 | Line 2536 | public class ConcurrentHashMapV8<K, V>
2536		}
2537
2538		/**
2539	<	* Computes and enters a new mapping value given a key and
2539	>	* Computes a new mapping value given a key and
2540		* its current mapped value (or {@code null} if there is no current
2541		* mapping). This is equivalent to
2542		*  <pre> {@code
2543	<	*  map.put(key, remappingFunction.remap(key, map.get(key));
2543	>	*   value = remappingFunction.remap(key, map.get(key));
2544	>	*   if (value != null)
2545	>	*     map.put(key, value);
2546	>	*   else
2547	>	*     map.remove(key);
2548		* }</pre>
2549		*
2550		* except that the action is performed atomically.  If the
2551	<	* function returns {@code null} (in which case a {@code
2552	<	* NullPointerException} is thrown), or the function itself throws
2553	<	* an (unchecked) exception, the exception is rethrown to its
2554	<	* caller, and current mapping is left unchanged.  Some attempted
2555	<	* update operations on this map by other threads may be blocked
2556	<	* while computation is in progress, so the computation should be
2557	<	* short and simple, and must not attempt to update any other
2558	<	* mappings of this Map. For example, to either create or
2463	<	* append new messages to a value mapping:
2551	>	* function returns {@code null}, the mapping is removed.  If the
2552	>	* function itself throws an (unchecked) exception, the exception
2553	>	* is rethrown to its caller, and the current mapping is left
2554	>	* unchanged.  Some attempted update operations on this map by
2555	>	* other threads may be blocked while computation is in progress,
2556	>	* so the computation should be short and simple, and must not
2557	>	* attempt to update any other mappings of this Map. For example,
2558	>	* to either create or append new messages to a value mapping:
2559		*
2560		* <pre> {@code
2561		* Map<Key, String> map = ...;
#	Line 2472 | Line 2567 | public class ConcurrentHashMapV8<K, V>
2567		* @param key key with which the specified value is to be associated
2568		* @param remappingFunction the function to compute a value
2569		* @return the new value associated with
2570	<	*         the specified key.
2570	>	*         the specified key, or null if none.
2571		* @throws NullPointerException if the specified key or remappingFunction
2572	<	*         or computed value is null
2572	>	*         is null
2573		* @throws IllegalStateException if the computation detectably
2574		*         attempts a recursive update to this map that would
2575		*         otherwise never complete
#	Line 2633 | Line 2728 | public class ConcurrentHashMapV8<K, V>
2728		}
2729
2730		/**
2731	+	* Returns a partionable iterator of the keys in this map.
2732	+	*
2733	+	* @return a partionable iterator of the keys in this map
2734	+	*/
2735	+	public Spliterator<K> keySpliterator() {
2736	+	return new KeyIterator<K,V>(this);
2737	+	}
2738	+
2739	+	/**
2740	+	* Returns a partionable iterator of the values in this map.
2741	+	*
2742	+	* @return a partionable iterator of the values in this map
2743	+	*/
2744	+	public Spliterator<V> valueSpliterator() {
2745	+	return new ValueIterator<K,V>(this);
2746	+	}
2747	+
2748	+	/**
2749	+	* Returns a partionable iterator of the entries in this map.
2750	+	*
2751	+	* @return a partionable iterator of the entries in this map
2752	+	*/
2753	+	public Spliterator<Map.Entry<K,V>> entrySpliterator() {
2754	+	return new EntryIterator<K,V>(this);
2755	+	}
2756	+
2757	+	/**
2758		* Returns the hash code value for this {@link Map}, i.e.,
2759		* the sum of, for each key-value pair in the map,
2760		* {@code key.hashCode() ^ value.hashCode()}.
#	Line 2641 | Line 2763 | public class ConcurrentHashMapV8<K, V>
2763		*/
2764		public int hashCode() {
2765		int h = 0;
2766	<	InternalIterator it = new InternalIterator(table);
2767	<	while (it.next != null) {
2768	<	h += it.nextKey.hashCode() ^ it.nextVal.hashCode();
2769	<	it.advance();
2766	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2767	>	Object v;
2768	>	while ((v = it.advance()) != null) {
2769	>	h += it.nextKey.hashCode() ^ v.hashCode();
2770		}
2771		return h;
2772		}
#	Line 2661 | Line 2783 | public class ConcurrentHashMapV8<K, V>
2783		* @return a string representation of this map
2784		*/
2785		public String toString() {
2786	<	InternalIterator it = new InternalIterator(table);
2786	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2787		StringBuilder sb = new StringBuilder();
2788		sb.append('{');
2789	<	if (it.next != null) {
2789	>	Object v;
2790	>	if ((v = it.advance()) != null) {
2791		for (;;) {
2792	<	Object k = it.nextKey, v = it.nextVal;
2792	>	Object k = it.nextKey;
2793		sb.append(k == this ? "(this Map)" : k);
2794		sb.append('=');
2795		sb.append(v == this ? "(this Map)" : v);
2796	<	it.advance();
2674	<	if (it.next == null)
2796	>	if ((v = it.advance()) == null)
2797		break;
2798		sb.append(',').append(' ');
2799		}
#	Line 2694 | Line 2816 | public class ConcurrentHashMapV8<K, V>
2816		if (!(o instanceof Map))
2817		return false;
2818		Map<?,?> m = (Map<?,?>) o;
2819	<	InternalIterator it = new InternalIterator(table);
2820	<	while (it.next != null) {
2821	<	Object val = it.nextVal;
2819	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
2820	>	Object val;
2821	>	while ((val = it.advance()) != null) {
2822		Object v = m.get(it.nextKey);
2823		if (v == null || (v != val && !v.equals(val)))
2824		return false;
2703	–	it.advance();
2825		}
2826		for (Map.Entry<?,?> e : m.entrySet()) {
2827		Object mk, mv, v;
#	Line 2716 | Line 2837 | public class ConcurrentHashMapV8<K, V>
2837
2838		/* ----------------Iterators -------------- */
2839
2840	<	/**
2841	<	* Base class for key, value, and entry iterators.  Adds a map
2842	<	* reference to InternalIterator to support Iterator.remove.
2843	<	*/
2844	<	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;
2840	>	static final class KeyIterator<K,V> extends InternalIterator<K,V>
2841	>	implements Spliterator<K>, Enumeration<K> {
2842	>	KeyIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
2843	>	KeyIterator(InternalIterator<K,V> it, boolean split) {
2844	>	super(it, split);
2845		}
2846	<
2847	<	public final void remove() {
2731	<	if (last == null)
2846	>	public KeyIterator<K,V> split() {
2847	>	if (last != null || (next != null && nextVal == null))
2848		throw new IllegalStateException();
2849	<	map.remove(last.key);
2850	<	last = null;
2849	>	return new KeyIterator<K,V>(this, true);
2850	>	}
2851	>	public KeyIterator<K,V> clone() {
2852	>	if (last != null || (next != null && nextVal == null))
2853	>	throw new IllegalStateException();
2854	>	return new KeyIterator<K,V>(this, false);
2855		}
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); }
2856
2857		@SuppressWarnings("unchecked")
2858		public final K next() {
2859	<	if (next == null)
2859	>	if (nextVal == null && advance() == null)
2860		throw new NoSuchElementException();
2861		Object k = nextKey;
2862	<	advance();
2863	<	return (K)k;
2862	>	nextVal = null;
2863	>	return (K) k;
2864		}
2865
2866		public final K nextElement() { return next(); }
2867		}
2868
2869	<	static final class ValueIterator<K,V> extends ViewIterator<K,V>
2870	<	implements Iterator<V>, Enumeration<V> {
2869	>	static final class ValueIterator<K,V> extends InternalIterator<K,V>
2870	>	implements Spliterator<V>, Enumeration<V> {
2871		ValueIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
2872	+	ValueIterator(InternalIterator<K,V> it, boolean split) {
2873	+	super(it, split);
2874	+	}
2875	+	public ValueIterator<K,V> split() {
2876	+	if (last != null || (next != null && nextVal == null))
2877	+	throw new IllegalStateException();
2878	+	return new ValueIterator<K,V>(this, true);
2879	+	}
2880	+
2881	+	public ValueIterator<K,V> clone() {
2882	+	if (last != null || (next != null && nextVal == null))
2883	+	throw new IllegalStateException();
2884	+	return new ValueIterator<K,V>(this, false);
2885	+	}
2886
2887		@SuppressWarnings("unchecked")
2888		public final V next() {
2889	<	if (next == null)
2889	>	Object v;
2890	>	if ((v = nextVal) == null && (v = advance()) == null)
2891		throw new NoSuchElementException();
2892	<	Object v = nextVal;
2893	<	advance();
2767	<	return (V)v;
2892	>	nextVal = null;
2893	>	return (V) v;
2894		}
2895
2896		public final V nextElement() { return next(); }
2897		}
2898
2899	<	static final class EntryIterator<K,V> extends ViewIterator<K,V>
2900	<	implements Iterator<Map.Entry<K,V>> {
2899	>	static final class EntryIterator<K,V> extends InternalIterator<K,V>
2900	>	implements Spliterator<Map.Entry<K,V>> {
2901		EntryIterator(ConcurrentHashMapV8<K, V> map) { super(map); }
2902	<
2903	<	@SuppressWarnings("unchecked")
2904	<	public final Map.Entry<K,V> next() {
2905	<	if (next == null)
2906	<	throw new NoSuchElementException();
2907	<	Object k = nextKey;
2908	<	Object v = nextVal;
2909	<	advance();
2910	<	return new WriteThroughEntry<K,V>((K)k, (V)v, map);
2902	>	EntryIterator(InternalIterator<K,V> it, boolean split) {
2903	>	super(it, split);
2904	>	}
2905	>	public EntryIterator<K,V> split() {
2906	>	if (last != null || (next != null && nextVal == null))
2907	>	throw new IllegalStateException();
2908	>	return new EntryIterator<K,V>(this, true);
2909	>	}
2910	>	public EntryIterator<K,V> clone() {
2911	>	if (last != null || (next != null && nextVal == null))
2912	>	throw new IllegalStateException();
2913	>	return new EntryIterator<K,V>(this, false);
2914		}
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); }
2915
2916		@SuppressWarnings("unchecked")
2917		public final Map.Entry<K,V> next() {
2918	<	if (next == null)
2918	>	Object v;
2919	>	if ((v = nextVal) == null && (v = advance()) == null)
2920		throw new NoSuchElementException();
2921		Object k = nextKey;
2922	<	Object v = nextVal;
2923	<	advance();
2799	<	return new SnapshotEntry<K,V>((K)k, (V)v);
2922	>	nextVal = null;
2923	>	return new MapEntry<K,V>((K)k, (V)v, map);
2924		}
2925		}
2926
2927		/**
2928	<	* Base of writeThrough and Snapshot entry classes
2928	>	* Exported Entry for iterators
2929		*/
2930	<	static abstract class MapEntry<K,V> implements Map.Entry<K, V> {
2930	>	static final class MapEntry<K,V> implements Map.Entry<K, V> {
2931		final K key; // non-null
2932		V val;       // non-null
2933	<	MapEntry(K key, V val)        { this.key = key; this.val = val; }
2933	>	final ConcurrentHashMapV8<K, V> map;
2934	>	MapEntry(K key, V val, ConcurrentHashMapV8<K, V> map) {
2935	>	this.key = key;
2936	>	this.val = val;
2937	>	this.map = map;
2938	>	}
2939		public final K getKey()       { return key; }
2940		public final V getValue()     { return val; }
2941		public final int hashCode()   { return key.hashCode() ^ val.hashCode(); }
#	Line 2821 | Line 2950 | public class ConcurrentHashMapV8<K, V>
2950		(v == val || v.equals(val)));
2951		}
2952
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	–
2953		/**
2954		* Sets our entry's value and writes through to the map. The
2955	<	* value to return is somewhat arbitrary here. Since a
2956	<	* WriteThroughEntry does not necessarily track asynchronous
2957	<	* changes, the most recent "previous" value could be
2958	<	* different from what we return (or could even have been
2959	<	* removed in which case the put will re-establish). We do not
2846	<	* and cannot guarantee more.
2955	>	* value to return is somewhat arbitrary here. Since a we do
2956	>	* not necessarily track asynchronous changes, the most recent
2957	>	* "previous" value could be different from what we return (or
2958	>	* could even have been removed in which case the put will
2959	>	* re-establish). We do not and cannot guarantee more.
2960		*/
2961		public final V setValue(V value) {
2962		if (value == null) throw new NullPointerException();
#	Line 2854 | Line 2967 | public class ConcurrentHashMapV8<K, V>
2967		}
2968		}
2969
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	–
2970		/* ----------------Views -------------- */
2971
2972		/**
2973	<	* Base class for views. This is done mainly to allow adding
2875	<	* customized parallel traversals (not yet implemented.)
2973	>	* Base class for views.
2974		*/
2975		static abstract class MapView<K, V> {
2976		final ConcurrentHashMapV8<K, V> map;
#	Line 2882 | Line 2980 | public class ConcurrentHashMapV8<K, V>
2980		public final void clear()               { map.clear(); }
2981
2982		// implementations below rely on concrete classes supplying these
2983	<	abstract Iterator<?> iter();
2983	>	abstract public Iterator<?> iterator();
2984		abstract public boolean contains(Object o);
2985		abstract public boolean remove(Object o);
2986
#	Line 2895 | Line 2993 | public class ConcurrentHashMapV8<K, V>
2993		int n = (int)sz;
2994		Object[] r = new Object[n];
2995		int i = 0;
2996	<	Iterator<?> it = iter();
2996	>	Iterator<?> it = iterator();
2997		while (it.hasNext()) {
2998		if (i == n) {
2999		if (n >= MAX_ARRAY_SIZE)
#	Line 2922 | Line 3020 | public class ConcurrentHashMapV8<K, V>
3020		.newInstance(a.getClass().getComponentType(), m);
3021		int n = r.length;
3022		int i = 0;
3023	<	Iterator<?> it = iter();
3023	>	Iterator<?> it = iterator();
3024		while (it.hasNext()) {
3025		if (i == n) {
3026		if (n >= MAX_ARRAY_SIZE)
#	Line 2944 | Line 3042 | public class ConcurrentHashMapV8<K, V>
3042
3043		public final int hashCode() {
3044		int h = 0;
3045	<	for (Iterator<?> it = iter(); it.hasNext();)
3045	>	for (Iterator<?> it = iterator(); it.hasNext();)
3046		h += it.next().hashCode();
3047		return h;
3048		}
#	Line 2952 | Line 3050 | public class ConcurrentHashMapV8<K, V>
3050		public final String toString() {
3051		StringBuilder sb = new StringBuilder();
3052		sb.append('[');
3053	<	Iterator<?> it = iter();
3053	>	Iterator<?> it = iterator();
3054		if (it.hasNext()) {
3055		for (;;) {
3056		Object e = it.next();
#	Line 2978 | Line 3076 | public class ConcurrentHashMapV8<K, V>
3076
3077		public final boolean removeAll(Collection<?> c) {
3078		boolean modified = false;
3079	<	for (Iterator<?> it = iter(); it.hasNext();) {
3079	>	for (Iterator<?> it = iterator(); it.hasNext();) {
3080		if (c.contains(it.next())) {
3081		it.remove();
3082		modified = true;
#	Line 2989 | Line 3087 | public class ConcurrentHashMapV8<K, V>
3087
3088		public final boolean retainAll(Collection<?> c) {
3089		boolean modified = false;
3090	<	for (Iterator<?> it = iter(); it.hasNext();) {
3090	>	for (Iterator<?> it = iterator(); it.hasNext();) {
3091		if (!c.contains(it.next())) {
3092		it.remove();
3093		modified = true;
#	Line 3004 | Line 3102 | public class ConcurrentHashMapV8<K, V>
3102		KeySet(ConcurrentHashMapV8<K, V> map)   { super(map); }
3103		public final boolean contains(Object o) { return map.containsKey(o); }
3104		public final boolean remove(Object o)   { return map.remove(o) != null; }
3007	–
3105		public final Iterator<K> iterator() {
3106		return new KeyIterator<K,V>(map);
3107		}
3011	–	final Iterator<?> iter() {
3012	–	return new KeyIterator<K,V>(map);
3013	–	}
3108		public final boolean add(K e) {
3109		throw new UnsupportedOperationException();
3110		}
#	Line 3029 | Line 3123 | public class ConcurrentHashMapV8<K, V>
3123		implements Collection<V> {
3124		Values(ConcurrentHashMapV8<K, V> map)   { super(map); }
3125		public final boolean contains(Object o) { return map.containsValue(o); }
3032	–
3126		public final boolean remove(Object o) {
3127		if (o != null) {
3128		Iterator<V> it = new ValueIterator<K,V>(map);
#	Line 3045 | Line 3138 | public class ConcurrentHashMapV8<K, V>
3138		public final Iterator<V> iterator() {
3139		return new ValueIterator<K,V>(map);
3140		}
3048	–	final Iterator<?> iter() {
3049	–	return new ValueIterator<K,V>(map);
3050	–	}
3141		public final boolean add(V e) {
3142		throw new UnsupportedOperationException();
3143		}
#	Line 3059 | Line 3149 | public class ConcurrentHashMapV8<K, V>
3149		static final class EntrySet<K,V> extends MapView<K,V>
3150		implements Set<Map.Entry<K,V>> {
3151		EntrySet(ConcurrentHashMapV8<K, V> map) { super(map); }
3062	–
3152		public final boolean contains(Object o) {
3153		Object k, v, r; Map.Entry<?,?> e;
3154		return ((o instanceof Map.Entry) &&
#	Line 3068 | Line 3157 | public class ConcurrentHashMapV8<K, V>
3157		(v = e.getValue()) != null &&
3158		(v == r || v.equals(r)));
3159		}
3071	–
3160		public final boolean remove(Object o) {
3161		Object k, v; Map.Entry<?,?> e;
3162		return ((o instanceof Map.Entry) &&
#	Line 3076 | Line 3164 | public class ConcurrentHashMapV8<K, V>
3164		(v = e.getValue()) != null &&
3165		map.remove(k, v));
3166		}
3079	–
3167		public final Iterator<Map.Entry<K,V>> iterator() {
3168		return new EntryIterator<K,V>(map);
3169		}
3083	–	final Iterator<?> iter() {
3084	–	return new SnapshotEntryIterator<K,V>(map);
3085	–	}
3170		public final boolean add(Entry<K,V> e) {
3171		throw new UnsupportedOperationException();
3172		}
#	Line 3128 | Line 3212 | public class ConcurrentHashMapV8<K, V>
3212		segments[i] = new Segment<K,V>(LOAD_FACTOR);
3213		}
3214		s.defaultWriteObject();
3215	<	InternalIterator it = new InternalIterator(table);
3216	<	while (it.next != null) {
3215	>	InternalIterator<K,V> it = new InternalIterator<K,V>(this);
3216	>	Object v;
3217	>	while ((v = it.advance()) != null) {
3218		s.writeObject(it.nextKey);
3219	<	s.writeObject(it.nextVal);
3135	<	it.advance();
3219	>	s.writeObject(v);
3220		}
3221		s.writeObject(null);
3222		s.writeObject(null);
#	Line 3219 | Line 3303 | public class ConcurrentHashMapV8<K, V>
3303		p = p.next;
3304		}
3305		}
3222	–
3306		}
3307		}
3308

Diff Legend

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