/* * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation.  Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ /* * This file is available under and governed by the GNU General Public * License version 2 only, as published by the Free Software Foundation. * However, the following notice accompanied the original version of this * file: * * Written by Doug Lea with assistance from members of JCP JSR-166 * Expert Group and released to the public domain, as explained at * http://creativecommons.org/publicdomain/zero/1.0/ */ package java.util.concurrent; import java.util.AbstractQueue;import java.util.Collection;import java.util.Iterator;import java.util.NoSuchElementException;import java.util.concurrent.locks.Condition;import java.util.concurrent.locks.ReentrantLock; /** * An optionally-bounded {@linkplain BlockingDeque blocking deque} based on * linked nodes. * * <p> The optional capacity bound constructor argument serves as a * way to prevent excessive expansion. The capacity, if unspecified, * is equal to {@link Integer#MAX_VALUE}.  Linked nodes are * dynamically created upon each insertion unless this would bring the * deque above capacity. * * <p>Most operations run in constant time (ignoring time spent * blocking).  Exceptions include {@link #remove(Object) remove}, * {@link #removeFirstOccurrence removeFirstOccurrence}, {@link * #removeLastOccurrence removeLastOccurrence}, {@link #contains * contains}, {@link #iterator iterator.remove()}, and the bulk * operations, all of which run in linear time. * * <p>This class and its iterator implement all of the * <em>optional</em> methods of the {@link Collection} and {@link * Iterator} interfaces. * * <p>This class is a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @since 1.6 * @author  Doug Lea * @param <E> the type of elements held in this collection */public class LinkedBlockingDeque<E>    extends AbstractQueue<E>    implements BlockingDeque<E>,  java.io.Serializable {     /*     * Implemented as a simple doubly-linked list protected by a     * single lock and using conditions to manage blocking.     *     * To implement weakly consistent iterators, it appears we need to     * keep all Nodes GC-reachable from a predecessor dequeued Node.     * That would cause two problems:     * - allow a rogue Iterator to cause unbounded memory retention     * - cause cross-generational linking of old Nodes to new Nodes if     *   a Node was tenured while live, which generational GCs have a     *   hard time dealing with, causing repeated major collections.     * However, only non-deleted Nodes need to be reachable from     * dequeued Nodes, and reachability does not necessarily have to     * be of the kind understood by the GC.  We use the trick of     * linking a Node that has just been dequeued to itself.  Such a     * self-link implicitly means to jump to "first" (for next links)     * or "last" (for prev links).     */     /*     * We have "diamond" multiple interface/abstract class inheritance     * here, and that introduces ambiguities. Often we want the     * BlockingDeque javadoc combined with the AbstractQueue     * implementation, so a lot of method specs are duplicated here.     */     private static final long serialVersionUID = -387911632671998426L;     /** Doubly-linked list node class */    static final class Node<E> {        /**         * The item, or null if this node has been removed.         */        E item;         /**         * One of:         * - the real predecessor Node         * - this Node, meaning the predecessor is tail         * - null, meaning there is no predecessor         */        Node<E> prev;         /**         * One of:         * - the real successor Node         * - this Node, meaning the successor is head         * - null, meaning there is no successor         */        Node<E> next;         Node(E x) {            item = x;        }    }     /**     * Pointer to first node.     * Invariant: (first == null && last == null) ||     *            (first.prev == null && first.item != null)     */    transient Node<E> first;     /**     * Pointer to last node.     * Invariant: (first == null && last == null) ||     *            (last.next == null && last.item != null)     */    transient Node<E> last;     /** Number of items in the deque */    private transient int count;     /** Maximum number of items in the deque */    private final int capacity;     /** Main lock guarding all access */    final ReentrantLock lock = new ReentrantLock();     /** Condition for waiting takes */    private final Condition notEmpty = lock.newCondition();     /** Condition for waiting puts */    private final Condition notFull = lock.newCondition();     /**     * Creates a {@code LinkedBlockingDeque} with a capacity of     * {@link Integer#MAX_VALUE}.     */    public LinkedBlockingDeque() {        this(Integer.MAX_VALUE);    }     /**     * Creates a {@code LinkedBlockingDeque} with the given (fixed) capacity.     *     * @param capacity the capacity of this deque     * @throws IllegalArgumentException if {@code capacity} is less than 1     */    public LinkedBlockingDeque(int capacity) {        if (capacity <= 0) throw new IllegalArgumentException();        this.capacity = capacity;    }     /**     * Creates a {@code LinkedBlockingDeque} with a capacity of     * {@link Integer#MAX_VALUE}, initially containing the elements of     * the given collection, added in traversal order of the     * collection's iterator.     *     * @param c the collection of elements to initially contain     * @throws NullPointerException if the specified collection or any     *         of its elements are null     */    public LinkedBlockingDeque(Collection<? extends E> c) {        this(Integer.MAX_VALUE);        final ReentrantLock lock = this.lock;        lock.lock(); // Never contended, but necessary for visibility        try {            for (E e : c) {                if (e == null)                    throw new NullPointerException();                if (!linkLast(new Node<E>(e)))                    throw new IllegalStateException("Deque full");            }        } finally {            lock.unlock();        }    }      // Basic linking and unlinking operations, called only while holding lock     /**     * Links node as first element, or returns false if full.     */    private boolean linkFirst(Node<E> node) {        // assert lock.isHeldByCurrentThread();        if (count >= capacity)            return false;        Node<E> f = first;        node.next = f;        first = node;        if (last == null)            last = node;        else            f.prev = node;        ++count;        notEmpty.signal();        return true;    }     /**     * Links node as last element, or returns false if full.     */    private boolean linkLast(Node<E> node) {        // assert lock.isHeldByCurrentThread();        if (count >= capacity)            return false;        Node<E> l = last;        node.prev = l;        last = node;        if (first == null)            first = node;        else            l.next = node;        ++count;        notEmpty.signal();        return true;    }     /**     * Removes and returns first element, or null if empty.     */    private E unlinkFirst() {        // assert lock.isHeldByCurrentThread();        Node<E> f = first;        if (f == null)            return null;        Node<E> n = f.next;        E item = f.item;        f.item = null;        f.next = f; // help GC        first = n;        if (n == null)            last = null;        else            n.prev = null;        --count;        notFull.signal();        return item;    }     /**     * Removes and returns last element, or null if empty.     */    private E unlinkLast() {        // assert lock.isHeldByCurrentThread();        Node<E> l = last;        if (l == null)            return null;        Node<E> p = l.prev;        E item = l.item;        l.item = null;        l.prev = l; // help GC        last = p;        if (p == null)            first = null;        else            p.next = null;        --count;        notFull.signal();        return item;    }     /**     * Unlinks x.     */    void unlink(Node<E> x) {        // assert lock.isHeldByCurrentThread();        Node<E> p = x.prev;        Node<E> n = x.next;        if (p == null) {            unlinkFirst();        } else if (n == null) {            unlinkLast();        } else {            p.next = n;            n.prev = p;            x.item = null;            // Don't mess with x's links.  They may still be in use by            // an iterator.            --count;            notFull.signal();        }    }     // BlockingDeque methods     /**     * @throws IllegalStateException {@inheritDoc}     * @throws NullPointerException  {@inheritDoc}     */    public void addFirst(E e) {        if (!offerFirst(e))            throw new IllegalStateException("Deque full");    }     /**     * @throws IllegalStateException {@inheritDoc}     * @throws NullPointerException  {@inheritDoc}     */    public void addLast(E e) {        if (!offerLast(e))            throw new IllegalStateException("Deque full");    }     /**     * @throws NullPointerException {@inheritDoc}     */    public boolean offerFirst(E e) {        if (e == null) throw new NullPointerException();        Node<E> node = new Node<E>(e);        final ReentrantLock lock = this.lock;        lock.lock();        try {            return linkFirst(node);        } finally {            lock.unlock();        }    }     /**     * @throws NullPointerException {@inheritDoc}     */    public boolean offerLast(E e) {        if (e == null) throw new NullPointerException();        Node<E> node = new Node<E>(e);        final ReentrantLock lock = this.lock;        lock.lock();        try {            return linkLast(node);        } finally {            lock.unlock();        }    }     /**     * @throws NullPointerException {@inheritDoc}     * @throws InterruptedException {@inheritDoc}     */    public void putFirst(E e) throws InterruptedException {        if (e == null) throw new NullPointerException();        Node<E> node = new Node<E>(e);        final ReentrantLock lock = this.lock;        lock.lock();        try {            while (!linkFirst(node))                notFull.await();        } finally {            lock.unlock();        }    }     /**     * @throws NullPointerException {@inheritDoc}     * @throws InterruptedException {@inheritDoc}     */    public void putLast(E e) throws InterruptedException {        if (e == null) throw new NullPointerException();        Node<E> node = new Node<E>(e);        final ReentrantLock lock = this.lock;        lock.lock();        try {            while (!linkLast(node))                notFull.await();        } finally {            lock.unlock();        }    }     /**     * @throws NullPointerException {@inheritDoc}     * @throws InterruptedException {@inheritDoc}     */    public boolean offerFirst(E e, long timeout, TimeUnit unit)        throws InterruptedException {        if (e == null) throw new NullPointerException();        Node<E> node = new Node<E>(e);        long nanos = unit.toNanos(timeout);        final ReentrantLock lock = this.lock;        lock.lockInterruptibly();        try {            while (!linkFirst(node)) {                if (nanos <= 0)                    return false;                nanos = notFull.awaitNanos(nanos);            }            return true;        } finally {            lock.unlock();        }    }     /**     * @throws NullPointerException {@inheritDoc}     * @throws InterruptedException {@inheritDoc}     */    public boolean offerLast(E e, long timeout, TimeUnit unit)        throws InterruptedException {        if (e == null) throw new NullPointerException();        Node<E> node = new Node<E>(e);        long nanos = unit.toNanos(timeout);        final ReentrantLock lock = this.lock;        lock.lockInterruptibly();        try {            while (!linkLast(node)) {                if (nanos <= 0)                    return false;                nanos = notFull.awaitNanos(nanos);            }            return true;        } finally {            lock.unlock();        }    }     /**     * @throws NoSuchElementException {@inheritDoc}     */    public E removeFirst() {        E x = pollFirst();        if (x == null) throw new NoSuchElementException();        return x;    }     /**     * @throws NoSuchElementException {@inheritDoc}     */    public E removeLast() {        E x = pollLast();        if (x == null) throw new NoSuchElementException();        return x;    }     public E pollFirst() {        final ReentrantLock lock = this.lock;        lock.lock();        try {            return unlinkFirst();        } finally {            lock.unlock();        }    }     public E pollLast() {        final ReentrantLock lock = this.lock;        lock.lock();        try {            return unlinkLast();        } finally {            lock.unlock();        }    }     public E takeFirst() throws InterruptedException {        final ReentrantLock lock = this.lock;        lock.lock();        try {            E x;            while ( (x = unlinkFirst()) == null)                notEmpty.await();            return x;        } finally {            lock.unlock();        }    }     public E takeLast() throws InterruptedException {        final ReentrantLock lock = this.lock;        lock.lock();        try {            E x;

Lines 1–500 of 1198. Load more