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.9 by jsr166, Tue Aug 30 14:55:58 2011 UTC vs.
Revision 1.10 by dl, Tue Aug 30 16:03:48 2011 UTC

#	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
#	Line 342 | Line 342 | public class ConcurrentHashMapV8<K, V>
342
343		/* ---------------- Access and update operations -------------- */
344
345	<	/** Implementation for 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 366 | Line 366 | public class ConcurrentHashMapV8<K, V>
366		return null;
367		}
368
369	<	/** Implementation for 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
#	Line 385 | Line 386 | public class ConcurrentHashMapV8<K, V>
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) {
396	<	validated = true;
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	<	}
403	<	Node last = e;
404	<	if ((e = e.next) == null) {
405	<	if (tabAt(tab, i) == first) {
406	<	validated = true;
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		}
411	–	break;
409		}
410		}
411		}
#	Line 426 | 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 443 | Line 440 | public class ConcurrentHashMapV8<K, V>
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) {
455	<	validated = true;
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 464 | Line 460 | public class ConcurrentHashMapV8<K, V>
460		setTabAt(tab, i, en);
461		}
462		}
463	+	break;
464		}
465	<	break;
466	<	}
470	<	pred = e;
471	<	if ((e = e.next) == null) {
472	<	if (tabAt(tab, i) == first)
473	<	validated = true;
474	<	break;
475	<	}
465	>	pred = e;
466	>	} while ((e = e.next) != null);
467		}
468		}
469		if (validated) {
#	Line 493 | Line 484 | public class ConcurrentHashMapV8<K, V>
484		int h = spread(k.hashCode());
485		V val = null;
486		boolean added = false;
496	–	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		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;
#	Line 516 | 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;
530	<	if (replace && (ev = f.map(k)) != null)
537	<	e.val = ev;
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	<	}
542	<	Node last = e;
543	<	if ((e = e.next) == null) {
544	<	if (tabAt(tab, i) == first) {
545	<	validated = true;
534	>	Node last = e;
535	>	if ((e = e.next) == null) {
536		if ((val = f.map(k)) != null) {
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		}
553	–	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 591 | 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) {
596	–	int idx = e.hash & mask;
597	–	Node lastRun = e;
598	–	for (Node p = e.next; p != null; p = p.next) {
599	–	int j = p.hash & mask;
600	–	if (j != idx) {
601	–	idx = j;
602	–	lastRun = p;
603	–	}
604	–	}
590		if (tabAt(tab, i) == e) {
591		validated = true;
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;
#	Line 663 | Line 656 | public class ConcurrentHashMapV8<K, V>
656		transfer(tab, nextTab);
657		table = nextTab;
658		if (tab == null || cap >= MAXIMUM_CAPACITY ||
659	<	(sizeHint > 0 && cap >= sizeHint) ||
660	<	counter.sum() < threshold)
659	>	((sizeHint > 0) ? cap >= sizeHint :
660	>	counter.sum() < threshold))
661		break;
662		}
663		} finally {

Diff Legend

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