1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     3  *

     4  * This code is free software; you can redistribute it and/or modify it

     5  * under the terms of the GNU General Public License version 2 only, as

     6  * published by the Free Software Foundation.  Sun designates this

     7  * particular file as subject to the "Classpath" exception as provided

     8  * by Sun in the LICENSE file that accompanied this code.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    21  * CA 95054 USA or visit www.sun.com if you need additional information or

    22  * have any questions.

    23  */

    24 

    25 /*

    26  * This file is available under and governed by the GNU General Public

    27  * License version 2 only, as published by the Free Software Foundation.

    28  * However, the following notice accompanied the original version of this

    29  * file:

    30  *

    31  * Written by Doug Lea with assistance from members of JCP JSR-166

    32  * Expert Group and released to the public domain, as explained at

    33  * http://creativecommons.org/licenses/publicdomain

    34  */

    35 

    36 package java.util.concurrent;

    37 import java.util.*;

    38 import java.util.concurrent.locks.*;

    39 

    40 /**

    41  * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on

    42  * linked nodes.

    43  *

    44  * <p> The optional capacity bound constructor argument serves as a

    45  * way to prevent excessive expansion. The capacity, if unspecified,

    46  * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are

    47  * dynamically created upon each insertion unless this would bring the

    48  * deque above capacity.

    49  *

    50  * <p>Most operations run in constant time (ignoring time spent

    51  * blocking).  Exceptions include {@link #remove(Object) remove},

    52  * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link

    53  * #removeLastOccurrence removeLastOccurrence}, {@link #contains

    54  * contains}, {@link #iterator iterator.remove()}, and the bulk

    55  * operations, all of which run in linear time.

    56  *

    57  * <p>This class and its iterator implement all of the

    58  * <em>optional</em> methods of the {@link Collection} and {@link

    59  * Iterator} interfaces.

    60  *

    61  * <p>This class is a member of the

    62  * <a href="{@docRoot}/../technotes/guides/collections/index.html">

    63  * Java Collections Framework</a>.

    64  *

    65  * @since 1.6

    66  * @author  Doug Lea

    67  * @param <E> the type of elements held in this collection

    68  */

    69 public class LinkedBlockingDeque<E>

    70     extends AbstractQueue<E>

    71     implements BlockingDeque<E>,  java.io.Serializable {

    72 

    73     /*

    74      * Implemented as a simple doubly-linked list protected by a

    75      * single lock and using conditions to manage blocking.

    76      */

    77 

    78     /*

    79      * We have "diamond" multiple interface/abstract class inheritance

    80      * here, and that introduces ambiguities. Often we want the

    81      * BlockingDeque javadoc combined with the AbstractQueue

    82      * implementation, so a lot of method specs are duplicated here.

    83      */

    84 

    85     private static final long serialVersionUID = -387911632671998426L;

    86 

    87     /** Doubly-linked list node class */

    88     static final class Node<E> {

    89         E item;

    90         Node<E> prev;

    91         Node<E> next;

    92         Node(E x, Node<E> p, Node<E> n) {

    93             item = x;

    94             prev = p;

    95             next = n;

    96         }

    97     }

    98 

    99     /** Pointer to first node */

   100     private transient Node<E> first;

   101     /** Pointer to last node */

   102     private transient Node<E> last;

   103     /** Number of items in the deque */

   104     private transient int count;

   105     /** Maximum number of items in the deque */

   106     private final int capacity;

   107     /** Main lock guarding all access */

   108     private final ReentrantLock lock = new ReentrantLock();

   109     /** Condition for waiting takes */

   110     private final Condition notEmpty = lock.newCondition();

   111     /** Condition for waiting puts */

   112     private final Condition notFull = lock.newCondition();

   113 

   114     /**

   115      * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of

   116      * {@link Integer#MAX_VALUE}.

   117      */

   118     public LinkedBlockingDeque() {

   119         this(Integer.MAX_VALUE);

   120     }

   121 

   122     /**

   123      * Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed) capacity.

   124      *

   125      * @param capacity the capacity of this deque

   126      * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1

   127      */

   128     public LinkedBlockingDeque(int capacity) {

   129         if (capacity <= 0) throw new IllegalArgumentException();

   130         this.capacity = capacity;

   131     }

   132 

   133     /**

   134      * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of

   135      * {@link Integer#MAX_VALUE}, initially containing the elements of

   136      * the given collection, added in traversal order of the

   137      * collection's iterator.

   138      *

   139      * @param c the collection of elements to initially contain

   140      * @throws NullPointerException if the specified collection or any

   141      *         of its elements are null

   142      */

   143     public LinkedBlockingDeque(Collection<? extends E> c) {

   144         this(Integer.MAX_VALUE);

   145         for (E e : c)

   146             add(e);

   147     }

   148 

   149 

   150     // Basic linking and unlinking operations, called only while holding lock

   151 

   152     /**

   153      * Links e as first element, or returns false if full.

   154      */

   155     private boolean linkFirst(E e) {

   156         if (count >= capacity)

   157             return false;

   158         ++count;

   159         Node<E> f = first;

   160         Node<E> x = new Node<E>(e, null, f);

   161         first = x;

   162         if (last == null)

   163             last = x;

   164         else

   165             f.prev = x;

   166         notEmpty.signal();

   167         return true;

   168     }

   169 

   170     /**

   171      * Links e as last element, or returns false if full.

   172      */

   173     private boolean linkLast(E e) {

   174         if (count >= capacity)

   175             return false;

   176         ++count;

   177         Node<E> l = last;

   178         Node<E> x = new Node<E>(e, l, null);

   179         last = x;

   180         if (first == null)

   181             first = x;

   182         else

   183             l.next = x;

   184         notEmpty.signal();

   185         return true;

   186     }

   187 

   188     /**

   189      * Removes and returns first element, or null if empty.

   190      */

   191     private E unlinkFirst() {

   192         Node<E> f = first;

   193         if (f == null)

   194             return null;

   195         Node<E> n = f.next;

   196         first = n;

   197         if (n == null)

   198             last = null;

   199         else

   200             n.prev = null;

   201         --count;

   202         notFull.signal();

   203         return f.item;

   204     }

   205 

   206     /**

   207      * Removes and returns last element, or null if empty.

   208      */

   209     private E unlinkLast() {

   210         Node<E> l = last;

   211         if (l == null)

   212             return null;

   213         Node<E> p = l.prev;

   214         last = p;

   215         if (p == null)

   216             first = null;

   217         else

   218             p.next = null;

   219         --count;

   220         notFull.signal();

   221         return l.item;

   222     }

   223 

   224     /**

   225      * Unlink e

   226      */

   227     private void unlink(Node<E> x) {

   228         Node<E> p = x.prev;

   229         Node<E> n = x.next;

   230         if (p == null) {

   231             if (n == null)

   232                 first = last = null;

   233             else {

   234                 n.prev = null;

   235                 first = n;

   236             }

   237         } else if (n == null) {

   238             p.next = null;

   239             last = p;

   240         } else {

   241             p.next = n;

   242             n.prev = p;

   243         }

   244         --count;

   245         notFull.signalAll();

   246     }

   247 

   248     // BlockingDeque methods

   249 

   250     /**

   251      * @throws IllegalStateException {@inheritDoc}

   252      * @throws NullPointerException  {@inheritDoc}

   253      */

   254     public void addFirst(E e) {

   255         if (!offerFirst(e))

   256             throw new IllegalStateException("Deque full");

   257     }

   258 

   259     /**

   260      * @throws IllegalStateException {@inheritDoc}

   261      * @throws NullPointerException  {@inheritDoc}

   262      */

   263     public void addLast(E e) {

   264         if (!offerLast(e))

   265             throw new IllegalStateException("Deque full");

   266     }

   267 

   268     /**

   269      * @throws NullPointerException {@inheritDoc}

   270      */

   271     public boolean offerFirst(E e) {

   272         if (e == null) throw new NullPointerException();

   273         lock.lock();

   274         try {

   275             return linkFirst(e);

   276         } finally {

   277             lock.unlock();

   278         }

   279     }

   280 

   281     /**

   282      * @throws NullPointerException {@inheritDoc}

   283      */

   284     public boolean offerLast(E e) {

   285         if (e == null) throw new NullPointerException();

   286         lock.lock();

   287         try {

   288             return linkLast(e);

   289         } finally {

   290             lock.unlock();

   291         }

   292     }

   293 

   294     /**

   295      * @throws NullPointerException {@inheritDoc}

   296      * @throws InterruptedException {@inheritDoc}

   297      */

   298     public void putFirst(E e) throws InterruptedException {

   299         if (e == null) throw new NullPointerException();

   300         lock.lock();

   301         try {

   302             while (!linkFirst(e))

   303                 notFull.await();

   304         } finally {

   305             lock.unlock();

   306         }

   307     }

   308 

   309     /**

   310      * @throws NullPointerException {@inheritDoc}

   311      * @throws InterruptedException {@inheritDoc}

   312      */

   313     public void putLast(E e) throws InterruptedException {

   314         if (e == null) throw new NullPointerException();

   315         lock.lock();

   316         try {

   317             while (!linkLast(e))

   318                 notFull.await();

   319         } finally {

   320             lock.unlock();

   321         }

   322     }

   323 

   324     /**

   325      * @throws NullPointerException {@inheritDoc}

   326      * @throws InterruptedException {@inheritDoc}

   327      */

   328     public boolean offerFirst(E e, long timeout, TimeUnit unit)

   329         throws InterruptedException {

   330         if (e == null) throw new NullPointerException();

   331         long nanos = unit.toNanos(timeout);

   332         lock.lockInterruptibly();

   333         try {

   334             for (;;) {

   335                 if (linkFirst(e))

   336                     return true;

   337                 if (nanos <= 0)

   338                     return false;

   339                 nanos = notFull.awaitNanos(nanos);

   340             }

   341         } finally {

   342             lock.unlock();

   343         }

   344     }

   345 

   346     /**

   347      * @throws NullPointerException {@inheritDoc}

   348      * @throws InterruptedException {@inheritDoc}

   349      */

   350     public boolean offerLast(E e, long timeout, TimeUnit unit)

   351         throws InterruptedException {

   352         if (e == null) throw new NullPointerException();

   353         long nanos = unit.toNanos(timeout);

   354         lock.lockInterruptibly();

   355         try {

   356             for (;;) {

   357                 if (linkLast(e))

   358                     return true;

   359                 if (nanos <= 0)

   360                     return false;

   361                 nanos = notFull.awaitNanos(nanos);

   362             }

   363         } finally {

   364             lock.unlock();

   365         }

   366     }

   367 

   368     /**

   369      * @throws NoSuchElementException {@inheritDoc}

   370      */

   371     public E removeFirst() {

   372         E x = pollFirst();

   373         if (x == null) throw new NoSuchElementException();

   374         return x;

   375     }

   376 

   377     /**

   378      * @throws NoSuchElementException {@inheritDoc}

   379      */

   380     public E removeLast() {

   381         E x = pollLast();

   382         if (x == null) throw new NoSuchElementException();

   383         return x;

   384     }

   385 

   386     public E pollFirst() {

   387         lock.lock();

   388         try {

   389             return unlinkFirst();

   390         } finally {

   391             lock.unlock();

   392         }

   393     }

   394 

   395     public E pollLast() {

   396         lock.lock();

   397         try {

   398             return unlinkLast();

   399         } finally {

   400             lock.unlock();

   401         }

   402     }

   403 

   404     public E takeFirst() throws InterruptedException {

   405         lock.lock();

   406         try {

   407             E x;

   408             while ( (x = unlinkFirst()) == null)

   409                 notEmpty.await();

   410             return x;

   411         } finally {

   412             lock.unlock();

   413         }

   414     }

   415 

   416     public E takeLast() throws InterruptedException {

   417         lock.lock();

   418         try {

   419             E x;

   420             while ( (x = unlinkLast()) == null)

   421                 notEmpty.await();

   422             return x;

   423         } finally {

   424             lock.unlock();

   425         }

   426     }

   427 

   428     public E pollFirst(long timeout, TimeUnit unit)

   429         throws InterruptedException {

   430         long nanos = unit.toNanos(timeout);

   431         lock.lockInterruptibly();

   432         try {

   433             for (;;) {

   434                 E x = unlinkFirst();

   435                 if (x != null)

   436                     return x;

   437                 if (nanos <= 0)

   438                     return null;

   439                 nanos = notEmpty.awaitNanos(nanos);

   440             }

   441         } finally {

   442             lock.unlock();

   443         }

   444     }

   445 

   446     public E pollLast(long timeout, TimeUnit unit)

   447         throws InterruptedException {

   448         long nanos = unit.toNanos(timeout);

   449         lock.lockInterruptibly();

   450         try {

   451             for (;;) {

   452                 E x = unlinkLast();

   453                 if (x != null)

   454                     return x;

   455                 if (nanos <= 0)

   456                     return null;

   457                 nanos = notEmpty.awaitNanos(nanos);

   458             }

   459         } finally {

   460             lock.unlock();

   461         }

   462     }

   463 

   464     /**

   465      * @throws NoSuchElementException {@inheritDoc}

   466      */

   467     public E getFirst() {

   468         E x = peekFirst();

   469         if (x == null) throw new NoSuchElementException();

   470         return x;

   471     }

   472 

   473     /**

   474      * @throws NoSuchElementException {@inheritDoc}

   475      */

   476     public E getLast() {

   477         E x = peekLast();

   478         if (x == null) throw new NoSuchElementException();

   479         return x;

   480     }

   481 

   482     public E peekFirst() {

   483         lock.lock();

   484         try {

   485             return (first == null) ? null : first.item;

   486         } finally {

   487             lock.unlock();

   488         }

   489     }

   490 

   491     public E peekLast() {

   492         lock.lock();

   493         try {

   494             return (last == null) ? null : last.item;

   495         } finally {

   496             lock.unlock();

   497         }

   498     }

   499 

   500     public boolean removeFirstOccurrence(Object o) {

   501         if (o == null) return false;

   502         lock.lock();

   503         try {

   504             for (Node<E> p = first; p != null; p = p.next) {

   505                 if (o.equals(p.item)) {

   506                     unlink(p);

   507                     return true;

   508                 }

   509             }

   510             return false;

   511         } finally {

   512             lock.unlock();

   513         }

   514     }

   515 

   516     public boolean removeLastOccurrence(Object o) {

   517         if (o == null) return false;

   518         lock.lock();

   519         try {

   520             for (Node<E> p = last; p != null; p = p.prev) {

   521                 if (o.equals(p.item)) {

   522                     unlink(p);

   523                     return true;

   524                 }

   525             }

   526             return false;

   527         } finally {

   528             lock.unlock();

   529         }

   530     }

   531 

   532     // BlockingQueue methods

   533 

   534     /**

   535      * Inserts the specified element at the end of this deque unless it would

   536      * violate capacity restrictions.  When using a capacity-restricted deque,

   537      * it is generally preferable to use method {@link #offer(Object) offer}.

   538      *

   539      * <p>This method is equivalent to {@link #addLast}.

   540      *

   541      * @throws IllegalStateException if the element cannot be added at this

   542      *         time due to capacity restrictions

   543      * @throws NullPointerException if the specified element is null

   544      */

   545     public boolean add(E e) {

   546         addLast(e);

   547         return true;

   548     }

   549 

   550     /**

   551      * @throws NullPointerException if the specified element is null

   552      */

   553     public boolean offer(E e) {

   554         return offerLast(e);

   555     }

   556 

   557     /**

   558      * @throws NullPointerException {@inheritDoc}

   559      * @throws InterruptedException {@inheritDoc}

   560      */

   561     public void put(E e) throws InterruptedException {

   562         putLast(e);

   563     }

   564 

   565     /**

   566      * @throws NullPointerException {@inheritDoc}

   567      * @throws InterruptedException {@inheritDoc}

   568      */

   569     public boolean offer(E e, long timeout, TimeUnit unit)

   570         throws InterruptedException {

   571         return offerLast(e, timeout, unit);

   572     }

   573 

   574     /**

   575      * Retrieves and removes the head of the queue represented by this deque.

   576      * This method differs from {@link #poll poll} only in that it throws an

   577      * exception if this deque is empty.

   578      *

   579      * <p>This method is equivalent to {@link #removeFirst() removeFirst}.

   580      *

   581      * @return the head of the queue represented by this deque

   582      * @throws NoSuchElementException if this deque is empty

   583      */

   584     public E remove() {

   585         return removeFirst();

   586     }

   587 

   588     public E poll() {

   589         return pollFirst();

   590     }

   591 

   592     public E take() throws InterruptedException {

   593         return takeFirst();

   594     }

   595 

   596     public E poll(long timeout, TimeUnit unit) throws InterruptedException {

   597         return pollFirst(timeout, unit);

   598     }

   599 

   600     /**

   601      * Retrieves, but does not remove, the head of the queue represented by

   602      * this deque.  This method differs from {@link #peek peek} only in that

   603      * it throws an exception if this deque is empty.

   604      *

   605      * <p>This method is equivalent to {@link #getFirst() getFirst}.

   606      *

   607      * @return the head of the queue represented by this deque

   608      * @throws NoSuchElementException if this deque is empty

   609      */

   610     public E element() {

   611         return getFirst();

   612     }

   613 

   614     public E peek() {

   615         return peekFirst();

   616     }

   617 

   618     /**

   619      * Returns the number of additional elements that this deque can ideally

   620      * (in the absence of memory or resource constraints) accept without

   621      * blocking. This is always equal to the initial capacity of this deque

   622      * less the current <tt>size</tt> of this deque.

   623      *

   624      * <p>Note that you <em>cannot</em> always tell if an attempt to insert

   625      * an element will succeed by inspecting <tt>remainingCapacity</tt>

   626      * because it may be the case that another thread is about to

   627      * insert or remove an element.

   628      */

   629     public int remainingCapacity() {

   630         lock.lock();

   631         try {

   632             return capacity - count;

   633         } finally {

   634             lock.unlock();

   635         }

   636     }

   637 

   638     /**

   639      * @throws UnsupportedOperationException {@inheritDoc}

   640      * @throws ClassCastException            {@inheritDoc}

   641      * @throws NullPointerException          {@inheritDoc}

   642      * @throws IllegalArgumentException      {@inheritDoc}

   643      */

   644     public int drainTo(Collection<? super E> c) {

   645         if (c == null)

   646             throw new NullPointerException();

   647         if (c == this)

   648             throw new IllegalArgumentException();

   649         lock.lock();

   650         try {

   651             for (Node<E> p = first; p != null; p = p.next)

   652                 c.add(p.item);

   653             int n = count;

   654             count = 0;

   655             first = last = null;

   656             notFull.signalAll();

   657             return n;

   658         } finally {

   659             lock.unlock();

   660         }

   661     }

   662 

   663     /**

   664      * @throws UnsupportedOperationException {@inheritDoc}

   665      * @throws ClassCastException            {@inheritDoc}

   666      * @throws NullPointerException          {@inheritDoc}

   667      * @throws IllegalArgumentException      {@inheritDoc}

   668      */

   669     public int drainTo(Collection<? super E> c, int maxElements) {

   670         if (c == null)

   671             throw new NullPointerException();

   672         if (c == this)

   673             throw new IllegalArgumentException();

   674         lock.lock();

   675         try {

   676             int n = 0;

   677             while (n < maxElements && first != null) {

   678                 c.add(first.item);

   679                 first.prev = null;

   680                 first = first.next;

   681                 --count;

   682                 ++n;

   683             }

   684             if (first == null)

   685                 last = null;

   686             notFull.signalAll();

   687             return n;

   688         } finally {

   689             lock.unlock();

   690         }

   691     }

   692 

   693     // Stack methods

   694 

   695     /**

   696      * @throws IllegalStateException {@inheritDoc}

   697      * @throws NullPointerException  {@inheritDoc}

   698      */

   699     public void push(E e) {

   700         addFirst(e);

   701     }

   702 

   703     /**

   704      * @throws NoSuchElementException {@inheritDoc}

   705      */

   706     public E pop() {

   707         return removeFirst();

   708     }

   709 

   710     // Collection methods

   711 

   712     /**

   713      * Removes the first occurrence of the specified element from this deque.

   714      * If the deque does not contain the element, it is unchanged.

   715      * More formally, removes the first element <tt>e</tt> such that

   716      * <tt>o.equals(e)</tt> (if such an element exists).

   717      * Returns <tt>true</tt> if this deque contained the specified element

   718      * (or equivalently, if this deque changed as a result of the call).

   719      *

   720      * <p>This method is equivalent to

   721      * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.

   722      *

   723      * @param o element to be removed from this deque, if present

   724      * @return <tt>true</tt> if this deque changed as a result of the call

   725      */

   726     public boolean remove(Object o) {

   727         return removeFirstOccurrence(o);

   728     }

   729 

   730     /**

   731      * Returns the number of elements in this deque.

   732      *

   733      * @return the number of elements in this deque

   734      */

   735     public int size() {

   736         lock.lock();

   737         try {

   738             return count;

   739         } finally {

   740             lock.unlock();

   741         }

   742     }

   743 

   744     /**

   745      * Returns <tt>true</tt> if this deque contains the specified element.

   746      * More formally, returns <tt>true</tt> if and only if this deque contains

   747      * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.

   748      *

   749      * @param o object to be checked for containment in this deque

   750      * @return <tt>true</tt> if this deque contains the specified element

   751      */

   752     public boolean contains(Object o) {

   753         if (o == null) return false;

   754         lock.lock();

   755         try {

   756             for (Node<E> p = first; p != null; p = p.next)

   757                 if (o.equals(p.item))

   758                     return true;

   759             return false;

   760         } finally {

   761             lock.unlock();

   762         }

   763     }

   764 

   765     /**

   766      * Variant of removeFirstOccurrence needed by iterator.remove.

   767      * Searches for the node, not its contents.

   768      */

   769     boolean removeNode(Node<E> e) {

   770         lock.lock();

   771         try {

   772             for (Node<E> p = first; p != null; p = p.next) {

   773                 if (p == e) {

   774                     unlink(p);

   775                     return true;

   776                 }

   777             }

   778             return false;

   779         } finally {

   780             lock.unlock();

   781         }

   782     }

   783 

   784     /**

   785      * Returns an array containing all of the elements in this deque, in

   786      * proper sequence (from first to last element).

   787      *

   788      * <p>The returned array will be "safe" in that no references to it are

   789      * maintained by this deque.  (In other words, this method must allocate

   790      * a new array).  The caller is thus free to modify the returned array.

   791      *

   792      * <p>This method acts as bridge between array-based and collection-based

   793      * APIs.

   794      *

   795      * @return an array containing all of the elements in this deque

   796      */

   797     public Object[] toArray() {

   798         lock.lock();

   799         try {

   800             Object[] a = new Object[count];

   801             int k = 0;

   802             for (Node<E> p = first; p != null; p = p.next)

   803                 a[k++] = p.item;

   804             return a;

   805         } finally {

   806             lock.unlock();

   807         }

   808     }

   809 

   810     /**

   811      * Returns an array containing all of the elements in this deque, in

   812      * proper sequence; the runtime type of the returned array is that of

   813      * the specified array.  If the deque fits in the specified array, it

   814      * is returned therein.  Otherwise, a new array is allocated with the

   815      * runtime type of the specified array and the size of this deque.

   816      *

   817      * <p>If this deque fits in the specified array with room to spare

   818      * (i.e., the array has more elements than this deque), the element in

   819      * the array immediately following the end of the deque is set to

   820      * <tt>null</tt>.

   821      *

   822      * <p>Like the {@link #toArray()} method, this method acts as bridge between

   823      * array-based and collection-based APIs.  Further, this method allows

   824      * precise control over the runtime type of the output array, and may,

   825      * under certain circumstances, be used to save allocation costs.

   826      *

   827      * <p>Suppose <tt>x</tt> is a deque known to contain only strings.

   828      * The following code can be used to dump the deque into a newly

   829      * allocated array of <tt>String</tt>:

   830      *

   831      * <pre>

   832      *     String[] y = x.toArray(new String[0]);</pre>

   833      *

   834      * Note that <tt>toArray(new Object[0])</tt> is identical in function to

   835      * <tt>toArray()</tt>.

   836      *

   837      * @param a the array into which the elements of the deque are to

   838      *          be stored, if it is big enough; otherwise, a new array of the

   839      *          same runtime type is allocated for this purpose

   840      * @return an array containing all of the elements in this deque

   841      * @throws ArrayStoreException if the runtime type of the specified array

   842      *         is not a supertype of the runtime type of every element in

   843      *         this deque

   844      * @throws NullPointerException if the specified array is null

   845      */

   846     public <T> T[] toArray(T[] a) {

   847         lock.lock();

   848         try {

   849             if (a.length < count)

   850                 a = (T[])java.lang.reflect.Array.newInstance(

   851                     a.getClass().getComponentType(),

   852                     count

   853                     );

   854 

   855             int k = 0;

   856             for (Node<E> p = first; p != null; p = p.next)

   857                 a[k++] = (T)p.item;

   858             if (a.length > k)

   859                 a[k] = null;

   860             return a;

   861         } finally {

   862             lock.unlock();

   863         }

   864     }

   865 

   866     public String toString() {

   867         lock.lock();

   868         try {

   869             return super.toString();

   870         } finally {

   871             lock.unlock();

   872         }

   873     }

   874 

   875     /**

   876      * Atomically removes all of the elements from this deque.

   877      * The deque will be empty after this call returns.

   878      */

   879     public void clear() {

   880         lock.lock();

   881         try {

   882             first = last = null;

   883             count = 0;

   884             notFull.signalAll();

   885         } finally {

   886             lock.unlock();

   887         }

   888     }

   889 

   890     /**

   891      * Returns an iterator over the elements in this deque in proper sequence.

   892      * The elements will be returned in order from first (head) to last (tail).

   893      * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that

   894      * will never throw {@link ConcurrentModificationException},

   895      * and guarantees to traverse elements as they existed upon

   896      * construction of the iterator, and may (but is not guaranteed to)

   897      * reflect any modifications subsequent to construction.

   898      *

   899      * @return an iterator over the elements in this deque in proper sequence

   900      */

   901     public Iterator<E> iterator() {

   902         return new Itr();

   903     }

   904 

   905     /**

   906      * Returns an iterator over the elements in this deque in reverse

   907      * sequential order.  The elements will be returned in order from

   908      * last (tail) to first (head).

   909      * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that

   910      * will never throw {@link ConcurrentModificationException},

   911      * and guarantees to traverse elements as they existed upon

   912      * construction of the iterator, and may (but is not guaranteed to)

   913      * reflect any modifications subsequent to construction.

   914      */

   915     public Iterator<E> descendingIterator() {

   916         return new DescendingItr();

   917     }

   918 

   919     /**

   920      * Base class for Iterators for LinkedBlockingDeque

   921      */

   922     private abstract class AbstractItr implements Iterator<E> {

   923         /**

   924          * The next node to return in next

   925          */

   926          Node<E> next;

   927 

   928         /**

   929          * nextItem holds on to item fields because once we claim that

   930          * an element exists in hasNext(), we must return item read

   931          * under lock (in advance()) even if it was in the process of

   932          * being removed when hasNext() was called.

   933          */

   934         E nextItem;

   935 

   936         /**

   937          * Node returned by most recent call to next. Needed by remove.

   938          * Reset to null if this element is deleted by a call to remove.

   939          */

   940         private Node<E> lastRet;

   941 

   942         AbstractItr() {

   943             advance(); // set to initial position

   944         }

   945 

   946         /**

   947          * Advances next, or if not yet initialized, sets to first node.

   948          * Implemented to move forward vs backward in the two subclasses.

   949          */

   950         abstract void advance();

   951 

   952         public boolean hasNext() {

   953             return next != null;

   954         }

   955 

   956         public E next() {

   957             if (next == null)

   958                 throw new NoSuchElementException();

   959             lastRet = next;

   960             E x = nextItem;

   961             advance();

   962             return x;

   963         }

   964 

   965         public void remove() {

   966             Node<E> n = lastRet;

   967             if (n == null)

   968                 throw new IllegalStateException();

   969             lastRet = null;

   970             // Note: removeNode rescans looking for this node to make

   971             // sure it was not already removed. Otherwise, trying to

   972             // re-remove could corrupt list.

   973             removeNode(n);

   974         }

   975     }

   976 

   977     /** Forward iterator */

   978     private class Itr extends AbstractItr {

   979         void advance() {

   980             final ReentrantLock lock = LinkedBlockingDeque.this.lock;

   981             lock.lock();

   982             try {

   983                 next = (next == null)? first : next.next;

   984                 nextItem = (next == null)? null : next.item;

   985             } finally {

   986                 lock.unlock();

   987             }

   988         }

   989     }

   990 

   991     /**

   992      * Descending iterator for LinkedBlockingDeque

   993      */

   994     private class DescendingItr extends AbstractItr {

   995         void advance() {

   996             final ReentrantLock lock = LinkedBlockingDeque.this.lock;

   997             lock.lock();

   998             try {

   999                 next = (next == null)? last : next.prev;

  1000                 nextItem = (next == null)? null : next.item;

  1001             } finally {

  1002                 lock.unlock();

  1003             }

  1004         }

  1005     }

  1006 

  1007     /**

  1008      * Save the state of this deque to a stream (that is, serialize it).

  1009      *

  1010      * @serialData The capacity (int), followed by elements (each an

  1011      * <tt>Object</tt>) in the proper order, followed by a null

  1012      * @param s the stream

  1013      */

  1014     private void writeObject(java.io.ObjectOutputStream s)

  1015         throws java.io.IOException {

  1016         lock.lock();

  1017         try {

  1018             // Write out capacity and any hidden stuff

  1019             s.defaultWriteObject();

  1020             // Write out all elements in the proper order.

  1021             for (Node<E> p = first; p != null; p = p.next)

  1022                 s.writeObject(p.item);

  1023             // Use trailing null as sentinel

  1024             s.writeObject(null);

  1025         } finally {

  1026             lock.unlock();

  1027         }

  1028     }

  1029 

  1030     /**

  1031      * Reconstitute this deque from a stream (that is,

  1032      * deserialize it).

  1033      * @param s the stream

  1034      */

  1035     private void readObject(java.io.ObjectInputStream s)

  1036         throws java.io.IOException, ClassNotFoundException {

  1037         s.defaultReadObject();

  1038         count = 0;

  1039         first = null;

  1040         last = null;

  1041         // Read in all elements and place in queue

  1042         for (;;) {

  1043             E item = (E)s.readObject();

  1044             if (item == null)

  1045                 break;

  1046             add(item);

  1047         }

  1048     }

  1049 

  1050 }