lib/classpath/external/jsr166/java/util/concurrent/LinkedBlockingDeque.java

   1 /*
   2  * Written by Doug Lea with assistance from members of JCP JSR-166
   3  * Expert Group and released to the public domain, as explained at
   4  * http://creativecommons.org/licenses/publicdomain
   5  */
   6
   7 package java.util.concurrent;
   8 import java.util.*;
   9 import java.util.concurrent.locks.*;
  10
  11 /**
  12  * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
  13  * linked nodes.
  14  *
  15  * <p> The optional capacity bound constructor argument serves as a
  16  * way to prevent excessive expansion. The capacity, if unspecified,
  17  * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are
  18  * dynamically created upon each insertion unless this would bring the
  19  * deque above capacity.
  20  *
  21  * <p>Most operations run in constant time (ignoring time spent
  22  * blocking).  Exceptions include {@link #remove(Object) remove},
  23  * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
  24  * #removeLastOccurrence removeLastOccurrence}, {@link #contains
  25  * contains}, {@link #iterator iterator.remove()}, and the bulk
  26  * operations, all of which run in linear time.
  27  *
  28  * <p>This class and its iterator implement all of the
  29  * <em>optional</em> methods of the {@link Collection} and {@link
  30  * Iterator} interfaces.
  31  *
  32  * <p>This class is a member of the
  33  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  34  * Java Collections Framework</a>.
  35  *
  36  * @since 1.6
  37  * @author  Doug Lea
  38  * @param <E> the type of elements held in this collection
  39  */
  40 public class LinkedBlockingDeque<E>
  41     extends AbstractQueue<E>
  42     implements BlockingDeque<E>,  java.io.Serializable {
  43
  44     /*
  45      * Implemented as a simple doubly-linked list protected by a
  46      * single lock and using conditions to manage blocking.
  47      */
  48
  49     /*
  50      * We have "diamond" multiple interface/abstract class inheritance
  51      * here, and that introduces ambiguities. Often we want the
  52      * BlockingDeque javadoc combined with the AbstractQueue
  53      * implementation, so a lot of method specs are duplicated here.
  54      */
  55
  56     private static final long serialVersionUID = -387911632671998426L;
  57
  58     /** Doubly-linked list node class */
  59     static final class Node<E> {
  60         E item;
  61         Node<E> prev;
  62         Node<E> next;
  63         Node(E x, Node<E> p, Node<E> n) {
  64             item = x;
  65             prev = p;
  66             next = n;
  67         }
  68     }
  69
  70     /** Pointer to first node */
  71     private transient Node<E> first;
  72     /** Pointer to last node */
  73     private transient Node<E> last;
  74     /** Number of items in the deque */
  75     private transient int count;
  76     /** Maximum number of items in the deque */
  77     private final int capacity;
  78     /** Main lock guarding all access */
  79     private final ReentrantLock lock = new ReentrantLock();
  80     /** Condition for waiting takes */
  81     private final Condition notEmpty = lock.newCondition();
  82     /** Condition for waiting puts */
  83     private final Condition notFull = lock.newCondition();
  84
  85     /**
  86      * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
  87      * {@link Integer#MAX_VALUE}.
  88      */
  89     public LinkedBlockingDeque() {
  90         this(Integer.MAX_VALUE);
  91     }
  92
  93     /**
  94      * Creates a <tt>LinkedBlockingDeque</tt> with the given (fixed) capacity.
  95      *
  96      * @param capacity the capacity of this deque
  97      * @throws IllegalArgumentException if <tt>capacity</tt> is less than 1
  98      */
  99     public LinkedBlockingDeque(int capacity) {
 100         if (capacity <= 0) throw new IllegalArgumentException();
 101         this.capacity = capacity;
 102     }
 103
 104     /**
 105      * Creates a <tt>LinkedBlockingDeque</tt> with a capacity of
 106      * {@link Integer#MAX_VALUE}, initially containing the elements of
 107      * the given collection, added in traversal order of the
 108      * collection's iterator.
 109      *
 110      * @param c the collection of elements to initially contain
 111      * @throws NullPointerException if the specified collection or any
 112      *         of its elements are null
 113      */
 114     public LinkedBlockingDeque(Collection<? extends E> c) {
 115         this(Integer.MAX_VALUE);
 116         for (E e : c)
 117             add(e);
 118     }
 119
 120
 121     // Basic linking and unlinking operations, called only while holding lock
 122
 123     /**
 124      * Links e as first element, or returns false if full.
 125      */
 126     private boolean linkFirst(E e) {
 127         if (count >= capacity)
 128             return false;
 129         ++count;
 130         Node<E> f = first;
 131         Node<E> x = new Node<E>(e, null, f);
 132         first = x;
 133         if (last == null)
 134             last = x;
 135         else
 136             f.prev = x;
 137         notEmpty.signal();
 138         return true;
 139     }
 140
 141     /**
 142      * Links e as last element, or returns false if full.
 143      */
 144     private boolean linkLast(E e) {
 145         if (count >= capacity)
 146             return false;
 147         ++count;
 148         Node<E> l = last;
 149         Node<E> x = new Node<E>(e, l, null);
 150         last = x;
 151         if (first == null)
 152             first = x;
 153         else
 154             l.next = x;
 155         notEmpty.signal();
 156         return true;
 157     }
 158
 159     /**
 160      * Removes and returns first element, or null if empty.
 161      */
 162     private E unlinkFirst() {
 163         Node<E> f = first;
 164         if (f == null)
 165             return null;
 166         Node<E> n = f.next;
 167         first = n;
 168         if (n == null)
 169             last = null;
 170         else
 171             n.prev = null;
 172         --count;
 173         notFull.signal();
 174         return f.item;
 175     }
 176
 177     /**
 178      * Removes and returns last element, or null if empty.
 179      */
 180     private E unlinkLast() {
 181         Node<E> l = last;
 182         if (l == null)
 183             return null;
 184         Node<E> p = l.prev;
 185         last = p;
 186         if (p == null)
 187             first = null;
 188         else
 189             p.next = null;
 190         --count;
 191         notFull.signal();
 192         return l.item;
 193     }
 194
 195     /**
 196      * Unlink e
 197      */
 198     private void unlink(Node<E> x) {
 199         Node<E> p = x.prev;
 200         Node<E> n = x.next;
 201         if (p == null) {
 202             if (n == null)
 203                 first = last = null;
 204             else {
 205                 n.prev = null;
 206                 first = n;
 207             }
 208         } else if (n == null) {
 209             p.next = null;
 210             last = p;
 211         } else {
 212             p.next = n;
 213             n.prev = p;
 214         }
 215         --count;
 216         notFull.signalAll();
 217     }
 218
 219     // BlockingDeque methods
 220
 221     /**
 222      * @throws IllegalStateException {@inheritDoc}
 223      * @throws NullPointerException  {@inheritDoc}
 224      */
 225     public void addFirst(E e) {
 226         if (!offerFirst(e))
 227             throw new IllegalStateException("Deque full");
 228     }
 229
 230     /**
 231      * @throws IllegalStateException {@inheritDoc}
 232      * @throws NullPointerException  {@inheritDoc}
 233      */
 234     public void addLast(E e) {
 235         if (!offerLast(e))
 236             throw new IllegalStateException("Deque full");
 237     }
 238
 239     /**
 240      * @throws NullPointerException {@inheritDoc}
 241      */
 242     public boolean offerFirst(E e) {
 243         if (e == null) throw new NullPointerException();
 244         lock.lock();
 245         try {
 246             return linkFirst(e);
 247         } finally {
 248             lock.unlock();
 249         }
 250     }
 251
 252     /**
 253      * @throws NullPointerException {@inheritDoc}
 254      */
 255     public boolean offerLast(E e) {
 256         if (e == null) throw new NullPointerException();
 257         lock.lock();
 258         try {
 259             return linkLast(e);
 260         } finally {
 261             lock.unlock();
 262         }
 263     }
 264
 265     /**
 266      * @throws NullPointerException {@inheritDoc}
 267      * @throws InterruptedException {@inheritDoc}
 268      */
 269     public void putFirst(E e) throws InterruptedException {
 270         if (e == null) throw new NullPointerException();
 271         lock.lock();
 272         try {
 273             while (!linkFirst(e))
 274                 notFull.await();
 275         } finally {
 276             lock.unlock();
 277         }
 278     }
 279
 280     /**
 281      * @throws NullPointerException {@inheritDoc}
 282      * @throws InterruptedException {@inheritDoc}
 283      */
 284     public void putLast(E e) throws InterruptedException {
 285         if (e == null) throw new NullPointerException();
 286         lock.lock();
 287         try {
 288             while (!linkLast(e))
 289                 notFull.await();
 290         } finally {
 291             lock.unlock();
 292         }
 293     }
 294
 295     /**
 296      * @throws NullPointerException {@inheritDoc}
 297      * @throws InterruptedException {@inheritDoc}
 298      */
 299     public boolean offerFirst(E e, long timeout, TimeUnit unit)
 300         throws InterruptedException {
 301         if (e == null) throw new NullPointerException();
 302         long nanos = unit.toNanos(timeout);
 303         lock.lockInterruptibly();
 304         try {
 305             for (;;) {
 306                 if (linkFirst(e))
 307                     return true;
 308                 if (nanos <= 0)
 309                     return false;
 310                 nanos = notFull.awaitNanos(nanos);
 311             }
 312         } finally {
 313             lock.unlock();
 314         }
 315     }
 316
 317     /**
 318      * @throws NullPointerException {@inheritDoc}
 319      * @throws InterruptedException {@inheritDoc}
 320      */
 321     public boolean offerLast(E e, long timeout, TimeUnit unit)
 322         throws InterruptedException {
 323         if (e == null) throw new NullPointerException();
 324         long nanos = unit.toNanos(timeout);
 325         lock.lockInterruptibly();
 326         try {
 327             for (;;) {
 328                 if (linkLast(e))
 329                     return true;
 330                 if (nanos <= 0)
 331                     return false;
 332                 nanos = notFull.awaitNanos(nanos);
 333             }
 334         } finally {
 335             lock.unlock();
 336         }
 337     }
 338
 339     /**
 340      * @throws NoSuchElementException {@inheritDoc}
 341      */
 342     public E removeFirst() {
 343         E x = pollFirst();
 344         if (x == null) throw new NoSuchElementException();
 345         return x;
 346     }
 347
 348     /**
 349      * @throws NoSuchElementException {@inheritDoc}
 350      */
 351     public E removeLast() {
 352         E x = pollLast();
 353         if (x == null) throw new NoSuchElementException();
 354         return x;
 355     }
 356
 357     public E pollFirst() {
 358         lock.lock();
 359         try {
 360             return unlinkFirst();
 361         } finally {
 362             lock.unlock();
 363         }
 364     }
 365
 366     public E pollLast() {
 367         lock.lock();
 368         try {
 369             return unlinkLast();
 370         } finally {
 371             lock.unlock();
 372         }
 373     }
 374
 375     public E takeFirst() throws InterruptedException {
 376         lock.lock();
 377         try {
 378             E x;
 379             while ( (x = unlinkFirst()) == null)
 380                 notEmpty.await();
 381             return x;
 382         } finally {
 383             lock.unlock();
 384         }
 385     }
 386
 387     public E takeLast() throws InterruptedException {
 388         lock.lock();
 389         try {
 390             E x;
 391             while ( (x = unlinkLast()) == null)
 392                 notEmpty.await();
 393             return x;
 394         } finally {
 395             lock.unlock();
 396         }
 397     }
 398
 399     public E pollFirst(long timeout, TimeUnit unit)
 400         throws InterruptedException {
 401         long nanos = unit.toNanos(timeout);
 402         lock.lockInterruptibly();
 403         try {
 404             for (;;) {
 405                 E x = unlinkFirst();
 406                 if (x != null)
 407                     return x;
 408                 if (nanos <= 0)
 409                     return null;
 410                 nanos = notEmpty.awaitNanos(nanos);
 411             }
 412         } finally {
 413             lock.unlock();
 414         }
 415     }
 416
 417     public E pollLast(long timeout, TimeUnit unit)
 418         throws InterruptedException {
 419         long nanos = unit.toNanos(timeout);
 420         lock.lockInterruptibly();
 421         try {
 422             for (;;) {
 423                 E x = unlinkLast();
 424                 if (x != null)
 425                     return x;
 426                 if (nanos <= 0)
 427                     return null;
 428                 nanos = notEmpty.awaitNanos(nanos);
 429             }
 430         } finally {
 431             lock.unlock();
 432         }
 433     }
 434
 435     /**
 436      * @throws NoSuchElementException {@inheritDoc}
 437      */
 438     public E getFirst() {
 439         E x = peekFirst();
 440         if (x == null) throw new NoSuchElementException();
 441         return x;
 442     }
 443
 444     /**
 445      * @throws NoSuchElementException {@inheritDoc}
 446      */
 447     public E getLast() {
 448         E x = peekLast();
 449         if (x == null) throw new NoSuchElementException();
 450         return x;
 451     }
 452
 453     public E peekFirst() {
 454         lock.lock();
 455         try {
 456             return (first == null) ? null : first.item;
 457         } finally {
 458             lock.unlock();
 459         }
 460     }
 461
 462     public E peekLast() {
 463         lock.lock();
 464         try {
 465             return (last == null) ? null : last.item;
 466         } finally {
 467             lock.unlock();
 468         }
 469     }
 470
 471     public boolean removeFirstOccurrence(Object o) {
 472         if (o == null) return false;
 473         lock.lock();
 474         try {
 475             for (Node<E> p = first; p != null; p = p.next) {
 476                 if (o.equals(p.item)) {
 477                     unlink(p);
 478                     return true;
 479                 }
 480             }
 481             return false;
 482         } finally {
 483             lock.unlock();
 484         }
 485     }
 486
 487     public boolean removeLastOccurrence(Object o) {
 488         if (o == null) return false;
 489         lock.lock();
 490         try {
 491             for (Node<E> p = last; p != null; p = p.prev) {
 492                 if (o.equals(p.item)) {
 493                     unlink(p);
 494                     return true;
 495                 }
 496             }
 497             return false;
 498         } finally {
 499             lock.unlock();
 500         }
 501     }
 502
 503     // BlockingQueue methods
 504
 505     /**
 506      * Inserts the specified element at the end of this deque unless it would
 507      * violate capacity restrictions.  When using a capacity-restricted deque,
 508      * it is generally preferable to use method {@link #offer(Object) offer}.
 509      *
 510      * <p>This method is equivalent to {@link #addLast}.
 511      *
 512      * @throws IllegalStateException if the element cannot be added at this
 513      *         time due to capacity restrictions
 514      * @throws NullPointerException if the specified element is null
 515      */
 516     public boolean add(E e) {
 517         addLast(e);
 518         return true;
 519     }
 520
 521     /**
 522      * @throws NullPointerException if the specified element is null
 523      */
 524     public boolean offer(E e) {
 525         return offerLast(e);
 526     }
 527
 528     /**
 529      * @throws NullPointerException {@inheritDoc}
 530      * @throws InterruptedException {@inheritDoc}
 531      */
 532     public void put(E e) throws InterruptedException {
 533         putLast(e);
 534     }
 535
 536     /**
 537      * @throws NullPointerException {@inheritDoc}
 538      * @throws InterruptedException {@inheritDoc}
 539      */
 540     public boolean offer(E e, long timeout, TimeUnit unit)
 541         throws InterruptedException {
 542         return offerLast(e, timeout, unit);
 543     }
 544
 545     /**
 546      * Retrieves and removes the head of the queue represented by this deque.
 547      * This method differs from {@link #poll poll} only in that it throws an
 548      * exception if this deque is empty.
 549      *
 550      * <p>This method is equivalent to {@link #removeFirst() removeFirst}.
 551      *
 552      * @return the head of the queue represented by this deque
 553      * @throws NoSuchElementException if this deque is empty
 554      */
 555     public E remove() {
 556         return removeFirst();
 557     }
 558
 559     public E poll() {
 560         return pollFirst();
 561     }
 562
 563     public E take() throws InterruptedException {
 564         return takeFirst();
 565     }
 566
 567     public E poll(long timeout, TimeUnit unit) throws InterruptedException {
 568         return pollFirst(timeout, unit);
 569     }
 570
 571     /**
 572      * Retrieves, but does not remove, the head of the queue represented by
 573      * this deque.  This method differs from {@link #peek peek} only in that
 574      * it throws an exception if this deque is empty.
 575      *
 576      * <p>This method is equivalent to {@link #getFirst() getFirst}.
 577      *
 578      * @return the head of the queue represented by this deque
 579      * @throws NoSuchElementException if this deque is empty
 580      */
 581     public E element() {
 582         return getFirst();
 583     }
 584
 585     public E peek() {
 586         return peekFirst();
 587     }
 588
 589     /**
 590      * Returns the number of additional elements that this deque can ideally
 591      * (in the absence of memory or resource constraints) accept without
 592      * blocking. This is always equal to the initial capacity of this deque
 593      * less the current <tt>size</tt> of this deque.
 594      *
 595      * <p>Note that you <em>cannot</em> always tell if an attempt to insert
 596      * an element will succeed by inspecting <tt>remainingCapacity</tt>
 597      * because it may be the case that another thread is about to
 598      * insert or remove an element.
 599      */
 600     public int remainingCapacity() {
 601         lock.lock();
 602         try {
 603             return capacity - count;
 604         } finally {
 605             lock.unlock();
 606         }
 607     }
 608
 609     /**
 610      * @throws UnsupportedOperationException {@inheritDoc}
 611      * @throws ClassCastException            {@inheritDoc}
 612      * @throws NullPointerException          {@inheritDoc}
 613      * @throws IllegalArgumentException      {@inheritDoc}
 614      */
 615     public int drainTo(Collection<? super E> c) {
 616         if (c == null)
 617             throw new NullPointerException();
 618         if (c == this)
 619             throw new IllegalArgumentException();
 620         lock.lock();
 621         try {
 622             for (Node<E> p = first; p != null; p = p.next)
 623                 c.add(p.item);
 624             int n = count;
 625             count = 0;
 626             first = last = null;
 627             notFull.signalAll();
 628             return n;
 629         } finally {
 630             lock.unlock();
 631         }
 632     }
 633
 634     /**
 635      * @throws UnsupportedOperationException {@inheritDoc}
 636      * @throws ClassCastException            {@inheritDoc}
 637      * @throws NullPointerException          {@inheritDoc}
 638      * @throws IllegalArgumentException      {@inheritDoc}
 639      */
 640     public int drainTo(Collection<? super E> c, int maxElements) {
 641         if (c == null)
 642             throw new NullPointerException();
 643         if (c == this)
 644             throw new IllegalArgumentException();
 645         lock.lock();
 646         try {
 647             int n = 0;
 648             while (n < maxElements && first != null) {
 649                 c.add(first.item);
 650                 first.prev = null;
 651                 first = first.next;
 652                 --count;
 653                 ++n;
 654             }
 655             if (first == null)
 656                 last = null;
 657             notFull.signalAll();
 658             return n;
 659         } finally {
 660             lock.unlock();
 661         }
 662     }
 663
 664     // Stack methods
 665
 666     /**
 667      * @throws IllegalStateException {@inheritDoc}
 668      * @throws NullPointerException  {@inheritDoc}
 669      */
 670     public void push(E e) {
 671         addFirst(e);
 672     }
 673
 674     /**
 675      * @throws NoSuchElementException {@inheritDoc}
 676      */
 677     public E pop() {
 678         return removeFirst();
 679     }
 680
 681     // Collection methods
 682
 683     /**
 684      * Removes the first occurrence of the specified element from this deque.
 685      * If the deque does not contain the element, it is unchanged.
 686      * More formally, removes the first element <tt>e</tt> such that
 687      * <tt>o.equals(e)</tt> (if such an element exists).
 688      * Returns <tt>true</tt> if this deque contained the specified element
 689      * (or equivalently, if this deque changed as a result of the call).
 690      *
 691      * <p>This method is equivalent to
 692      * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
 693      *
 694      * @param o element to be removed from this deque, if present
 695      * @return <tt>true</tt> if this deque changed as a result of the call
 696      */
 697     public boolean remove(Object o) {
 698         return removeFirstOccurrence(o);
 699     }
 700
 701     /**
 702      * Returns the number of elements in this deque.
 703      *
 704      * @return the number of elements in this deque
 705      */
 706     public int size() {
 707         lock.lock();
 708         try {
 709             return count;
 710         } finally {
 711             lock.unlock();
 712         }
 713     }
 714
 715     /**
 716      * Returns <tt>true</tt> if this deque contains the specified element.
 717      * More formally, returns <tt>true</tt> if and only if this deque contains
 718      * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
 719      *
 720      * @param o object to be checked for containment in this deque
 721      * @return <tt>true</tt> if this deque contains the specified element
 722      */
 723     public boolean contains(Object o) {
 724         if (o == null) return false;
 725         lock.lock();
 726         try {
 727             for (Node<E> p = first; p != null; p = p.next)
 728                 if (o.equals(p.item))
 729                     return true;
 730             return false;
 731         } finally {
 732             lock.unlock();
 733         }
 734     }
 735
 736     /**
 737      * Variant of removeFirstOccurrence needed by iterator.remove.
 738      * Searches for the node, not its contents.
 739      */
 740     boolean removeNode(Node<E> e) {
 741         lock.lock();
 742         try {
 743             for (Node<E> p = first; p != null; p = p.next) {
 744                 if (p == e) {
 745                     unlink(p);
 746                     return true;
 747                 }
 748             }
 749             return false;
 750         } finally {
 751             lock.unlock();
 752         }
 753     }
 754
 755     /**
 756      * Returns an array containing all of the elements in this deque, in
 757      * proper sequence (from first to last element).
 758      *
 759      * <p>The returned array will be "safe" in that no references to it are
 760      * maintained by this deque.  (In other words, this method must allocate
 761      * a new array).  The caller is thus free to modify the returned array.
 762      *
 763      * <p>This method acts as bridge between array-based and collection-based
 764      * APIs.
 765      *
 766      * @return an array containing all of the elements in this deque
 767      */
 768     public Object[] toArray() {
 769         lock.lock();
 770         try {
 771             Object[] a = new Object[count];
 772             int k = 0;
 773             for (Node<E> p = first; p != null; p = p.next)
 774                 a[k++] = p.item;
 775             return a;
 776         } finally {
 777             lock.unlock();
 778         }
 779     }
 780
 781     /**
 782      * Returns an array containing all of the elements in this deque, in
 783      * proper sequence; the runtime type of the returned array is that of
 784      * the specified array.  If the deque fits in the specified array, it
 785      * is returned therein.  Otherwise, a new array is allocated with the
 786      * runtime type of the specified array and the size of this deque.
 787      *
 788      * <p>If this deque fits in the specified array with room to spare
 789      * (i.e., the array has more elements than this deque), the element in
 790      * the array immediately following the end of the deque is set to
 791      * <tt>null</tt>.
 792      *
 793      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 794      * array-based and collection-based APIs.  Further, this method allows
 795      * precise control over the runtime type of the output array, and may,
 796      * under certain circumstances, be used to save allocation costs.
 797      *
 798      * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
 799      * The following code can be used to dump the deque into a newly
 800      * allocated array of <tt>String</tt>:
 801      *
 802      * <pre>
 803      *     String[] y = x.toArray(new String[0]);</pre>
 804      *
 805      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 806      * <tt>toArray()</tt>.
 807      *
 808      * @param a the array into which the elements of the deque are to
 809      *          be stored, if it is big enough; otherwise, a new array of the
 810      *          same runtime type is allocated for this purpose
 811      * @return an array containing all of the elements in this deque
 812      * @throws ArrayStoreException if the runtime type of the specified array
 813      *         is not a supertype of the runtime type of every element in
 814      *         this deque
 815      * @throws NullPointerException if the specified array is null
 816      */
 817     public <T> T[] toArray(T[] a) {
 818         lock.lock();
 819         try {
 820             if (a.length < count)
 821                 a = (T[])java.lang.reflect.Array.newInstance(
 822                     a.getClass().getComponentType(),
 823                     count
 824                     );
 825
 826             int k = 0;
 827             for (Node<E> p = first; p != null; p = p.next)
 828                 a[k++] = (T)p.item;
 829             if (a.length > k)
 830                 a[k] = null;
 831             return a;
 832         } finally {
 833             lock.unlock();
 834         }
 835     }
 836
 837     public String toString() {
 838         lock.lock();
 839         try {
 840             return super.toString();
 841         } finally {
 842             lock.unlock();
 843         }
 844     }
 845
 846     /**
 847      * Atomically removes all of the elements from this deque.
 848      * The deque will be empty after this call returns.
 849      */
 850     public void clear() {
 851         lock.lock();
 852         try {
 853             first = last = null;
 854             count = 0;
 855             notFull.signalAll();
 856         } finally {
 857             lock.unlock();
 858         }
 859     }
 860
 861     /**
 862      * Returns an iterator over the elements in this deque in proper sequence.
 863      * The elements will be returned in order from first (head) to last (tail).
 864      * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
 865      * will never throw {@link ConcurrentModificationException},
 866      * and guarantees to traverse elements as they existed upon
 867      * construction of the iterator, and may (but is not guaranteed to)
 868      * reflect any modifications subsequent to construction.
 869      *
 870      * @return an iterator over the elements in this deque in proper sequence
 871      */
 872     public Iterator<E> iterator() {
 873         return new Itr();
 874     }
 875
 876     /**
 877      * Returns an iterator over the elements in this deque in reverse
 878      * sequential order.  The elements will be returned in order from
 879      * last (tail) to first (head).
 880      * The returned <tt>Iterator</tt> is a "weakly consistent" iterator that
 881      * will never throw {@link ConcurrentModificationException},
 882      * and guarantees to traverse elements as they existed upon
 883      * construction of the iterator, and may (but is not guaranteed to)
 884      * reflect any modifications subsequent to construction.
 885      */
 886     public Iterator<E> descendingIterator() {
 887         return new DescendingItr();
 888     }
 889
 890     /**
 891      * Base class for Iterators for LinkedBlockingDeque
 892      */
 893     private abstract class AbstractItr implements Iterator<E> {
 894         /**
 895          * The next node to return in next
 896          */
 897          Node<E> next;
 898
 899         /**
 900          * nextItem holds on to item fields because once we claim that
 901          * an element exists in hasNext(), we must return item read
 902          * under lock (in advance()) even if it was in the process of
 903          * being removed when hasNext() was called.
 904          */
 905         E nextItem;
 906
 907         /**
 908          * Node returned by most recent call to next. Needed by remove.
 909          * Reset to null if this element is deleted by a call to remove.
 910          */
 911         private Node<E> lastRet;
 912
 913         AbstractItr() {
 914             advance(); // set to initial position
 915         }
 916
 917         /**
 918          * Advances next, or if not yet initialized, sets to first node.
 919          * Implemented to move forward vs backward in the two subclasses.
 920          */
 921         abstract void advance();
 922
 923         public boolean hasNext() {
 924             return next != null;
 925         }
 926
 927         public E next() {
 928             if (next == null)
 929                 throw new NoSuchElementException();
 930             lastRet = next;
 931             E x = nextItem;
 932             advance();
 933             return x;
 934         }
 935
 936         public void remove() {
 937             Node<E> n = lastRet;
 938             if (n == null)
 939                 throw new IllegalStateException();
 940             lastRet = null;
 941             // Note: removeNode rescans looking for this node to make
 942             // sure it was not already removed. Otherwise, trying to
 943             // re-remove could corrupt list.
 944             removeNode(n);
 945         }
 946     }
 947
 948     /** Forward iterator */
 949     private class Itr extends AbstractItr {
 950         void advance() {
 951             final ReentrantLock lock = LinkedBlockingDeque.this.lock;
 952             lock.lock();
 953             try {
 954                 next = (next == null)? first : next.next;
 955                 nextItem = (next == null)? null : next.item;
 956             } finally {
 957                 lock.unlock();
 958             }
 959         }
 960     }
 961
 962     /**
 963      * Descending iterator for LinkedBlockingDeque
 964      */
 965     private class DescendingItr extends AbstractItr {
 966         void advance() {
 967             final ReentrantLock lock = LinkedBlockingDeque.this.lock;
 968             lock.lock();
 969             try {
 970                 next = (next == null)? last : next.prev;
 971                 nextItem = (next == null)? null : next.item;
 972             } finally {
 973                 lock.unlock();
 974             }
 975         }
 976     }
 977
 978     /**
 979      * Save the state of this deque to a stream (that is, serialize it).
 980      *
 981      * @serialData The capacity (int), followed by elements (each an
 982      * <tt>Object</tt>) in the proper order, followed by a null
 983      * @param s the stream
 984      */
 985     private void writeObject(java.io.ObjectOutputStream s)
 986         throws java.io.IOException {
 987         lock.lock();
 988         try {
 989             // Write out capacity and any hidden stuff
 990             s.defaultWriteObject();
 991             // Write out all elements in the proper order.
 992             for (Node<E> p = first; p != null; p = p.next)
 993                 s.writeObject(p.item);
 994             // Use trailing null as sentinel
 995             s.writeObject(null);
 996         } finally {
 997             lock.unlock();
 998         }
 999     }
1000
1001     /**
1002      * Reconstitute this deque from a stream (that is,
1003      * deserialize it).
1004      * @param s the stream
1005      */
1006     private void readObject(java.io.ObjectInputStream s)
1007         throws java.io.IOException, ClassNotFoundException {
1008         s.defaultReadObject();
1009         count = 0;
1010         first = null;
1011         last = null;
1012         // Read in all elements and place in queue
1013         for (;;) {
1014             E item = (E)s.readObject();
1015             if (item == null)
1016                 break;
1017             add(item);
1018         }
1019     }
1020
1021 }