ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/main/java/util/concurrent/LinkedTransferQueue.java

Comparing jsr166/src/main/java/util/concurrent/LinkedTransferQueue.java (file contents):
Revision 1.133 by jsr166, Mon Jan 2 00:10:14 2017 UTC vs.
Revision 1.134 by jsr166, Mon Jan 2 04:41:13 2017 UTC

#	Line 895 | Line 895 | public class LinkedTransferQueue<E> exte
895		return (T[]) toArrayInternal(a);
896		}
897
898	+	/**
899	+	* Weakly-consistent iterator.
900	+	*
901	+	* Lazily updated ancestor is expected to be amortized O(1) remove(),
902	+	* but O(n) in the worst case, when lastRet is concurrently deleted.
903	+	*/
904		final class Itr implements Iterator<E> {
905		private Node nextNode;   // next node to return item for
906		private E nextItem;      // the corresponding item
907		private Node lastRet;    // last returned node, to support remove
908	<	private Node lastPred;   // predecessor to unlink lastRet
908	>	private Node ancestor;   // Helps unlink lastRet on remove()
909
910		/**
911	<	* Moves to next node after prev, or first node if prev null.
911	>	* Moves to next node after pred, or first node if pred null.
912		*/
913	<	private void advance(Node prev) {
914	<	/*
915	<	* To track and avoid buildup of deleted nodes in the face
916	<	* of calls to both Queue.remove and Itr.remove, we must
917	<	* include variants of unsplice and sweep upon each
918	<	* advance: Upon Itr.remove, we may need to catch up links
919	<	* from lastPred, and upon other removes, we might need to
920	<	* skip ahead from stale nodes and unsplice deleted ones
921	<	* found while advancing.
922	<	*/
923	<
924	<	Node r, b; // reset lastPred upon possible deletion of lastRet
925	<	if ((r = lastRet) != null && !r.isMatched())
920	<	lastPred = r;    // next lastPred is old lastRet
921	<	else if ((b = lastPred) == null || b.isMatched())
922	<	lastPred = null; // at start of list
923	<	else {
924	<	Node s, n;       // help with removal of lastPred.next
925	<	while ((s = b.next) != null &&
926	<	s != b && s.isMatched() &&
927	<	(n = s.next) != null && n != s)
928	<	b.casNext(s, n);
929	<	}
930	<
931	<	this.lastRet = prev;
932	<
933	<	for (Node p = prev, s, n;;) {
934	<	s = (p == null) ? head : p.next;
935	<	if (s == null)
913	>	@SuppressWarnings("unchecked")
914	>	private void advance(Node pred) {
915	>	for (Node p = (pred == null) ? head : pred.next, c = p;
916	>	p != null; ) {
917	>	final Object item;
918	>	if ((item = p.item) != null && p.isData) {
919	>	nextNode = p;
920	>	nextItem = (E) item;
921	>	if (c != p)
922	>	tryCasSuccessor(pred, c, p);
923	>	return;
924	>	}
925	>	else if (!p.isData && item == null)
926		break;
927	<	else if (s == p) {
928	<	p = null;
929	<	continue;
927	>	if (c != p && !tryCasSuccessor(pred, c, c = p)) {
928	>	pred = p;
929	>	c = p = p.next;
930		}
931	<	Object item = s.item;
932	<	if (s.isData) {
933	<	if (item != null) {
944	<	@SuppressWarnings("unchecked") E itemE = (E) item;
945	<	nextItem = itemE;
946	<	nextNode = s;
947	<	return;
948	<	}
931	>	else if (p == (p = p.next)) {
932	>	pred = null;
933	>	c = p = head;
934		}
950	–	else if (item == null)
951	–	break;
952	–	// assert s.isMatched();
953	–	if (p == null)
954	–	p = s;
955	–	else if ((n = s.next) == null)
956	–	break;
957	–	else if (s == n)
958	–	p = null;
959	–	else
960	–	p.casNext(s, n);
935		}
962	–	nextNode = null;
936		nextItem = null;
937	+	nextNode = null;
938		}
939
940		Itr() {
#	Line 975 | Line 949 | public class LinkedTransferQueue<E> exte
949		final Node p;
950		if ((p = nextNode) == null) throw new NoSuchElementException();
951		E e = nextItem;
952	<	advance(p);
952	>	advance(lastRet = p);
953		return e;
954		}
955
956	<	// Default implementation of forEachRemaining is "good enough".
956	>	public void forEachRemaining(Consumer<? super E> action) {
957	>	Objects.requireNonNull(action);
958	>	Node q = null;
959	>	for (Node p; (p = nextNode) != null; advance(q = p))
960	>	action.accept(nextItem);
961	>	if (q != null)
962	>	lastRet = q;
963	>	}
964
965		public final void remove() {
966		final Node lastRet = this.lastRet;
967		if (lastRet == null)
968		throw new IllegalStateException();
969		this.lastRet = null;
970	<	if (lastRet.tryMatchData())
971	<	unsplice(lastPred, lastRet);
970	>	if (lastRet.item == null)   // already deleted?
971	>	return;
972	>	// Advance ancestor, collapsing intervening dead nodes
973	>	Node pred = ancestor;
974	>	for (Node p = (pred == null) ? head : pred.next, c = p, q;
975	>	p != null; ) {
976	>	if (p == lastRet) {
977	>	p.tryMatchData();
978	>	if ((q = p.next) == null) q = p;
979	>	if (c != q) tryCasSuccessor(pred, c, q);
980	>	ancestor = pred;
981	>	return;
982	>	}
983	>	final Object item; final boolean pAlive;
984	>	if (pAlive = ((item = p.item) != null && p.isData)) {
985	>	// exceptionally, nothing to do
986	>	}
987	>	else if (!p.isData && item == null)
988	>	break;
989	>	if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
990	>	pred = p;
991	>	c = p = p.next;
992	>	}
993	>	else if (p == (p = p.next)) {
994	>	pred = null;
995	>	c = p = head;
996	>	}
997	>	}
998	>	// traversal failed to find lastRet; must have been deleted;
999	>	// leave ancestor at original location to avoid overshoot;
1000	>	// better luck next time!
1001	>
1002	>	// assert lastRet.isMatched();
1003		}
1004		}
1005
#	Line 1451 | Line 1463 | public class LinkedTransferQueue<E> exte
1463		}
1464		else if (!p.isData && item == null)
1465		break;
1466	<	if (c != p && tryCasSuccessor(pred, c, p))
1455	<	c = p;
1456	<	q = p.next;
1457	<	if (pAlive || c != p) {
1466	>	if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
1467		pred = p;
1468	<	p = c = q;
1468	>	c = p = p.next;
1469		}
1470	<	else if (p == (p = q))
1470	>	else if (p == (p = p.next))
1471		continue restartFromHead;
1472		}
1473		return false;
#	Line 1477 | Line 1486 | public class LinkedTransferQueue<E> exte
1486		if (o == null)
1487		return false;
1488		restartFromHead: for (;;) {
1489	<	for (Node p = head, c = p, pred = null, q; p != null; ) {
1489	>	for (Node p = head, c = p, pred = null; p != null; ) {
1490		final Object item; final boolean pAlive;
1491		if (pAlive = ((item = p.item) != null && p.isData)) {
1492		if (o.equals(item))
#	Line 1485 | Line 1494 | public class LinkedTransferQueue<E> exte
1494		}
1495		else if (!p.isData && item == null)
1496		break;
1497	<	if (c != p && tryCasSuccessor(pred, c, p))
1489	<	c = p;
1490	<	q = p.next;
1491	<	if (pAlive || c != p) {
1497	>	if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
1498		pred = p;
1499	<	p = c = q;
1499	>	c = p = p.next;
1500		}
1501	<	else if (p == (p = q))
1501	>	else if (p == (p = p.next))
1502		continue restartFromHead;
1503		}
1504		return false;
#	Line 1605 | Line 1611 | public class LinkedTransferQueue<E> exte
1611		// p might already be self-linked here, but if so:
1612		// - CASing head will surely fail
1613		// - CASing pred's next will be useless but harmless.
1614	<	if (c != p && tryCasSuccessor(pred, c, p))
1615	<	c = p;
1616	<	// if c != p, CAS failed, so abandon old pred
1611	<	if (pAlive || c != p) {
1614	>	if ((c != p && !tryCasSuccessor(pred, c, c = p))
1615	>	|| pAlive) {
1616	>	// if CAS failed or alive, abandon old pred
1617		hops = MAX_HOPS;
1618		pred = p;
1619		c = q;
#	Line 1626 | Line 1631 | public class LinkedTransferQueue<E> exte
1631		*/
1632		@SuppressWarnings("unchecked")
1633		void forEachFrom(Consumer<? super E> action, Node p) {
1634	<	for (Node c = p, pred = null, q; p != null; ) {
1634	>	for (Node c = p, pred = null; p != null; ) {
1635		final Object item; final boolean pAlive;
1636		if (pAlive = ((item = p.item) != null && p.isData))
1637		action.accept((E) item);
1638		else if (!p.isData && item == null)
1639		break;
1640	<	if (c != p && tryCasSuccessor(pred, c, p))
1636	<	c = p;
1637	<	q = p.next;
1638	<	if (pAlive || c != p) {
1640	>	if ((c != p && !tryCasSuccessor(pred, c, c = p)) || pAlive) {
1641		pred = p;
1642	<	p = c = q;
1642	>	c = p = p.next;
1643		}
1644	<	else if (p == (p = q)) {
1644	>	else if (p == (p = p.next)) {
1645		pred = null;
1646		c = p = head;
1647		}

Diff Legend

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