ViewVC Help

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

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

Comparing jsr166/src/main/java/util/concurrent/LinkedBlockingDeque.java (file contents):
Revision 1.73 by jsr166, Mon Dec 26 19:54:45 2016 UTC vs.
Revision 1.74 by jsr166, Tue Dec 27 02:26:23 2016 UTC

#	Line 16 | Line 16 | import java.util.Spliterators;
16		import java.util.concurrent.locks.Condition;
17		import java.util.concurrent.locks.ReentrantLock;
18		import java.util.function.Consumer;
19	+	import java.util.function.Predicate;
20
21		/**
22		* An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
#	Line 166 | Line 167 | public class LinkedBlockingDeque<E>
167		*/
168		public LinkedBlockingDeque(Collection<? extends E> c) {
169		this(Integer.MAX_VALUE);
170	<	final ReentrantLock lock = this.lock;
170	<	lock.lock(); // Never contended, but necessary for visibility
171	<	try {
172	<	for (E e : c) {
173	<	if (e == null)
174	<	throw new NullPointerException();
175	<	if (!linkLast(new Node<E>(e)))
176	<	throw new IllegalStateException("Deque full");
177	<	}
178	<	} finally {
179	<	// checkInvariants();
180	<	lock.unlock();
181	<	}
170	>	addAll(c);
171		}
172
173
#	Line 826 | Line 815 | public class LinkedBlockingDeque<E>
815		}
816		}
817
818	<	/*
819	<	* TODO: Add support for more efficient bulk operations.
818	>	/**
819	>	* Appends all of the elements in the specified collection to the end of
820	>	* this deque, in the order that they are returned by the specified
821	>	* collection's iterator.  Attempts to {@code addAll} of a deque to
822	>	* itself result in {@code IllegalArgumentException}.
823		*
824	<	* We don't want to acquire the lock for every iteration, but we
825	<	* also want other threads a chance to interact with the
826	<	* collection, especially when count is close to capacity.
827	<	*/
828	<
829	<	//     /**
830	<	//      * Adds all of the elements in the specified collection to this
831	<	//      * queue.  Attempts to addAll of a queue to itself result in
832	<	//      * {@code IllegalArgumentException}. Further, the behavior of
833	<	//      * this operation is undefined if the specified collection is
834	<	//      * modified while the operation is in progress.
835	<	//      *
836	<	//      * @param c collection containing elements to be added to this queue
837	<	//      * @return {@code true} if this queue changed as a result of the call
838	<	//      * @throws ClassCastException            {@inheritDoc}
839	<	//      * @throws NullPointerException          {@inheritDoc}
840	<	//      * @throws IllegalArgumentException      {@inheritDoc}
841	<	//      * @throws IllegalStateException if this deque is full
842	<	//      * @see #add(Object)
843	<	//      */
844	<	//     public boolean addAll(Collection<? extends E> c) {
845	<	//         if (c == null)
846	<	//             throw new NullPointerException();
847	<	//         if (c == this)
848	<	//             throw new IllegalArgumentException();
849	<	//         final ReentrantLock lock = this.lock;
850	<	//         lock.lock();
851	<	//         try {
852	<	//             boolean modified = false;
853	<	//             for (E e : c)
854	<	//                 if (linkLast(e))
855	<	//                     modified = true;
856	<	//             return modified;
857	<	//         } finally {
858	<	//             lock.unlock();
859	<	//         }
860	<	//     }
824	>	* @param c the elements to be inserted into this deque
825	>	* @return {@code true} if this deque changed as a result of the call
826	>	* @throws NullPointerException if the specified collection or any
827	>	*         of its elements are null
828	>	* @throws IllegalArgumentException if the collection is this deque
829	>	* @throws IllegalStateException if this deque is full
830	>	* @see #add(Object)
831	>	*/
832	>	public boolean addAll(Collection<? extends E> c) {
833	>	if (c == this)
834	>	// As historically specified in AbstractQueue#addAll
835	>	throw new IllegalArgumentException();
836	>
837	>	// Copy c into a private chain of Nodes
838	>	Node<E> beg = null, end = null;
839	>	int n = 0;
840	>	for (E e : c) {
841	>	Objects.requireNonNull(e);
842	>	n++;
843	>	Node<E> newNode = new Node<E>(e);
844	>	if (beg == null)
845	>	beg = end = newNode;
846	>	else {
847	>	end.next = newNode;
848	>	newNode.prev = end;
849	>	end = newNode;
850	>	}
851	>	}
852	>	if (beg == null)
853	>	return false;
854	>
855	>	// Atomically append the chain at the end
856	>	final ReentrantLock lock = this.lock;
857	>	lock.lock();
858	>	try {
859	>	if (count + n <= capacity) {
860	>	beg.prev = last;
861	>	if (first == null)
862	>	first = beg;
863	>	else
864	>	last.next = beg;
865	>	last = end;
866	>	count += n;
867	>	notEmpty.signalAll();
868	>	return true;
869	>	}
870	>	} finally {
871	>	// checkInvariants();
872	>	lock.unlock();
873	>	}
874	>	// Fall back to historic non-atomic implementation, failing
875	>	// with IllegalStateException when the capacity is exceeded.
876	>	return super.addAll(c);
877	>	}
878
879		/**
880		* Returns an array containing all of the elements in this deque, in
#	Line 1315 | Line 1324 | public class LinkedBlockingDeque<E>
1324		}
1325
1326		/**
1327	+	* @throws NullPointerException {@inheritDoc}
1328	+	*/
1329	+	public boolean removeIf(Predicate<? super E> filter) {
1330	+	Objects.requireNonNull(filter);
1331	+	return bulkRemove(filter);
1332	+	}
1333	+
1334	+	/**
1335	+	* @throws NullPointerException {@inheritDoc}
1336	+	*/
1337	+	public boolean removeAll(Collection<?> c) {
1338	+	Objects.requireNonNull(c);
1339	+	return bulkRemove(e -> c.contains(e));
1340	+	}
1341	+
1342	+	/**
1343	+	* @throws NullPointerException {@inheritDoc}
1344	+	*/
1345	+	public boolean retainAll(Collection<?> c) {
1346	+	Objects.requireNonNull(c);
1347	+	return bulkRemove(e -> !c.contains(e));
1348	+	}
1349	+
1350	+	/** Implementation of bulk remove methods. */
1351	+	@SuppressWarnings("unchecked")
1352	+	private boolean bulkRemove(Predicate<? super E> filter) {
1353	+	boolean removed = false;
1354	+	Node<E> p = null;
1355	+	final ReentrantLock lock = this.lock;
1356	+	Node<E>[] nodes = null;
1357	+	int n, len = 0;
1358	+	do {
1359	+	// 1. Extract batch of up to 64 elements while holding the lock.
1360	+	long deathRow = 0;          // "bitset" of size 64
1361	+	lock.lock();
1362	+	try {
1363	+	if (nodes == null) {
1364	+	if (p == null) p = first;
1365	+	for (Node<E> q = p; q != null; q = succ(q))
1366	+	if (q.item != null && ++len == 64)
1367	+	break;
1368	+	nodes = (Node<E>[]) new Node<?>[len];
1369	+	}
1370	+	for (n = 0; p != null && n < len; p = succ(p))
1371	+	nodes[n++] = p;
1372	+	} finally {
1373	+	// checkInvariants();
1374	+	lock.unlock();
1375	+	}
1376	+
1377	+	// 2. Run the filter on the elements while lock is free.
1378	+	for (int i = 0; i < n; i++) {
1379	+	final E e;
1380	+	if ((e = nodes[i].item) != null && filter.test(e))
1381	+	deathRow |= 1L << i;
1382	+	}
1383	+
1384	+	// 3. Remove any filtered elements while holding the lock.
1385	+	if (deathRow != 0) {
1386	+	lock.lock();
1387	+	try {
1388	+	for (int i = 0; i < n; i++) {
1389	+	final Node<E> q;
1390	+	if ((deathRow & (1L << i)) != 0L
1391	+	&& (q = nodes[i]).item != null) {
1392	+	q.item = null;
1393	+	unlink(q);
1394	+	removed = true;
1395	+	}
1396	+	}
1397	+	} finally {
1398	+	// checkInvariants();
1399	+	lock.unlock();
1400	+	}
1401	+	}
1402	+	} while (n > 0 && p != null);
1403	+	return removed;
1404	+	}
1405	+
1406	+	/**
1407		* Saves this deque to a stream (that is, serializes it).
1408		*
1409		* @param s the stream

Diff Legend

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