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