/* * 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 and Martin Buchholz 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.AbstractCollection;import java.util.ArrayList;import java.util.Collection;import java.util.Deque;import java.util.Iterator;import java.util.NoSuchElementException;import java.util.Queue; /** * An unbounded concurrent {@linkplain Deque deque} based on linked nodes. * Concurrent insertion, removal, and access operations execute safely * across multiple threads. * A {@code ConcurrentLinkedDeque} is an appropriate choice when * many threads will share access to a common collection. * Like most other concurrent collection implementations, this class * does not permit the use of {@code null} elements. * * <p>Iterators are <i>weakly consistent</i>, returning elements * reflecting the state of the deque at some point at or since the * creation of the iterator.  They do <em>not</em> throw {@link * java.util.ConcurrentModificationException * ConcurrentModificationException}, and may proceed concurrently with * other operations. * * <p>Beware that, unlike in most collections, the {@code size} method * is <em>NOT</em> a constant-time operation. Because of the * asynchronous nature of these deques, determining the current number * of elements requires a traversal of the elements, and so may report * inaccurate results if this collection is modified during traversal. * Additionally, the bulk operations {@code addAll}, * {@code removeAll}, {@code retainAll}, {@code containsAll}, * {@code equals}, and {@code toArray} are <em>not</em> guaranteed * to be performed atomically. For example, an iterator operating * concurrently with an {@code addAll} operation might view only some * of the added elements. * * <p>This class and its iterator implement all of the <em>optional</em> * methods of the {@link Deque} and {@link Iterator} interfaces. * * <p>Memory consistency effects: As with other concurrent collections, * actions in a thread prior to placing an object into a * {@code ConcurrentLinkedDeque} * <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a> * actions subsequent to the access or removal of that element from * the {@code ConcurrentLinkedDeque} in another thread. * * <p>This class is a member of the * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * * @since 1.7 * @author Doug Lea * @author Martin Buchholz * @param <E> the type of elements held in this collection */ public class ConcurrentLinkedDeque<E>    extends AbstractCollection<E>    implements Deque<E>, java.io.Serializable {     /*     * This is an implementation of a concurrent lock-free deque     * supporting interior removes but not interior insertions, as     * required to support the entire Deque interface.     *     * We extend the techniques developed for ConcurrentLinkedQueue and     * LinkedTransferQueue (see the internal docs for those classes).     * Understanding the ConcurrentLinkedQueue implementation is a     * prerequisite for understanding the implementation of this class.     *     * The data structure is a symmetrical doubly-linked "GC-robust"     * linked list of nodes.  We minimize the number of volatile writes     * using two techniques: advancing multiple hops with a single CAS     * and mixing volatile and non-volatile writes of the same memory     * locations.     *     * A node contains the expected E ("item") and links to predecessor     * ("prev") and successor ("next") nodes:     *     * class Node<E> { volatile Node<E> prev, next; volatile E item; }     *     * A node p is considered "live" if it contains a non-null item     * (p.item != null).  When an item is CASed to null, the item is     * atomically logically deleted from the collection.     *     * At any time, there is precisely one "first" node with a null     * prev reference that terminates any chain of prev references     * starting at a live node.  Similarly there is precisely one     * "last" node terminating any chain of next references starting at     * a live node.  The "first" and "last" nodes may or may not be live.     * The "first" and "last" nodes are always mutually reachable.     *     * A new element is added atomically by CASing the null prev or     * next reference in the first or last node to a fresh node     * containing the element.  The element's node atomically becomes     * "live" at that point.     *     * A node is considered "active" if it is a live node, or the     * first or last node.  Active nodes cannot be unlinked.     *     * A "self-link" is a next or prev reference that is the same node:     *   p.prev == p  or  p.next == p     * Self-links are used in the node unlinking process.  Active nodes     * never have self-links.     *     * A node p is active if and only if:     *     * p.item != null ||     * (p.prev == null && p.next != p) ||     * (p.next == null && p.prev != p)     *     * The deque object has two node references, "head" and "tail".     * The head and tail are only approximations to the first and last     * nodes of the deque.  The first node can always be found by     * following prev pointers from head; likewise for tail.  However,     * it is permissible for head and tail to be referring to deleted     * nodes that have been unlinked and so may not be reachable from     * any live node.     *     * There are 3 stages of node deletion;     * "logical deletion", "unlinking", and "gc-unlinking".     *     * 1. "logical deletion" by CASing item to null atomically removes     * the element from the collection, and makes the containing node     * eligible for unlinking.     *     * 2. "unlinking" makes a deleted node unreachable from active     * nodes, and thus eventually reclaimable by GC.  Unlinked nodes     * may remain reachable indefinitely from an iterator.     *     * Physical node unlinking is merely an optimization (albeit a     * critical one), and so can be performed at our convenience.  At     * any time, the set of live nodes maintained by prev and next     * links are identical, that is, the live nodes found via next     * links from the first node is equal to the elements found via     * prev links from the last node.  However, this is not true for     * nodes that have already been logically deleted - such nodes may     * be reachable in one direction only.     *     * 3. "gc-unlinking" takes unlinking further by making active     * nodes unreachable from deleted nodes, making it easier for the     * GC to reclaim future deleted nodes.  This step makes the data     * structure "gc-robust", as first described in detail by Boehm     * (http://portal.acm.org/citation.cfm?doid=503272.503282).     *     * GC-unlinked nodes may remain reachable indefinitely from an     * iterator, but unlike unlinked nodes, are never reachable from     * head or tail.     *     * Making the data structure GC-robust will eliminate the risk of     * unbounded memory retention with conservative GCs and is likely     * to improve performance with generational GCs.     *     * When a node is dequeued at either end, e.g. via poll(), we would     * like to break any references from the node to active nodes.  We     * develop further the use of self-links that was very effective in     * other concurrent collection classes.  The idea is to replace     * prev and next pointers with special values that are interpreted     * to mean off-the-list-at-one-end.  These are approximations, but     * good enough to preserve the properties we want in our     * traversals, e.g. we guarantee that a traversal will never visit     * the same element twice, but we don't guarantee whether a     * traversal that runs out of elements will be able to see more     * elements later after enqueues at that end.  Doing gc-unlinking     * safely is particularly tricky, since any node can be in use     * indefinitely (for example by an iterator).  We must ensure that     * the nodes pointed at by head/tail never get gc-unlinked, since     * head/tail are needed to get "back on track" by other nodes that     * are gc-unlinked.  gc-unlinking accounts for much of the     * implementation complexity.     *     * Since neither unlinking nor gc-unlinking are necessary for     * correctness, there are many implementation choices regarding     * frequency (eagerness) of these operations.  Since volatile     * reads are likely to be much cheaper than CASes, saving CASes by     * unlinking multiple adjacent nodes at a time may be a win.     * gc-unlinking can be performed rarely and still be effective,     * since it is most important that long chains of deleted nodes     * are occasionally broken.     *     * The actual representation we use is that p.next == p means to     * goto the first node (which in turn is reached by following prev     * pointers from head), and p.next == null && p.prev == p means     * that the iteration is at an end and that p is a (static final)     * dummy node, NEXT_TERMINATOR, and not the last active node.     * Finishing the iteration when encountering such a TERMINATOR is     * good enough for read-only traversals, so such traversals can use     * p.next == null as the termination condition.  When we need to     * find the last (active) node, for enqueueing a new node, we need     * to check whether we have reached a TERMINATOR node; if so,     * restart traversal from tail.     *     * The implementation is completely directionally symmetrical,     * except that most public methods that iterate through the list     * follow next pointers ("forward" direction).     *     * We believe (without full proof) that all single-element deque     * operations (e.g., addFirst, peekLast, pollLast) are linearizable     * (see Herlihy and Shavit's book).  However, some combinations of     * operations are known not to be linearizable.  In particular,     * when an addFirst(A) is racing with pollFirst() removing B, it is     * possible for an observer iterating over the elements to observe     * A B C and subsequently observe A C, even though no interior     * removes are ever performed.  Nevertheless, iterators behave     * reasonably, providing the "weakly consistent" guarantees.     *     * Empirically, microbenchmarks suggest that this class adds about     * 40% overhead relative to ConcurrentLinkedQueue, which feels as     * good as we can hope for.     */     private static final long serialVersionUID = 876323262645176354L;     /**     * A node from which the first node on list (that is, the unique node p     * with p.prev == null && p.next != p) can be reached in O(1) time.     * Invariants:     * - the first node is always O(1) reachable from head via prev links     * - all live nodes are reachable from the first node via succ()     * - head != null     * - (tmp = head).next != tmp || tmp != head     * - head is never gc-unlinked (but may be unlinked)     * Non-invariants:     * - head.item may or may not be null     * - head may not be reachable from the first or last node, or from tail     */    private transient volatile Node<E> head;     /**     * A node from which the last node on list (that is, the unique node p     * with p.next == null && p.prev != p) can be reached in O(1) time.     * Invariants:     * - the last node is always O(1) reachable from tail via next links     * - all live nodes are reachable from the last node via pred()     * - tail != null     * - tail is never gc-unlinked (but may be unlinked)     * Non-invariants:     * - tail.item may or may not be null     * - tail may not be reachable from the first or last node, or from head     */    private transient volatile Node<E> tail;     private static final Node<Object> PREV_TERMINATOR, NEXT_TERMINATOR;     @SuppressWarnings("unchecked")    Node<E> prevTerminator() {        return (Node<E>) PREV_TERMINATOR;    }     @SuppressWarnings("unchecked")    Node<E> nextTerminator() {        return (Node<E>) NEXT_TERMINATOR;    }     static final class Node<E> {        volatile Node<E> prev;        volatile E item;        volatile Node<E> next;         Node() {  // default constructor for NEXT_TERMINATOR, PREV_TERMINATOR        }         /**         * Constructs a new node.  Uses relaxed write because item can         * only be seen after publication via casNext or casPrev.         */        Node(E item) {            UNSAFE.putObject(this, itemOffset, item);        }         boolean casItem(E cmp, E val) {            return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);        }         void lazySetNext(Node<E> val) {            UNSAFE.putOrderedObject(this, nextOffset, val);        }         boolean casNext(Node<E> cmp, Node<E> val) {            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);        }         void lazySetPrev(Node<E> val) {            UNSAFE.putOrderedObject(this, prevOffset, val);        }         boolean casPrev(Node<E> cmp, Node<E> val) {            return UNSAFE.compareAndSwapObject(this, prevOffset, cmp, val);        }         // Unsafe mechanics         private static final sun.misc.Unsafe UNSAFE;        private static final long prevOffset;        private static final long itemOffset;        private static final long nextOffset;         static {            try {                UNSAFE = sun.misc.Unsafe.getUnsafe();                Class k = Node.class;                prevOffset = UNSAFE.objectFieldOffset                    (k.getDeclaredField("prev"));                itemOffset = UNSAFE.objectFieldOffset                    (k.getDeclaredField("item"));                nextOffset = UNSAFE.objectFieldOffset                    (k.getDeclaredField("next"));            } catch (Exception e) {                throw new Error(e);            }        }    }     /**     * Links e as first element.     */    private void linkFirst(E e) {        checkNotNull(e);        final Node<E> newNode = new Node<E>(e);         restartFromHead:        for (;;)            for (Node<E> h = head, p = h, q;;) {                if ((q = p.prev) != null &&                    (q = (p = q).prev) != null)                    // Check for head updates every other hop.                    // If p == q, we are sure to follow head instead.                    p = (h != (h = head)) ? h : q;                else if (p.next == p) // PREV_TERMINATOR                    continue restartFromHead;                else {                    // p is first node                    newNode.lazySetNext(p); // CAS piggyback                    if (p.casPrev(null, newNode)) {                        // Successful CAS is the linearization point                        // for e to become an element of this deque,                        // and for newNode to become "live".                        if (p != h) // hop two nodes at a time                            casHead(h, newNode);  // Failure is OK.                        return;                    }                    // Lost CAS race to another thread; re-read prev                }            }    }     /**     * Links e as last element.     */    private void linkLast(E e) {        checkNotNull(e);        final Node<E> newNode = new Node<E>(e);         restartFromTail:        for (;;)            for (Node<E> t = tail, p = t, q;;) {                if ((q = p.next) != null &&                    (q = (p = q).next) != null)                    // Check for tail updates every other hop.                    // If p == q, we are sure to follow tail instead.                    p = (t != (t = tail)) ? t : q;                else if (p.prev == p) // NEXT_TERMINATOR                    continue restartFromTail;                else {                    // p is last node                    newNode.lazySetPrev(p); // CAS piggyback                    if (p.casNext(null, newNode)) {                        // Successful CAS is the linearization point                        // for e to become an element of this deque,                        // and for newNode to become "live".                        if (p != t) // hop two nodes at a time                            casTail(t, newNode);  // Failure is OK.                        return;                    }                    // Lost CAS race to another thread; re-read next                }            }    }     private static final int HOPS = 2;     /**     * Unlinks non-null node x.     */    void unlink(Node<E> x) {        // assert x != null;        // assert x.item == null;        // assert x != PREV_TERMINATOR;        // assert x != NEXT_TERMINATOR;         final Node<E> prev = x.prev;        final Node<E> next = x.next;        if (prev == null) {            unlinkFirst(x, next);        } else if (next == null) {            unlinkLast(x, prev);        } else {            // Unlink interior node.            //            // This is the common case, since a series of polls at the            // same end will be "interior" removes, except perhaps for            // the first one, since end nodes cannot be unlinked.            //            // At any time, all active nodes are mutually reachable by            // following a sequence of either next or prev pointers.            //            // Our strategy is to find the unique active predecessor            // and successor of x.  Try to fix up their links so that            // they point to each other, leaving x unreachable from            // active nodes.  If successful, and if x has no live            // predecessor/successor, we additionally try to gc-unlink,            // leaving active nodes unreachable from x, by rechecking            // that the status of predecessor and successor are            // unchanged and ensuring that x is not reachable from            // tail/head, before setting x's prev/next links to their            // logical approximate replacements, self/TERMINATOR.            Node<E> activePred, activeSucc;            boolean isFirst, isLast;            int hops = 1;             // Find active predecessor            for (Node<E> p = prev; ; ++hops) {                if (p.item != null) {                    activePred = p;                    isFirst = false;                    break;                }                Node<E> q = p.prev;                if (q == null) {                    if (p.next == p)                        return;                    activePred = p;                    isFirst = true;                    break;                }                else if (p == q)                    return;                else                    p = q;            }             // Find active successor            for (Node<E> p = next; ; ++hops) {                if (p.item != null) {                    activeSucc = p;                    isLast = false;                    break;                }                Node<E> q = p.next;                if (q == null) {                    if (p.prev == p)                        return;                    activeSucc = p;                    isLast = true;                    break;                }                else if (p == q)                    return;                else                    p = q;            }             // TODO: better HOP heuristics

Lines 1–500 of 1469. Load more