1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/LinkedBlockingDeque.java Sat Mar 19 10:46:31 2016 +0100
1.3 @@ -0,0 +1,1198 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.6 + *
1.7 + * This code is free software; you can redistribute it and/or modify it
1.8 + * under the terms of the GNU General Public License version 2 only, as
1.9 + * published by the Free Software Foundation. Oracle designates this
1.10 + * particular file as subject to the "Classpath" exception as provided
1.11 + * by Oracle in the LICENSE file that accompanied this code.
1.12 + *
1.13 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.14 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.15 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.16 + * version 2 for more details (a copy is included in the LICENSE file that
1.17 + * accompanied this code).
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License version
1.20 + * 2 along with this work; if not, write to the Free Software Foundation,
1.21 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.22 + *
1.23 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.24 + * or visit www.oracle.com if you need additional information or have any
1.25 + * questions.
1.26 + */
1.27 +
1.28 +/*
1.29 + * This file is available under and governed by the GNU General Public
1.30 + * License version 2 only, as published by the Free Software Foundation.
1.31 + * However, the following notice accompanied the original version of this
1.32 + * file:
1.33 + *
1.34 + * Written by Doug Lea with assistance from members of JCP JSR-166
1.35 + * Expert Group and released to the public domain, as explained at
1.36 + * http://creativecommons.org/publicdomain/zero/1.0/
1.37 + */
1.38 +
1.39 +package java.util.concurrent;
1.40 +
1.41 +import java.util.AbstractQueue;
1.42 +import java.util.Collection;
1.43 +import java.util.Iterator;
1.44 +import java.util.NoSuchElementException;
1.45 +import java.util.concurrent.locks.Condition;
1.46 +import java.util.concurrent.locks.ReentrantLock;
1.47 +
1.48 +/**
1.49 + * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on
1.50 + * linked nodes.
1.51 + *
1.52 + * <p> The optional capacity bound constructor argument serves as a
1.53 + * way to prevent excessive expansion. The capacity, if unspecified,
1.54 + * is equal to {@link Integer#MAX_VALUE}. Linked nodes are
1.55 + * dynamically created upon each insertion unless this would bring the
1.56 + * deque above capacity.
1.57 + *
1.58 + * <p>Most operations run in constant time (ignoring time spent
1.59 + * blocking). Exceptions include {@link #remove(Object) remove},
1.60 + * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link
1.61 + * #removeLastOccurrence removeLastOccurrence}, {@link #contains
1.62 + * contains}, {@link #iterator iterator.remove()}, and the bulk
1.63 + * operations, all of which run in linear time.
1.64 + *
1.65 + * <p>This class and its iterator implement all of the
1.66 + * <em>optional</em> methods of the {@link Collection} and {@link
1.67 + * Iterator} interfaces.
1.68 + *
1.69 + * <p>This class is a member of the
1.70 + * <a href="{@docRoot}/../technotes/guides/collections/index.html">
1.71 + * Java Collections Framework</a>.
1.72 + *
1.73 + * @since 1.6
1.74 + * @author Doug Lea
1.75 + * @param <E> the type of elements held in this collection
1.76 + */
1.77 +public class LinkedBlockingDeque<E>
1.78 + extends AbstractQueue<E>
1.79 + implements BlockingDeque<E>, java.io.Serializable {
1.80 +
1.81 + /*
1.82 + * Implemented as a simple doubly-linked list protected by a
1.83 + * single lock and using conditions to manage blocking.
1.84 + *
1.85 + * To implement weakly consistent iterators, it appears we need to
1.86 + * keep all Nodes GC-reachable from a predecessor dequeued Node.
1.87 + * That would cause two problems:
1.88 + * - allow a rogue Iterator to cause unbounded memory retention
1.89 + * - cause cross-generational linking of old Nodes to new Nodes if
1.90 + * a Node was tenured while live, which generational GCs have a
1.91 + * hard time dealing with, causing repeated major collections.
1.92 + * However, only non-deleted Nodes need to be reachable from
1.93 + * dequeued Nodes, and reachability does not necessarily have to
1.94 + * be of the kind understood by the GC. We use the trick of
1.95 + * linking a Node that has just been dequeued to itself. Such a
1.96 + * self-link implicitly means to jump to "first" (for next links)
1.97 + * or "last" (for prev links).
1.98 + */
1.99 +
1.100 + /*
1.101 + * We have "diamond" multiple interface/abstract class inheritance
1.102 + * here, and that introduces ambiguities. Often we want the
1.103 + * BlockingDeque javadoc combined with the AbstractQueue
1.104 + * implementation, so a lot of method specs are duplicated here.
1.105 + */
1.106 +
1.107 + private static final long serialVersionUID = -387911632671998426L;
1.108 +
1.109 + /** Doubly-linked list node class */
1.110 + static final class Node<E> {
1.111 + /**
1.112 + * The item, or null if this node has been removed.
1.113 + */
1.114 + E item;
1.115 +
1.116 + /**
1.117 + * One of:
1.118 + * - the real predecessor Node
1.119 + * - this Node, meaning the predecessor is tail
1.120 + * - null, meaning there is no predecessor
1.121 + */
1.122 + Node<E> prev;
1.123 +
1.124 + /**
1.125 + * One of:
1.126 + * - the real successor Node
1.127 + * - this Node, meaning the successor is head
1.128 + * - null, meaning there is no successor
1.129 + */
1.130 + Node<E> next;
1.131 +
1.132 + Node(E x) {
1.133 + item = x;
1.134 + }
1.135 + }
1.136 +
1.137 + /**
1.138 + * Pointer to first node.
1.139 + * Invariant: (first == null && last == null) ||
1.140 + * (first.prev == null && first.item != null)
1.141 + */
1.142 + transient Node<E> first;
1.143 +
1.144 + /**
1.145 + * Pointer to last node.
1.146 + * Invariant: (first == null && last == null) ||
1.147 + * (last.next == null && last.item != null)
1.148 + */
1.149 + transient Node<E> last;
1.150 +
1.151 + /** Number of items in the deque */
1.152 + private transient int count;
1.153 +
1.154 + /** Maximum number of items in the deque */
1.155 + private final int capacity;
1.156 +
1.157 + /** Main lock guarding all access */
1.158 + final ReentrantLock lock = new ReentrantLock();
1.159 +
1.160 + /** Condition for waiting takes */
1.161 + private final Condition notEmpty = lock.newCondition();
1.162 +
1.163 + /** Condition for waiting puts */
1.164 + private final Condition notFull = lock.newCondition();
1.165 +
1.166 + /**
1.167 + * Creates a {@code LinkedBlockingDeque} with a capacity of
1.168 + * {@link Integer#MAX_VALUE}.
1.169 + */
1.170 + public LinkedBlockingDeque() {
1.171 + this(Integer.MAX_VALUE);
1.172 + }
1.173 +
1.174 + /**
1.175 + * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.
1.176 + *
1.177 + * @param capacity the capacity of this deque
1.178 + * @throws IllegalArgumentException if {@code capacity} is less than 1
1.179 + */
1.180 + public LinkedBlockingDeque(int capacity) {
1.181 + if (capacity <= 0) throw new IllegalArgumentException();
1.182 + this.capacity = capacity;
1.183 + }
1.184 +
1.185 + /**
1.186 + * Creates a {@code LinkedBlockingDeque} with a capacity of
1.187 + * {@link Integer#MAX_VALUE}, initially containing the elements of
1.188 + * the given collection, added in traversal order of the
1.189 + * collection's iterator.
1.190 + *
1.191 + * @param c the collection of elements to initially contain
1.192 + * @throws NullPointerException if the specified collection or any
1.193 + * of its elements are null
1.194 + */
1.195 + public LinkedBlockingDeque(Collection<? extends E> c) {
1.196 + this(Integer.MAX_VALUE);
1.197 + final ReentrantLock lock = this.lock;
1.198 + lock.lock(); // Never contended, but necessary for visibility
1.199 + try {
1.200 + for (E e : c) {
1.201 + if (e == null)
1.202 + throw new NullPointerException();
1.203 + if (!linkLast(new Node<E>(e)))
1.204 + throw new IllegalStateException("Deque full");
1.205 + }
1.206 + } finally {
1.207 + lock.unlock();
1.208 + }
1.209 + }
1.210 +
1.211 +
1.212 + // Basic linking and unlinking operations, called only while holding lock
1.213 +
1.214 + /**
1.215 + * Links node as first element, or returns false if full.
1.216 + */
1.217 + private boolean linkFirst(Node<E> node) {
1.218 + // assert lock.isHeldByCurrentThread();
1.219 + if (count >= capacity)
1.220 + return false;
1.221 + Node<E> f = first;
1.222 + node.next = f;
1.223 + first = node;
1.224 + if (last == null)
1.225 + last = node;
1.226 + else
1.227 + f.prev = node;
1.228 + ++count;
1.229 + notEmpty.signal();
1.230 + return true;
1.231 + }
1.232 +
1.233 + /**
1.234 + * Links node as last element, or returns false if full.
1.235 + */
1.236 + private boolean linkLast(Node<E> node) {
1.237 + // assert lock.isHeldByCurrentThread();
1.238 + if (count >= capacity)
1.239 + return false;
1.240 + Node<E> l = last;
1.241 + node.prev = l;
1.242 + last = node;
1.243 + if (first == null)
1.244 + first = node;
1.245 + else
1.246 + l.next = node;
1.247 + ++count;
1.248 + notEmpty.signal();
1.249 + return true;
1.250 + }
1.251 +
1.252 + /**
1.253 + * Removes and returns first element, or null if empty.
1.254 + */
1.255 + private E unlinkFirst() {
1.256 + // assert lock.isHeldByCurrentThread();
1.257 + Node<E> f = first;
1.258 + if (f == null)
1.259 + return null;
1.260 + Node<E> n = f.next;
1.261 + E item = f.item;
1.262 + f.item = null;
1.263 + f.next = f; // help GC
1.264 + first = n;
1.265 + if (n == null)
1.266 + last = null;
1.267 + else
1.268 + n.prev = null;
1.269 + --count;
1.270 + notFull.signal();
1.271 + return item;
1.272 + }
1.273 +
1.274 + /**
1.275 + * Removes and returns last element, or null if empty.
1.276 + */
1.277 + private E unlinkLast() {
1.278 + // assert lock.isHeldByCurrentThread();
1.279 + Node<E> l = last;
1.280 + if (l == null)
1.281 + return null;
1.282 + Node<E> p = l.prev;
1.283 + E item = l.item;
1.284 + l.item = null;
1.285 + l.prev = l; // help GC
1.286 + last = p;
1.287 + if (p == null)
1.288 + first = null;
1.289 + else
1.290 + p.next = null;
1.291 + --count;
1.292 + notFull.signal();
1.293 + return item;
1.294 + }
1.295 +
1.296 + /**
1.297 + * Unlinks x.
1.298 + */
1.299 + void unlink(Node<E> x) {
1.300 + // assert lock.isHeldByCurrentThread();
1.301 + Node<E> p = x.prev;
1.302 + Node<E> n = x.next;
1.303 + if (p == null) {
1.304 + unlinkFirst();
1.305 + } else if (n == null) {
1.306 + unlinkLast();
1.307 + } else {
1.308 + p.next = n;
1.309 + n.prev = p;
1.310 + x.item = null;
1.311 + // Don't mess with x's links. They may still be in use by
1.312 + // an iterator.
1.313 + --count;
1.314 + notFull.signal();
1.315 + }
1.316 + }
1.317 +
1.318 + // BlockingDeque methods
1.319 +
1.320 + /**
1.321 + * @throws IllegalStateException {@inheritDoc}
1.322 + * @throws NullPointerException {@inheritDoc}
1.323 + */
1.324 + public void addFirst(E e) {
1.325 + if (!offerFirst(e))
1.326 + throw new IllegalStateException("Deque full");
1.327 + }
1.328 +
1.329 + /**
1.330 + * @throws IllegalStateException {@inheritDoc}
1.331 + * @throws NullPointerException {@inheritDoc}
1.332 + */
1.333 + public void addLast(E e) {
1.334 + if (!offerLast(e))
1.335 + throw new IllegalStateException("Deque full");
1.336 + }
1.337 +
1.338 + /**
1.339 + * @throws NullPointerException {@inheritDoc}
1.340 + */
1.341 + public boolean offerFirst(E e) {
1.342 + if (e == null) throw new NullPointerException();
1.343 + Node<E> node = new Node<E>(e);
1.344 + final ReentrantLock lock = this.lock;
1.345 + lock.lock();
1.346 + try {
1.347 + return linkFirst(node);
1.348 + } finally {
1.349 + lock.unlock();
1.350 + }
1.351 + }
1.352 +
1.353 + /**
1.354 + * @throws NullPointerException {@inheritDoc}
1.355 + */
1.356 + public boolean offerLast(E e) {
1.357 + if (e == null) throw new NullPointerException();
1.358 + Node<E> node = new Node<E>(e);
1.359 + final ReentrantLock lock = this.lock;
1.360 + lock.lock();
1.361 + try {
1.362 + return linkLast(node);
1.363 + } finally {
1.364 + lock.unlock();
1.365 + }
1.366 + }
1.367 +
1.368 + /**
1.369 + * @throws NullPointerException {@inheritDoc}
1.370 + * @throws InterruptedException {@inheritDoc}
1.371 + */
1.372 + public void putFirst(E e) throws InterruptedException {
1.373 + if (e == null) throw new NullPointerException();
1.374 + Node<E> node = new Node<E>(e);
1.375 + final ReentrantLock lock = this.lock;
1.376 + lock.lock();
1.377 + try {
1.378 + while (!linkFirst(node))
1.379 + notFull.await();
1.380 + } finally {
1.381 + lock.unlock();
1.382 + }
1.383 + }
1.384 +
1.385 + /**
1.386 + * @throws NullPointerException {@inheritDoc}
1.387 + * @throws InterruptedException {@inheritDoc}
1.388 + */
1.389 + public void putLast(E e) throws InterruptedException {
1.390 + if (e == null) throw new NullPointerException();
1.391 + Node<E> node = new Node<E>(e);
1.392 + final ReentrantLock lock = this.lock;
1.393 + lock.lock();
1.394 + try {
1.395 + while (!linkLast(node))
1.396 + notFull.await();
1.397 + } finally {
1.398 + lock.unlock();
1.399 + }
1.400 + }
1.401 +
1.402 + /**
1.403 + * @throws NullPointerException {@inheritDoc}
1.404 + * @throws InterruptedException {@inheritDoc}
1.405 + */
1.406 + public boolean offerFirst(E e, long timeout, TimeUnit unit)
1.407 + throws InterruptedException {
1.408 + if (e == null) throw new NullPointerException();
1.409 + Node<E> node = new Node<E>(e);
1.410 + long nanos = unit.toNanos(timeout);
1.411 + final ReentrantLock lock = this.lock;
1.412 + lock.lockInterruptibly();
1.413 + try {
1.414 + while (!linkFirst(node)) {
1.415 + if (nanos <= 0)
1.416 + return false;
1.417 + nanos = notFull.awaitNanos(nanos);
1.418 + }
1.419 + return true;
1.420 + } finally {
1.421 + lock.unlock();
1.422 + }
1.423 + }
1.424 +
1.425 + /**
1.426 + * @throws NullPointerException {@inheritDoc}
1.427 + * @throws InterruptedException {@inheritDoc}
1.428 + */
1.429 + public boolean offerLast(E e, long timeout, TimeUnit unit)
1.430 + throws InterruptedException {
1.431 + if (e == null) throw new NullPointerException();
1.432 + Node<E> node = new Node<E>(e);
1.433 + long nanos = unit.toNanos(timeout);
1.434 + final ReentrantLock lock = this.lock;
1.435 + lock.lockInterruptibly();
1.436 + try {
1.437 + while (!linkLast(node)) {
1.438 + if (nanos <= 0)
1.439 + return false;
1.440 + nanos = notFull.awaitNanos(nanos);
1.441 + }
1.442 + return true;
1.443 + } finally {
1.444 + lock.unlock();
1.445 + }
1.446 + }
1.447 +
1.448 + /**
1.449 + * @throws NoSuchElementException {@inheritDoc}
1.450 + */
1.451 + public E removeFirst() {
1.452 + E x = pollFirst();
1.453 + if (x == null) throw new NoSuchElementException();
1.454 + return x;
1.455 + }
1.456 +
1.457 + /**
1.458 + * @throws NoSuchElementException {@inheritDoc}
1.459 + */
1.460 + public E removeLast() {
1.461 + E x = pollLast();
1.462 + if (x == null) throw new NoSuchElementException();
1.463 + return x;
1.464 + }
1.465 +
1.466 + public E pollFirst() {
1.467 + final ReentrantLock lock = this.lock;
1.468 + lock.lock();
1.469 + try {
1.470 + return unlinkFirst();
1.471 + } finally {
1.472 + lock.unlock();
1.473 + }
1.474 + }
1.475 +
1.476 + public E pollLast() {
1.477 + final ReentrantLock lock = this.lock;
1.478 + lock.lock();
1.479 + try {
1.480 + return unlinkLast();
1.481 + } finally {
1.482 + lock.unlock();
1.483 + }
1.484 + }
1.485 +
1.486 + public E takeFirst() throws InterruptedException {
1.487 + final ReentrantLock lock = this.lock;
1.488 + lock.lock();
1.489 + try {
1.490 + E x;
1.491 + while ( (x = unlinkFirst()) == null)
1.492 + notEmpty.await();
1.493 + return x;
1.494 + } finally {
1.495 + lock.unlock();
1.496 + }
1.497 + }
1.498 +
1.499 + public E takeLast() throws InterruptedException {
1.500 + final ReentrantLock lock = this.lock;
1.501 + lock.lock();
1.502 + try {
1.503 + E x;
1.504 + while ( (x = unlinkLast()) == null)
1.505 + notEmpty.await();
1.506 + return x;
1.507 + } finally {
1.508 + lock.unlock();
1.509 + }
1.510 + }
1.511 +
1.512 + public E pollFirst(long timeout, TimeUnit unit)
1.513 + throws InterruptedException {
1.514 + long nanos = unit.toNanos(timeout);
1.515 + final ReentrantLock lock = this.lock;
1.516 + lock.lockInterruptibly();
1.517 + try {
1.518 + E x;
1.519 + while ( (x = unlinkFirst()) == null) {
1.520 + if (nanos <= 0)
1.521 + return null;
1.522 + nanos = notEmpty.awaitNanos(nanos);
1.523 + }
1.524 + return x;
1.525 + } finally {
1.526 + lock.unlock();
1.527 + }
1.528 + }
1.529 +
1.530 + public E pollLast(long timeout, TimeUnit unit)
1.531 + throws InterruptedException {
1.532 + long nanos = unit.toNanos(timeout);
1.533 + final ReentrantLock lock = this.lock;
1.534 + lock.lockInterruptibly();
1.535 + try {
1.536 + E x;
1.537 + while ( (x = unlinkLast()) == null) {
1.538 + if (nanos <= 0)
1.539 + return null;
1.540 + nanos = notEmpty.awaitNanos(nanos);
1.541 + }
1.542 + return x;
1.543 + } finally {
1.544 + lock.unlock();
1.545 + }
1.546 + }
1.547 +
1.548 + /**
1.549 + * @throws NoSuchElementException {@inheritDoc}
1.550 + */
1.551 + public E getFirst() {
1.552 + E x = peekFirst();
1.553 + if (x == null) throw new NoSuchElementException();
1.554 + return x;
1.555 + }
1.556 +
1.557 + /**
1.558 + * @throws NoSuchElementException {@inheritDoc}
1.559 + */
1.560 + public E getLast() {
1.561 + E x = peekLast();
1.562 + if (x == null) throw new NoSuchElementException();
1.563 + return x;
1.564 + }
1.565 +
1.566 + public E peekFirst() {
1.567 + final ReentrantLock lock = this.lock;
1.568 + lock.lock();
1.569 + try {
1.570 + return (first == null) ? null : first.item;
1.571 + } finally {
1.572 + lock.unlock();
1.573 + }
1.574 + }
1.575 +
1.576 + public E peekLast() {
1.577 + final ReentrantLock lock = this.lock;
1.578 + lock.lock();
1.579 + try {
1.580 + return (last == null) ? null : last.item;
1.581 + } finally {
1.582 + lock.unlock();
1.583 + }
1.584 + }
1.585 +
1.586 + public boolean removeFirstOccurrence(Object o) {
1.587 + if (o == null) return false;
1.588 + final ReentrantLock lock = this.lock;
1.589 + lock.lock();
1.590 + try {
1.591 + for (Node<E> p = first; p != null; p = p.next) {
1.592 + if (o.equals(p.item)) {
1.593 + unlink(p);
1.594 + return true;
1.595 + }
1.596 + }
1.597 + return false;
1.598 + } finally {
1.599 + lock.unlock();
1.600 + }
1.601 + }
1.602 +
1.603 + public boolean removeLastOccurrence(Object o) {
1.604 + if (o == null) return false;
1.605 + final ReentrantLock lock = this.lock;
1.606 + lock.lock();
1.607 + try {
1.608 + for (Node<E> p = last; p != null; p = p.prev) {
1.609 + if (o.equals(p.item)) {
1.610 + unlink(p);
1.611 + return true;
1.612 + }
1.613 + }
1.614 + return false;
1.615 + } finally {
1.616 + lock.unlock();
1.617 + }
1.618 + }
1.619 +
1.620 + // BlockingQueue methods
1.621 +
1.622 + /**
1.623 + * Inserts the specified element at the end of this deque unless it would
1.624 + * violate capacity restrictions. When using a capacity-restricted deque,
1.625 + * it is generally preferable to use method {@link #offer(Object) offer}.
1.626 + *
1.627 + * <p>This method is equivalent to {@link #addLast}.
1.628 + *
1.629 + * @throws IllegalStateException if the element cannot be added at this
1.630 + * time due to capacity restrictions
1.631 + * @throws NullPointerException if the specified element is null
1.632 + */
1.633 + public boolean add(E e) {
1.634 + addLast(e);
1.635 + return true;
1.636 + }
1.637 +
1.638 + /**
1.639 + * @throws NullPointerException if the specified element is null
1.640 + */
1.641 + public boolean offer(E e) {
1.642 + return offerLast(e);
1.643 + }
1.644 +
1.645 + /**
1.646 + * @throws NullPointerException {@inheritDoc}
1.647 + * @throws InterruptedException {@inheritDoc}
1.648 + */
1.649 + public void put(E e) throws InterruptedException {
1.650 + putLast(e);
1.651 + }
1.652 +
1.653 + /**
1.654 + * @throws NullPointerException {@inheritDoc}
1.655 + * @throws InterruptedException {@inheritDoc}
1.656 + */
1.657 + public boolean offer(E e, long timeout, TimeUnit unit)
1.658 + throws InterruptedException {
1.659 + return offerLast(e, timeout, unit);
1.660 + }
1.661 +
1.662 + /**
1.663 + * Retrieves and removes the head of the queue represented by this deque.
1.664 + * This method differs from {@link #poll poll} only in that it throws an
1.665 + * exception if this deque is empty.
1.666 + *
1.667 + * <p>This method is equivalent to {@link #removeFirst() removeFirst}.
1.668 + *
1.669 + * @return the head of the queue represented by this deque
1.670 + * @throws NoSuchElementException if this deque is empty
1.671 + */
1.672 + public E remove() {
1.673 + return removeFirst();
1.674 + }
1.675 +
1.676 + public E poll() {
1.677 + return pollFirst();
1.678 + }
1.679 +
1.680 + public E take() throws InterruptedException {
1.681 + return takeFirst();
1.682 + }
1.683 +
1.684 + public E poll(long timeout, TimeUnit unit) throws InterruptedException {
1.685 + return pollFirst(timeout, unit);
1.686 + }
1.687 +
1.688 + /**
1.689 + * Retrieves, but does not remove, the head of the queue represented by
1.690 + * this deque. This method differs from {@link #peek peek} only in that
1.691 + * it throws an exception if this deque is empty.
1.692 + *
1.693 + * <p>This method is equivalent to {@link #getFirst() getFirst}.
1.694 + *
1.695 + * @return the head of the queue represented by this deque
1.696 + * @throws NoSuchElementException if this deque is empty
1.697 + */
1.698 + public E element() {
1.699 + return getFirst();
1.700 + }
1.701 +
1.702 + public E peek() {
1.703 + return peekFirst();
1.704 + }
1.705 +
1.706 + /**
1.707 + * Returns the number of additional elements that this deque can ideally
1.708 + * (in the absence of memory or resource constraints) accept without
1.709 + * blocking. This is always equal to the initial capacity of this deque
1.710 + * less the current {@code size} of this deque.
1.711 + *
1.712 + * <p>Note that you <em>cannot</em> always tell if an attempt to insert
1.713 + * an element will succeed by inspecting {@code remainingCapacity}
1.714 + * because it may be the case that another thread is about to
1.715 + * insert or remove an element.
1.716 + */
1.717 + public int remainingCapacity() {
1.718 + final ReentrantLock lock = this.lock;
1.719 + lock.lock();
1.720 + try {
1.721 + return capacity - count;
1.722 + } finally {
1.723 + lock.unlock();
1.724 + }
1.725 + }
1.726 +
1.727 + /**
1.728 + * @throws UnsupportedOperationException {@inheritDoc}
1.729 + * @throws ClassCastException {@inheritDoc}
1.730 + * @throws NullPointerException {@inheritDoc}
1.731 + * @throws IllegalArgumentException {@inheritDoc}
1.732 + */
1.733 + public int drainTo(Collection<? super E> c) {
1.734 + return drainTo(c, Integer.MAX_VALUE);
1.735 + }
1.736 +
1.737 + /**
1.738 + * @throws UnsupportedOperationException {@inheritDoc}
1.739 + * @throws ClassCastException {@inheritDoc}
1.740 + * @throws NullPointerException {@inheritDoc}
1.741 + * @throws IllegalArgumentException {@inheritDoc}
1.742 + */
1.743 + public int drainTo(Collection<? super E> c, int maxElements) {
1.744 + if (c == null)
1.745 + throw new NullPointerException();
1.746 + if (c == this)
1.747 + throw new IllegalArgumentException();
1.748 + final ReentrantLock lock = this.lock;
1.749 + lock.lock();
1.750 + try {
1.751 + int n = Math.min(maxElements, count);
1.752 + for (int i = 0; i < n; i++) {
1.753 + c.add(first.item); // In this order, in case add() throws.
1.754 + unlinkFirst();
1.755 + }
1.756 + return n;
1.757 + } finally {
1.758 + lock.unlock();
1.759 + }
1.760 + }
1.761 +
1.762 + // Stack methods
1.763 +
1.764 + /**
1.765 + * @throws IllegalStateException {@inheritDoc}
1.766 + * @throws NullPointerException {@inheritDoc}
1.767 + */
1.768 + public void push(E e) {
1.769 + addFirst(e);
1.770 + }
1.771 +
1.772 + /**
1.773 + * @throws NoSuchElementException {@inheritDoc}
1.774 + */
1.775 + public E pop() {
1.776 + return removeFirst();
1.777 + }
1.778 +
1.779 + // Collection methods
1.780 +
1.781 + /**
1.782 + * Removes the first occurrence of the specified element from this deque.
1.783 + * If the deque does not contain the element, it is unchanged.
1.784 + * More formally, removes the first element {@code e} such that
1.785 + * {@code o.equals(e)} (if such an element exists).
1.786 + * Returns {@code true} if this deque contained the specified element
1.787 + * (or equivalently, if this deque changed as a result of the call).
1.788 + *
1.789 + * <p>This method is equivalent to
1.790 + * {@link #removeFirstOccurrence(Object) removeFirstOccurrence}.
1.791 + *
1.792 + * @param o element to be removed from this deque, if present
1.793 + * @return {@code true} if this deque changed as a result of the call
1.794 + */
1.795 + public boolean remove(Object o) {
1.796 + return removeFirstOccurrence(o);
1.797 + }
1.798 +
1.799 + /**
1.800 + * Returns the number of elements in this deque.
1.801 + *
1.802 + * @return the number of elements in this deque
1.803 + */
1.804 + public int size() {
1.805 + final ReentrantLock lock = this.lock;
1.806 + lock.lock();
1.807 + try {
1.808 + return count;
1.809 + } finally {
1.810 + lock.unlock();
1.811 + }
1.812 + }
1.813 +
1.814 + /**
1.815 + * Returns {@code true} if this deque contains the specified element.
1.816 + * More formally, returns {@code true} if and only if this deque contains
1.817 + * at least one element {@code e} such that {@code o.equals(e)}.
1.818 + *
1.819 + * @param o object to be checked for containment in this deque
1.820 + * @return {@code true} if this deque contains the specified element
1.821 + */
1.822 + public boolean contains(Object o) {
1.823 + if (o == null) return false;
1.824 + final ReentrantLock lock = this.lock;
1.825 + lock.lock();
1.826 + try {
1.827 + for (Node<E> p = first; p != null; p = p.next)
1.828 + if (o.equals(p.item))
1.829 + return true;
1.830 + return false;
1.831 + } finally {
1.832 + lock.unlock();
1.833 + }
1.834 + }
1.835 +
1.836 + /*
1.837 + * TODO: Add support for more efficient bulk operations.
1.838 + *
1.839 + * We don't want to acquire the lock for every iteration, but we
1.840 + * also want other threads a chance to interact with the
1.841 + * collection, especially when count is close to capacity.
1.842 + */
1.843 +
1.844 +// /**
1.845 +// * Adds all of the elements in the specified collection to this
1.846 +// * queue. Attempts to addAll of a queue to itself result in
1.847 +// * {@code IllegalArgumentException}. Further, the behavior of
1.848 +// * this operation is undefined if the specified collection is
1.849 +// * modified while the operation is in progress.
1.850 +// *
1.851 +// * @param c collection containing elements to be added to this queue
1.852 +// * @return {@code true} if this queue changed as a result of the call
1.853 +// * @throws ClassCastException {@inheritDoc}
1.854 +// * @throws NullPointerException {@inheritDoc}
1.855 +// * @throws IllegalArgumentException {@inheritDoc}
1.856 +// * @throws IllegalStateException {@inheritDoc}
1.857 +// * @see #add(Object)
1.858 +// */
1.859 +// public boolean addAll(Collection<? extends E> c) {
1.860 +// if (c == null)
1.861 +// throw new NullPointerException();
1.862 +// if (c == this)
1.863 +// throw new IllegalArgumentException();
1.864 +// final ReentrantLock lock = this.lock;
1.865 +// lock.lock();
1.866 +// try {
1.867 +// boolean modified = false;
1.868 +// for (E e : c)
1.869 +// if (linkLast(e))
1.870 +// modified = true;
1.871 +// return modified;
1.872 +// } finally {
1.873 +// lock.unlock();
1.874 +// }
1.875 +// }
1.876 +
1.877 + /**
1.878 + * Returns an array containing all of the elements in this deque, in
1.879 + * proper sequence (from first to last element).
1.880 + *
1.881 + * <p>The returned array will be "safe" in that no references to it are
1.882 + * maintained by this deque. (In other words, this method must allocate
1.883 + * a new array). The caller is thus free to modify the returned array.
1.884 + *
1.885 + * <p>This method acts as bridge between array-based and collection-based
1.886 + * APIs.
1.887 + *
1.888 + * @return an array containing all of the elements in this deque
1.889 + */
1.890 + @SuppressWarnings("unchecked")
1.891 + public Object[] toArray() {
1.892 + final ReentrantLock lock = this.lock;
1.893 + lock.lock();
1.894 + try {
1.895 + Object[] a = new Object[count];
1.896 + int k = 0;
1.897 + for (Node<E> p = first; p != null; p = p.next)
1.898 + a[k++] = p.item;
1.899 + return a;
1.900 + } finally {
1.901 + lock.unlock();
1.902 + }
1.903 + }
1.904 +
1.905 + /**
1.906 + * Returns an array containing all of the elements in this deque, in
1.907 + * proper sequence; the runtime type of the returned array is that of
1.908 + * the specified array. If the deque fits in the specified array, it
1.909 + * is returned therein. Otherwise, a new array is allocated with the
1.910 + * runtime type of the specified array and the size of this deque.
1.911 + *
1.912 + * <p>If this deque fits in the specified array with room to spare
1.913 + * (i.e., the array has more elements than this deque), the element in
1.914 + * the array immediately following the end of the deque is set to
1.915 + * {@code null}.
1.916 + *
1.917 + * <p>Like the {@link #toArray()} method, this method acts as bridge between
1.918 + * array-based and collection-based APIs. Further, this method allows
1.919 + * precise control over the runtime type of the output array, and may,
1.920 + * under certain circumstances, be used to save allocation costs.
1.921 + *
1.922 + * <p>Suppose {@code x} is a deque known to contain only strings.
1.923 + * The following code can be used to dump the deque into a newly
1.924 + * allocated array of {@code String}:
1.925 + *
1.926 + * <pre>
1.927 + * String[] y = x.toArray(new String[0]);</pre>
1.928 + *
1.929 + * Note that {@code toArray(new Object[0])} is identical in function to
1.930 + * {@code toArray()}.
1.931 + *
1.932 + * @param a the array into which the elements of the deque are to
1.933 + * be stored, if it is big enough; otherwise, a new array of the
1.934 + * same runtime type is allocated for this purpose
1.935 + * @return an array containing all of the elements in this deque
1.936 + * @throws ArrayStoreException if the runtime type of the specified array
1.937 + * is not a supertype of the runtime type of every element in
1.938 + * this deque
1.939 + * @throws NullPointerException if the specified array is null
1.940 + */
1.941 + @SuppressWarnings("unchecked")
1.942 + public <T> T[] toArray(T[] a) {
1.943 + final ReentrantLock lock = this.lock;
1.944 + lock.lock();
1.945 + try {
1.946 + if (a.length < count)
1.947 + a = (T[])java.lang.reflect.Array.newInstance
1.948 + (a.getClass().getComponentType(), count);
1.949 +
1.950 + int k = 0;
1.951 + for (Node<E> p = first; p != null; p = p.next)
1.952 + a[k++] = (T)p.item;
1.953 + if (a.length > k)
1.954 + a[k] = null;
1.955 + return a;
1.956 + } finally {
1.957 + lock.unlock();
1.958 + }
1.959 + }
1.960 +
1.961 + public String toString() {
1.962 + final ReentrantLock lock = this.lock;
1.963 + lock.lock();
1.964 + try {
1.965 + Node<E> p = first;
1.966 + if (p == null)
1.967 + return "[]";
1.968 +
1.969 + StringBuilder sb = new StringBuilder();
1.970 + sb.append('[');
1.971 + for (;;) {
1.972 + E e = p.item;
1.973 + sb.append(e == this ? "(this Collection)" : e);
1.974 + p = p.next;
1.975 + if (p == null)
1.976 + return sb.append(']').toString();
1.977 + sb.append(',').append(' ');
1.978 + }
1.979 + } finally {
1.980 + lock.unlock();
1.981 + }
1.982 + }
1.983 +
1.984 + /**
1.985 + * Atomically removes all of the elements from this deque.
1.986 + * The deque will be empty after this call returns.
1.987 + */
1.988 + public void clear() {
1.989 + final ReentrantLock lock = this.lock;
1.990 + lock.lock();
1.991 + try {
1.992 + for (Node<E> f = first; f != null; ) {
1.993 + f.item = null;
1.994 + Node<E> n = f.next;
1.995 + f.prev = null;
1.996 + f.next = null;
1.997 + f = n;
1.998 + }
1.999 + first = last = null;
1.1000 + count = 0;
1.1001 + notFull.signalAll();
1.1002 + } finally {
1.1003 + lock.unlock();
1.1004 + }
1.1005 + }
1.1006 +
1.1007 + /**
1.1008 + * Returns an iterator over the elements in this deque in proper sequence.
1.1009 + * The elements will be returned in order from first (head) to last (tail).
1.1010 + *
1.1011 + * <p>The returned iterator is a "weakly consistent" iterator that
1.1012 + * will never throw {@link java.util.ConcurrentModificationException
1.1013 + * ConcurrentModificationException}, and guarantees to traverse
1.1014 + * elements as they existed upon construction of the iterator, and
1.1015 + * may (but is not guaranteed to) reflect any modifications
1.1016 + * subsequent to construction.
1.1017 + *
1.1018 + * @return an iterator over the elements in this deque in proper sequence
1.1019 + */
1.1020 + public Iterator<E> iterator() {
1.1021 + return new Itr();
1.1022 + }
1.1023 +
1.1024 + /**
1.1025 + * Returns an iterator over the elements in this deque in reverse
1.1026 + * sequential order. The elements will be returned in order from
1.1027 + * last (tail) to first (head).
1.1028 + *
1.1029 + * <p>The returned iterator is a "weakly consistent" iterator that
1.1030 + * will never throw {@link java.util.ConcurrentModificationException
1.1031 + * ConcurrentModificationException}, and guarantees to traverse
1.1032 + * elements as they existed upon construction of the iterator, and
1.1033 + * may (but is not guaranteed to) reflect any modifications
1.1034 + * subsequent to construction.
1.1035 + *
1.1036 + * @return an iterator over the elements in this deque in reverse order
1.1037 + */
1.1038 + public Iterator<E> descendingIterator() {
1.1039 + return new DescendingItr();
1.1040 + }
1.1041 +
1.1042 + /**
1.1043 + * Base class for Iterators for LinkedBlockingDeque
1.1044 + */
1.1045 + private abstract class AbstractItr implements Iterator<E> {
1.1046 + /**
1.1047 + * The next node to return in next()
1.1048 + */
1.1049 + Node<E> next;
1.1050 +
1.1051 + /**
1.1052 + * nextItem holds on to item fields because once we claim that
1.1053 + * an element exists in hasNext(), we must return item read
1.1054 + * under lock (in advance()) even if it was in the process of
1.1055 + * being removed when hasNext() was called.
1.1056 + */
1.1057 + E nextItem;
1.1058 +
1.1059 + /**
1.1060 + * Node returned by most recent call to next. Needed by remove.
1.1061 + * Reset to null if this element is deleted by a call to remove.
1.1062 + */
1.1063 + private Node<E> lastRet;
1.1064 +
1.1065 + abstract Node<E> firstNode();
1.1066 + abstract Node<E> nextNode(Node<E> n);
1.1067 +
1.1068 + AbstractItr() {
1.1069 + // set to initial position
1.1070 + final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1.1071 + lock.lock();
1.1072 + try {
1.1073 + next = firstNode();
1.1074 + nextItem = (next == null) ? null : next.item;
1.1075 + } finally {
1.1076 + lock.unlock();
1.1077 + }
1.1078 + }
1.1079 +
1.1080 + /**
1.1081 + * Returns the successor node of the given non-null, but
1.1082 + * possibly previously deleted, node.
1.1083 + */
1.1084 + private Node<E> succ(Node<E> n) {
1.1085 + // Chains of deleted nodes ending in null or self-links
1.1086 + // are possible if multiple interior nodes are removed.
1.1087 + for (;;) {
1.1088 + Node<E> s = nextNode(n);
1.1089 + if (s == null)
1.1090 + return null;
1.1091 + else if (s.item != null)
1.1092 + return s;
1.1093 + else if (s == n)
1.1094 + return firstNode();
1.1095 + else
1.1096 + n = s;
1.1097 + }
1.1098 + }
1.1099 +
1.1100 + /**
1.1101 + * Advances next.
1.1102 + */
1.1103 + void advance() {
1.1104 + final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1.1105 + lock.lock();
1.1106 + try {
1.1107 + // assert next != null;
1.1108 + next = succ(next);
1.1109 + nextItem = (next == null) ? null : next.item;
1.1110 + } finally {
1.1111 + lock.unlock();
1.1112 + }
1.1113 + }
1.1114 +
1.1115 + public boolean hasNext() {
1.1116 + return next != null;
1.1117 + }
1.1118 +
1.1119 + public E next() {
1.1120 + if (next == null)
1.1121 + throw new NoSuchElementException();
1.1122 + lastRet = next;
1.1123 + E x = nextItem;
1.1124 + advance();
1.1125 + return x;
1.1126 + }
1.1127 +
1.1128 + public void remove() {
1.1129 + Node<E> n = lastRet;
1.1130 + if (n == null)
1.1131 + throw new IllegalStateException();
1.1132 + lastRet = null;
1.1133 + final ReentrantLock lock = LinkedBlockingDeque.this.lock;
1.1134 + lock.lock();
1.1135 + try {
1.1136 + if (n.item != null)
1.1137 + unlink(n);
1.1138 + } finally {
1.1139 + lock.unlock();
1.1140 + }
1.1141 + }
1.1142 + }
1.1143 +
1.1144 + /** Forward iterator */
1.1145 + private class Itr extends AbstractItr {
1.1146 + Node<E> firstNode() { return first; }
1.1147 + Node<E> nextNode(Node<E> n) { return n.next; }
1.1148 + }
1.1149 +
1.1150 + /** Descending iterator */
1.1151 + private class DescendingItr extends AbstractItr {
1.1152 + Node<E> firstNode() { return last; }
1.1153 + Node<E> nextNode(Node<E> n) { return n.prev; }
1.1154 + }
1.1155 +
1.1156 + /**
1.1157 + * Save the state of this deque to a stream (that is, serialize it).
1.1158 + *
1.1159 + * @serialData The capacity (int), followed by elements (each an
1.1160 + * {@code Object}) in the proper order, followed by a null
1.1161 + * @param s the stream
1.1162 + */
1.1163 + private void writeObject(java.io.ObjectOutputStream s)
1.1164 + throws java.io.IOException {
1.1165 + final ReentrantLock lock = this.lock;
1.1166 + lock.lock();
1.1167 + try {
1.1168 + // Write out capacity and any hidden stuff
1.1169 + s.defaultWriteObject();
1.1170 + // Write out all elements in the proper order.
1.1171 + for (Node<E> p = first; p != null; p = p.next)
1.1172 + s.writeObject(p.item);
1.1173 + // Use trailing null as sentinel
1.1174 + s.writeObject(null);
1.1175 + } finally {
1.1176 + lock.unlock();
1.1177 + }
1.1178 + }
1.1179 +
1.1180 + /**
1.1181 + * Reconstitute this deque from a stream (that is,
1.1182 + * deserialize it).
1.1183 + * @param s the stream
1.1184 + */
1.1185 + private void readObject(java.io.ObjectInputStream s)
1.1186 + throws java.io.IOException, ClassNotFoundException {
1.1187 + s.defaultReadObject();
1.1188 + count = 0;
1.1189 + first = null;
1.1190 + last = null;
1.1191 + // Read in all elements and place in queue
1.1192 + for (;;) {
1.1193 + @SuppressWarnings("unchecked")
1.1194 + E item = (E)s.readObject();
1.1195 + if (item == null)
1.1196 + break;
1.1197 + add(item);
1.1198 + }
1.1199 + }
1.1200 +
1.1201 +}