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.1 by dl, Sun Aug 28 19:08:07 2011 UTC vs.
Revision 1.12 by jsr166, Tue Aug 30 18:31:54 2011 UTC

#	Line 54 | Line 54 | import java.io.Serializable;
54		* <p> Resizing this or any other kind of hash table is a relatively
55		* slow operation, so, when possible, it is a good idea to provide
56		* estimates of expected table sizes in constructors. Also, for
57	<	* compatability with previous versions of this class, constructors
57	>	* compatibility with previous versions of this class, constructors
58		* may optionally specify an expected {@code concurrencyLevel} as an
59		* additional hint for internal sizing.
60		*
#	Line 83 | Line 83 | public class ConcurrentHashMapV8<K, V>
83
84		/**
85		* A function computing a mapping from the given key to a value,
86	<	*  or <code>null</code> if there is no mapping. This is a
87	<	* place-holder for an upcoming JDK8 interface.
86	>	* or {@code null} if there is no mapping. This is a place-holder
87	>	* for an upcoming JDK8 interface.
88		*/
89		public static interface MappingFunction<K, V> {
90		/**
#	Line 125 | Line 125 | public class ConcurrentHashMapV8<K, V>
125		* within bins are always accurately traversable under volatile
126		* reads, so long as lookups check hash code and non-nullness of
127		* key and value before checking key equality. (All valid hash
128	<	* codes are nonnegative. Negative values are served for special
129	<	* nodes.)
128	>	* codes are nonnegative. Negative values are reserved for special
129	>	* forwarding nodes; see below.)
130		*
131		* A bin may be locked during update (insert, delete, and replace)
132		* operations.  We do not want to waste the space required to
#	Line 139 | Line 139 | public class ConcurrentHashMapV8<K, V>
139		* that it is still the first node, and retry if not. (Because new
140		* nodes are always appended to lists, once a node is first in a
141		* bin, it remains first until deleted or the bin becomes
142	<	* invalidated.)  However, update operations can and usually do
142	>	* invalidated.)  However, update operations can and sometimes do
143		* still traverse the bin until the point of update, which helps
144		* reduce cache misses on retries.  This is a converse of sorts to
145		* the lazy locking technique described by Herlihy & Shavit. If
146		* there is no existing node during a put operation, then one can
147		* be CAS'ed in (without need for lock except in computeIfAbsent);
148		* the CAS serves as validation. This is on average the most
149	<	* common case for put operations. The expected number of locks
150	<	* covering different elements (i.e., bins with 2 or more nodes)
151	<	* is approximately 10% at steady state under default settings.
152	<	* Lock contention probability for two threads accessing arbitrary
153	<	* distinct elements is thus less than 1% even for small tables.
149	>	* common case for put operations -- under random hash codes, the
150	>	* distribution of nodes in bins follows a Poisson distribution
151	>	* (see http://en.wikipedia.org/wiki/Poisson_distribution) with a
152	>	* parameter of 0.5 on average under the default loadFactor of
153	>	* 0.75.  The expected number of locks covering different elements
154	>	* (i.e., bins with 2 or more nodes) is approximately 10% at
155	>	* steady state under default settings.  Lock contention
156	>	* probability for two threads accessing arbitrary distinct
157	>	* elements is, roughly, 1 / (8 * #elements).
158		*
159		* The table is resized when occupancy exceeds a threshold.  Only
160		* a single thread performs the resize (using field "resizing", to
#	Line 172 | Line 176 | public class ConcurrentHashMapV8<K, V>
176		* complexity of access and iteration schemes that could admit
177		* out-of-order or concurrent bin transfers.
178		*
179	<	* (While not yet implemented, a similar traversal scheme can
180	<	* apply to partial traversals during partitioned aggregate
181	<	* operations. Also, read-only operations give up if ever
182	<	* forwarded to a null table, which provides support for
183	<	* shutdown-style clearing, which is also not currently
180	<	* implemented.)
179	>	* A similar traversal scheme (not yet implemented) can apply to
180	>	* partial traversals during partitioned aggregate operations.
181	>	* Also, read-only operations give up if ever forwarded to a null
182	>	* table, which provides support for shutdown-style clearing,
183	>	* which is also not currently implemented.
184		*
185		* The element count is maintained using a LongAdder, which avoids
186		* contention on updates but can encounter cache thrashing if read
187		* too frequently during concurrent updates. To avoid reading so
188	<	* often, resizing is attempted only upon adding to a bin already
189	<	* holding two or more nodes. Under the default threshold (0.75),
190	<	* and uniform hash distributions, the probability of this
188	>	* often, resizing is normally attempted only upon adding to a bin
189	>	* already holding two or more nodes. Under the default threshold
190	>	* (0.75), and uniform hash distributions, the probability of this
191		* occurring at threshold is around 13%, meaning that only about 1
192		* in 8 puts check threshold (and after resizing, many fewer do
193	<	* so). To increase the probablity that a resize occurs soon
194	<	* enough, we offset the threshold (see THRESHOLD_OFFSET) by the
195	<	* expected number of puts between checks. This is currently set
196	<	* to 8, in accord with the default load factor. In practice, this
197	<	* is rarely overridden, and in any case is close enough to other
198	<	* plausible values not to waste dynamic probablity computation
193	>	* so). But this approximation has high variance for small table
194	>	* sizes, so we check on any collision for sizes <= 64.  Further,
195	>	* to increase the probability that a resize occurs soon enough, we
196	>	* offset the threshold (see THRESHOLD_OFFSET) by the expected
197	>	* number of puts between checks. This is currently set to 8, in
198	>	* accord with the default load factor. In practice, this is
199	>	* rarely overridden, and in any case is close enough to other
200	>	* plausible values not to waste dynamic probability computation
201		* for more precision.
202		*/
203
#	Line 212 | Line 217 | public class ConcurrentHashMapV8<K, V>
217
218		/**
219		* The default initial table capacity.  Must be a power of 2, at
220	<	* least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY
220	>	* least MINIMUM_CAPACITY and at most MAXIMUM_CAPACITY.
221		*/
222		static final int DEFAULT_CAPACITY = 16;
223
#	Line 229 | Line 234 | public class ConcurrentHashMapV8<K, V>
234		static final int DEFAULT_CONCURRENCY_LEVEL = 16;
235
236		/**
237	<	* The count value to offset thesholds to compensate for checking
237	>	* The count value to offset thresholds to compensate for checking
238		* for resizing only when inserting into bins with two or more
239		* elements. See above for explanation.
240		*/
#	Line 266 | Line 271 | public class ConcurrentHashMapV8<K, V>
271		transient Set<Map.Entry<K,V>> entrySet;
272		transient Collection<V> values;
273
274	<	/** For serialization compatability. Null unless serialized; see below */
274	>	/** For serialization compatibility. Null unless serialized; see below */
275		Segment<K,V>[] segments;
276
277		/**
#	Line 304 | Line 309 | public class ConcurrentHashMapV8<K, V>
309		}
310
311		/*
312	<	* Volatile access nethods are used for table elements as well as
312	>	* Volatile access methods are used for table elements as well as
313		* elements of in-progress next table while resizing.  Uses in
314		* access and update methods are null checked by callers, and
315		* implicitly bounds-checked, relying on the invariants that tab
316		* arrays have non-zero size, and all indices are masked with
317		* (tab.length - 1) which is never negative and always less than
318	<	* length. The only other usage is in HashIterator.advance, which
319	<	* performs explicit checks.
318	>	* length. The "relaxed" non-volatile forms are used only during
319	>	* table initialization. The only other usage is in
320	>	* HashIterator.advance, which performs explicit checks.
321		*/
322
323		static final Node tabAt(Node[] tab, int i) { // used in HashIterator
#	Line 326 | Line 332 | public class ConcurrentHashMapV8<K, V>
332		UNSAFE.putObjectVolatile(tab, ((long)i<<ASHIFT)+ABASE, v);
333		}
334
335	+	private static final Node relaxedTabAt(Node[] tab, int i) {
336	+	return (Node)UNSAFE.getObject(tab, ((long)i<<ASHIFT)+ABASE);
337	+	}
338	+
339	+	private static final void relaxedSetTabAt(Node[] tab, int i, Node v) {
340	+	UNSAFE.putObject(tab, ((long)i<<ASHIFT)+ABASE, v);
341	+	}
342	+
343		/* ---------------- Access and update operations -------------- */
344
345	<	/** Implements get and containsKey **/
345	>	/** Implementation for get and containsKey */
346		private final Object internalGet(Object k) {
347		int h = spread(k.hashCode());
348		Node[] tab = table;
#	Line 341 | Line 355 | public class ConcurrentHashMapV8<K, V>
355		if (ev != null && ek != null && (k == ek || k.equals(ek)))
356		return ev;
357		}
358	<	if (eh < 0) { // bin was moved during resize
358	>	else if (eh < 0) { // bin was moved during resize
359		tab = (Node[])e.key;
360		continue retry;
361		}
#	Line 352 | Line 366 | public class ConcurrentHashMapV8<K, V>
366		return null;
367		}
368
369	<	/** Implements put and putIfAbsent **/
369	>
370	>	/** Implementation for put and putIfAbsent */
371		private final Object internalPut(Object k, Object v, boolean replace) {
372		int h = spread(k.hashCode());
373		Object oldVal = null;  // the previous value or null if none
359	–	Node node = null;      // the node created if absent
374		Node[] tab = table;
375		for (;;) {
376		Node e; int i;
377		if (tab == null)
378		tab = grow(0);
379		else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
380	<	if (node == null)
367	<	node = new Node(h, k, v, null);
368	<	if (casTabAt(tab, i, null, node))
380	>	if (casTabAt(tab, i, null, new Node(h, k, v, null)))
381		break;
382		}
383		else if (e.hash < 0)
#	Line 373 | Line 385 | public class ConcurrentHashMapV8<K, V>
385		else {
386		boolean validated = false;
387		boolean checkSize = false;
388	<	synchronized(e) {
389	<	Node first = e;
390	<	for (;;) {
391	<	Object ek, ev;
392	<	if ((ev = e.val) == null)
393	<	break;
394	<	if (e.hash == h && (ek = e.key) != null &&
395	<	(k == ek || k.equals(ek))) {
396	<	if (tabAt(tab, i) == first) {
385	<	validated = true;
388	>	synchronized (e) {
389	>	if (tabAt(tab, i) == e) {
390	>	validated = true;
391	>	for (Node first = e;;) {
392	>	Object ek, ev;
393	>	if (e.hash == h &&
394	>	(ek = e.key) != null &&
395	>	(ev = e.val) != null &&
396	>	(k == ek || k.equals(ek))) {
397		oldVal = ev;
398		if (replace)
399		e.val = v;
400	+	break;
401		}
402	<	break;
403	<	}
404	<	Node last = e;
405	<	if ((e = e.next) == null) {
394	<	if (tabAt(tab, i) == first) {
395	<	validated = true;
396	<	if (node == null)
397	<	node = new Node(h, k, v, null);
398	<	last.next = node;
399	<	if (last != first)
402	>	Node last = e;
403	>	if ((e = e.next) == null) {
404	>	last.next = new Node(h, k, v, null);
405	>	if (last != first || tab.length <= 64)
406		checkSize = true;
407	+	break;
408		}
402	–	break;
409		}
410		}
411		}
#	Line 417 | Line 423 | public class ConcurrentHashMapV8<K, V>
423		}
424
425		/**
426	<	* Covers the four public remove/replace methods: Replaces node
427	<	* value with v, conditional upon match of cv if non-null.  If
428	<	* resulting value is null, delete.
426	>	* Implementation for the four public remove/replace methods:
427	>	* Replaces node value with v, conditional upon match of cv if
428	>	* non-null.  If resulting value is null, delete.
429		*/
430		private final Object internalReplace(Object k, Object v, Object cv) {
431		int h = spread(k.hashCode());
#	Line 433 | Line 439 | public class ConcurrentHashMapV8<K, V>
439		else {
440		boolean validated = false;
441		boolean deleted = false;
442	<	synchronized(e) {
443	<	Node pred = null;
444	<	Node first = e;
445	<	for (;;) {
446	<	Object ek, ev;
447	<	if ((ev = e.val) == null)
448	<	break;
449	<	if (e.hash == h && (ek = e.key) != null &&
450	<	(k == ek || k.equals(ek))) {
451	<	if (tabAt(tab, i) == first) {
446	<	validated = true;
442	>	synchronized (e) {
443	>	if (tabAt(tab, i) == e) {
444	>	validated = true;
445	>	Node pred = null;
446	>	do {
447	>	Object ek, ev;
448	>	if (e.hash == h &&
449	>	(ek = e.key) != null &&
450	>	(ev = e.val) != null &&
451	>	(k == ek || k.equals(ek))) {
452		if (cv == null || cv == ev || cv.equals(ev)) {
453		oldVal = ev;
454		if ((e.val = v) == null) {
#	Line 455 | Line 460 | public class ConcurrentHashMapV8<K, V>
460		setTabAt(tab, i, en);
461		}
462		}
463	+	break;
464		}
465	<	break;
466	<	}
461	<	pred = e;
462	<	if ((e = e.next) == null) {
463	<	if (tabAt(tab, i) == first)
464	<	validated = true;
465	<	break;
466	<	}
465	>	pred = e;
466	>	} while ((e = e.next) != null);
467		}
468		}
469		if (validated) {
#	Line 476 | Line 476 | public class ConcurrentHashMapV8<K, V>
476		return oldVal;
477		}
478
479	<	/** Implements computeIfAbsent */
479	>	/** Implementation for computeIfAbsent and compute */
480		@SuppressWarnings("unchecked")
481	<	private final V computeVal(K k, MappingFunction<? super K, ? extends V> f) {
481	>	private final V internalCompute(K k,
482	>	MappingFunction<? super K, ? extends V> f,
483	>	boolean replace) {
484		int h = spread(k.hashCode());
485		V val = null;
484	–	Node node = null;
486		boolean added = false;
486	–	boolean validated = false;
487		Node[] tab = table;
488	<	do {
488	>	for (;;) {
489		Node e; int i;
490		if (tab == null)
491		tab = grow(0);
492		else if ((e = tabAt(tab, i = (tab.length - 1) & h)) == null) {
493	<	if (node == null)
494	<	node = new Node(h, k, null, null);
495	<	synchronized(node) {
493	>	Node node = new Node(h, k, null, null);
494	>	boolean validated = false;
495	>	synchronized (node) {
496		if (casTabAt(tab, i, null, node)) {
497		validated = true;
498		try {
#	Line 507 | Line 507 | public class ConcurrentHashMapV8<K, V>
507		}
508		}
509		}
510	+	if (validated)
511	+	break;
512		}
513		else if (e.hash < 0)
514		tab = (Node[])e.key;
515	+	else if (Thread.holdsLock(e))
516	+	throw new IllegalStateException("Recursive map computation");
517		else {
518	+	boolean validated = false;
519		boolean checkSize = false;
520	<	synchronized(e) {
521	<	Node first = e;
522	<	for (;;) {
523	<	Object ek, ev;
524	<	if ((ev = e.val) == null)
525	<	break;
526	<	if (e.hash == h && (ek = e.key) != null &&
527	<	(k == ek || k.equals(ek))) {
528	<	if (tabAt(tab, i) == first) {
529	<	validated = true;
520	>	synchronized (e) {
521	>	if (tabAt(tab, i) == e) {
522	>	validated = true;
523	>	for (Node first = e;;) {
524	>	Object ek, ev, fv;
525	>	if (e.hash == h &&
526	>	(ek = e.key) != null &&
527	>	(ev = e.val) != null &&
528	>	(k == ek || k.equals(ek))) {
529	>	if (replace && (fv = f.map(k)) != null)
530	>	ev = e.val = fv;
531		val = (V)ev;
532	+	break;
533		}
534	<	break;
535	<	}
529	<	Node last = e;
530	<	if ((e = e.next) == null) {
531	<	if (tabAt(tab, i) == first) {
532	<	validated = true;
534	>	Node last = e;
535	>	if ((e = e.next) == null) {
536		if ((val = f.map(k)) != null) {
537	<	if (node == null)
535	<	node = new Node(h, k, val, null);
536	<	else
537	<	node.val = val;
538	<	last.next = node;
539	<	if (last != first)
540	<	checkSize = true;
537	>	last.next = new Node(h, k, val, null);
538		added = true;
539	+	if (last != first || tab.length <= 64)
540	+	checkSize = true;
541		}
542	+	break;
543		}
544	–	break;
544		}
545		}
546		}
547	<	if (checkSize && tab.length < MAXIMUM_CAPACITY &&
548	<	resizing == 0 && counter.sum() >= threshold)
549	<	grow(0);
547	>	if (validated) {
548	>	if (checkSize && tab.length < MAXIMUM_CAPACITY &&
549	>	resizing == 0 && counter.sum() >= threshold)
550	>	grow(0);
551	>	break;
552	>	}
553		}
554	<	} while (!validated);
554	>	}
555		if (added)
556		counter.increment();
557		return val;
#	Line 582 | Line 584 | public class ConcurrentHashMapV8<K, V>
584		break;
585		}
586		else {
587	+	int idx = e.hash & mask;
588		boolean validated = false;
589	<	synchronized(e) {
587	<	int idx = e.hash & mask;
588	<	Node lastRun = e;
589	<	for (Node p = e.next; p != null; p = p.next) {
590	<	int j = p.hash & mask;
591	<	if (j != idx) {
592	<	idx = j;
593	<	lastRun = p;
594	<	}
595	<	}
589	>	synchronized (e) {
590		if (tabAt(tab, i) == e) {
591		validated = true;
592	<	setTabAt(nextTab, idx, lastRun);
592	>	Node lastRun = e;
593	>	for (Node p = e.next; p != null; p = p.next) {
594	>	int j = p.hash & mask;
595	>	if (j != idx) {
596	>	idx = j;
597	>	lastRun = p;
598	>	}
599	>	}
600	>	relaxedSetTabAt(nextTab, idx, lastRun);
601		for (Node p = e; p != lastRun; p = p.next) {
602		int h = p.hash;
603		int j = h & mask;
604	<	Object pk = p.key, pv = p.val;
605	<	Node r = tabAt(nextTab, j);
606	<	setTabAt(nextTab, j, new Node(h, pk, pv, r));
604	>	Node r = relaxedTabAt(nextTab, j);
605	>	relaxedSetTabAt(nextTab, j,
606	>	new Node(h, p.key, p.val, r));
607		}
608		setTabAt(tab, i, fwd);
609		}
#	Line 623 | Line 625 | public class ConcurrentHashMapV8<K, V>
625		* @return current table
626		*/
627		private final Node[] grow(int sizeHint) {
626	–	Node[] tab;
628		if (resizing == 0 &&
629		UNSAFE.compareAndSwapInt(this, resizingOffset, 0, 1)) {
630		try {
631		for (;;) {
632		int cap, n;
633	<	if ((tab = table) == null) {
633	>	Node[] tab = table;
634	>	if (tab == null) {
635		int c = initCap;
636		if (c < sizeHint)
637		c = sizeHint;
#	Line 653 | Line 655 | public class ConcurrentHashMapV8<K, V>
655		if (tab != null)
656		transfer(tab, nextTab);
657		table = nextTab;
658	<	if (tab == null || counter.sum() < threshold) {
659	<	tab = nextTab;
658	>	if (tab == null || cap >= MAXIMUM_CAPACITY ||
659	>	((sizeHint > 0) ? cap >= sizeHint :
660	>	counter.sum() < threshold))
661		break;
659	–	}
662		}
663		} finally {
664		resizing = 0;
665		}
666		}
667	<	else if ((tab = table) == null)
667	>	else if (table == null)
668		Thread.yield(); // lost initialization race; just spin
669	<	return tab;
669	>	return table;
670		}
671
672		/**
673	<	* Implements putAll and constructor with Map argument. Tries to
674	<	* first override initial capacity or grow (once) based on map
675	<	* size to pre-allocate table space.
673	>	* Implementation for putAll and constructor with Map
674	>	* argument. Tries to first override initial capacity or grow
675	>	* based on map size to pre-allocate table space.
676		*/
677		private final void internalPutAll(Map<? extends K, ? extends V> m) {
678		int s = m.size();
679	<	grow((s >= (MAXIMUM_CAPACITY >>> 1))? s : s + (s >>> 1));
679	>	grow((s >= (MAXIMUM_CAPACITY >>> 1)) ? s : s + (s >>> 1));
680		for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
681		Object k = e.getKey();
682		Object v = e.getValue();
#	Line 685 | Line 687 | public class ConcurrentHashMapV8<K, V>
687		}
688
689		/**
690	<	* Implements clear. Steps through each bin, removing all nodes.
690	>	* Implementation for clear. Steps through each bin, removing all nodes.
691		*/
692		private final void internalClear() {
693	<	long delta = 0L; // negative of number of deletions
693	>	long deletions = 0L;
694		int i = 0;
695		Node[] tab = table;
696		while (tab != null && i < tab.length) {
#	Line 699 | Line 701 | public class ConcurrentHashMapV8<K, V>
701		tab = (Node[])e.key;
702		else {
703		boolean validated = false;
704	<	synchronized(e) {
704	>	synchronized (e) {
705		if (tabAt(tab, i) == e) {
706		validated = true;
707		do {
708		if (e.val != null) {
709		e.val = null;
710	<	--delta;
710	>	++deletions;
711		}
712		} while ((e = e.next) != null);
713		setTabAt(tab, i, null);
714		}
715		}
716	<	if (validated)
716	>	if (validated) {
717		++i;
718	+	if (deletions > THRESHOLD_OFFSET) { // bound lag in counts
719	+	counter.add(-deletions);
720	+	deletions = 0L;
721	+	}
722	+	}
723		}
724		}
725	<	counter.add(delta);
725	>	if (deletions != 0L)
726	>	counter.add(-deletions);
727		}
728
729		/**
#	Line 894 | Line 902 | public class ConcurrentHashMapV8<K, V>
902		* nonpositive.
903		*/
904		public ConcurrentHashMapV8(int initialCapacity,
905	<	float loadFactor, int concurrencyLevel) {
905	>	float loadFactor, int concurrencyLevel) {
906		if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
907		throw new IllegalArgumentException();
908		this.initCap = initialCapacity;
#	Line 962 | Line 970 | public class ConcurrentHashMapV8<K, V>
970		* @return {@code true} if this map contains no key-value mappings
971		*/
972		public boolean isEmpty() {
973	<	return counter.sum() == 0L;
973	>	return counter.sum() <= 0L; // ignore transient negative values
974		}
975
976		/**
#	Line 974 | Line 982 | public class ConcurrentHashMapV8<K, V>
982		*/
983		public int size() {
984		long n = counter.sum();
985	<	return n >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)n;
985	>	return ((n >>> 31) == 0) ? (int)n : (n < 0L) ? 0 : Integer.MAX_VALUE;
986		}
987
988		/**
#	Line 1103 | Line 1111 | public class ConcurrentHashMapV8<K, V>
1111		*       return map.get(key);
1112		*   value = mappingFunction.map(key);
1113		*   if (value != null)
1114	<	*      return map.put(key, value);
1115	<	*   else
1108	<	*      return null;
1114	>	*      map.put(key, value);
1115	>	*   return value;
1116		* </pre>
1117		*
1118		* except that the action is performed atomically.  Some attempted
1119	<	* operations on this map by other threads may be blocked while
1120	<	* computation is in progress. Because this function is invoked
1121	<	* within atomicity control, the computation should be short and
1122	<	* simple, and must not attempt to update any other mappings of
1123	<	* this Map. The most common usage is to construct a new object
1124	<	* serving as an initial mapped value, or memoized result.
1119	>	* update operations on this map by other threads may be blocked
1120	>	* while computation is in progress, so the computation should be
1121	>	* short and simple, and must not attempt to update any other
1122	>	* mappings of this Map. The most appropriate usage is to
1123	>	* construct a new object serving as an initial mapped value, or
1124	>	* memoized result, as in:
1125	>	* <pre>{@code
1126	>	* map.computeIfAbsent(key, new MappingFunction<K, V>() {
1127	>	*   public V map(K k) { return new Value(f(k)); }};
1128	>	* }</pre>
1129		*
1130		* @param key key with which the specified value is to be associated
1131		* @param mappingFunction the function to compute a value
#	Line 1123 | Line 1134 | public class ConcurrentHashMapV8<K, V>
1134		*         returned {@code null}.
1135		* @throws NullPointerException if the specified key or mappingFunction
1136		*         is null,
1137	+	* @throws IllegalStateException if the computation detectably
1138	+	*         attempts a recursive update to this map that would
1139	+	*         otherwise never complete.
1140		* @throws RuntimeException or Error if the mappingFunction does so,
1141		*         in which case the mapping is left unestablished.
1142		*/
1143		public V computeIfAbsent(K key, MappingFunction<? super K, ? extends V> mappingFunction) {
1144		if (key == null || mappingFunction == null)
1145		throw new NullPointerException();
1146	<	return computeVal(key, mappingFunction);
1146	>	return internalCompute(key, mappingFunction, false);
1147	>	}
1148	>
1149	>	/**
1150	>	* Computes the value associated with the given key using the given
1151	>	* mappingFunction, and if non-null, enters it into the map.  This
1152	>	* is equivalent to
1153	>	*
1154	>	* <pre>
1155	>	*   value = mappingFunction.map(key);
1156	>	*   if (value != null)
1157	>	*      map.put(key, value);
1158	>	*   else
1159	>	*      value = map.get(key);
1160	>	*   return value;
1161	>	* </pre>
1162	>	*
1163	>	* except that the action is performed atomically.  Some attempted
1164	>	* update operations on this map by other threads may be blocked
1165	>	* while computation is in progress, so the computation should be
1166	>	* short and simple, and must not attempt to update any other
1167	>	* mappings of this Map.
1168	>	*
1169	>	* @param key key with which the specified value is to be associated
1170	>	* @param mappingFunction the function to compute a value
1171	>	* @return the current value associated with
1172	>	*         the specified key, or {@code null} if the computation
1173	>	*         returned {@code null} and the value was not otherwise present.
1174	>	* @throws NullPointerException if the specified key or mappingFunction
1175	>	*         is null,
1176	>	* @throws IllegalStateException if the computation detectably
1177	>	*         attempts a recursive update to this map that would
1178	>	*         otherwise never complete.
1179	>	* @throws RuntimeException or Error if the mappingFunction does so,
1180	>	*         in which case the mapping is unchanged.
1181	>	*/
1182	>	public V compute(K key, MappingFunction<? super K, ? extends V> mappingFunction) {
1183	>	if (key == null || mappingFunction == null)
1184	>	throw new NullPointerException();
1185	>	return internalCompute(key, mappingFunction, true);
1186		}
1187
1188		/**
#	Line 1145 | Line 1198 | public class ConcurrentHashMapV8<K, V>
1198		public V remove(Object key) {
1199		if (key == null)
1200		throw new NullPointerException();
1201	<	return (V)internalReplace(key, null, null);
1201	>	return (V)internalReplace(key, null, null);
1202		}
1203
1204		/**
#	Line 1169 | Line 1222 | public class ConcurrentHashMapV8<K, V>
1222		public boolean replace(K key, V oldValue, V newValue) {
1223		if (key == null || oldValue == null || newValue == null)
1224		throw new NullPointerException();
1225	<	return internalReplace(key, newValue, oldValue) != null;
1225	>	return internalReplace(key, newValue, oldValue) != null;
1226		}
1227
1228		/**
#	Line 1183 | Line 1236 | public class ConcurrentHashMapV8<K, V>
1236		public V replace(K key, V value) {
1237		if (key == null || value == null)
1238		throw new NullPointerException();
1239	<	return (V)internalReplace(key, value, null);
1239	>	return (V)internalReplace(key, value, null);
1240		}
1241
1242		/**
#	Line 1277 | Line 1330 | public class ConcurrentHashMapV8<K, V>
1330		}
1331
1332		/**
1333	<	* {@inheritDoc}
1333	>	* Returns the hash code value for this {@link Map}, i.e.,
1334	>	* the sum of, for each key-value pair in the map,
1335	>	* {@code key.hashCode() ^ value.hashCode()}.
1336	>	*
1337	>	* @return the hash code value for this map
1338		*/
1339		public int hashCode() {
1340		return new HashIterator().mapHashCode();
1341		}
1342
1343		/**
1344	<	* {@inheritDoc}
1344	>	* Returns a string representation of this map.  The string
1345	>	* representation consists of a list of key-value mappings (in no
1346	>	* particular order) enclosed in braces ("{@code {}}").  Adjacent
1347	>	* mappings are separated by the characters {@code ", "} (comma
1348	>	* and space).  Each key-value mapping is rendered as the key
1349	>	* followed by an equals sign ("{@code =}") followed by the
1350	>	* associated value.
1351	>	*
1352	>	* @return a string representation of this map
1353		*/
1354		public String toString() {
1355		return new HashIterator().mapToString();
1356		}
1357
1358		/**
1359	<	* {@inheritDoc}
1359	>	* Compares the specified object with this map for equality.
1360	>	* Returns {@code true} if the given object is a map with the same
1361	>	* mappings as this map.  This operation may return misleading
1362	>	* results if either map is concurrently modified during execution
1363	>	* of this method.
1364	>	*
1365	>	* @param o object to be compared for equality with this map
1366	>	* @return {@code true} if the specified object is equal to this map
1367		*/
1368		public boolean equals(Object o) {
1369		if (o == this)
#	Line 1471 | Line 1543 | public class ConcurrentHashMapV8<K, V>
1543		}
1544
1545		/**
1546	<	* Reconstitutes the  instance from a
1475	<	* stream (i.e., deserializes it).
1546	>	* Reconstitutes the instance from a stream (that is, deserializes it).
1547		* @param s the stream
1548		*/
1549		@SuppressWarnings("unchecked")

Diff Legend

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