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/publicdomain/zero/1.0/ 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.Objects; 43 import java.util.Spliterator; 44 import java.util.Spliterators; 45 import java.util.concurrent.locks.Condition; 46 import java.util.concurrent.locks.ReentrantLock; 47 import java.util.function.Consumer; 48 import java.util.function.Predicate; 49 50 /** 51 * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on 52 * linked nodes. 53 * 54 * <p>The optional capacity bound constructor argument serves as a 55 * way to prevent excessive expansion. The capacity, if unspecified, 56 * is equal to {@link Integer#MAX_VALUE}. Linked nodes are 57 * dynamically created upon each insertion unless this would bring the 58 * deque above capacity. 59 * 60 * <p>Most operations run in constant time (ignoring time spent 61 * blocking). Exceptions include {@link #remove(Object) remove}, 62 * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link 63 * #removeLastOccurrence removeLastOccurrence}, {@link #contains 64 * contains}, {@link #iterator iterator.remove()}, and the bulk 65 * operations, all of which run in linear time. 66 * 67 * <p>This class and its iterator implement all of the <em>optional</em> 68 * methods of the {@link Collection} and {@link Iterator} interfaces. 69 * 70 * <p>This class is a member of the 71 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework"> 72 * Java Collections Framework</a>. 73 * 74 * @since 1.6 75 * @author Doug Lea 76 * @param <E> the type of elements held in this deque 77 */ 78 public class LinkedBlockingDeque<E> 79 extends AbstractQueue<E> 80 implements BlockingDeque<E>, java.io.Serializable { 81 82 /* 83 * Implemented as a simple doubly-linked list protected by a 84 * single lock and using conditions to manage blocking. 85 * 86 * To implement weakly consistent iterators, it appears we need to 87 * keep all Nodes GC-reachable from a predecessor dequeued Node. 88 * That would cause two problems: 89 * - allow a rogue Iterator to cause unbounded memory retention 90 * - cause cross-generational linking of old Nodes to new Nodes if 91 * a Node was tenured while live, which generational GCs have a 92 * hard time dealing with, causing repeated major collections. 93 * However, only non-deleted Nodes need to be reachable from 94 * dequeued Nodes, and reachability does not necessarily have to 95 * be of the kind understood by the GC. We use the trick of 96 * linking a Node that has just been dequeued to itself. Such a 97 * self-link implicitly means to jump to "first" (for next links) 98 * or "last" (for prev links). 99 */ 100 101 /* 102 * We have "diamond" multiple interface/abstract class inheritance 103 * here, and that introduces ambiguities. Often we want the 104 * BlockingDeque javadoc combined with the AbstractQueue 105 * implementation, so a lot of method specs are duplicated here. 106 */ 107 108 private static final long serialVersionUID = -387911632671998426L; 109 110 /** Doubly-linked list node class */ 111 static final class Node<E> { 112 /** 113 * The item, or null if this node has been removed. 114 */ 115 E item; 116 117 /** 118 * One of: 119 * - the real predecessor Node 120 * - this Node, meaning the predecessor is tail 121 * - null, meaning there is no predecessor 122 */ 123 Node<E> prev; 124 125 /** 126 * One of: 127 * - the real successor Node 128 * - this Node, meaning the successor is head 129 * - null, meaning there is no successor 130 */ 131 Node<E> next; 132 Node(E x)133 Node(E x) { 134 item = x; 135 } 136 } 137 138 /** 139 * Pointer to first node. 140 * Invariant: (first == null && last == null) || 141 * (first.prev == null && first.item != null) 142 */ 143 transient Node<E> first; 144 145 /** 146 * Pointer to last node. 147 * Invariant: (first == null && last == null) || 148 * (last.next == null && last.item != null) 149 */ 150 transient Node<E> last; 151 152 /** Number of items in the deque */ 153 private transient int count; 154 155 /** Maximum number of items in the deque */ 156 private final int capacity; 157 158 /** Main lock guarding all access */ 159 final ReentrantLock lock = new ReentrantLock(); 160 161 /** Condition for waiting takes */ 162 @SuppressWarnings("serial") // Classes implementing Condition may be serializable. 163 private final Condition notEmpty = lock.newCondition(); 164 165 /** Condition for waiting puts */ 166 @SuppressWarnings("serial") // Classes implementing Condition may be serializable. 167 private final Condition notFull = lock.newCondition(); 168 169 /** 170 * Creates a {@code LinkedBlockingDeque} with a capacity of 171 * {@link Integer#MAX_VALUE}. 172 */ LinkedBlockingDeque()173 public LinkedBlockingDeque() { 174 this(Integer.MAX_VALUE); 175 } 176 177 /** 178 * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity. 179 * 180 * @param capacity the capacity of this deque 181 * @throws IllegalArgumentException if {@code capacity} is less than 1 182 */ LinkedBlockingDeque(int capacity)183 public LinkedBlockingDeque(int capacity) { 184 if (capacity <= 0) throw new IllegalArgumentException(); 185 this.capacity = capacity; 186 } 187 188 /** 189 * Creates a {@code LinkedBlockingDeque} with a capacity of 190 * {@link Integer#MAX_VALUE}, initially containing the elements of 191 * the given collection, added in traversal order of the 192 * collection's iterator. 193 * 194 * @param c the collection of elements to initially contain 195 * @throws NullPointerException if the specified collection or any 196 * of its elements are null 197 */ LinkedBlockingDeque(Collection<? extends E> c)198 public LinkedBlockingDeque(Collection<? extends E> c) { 199 this(Integer.MAX_VALUE); 200 addAll(c); 201 } 202 203 204 // Basic linking and unlinking operations, called only while holding lock 205 206 /** 207 * Links node as first element, or returns false if full. 208 */ linkFirst(Node<E> node)209 private boolean linkFirst(Node<E> node) { 210 // assert lock.isHeldByCurrentThread(); 211 if (count >= capacity) 212 return false; 213 Node<E> f = first; 214 node.next = f; 215 first = node; 216 if (last == null) 217 last = node; 218 else 219 f.prev = node; 220 ++count; 221 notEmpty.signal(); 222 return true; 223 } 224 225 /** 226 * Links node as last element, or returns false if full. 227 */ linkLast(Node<E> node)228 private boolean linkLast(Node<E> node) { 229 // assert lock.isHeldByCurrentThread(); 230 if (count >= capacity) 231 return false; 232 Node<E> l = last; 233 node.prev = l; 234 last = node; 235 if (first == null) 236 first = node; 237 else 238 l.next = node; 239 ++count; 240 notEmpty.signal(); 241 return true; 242 } 243 244 /** 245 * Removes and returns first element, or null if empty. 246 */ unlinkFirst()247 private E unlinkFirst() { 248 // assert lock.isHeldByCurrentThread(); 249 Node<E> f = first; 250 if (f == null) 251 return null; 252 Node<E> n = f.next; 253 E item = f.item; 254 f.item = null; 255 f.next = f; // help GC 256 first = n; 257 if (n == null) 258 last = null; 259 else 260 n.prev = null; 261 --count; 262 notFull.signal(); 263 return item; 264 } 265 266 /** 267 * Removes and returns last element, or null if empty. 268 */ unlinkLast()269 private E unlinkLast() { 270 // assert lock.isHeldByCurrentThread(); 271 Node<E> l = last; 272 if (l == null) 273 return null; 274 Node<E> p = l.prev; 275 E item = l.item; 276 l.item = null; 277 l.prev = l; // help GC 278 last = p; 279 if (p == null) 280 first = null; 281 else 282 p.next = null; 283 --count; 284 notFull.signal(); 285 return item; 286 } 287 288 /** 289 * Unlinks x. 290 */ unlink(Node<E> x)291 void unlink(Node<E> x) { 292 // assert lock.isHeldByCurrentThread(); 293 // assert x.item != null; 294 Node<E> p = x.prev; 295 Node<E> n = x.next; 296 if (p == null) { 297 unlinkFirst(); 298 } else if (n == null) { 299 unlinkLast(); 300 } else { 301 p.next = n; 302 n.prev = p; 303 x.item = null; 304 // Don't mess with x's links. They may still be in use by 305 // an iterator. 306 --count; 307 notFull.signal(); 308 } 309 } 310 311 // BlockingDeque methods 312 313 /** 314 * @throws IllegalStateException if this deque is full 315 * @throws NullPointerException {@inheritDoc} 316 */ addFirst(E e)317 public void addFirst(E e) { 318 if (!offerFirst(e)) 319 throw new IllegalStateException("Deque full"); 320 } 321 322 /** 323 * @throws IllegalStateException if this deque is full 324 * @throws NullPointerException {@inheritDoc} 325 */ addLast(E e)326 public void addLast(E e) { 327 if (!offerLast(e)) 328 throw new IllegalStateException("Deque full"); 329 } 330 331 /** 332 * @throws NullPointerException {@inheritDoc} 333 */ offerFirst(E e)334 public boolean offerFirst(E e) { 335 if (e == null) throw new NullPointerException(); 336 Node<E> node = new Node<E>(e); 337 final ReentrantLock lock = this.lock; 338 lock.lock(); 339 try { 340 return linkFirst(node); 341 } finally { 342 lock.unlock(); 343 } 344 } 345 346 /** 347 * @throws NullPointerException {@inheritDoc} 348 */ offerLast(E e)349 public boolean offerLast(E e) { 350 if (e == null) throw new NullPointerException(); 351 Node<E> node = new Node<E>(e); 352 final ReentrantLock lock = this.lock; 353 lock.lock(); 354 try { 355 return linkLast(node); 356 } finally { 357 lock.unlock(); 358 } 359 } 360 361 /** 362 * @throws NullPointerException {@inheritDoc} 363 * @throws InterruptedException {@inheritDoc} 364 */ putFirst(E e)365 public void putFirst(E e) throws InterruptedException { 366 if (e == null) throw new NullPointerException(); 367 Node<E> node = new Node<E>(e); 368 final ReentrantLock lock = this.lock; 369 lock.lock(); 370 try { 371 while (!linkFirst(node)) 372 notFull.await(); 373 } finally { 374 lock.unlock(); 375 } 376 } 377 378 /** 379 * @throws NullPointerException {@inheritDoc} 380 * @throws InterruptedException {@inheritDoc} 381 */ putLast(E e)382 public void putLast(E e) throws InterruptedException { 383 if (e == null) throw new NullPointerException(); 384 Node<E> node = new Node<E>(e); 385 final ReentrantLock lock = this.lock; 386 lock.lock(); 387 try { 388 while (!linkLast(node)) 389 notFull.await(); 390 } finally { 391 lock.unlock(); 392 } 393 } 394 395 /** 396 * @throws NullPointerException {@inheritDoc} 397 * @throws InterruptedException {@inheritDoc} 398 */ offerFirst(E e, long timeout, TimeUnit unit)399 public boolean offerFirst(E e, long timeout, TimeUnit unit) 400 throws InterruptedException { 401 if (e == null) throw new NullPointerException(); 402 Node<E> node = new Node<E>(e); 403 long nanos = unit.toNanos(timeout); 404 final ReentrantLock lock = this.lock; 405 lock.lockInterruptibly(); 406 try { 407 while (!linkFirst(node)) { 408 if (nanos <= 0L) 409 return false; 410 nanos = notFull.awaitNanos(nanos); 411 } 412 return true; 413 } finally { 414 lock.unlock(); 415 } 416 } 417 418 /** 419 * @throws NullPointerException {@inheritDoc} 420 * @throws InterruptedException {@inheritDoc} 421 */ offerLast(E e, long timeout, TimeUnit unit)422 public boolean offerLast(E e, long timeout, TimeUnit unit) 423 throws InterruptedException { 424 if (e == null) throw new NullPointerException(); 425 Node<E> node = new Node<E>(e); 426 long nanos = unit.toNanos(timeout); 427 final ReentrantLock lock = this.lock; 428 lock.lockInterruptibly(); 429 try { 430 while (!linkLast(node)) { 431 if (nanos <= 0L) 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 */ removeFirst()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 */ removeLast()453 public E removeLast() { 454 E x = pollLast(); 455 if (x == null) throw new NoSuchElementException(); 456 return x; 457 } 458 pollFirst()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 pollLast()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 takeFirst()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 takeLast()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 pollFirst(long timeout, TimeUnit unit)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 <= 0L) 514 return null; 515 nanos = notEmpty.awaitNanos(nanos); 516 } 517 return x; 518 } finally { 519 lock.unlock(); 520 } 521 } 522 pollLast(long timeout, TimeUnit unit)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 <= 0L) 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 */ getFirst()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 */ getLast()553 public E getLast() { 554 E x = peekLast(); 555 if (x == null) throw new NoSuchElementException(); 556 return x; 557 } 558 peekFirst()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 peekLast()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 removeFirstOccurrence(Object o)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 removeLastOccurrence(Object o)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 this deque is full 623 * @throws NullPointerException if the specified element is null 624 */ add(E e)625 public boolean add(E e) { 626 addLast(e); 627 return true; 628 } 629 630 /** 631 * @throws NullPointerException if the specified element is null 632 */ offer(E e)633 public boolean offer(E e) { 634 return offerLast(e); 635 } 636 637 /** 638 * @throws NullPointerException {@inheritDoc} 639 * @throws InterruptedException {@inheritDoc} 640 */ put(E e)641 public void put(E e) throws InterruptedException { 642 putLast(e); 643 } 644 645 /** 646 * @throws NullPointerException {@inheritDoc} 647 * @throws InterruptedException {@inheritDoc} 648 */ offer(E e, long timeout, TimeUnit unit)649 public boolean offer(E e, long timeout, TimeUnit unit) 650 throws InterruptedException { 651 return offerLast(e, timeout, unit); 652 } 653 654 /** 655 * Retrieves and removes the head of the queue represented by this deque. 656 * This method differs from {@link #poll() poll()} only in that it throws an 657 * exception if this deque is empty. 658 * 659 * <p>This method is equivalent to {@link #removeFirst() removeFirst}. 660 * 661 * @return the head of the queue represented by this deque 662 * @throws NoSuchElementException if this deque is empty 663 */ remove()664 public E remove() { 665 return removeFirst(); 666 } 667 poll()668 public E poll() { 669 return pollFirst(); 670 } 671 take()672 public E take() throws InterruptedException { 673 return takeFirst(); 674 } 675 poll(long timeout, TimeUnit unit)676 public E poll(long timeout, TimeUnit unit) throws InterruptedException { 677 return pollFirst(timeout, unit); 678 } 679 680 /** 681 * Retrieves, but does not remove, the head of the queue represented by 682 * this deque. This method differs from {@link #peek() peek()} only in that 683 * it throws an exception if this deque is empty. 684 * 685 * <p>This method is equivalent to {@link #getFirst() getFirst}. 686 * 687 * @return the head of the queue represented by this deque 688 * @throws NoSuchElementException if this deque is empty 689 */ element()690 public E element() { 691 return getFirst(); 692 } 693 peek()694 public E peek() { 695 return peekFirst(); 696 } 697 698 /** 699 * Returns the number of additional elements that this deque can ideally 700 * (in the absence of memory or resource constraints) accept without 701 * blocking. This is always equal to the initial capacity of this deque 702 * less the current {@code size} of this deque. 703 * 704 * <p>Note that you <em>cannot</em> always tell if an attempt to insert 705 * an element will succeed by inspecting {@code remainingCapacity} 706 * because it may be the case that another thread is about to 707 * insert or remove an element. 708 */ remainingCapacity()709 public int remainingCapacity() { 710 final ReentrantLock lock = this.lock; 711 lock.lock(); 712 try { 713 return capacity - count; 714 } finally { 715 lock.unlock(); 716 } 717 } 718 719 /** 720 * @throws UnsupportedOperationException {@inheritDoc} 721 * @throws ClassCastException {@inheritDoc} 722 * @throws NullPointerException {@inheritDoc} 723 * @throws IllegalArgumentException {@inheritDoc} 724 */ drainTo(Collection<? super E> c)725 public int drainTo(Collection<? super E> c) { 726 return drainTo(c, Integer.MAX_VALUE); 727 } 728 729 /** 730 * @throws UnsupportedOperationException {@inheritDoc} 731 * @throws ClassCastException {@inheritDoc} 732 * @throws NullPointerException {@inheritDoc} 733 * @throws IllegalArgumentException {@inheritDoc} 734 */ drainTo(Collection<? super E> c, int maxElements)735 public int drainTo(Collection<? super E> c, int maxElements) { 736 Objects.requireNonNull(c); 737 if (c == this) 738 throw new IllegalArgumentException(); 739 if (maxElements <= 0) 740 return 0; 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 if this deque is full 759 * @throws NullPointerException {@inheritDoc} 760 */ push(E e)761 public void push(E e) { 762 addFirst(e); 763 } 764 765 /** 766 * @throws NoSuchElementException {@inheritDoc} 767 */ pop()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 */ remove(Object o)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 */ size()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 */ contains(Object o)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 * Appends all of the elements in the specified collection to the end of 831 * this deque, in the order that they are returned by the specified 832 * collection's iterator. Attempts to {@code addAll} of a deque to 833 * itself result in {@code IllegalArgumentException}. 834 * 835 * @param c the elements to be inserted into this deque 836 * @return {@code true} if this deque changed as a result of the call 837 * @throws NullPointerException if the specified collection or any 838 * of its elements are null 839 * @throws IllegalArgumentException if the collection is this deque 840 * @throws IllegalStateException if this deque is full 841 * @see #add(Object) 842 */ addAll(Collection<? extends E> c)843 public boolean addAll(Collection<? extends E> c) { 844 if (c == this) 845 // As historically specified in AbstractQueue#addAll 846 throw new IllegalArgumentException(); 847 848 // Copy c into a private chain of Nodes 849 Node<E> beg = null, end = null; 850 int n = 0; 851 for (E e : c) { 852 Objects.requireNonNull(e); 853 n++; 854 Node<E> newNode = new Node<E>(e); 855 if (beg == null) 856 beg = end = newNode; 857 else { 858 end.next = newNode; 859 newNode.prev = end; 860 end = newNode; 861 } 862 } 863 if (beg == null) 864 return false; 865 866 // Atomically append the chain at the end 867 final ReentrantLock lock = this.lock; 868 lock.lock(); 869 try { 870 if (count + n <= capacity) { 871 beg.prev = last; 872 if (first == null) 873 first = beg; 874 else 875 last.next = beg; 876 last = end; 877 count += n; 878 notEmpty.signalAll(); 879 return true; 880 } 881 } finally { 882 lock.unlock(); 883 } 884 // Fall back to historic non-atomic implementation, failing 885 // with IllegalStateException when the capacity is exceeded. 886 return super.addAll(c); 887 } 888 889 /** 890 * Returns an array containing all of the elements in this deque, in 891 * proper sequence (from first to last element). 892 * 893 * <p>The returned array will be "safe" in that no references to it are 894 * maintained by this deque. (In other words, this method must allocate 895 * a new array). The caller is thus free to modify the returned array. 896 * 897 * <p>This method acts as bridge between array-based and collection-based 898 * APIs. 899 * 900 * @return an array containing all of the elements in this deque 901 */ 902 @SuppressWarnings("unchecked") toArray()903 public Object[] toArray() { 904 final ReentrantLock lock = this.lock; 905 lock.lock(); 906 try { 907 Object[] a = new Object[count]; 908 int k = 0; 909 for (Node<E> p = first; p != null; p = p.next) 910 a[k++] = p.item; 911 return a; 912 } finally { 913 lock.unlock(); 914 } 915 } 916 917 /** 918 * Returns an array containing all of the elements in this deque, in 919 * proper sequence; the runtime type of the returned array is that of 920 * the specified array. If the deque fits in the specified array, it 921 * is returned therein. Otherwise, a new array is allocated with the 922 * runtime type of the specified array and the size of this deque. 923 * 924 * <p>If this deque fits in the specified array with room to spare 925 * (i.e., the array has more elements than this deque), the element in 926 * the array immediately following the end of the deque is set to 927 * {@code null}. 928 * 929 * <p>Like the {@link #toArray()} method, this method acts as bridge between 930 * array-based and collection-based APIs. Further, this method allows 931 * precise control over the runtime type of the output array, and may, 932 * under certain circumstances, be used to save allocation costs. 933 * 934 * <p>Suppose {@code x} is a deque known to contain only strings. 935 * The following code can be used to dump the deque into a newly 936 * allocated array of {@code String}: 937 * 938 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 939 * 940 * Note that {@code toArray(new Object[0])} is identical in function to 941 * {@code toArray()}. 942 * 943 * @param a the array into which the elements of the deque are to 944 * be stored, if it is big enough; otherwise, a new array of the 945 * same runtime type is allocated for this purpose 946 * @return an array containing all of the elements in this deque 947 * @throws ArrayStoreException if the runtime type of the specified array 948 * is not a supertype of the runtime type of every element in 949 * this deque 950 * @throws NullPointerException if the specified array is null 951 */ 952 @SuppressWarnings("unchecked") toArray(T[] a)953 public <T> T[] toArray(T[] a) { 954 final ReentrantLock lock = this.lock; 955 lock.lock(); 956 try { 957 if (a.length < count) 958 a = (T[])java.lang.reflect.Array.newInstance 959 (a.getClass().getComponentType(), count); 960 961 int k = 0; 962 for (Node<E> p = first; p != null; p = p.next) 963 a[k++] = (T)p.item; 964 if (a.length > k) 965 a[k] = null; 966 return a; 967 } finally { 968 lock.unlock(); 969 } 970 } 971 toString()972 public String toString() { 973 return Helpers.collectionToString(this); 974 } 975 976 /** 977 * Atomically removes all of the elements from this deque. 978 * The deque will be empty after this call returns. 979 */ clear()980 public void clear() { 981 final ReentrantLock lock = this.lock; 982 lock.lock(); 983 try { 984 for (Node<E> f = first; f != null; ) { 985 f.item = null; 986 Node<E> n = f.next; 987 f.prev = null; 988 f.next = null; 989 f = n; 990 } 991 first = last = null; 992 count = 0; 993 notFull.signalAll(); 994 } finally { 995 lock.unlock(); 996 } 997 } 998 999 /** 1000 * Used for any element traversal that is not entirely under lock. 1001 * Such traversals must handle both: 1002 * - dequeued nodes (p.next == p) 1003 * - (possibly multiple) interior removed nodes (p.item == null) 1004 */ succ(Node<E> p)1005 Node<E> succ(Node<E> p) { 1006 if (p == (p = p.next)) 1007 p = first; 1008 return p; 1009 } 1010 1011 /** 1012 * Returns an iterator over the elements in this deque in proper sequence. 1013 * The elements will be returned in order from first (head) to last (tail). 1014 * 1015 * <p>The returned iterator is 1016 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1017 * 1018 * @return an iterator over the elements in this deque in proper sequence 1019 */ iterator()1020 public Iterator<E> iterator() { 1021 return new Itr(); 1022 } 1023 1024 /** 1025 * Returns an iterator over the elements in this deque in reverse 1026 * sequential order. The elements will be returned in order from 1027 * last (tail) to first (head). 1028 * 1029 * <p>The returned iterator is 1030 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1031 * 1032 * @return an iterator over the elements in this deque in reverse order 1033 */ descendingIterator()1034 public Iterator<E> descendingIterator() { 1035 return new DescendingItr(); 1036 } 1037 1038 /** 1039 * Base class for LinkedBlockingDeque iterators. 1040 */ 1041 private abstract class AbstractItr implements Iterator<E> { 1042 /** 1043 * The next node to return in next(). 1044 */ 1045 Node<E> next; 1046 1047 /** 1048 * nextItem holds on to item fields because once we claim that 1049 * an element exists in hasNext(), we must return item read 1050 * under lock even if it was in the process of being removed 1051 * when hasNext() was called. 1052 */ 1053 E nextItem; 1054 1055 /** 1056 * Node returned by most recent call to next. Needed by remove. 1057 * Reset to null if this element is deleted by a call to remove. 1058 */ 1059 private Node<E> lastRet; 1060 firstNode()1061 abstract Node<E> firstNode(); nextNode(Node<E> n)1062 abstract Node<E> nextNode(Node<E> n); 1063 succ(Node<E> p)1064 private Node<E> succ(Node<E> p) { 1065 if (p == (p = nextNode(p))) 1066 p = firstNode(); 1067 return p; 1068 } 1069 AbstractItr()1070 AbstractItr() { 1071 // set to initial position 1072 final ReentrantLock lock = LinkedBlockingDeque.this.lock; 1073 lock.lock(); 1074 try { 1075 if ((next = firstNode()) != null) 1076 nextItem = next.item; 1077 } finally { 1078 lock.unlock(); 1079 } 1080 } 1081 hasNext()1082 public boolean hasNext() { 1083 return next != null; 1084 } 1085 next()1086 public E next() { 1087 Node<E> p; 1088 if ((p = next) == null) 1089 throw new NoSuchElementException(); 1090 lastRet = p; 1091 E x = nextItem; 1092 final ReentrantLock lock = LinkedBlockingDeque.this.lock; 1093 lock.lock(); 1094 try { 1095 E e = null; 1096 for (p = nextNode(p); p != null && (e = p.item) == null; ) 1097 p = succ(p); 1098 next = p; 1099 nextItem = e; 1100 } finally { 1101 lock.unlock(); 1102 } 1103 return x; 1104 } 1105 forEachRemaining(Consumer<? super E> action)1106 public void forEachRemaining(Consumer<? super E> action) { 1107 // A variant of forEachFrom 1108 Objects.requireNonNull(action); 1109 Node<E> p; 1110 if ((p = next) == null) return; 1111 lastRet = p; 1112 next = null; 1113 final ReentrantLock lock = LinkedBlockingDeque.this.lock; 1114 final int batchSize = 64; 1115 Object[] es = null; 1116 int n, len = 1; 1117 do { 1118 lock.lock(); 1119 try { 1120 if (es == null) { 1121 p = nextNode(p); 1122 for (Node<E> q = p; q != null; q = succ(q)) 1123 if (q.item != null && ++len == batchSize) 1124 break; 1125 es = new Object[len]; 1126 es[0] = nextItem; 1127 nextItem = null; 1128 n = 1; 1129 } else 1130 n = 0; 1131 for (; p != null && n < len; p = succ(p)) 1132 if ((es[n] = p.item) != null) { 1133 lastRet = p; 1134 n++; 1135 } 1136 } finally { 1137 lock.unlock(); 1138 } 1139 for (int i = 0; i < n; i++) { 1140 @SuppressWarnings("unchecked") E e = (E) es[i]; 1141 action.accept(e); 1142 } 1143 } while (n > 0 && p != null); 1144 } 1145 remove()1146 public void remove() { 1147 Node<E> n = lastRet; 1148 if (n == null) 1149 throw new IllegalStateException(); 1150 lastRet = null; 1151 final ReentrantLock lock = LinkedBlockingDeque.this.lock; 1152 lock.lock(); 1153 try { 1154 if (n.item != null) 1155 unlink(n); 1156 } finally { 1157 lock.unlock(); 1158 } 1159 } 1160 } 1161 1162 /** Forward iterator */ 1163 private class Itr extends AbstractItr { Itr()1164 Itr() {} // prevent access constructor creation firstNode()1165 Node<E> firstNode() { return first; } nextNode(Node<E> n)1166 Node<E> nextNode(Node<E> n) { return n.next; } 1167 } 1168 1169 /** Descending iterator */ 1170 private class DescendingItr extends AbstractItr { DescendingItr()1171 DescendingItr() {} // prevent access constructor creation firstNode()1172 Node<E> firstNode() { return last; } nextNode(Node<E> n)1173 Node<E> nextNode(Node<E> n) { return n.prev; } 1174 } 1175 1176 /** 1177 * A customized variant of Spliterators.IteratorSpliterator. 1178 * Keep this class in sync with (very similar) LBQSpliterator. 1179 */ 1180 private final class LBDSpliterator implements Spliterator<E> { 1181 static final int MAX_BATCH = 1 << 25; // max batch array size; 1182 Node<E> current; // current node; null until initialized 1183 int batch; // batch size for splits 1184 boolean exhausted; // true when no more nodes 1185 long est = size(); // size estimate 1186 LBDSpliterator()1187 LBDSpliterator() {} 1188 estimateSize()1189 public long estimateSize() { return est; } 1190 trySplit()1191 public Spliterator<E> trySplit() { 1192 Node<E> h; 1193 if (!exhausted && 1194 ((h = current) != null || (h = first) != null) 1195 && h.next != null) { 1196 int n = batch = Math.min(batch + 1, MAX_BATCH); 1197 Object[] a = new Object[n]; 1198 final ReentrantLock lock = LinkedBlockingDeque.this.lock; 1199 int i = 0; 1200 Node<E> p = current; 1201 lock.lock(); 1202 try { 1203 if (p != null || (p = first) != null) 1204 for (; p != null && i < n; p = succ(p)) 1205 if ((a[i] = p.item) != null) 1206 i++; 1207 } finally { 1208 lock.unlock(); 1209 } 1210 if ((current = p) == null) { 1211 est = 0L; 1212 exhausted = true; 1213 } 1214 else if ((est -= i) < 0L) 1215 est = 0L; 1216 if (i > 0) 1217 return Spliterators.spliterator 1218 (a, 0, i, (Spliterator.ORDERED | 1219 Spliterator.NONNULL | 1220 Spliterator.CONCURRENT)); 1221 } 1222 return null; 1223 } 1224 tryAdvance(Consumer<? super E> action)1225 public boolean tryAdvance(Consumer<? super E> action) { 1226 Objects.requireNonNull(action); 1227 if (!exhausted) { 1228 E e = null; 1229 final ReentrantLock lock = LinkedBlockingDeque.this.lock; 1230 lock.lock(); 1231 try { 1232 Node<E> p; 1233 if ((p = current) != null || (p = first) != null) 1234 do { 1235 e = p.item; 1236 p = succ(p); 1237 } while (e == null && p != null); 1238 if ((current = p) == null) 1239 exhausted = true; 1240 } finally { 1241 lock.unlock(); 1242 } 1243 if (e != null) { 1244 action.accept(e); 1245 return true; 1246 } 1247 } 1248 return false; 1249 } 1250 forEachRemaining(Consumer<? super E> action)1251 public void forEachRemaining(Consumer<? super E> action) { 1252 Objects.requireNonNull(action); 1253 if (!exhausted) { 1254 exhausted = true; 1255 Node<E> p = current; 1256 current = null; 1257 forEachFrom(action, p); 1258 } 1259 } 1260 characteristics()1261 public int characteristics() { 1262 return (Spliterator.ORDERED | 1263 Spliterator.NONNULL | 1264 Spliterator.CONCURRENT); 1265 } 1266 } 1267 1268 /** 1269 * Returns a {@link Spliterator} over the elements in this deque. 1270 * 1271 * <p>The returned spliterator is 1272 * <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>. 1273 * 1274 * <p>The {@code Spliterator} reports {@link Spliterator#CONCURRENT}, 1275 * {@link Spliterator#ORDERED}, and {@link Spliterator#NONNULL}. 1276 * 1277 * @implNote 1278 * The {@code Spliterator} implements {@code trySplit} to permit limited 1279 * parallelism. 1280 * 1281 * @return a {@code Spliterator} over the elements in this deque 1282 * @since 1.8 1283 */ spliterator()1284 public Spliterator<E> spliterator() { 1285 return new LBDSpliterator(); 1286 } 1287 1288 /** 1289 * @throws NullPointerException {@inheritDoc} 1290 */ forEach(Consumer<? super E> action)1291 public void forEach(Consumer<? super E> action) { 1292 Objects.requireNonNull(action); 1293 forEachFrom(action, null); 1294 } 1295 1296 /** 1297 * Runs action on each element found during a traversal starting at p. 1298 * If p is null, traversal starts at head. 1299 */ forEachFrom(Consumer<? super E> action, Node<E> p)1300 void forEachFrom(Consumer<? super E> action, Node<E> p) { 1301 // Extract batches of elements while holding the lock; then 1302 // run the action on the elements while not 1303 final ReentrantLock lock = this.lock; 1304 final int batchSize = 64; // max number of elements per batch 1305 Object[] es = null; // container for batch of elements 1306 int n, len = 0; 1307 do { 1308 lock.lock(); 1309 try { 1310 if (es == null) { 1311 if (p == null) p = first; 1312 for (Node<E> q = p; q != null; q = succ(q)) 1313 if (q.item != null && ++len == batchSize) 1314 break; 1315 es = new Object[len]; 1316 } 1317 for (n = 0; p != null && n < len; p = succ(p)) 1318 if ((es[n] = p.item) != null) 1319 n++; 1320 } finally { 1321 lock.unlock(); 1322 } 1323 for (int i = 0; i < n; i++) { 1324 @SuppressWarnings("unchecked") E e = (E) es[i]; 1325 action.accept(e); 1326 } 1327 } while (n > 0 && p != null); 1328 } 1329 1330 /** 1331 * @throws NullPointerException {@inheritDoc} 1332 */ removeIf(Predicate<? super E> filter)1333 public boolean removeIf(Predicate<? super E> filter) { 1334 Objects.requireNonNull(filter); 1335 return bulkRemove(filter); 1336 } 1337 1338 /** 1339 * @throws NullPointerException {@inheritDoc} 1340 */ removeAll(Collection<?> c)1341 public boolean removeAll(Collection<?> c) { 1342 Objects.requireNonNull(c); 1343 return bulkRemove(e -> c.contains(e)); 1344 } 1345 1346 /** 1347 * @throws NullPointerException {@inheritDoc} 1348 */ retainAll(Collection<?> c)1349 public boolean retainAll(Collection<?> c) { 1350 Objects.requireNonNull(c); 1351 return bulkRemove(e -> !c.contains(e)); 1352 } 1353 1354 /** Implementation of bulk remove methods. */ 1355 @SuppressWarnings("unchecked") bulkRemove(Predicate<? super E> filter)1356 private boolean bulkRemove(Predicate<? super E> filter) { 1357 boolean removed = false; 1358 final ReentrantLock lock = this.lock; 1359 Node<E> p = null; 1360 Node<E>[] nodes = null; 1361 int n, len = 0; 1362 do { 1363 // 1. Extract batch of up to 64 elements while holding the lock. 1364 lock.lock(); 1365 try { 1366 if (nodes == null) { // first batch; initialize 1367 p = first; 1368 for (Node<E> q = p; q != null; q = succ(q)) 1369 if (q.item != null && ++len == 64) 1370 break; 1371 nodes = (Node<E>[]) new Node<?>[len]; 1372 } 1373 for (n = 0; p != null && n < len; p = succ(p)) 1374 nodes[n++] = p; 1375 } finally { 1376 lock.unlock(); 1377 } 1378 1379 // 2. Run the filter on the elements while lock is free. 1380 long deathRow = 0L; // "bitset" of size 64 1381 for (int i = 0; i < n; i++) { 1382 final E e; 1383 if ((e = nodes[i].item) != null && filter.test(e)) 1384 deathRow |= 1L << i; 1385 } 1386 1387 // 3. Remove any filtered elements while holding the lock. 1388 if (deathRow != 0) { 1389 lock.lock(); 1390 try { 1391 for (int i = 0; i < n; i++) { 1392 final Node<E> q; 1393 if ((deathRow & (1L << i)) != 0L 1394 && (q = nodes[i]).item != null) { 1395 unlink(q); 1396 removed = true; 1397 } 1398 nodes[i] = null; // help GC 1399 } 1400 } finally { 1401 lock.unlock(); 1402 } 1403 } 1404 } while (n > 0 && p != null); 1405 return removed; 1406 } 1407 1408 /** 1409 * Saves this deque to a stream (that is, serializes it). 1410 * 1411 * @param s the stream 1412 * @throws java.io.IOException if an I/O error occurs 1413 * @serialData The capacity (int), followed by elements (each an 1414 * {@code Object}) in the proper order, followed by a null 1415 */ writeObject(java.io.ObjectOutputStream s)1416 private void writeObject(java.io.ObjectOutputStream s) 1417 throws java.io.IOException { 1418 final ReentrantLock lock = this.lock; 1419 lock.lock(); 1420 try { 1421 // Write out capacity and any hidden stuff 1422 s.defaultWriteObject(); 1423 // Write out all elements in the proper order. 1424 for (Node<E> p = first; p != null; p = p.next) 1425 s.writeObject(p.item); 1426 // Use trailing null as sentinel 1427 s.writeObject(null); 1428 } finally { 1429 lock.unlock(); 1430 } 1431 } 1432 1433 /** 1434 * Reconstitutes this deque from a stream (that is, deserializes it). 1435 * @param s the stream 1436 * @throws ClassNotFoundException if the class of a serialized object 1437 * could not be found 1438 * @throws java.io.IOException if an I/O error occurs 1439 */ readObject(java.io.ObjectInputStream s)1440 private void readObject(java.io.ObjectInputStream s) 1441 throws java.io.IOException, ClassNotFoundException { 1442 s.defaultReadObject(); 1443 count = 0; 1444 first = null; 1445 last = null; 1446 // Read in all elements and place in queue 1447 for (;;) { 1448 @SuppressWarnings("unchecked") E item = (E)s.readObject(); 1449 if (item == null) 1450 break; 1451 add(item); 1452 } 1453 } 1454 checkInvariants()1455 void checkInvariants() { 1456 // assert lock.isHeldByCurrentThread(); 1457 // Nodes may get self-linked or lose their item, but only 1458 // after being unlinked and becoming unreachable from first. 1459 for (Node<E> p = first; p != null; p = p.next) { 1460 // assert p.next != p; 1461 // assert p.item != null; 1462 } 1463 } 1464 1465 } 1466