Source for java.util.concurrent.LinkedBlockingDeque

   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: }