jdk-sandbox: comparison jdk/src/java.base/share/classes/java/util/concurrent/LinkedBlockingDeque.java

equal deleted inserted replaced

-:5ea771a26665
+:8b9cacdadb2d
 import java.util.AbstractQueue;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.NoSuchElementException;
+import java.util.Objects;
 import java.util.Spliterator;
 import java.util.Spliterators;
 import java.util.concurrent.locks.Condition;
 import java.util.concurrent.locks.ReentrantLock;
 import java.util.function.Consumer;
 * @throws ClassCastException            {@inheritDoc}
 * @throws NullPointerException          {@inheritDoc}
 * @throws IllegalArgumentException      {@inheritDoc}
 */
 public int drainTo(Collection<? super E> c, int maxElements) {
-if (c == null)
+Objects.requireNonNull(c);
-throw new NullPointerException();
 if (c == this)
 throw new IllegalArgumentException();
 if (maxElements <= 0)
 return 0;
 final ReentrantLock lock = this.lock;
 lock.unlock();
 }
 }
 /**
+* Used for any element traversal that is not entirely under lock.
+* Such traversals must handle both:
+* - dequeued nodes (p.next == p)
+* - (possibly multiple) interior removed nodes (p.item == null)
+*/
+Node<E> succ(Node<E> p) {
+return (p == (p = p.next)) ? first : p;
+}
+/**
 * Returns an iterator over the elements in this deque in proper sequence.
 * The elements will be returned in order from first (head) to last (tail).
 *
 * <p>The returned iterator is
 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
 Node<E> next;
 /**
 * nextItem holds on to item fields because once we claim that
 * an element exists in hasNext(), we must return item read
-* under lock (in advance()) even if it was in the process of
+* under lock even if it was in the process of being removed
-* being removed when hasNext() was called.
+* when hasNext() was called.
 */
 E nextItem;
 /**
 * Node returned by most recent call to next. Needed by remove.
 private Node<E> lastRet;
 abstract Node<E> firstNode();
 abstract Node<E> nextNode(Node<E> n);
+private Node<E> succ(Node<E> p) {
+return (p == (p = nextNode(p))) ? firstNode() : p;
+}
 AbstractItr() {
 // set to initial position
 final ReentrantLock lock = LinkedBlockingDeque.this.lock;
 lock.lock();
 try {
-next = firstNode();
+if ((next = firstNode()) != null)
-nextItem = (next == null) ? null : next.item;
+nextItem = next.item;
 } finally {
 lock.unlock();
 }
 }
-/**
+public boolean hasNext() {
-* Returns the successor node of the given non-null, but
+return next != null;
-* possibly previously deleted, node.
+}
-*/
-private Node<E> succ(Node<E> n) {
+public E next() {
-// Chains of deleted nodes ending in null or self-links
+Node<E> p;
-// are possible if multiple interior nodes are removed.
+if ((p = next) == null)
-for (;;) {
+throw new NoSuchElementException();
-Node<E> s = nextNode(n);
+lastRet = p;
-if (s == null)
+E x = nextItem;
-return null;
-else if (s.item != null)
-return s;
-else if (s == n)
-return firstNode();
-else
-n = s;
-}
-}
-/**
-* Advances next.
-*/
-void advance() {
 final ReentrantLock lock = LinkedBlockingDeque.this.lock;
 lock.lock();
 try {
-// assert next != null;
+E e = null;
-next = succ(next);
+for (p = nextNode(p); p != null && (e = p.item) == null; )
-nextItem = (next == null) ? null : next.item;
+p = succ(p);
+next = p;
+nextItem = e;
 } finally {
 lock.unlock();
 }
-}
-public boolean hasNext() {
-return next != null;
-}
-public E next() {
-if (next == null)
-throw new NoSuchElementException();
-lastRet = next;
-E x = nextItem;
-advance();
 return x;
+}
+public void forEachRemaining(Consumer<? super E> action) {
+// A variant of forEachFrom
+Objects.requireNonNull(action);
+Node<E> p;
+if ((p = next) == null) return;
+lastRet = p;
+next = null;
+final ReentrantLock lock = LinkedBlockingDeque.this.lock;
+final int batchSize = 32;
+Object[] es = null;
+int n, len = 1;
+do {
+lock.lock();
+try {
+if (es == null) {
+p = nextNode(p);
+for (Node<E> q = p; q != null; q = succ(q))
+if (q.item != null && ++len == batchSize)
+break;
+es = new Object[len];
+es[0] = nextItem;
+nextItem = null;
+n = 1;
+} else
+n = 0;
+for (; p != null && n < len; p = succ(p))
+if ((es[n] = p.item) != null) {
+lastRet = p;
+n++;
+}
+} finally {
+lock.unlock();
+}
+for (int i = 0; i < n; i++) {
+@SuppressWarnings("unchecked") E e = (E) es[i];
+action.accept(e);
+}
+} while (n > 0 && p != null);
 }
 public void remove() {
 Node<E> n = lastRet;
 if (n == null)
 }
 }
 /** Forward iterator */
 private class Itr extends AbstractItr {
+Itr() {}                        // prevent access constructor creation
 Node<E> firstNode() { return first; }
 Node<E> nextNode(Node<E> n) { return n.next; }
 }
 /** Descending iterator */
 private class DescendingItr extends AbstractItr {
+DescendingItr() {}              // prevent access constructor creation
 Node<E> firstNode() { return last; }
 Node<E> nextNode(Node<E> n) { return n.prev; }
 }
-/** A customized variant of Spliterators.IteratorSpliterator */
+/**
+* A customized variant of Spliterators.IteratorSpliterator.
+* Keep this class in sync with (very similar) LBQSpliterator.
+*/
 private final class LBDSpliterator implements Spliterator<E> {
 static final int MAX_BATCH = 1 << 25;  // max batch array size;
 Node<E> current;    // current node; null until initialized
 int batch;          // batch size for splits
 boolean exhausted;  // true when no more nodes
-long est;           // size estimate
+long est = size();  // size estimate
-LBDSpliterator() { est = size(); }
+LBDSpliterator() {}
 public long estimateSize() { return est; }
 public Spliterator<E> trySplit() {
 Node<E> h;
 int b = batch;
 int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1;
 if (!exhausted &&
-(((h = current) != null && h != h.next)
+((h = current) != null || (h = first) != null)
-|| (h = first) != null)
 && h.next != null) {
 Object[] a = new Object[n];
 final ReentrantLock lock = LinkedBlockingDeque.this.lock;
 int i = 0;
 Node<E> p = current;
 lock.lock();
 try {
-if (((p != null && p != p.next) || (p = first) != null)
+if (p != null || (p = first) != null)
-&& p.item != null)
+for (; p != null && i < n; p = succ(p))
-for (; p != null && i < n; p = p.next)
+if ((a[i] = p.item) != null)
-a[i++] = p.item;
+i++;
 } finally {
 lock.unlock();
 }
 if ((current = p) == null) {
 est = 0L;
 }
 }
 return null;
 }
-public void forEachRemaining(Consumer<? super E> action) {
+public boolean tryAdvance(Consumer<? super E> action) {
-if (action == null) throw new NullPointerException();
+Objects.requireNonNull(action);
-if (exhausted)
+if (!exhausted) {
-return;
-exhausted = true;
-final ReentrantLock lock = LinkedBlockingDeque.this.lock;
-Node<E> p = current;
-current = null;
-do {
 E e = null;
+final ReentrantLock lock = LinkedBlockingDeque.this.lock;
 lock.lock();
 try {
-if ((p != null && p != p.next) || (p = first) != null) {
+Node<E> p;
-e = p.item;
+if ((p = current) != null || (p = first) != null)
-p = p.next;
+do {
-}
+e = p.item;
+p = succ(p);
+} while (e == null && p != null);
+exhausted = ((current = p) == null);
 } finally {
 lock.unlock();
 }
-if (e != null)
+if (e != null) {
 action.accept(e);
-} while (p != null);
+return true;
-}
-public boolean tryAdvance(Consumer<? super E> action) {
-if (action == null) throw new NullPointerException();
-if (exhausted)
-return false;
-final ReentrantLock lock = LinkedBlockingDeque.this.lock;
-Node<E> p = current;
-E e = null;
-lock.lock();
-try {
-if ((p != null && p != p.next) || (p = first) != null) {
-e = p.item;
-p = p.next;
 }
-} finally {
+}
-lock.unlock();
+return false;
 }
-exhausted = ((current = p) == null);
-if (e == null)
+public void forEachRemaining(Consumer<? super E> action) {
-return false;
+Objects.requireNonNull(action);
-action.accept(e);
+if (!exhausted) {
-return true;
+exhausted = true;
+Node<E> p = current;
+current = null;
+forEachFrom(action, p);
+}
 }
 public int characteristics() {
 return (Spliterator.ORDERED |
 Spliterator.NONNULL |
 * @return a {@code Spliterator} over the elements in this deque
 * @since 1.8
 */
 public Spliterator<E> spliterator() {
 return new LBDSpliterator();
+}
+/**
+* @throws NullPointerException {@inheritDoc}
+*/
+public void forEach(Consumer<? super E> action) {
+Objects.requireNonNull(action);
+forEachFrom(action, null);
+}
+/**
+* Runs action on each element found during a traversal starting at p.
+* If p is null, traversal starts at head.
+*/
+void forEachFrom(Consumer<? super E> action, Node<E> p) {
+// Extract batches of elements while holding the lock; then
+// run the action on the elements while not
+final ReentrantLock lock = this.lock;
+final int batchSize = 32;       // max number of elements per batch
+Object[] es = null;             // container for batch of elements
+int n, len = 0;
+do {
+lock.lock();
+try {
+if (es == null) {
+if (p == null) p = first;
+for (Node<E> q = p; q != null; q = succ(q))
+if (q.item != null && ++len == batchSize)
+break;
+es = new Object[len];
+}
+for (n = 0; p != null && n < len; p = succ(p))
+if ((es[n] = p.item) != null)
+n++;
+} finally {
+lock.unlock();
+}
+for (int i = 0; i < n; i++) {
+@SuppressWarnings("unchecked") E e = (E) es[i];
+action.accept(e);
+}
+} while (n > 0 && p != null);
 }
 /**
 * Saves this deque to a stream (that is, serializes it).
 *
 count = 0;
 first = null;
 last = null;
 // Read in all elements and place in queue
 for (;;) {
-@SuppressWarnings("unchecked")
+@SuppressWarnings("unchecked") E item = (E)s.readObject();
-E item = (E)s.readObject();
 if (item == null)
 break;
 add(item);
 }
 }

changeset 42926	8b9cacdadb2d
parent 42319	0193886267c3
child 43521	60e247b8d9a4