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