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