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