LinkedBlockingDeque.java revision a807b4d808d2591894daf13aab179b2e9c46a2f5
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; 136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.concurrent.locks.Condition; 146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonimport java.util.concurrent.locks.ReentrantLock; 156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 16a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// BEGIN android-note 17a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// removed link to collections framework docs 18a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson// END android-note 19a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson 206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson/** 216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on 226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * linked nodes. 236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p> The optional capacity bound constructor argument serves as a 256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * way to prevent excessive expansion. The capacity, if unspecified, 266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * is equal to {@link Integer#MAX_VALUE}. Linked nodes are 276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * dynamically created upon each insertion unless this would bring the 286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * deque above capacity. 296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Most operations run in constant time (ignoring time spent 316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * blocking). Exceptions include {@link #remove(Object) remove}, 326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link 336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * #removeLastOccurrence removeLastOccurrence}, {@link #contains 346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * contains}, {@link #iterator iterator.remove()}, and the bulk 356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * operations, all of which run in linear time. 366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This class and its iterator implement all of the 386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <em>optional</em> methods of the {@link Collection} and {@link 396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Iterator} interfaces. 406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @since 1.6 426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @author Doug Lea 436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param <E> the type of elements held in this collection 446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilsonpublic class LinkedBlockingDeque<E> 466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson extends AbstractQueue<E> 476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson implements BlockingDeque<E>, java.io.Serializable { 486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /* 506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Implemented as a simple doubly-linked list protected by a 516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * single lock and using conditions to manage blocking. 526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * To implement weakly consistent iterators, it appears we need to 546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * keep all Nodes GC-reachable from a predecessor dequeued Node. 556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * That would cause two problems: 566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - allow a rogue Iterator to cause unbounded memory retention 576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - cause cross-generational linking of old Nodes to new Nodes if 586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * a Node was tenured while live, which generational GCs have a 596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * hard time dealing with, causing repeated major collections. 606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * However, only non-deleted Nodes need to be reachable from 616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * dequeued Nodes, and reachability does not necessarily have to 626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * be of the kind understood by the GC. We use the trick of 636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * linking a Node that has just been dequeued to itself. Such a 646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * self-link implicitly means to jump to "first" (for next links) 656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * or "last" (for prev links). 666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /* 696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * We have "diamond" multiple interface/abstract class inheritance 706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * here, and that introduces ambiguities. Often we want the 716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * BlockingDeque javadoc combined with the AbstractQueue 726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * implementation, so a lot of method specs are duplicated here. 736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private static final long serialVersionUID = -387911632671998426L; 766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Doubly-linked list node class */ 786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson static final class Node<E> { 796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * The item, or null if this node has been removed. 816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item; 836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * One of: 866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - the real predecessor Node 876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - this Node, meaning the predecessor is tail 886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - null, meaning there is no predecessor 896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> prev; 916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * One of: 946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - the real successor Node 956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - this Node, meaning the successor is head 966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * - null, meaning there is no successor 976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> next; 996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node(E x) { 1016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson item = x; 1026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Pointer to first node. 1076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: (first == null && last == null) || 1086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (first.prev == null && first.item != null) 1096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson transient Node<E> first; 1116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Pointer to last node. 1146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Invariant: (first == null && last == null) || 1156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (last.next == null && last.item != null) 1166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson transient Node<E> last; 1186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Number of items in the deque */ 1206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private transient int count; 1216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Maximum number of items in the deque */ 1236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private final int capacity; 1246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Main lock guarding all access */ 1266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = new ReentrantLock(); 1276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Condition for waiting takes */ 1296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private final Condition notEmpty = lock.newCondition(); 1306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Condition for waiting puts */ 1326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private final Condition notFull = lock.newCondition(); 1336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingDeque} with a capacity of 1366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@link Integer#MAX_VALUE}. 1376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public LinkedBlockingDeque() { 1396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson this(Integer.MAX_VALUE); 1406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity. 1446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param capacity the capacity of this deque 1466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalArgumentException if {@code capacity} is less than 1 1476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public LinkedBlockingDeque(int capacity) { 1496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (capacity <= 0) throw new IllegalArgumentException(); 1506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson this.capacity = capacity; 1516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Creates a {@code LinkedBlockingDeque} with a capacity of 1556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@link Integer#MAX_VALUE}, initially containing the elements of 1566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * the given collection, added in traversal order of the 1576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * collection's iterator. 1586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 1596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param c the collection of elements to initially contain 1606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException if the specified collection or any 1616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * of its elements are null 1626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public LinkedBlockingDeque(Collection<? extends E> c) { 1646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson this(Integer.MAX_VALUE); 1656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 1666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); // Never contended, but necessary for visibility 1676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 1686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (E e : c) { 1696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) 1706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new NullPointerException(); 1718eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (!linkLast(new Node<E>(e))) 1726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException("Deque full"); 1736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 1756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 1766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 1786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Basic linking and unlinking operations, called only while holding lock 1816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 1826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Links node as first element, or returns false if full. 1846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private boolean linkFirst(Node<E> node) { 1866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 1876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (count >= capacity) 1886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 1896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> f = first; 1908eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson node.next = f; 1918eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson first = node; 1926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (last == null) 1938eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last = node; 1946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson else 1958eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson f.prev = node; 1966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++count; 1976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.signal(); 1986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 1996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Links node as last element, or returns false if full. 2036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private boolean linkLast(Node<E> node) { 2056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 2066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (count >= capacity) 2076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 2086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> l = last; 2098eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson node.prev = l; 2108eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson last = node; 2116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (first == null) 2128eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson first = node; 2136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson else 2148eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson l.next = node; 2156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson ++count; 2166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.signal(); 2176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 2186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Removes and returns first element, or null if empty. 2226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private E unlinkFirst() { 2246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 2256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> f = first; 2266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (f == null) 2276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return null; 2286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> n = f.next; 2296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item = f.item; 2306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.item = null; 2316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.next = f; // help GC 2326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson first = n; 2336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (n == null) 2346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson last = null; 2356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson else 2366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson n.prev = null; 2376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson --count; 2386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 2396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return item; 2406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Removes and returns last element, or null if empty. 2446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private E unlinkLast() { 2466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 2476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> l = last; 2486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (l == null) 2496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return null; 2506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> p = l.prev; 2516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item = l.item; 2526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson l.item = null; 2536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson l.prev = l; // help GC 2546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson last = p; 2556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (p == null) 2566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson first = null; 2576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson else 2586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.next = null; 2596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson --count; 2606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 2616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return item; 2626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Unlinks x. 2666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void unlink(Node<E> x) { 2686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert lock.isHeldByCurrentThread(); 2696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> p = x.prev; 2706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> n = x.next; 2716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (p == null) { 2726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlinkFirst(); 2736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } else if (n == null) { 2746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlinkLast(); 2756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } else { 2766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson p.next = n; 2776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson n.prev = p; 2786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson x.item = null; 2796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Don't mess with x's links. They may still be in use by 2806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // an iterator. 2816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson --count; 2826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signal(); 2836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // BlockingDeque methods 2876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalStateException {@inheritDoc} 2906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 2916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 2926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void addFirst(E e) { 2936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (!offerFirst(e)) 2946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException("Deque full"); 2956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 2966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 2976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 2986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalStateException {@inheritDoc} 2996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void addLast(E e) { 3026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (!offerLast(e)) 3036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException("Deque full"); 3046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerFirst(E e) { 3106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3118eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 3146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3158eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return linkFirst(node); 3166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerLast(E e) { 3256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3268eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 3296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3308eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return linkLast(node); 3316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 3396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void putFirst(E e) throws InterruptedException { 3416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 3456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (!linkFirst(node)) 3476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.await(); 3486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 3566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void putLast(E e) throws InterruptedException { 3586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 3626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (!linkLast(node)) 3646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.await(); 3656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 3736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerFirst(E e, long timeout, TimeUnit unit) 3756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 3766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 3778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 3786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson long nanos = unit.toNanos(timeout); 3796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 3806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lockInterruptibly(); 3816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 3828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (!linkFirst(node)) { 3836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (nanos <= 0) 3846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 3856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notFull.awaitNanos(nanos); 3866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 3886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 3896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 3906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 3926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 3936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 3946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 3956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 3966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 3976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offerLast(E e, long timeout, TimeUnit unit) 3986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 3996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (e == null) throw new NullPointerException(); 4008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> node = new Node<E>(e); 4016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson long nanos = unit.toNanos(timeout); 4026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lockInterruptibly(); 4046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson while (!linkLast(node)) { 4066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (nanos <= 0) 4076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 4086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notFull.awaitNanos(nanos); 4096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 4116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 4186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E removeFirst() { 4206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = pollFirst(); 4216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (x == null) throw new NoSuchElementException(); 4226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 4266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 4276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 4286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E removeLast() { 4296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = pollLast(); 4306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (x == null) throw new NoSuchElementException(); 4316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pollFirst() { 4356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 4376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return unlinkFirst(); 4396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pollLast() { 4456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 4476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return unlinkLast(); 4496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E takeFirst() throws InterruptedException { 4556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 4576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x; 4596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while ( (x = unlinkFirst()) == null) 4606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.await(); 4616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E takeLast() throws InterruptedException { 4686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 4706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x; 4726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while ( (x = unlinkLast()) == null) 4736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notEmpty.await(); 4746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pollFirst(long timeout, TimeUnit unit) 4816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 4826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson long nanos = unit.toNanos(timeout); 4836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 4846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lockInterruptibly(); 4856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 4866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x; 4876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while ( (x = unlinkFirst()) == null) { 4886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (nanos <= 0) 4896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return null; 4906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notEmpty.awaitNanos(nanos); 4916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 4936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 4946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 4956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 4976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 4986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pollLast(long timeout, TimeUnit unit) 4996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 5006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson long nanos = unit.toNanos(timeout); 5016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lockInterruptibly(); 5036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x; 5056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson while ( (x = unlinkLast()) == null) { 5066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (nanos <= 0) 5076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return null; 5086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nanos = notEmpty.awaitNanos(nanos); 5096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 5116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 5176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 5186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E getFirst() { 5206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = peekFirst(); 5216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (x == null) throw new NoSuchElementException(); 5226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 5236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 5266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 5276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 5286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E getLast() { 5296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = peekLast(); 5306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (x == null) throw new NoSuchElementException(); 5316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 5326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E peekFirst() { 5356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 5376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return (first == null) ? null : first.item; 5396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E peekLast() { 5456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 5476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return (last == null) ? null : last.item; 5496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean removeFirstOccurrence(Object o) { 5556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o == null) return false; 5566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 5586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) { 5606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o.equals(p.item)) { 5616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p); 5626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 5636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 5666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean removeLastOccurrence(Object o) { 5726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o == null) return false; 5736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 5746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 5756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 5766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = last; p != null; p = p.prev) { 5776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o.equals(p.item)) { 5786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(p); 5796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 5806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 5836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 5846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 5856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 5876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // BlockingQueue methods 5896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 5906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 5916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Inserts the specified element at the end of this deque unless it would 5926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * violate capacity restrictions. When using a capacity-restricted deque, 593a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * it is generally preferable to use method {@link #offer(Object) offer}. 5946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 5956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method is equivalent to {@link #addLast}. 5966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 5976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalStateException if the element cannot be added at this 5986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * time due to capacity restrictions 5996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException if the specified element is null 6006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean add(E e) { 6026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson addLast(e); 6036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 6046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException if the specified element is null 6086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offer(E e) { 6106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return offerLast(e); 6116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 6156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 6166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void put(E e) throws InterruptedException { 6186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson putLast(e); 6196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 6236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws InterruptedException {@inheritDoc} 6246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean offer(E e, long timeout, TimeUnit unit) 6266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws InterruptedException { 6276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return offerLast(e, timeout, unit); 6286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Retrieves and removes the head of the queue represented by this deque. 6326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * This method differs from {@link #poll poll} only in that it throws an 6336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * exception if this deque is empty. 6346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method is equivalent to {@link #removeFirst() removeFirst}. 6366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return the head of the queue represented by this deque 6386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException if this deque is empty 6396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E remove() { 6416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return removeFirst(); 6426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E poll() { 6456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return pollFirst(); 6466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E take() throws InterruptedException { 6496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return takeFirst(); 6506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E poll(long timeout, TimeUnit unit) throws InterruptedException { 6536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return pollFirst(timeout, unit); 6546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Retrieves, but does not remove, the head of the queue represented by 6586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * this deque. This method differs from {@link #peek peek} only in that 6596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * it throws an exception if this deque is empty. 6606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method is equivalent to {@link #getFirst() getFirst}. 6626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return the head of the queue represented by this deque 6646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException if this deque is empty 6656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E element() { 6676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return getFirst(); 6686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E peek() { 6716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return peekFirst(); 6726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns the number of additional elements that this deque can ideally 6766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (in the absence of memory or resource constraints) accept without 6776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * blocking. This is always equal to the initial capacity of this deque 6786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * less the current {@code size} of this deque. 6796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 6806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Note that you <em>cannot</em> always tell if an attempt to insert 6816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * an element will succeed by inspecting {@code remainingCapacity} 6826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * because it may be the case that another thread is about to 6836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * insert or remove an element. 6846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 6856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public int remainingCapacity() { 6866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 6876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 6886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 6896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return capacity - count; 6906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 6916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 6926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 6946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 6956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 6966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 6976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws ClassCastException {@inheritDoc} 6986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 6996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 7006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public int drainTo(Collection<? super E> c) { 7026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return drainTo(c, Integer.MAX_VALUE); 7036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws UnsupportedOperationException {@inheritDoc} 7076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws ClassCastException {@inheritDoc} 7086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 7096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalArgumentException {@inheritDoc} 7106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public int drainTo(Collection<? super E> c, int maxElements) { 7126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (c == null) 7136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new NullPointerException(); 7146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (c == this) 7156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalArgumentException(); 716a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson if (maxElements <= 0) 717a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson return 0; 7186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 7196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 7206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 7216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int n = Math.min(maxElements, count); 7226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (int i = 0; i < n; i++) { 7236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson c.add(first.item); // In this order, in case add() throws. 7246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlinkFirst(); 7256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return n; 7276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 7286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 7296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Stack methods 7336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws IllegalStateException {@inheritDoc} 7366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException {@inheritDoc} 7376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void push(E e) { 7396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson addFirst(e); 7406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NoSuchElementException {@inheritDoc} 7446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E pop() { 7466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return removeFirst(); 7476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Collection methods 7506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Removes the first occurrence of the specified element from this deque. 7536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * If the deque does not contain the element, it is unchanged. 7546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * More formally, removes the first element {@code e} such that 7556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code o.equals(e)} (if such an element exists). 7566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns {@code true} if this deque contained the specified element 7576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (or equivalently, if this deque changed as a result of the call). 7586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method is equivalent to 7606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}. 7616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param o element to be removed from this deque, if present 7636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if this deque changed as a result of the call 7646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean remove(Object o) { 7666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return removeFirstOccurrence(o); 7676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns the number of elements in this deque. 7716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return the number of elements in this deque 7736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public int size() { 7756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 7766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 7776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 7786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return count; 7796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 7806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 7816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 7836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 7846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 7856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns {@code true} if this deque contains the specified element. 7866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * More formally, returns {@code true} if and only if this deque contains 7876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * at least one element {@code e} such that {@code o.equals(e)}. 7886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 7896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param o object to be checked for containment in this deque 7906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return {@code true} if this deque contains the specified element 7916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 7926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean contains(Object o) { 7936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o == null) return false; 7946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 7956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 7966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 7976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) 7986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (o.equals(p.item)) 7996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return true; 8006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return false; 8016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 8026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 8036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /* 8076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * TODO: Add support for more efficient bulk operations. 8086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * We don't want to acquire the lock for every iteration, but we 8106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * also want other threads a chance to interact with the 8116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * collection, especially when count is close to capacity. 8126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 8136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// /** 8156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * Adds all of the elements in the specified collection to this 8166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * queue. Attempts to addAll of a queue to itself result in 8176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * {@code IllegalArgumentException}. Further, the behavior of 8186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * this operation is undefined if the specified collection is 8196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * modified while the operation is in progress. 8206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * 8216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @param c collection containing elements to be added to this queue 8226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @return {@code true} if this queue changed as a result of the call 8236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @throws ClassCastException {@inheritDoc} 8246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @throws NullPointerException {@inheritDoc} 8256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @throws IllegalArgumentException {@inheritDoc} 8266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @throws IllegalStateException {@inheritDoc} 8276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// * @see #add(Object) 8286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// */ 8296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// public boolean addAll(Collection<? extends E> c) { 8306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// if (c == null) 8316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// throw new NullPointerException(); 8326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// if (c == this) 8336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// throw new IllegalArgumentException(); 8346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// final ReentrantLock lock = this.lock; 8356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// lock.lock(); 8366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// try { 8376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// boolean modified = false; 8386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// for (E e : c) 8396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// if (linkLast(e)) 8406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// modified = true; 8416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// return modified; 8426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// } finally { 8436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// lock.unlock(); 8446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// } 8456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson// } 8466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 8486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns an array containing all of the elements in this deque, in 8496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * proper sequence (from first to last element). 8506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>The returned array will be "safe" in that no references to it are 8526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * maintained by this deque. (In other words, this method must allocate 8536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * a new array). The caller is thus free to modify the returned array. 8546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>This method acts as bridge between array-based and collection-based 8566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * APIs. 8576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return an array containing all of the elements in this deque 8596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 8606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 8616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public Object[] toArray() { 8626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 8636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 8646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 8656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Object[] a = new Object[count]; 8666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int k = 0; 8676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) 8686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson a[k++] = p.item; 8696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return a; 8706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 8716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 8726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 8746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 8756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 8766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns an array containing all of the elements in this deque, in 8776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * proper sequence; the runtime type of the returned array is that of 8786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * the specified array. If the deque fits in the specified array, it 8796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * is returned therein. Otherwise, a new array is allocated with the 8806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * runtime type of the specified array and the size of this deque. 8816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>If this deque fits in the specified array with room to spare 8836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * (i.e., the array has more elements than this deque), the element in 8846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * the array immediately following the end of the deque is set to 8856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code null}. 8866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Like the {@link #toArray()} method, this method acts as bridge between 8886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * array-based and collection-based APIs. Further, this method allows 8896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * precise control over the runtime type of the output array, and may, 8906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * under certain circumstances, be used to save allocation costs. 8916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * <p>Suppose {@code x} is a deque known to contain only strings. 8936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * The following code can be used to dump the deque into a newly 8946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * allocated array of {@code String}: 8956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 896a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 8976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 8986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Note that {@code toArray(new Object[0])} is identical in function to 8996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code toArray()}. 9006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 9016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param a the array into which the elements of the deque are to 9026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * be stored, if it is big enough; otherwise, a new array of the 9036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * same runtime type is allocated for this purpose 9046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return an array containing all of the elements in this deque 9056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws ArrayStoreException if the runtime type of the specified array 9066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * is not a supertype of the runtime type of every element in 9076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * this deque 9086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @throws NullPointerException if the specified array is null 9096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 9106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 9116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public <T> T[] toArray(T[] a) { 9126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 9136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 9146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 9156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (a.length < count) 9166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson a = (T[])java.lang.reflect.Array.newInstance 9176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson (a.getClass().getComponentType(), count); 9186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson int k = 0; 9206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) 9216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson a[k++] = (T)p.item; 9226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (a.length > k) 9236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson a[k] = null; 9246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return a; 9256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 9266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 9276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public String toString() { 9316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 9326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 9336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 9348eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> p = first; 9358eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p == null) 9368eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return "[]"; 9378eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 9388eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson StringBuilder sb = new StringBuilder(); 9398eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append('['); 9408eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (;;) { 9418eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson E e = p.item; 9428eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(e == this ? "(this Collection)" : e); 9438eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson p = p.next; 9448eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (p == null) 9458eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return sb.append(']').toString(); 9468eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson sb.append(',').append(' '); 9478eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 9486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 9496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 9506232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9516232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 9546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Atomically removes all of the elements from this deque. 9556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * The deque will be empty after this call returns. 9566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 9576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void clear() { 9586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 9596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 9606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 9616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> f = first; f != null; ) { 9626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.item = null; 9636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> n = f.next; 9646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.prev = null; 9656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f.next = null; 9666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson f = n; 9676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson first = last = null; 9696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson count = 0; 9706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson notFull.signalAll(); 9716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 9726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 9736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 9776232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns an iterator over the elements in this deque in proper sequence. 9786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * The elements will be returned in order from first (head) to last (tail). 9798eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 9808eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>The returned iterator is a "weakly consistent" iterator that 9816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * will never throw {@link java.util.ConcurrentModificationException 9828eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * ConcurrentModificationException}, and guarantees to traverse 9838eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * elements as they existed upon construction of the iterator, and 9848eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * may (but is not guaranteed to) reflect any modifications 9858eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * subsequent to construction. 9866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 9876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @return an iterator over the elements in this deque in proper sequence 9886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 9896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public Iterator<E> iterator() { 9906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return new Itr(); 9916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 9926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 9936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 9946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Returns an iterator over the elements in this deque in reverse 9956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * sequential order. The elements will be returned in order from 9966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * last (tail) to first (head). 9978eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 9988eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * <p>The returned iterator is a "weakly consistent" iterator that 9996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * will never throw {@link java.util.ConcurrentModificationException 10008eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * ConcurrentModificationException}, and guarantees to traverse 10018eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * elements as they existed upon construction of the iterator, and 10028eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * may (but is not guaranteed to) reflect any modifications 10038eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * subsequent to construction. 10048eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * 10058eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * @return an iterator over the elements in this deque in reverse order 10066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 10076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public Iterator<E> descendingIterator() { 10086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return new DescendingItr(); 10096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 10126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Base class for Iterators for LinkedBlockingDeque 10136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 10146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private abstract class AbstractItr implements Iterator<E> { 10156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 10166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * The next node to return in next() 10176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 1018a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson Node<E> next; 10196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 10216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * nextItem holds on to item fields because once we claim that 10226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * an element exists in hasNext(), we must return item read 10236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * under lock (in advance()) even if it was in the process of 10246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * being removed when hasNext() was called. 10256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 10266232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E nextItem; 10276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 10296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Node returned by most recent call to next. Needed by remove. 10306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Reset to null if this element is deleted by a call to remove. 10316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 10326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private Node<E> lastRet; 10336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson abstract Node<E> firstNode(); 10356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson abstract Node<E> nextNode(Node<E> n); 10366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson AbstractItr() { 10386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // set to initial position 10396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = LinkedBlockingDeque.this.lock; 10406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 10416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 10426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson next = firstNode(); 10436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nextItem = (next == null) ? null : next.item; 10446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 10456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 10466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 10508eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * Returns the successor node of the given non-null, but 10518eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson * possibly previously deleted, node. 10528eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson */ 10538eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson private Node<E> succ(Node<E> n) { 10548eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // Chains of deleted nodes ending in null or self-links 10558eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson // are possible if multiple interior nodes are removed. 10568eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson for (;;) { 10578eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson Node<E> s = nextNode(n); 10588eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson if (s == null) 10598eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return null; 10608eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (s.item != null) 10618eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return s; 10628eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else if (s == n) 10638eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson return firstNode(); 10648eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson else 10658eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson n = s; 10668eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 10678eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson } 10688eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson 10698eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson /** 10706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * Advances next. 10716232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 10726232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson void advance() { 10736232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = LinkedBlockingDeque.this.lock; 10746232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 10756232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 10766232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // assert next != null; 10778eb35c835be1345d3873a82cc9e42f944d698afdJesse Wilson next = succ(next); 10786232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson nextItem = (next == null) ? null : next.item; 10796232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 10806232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 10816232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10826232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10836232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10846232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public boolean hasNext() { 10856232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return next != null; 10866232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10876232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10886232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public E next() { 10896232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (next == null) 10906232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new NoSuchElementException(); 10916232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lastRet = next; 10926232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E x = nextItem; 10936232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson advance(); 10946232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson return x; 10956232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 10966232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 10976232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson public void remove() { 10986232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> n = lastRet; 10996232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (n == null) 11006232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throw new IllegalStateException(); 11016232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lastRet = null; 11026232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = LinkedBlockingDeque.this.lock; 11036232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 11046232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 11056232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (n.item != null) 11066232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson unlink(n); 11076232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 11086232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 11096232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 11106232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 11116232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 11126232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 11136232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Forward iterator */ 11146232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private class Itr extends AbstractItr { 11156232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> firstNode() { return first; } 11166232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> nextNode(Node<E> n) { return n.next; } 11176232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 11186232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 11196232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** Descending iterator */ 11206232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private class DescendingItr extends AbstractItr { 11216232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> firstNode() { return last; } 11226232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson Node<E> nextNode(Node<E> n) { return n.prev; } 11236232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 11246232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 11256232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1126a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Saves the state of this deque to a stream (that is, serializes it). 11276232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * 11286232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @serialData The capacity (int), followed by elements (each an 11296232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * {@code Object}) in the proper order, followed by a null 11306232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param s the stream 11316232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 11326232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private void writeObject(java.io.ObjectOutputStream s) 11336232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws java.io.IOException { 11346232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson final ReentrantLock lock = this.lock; 11356232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.lock(); 11366232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson try { 11376232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Write out capacity and any hidden stuff 11386232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson s.defaultWriteObject(); 11396232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Write out all elements in the proper order. 11406232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (Node<E> p = first; p != null; p = p.next) 11416232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson s.writeObject(p.item); 11426232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Use trailing null as sentinel 11436232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson s.writeObject(null); 11446232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } finally { 11456232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson lock.unlock(); 11466232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 11476232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 11486232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 11496232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson /** 1150a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * Reconstitutes this deque from a stream (that is, deserializes it). 1151a807b4d808d2591894daf13aab179b2e9c46a2f5Jesse Wilson * 11526232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson * @param s the stream 11536232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson */ 11546232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson private void readObject(java.io.ObjectInputStream s) 11556232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson throws java.io.IOException, ClassNotFoundException { 11566232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson s.defaultReadObject(); 11576232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson count = 0; 11586232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson first = null; 11596232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson last = null; 11606232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson // Read in all elements and place in queue 11616232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson for (;;) { 11626232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson @SuppressWarnings("unchecked") 11636232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson E item = (E)s.readObject(); 11646232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson if (item == null) 11656232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson break; 11666232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson add(item); 11676232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 11686232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson } 11696232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson 11706232a5efed0ea103e35aec73206e5e03a8b82e0cJesse Wilson} 1171