ViewVC Help

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

root/jsr166/jsr166/src/jdk8/java/util/concurrent/LinkedBlockingDeque.java

Comparing jsr166/src/jdk8/java/util/concurrent/LinkedBlockingDeque.java (file contents):
Revision 1.2 by jsr166, Tue Nov 15 23:40:01 2016 UTC vs.
Revision 1.3 by jsr166, Sat Dec 17 21:56:54 2016 UTC

#	Line 10 | Line 10 | import java.util.AbstractQueue;
10		import java.util.Collection;
11		import java.util.Iterator;
12		import java.util.NoSuchElementException;
13	+	import java.util.Objects;
14		import java.util.Spliterator;
15		import java.util.Spliterators;
16		import java.util.concurrent.locks.Condition;
#	Line 175 | Line 176 | public class LinkedBlockingDeque<E>
176		throw new IllegalStateException("Deque full");
177		}
178		} finally {
179	+	// checkInvariants();
180		lock.unlock();
181		}
182		}
#	Line 317 | Line 319 | public class LinkedBlockingDeque<E>
319		try {
320		return linkFirst(node);
321		} finally {
322	+	// checkInvariants();
323		lock.unlock();
324		}
325		}
#	Line 332 | Line 335 | public class LinkedBlockingDeque<E>
335		try {
336		return linkLast(node);
337		} finally {
338	+	// checkInvariants();
339		lock.unlock();
340		}
341		}
#	Line 349 | Line 353 | public class LinkedBlockingDeque<E>
353		while (!linkFirst(node))
354		notFull.await();
355		} finally {
356	+	// checkInvariants();
357		lock.unlock();
358		}
359		}
#	Line 366 | Line 371 | public class LinkedBlockingDeque<E>
371		while (!linkLast(node))
372		notFull.await();
373		} finally {
374	+	// checkInvariants();
375		lock.unlock();
376		}
377		}
#	Line 389 | Line 395 | public class LinkedBlockingDeque<E>
395		}
396		return true;
397		} finally {
398	+	// checkInvariants();
399		lock.unlock();
400		}
401		}
#	Line 412 | Line 419 | public class LinkedBlockingDeque<E>
419		}
420		return true;
421		} finally {
422	+	// checkInvariants();
423		lock.unlock();
424		}
425		}
#	Line 440 | Line 448 | public class LinkedBlockingDeque<E>
448		try {
449		return unlinkFirst();
450		} finally {
451	+	// checkInvariants();
452		lock.unlock();
453		}
454		}
#	Line 450 | Line 459 | public class LinkedBlockingDeque<E>
459		try {
460		return unlinkLast();
461		} finally {
462	+	// checkInvariants();
463		lock.unlock();
464		}
465		}
#	Line 463 | Line 473 | public class LinkedBlockingDeque<E>
473		notEmpty.await();
474		return x;
475		} finally {
476	+	// checkInvariants();
477		lock.unlock();
478		}
479		}
#	Line 476 | Line 487 | public class LinkedBlockingDeque<E>
487		notEmpty.await();
488		return x;
489		} finally {
490	+	// checkInvariants();
491		lock.unlock();
492		}
493		}
#	Line 494 | Line 506 | public class LinkedBlockingDeque<E>
506		}
507		return x;
508		} finally {
509	+	// checkInvariants();
510		lock.unlock();
511		}
512		}
#	Line 512 | Line 525 | public class LinkedBlockingDeque<E>
525		}
526		return x;
527		} finally {
528	+	// checkInvariants();
529		lock.unlock();
530		}
531		}
#	Line 540 | Line 554 | public class LinkedBlockingDeque<E>
554		try {
555		return (first == null) ? null : first.item;
556		} finally {
557	+	// checkInvariants();
558		lock.unlock();
559		}
560		}
#	Line 550 | Line 565 | public class LinkedBlockingDeque<E>
565		try {
566		return (last == null) ? null : last.item;
567		} finally {
568	+	// checkInvariants();
569		lock.unlock();
570		}
571		}
#	Line 567 | Line 583 | public class LinkedBlockingDeque<E>
583		}
584		return false;
585		} finally {
586	+	// checkInvariants();
587		lock.unlock();
588		}
589		}
#	Line 584 | Line 601 | public class LinkedBlockingDeque<E>
601		}
602		return false;
603		} finally {
604	+	// checkInvariants();
605		lock.unlock();
606		}
607		}
#	Line 690 | Line 708 | public class LinkedBlockingDeque<E>
708		try {
709		return capacity - count;
710		} finally {
711	+	// checkInvariants();
712		lock.unlock();
713		}
714		}
#	Line 711 | Line 730 | public class LinkedBlockingDeque<E>
730		* @throws IllegalArgumentException      {@inheritDoc}
731		*/
732		public int drainTo(Collection<? super E> c, int maxElements) {
733	<	if (c == null)
715	<	throw new NullPointerException();
733	>	Objects.requireNonNull(c);
734		if (c == this)
735		throw new IllegalArgumentException();
736		if (maxElements <= 0)
#	Line 727 | Line 745 | public class LinkedBlockingDeque<E>
745		}
746		return n;
747		} finally {
748	+	// checkInvariants();
749		lock.unlock();
750		}
751		}
#	Line 779 | Line 798 | public class LinkedBlockingDeque<E>
798		try {
799		return count;
800		} finally {
801	+	// checkInvariants();
802		lock.unlock();
803		}
804		}
#	Line 801 | Line 821 | public class LinkedBlockingDeque<E>
821		return true;
822		return false;
823		} finally {
824	+	// checkInvariants();
825		lock.unlock();
826		}
827		}
#	Line 870 | Line 891 | public class LinkedBlockingDeque<E>
891		a[k++] = p.item;
892		return a;
893		} finally {
894	+	// checkInvariants();
895		lock.unlock();
896		}
897		}
#	Line 925 | Line 947 | public class LinkedBlockingDeque<E>
947		a[k] = null;
948		return a;
949		} finally {
950	+	// checkInvariants();
951		lock.unlock();
952		}
953		}
#	Line 952 | Line 975 | public class LinkedBlockingDeque<E>
975		count = 0;
976		notFull.signalAll();
977		} finally {
978	+	// checkInvariants();
979		lock.unlock();
980		}
981		}
982
983		/**
984	+	* Used for any element traversal that is not entirely under lock.
985	+	* Such traversals must handle both:
986	+	* - dequeued nodes (p.next == p)
987	+	* - (possibly multiple) interior removed nodes (p.item == null)
988	+	*/
989	+	Node<E> succ(Node<E> p) {
990	+	return (p == (p = p.next)) ? first : p;
991	+	}
992	+
993	+	/**
994		* Returns an iterator over the elements in this deque in proper sequence.
995		* The elements will be returned in order from first (head) to last (tail).
996		*
#	Line 995 | Line 1029 | public class LinkedBlockingDeque<E>
1029		/**
1030		* nextItem holds on to item fields because once we claim that
1031		* an element exists in hasNext(), we must return item read
1032	<	* under lock (in advance()) even if it was in the process of
1033	<	* being removed when hasNext() was called.
1032	>	* under lock even if it was in the process of being removed
1033	>	* when hasNext() was called.
1034		*/
1035		E nextItem;
1036
#	Line 1009 | Line 1043 | public class LinkedBlockingDeque<E>
1043		abstract Node<E> firstNode();
1044		abstract Node<E> nextNode(Node<E> n);
1045
1046	+	private Node<E> succ(Node<E> p) {
1047	+	return (p == (p = nextNode(p))) ? firstNode() : p;
1048	+	}
1049	+
1050		AbstractItr() {
1051		// set to initial position
1052		final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1053		lock.lock();
1054		try {
1055	<	next = firstNode();
1056	<	nextItem = (next == null) ? null : next.item;
1055	>	if ((next = firstNode()) != null)
1056	>	nextItem = next.item;
1057		} finally {
1058	+	// checkInvariants();
1059		lock.unlock();
1060		}
1061		}
1062
1063	<	/**
1064	<	* Returns the successor node of the given non-null, but
1026	<	* possibly previously deleted, node.
1027	<	*/
1028	<	private Node<E> succ(Node<E> n) {
1029	<	// Chains of deleted nodes ending in null or self-links
1030	<	// are possible if multiple interior nodes are removed.
1031	<	for (;;) {
1032	<	Node<E> s = nextNode(n);
1033	<	if (s == null)
1034	<	return null;
1035	<	else if (s.item != null)
1036	<	return s;
1037	<	else if (s == n)
1038	<	return firstNode();
1039	<	else
1040	<	n = s;
1041	<	}
1063	>	public boolean hasNext() {
1064	>	return next != null;
1065		}
1066
1067	<	/**
1068	<	* Advances next.
1069	<	*/
1070	<	void advance() {
1067	>	public E next() {
1068	>	Node<E> p;
1069	>	if ((p = next) == null)
1070	>	throw new NoSuchElementException();
1071	>	E ret = nextItem, e = null;
1072	>	lastRet = p;
1073		final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1074		lock.lock();
1075		try {
1076	<	// assert next != null;
1077	<	next = succ(next);
1078	<	nextItem = (next == null) ? null : next.item;
1076	>	for (p = nextNode(p); p != null; p = succ(p))
1077	>	if ((e = p.item) != null)
1078	>	break;
1079		} finally {
1080	+	// checkInvariants();
1081		lock.unlock();
1082		}
1083	+	next = p;
1084	+	nextItem = e;
1085	+	return ret;
1086		}
1087
1088	<	public boolean hasNext() {
1089	<	return next != null;
1090	<	}
1091	<
1092	<	public E next() {
1064	<	if (next == null)
1065	<	throw new NoSuchElementException();
1088	>	public void forEachRemaining(Consumer<? super E> action) {
1089	>	// A variant of forEachFrom
1090	>	Objects.requireNonNull(action);
1091	>	Node<E> p;
1092	>	if ((p = next) == null) return;
1093		lastRet = next;
1094	<	E x = nextItem;
1095	<	advance();
1096	<	return x;
1094	>	next = null;
1095	>	final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1096	>	final int batchSize = 32;
1097	>	Object[] es = null;
1098	>	int n, len = 1;
1099	>	do {
1100	>	lock.lock();
1101	>	try {
1102	>	if (es == null) {
1103	>	p = nextNode(p);
1104	>	for (Node<E> q = p; q != null; q = succ(q))
1105	>	if (q.item != null && ++len == batchSize)
1106	>	break;
1107	>	es = new Object[len];
1108	>	es[0] = nextItem;
1109	>	nextItem = null;
1110	>	n = 1;
1111	>	} else
1112	>	n = 0;
1113	>	for (; p != null && n < len; p = succ(p))
1114	>	if ((es[n] = p.item) != null) {
1115	>	lastRet = p;
1116	>	n++;
1117	>	}
1118	>	} finally {
1119	>	// checkInvariants();
1120	>	lock.unlock();
1121	>	}
1122	>	for (int i = 0; i < n; i++) {
1123	>	@SuppressWarnings("unchecked") E e = (E) es[i];
1124	>	action.accept(e);
1125	>	}
1126	>	} while (n > 0 && p != null);
1127		}
1128
1129		public void remove() {
#	Line 1080 | Line 1137 | public class LinkedBlockingDeque<E>
1137		if (n.item != null)
1138		unlink(n);
1139		} finally {
1140	+	// checkInvariants();
1141		lock.unlock();
1142		}
1143		}
#	Line 1097 | Line 1155 | public class LinkedBlockingDeque<E>
1155		Node<E> nextNode(Node<E> n) { return n.prev; }
1156		}
1157
1158	<	/** A customized variant of Spliterators.IteratorSpliterator */
1159	<	static final class LBDSpliterator<E> implements Spliterator<E> {
1158	>	/**
1159	>	* A customized variant of Spliterators.IteratorSpliterator.
1160	>	* Keep this class in sync with (very similar) LBQSpliterator.
1161	>	*/
1162	>	private final class LBDSpliterator implements Spliterator<E> {
1163		static final int MAX_BATCH = 1 << 25;  // max batch array size;
1103	–	final LinkedBlockingDeque<E> queue;
1164		Node<E> current;    // current node; null until initialized
1165		int batch;          // batch size for splits
1166		boolean exhausted;  // true when no more nodes
1167	<	long est;           // size estimate
1168	<	LBDSpliterator(LinkedBlockingDeque<E> queue) {
1169	<	this.queue = queue;
1110	<	this.est = queue.size();
1111	<	}
1167	>	long est = size();  // size estimate
1168	>
1169	>	LBDSpliterator() {}
1170
1171		public long estimateSize() { return est; }
1172
1173		public Spliterator<E> trySplit() {
1174		Node<E> h;
1117	–	final LinkedBlockingDeque<E> q = this.queue;
1175		int b = batch;
1176		int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
1177		if (!exhausted &&
1178	<	(((h = current) != null && h != h.next)
1122	<	|| (h = q.first) != null)
1178	>	((h = current) != null || (h = first) != null)
1179		&& h.next != null) {
1180		Object[] a = new Object[n];
1181	<	final ReentrantLock lock = q.lock;
1181	>	final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1182		int i = 0;
1183		Node<E> p = current;
1184		lock.lock();
1185		try {
1186	<	if ((p != null && p != p.next) || (p = q.first) != null) {
1187	<	do {
1186	>	if (p != null || (p = first) != null)
1187	>	for (; p != null && i < n; p = succ(p))
1188		if ((a[i] = p.item) != null)
1189	<	++i;
1134	<	} while ((p = p.next) != null && i < n);
1135	<	}
1189	>	i++;
1190		} finally {
1191	+	// checkInvariants();
1192		lock.unlock();
1193		}
1194		if ((current = p) == null) {
#	Line 1153 | Line 1208 | public class LinkedBlockingDeque<E>
1208		return null;
1209		}
1210
1211	<	public void forEachRemaining(Consumer<? super E> action) {
1212	<	if (action == null) throw new NullPointerException();
1211	>	public boolean tryAdvance(Consumer<? super E> action) {
1212	>	Objects.requireNonNull(action);
1213		if (!exhausted) {
1214	<	exhausted = true;
1214	>	final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1215		Node<E> p = current;
1216	<	current = null;
1217	<	final LinkedBlockingDeque<E> q = this.queue;
1218	<	final ReentrantLock lock = q.lock;
1219	<	do {
1165	<	E e;
1166	<	lock.lock();
1167	<	try {
1168	<	if (p == null)
1169	<	p = q.first;
1216	>	E e = null;
1217	>	lock.lock();
1218	>	try {
1219	>	if (p != null || (p = first) != null)
1220		do {
1171	–	if (p == null)
1172	–	return;
1221		e = p.item;
1222	<	if (p == (p = p.next)) p = q.first;
1223	<	} while (e == null);
1224	<	} finally {
1225	<	lock.unlock();
1226	<	}
1222	>	p = succ(p);
1223	>	} while (e == null && p != null);
1224	>	} finally {
1225	>	// checkInvariants();
1226	>	lock.unlock();
1227	>	}
1228	>	exhausted = ((current = p) == null);
1229	>	if (e != null) {
1230		action.accept(e);
1231	<	} while (p != null);
1231	>	return true;
1232	>	}
1233		}
1234	+	return false;
1235		}
1236
1237	<	public boolean tryAdvance(Consumer<? super E> action) {
1238	<	if (action == null) throw new NullPointerException();
1239	<	if (!exhausted) findElement: {
1240	<	final LinkedBlockingDeque<E> q = this.queue;
1188	<	final ReentrantLock lock = q.lock;
1189	<	E e;
1237	>	public void forEachRemaining(Consumer<? super E> action) {
1238	>	Objects.requireNonNull(action);
1239	>	if (!exhausted) {
1240	>	exhausted = true;
1241		Node<E> p = current;
1242	<	lock.lock();
1243	<	try {
1193	<	if (p == null)
1194	<	p = q.first;
1195	<	do {
1196	<	if (p == null) break findElement;
1197	<	e = p.item;
1198	<	if (p == (p = p.next)) p = q.first;
1199	<	} while (e == null);
1200	<	} finally {
1201	<	lock.unlock();
1202	<	}
1203	<	action.accept(e);
1204	<	if ((current = p) == null)
1205	<	exhausted = true;
1206	<	return true;
1242	>	current = null;
1243	>	forEachFrom(action, p);
1244		}
1208	–	current = null;
1209	–	exhausted = true;
1210	–	return false;
1245		}
1246
1247		public int characteristics() {
#	Line 1234 | Line 1268 | public class LinkedBlockingDeque<E>
1268		* @since 1.8
1269		*/
1270		public Spliterator<E> spliterator() {
1271	<	return new LBDSpliterator<E>(this);
1271	>	return new LBDSpliterator();
1272	>	}
1273	>
1274	>	/**
1275	>	* @throws NullPointerException {@inheritDoc}
1276	>	*/
1277	>	public void forEach(Consumer<? super E> action) {
1278	>	Objects.requireNonNull(action);
1279	>	forEachFrom(action, null);
1280	>	}
1281	>
1282	>	/**
1283	>	* Runs action on each element found during a traversal starting at p.
1284	>	* If p is null, traversal starts at head.
1285	>	*/
1286	>	void forEachFrom(Consumer<? super E> action, Node<E> p) {
1287	>	// Extract batches of elements while holding the lock; then
1288	>	// run the action on the elements while not
1289	>	final ReentrantLock lock = this.lock;
1290	>	final int batchSize = 32;       // max number of elements per batch
1291	>	Object[] es = null;             // container for batch of elements
1292	>	int n, len = 0;
1293	>	do {
1294	>	lock.lock();
1295	>	try {
1296	>	if (es == null) {
1297	>	if (p == null) p = first;
1298	>	for (Node<E> q = p; q != null; q = succ(q))
1299	>	if (q.item != null && ++len == batchSize)
1300	>	break;
1301	>	es = new Object[len];
1302	>	}
1303	>	for (n = 0; p != null && n < len; p = succ(p))
1304	>	if ((es[n] = p.item) != null)
1305	>	n++;
1306	>	} finally {
1307	>	// checkInvariants();
1308	>	lock.unlock();
1309	>	}
1310	>	for (int i = 0; i < n; i++) {
1311	>	@SuppressWarnings("unchecked") E e = (E) es[i];
1312	>	action.accept(e);
1313	>	}
1314	>	} while (n > 0 && p != null);
1315		}
1316
1317		/**
#	Line 1258 | Line 1335 | public class LinkedBlockingDeque<E>
1335		// Use trailing null as sentinel
1336		s.writeObject(null);
1337		} finally {
1338	+	// checkInvariants();
1339		lock.unlock();
1340		}
1341		}
#	Line 1277 | Line 1355 | public class LinkedBlockingDeque<E>
1355		last = null;
1356		// Read in all elements and place in queue
1357		for (;;) {
1358	<	@SuppressWarnings("unchecked")
1281	<	E item = (E)s.readObject();
1358	>	@SuppressWarnings("unchecked") E item = (E)s.readObject();
1359		if (item == null)
1360		break;
1361		add(item);
1362		}
1363		}
1364
1365	+	void checkInvariants() {
1366	+	// assert lock.isHeldByCurrentThread();
1367	+	// Nodes may get self-linked or lose their item, but only
1368	+	// after being unlinked and becoming unreachable from first.
1369	+	for (Node<E> p = first; p != null; p = p.next) {
1370	+	// assert p.next != p;
1371	+	// assert p.item != null;
1372	+	}
1373	+	}
1374	+
1375		}

Diff Legend

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