LinkedBlockingDeque.java revision 8eb35c835be1345d3873a82cc9e42f944d698afd
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 7package java.util.concurrent; 8 9import java.util.AbstractQueue; 10import java.util.Collection; 11import java.util.Iterator; 12import java.util.NoSuchElementException; 13import java.util.concurrent.locks.Condition; 14import java.util.concurrent.locks.ReentrantLock; 15 16/** 17 * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on 18 * linked nodes. 19 * 20 * <p> The optional capacity bound constructor argument serves as a 21 * way to prevent excessive expansion. The capacity, if unspecified, 22 * is equal to {@link Integer#MAX_VALUE}. Linked nodes are 23 * dynamically created upon each insertion unless this would bring the 24 * deque above capacity. 25 * 26 * <p>Most operations run in constant time (ignoring time spent 27 * blocking). Exceptions include {@link #remove(Object) remove}, 28 * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link 29 * #removeLastOccurrence removeLastOccurrence}, {@link #contains 30 * contains}, {@link #iterator iterator.remove()}, and the bulk 31 * operations, all of which run in linear time. 32 * 33 * <p>This class and its iterator implement all of the 34 * <em>optional</em> methods of the {@link Collection} and {@link 35 * Iterator} interfaces. 36 * 37 * <p>This class is a member of the 38 * <a href="{@docRoot}/../technotes/guides/collections/index.html"> 39 * Java Collections Framework</a>. 40 * 41 * @since 1.6 42 * @author Doug Lea 43 * @param <E> the type of elements held in this collection 44 */ 45public 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 final ReentrantLock lock = this.lock; 717 lock.lock(); 718 try { 719 int n = Math.min(maxElements, count); 720 for (int i = 0; i < n; i++) { 721 c.add(first.item); // In this order, in case add() throws. 722 unlinkFirst(); 723 } 724 return n; 725 } finally { 726 lock.unlock(); 727 } 728 } 729 730 // Stack methods 731 732 /** 733 * @throws IllegalStateException {@inheritDoc} 734 * @throws NullPointerException {@inheritDoc} 735 */ 736 public void push(E e) { 737 addFirst(e); 738 } 739 740 /** 741 * @throws NoSuchElementException {@inheritDoc} 742 */ 743 public E pop() { 744 return removeFirst(); 745 } 746 747 // Collection methods 748 749 /** 750 * Removes the first occurrence of the specified element from this deque. 751 * If the deque does not contain the element, it is unchanged. 752 * More formally, removes the first element {@code e} such that 753 * {@code o.equals(e)} (if such an element exists). 754 * Returns {@code true} if this deque contained the specified element 755 * (or equivalently, if this deque changed as a result of the call). 756 * 757 * <p>This method is equivalent to 758 * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}. 759 * 760 * @param o element to be removed from this deque, if present 761 * @return {@code true} if this deque changed as a result of the call 762 */ 763 public boolean remove(Object o) { 764 return removeFirstOccurrence(o); 765 } 766 767 /** 768 * Returns the number of elements in this deque. 769 * 770 * @return the number of elements in this deque 771 */ 772 public int size() { 773 final ReentrantLock lock = this.lock; 774 lock.lock(); 775 try { 776 return count; 777 } finally { 778 lock.unlock(); 779 } 780 } 781 782 /** 783 * Returns {@code true} if this deque contains the specified element. 784 * More formally, returns {@code true} if and only if this deque contains 785 * at least one element {@code e} such that {@code o.equals(e)}. 786 * 787 * @param o object to be checked for containment in this deque 788 * @return {@code true} if this deque contains the specified element 789 */ 790 public boolean contains(Object o) { 791 if (o == null) return false; 792 final ReentrantLock lock = this.lock; 793 lock.lock(); 794 try { 795 for (Node<E> p = first; p != null; p = p.next) 796 if (o.equals(p.item)) 797 return true; 798 return false; 799 } finally { 800 lock.unlock(); 801 } 802 } 803 804 /* 805 * TODO: Add support for more efficient bulk operations. 806 * 807 * We don't want to acquire the lock for every iteration, but we 808 * also want other threads a chance to interact with the 809 * collection, especially when count is close to capacity. 810 */ 811 812// /** 813// * Adds all of the elements in the specified collection to this 814// * queue. Attempts to addAll of a queue to itself result in 815// * {@code IllegalArgumentException}. Further, the behavior of 816// * this operation is undefined if the specified collection is 817// * modified while the operation is in progress. 818// * 819// * @param c collection containing elements to be added to this queue 820// * @return {@code true} if this queue changed as a result of the call 821// * @throws ClassCastException {@inheritDoc} 822// * @throws NullPointerException {@inheritDoc} 823// * @throws IllegalArgumentException {@inheritDoc} 824// * @throws IllegalStateException {@inheritDoc} 825// * @see #add(Object) 826// */ 827// public boolean addAll(Collection<? extends E> c) { 828// if (c == null) 829// throw new NullPointerException(); 830// if (c == this) 831// throw new IllegalArgumentException(); 832// final ReentrantLock lock = this.lock; 833// lock.lock(); 834// try { 835// boolean modified = false; 836// for (E e : c) 837// if (linkLast(e)) 838// modified = true; 839// return modified; 840// } finally { 841// lock.unlock(); 842// } 843// } 844 845 /** 846 * Returns an array containing all of the elements in this deque, in 847 * proper sequence (from first to last element). 848 * 849 * <p>The returned array will be "safe" in that no references to it are 850 * maintained by this deque. (In other words, this method must allocate 851 * a new array). The caller is thus free to modify the returned array. 852 * 853 * <p>This method acts as bridge between array-based and collection-based 854 * APIs. 855 * 856 * @return an array containing all of the elements in this deque 857 */ 858 @SuppressWarnings("unchecked") 859 public Object[] toArray() { 860 final ReentrantLock lock = this.lock; 861 lock.lock(); 862 try { 863 Object[] a = new Object[count]; 864 int k = 0; 865 for (Node<E> p = first; p != null; p = p.next) 866 a[k++] = p.item; 867 return a; 868 } finally { 869 lock.unlock(); 870 } 871 } 872 873 /** 874 * Returns an array containing all of the elements in this deque, in 875 * proper sequence; the runtime type of the returned array is that of 876 * the specified array. If the deque fits in the specified array, it 877 * is returned therein. Otherwise, a new array is allocated with the 878 * runtime type of the specified array and the size of this deque. 879 * 880 * <p>If this deque fits in the specified array with room to spare 881 * (i.e., the array has more elements than this deque), the element in 882 * the array immediately following the end of the deque is set to 883 * {@code null}. 884 * 885 * <p>Like the {@link #toArray()} method, this method acts as bridge between 886 * array-based and collection-based APIs. Further, this method allows 887 * precise control over the runtime type of the output array, and may, 888 * under certain circumstances, be used to save allocation costs. 889 * 890 * <p>Suppose {@code x} is a deque known to contain only strings. 891 * The following code can be used to dump the deque into a newly 892 * allocated array of {@code String}: 893 * 894 * <pre> 895 * String[] y = x.toArray(new String[0]);</pre> 896 * 897 * Note that {@code toArray(new Object[0])} is identical in function to 898 * {@code toArray()}. 899 * 900 * @param a the array into which the elements of the deque are to 901 * be stored, if it is big enough; otherwise, a new array of the 902 * same runtime type is allocated for this purpose 903 * @return an array containing all of the elements in this deque 904 * @throws ArrayStoreException if the runtime type of the specified array 905 * is not a supertype of the runtime type of every element in 906 * this deque 907 * @throws NullPointerException if the specified array is null 908 */ 909 @SuppressWarnings("unchecked") 910 public <T> T[] toArray(T[] a) { 911 final ReentrantLock lock = this.lock; 912 lock.lock(); 913 try { 914 if (a.length < count) 915 a = (T[])java.lang.reflect.Array.newInstance 916 (a.getClass().getComponentType(), count); 917 918 int k = 0; 919 for (Node<E> p = first; p != null; p = p.next) 920 a[k++] = (T)p.item; 921 if (a.length > k) 922 a[k] = null; 923 return a; 924 } finally { 925 lock.unlock(); 926 } 927 } 928 929 public String toString() { 930 final ReentrantLock lock = this.lock; 931 lock.lock(); 932 try { 933 Node<E> p = first; 934 if (p == null) 935 return "[]"; 936 937 StringBuilder sb = new StringBuilder(); 938 sb.append('['); 939 for (;;) { 940 E e = p.item; 941 sb.append(e == this ? "(this Collection)" : e); 942 p = p.next; 943 if (p == null) 944 return sb.append(']').toString(); 945 sb.append(',').append(' '); 946 } 947 } finally { 948 lock.unlock(); 949 } 950 } 951 952 /** 953 * Atomically removes all of the elements from this deque. 954 * The deque will be empty after this call returns. 955 */ 956 public void clear() { 957 final ReentrantLock lock = this.lock; 958 lock.lock(); 959 try { 960 for (Node<E> f = first; f != null; ) { 961 f.item = null; 962 Node<E> n = f.next; 963 f.prev = null; 964 f.next = null; 965 f = n; 966 } 967 first = last = null; 968 count = 0; 969 notFull.signalAll(); 970 } finally { 971 lock.unlock(); 972 } 973 } 974 975 /** 976 * Returns an iterator over the elements in this deque in proper sequence. 977 * The elements will be returned in order from first (head) to last (tail). 978 * 979 * <p>The returned iterator is a "weakly consistent" iterator that 980 * will never throw {@link java.util.ConcurrentModificationException 981 * ConcurrentModificationException}, and guarantees to traverse 982 * elements as they existed upon construction of the iterator, and 983 * may (but is not guaranteed to) reflect any modifications 984 * subsequent to construction. 985 * 986 * @return an iterator over the elements in this deque in proper sequence 987 */ 988 public Iterator<E> iterator() { 989 return new Itr(); 990 } 991 992 /** 993 * Returns an iterator over the elements in this deque in reverse 994 * sequential order. The elements will be returned in order from 995 * last (tail) to first (head). 996 * 997 * <p>The returned iterator is a "weakly consistent" iterator that 998 * will never throw {@link java.util.ConcurrentModificationException 999 * ConcurrentModificationException}, and guarantees to traverse 1000 * elements as they existed upon construction of the iterator, and 1001 * may (but is not guaranteed to) reflect any modifications 1002 * subsequent to construction. 1003 * 1004 * @return an iterator over the elements in this deque in reverse order 1005 */ 1006 public Iterator<E> descendingIterator() { 1007 return new DescendingItr(); 1008 } 1009 1010 /** 1011 * Base class for Iterators for LinkedBlockingDeque 1012 */ 1013 private abstract class AbstractItr implements Iterator<E> { 1014 /** 1015 * The next node to return in next() 1016 */ 1017 Node<E> next; 1018 1019 /** 1020 * nextItem holds on to item fields because once we claim that 1021 * an element exists in hasNext(), we must return item read 1022 * under lock (in advance()) even if it was in the process of 1023 * being removed when hasNext() was called. 1024 */ 1025 E nextItem; 1026 1027 /** 1028 * Node returned by most recent call to next. Needed by remove. 1029 * Reset to null if this element is deleted by a call to remove. 1030 */ 1031 private Node<E> lastRet; 1032 1033 abstract Node<E> firstNode(); 1034 abstract Node<E> nextNode(Node<E> n); 1035 1036 AbstractItr() { 1037 // set to initial position 1038 final ReentrantLock lock = LinkedBlockingDeque.this.lock; 1039 lock.lock(); 1040 try { 1041 next = firstNode(); 1042 nextItem = (next == null) ? null : next.item; 1043 } finally { 1044 lock.unlock(); 1045 } 1046 } 1047 1048 /** 1049 * Returns the successor node of the given non-null, but 1050 * possibly previously deleted, node. 1051 */ 1052 private Node<E> succ(Node<E> n) { 1053 // Chains of deleted nodes ending in null or self-links 1054 // are possible if multiple interior nodes are removed. 1055 for (;;) { 1056 Node<E> s = nextNode(n); 1057 if (s == null) 1058 return null; 1059 else if (s.item != null) 1060 return s; 1061 else if (s == n) 1062 return firstNode(); 1063 else 1064 n = s; 1065 } 1066 } 1067 1068 /** 1069 * Advances next. 1070 */ 1071 void advance() { 1072 final ReentrantLock lock = LinkedBlockingDeque.this.lock; 1073 lock.lock(); 1074 try { 1075 // assert next != null; 1076 next = succ(next); 1077 nextItem = (next == null) ? null : next.item; 1078 } finally { 1079 lock.unlock(); 1080 } 1081 } 1082 1083 public boolean hasNext() { 1084 return next != null; 1085 } 1086 1087 public E next() { 1088 if (next == null) 1089 throw new NoSuchElementException(); 1090 lastRet = next; 1091 E x = nextItem; 1092 advance(); 1093 return x; 1094 } 1095 1096 public void remove() { 1097 Node<E> n = lastRet; 1098 if (n == null) 1099 throw new IllegalStateException(); 1100 lastRet = null; 1101 final ReentrantLock lock = LinkedBlockingDeque.this.lock; 1102 lock.lock(); 1103 try { 1104 if (n.item != null) 1105 unlink(n); 1106 } finally { 1107 lock.unlock(); 1108 } 1109 } 1110 } 1111 1112 /** Forward iterator */ 1113 private class Itr extends AbstractItr { 1114 Node<E> firstNode() { return first; } 1115 Node<E> nextNode(Node<E> n) { return n.next; } 1116 } 1117 1118 /** Descending iterator */ 1119 private class DescendingItr extends AbstractItr { 1120 Node<E> firstNode() { return last; } 1121 Node<E> nextNode(Node<E> n) { return n.prev; } 1122 } 1123 1124 /** 1125 * Save the state of this deque to a stream (that is, serialize it). 1126 * 1127 * @serialData The capacity (int), followed by elements (each an 1128 * {@code Object}) in the proper order, followed by a null 1129 * @param s the stream 1130 */ 1131 private void writeObject(java.io.ObjectOutputStream s) 1132 throws java.io.IOException { 1133 final ReentrantLock lock = this.lock; 1134 lock.lock(); 1135 try { 1136 // Write out capacity and any hidden stuff 1137 s.defaultWriteObject(); 1138 // Write out all elements in the proper order. 1139 for (Node<E> p = first; p != null; p = p.next) 1140 s.writeObject(p.item); 1141 // Use trailing null as sentinel 1142 s.writeObject(null); 1143 } finally { 1144 lock.unlock(); 1145 } 1146 } 1147 1148 /** 1149 * Reconstitute this deque from a stream (that is, 1150 * deserialize it). 1151 * @param s the stream 1152 */ 1153 private void readObject(java.io.ObjectInputStream s) 1154 throws java.io.IOException, ClassNotFoundException { 1155 s.defaultReadObject(); 1156 count = 0; 1157 first = null; 1158 last = null; 1159 // Read in all elements and place in queue 1160 for (;;) { 1161 @SuppressWarnings("unchecked") 1162 E item = (E)s.readObject(); 1163 if (item == null) 1164 break; 1165 add(item); 1166 } 1167 } 1168 1169} 1170