16232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson/* 26232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Written by Doug Lea with assistance from members of JCP JSR-166 36232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Expert Group and released to the public domain, as explained at 4a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * http://creativecommons.org/publicdomain/zero/1.0/ 56232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 66232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 76232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonpackage java.util.concurrent; 86232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 96232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.AbstractQueue; 106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.Collection; 116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.Iterator; 126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.NoSuchElementException; 13e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Spliterator; 14e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.Spliterators; 156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.concurrent.locks.Condition; 166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.concurrent.locks.ReentrantLock; 17e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.function.Consumer; 186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 19a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// BEGIN android-note 20a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// removed link to collections framework docs 21a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// END android-note 22a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson/** 246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on 256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * linked nodes. 266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 2791770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * <p>The optional capacity bound constructor argument serves as a 286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * way to prevent excessive expansion. The capacity, if unspecified, 296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * is equal to {@link Integer#MAX_VALUE}. Linked nodes are 306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * dynamically created upon each insertion unless this would bring the 316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * deque above capacity. 326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Most operations run in constant time (ignoring time spent 346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * blocking). Exceptions include {@link #remove(Object) remove}, 356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link 366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * #removeLastOccurrence removeLastOccurrence}, {@link #contains 376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * contains}, {@link #iterator iterator.remove()}, and the bulk 386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * operations, all of which run in linear time. 396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This class and its iterator implement all of the 416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Iterator} interfaces. 436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @since 1.6 456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @author Doug Lea 46e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param <E> the type of elements held in this deque 476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonpublic class LinkedBlockingDeque<E> 496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson extends AbstractQueue<E> 5091770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle implements BlockingDeque<E>, java.io.Serializable { 516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /* 536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Implemented as a simple doubly-linked list protected by a 546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * single lock and using conditions to manage blocking. 556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * To implement weakly consistent iterators, it appears we need to 576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * keep all Nodes GC-reachable from a predecessor dequeued Node. 586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * That would cause two problems: 596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - allow a rogue Iterator to cause unbounded memory retention 606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - cause cross-generational linking of old Nodes to new Nodes if 616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * a Node was tenured while live, which generational GCs have a 626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * hard time dealing with, causing repeated major collections. 636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * However, only non-deleted Nodes need to be reachable from 646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * dequeued Nodes, and reachability does not necessarily have to 656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * be of the kind understood by the GC. We use the trick of 666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * linking a Node that has just been dequeued to itself. Such a 676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * self-link implicitly means to jump to "first" (for next links) 686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * or "last" (for prev links). 696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /* 726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * We have "diamond" multiple interface/abstract class inheritance 736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * here, and that introduces ambiguities. Often we want the 746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * BlockingDeque javadoc combined with the AbstractQueue 756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * implementation, so a lot of method specs are duplicated here. 766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private static final long serialVersionUID = -387911632671998426L; 796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Doubly-linked list node class */ 816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson static final class Node<E> { 826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * The item, or null if this node has been removed. 846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item; 866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * One of: 896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - the real predecessor Node 906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - this Node, meaning the predecessor is tail 916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - null, meaning there is no predecessor 926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> prev; 946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * One of: 976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - the real successor Node 986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - this Node, meaning the successor is head 996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - null, meaning there is no successor 1006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> next; 1026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node(E x) { 1046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson item = x; 1056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Pointer to first node. 1106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: (first == null && last == null) || 1116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (first.prev == null && first.item != null) 1126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson transient Node<E> first; 1146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Pointer to last node. 1176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: (first == null && last == null) || 1186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (last.next == null && last.item != null) 1196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson transient Node<E> last; 1216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Number of items in the deque */ 1236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private transient int count; 1246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Maximum number of items in the deque */ 1266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private final int capacity; 1276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Main lock guarding all access */ 1296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = new ReentrantLock(); 1306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Condition for waiting takes */ 1326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private final Condition notEmpty = lock.newCondition(); 1336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Condition for waiting puts */ 1356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private final Condition notFull = lock.newCondition(); 1366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingDeque} with a capacity of 1396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@link Integer#MAX_VALUE}. 1406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public LinkedBlockingDeque() { 1426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson this(Integer.MAX_VALUE); 1436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity. 1476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param capacity the capacity of this deque 1496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalArgumentException if {@code capacity} is less than 1 1506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public LinkedBlockingDeque(int capacity) { 1526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (capacity <= 0) throw new IllegalArgumentException(); 1536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson this.capacity = capacity; 1546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingDeque} with a capacity of 1586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@link Integer#MAX_VALUE}, initially containing the elements of 1596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * the given collection, added in traversal order of the 1606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * collection's iterator. 1616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param c the collection of elements to initially contain 1636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException if the specified collection or any 1646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * of its elements are null 1656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public LinkedBlockingDeque(Collection<? extends E> c) { 1676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson this(Integer.MAX_VALUE); 1686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 1696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); // Never contended, but necessary for visibility 1706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 1716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (E e : c) { 1726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) 1736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new NullPointerException(); 1748eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (!linkLast(new Node<E>(e))) 1756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException("Deque full"); 1766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 1786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 1796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Basic linking and unlinking operations, called only while holding lock 1846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1868eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Links node as first element, or returns false if full. 1876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1888eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private boolean linkFirst(Node<E> node) { 1896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 1906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (count >= capacity) 1916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 1926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> f = first; 1938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson node.next = f; 1948eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson first = node; 1956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (last == null) 1968eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last = node; 1976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson else 1988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson f.prev = node; 1996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++count; 2006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.signal(); 2016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 2026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Links node as last element, or returns false if full. 2066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2078eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private boolean linkLast(Node<E> node) { 2086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 2096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (count >= capacity) 2106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 2116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> l = last; 2128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson node.prev = l; 2138eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last = node; 2146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (first == null) 2158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson first = node; 2166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson else 2178eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson l.next = node; 2186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++count; 2196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.signal(); 2206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 2216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Removes and returns first element, or null if empty. 2256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private E unlinkFirst() { 2276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 2286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> f = first; 2296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (f == null) 2306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return null; 2316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> n = f.next; 2326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item = f.item; 2336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.item = null; 2346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.next = f; // help GC 2356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson first = n; 2366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (n == null) 2376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson last = null; 2386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson else 2396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson n.prev = null; 2406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson --count; 2416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 2426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return item; 2436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Removes and returns last element, or null if empty. 2476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private E unlinkLast() { 2496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 2506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> l = last; 2516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (l == null) 2526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return null; 2536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> p = l.prev; 2546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item = l.item; 2556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson l.item = null; 2566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson l.prev = l; // help GC 2576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson last = p; 2586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (p == null) 2596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson first = null; 2606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson else 2616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.next = null; 2626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson --count; 2636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 2646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return item; 2656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Unlinks x. 2696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void unlink(Node<E> x) { 2716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 2726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> p = x.prev; 2736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> n = x.next; 2746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (p == null) { 2756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlinkFirst(); 2766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } else if (n == null) { 2776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlinkLast(); 2786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } else { 2796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.next = n; 2806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson n.prev = p; 2816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson x.item = null; 2826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Don't mess with x's links. They may still be in use by 2836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // an iterator. 2846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson --count; 2856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 2866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // BlockingDeque methods 2906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 292e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws IllegalStateException if this deque is full 293e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws NullPointerException {@inheritDoc} 2946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void addFirst(E e) { 2966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (!offerFirst(e)) 2976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException("Deque full"); 2986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 301e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws IllegalStateException if this deque is full 3026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void addLast(E e) { 3056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (!offerLast(e)) 3066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException("Deque full"); 3076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerFirst(E e) { 3136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 3176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3188eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return linkFirst(node); 3196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerLast(E e) { 3286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 3326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return linkLast(node); 3346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 3426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void putFirst(E e) throws InterruptedException { 3446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 3486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3498eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (!linkFirst(node)) 3506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.await(); 3516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 3596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void putLast(E e) throws InterruptedException { 3616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 3656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (!linkLast(node)) 3676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.await(); 3686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 3766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerFirst(E e, long timeout, TimeUnit unit) 3786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 3796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson long nanos = unit.toNanos(timeout); 3826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lockInterruptibly(); 3846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (!linkFirst(node)) { 386e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (nanos <= 0L) 3876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 3886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notFull.awaitNanos(nanos); 3896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 3916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 3996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerLast(E e, long timeout, TimeUnit unit) 4016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 4026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 4038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 4046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson long nanos = unit.toNanos(timeout); 4056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lockInterruptibly(); 4076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4088eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (!linkLast(node)) { 409e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (nanos <= 0L) 4106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 4116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notFull.awaitNanos(nanos); 4126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 4146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 4216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E removeFirst() { 4236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = pollFirst(); 4246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (x == null) throw new NoSuchElementException(); 4256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 4306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E removeLast() { 4326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = pollLast(); 4336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (x == null) throw new NoSuchElementException(); 4346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pollFirst() { 4386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 4406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return unlinkFirst(); 4426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pollLast() { 4486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 4506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return unlinkLast(); 4526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E takeFirst() throws InterruptedException { 4586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 4606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x; 4626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while ( (x = unlinkFirst()) == null) 4636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.await(); 4646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E takeLast() throws InterruptedException { 4716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 4736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x; 4756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while ( (x = unlinkLast()) == null) 4766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.await(); 4776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pollFirst(long timeout, TimeUnit unit) 4846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 4856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson long nanos = unit.toNanos(timeout); 4866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lockInterruptibly(); 4886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x; 4906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while ( (x = unlinkFirst()) == null) { 491e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (nanos <= 0L) 4926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return null; 4936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notEmpty.awaitNanos(nanos); 4946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pollLast(long timeout, TimeUnit unit) 5026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 5036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson long nanos = unit.toNanos(timeout); 5046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lockInterruptibly(); 5066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x; 5086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while ( (x = unlinkLast()) == null) { 509e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (nanos <= 0L) 5106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return null; 5116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notEmpty.awaitNanos(nanos); 5126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 5146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 5206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 5216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E getFirst() { 5236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = peekFirst(); 5246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (x == null) throw new NoSuchElementException(); 5256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 5266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 5296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 5306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E getLast() { 5326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = peekLast(); 5336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (x == null) throw new NoSuchElementException(); 5346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 5356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E peekFirst() { 5386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 5406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return (first == null) ? null : first.item; 5426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E peekLast() { 5486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 5506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return (last == null) ? null : last.item; 5526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean removeFirstOccurrence(Object o) { 5586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o == null) return false; 5596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 5616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) { 5636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o.equals(p.item)) { 5646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p); 5656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 5666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 5696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean removeLastOccurrence(Object o) { 5756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o == null) return false; 5766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 5786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = last; p != null; p = p.prev) { 5806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o.equals(p.item)) { 5816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p); 5826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 5836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 5866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // BlockingQueue methods 5926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 5946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Inserts the specified element at the end of this deque unless it would 5956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * violate capacity restrictions. When using a capacity-restricted deque, 596a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * it is generally preferable to use method {@link #offer(Object) offer}. 5976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 5986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method is equivalent to {@link #addLast}. 5996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 600e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws IllegalStateException if this deque is full 6016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException if the specified element is null 6026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean add(E e) { 6046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson addLast(e); 6056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 6066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException if the specified element is null 6106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offer(E e) { 6126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return offerLast(e); 6136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 6176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 6186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void put(E e) throws InterruptedException { 6206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson putLast(e); 6216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 6256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 6266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) 6286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 6296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return offerLast(e, timeout, unit); 6306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Retrieves and removes the head of the queue represented by this deque. 6346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * This method differs from {@link #poll poll} only in that it throws an 6356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * exception if this deque is empty. 6366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method is equivalent to {@link #removeFirst() removeFirst}. 6386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return the head of the queue represented by this deque 6406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException if this deque is empty 6416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E remove() { 6436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return removeFirst(); 6446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E poll() { 6476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return pollFirst(); 6486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E take() throws InterruptedException { 6516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return takeFirst(); 6526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E poll(long timeout, TimeUnit unit) throws InterruptedException { 6556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return pollFirst(timeout, unit); 6566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Retrieves, but does not remove, the head of the queue represented by 6606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * this deque. This method differs from {@link #peek peek} only in that 6616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * it throws an exception if this deque is empty. 6626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method is equivalent to {@link #getFirst() getFirst}. 6646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return the head of the queue represented by this deque 6666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException if this deque is empty 6676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E element() { 6696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return getFirst(); 6706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E peek() { 6736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return peekFirst(); 6746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns the number of additional elements that this deque can ideally 6786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (in the absence of memory or resource constraints) accept without 6796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * blocking. This is always equal to the initial capacity of this deque 6806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * less the current {@code size} of this deque. 6816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Note that you <em>cannot</em> always tell if an attempt to insert 6836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * an element will succeed by inspecting {@code remainingCapacity} 6846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * because it may be the case that another thread is about to 6856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * insert or remove an element. 6866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public int remainingCapacity() { 6886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 6896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 6906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 6916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return capacity - count; 6926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 6936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 6946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 6996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws ClassCastException {@inheritDoc} 7006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 7016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 7026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public int drainTo(Collection<? super E> c) { 7046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return drainTo(c, Integer.MAX_VALUE); 7056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 7096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws ClassCastException {@inheritDoc} 7106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 7116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 7126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public int drainTo(Collection<? super E> c, int maxElements) { 7146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (c == null) 7156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new NullPointerException(); 7166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (c == this) 7176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalArgumentException(); 718a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (maxElements <= 0) 719a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return 0; 7206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 7216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 7226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 7236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int n = Math.min(maxElements, count); 7246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (int i = 0; i < n; i++) { 7256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c.add(first.item); // In this order, in case add() throws. 7266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlinkFirst(); 7276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return n; 7296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 7306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 7316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Stack methods 7356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 737e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws IllegalStateException if this deque is full 738e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws NullPointerException {@inheritDoc} 7396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void push(E e) { 7416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson addFirst(e); 7426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 7466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pop() { 7486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return removeFirst(); 7496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Collection methods 7526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Removes the first occurrence of the specified element from this deque. 7556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * If the deque does not contain the element, it is unchanged. 7566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * More formally, removes the first element {@code e} such that 7576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code o.equals(e)} (if such an element exists). 7586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns {@code true} if this deque contained the specified element 7596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (or equivalently, if this deque changed as a result of the call). 7606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method is equivalent to 7626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}. 7636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param o element to be removed from this deque, if present 7656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if this deque changed as a result of the call 7666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean remove(Object o) { 7686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return removeFirstOccurrence(o); 7696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns the number of elements in this deque. 7736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return the number of elements in this deque 7756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public int size() { 7776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 7786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 7796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 7806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return count; 7816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 7826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 7836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns {@code true} if this deque contains the specified element. 7886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * More formally, returns {@code true} if and only if this deque contains 7896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 7906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param o object to be checked for containment in this deque 7926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if this deque contains the specified element 7936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean contains(Object o) { 7956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o == null) return false; 7966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 7976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 7986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 7996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) 8006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o.equals(p.item)) 8016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 8026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 8036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 8046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 8056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /* 8096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * TODO: Add support for more efficient bulk operations. 8106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * We don't want to acquire the lock for every iteration, but we 8126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * also want other threads a chance to interact with the 8136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * collection, especially when count is close to capacity. 8146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 8156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// /** 8176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * Adds all of the elements in the specified collection to this 8186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * queue. Attempts to addAll of a queue to itself result in 8196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * {@code IllegalArgumentException}. Further, the behavior of 8206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * this operation is undefined if the specified collection is 8216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * modified while the operation is in progress. 8226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * 8236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @param c collection containing elements to be added to this queue 8246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @return {@code true} if this queue changed as a result of the call 8256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @throws ClassCastException {@inheritDoc} 8266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @throws NullPointerException {@inheritDoc} 8276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @throws IllegalArgumentException {@inheritDoc} 828e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak// * @throws IllegalStateException if this deque is full 8296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @see #add(Object) 8306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// */ 8316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// public boolean addAll(Collection<? extends E> c) { 8326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// if (c == null) 8336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// throw new NullPointerException(); 8346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// if (c == this) 8356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// throw new IllegalArgumentException(); 8366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// final ReentrantLock lock = this.lock; 8376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// lock.lock(); 8386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// try { 8396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// boolean modified = false; 8406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// for (E e : c) 8416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// if (linkLast(e)) 8426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// modified = true; 8436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// return modified; 8446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// } finally { 8456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// lock.unlock(); 8466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// } 8476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// } 8486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 8506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns an array containing all of the elements in this deque, in 8516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * proper sequence (from first to last element). 8526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>The returned array will be "safe" in that no references to it are 8546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * maintained by this deque. (In other words, this method must allocate 8556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * a new array). The caller is thus free to modify the returned array. 8566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method acts as bridge between array-based and collection-based 8586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * APIs. 8596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return an array containing all of the elements in this deque 8616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 8626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 8636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public Object[] toArray() { 8646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 8656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 8666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 8676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Object[] a = new Object[count]; 8686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int k = 0; 8696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) 8706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson a[k++] = p.item; 8716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return a; 8726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 8736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 8746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 8786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns an array containing all of the elements in this deque, in 8796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * proper sequence; the runtime type of the returned array is that of 8806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * the specified array. If the deque fits in the specified array, it 8816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * is returned therein. Otherwise, a new array is allocated with the 8826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * runtime type of the specified array and the size of this deque. 8836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>If this deque fits in the specified array with room to spare 8856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (i.e., the array has more elements than this deque), the element in 8866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * the array immediately following the end of the deque is set to 8876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code null}. 8886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 8906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * array-based and collection-based APIs. Further, this method allows 8916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * precise control over the runtime type of the output array, and may, 8926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * under certain circumstances, be used to save allocation costs. 8936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Suppose {@code x} is a deque known to contain only strings. 8956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * The following code can be used to dump the deque into a newly 8966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * allocated array of {@code String}: 8976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 898e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 8996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 9006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 9016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code toArray()}. 9026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 9036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param a the array into which the elements of the deque are to 9046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 9056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * same runtime type is allocated for this purpose 9066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return an array containing all of the elements in this deque 9076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 9086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * is not a supertype of the runtime type of every element in 9096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * this deque 9106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException if the specified array is null 9116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 9126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 9136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public <T> T[] toArray(T[] a) { 9146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 9156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 9166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 9176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (a.length < count) 9186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson a = (T[])java.lang.reflect.Array.newInstance 9196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson (a.getClass().getComponentType(), count); 9206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int k = 0; 9226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) 9236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson a[k++] = (T)p.item; 9246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (a.length > k) 9256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson a[k] = null; 9266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return a; 9276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 9286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 9296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public String toString() { 933e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return Helpers.collectionToString(this); 9346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 9376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Atomically removes all of the elements from this deque. 9386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * The deque will be empty after this call returns. 9396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 9406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void clear() { 9416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 9426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 9436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 9446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> f = first; f != null; ) { 9456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.item = null; 9466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> n = f.next; 9476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.prev = null; 9486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.next = null; 9496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f = n; 9506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson first = last = null; 9526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson count = 0; 9536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signalAll(); 9546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 9556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 9566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 9606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns an iterator over the elements in this deque in proper sequence. 9616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * The elements will be returned in order from first (head) to last (tail). 9628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 963e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The returned iterator is 964e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 9656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 9666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return an iterator over the elements in this deque in proper sequence 9676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 9686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public Iterator<E> iterator() { 9696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return new Itr(); 9706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 9736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns an iterator over the elements in this deque in reverse 9746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * sequential order. The elements will be returned in order from 9756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * last (tail) to first (head). 9768eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 977e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The returned iterator is 978e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 9798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 9808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return an iterator over the elements in this deque in reverse order 9816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 9826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public Iterator<E> descendingIterator() { 9836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return new DescendingItr(); 9846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 987e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Base class for LinkedBlockingDeque iterators. 9886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 9896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private abstract class AbstractItr implements Iterator<E> { 9906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 991e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * The next node to return in next(). 9926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 993a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node<E> next; 9946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 9966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * nextItem holds on to item fields because once we claim that 9976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * an element exists in hasNext(), we must return item read 9986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * under lock (in advance()) even if it was in the process of 9996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * being removed when hasNext() was called. 10006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 10016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E nextItem; 10026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 10046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Node returned by most recent call to next. Needed by remove. 10056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Reset to null if this element is deleted by a call to remove. 10066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 10076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private Node<E> lastRet; 10086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson abstract Node<E> firstNode(); 10106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson abstract Node<E> nextNode(Node<E> n); 10116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson AbstractItr() { 10136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // set to initial position 10146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = LinkedBlockingDeque.this.lock; 10156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 10166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 10176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson next = firstNode(); 10186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nextItem = (next == null) ? null : next.item; 10196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 10206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 10216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 10258eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns the successor node of the given non-null, but 10268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * possibly previously deleted, node. 10278eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 10288eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private Node<E> succ(Node<E> n) { 10298eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Chains of deleted nodes ending in null or self-links 10308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // are possible if multiple interior nodes are removed. 10318eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (;;) { 10328eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> s = nextNode(n); 10338eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (s == null) 10348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return null; 10358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (s.item != null) 10368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return s; 10378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (s == n) 10388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return firstNode(); 10398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 10408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson n = s; 10418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 10428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 10438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 10448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 10456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Advances next. 10466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 10476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void advance() { 10486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = LinkedBlockingDeque.this.lock; 10496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 10506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 10516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert next != null; 10528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson next = succ(next); 10536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nextItem = (next == null) ? null : next.item; 10546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 10556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 10566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean hasNext() { 10606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return next != null; 10616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E next() { 10646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (next == null) 10656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new NoSuchElementException(); 10666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lastRet = next; 10676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = nextItem; 10686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson advance(); 10696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 10706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void remove() { 10736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> n = lastRet; 10746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (n == null) 10756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException(); 10766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lastRet = null; 10776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = LinkedBlockingDeque.this.lock; 10786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 10796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 10806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (n.item != null) 10816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(n); 10826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 10836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 10846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Forward iterator */ 10896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private class Itr extends AbstractItr { 10906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> firstNode() { return first; } 10916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> nextNode(Node<E> n) { return n.next; } 10926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Descending iterator */ 10956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private class DescendingItr extends AbstractItr { 10966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> firstNode() { return last; } 10976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> nextNode(Node<E> n) { return n.prev; } 10986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1100e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** A customized variant of Spliterators.IteratorSpliterator */ 1101e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak static final class LBDSpliterator<E> implements Spliterator<E> { 1102e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak static final int MAX_BATCH = 1 << 25; // max batch array size; 1103e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final LinkedBlockingDeque<E> queue; 1104e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Node<E> current; // current node; null until initialized 1105e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int batch; // batch size for splits 1106e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak boolean exhausted; // true when no more nodes 1107e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long est; // size estimate 1108e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak LBDSpliterator(LinkedBlockingDeque<E> queue) { 1109e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak this.queue = queue; 1110e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak this.est = queue.size(); 1111e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1112e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1113e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long estimateSize() { return est; } 1114e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1115e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Spliterator<E> trySplit() { 1116e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Node<E> h; 1117e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final LinkedBlockingDeque<E> q = this.queue; 1118e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int b = batch; 1119e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int n = (b <= 0) ? 1 : (b >= MAX_BATCH) ? MAX_BATCH : b + 1; 1120e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!exhausted && 1121e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ((h = current) != null || (h = q.first) != null) && 1122e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak h.next != null) { 1123e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Object[] a = new Object[n]; 1124e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final ReentrantLock lock = q.lock; 1125e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int i = 0; 1126e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Node<E> p = current; 1127e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak lock.lock(); 1128e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak try { 1129e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (p != null || (p = q.first) != null) { 1130e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak do { 1131e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((a[i] = p.item) != null) 1132e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ++i; 1133e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } while ((p = p.next) != null && i < n); 1134e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1135e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } finally { 1136e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak lock.unlock(); 1137e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1138e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((current = p) == null) { 1139e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak est = 0L; 1140e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak exhausted = true; 1141e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1142e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((est -= i) < 0L) 1143e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak est = 0L; 1144e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (i > 0) { 1145e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak batch = i; 1146e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return Spliterators.spliterator 1147e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (a, 0, i, (Spliterator.ORDERED | 1148e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Spliterator.NONNULL | 1149e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Spliterator.CONCURRENT)); 1150e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1151e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1152e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return null; 1153e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1154e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1155e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void forEachRemaining(Consumer<? super E> action) { 1156e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (action == null) throw new NullPointerException(); 1157e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final LinkedBlockingDeque<E> q = this.queue; 1158e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final ReentrantLock lock = q.lock; 1159e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!exhausted) { 1160e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak exhausted = true; 1161e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Node<E> p = current; 1162e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak do { 1163e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak E e = null; 1164e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak lock.lock(); 1165e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak try { 1166e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (p == null) 1167e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak p = q.first; 1168e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while (p != null) { 1169e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak e = p.item; 1170e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak p = p.next; 1171e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (e != null) 1172e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1173e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1174e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } finally { 1175e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak lock.unlock(); 1176e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1177e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (e != null) 1178e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak action.accept(e); 1179e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } while (p != null); 1180e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1181e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1182e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1183e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean tryAdvance(Consumer<? super E> action) { 1184e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (action == null) throw new NullPointerException(); 1185e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final LinkedBlockingDeque<E> q = this.queue; 1186e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final ReentrantLock lock = q.lock; 1187e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!exhausted) { 1188e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak E e = null; 1189e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak lock.lock(); 1190e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak try { 1191e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (current == null) 1192e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak current = q.first; 1193e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while (current != null) { 1194e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak e = current.item; 1195e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak current = current.next; 1196e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (e != null) 1197e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1198e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1199e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } finally { 1200e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak lock.unlock(); 1201e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1202e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (current == null) 1203e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak exhausted = true; 1204e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (e != null) { 1205e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak action.accept(e); 1206e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return true; 1207e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1208e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1209e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return false; 1210e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1211e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1212e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public int characteristics() { 1213e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return Spliterator.ORDERED | Spliterator.NONNULL | 1214e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Spliterator.CONCURRENT; 1215e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1216e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1217e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1218e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 1219e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns a {@link Spliterator} over the elements in this deque. 1220e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 1221e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The returned spliterator is 1222e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1223e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 1224e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, 1225e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}. 1226e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 1227e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @implNote 1228e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * The {@code Spliterator} implements {@code trySplit} to permit limited 1229e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * parallelism. 1230e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 1231e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a {@code Spliterator} over the elements in this deque 1232e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @since 1.8 1233e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 1234e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Spliterator<E> spliterator() { 1235e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return new LBDSpliterator<E>(this); 1236e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1237e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 12386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 123991770798d8b9280d48d30df2ed7f63b3ed9b036fCalin Juravle * Saves this deque to a stream (that is, serializes it). 12406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1241e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param s the stream 1242e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 12436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @serialData The capacity (int), followed by elements (each an 12446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code Object}) in the proper order, followed by a null 12456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 12466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private void writeObject(java.io.ObjectOutputStream s) 12476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws java.io.IOException { 12486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 12496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 12506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 12516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Write out capacity and any hidden stuff 12526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson s.defaultWriteObject(); 12536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Write out all elements in the proper order. 12546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) 12556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson s.writeObject(p.item); 12566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Use trailing null as sentinel 12576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson s.writeObject(null); 12586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 12596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 12606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 12616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 12626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 12636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1264a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Reconstitutes this deque from a stream (that is, deserializes it). 1265e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param s the stream 1266e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws ClassNotFoundException if the class of a serialized object 1267e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * could not be found 1268e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws java.io.IOException if an I/O error occurs 12696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 12706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private void readObject(java.io.ObjectInputStream s) 12716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws java.io.IOException, ClassNotFoundException { 12726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson s.defaultReadObject(); 12736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson count = 0; 12746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson first = null; 12756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson last = null; 12766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Read in all elements and place in queue 12776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (;;) { 12786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 12796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item = (E)s.readObject(); 12806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (item == null) 12816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson break; 12826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson add(item); 12836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 12846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 12856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 12866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson} 1287