/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ /* * This file is available under and governed by the GNU General Public * License version 2 only, as published by the Free Software Foundation. * However, the following notice accompanied the original version of this * file: * * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at * http://creativecommons.org/publicdomain/zero/1.0/ */ package java.util.concurrent; import java.util.AbstractQueue; import java.util.Collection; import java.util.Iterator; import java.util.NoSuchElementException; 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; // BEGIN android-note // removed link to collections framework docs // END android-note /** * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on * linked nodes. * *

The optional capacity bound constructor argument serves as a * way to prevent excessive expansion. The capacity, if unspecified, * is equal to {@link Integer#MAX_VALUE}. Linked nodes are * dynamically created upon each insertion unless this would bring the * deque above capacity. * *

Most operations run in constant time (ignoring time spent * blocking). Exceptions include {@link #remove(Object) remove}, * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link * #removeLastOccurrence removeLastOccurrence}, {@link #contains * contains}, {@link #iterator iterator.remove()}, and the bulk * operations, all of which run in linear time. * *

This class and its iterator implement all of the * optional methods of the {@link Collection} and {@link * Iterator} interfaces. * * @since 1.6 * @author Doug Lea * @param the type of elements held in this deque */ public class LinkedBlockingDeque extends AbstractQueue implements BlockingDeque, java.io.Serializable { /* * Implemented as a simple doubly-linked list protected by a * single lock and using conditions to manage blocking. * * To implement weakly consistent iterators, it appears we need to * keep all Nodes GC-reachable from a predecessor dequeued Node. * That would cause two problems: * - allow a rogue Iterator to cause unbounded memory retention * - cause cross-generational linking of old Nodes to new Nodes if * a Node was tenured while live, which generational GCs have a * hard time dealing with, causing repeated major collections. * However, only non-deleted Nodes need to be reachable from * dequeued Nodes, and reachability does not necessarily have to * be of the kind understood by the GC. We use the trick of * linking a Node that has just been dequeued to itself. Such a * self-link implicitly means to jump to "first" (for next links) * or "last" (for prev links). */ /* * We have "diamond" multiple interface/abstract class inheritance * here, and that introduces ambiguities. Often we want the * BlockingDeque javadoc combined with the AbstractQueue * implementation, so a lot of method specs are duplicated here. */ private static final long serialVersionUID = -387911632671998426L; /** Doubly-linked list node class */ static final class Node { /** * The item, or null if this node has been removed. */ E item; /** * One of: * - the real predecessor Node * - this Node, meaning the predecessor is tail * - null, meaning there is no predecessor */ Node prev; /** * One of: * - the real successor Node * - this Node, meaning the successor is head * - null, meaning there is no successor */ Node next; Node(E x) { item = x; } } /** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node first; /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node last; /** Number of items in the deque */ private transient int count; /** Maximum number of items in the deque */ private final int capacity; /** Main lock guarding all access */ final ReentrantLock lock = new ReentrantLock(); /** Condition for waiting takes */ private final Condition notEmpty = lock.newCondition(); /** Condition for waiting puts */ private final Condition notFull = lock.newCondition(); /** * Creates a {@code LinkedBlockingDeque} with a capacity of * {@link Integer#MAX_VALUE}. */ public LinkedBlockingDeque() { this(Integer.MAX_VALUE); } /** * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity. * * @param capacity the capacity of this deque * @throws IllegalArgumentException if {@code capacity} is less than 1 */ public LinkedBlockingDeque(int capacity) { if (capacity <= 0) throw new IllegalArgumentException(); this.capacity = capacity; } /** * Creates a {@code LinkedBlockingDeque} with a capacity of * {@link Integer#MAX_VALUE}, initially containing the elements of * the given collection, added in traversal order of the * collection's iterator. * * @param c the collection of elements to initially contain * @throws NullPointerException if the specified collection or any * of its elements are null */ public LinkedBlockingDeque(Collection c) { this(Integer.MAX_VALUE); final ReentrantLock lock = this.lock; lock.lock(); // Never contended, but necessary for visibility try { for (E e : c) { if (e == null) throw new NullPointerException(); if (!linkLast(new Node(e))) throw new IllegalStateException("Deque full"); } } finally { lock.unlock(); } } // Basic linking and unlinking operations, called only while holding lock /** * Links node as first element, or returns false if full. */ private boolean linkFirst(Node node) { // assert lock.isHeldByCurrentThread(); if (count >= capacity) return false; Node f = first; node.next = f; first = node; if (last == null) last = node; else f.prev = node; ++count; notEmpty.signal(); return true; } /** * Links node as last element, or returns false if full. */ private boolean linkLast(Node node) { // assert lock.isHeldByCurrentThread(); if (count >= capacity) return false; Node l = last; node.prev = l; last = node; if (first == null) first = node; else l.next = node; ++count; notEmpty.signal(); return true; } /** * Removes and returns first element, or null if empty. */ private E unlinkFirst() { // assert lock.isHeldByCurrentThread(); Node f = first; if (f == null) return null; Node n = f.next; E item = f.item; f.item = null; f.next = f; // help GC first = n; if (n == null) last = null; else n.prev = null; --count; notFull.signal(); return item; } /** * Removes and returns last element, or null if empty. */ private E unlinkLast() { // assert lock.isHeldByCurrentThread(); Node l = last; if (l == null) return null; Node p = l.prev; E item = l.item; l.item = null; l.prev = l; // help GC last = p; if (p == null) first = null; else p.next = null; --count; notFull.signal(); return item; } /** * Unlinks x. */ void unlink(Node x) { // assert lock.isHeldByCurrentThread(); Node p = x.prev; Node n = x.next; if (p == null) { unlinkFirst(); } else if (n == null) { unlinkLast(); } else { p.next = n; n.prev = p; x.item = null; // Don't mess with x's links. They may still be in use by // an iterator. --count; notFull.signal(); } } // BlockingDeque methods /** * @throws IllegalStateException if this deque is full * @throws NullPointerException {@inheritDoc} */ public void addFirst(E e) { if (!offerFirst(e)) throw new IllegalStateException("Deque full"); } /** * @throws IllegalStateException if this deque is full * @throws NullPointerException {@inheritDoc} */ public void addLast(E e) { if (!offerLast(e)) throw new IllegalStateException("Deque full"); } /** * @throws NullPointerException {@inheritDoc} */ public boolean offerFirst(E e) { if (e == null) throw new NullPointerException(); Node node = new Node(e); final ReentrantLock lock = this.lock; lock.lock(); try { return linkFirst(node); } finally { lock.unlock(); } } /** * @throws NullPointerException {@inheritDoc} */ public boolean offerLast(E e) { if (e == null) throw new NullPointerException(); Node node = new Node(e); final ReentrantLock lock = this.lock; lock.lock(); try { return linkLast(node); } finally { lock.unlock(); } } /** * @throws NullPointerException {@inheritDoc} * @throws InterruptedException {@inheritDoc} */ public void putFirst(E e) throws InterruptedException { if (e == null) throw new NullPointerException(); Node node = new Node(e); final ReentrantLock lock = this.lock; lock.lock(); try { while (!linkFirst(node)) notFull.await(); } finally { lock.unlock(); } } /** * @throws NullPointerException {@inheritDoc} * @throws InterruptedException {@inheritDoc} */ public void putLast(E e) throws InterruptedException { if (e == null) throw new NullPointerException(); Node node = new Node(e); final ReentrantLock lock = this.lock; lock.lock(); try { while (!linkLast(node)) notFull.await(); } finally { lock.unlock(); } } /** * @throws NullPointerException {@inheritDoc} * @throws InterruptedException {@inheritDoc} */ public boolean offerFirst(E e, long timeout, TimeUnit unit) throws InterruptedException { if (e == null) throw new NullPointerException(); Node node = new Node(e); long nanos = unit.toNanos(timeout); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (!linkFirst(node)) { if (nanos <= 0L) return false; nanos = notFull.awaitNanos(nanos); } return true; } finally { lock.unlock(); } } /** * @throws NullPointerException {@inheritDoc} * @throws InterruptedException {@inheritDoc} */ public boolean offerLast(E e, long timeout, TimeUnit unit) throws InterruptedException { if (e == null) throw new NullPointerException(); Node node = new Node(e); long nanos = unit.toNanos(timeout); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { while (!linkLast(node)) { if (nanos <= 0L) return false; nanos = notFull.awaitNanos(nanos); } return true; } finally { lock.unlock(); } } /** * @throws NoSuchElementException {@inheritDoc} */ public E removeFirst() { E x = pollFirst(); if (x == null) throw new NoSuchElementException(); return x; } /** * @throws NoSuchElementException {@inheritDoc} */ public E removeLast() { E x = pollLast(); if (x == null) throw new NoSuchElementException(); return x; } public E pollFirst() { final ReentrantLock lock = this.lock; lock.lock(); try { return unlinkFirst(); } finally { lock.unlock(); } } public E pollLast() { final ReentrantLock lock = this.lock; lock.lock(); try { return unlinkLast(); } finally { lock.unlock(); } } public E takeFirst() throws InterruptedException { final ReentrantLock lock = this.lock; lock.lock(); try { E x; while ( (x = unlinkFirst()) == null) notEmpty.await(); return x; } finally { lock.unlock(); } } public E takeLast() throws InterruptedException { final ReentrantLock lock = this.lock; lock.lock(); try { E x; while ( (x = unlinkLast()) == null) notEmpty.await(); return x; } finally { lock.unlock(); } } public E pollFirst(long timeout, TimeUnit unit) throws InterruptedException { long nanos = unit.toNanos(timeout); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { E x; while ( (x = unlinkFirst()) == null) { if (nanos <= 0L) return null; nanos = notEmpty.awaitNanos(nanos); } return x; } finally { lock.unlock(); } } public E pollLast(long timeout, TimeUnit unit) throws InterruptedException { long nanos = unit.toNanos(timeout); final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { E x; while ( (x = unlinkLast()) == null) { if (nanos <= 0L) return null; nanos = notEmpty.awaitNanos(nanos); } return x; } finally { lock.unlock(); } } /** * @throws NoSuchElementException {@inheritDoc} */ public E getFirst() { E x = peekFirst(); if (x == null) throw new NoSuchElementException(); return x; } /** * @throws NoSuchElementException {@inheritDoc} */ public E getLast() { E x = peekLast(); if (x == null) throw new NoSuchElementException(); return x; } public E peekFirst() { final ReentrantLock lock = this.lock; lock.lock(); try { return (first == null) ? null : first.item; } finally { lock.unlock(); } } public E peekLast() { final ReentrantLock lock = this.lock; lock.lock(); try { return (last == null) ? null : last.item; } finally { lock.unlock(); } } public boolean removeFirstOccurrence(Object o) { if (o == null) return false; final ReentrantLock lock = this.lock; lock.lock(); try { for (Node p = first; p != null; p = p.next) { if (o.equals(p.item)) { unlink(p); return true; } } return false; } finally { lock.unlock(); } } public boolean removeLastOccurrence(Object o) { if (o == null) return false; final ReentrantLock lock = this.lock; lock.lock(); try { for (Node p = last; p != null; p = p.prev) { if (o.equals(p.item)) { unlink(p); return true; } } return false; } finally { lock.unlock(); } } // BlockingQueue methods /** * Inserts the specified element at the end of this deque unless it would * violate capacity restrictions. When using a capacity-restricted deque, * it is generally preferable to use method {@link #offer(Object) offer}. * *

This method is equivalent to {@link #addLast}. * * @throws IllegalStateException if this deque is full * @throws NullPointerException if the specified element is null */ public boolean add(E e) { addLast(e); return true; } /** * @throws NullPointerException if the specified element is null */ public boolean offer(E e) { return offerLast(e); } /** * @throws NullPointerException {@inheritDoc} * @throws InterruptedException {@inheritDoc} */ public void put(E e) throws InterruptedException { putLast(e); } /** * @throws NullPointerException {@inheritDoc} * @throws InterruptedException {@inheritDoc} */ public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException { return offerLast(e, timeout, unit); } /** * Retrieves and removes the head of the queue represented by this deque. * This method differs from {@link #poll poll} only in that it throws an * exception if this deque is empty. * *

This method is equivalent to {@link #removeFirst() removeFirst}. * * @return the head of the queue represented by this deque * @throws NoSuchElementException if this deque is empty */ public E remove() { return removeFirst(); } public E poll() { return pollFirst(); } public E take() throws InterruptedException { return takeFirst(); } public E poll(long timeout, TimeUnit unit) throws InterruptedException { return pollFirst(timeout, unit); } /** * Retrieves, but does not remove, the head of the queue represented by * this deque. This method differs from {@link #peek peek} only in that * it throws an exception if this deque is empty. * *

This method is equivalent to {@link #getFirst() getFirst}. * * @return the head of the queue represented by this deque * @throws NoSuchElementException if this deque is empty */ public E element() { return getFirst(); } public E peek() { return peekFirst(); } /** * Returns the number of additional elements that this deque can ideally * (in the absence of memory or resource constraints) accept without * blocking. This is always equal to the initial capacity of this deque * less the current {@code size} of this deque. * *

Note that you cannot always tell if an attempt to insert * an element will succeed by inspecting {@code remainingCapacity} * because it may be the case that another thread is about to * insert or remove an element. */ public int remainingCapacity() { final ReentrantLock lock = this.lock; lock.lock(); try { return capacity - count; } finally { lock.unlock(); } } /** * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */ public int drainTo(Collection c) { return drainTo(c, Integer.MAX_VALUE); } /** * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} */ public int drainTo(Collection c, int maxElements) { if (c == null) throw new NullPointerException(); if (c == this) throw new IllegalArgumentException(); if (maxElements <= 0) return 0; final ReentrantLock lock = this.lock; lock.lock(); try { int n = Math.min(maxElements, count); for (int i = 0; i < n; i++) { c.add(first.item); // In this order, in case add() throws. unlinkFirst(); } return n; } finally { lock.unlock(); } } // Stack methods /** * @throws IllegalStateException if this deque is full * @throws NullPointerException {@inheritDoc} */ public void push(E e) { addFirst(e); } /** * @throws NoSuchElementException {@inheritDoc} */ public E pop() { return removeFirst(); } // Collection methods /** * Removes the first occurrence of the specified element from this deque. * If the deque does not contain the element, it is unchanged. * More formally, removes the first element {@code e} such that * {@code o.equals(e)} (if such an element exists). * Returns {@code true} if this deque contained the specified element * (or equivalently, if this deque changed as a result of the call). * *

This method is equivalent to * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}. * * @param o element to be removed from this deque, if present * @return {@code true} if this deque changed as a result of the call */ public boolean remove(Object o) { return removeFirstOccurrence(o); } /** * Returns the number of elements in this deque. * * @return the number of elements in this deque */ public int size() { final ReentrantLock lock = this.lock; lock.lock(); try { return count; } finally { lock.unlock(); } } /** * Returns {@code true} if this deque contains the specified element. * More formally, returns {@code true} if and only if this deque contains * at least one element {@code e} such that {@code o.equals(e)}. * * @param o object to be checked for containment in this deque * @return {@code true} if this deque contains the specified element */ public boolean contains(Object o) { if (o == null) return false; final ReentrantLock lock = this.lock; lock.lock(); try { for (Node p = first; p != null; p = p.next) if (o.equals(p.item)) return true; return false; } finally { lock.unlock(); } } /* * TODO: Add support for more efficient bulk operations. * * We don't want to acquire the lock for every iteration, but we * also want other threads a chance to interact with the * collection, especially when count is close to capacity. */ // /** // * Adds all of the elements in the specified collection to this // * queue. Attempts to addAll of a queue to itself result in // * {@code IllegalArgumentException}. Further, the behavior of // * this operation is undefined if the specified collection is // * modified while the operation is in progress. // * // * @param c collection containing elements to be added to this queue // * @return {@code true} if this queue changed as a result of the call // * @throws ClassCastException {@inheritDoc} // * @throws NullPointerException {@inheritDoc} // * @throws IllegalArgumentException {@inheritDoc} // * @throws IllegalStateException if this deque is full // * @see #add(Object) // */ // public boolean addAll(Collection c) { // if (c == null) // throw new NullPointerException(); // if (c == this) // throw new IllegalArgumentException(); // final ReentrantLock lock = this.lock; // lock.lock(); // try { // boolean modified = false; // for (E e : c) // if (linkLast(e)) // modified = true; // return modified; // } finally { // lock.unlock(); // } // } /** * Returns an array containing all of the elements in this deque, in * proper sequence (from first to last element). * *

The returned array will be "safe" in that no references to it are * maintained by this deque. (In other words, this method must allocate * a new array). The caller is thus free to modify the returned array. * *

This method acts as bridge between array-based and collection-based * APIs. * * @return an array containing all of the elements in this deque */ @SuppressWarnings("unchecked") public Object[] toArray() { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] a = new Object[count]; int k = 0; for (Node p = first; p != null; p = p.next) a[k++] = p.item; return a; } finally { lock.unlock(); } } /** * Returns an array containing all of the elements in this deque, in * proper sequence; the runtime type of the returned array is that of * the specified array. If the deque fits in the specified array, it * is returned therein. Otherwise, a new array is allocated with the * runtime type of the specified array and the size of this deque. * *

If this deque fits in the specified array with room to spare * (i.e., the array has more elements than this deque), the element in * the array immediately following the end of the deque is set to * {@code null}. * *

Like the {@link #toArray()} method, this method acts as bridge between * array-based and collection-based APIs. Further, this method allows * precise control over the runtime type of the output array, and may, * under certain circumstances, be used to save allocation costs. * *

Suppose {@code x} is a deque known to contain only strings. * The following code can be used to dump the deque into a newly * allocated array of {@code String}: * *

 {@code String[] y = x.toArray(new String[0]);}
* * Note that {@code toArray(new Object[0])} is identical in function to * {@code toArray()}. * * @param a the array into which the elements of the deque are to * be stored, if it is big enough; otherwise, a new array of the * same runtime type is allocated for this purpose * @return an array containing all of the elements in this deque * @throws ArrayStoreException if the runtime type of the specified array * is not a supertype of the runtime type of every element in * this deque * @throws NullPointerException if the specified array is null */ @SuppressWarnings("unchecked") public T[] toArray(T[] a) { final ReentrantLock lock = this.lock; lock.lock(); try { if (a.length < count) a = (T[])java.lang.reflect.Array.newInstance (a.getClass().getComponentType(), count); int k = 0; for (Node p = first; p != null; p = p.next) a[k++] = (T)p.item; if (a.length > k) a[k] = null; return a; } finally { lock.unlock(); } } public String toString() { return Helpers.collectionToString(this); } /** * Atomically removes all of the elements from this deque. * The deque will be empty after this call returns. */ public void clear() { final ReentrantLock lock = this.lock; lock.lock(); try { for (Node f = first; f != null; ) { f.item = null; Node n = f.next; f.prev = null; f.next = null; f = n; } first = last = null; count = 0; notFull.signalAll(); } finally { lock.unlock(); } } /** * 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). * *

The returned iterator is * weakly consistent. * * @return an iterator over the elements in this deque in proper sequence */ public Iterator iterator() { return new Itr(); } /** * Returns an iterator over the elements in this deque in reverse * sequential order. The elements will be returned in order from * last (tail) to first (head). * *

The returned iterator is * weakly consistent. * * @return an iterator over the elements in this deque in reverse order */ public Iterator descendingIterator() { return new DescendingItr(); } /** * Base class for LinkedBlockingDeque iterators. */ private abstract class AbstractItr implements Iterator { /** * The next node to return in next(). */ Node 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 * being removed when hasNext() was called. */ E nextItem; /** * Node returned by most recent call to next. Needed by remove. * Reset to null if this element is deleted by a call to remove. */ private Node lastRet; abstract Node firstNode(); abstract Node nextNode(Node n); AbstractItr() { // set to initial position final ReentrantLock lock = LinkedBlockingDeque.this.lock; lock.lock(); try { next = firstNode(); nextItem = (next == null) ? null : next.item; } finally { lock.unlock(); } } /** * Returns the successor node of the given non-null, but * possibly previously deleted, node. */ private Node succ(Node n) { // Chains of deleted nodes ending in null or self-links // are possible if multiple interior nodes are removed. for (;;) { Node s = nextNode(n); if (s == null) 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; next = succ(next); nextItem = (next == null) ? null : next.item; } 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 remove() { Node n = lastRet; if (n == null) throw new IllegalStateException(); lastRet = null; final ReentrantLock lock = LinkedBlockingDeque.this.lock; lock.lock(); try { if (n.item != null) unlink(n); } finally { lock.unlock(); } } } /** Forward iterator */ private class Itr extends AbstractItr { Node firstNode() { return first; } Node nextNode(Node n) { return n.next; } } /** Descending iterator */ private class DescendingItr extends AbstractItr { Node firstNode() { return last; } Node nextNode(Node n) { return n.prev; } } /** A customized variant of Spliterators.IteratorSpliterator */ static final class LBDSpliterator implements Spliterator { static final int MAX_BATCH = 1 << 25; // max batch array size; final LinkedBlockingDeque queue; Node current; // current node; null until initialized int batch; // batch size for splits boolean exhausted; // true when no more nodes long est; // size estimate LBDSpliterator(LinkedBlockingDeque queue) { this.queue = queue; this.est = queue.size(); } public long estimateSize() { return est; } public Spliterator trySplit() { Node h; final LinkedBlockingDeque q = this.queue; int b = batch; int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1; if (!exhausted && ((h = current) != null || (h = q.first) != null) && h.next != null) { Object[] a = new Object[n]; final ReentrantLock lock = q.lock; int i = 0; Node p = current; lock.lock(); try { if (p != null || (p = q.first) != null) { do { if ((a[i] = p.item) != null) ++i; } while ((p = p.next) != null && i < n); } } finally { lock.unlock(); } if ((current = p) == null) { est = 0L; exhausted = true; } else if ((est -= i) < 0L) est = 0L; if (i > 0) { batch = i; return Spliterators.spliterator (a, 0, i, (Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.CONCURRENT)); } } return null; } public void forEachRemaining(Consumer action) { if (action == null) throw new NullPointerException(); final LinkedBlockingDeque q = this.queue; final ReentrantLock lock = q.lock; if (!exhausted) { exhausted = true; Node p = current; do { E e = null; lock.lock(); try { if (p == null) p = q.first; while (p != null) { e = p.item; p = p.next; if (e != null) break; } } finally { lock.unlock(); } if (e != null) action.accept(e); } while (p != null); } } public boolean tryAdvance(Consumer action) { if (action == null) throw new NullPointerException(); final LinkedBlockingDeque q = this.queue; final ReentrantLock lock = q.lock; if (!exhausted) { E e = null; lock.lock(); try { if (current == null) current = q.first; while (current != null) { e = current.item; current = current.next; if (e != null) break; } } finally { lock.unlock(); } if (current == null) exhausted = true; if (e != null) { action.accept(e); return true; } } return false; } public int characteristics() { return Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.CONCURRENT; } } /** * Returns a {@link Spliterator} over the elements in this deque. * *

The returned spliterator is * weakly consistent. * *

The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}. * * @implNote * The {@code Spliterator} implements {@code trySplit} to permit limited * parallelism. * * @return a {@code Spliterator} over the elements in this deque * @since 1.8 */ public Spliterator spliterator() { return new LBDSpliterator(this); } /** * Saves this deque to a stream (that is, serializes it). * * @param s the stream * @throws java.io.IOException if an I/O error occurs * @serialData The capacity (int), followed by elements (each an * {@code Object}) in the proper order, followed by a null */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { final ReentrantLock lock = this.lock; lock.lock(); try { // Write out capacity and any hidden stuff s.defaultWriteObject(); // Write out all elements in the proper order. for (Node p = first; p != null; p = p.next) s.writeObject(p.item); // Use trailing null as sentinel s.writeObject(null); } finally { lock.unlock(); } } /** * Reconstitutes this deque from a stream (that is, deserializes it). * @param s the stream * @throws ClassNotFoundException if the class of a serialized object * could not be found * @throws java.io.IOException if an I/O error occurs */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { s.defaultReadObject(); count = 0; first = null; last = null; // Read in all elements and place in queue for (;;) { @SuppressWarnings("unchecked") E item = (E)s.readObject(); if (item == null) break; add(item); } } }