You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@aries.apache.org by cs...@apache.org on 2017/10/10 15:52:01 UTC
svn commit: r1811728 -
/aries/trunk/component-dsl/component-dsl/src/main/java/org/apache/aries/osgi/functional/internal/ConcurrentDoublyLinkedList.java
Author: csierra
Date: Tue Oct 10 15:52:01 2017
New Revision: 1811728
URL: http://svn.apache.org/viewvc?rev=1811728&view=rev
Log:
[Component-DSL] Add Doug Lea's doubly linked list impl
Added:
aries/trunk/component-dsl/component-dsl/src/main/java/org/apache/aries/osgi/functional/internal/ConcurrentDoublyLinkedList.java
Added: aries/trunk/component-dsl/component-dsl/src/main/java/org/apache/aries/osgi/functional/internal/ConcurrentDoublyLinkedList.java
URL: http://svn.apache.org/viewvc/aries/trunk/component-dsl/component-dsl/src/main/java/org/apache/aries/osgi/functional/internal/ConcurrentDoublyLinkedList.java?rev=1811728&view=auto
==============================================================================
--- aries/trunk/component-dsl/component-dsl/src/main/java/org/apache/aries/osgi/functional/internal/ConcurrentDoublyLinkedList.java (added)
+++ aries/trunk/component-dsl/component-dsl/src/main/java/org/apache/aries/osgi/functional/internal/ConcurrentDoublyLinkedList.java Tue Oct 10 15:52:01 2017
@@ -0,0 +1,942 @@
+/*
+ *
+ * Copyright 2012-2015 Viant.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License"); you may not
+ * use this file except in compliance with the License. You may obtain a copy of
+ * the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+ * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+ * License for the specific language governing permissions and limitations under
+ * the License.
+ *
+ */
+
+package org.apache.aries.osgi.functional.internal;
+
+
+/*
+ * 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/licenses/publicdomain
+ */
+
+import java.util.AbstractCollection;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.ConcurrentModificationException;
+import java.util.Deque;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+import java.util.concurrent.atomic.AtomicReference;
+
+/**
+ * A concurrent linked-list implementation of a {@link Deque} (double-ended
+ * queue). Concurrent insertion, removal, and access operations execute safely
+ * across multiple threads. 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
+ * ConcurrentModificationException}, and may proceed concurrently with other
+ * operations.
+ *
+ * <p>
+ * This class and its iterators implement all of the <em>optional</em> methods
+ * of the {@link Collection} and {@link Iterator} interfaces. Like most other
+ * concurrent collection implementations, this class does not permit the use of
+ * <tt>null</tt> elements. because some null arguments and return values
+ * cannot be reliably distinguished from the absence of elements. Arbitrarily,
+ * the {@link Collection#remove} method is mapped to
+ * <tt>removeFirstOccurrence</tt>, and {@link Collection#add} is mapped to
+ * <tt>addLast</tt>.
+ *
+ * <p>
+ * Beware that, unlike in most collections, the <tt>size</tt> 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.
+ *
+ * <p>
+ * This class is <tt>Serializable</tt>, but relies on default serialization
+ * mechanisms. Usually, it is a better idea for any serializable class using a
+ * <tt>ConcurrentLinkedDeque</tt> to instead serialize a snapshot of the
+ * elements obtained by method <tt>toArray</tt>.
+ *
+ * @author Doug Lea
+ * @param <E>
+ * the type of elements held in this collection
+ */
+
+public class ConcurrentDoublyLinkedList<E> extends AbstractCollection<E>
+ implements java.io.Serializable {
+
+ /*
+ * This is an adaptation of an algorithm described in Paul Martin's "A
+ * Practical Lock-Free Doubly-Linked List". Sun Labs Tech report. The basic
+ * idea is to primarily rely on next-pointers to ensure consistency.
+ * Prev-pointers are in part optimistic, reconstructed using forward
+ * pointers as needed. The main forward list uses a variant of HM-list
+ * algorithm similar to the one used in ConcurrentSkipListMap class, but a
+ * little simpler. It is also basically similar to the approach in Edya
+ * Ladan-Mozes and Nir Shavit "An Optimistic Approach to Lock-Free FIFO
+ * Queues" in DISC04.
+ *
+ * Quoting a summary in Paul Martin's tech report:
+ *
+ * All cleanups work to maintain these invariants: (1) forward pointers are
+ * the ground truth. (2) forward pointers to dead nodes can be improved by
+ * swinging them further forward around the dead node. (2.1) forward
+ * pointers are still correct when pointing to dead nodes, and forward
+ * pointers from dead nodes are left as they were when the node was deleted.
+ * (2.2) multiple dead nodes may point forward to the same node. (3)
+ * backward pointers were correct when they were installed (3.1) backward
+ * pointers are correct when pointing to any node which points forward to
+ * them, but since more than one forward pointer may point to them, the live
+ * one is best. (4) backward pointers that are out of date due to deletion
+ * point to a deleted node, and need to point further back until they point
+ * to the live node that points to their source. (5) backward pointers that
+ * are out of date due to insertion point too far backwards, so shortening
+ * their scope (by searching forward) fixes them. (6) backward pointers from
+ * a dead node cannot be "improved" since there may be no live node pointing
+ * forward to their origin. (However, it does no harm to try to improve them
+ * while racing with a deletion.)
+ *
+ *
+ * Notation guide for local variables n, b, f : a node, its predecessor, and
+ * successor s : some other successor
+ */
+
+ // Minor convenience utilities
+
+ /**
+ * Returns true if given reference is non-null and isn't a header, trailer,
+ * or marker.
+ *
+ * @param n
+ * (possibly null) node
+ * @return true if n exists as a user node
+ */
+ private static boolean usable(NodeImpl<?> n) {
+ return n != null && !n.isSpecial();
+ }
+
+ /**
+ * Throws NullPointerException if argument is null
+ *
+ * @param v
+ * the element
+ */
+ private static void checkNullArg(Object v) {
+ if (v == null)
+ throw new NullPointerException();
+ }
+
+ /**
+ * Returns element unless it is null, in which case throws
+ * NoSuchElementException.
+ *
+ * @param v
+ * the element
+ * @return the element
+ */
+ private E screenNullResult(E v) {
+ if (v == null)
+ throw new NoSuchElementException();
+ return v;
+ }
+
+ /**
+ * Creates an array list and fills it with elements of this list. Used by
+ * toArray.
+ *
+ * @return the arrayList
+ */
+ private ArrayList<E> toArrayList() {
+ ArrayList<E> c = new ArrayList<E>();
+ for (NodeImpl<E> n = header.forward(); n != null; n = n.forward())
+ c.add(n.element);
+ return c;
+ }
+
+ // Fields and constructors
+
+ private static final long serialVersionUID = 876323262645176354L;
+
+ /**
+ * List header. First usable node is at header.forward().
+ */
+ private final NodeImpl<E> header;
+
+ /**
+ * List trailer. Last usable node is at trailer.back().
+ */
+ private final NodeImpl<E> trailer;
+
+ /**
+ * Constructs an empty deque.
+ */
+ public ConcurrentDoublyLinkedList() {
+ NodeImpl h = new NodeImpl(null, null, null);
+ NodeImpl t = new NodeImpl(null, null, h);
+ h.setNext(t);
+ header = h;
+ trailer = t;
+ }
+
+ /**
+ * Constructs a deque containing the elements of the specified collection,
+ * in the order they are returned by the collection's iterator.
+ *
+ * @param c
+ * the collection whose elements are to be placed into this
+ * deque.
+ * @throws NullPointerException
+ * if <tt>c</tt> or any element within it is <tt>null</tt>
+ */
+ public ConcurrentDoublyLinkedList(Collection<? extends E> c) {
+ this();
+ addAll(c);
+ }
+
+ /**
+ * Prepends the given element at the beginning of this deque.
+ *
+ * @param o
+ * the element to be inserted at the beginning of this deque.
+ * @throws NullPointerException
+ * if the specified element is <tt>null</tt>
+ */
+ public void addFirst(E o) {
+ checkNullArg(o);
+ while (header.append(o) == null)
+ ;
+ }
+
+ /**
+ * Appends the given element to the end of this deque. This is identical in
+ * function to the <tt>add</tt> method.
+ *
+ * @param o
+ * the element to be inserted at the end of this deque.
+ * @throws NullPointerException
+ * if the specified element is <tt>null</tt>
+ */
+ public void addLast(E o) {
+ checkNullArg(o);
+ while (trailer.prepend(o) == null)
+ ;
+ }
+
+ /**
+ * Prepends the given element at the beginning of this deque.
+ *
+ * @param o
+ * the element to be inserted at the beginning of this deque.
+ * @return <tt>true</tt> always
+ * @throws NullPointerException
+ * if the specified element is <tt>null</tt>
+ */
+ public boolean offerFirst(E o) {
+ addFirst(o);
+ return true;
+ }
+
+ /**
+ * Appends the given element to the end of this deque. (Identical in
+ * function to the <tt>add</tt> method; included only for consistency.)
+ *
+ * @param o
+ * the element to be inserted at the end of this deque.
+ * @return <tt>true</tt> always
+ * @throws NullPointerException
+ * if the specified element is <tt>null</tt>
+ */
+ public boolean offerLast(E o) {
+ addLast(o);
+ return true;
+ }
+
+ /**
+ * Retrieves, but does not remove, the first element of this deque, or
+ * returns null if this deque is empty.
+ *
+ * @return the first element of this queue, or <tt>null</tt> if empty.
+ */
+ public E peekFirst() {
+ NodeImpl<E> n = header.successor();
+ return (n == null) ? null : n.element;
+ }
+
+ /**
+ * Retrieves, but does not remove, the last element of this deque, or
+ * returns null if this deque is empty.
+ *
+ * @return the last element of this deque, or <tt>null</tt> if empty.
+ */
+ public E peekLast() {
+ NodeImpl<E> n = trailer.predecessor();
+ return (n == null) ? null : n.element;
+ }
+
+ /**
+ * Returns the first element in this deque.
+ *
+ * @return the first element in this deque.
+ * @throws NoSuchElementException
+ * if this deque is empty.
+ */
+ public E getFirst() {
+ return screenNullResult(peekFirst());
+ }
+
+ /**
+ * Returns the last element in this deque.
+ *
+ * @return the last element in this deque.
+ * @throws NoSuchElementException
+ * if this deque is empty.
+ */
+ public E getLast() {
+ return screenNullResult(peekLast());
+ }
+
+ /**
+ * Retrieves and removes the first element of this deque, or returns null if
+ * this deque is empty.
+ *
+ * @return the first element of this deque, or <tt>null</tt> if empty.
+ */
+ public E pollFirst() {
+ for (;;) {
+ NodeImpl<E> n = header.successor();
+ if (!usable(n))
+ return null;
+ if (n.delete())
+ return n.element;
+ }
+ }
+
+ /**
+ * Retrieves and removes the last element of this deque, or returns null if
+ * this deque is empty.
+ *
+ * @return the last element of this deque, or <tt>null</tt> if empty.
+ */
+ public E pollLast() {
+ for (;;) {
+ NodeImpl<E> n = trailer.predecessor();
+ if (!usable(n))
+ return null;
+ if (n.delete())
+ return n.element;
+ }
+ }
+
+ /**
+ * Removes and returns the first element from this deque.
+ *
+ * @return the first element from this deque.
+ * @throws NoSuchElementException
+ * if this deque is empty.
+ */
+ public E removeFirst() {
+ return screenNullResult(pollFirst());
+ }
+
+ /**
+ * Removes and returns the last element from this deque.
+ *
+ * @return the last element from this deque.
+ * @throws NoSuchElementException
+ * if this deque is empty.
+ */
+ public E removeLast() {
+ return screenNullResult(pollLast());
+ }
+
+ // *** Queue and stack methods ***
+ public boolean offer(E e) {
+ return offerLast(e);
+ }
+
+ public boolean add(E e) {
+ return offerLast(e);
+ }
+
+ public E poll() {
+ return pollFirst();
+ }
+
+ public E remove() {
+ return removeFirst();
+ }
+
+ public E peek() {
+ return peekFirst();
+ }
+
+ public E element() {
+ return getFirst();
+ }
+
+ public void push(E e) {
+ addFirst(e);
+ }
+
+ public E pop() {
+ return removeFirst();
+ }
+
+ /**
+ * Removes the first element <tt>e</tt> such that <tt>o.equals(e)</tt>,
+ * if such an element exists in this deque. If the deque does not contain
+ * the element, it is unchanged.
+ *
+ * @param o
+ * element to be removed from this deque, if present.
+ * @return <tt>true</tt> if the deque contained the specified element.
+ * @throws NullPointerException
+ * if the specified element is <tt>null</tt>
+ */
+ public boolean removeFirstOccurrence(Object o) {
+ checkNullArg(o);
+ for (;;) {
+ NodeImpl<E> n = header.forward();
+ for (;;) {
+ if (n == null)
+ return false;
+ if (o.equals(n.element)) {
+ if (n.delete())
+ return true;
+ else
+ break; // restart if interference
+ }
+ n = n.forward();
+ }
+ }
+ }
+
+ /**
+ * Removes the last element <tt>e</tt> such that <tt>o.equals(e)</tt>,
+ * if such an element exists in this deque. If the deque does not contain
+ * the element, it is unchanged.
+ *
+ * @param o
+ * element to be removed from this deque, if present.
+ * @return <tt>true</tt> if the deque contained the specified element.
+ * @throws NullPointerException
+ * if the specified element is <tt>null</tt>
+ */
+ public boolean removeLastOccurrence(Object o) {
+ checkNullArg(o);
+ for (;;) {
+ NodeImpl<E> s = trailer;
+ for (;;) {
+ NodeImpl<E> n = s.back();
+ if (s.isDeleted() || (n != null && n.successor() != s))
+ break; // restart if pred link is suspect.
+ if (n == null)
+ return false;
+ if (o.equals(n.element)) {
+ if (n.delete())
+ return true;
+ else
+ break; // restart if interference
+ }
+ s = n;
+ }
+ }
+ }
+
+ /**
+ * Returns <tt>true</tt> if this deque contains at least one element
+ * <tt>e</tt> such that <tt>o.equals(e)</tt>.
+ *
+ * @param o
+ * element whose presence in this deque is to be tested.
+ * @return <tt>true</tt> if this deque contains the specified element.
+ */
+ public boolean contains(Object o) {
+ if (o == null)
+ return false;
+ for (NodeImpl<E> n = header.forward(); n != null; n = n.forward())
+ if (o.equals(n.element))
+ return true;
+ return false;
+ }
+
+ /**
+ * Returns <tt>true</tt> if this collection contains no elements.
+ * <p>
+ *
+ * @return <tt>true</tt> if this collection contains no elements.
+ */
+ public boolean isEmpty() {
+ return !usable(header.successor());
+ }
+
+ /**
+ * Returns the number of elements in this deque. If this deque contains more
+ * than <tt>Integer.MAX_VALUE</tt> elements, it returns
+ * <tt>Integer.MAX_VALUE</tt>.
+ *
+ * <p>
+ * Beware that, unlike in most collections, this method is <em>NOT</em> a
+ * constant-time operation. Because of the asynchronous nature of these
+ * deques, determining the current number of elements requires traversing
+ * them all to count them. Additionally, it is possible for the size to
+ * change during execution of this method, in which case the returned result
+ * will be inaccurate. Thus, this method is typically not very useful in
+ * concurrent applications.
+ *
+ * @return the number of elements in this deque.
+ */
+ public int size() {
+ long count = 0;
+ for (NodeImpl<E> n = header.forward(); n != null; n = n.forward())
+ ++count;
+ return (count >= Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int) count;
+ }
+
+ /**
+ * Removes the first element <tt>e</tt> such that <tt>o.equals(e)</tt>,
+ * if such an element exists in this deque. If the deque does not contain
+ * the element, it is unchanged.
+ *
+ * @param o
+ * element to be removed from this deque, if present.
+ * @return <tt>true</tt> if the deque contained the specified element.
+ * @throws NullPointerException
+ * if the specified element is <tt>null</tt>
+ */
+ public boolean remove(Object o) {
+ return removeFirstOccurrence(o);
+ }
+
+ /**
+ * Appends all of the elements in the specified collection to the end of
+ * this deque, in the order that they are returned by the specified
+ * collection's iterator. The behavior of this operation is undefined if the
+ * specified collection is modified while the operation is in progress.
+ * (This implies that the behavior of this call is undefined if the
+ * specified Collection is this deque, and this deque is nonempty.)
+ *
+ * @param c
+ * the elements to be inserted into this deque.
+ * @return <tt>true</tt> if this deque changed as a result of the call.
+ * @throws NullPointerException
+ * if <tt>c</tt> or any element within it is <tt>null</tt>
+ */
+ public boolean addAll(Collection<? extends E> c) {
+ Iterator<? extends E> it = c.iterator();
+ if (!it.hasNext())
+ return false;
+ do {
+ addLast(it.next());
+ } while (it.hasNext());
+ return true;
+ }
+
+ /**
+ * Removes all of the elements from this deque.
+ */
+ public void clear() {
+ while (pollFirst() != null)
+ ;
+ }
+
+ /**
+ * Returns an array containing all of the elements in this deque in the
+ * correct order.
+ *
+ * @return an array containing all of the elements in this deque in the
+ * correct order.
+ */
+ public Object[] toArray() {
+ return toArrayList().toArray();
+ }
+
+ /**
+ * Returns an array containing all of the elements in this deque in the
+ * correct order; the runtime type of the returned array is that of the
+ * specified array. If the deque fits in the specified array, it is returned
+ * therein. Otherwise, a new array is allocated with the runtime type of the
+ * specified array and the size of this deque.
+ * <p>
+ *
+ * If the deque fits in the specified array with room to spare (i.e., the
+ * array has more elements than the deque), the element in the array
+ * immediately following the end of the collection is set to null. This is
+ * useful in determining the length of the deque <i>only</i> if the caller
+ * knows that the deque does not contain any null elements.
+ *
+ * @param a
+ * the array into which the elements of the deque are to be
+ * stored, if it is big enough; otherwise, a new array of the
+ * same runtime type is allocated for this purpose.
+ * @return an array containing the elements of the deque.
+ * @throws ArrayStoreException
+ * if the runtime type of a is not a supertype of the runtime
+ * type of every element in this deque.
+ * @throws NullPointerException
+ * if the specified array is null.
+ */
+ public <T> T[] toArray(T[] a) {
+ return toArrayList().toArray(a);
+ }
+
+ /**
+ * Returns a weakly consistent iterator over the elements in this deque, in
+ * first-to-last order. The <tt>next</tt> method returns elements
+ * reflecting the state of the deque at some point at or since the creation
+ * of the iterator. The method does <em>not</em> throw
+ * {@link ConcurrentModificationException}, and may proceed concurrently
+ * with other operations.
+ *
+ * @return an iterator over the elements in this deque
+ */
+ public Iterator<E> iterator() {
+ return new CLDIterator();
+ }
+
+ final class CLDIterator implements Iterator<E> {
+ NodeImpl<E> last;
+
+ NodeImpl<E> next = header.forward();
+
+ public boolean hasNext() {
+ return next != null;
+ }
+
+ public E next() {
+ NodeImpl<E> l = last = next;
+ if (l == null)
+ throw new NoSuchElementException();
+ next = next.forward();
+ return l.element;
+ }
+
+ public void remove() {
+ NodeImpl<E> l = last;
+ if (l == null)
+ throw new IllegalStateException();
+ while (!l.delete() && !l.isDeleted())
+ ;
+ }
+ }
+
+}
+
+
+
+/**
+ * Linked Nodes. As a minor efficiency hack, this class opportunistically
+ * inherits from AtomicReference, with the atomic ref used as the "next"
+ * link.
+ *
+ * Nodes are in doubly-linked lists. There are three kinds of special nodes,
+ * distinguished by: * The list header has a null prev link * The list
+ * trailer has a null next link * A deletion marker has a prev link pointing
+ * to itself. All three kinds of special nodes have null element fields.
+ *
+ * Regular nodes have non-null element, next, and prev fields. To avoid
+ * visible inconsistencies when deletions overlap element replacement,
+ * replacements are done by replacing the node, not just setting the
+ * element.
+ *
+ * Nodes can be traversed by read-only ConcurrentLinkedDeque class
+ * operations just by following raw next pointers, so long as they ignore
+ * any special nodes seen along the way. (This is automated in method
+ * forward.) However, traversal using prev pointers is not guaranteed to see
+ * all live nodes since a prev pointer of a deleted node can become
+ * unrecoverably stale.
+ */
+
+class NodeImpl<E> extends AtomicReference<NodeImpl<E>> {
+ private volatile NodeImpl<E> prev;
+
+ final E element;
+
+ /** Creates a node with given contents */
+ NodeImpl(E element, NodeImpl<E> next, NodeImpl<E> prev) {
+ super(next);
+ this.prev = prev;
+ this.element = element;
+ }
+
+ /** Creates a marker node with given successor */
+ NodeImpl(NodeImpl<E> next) {
+ super(next);
+ this.prev = this;
+ this.element = null;
+ }
+
+ /**
+ * Gets next link (which is actually the value held as atomic
+ * reference).
+ */
+ private NodeImpl<E> getNext() {
+ return get();
+ }
+
+ /**
+ * Sets next link
+ *
+ * @param n
+ * the next node
+ */
+ void setNext(NodeImpl<E> n) {
+ set(n);
+ }
+
+ /**
+ * compareAndSet next link
+ */
+ private boolean casNext(NodeImpl<E> cmp, NodeImpl<E> val) {
+ return compareAndSet(cmp, val);
+ }
+
+ /**
+ * Gets prev link
+ */
+ private NodeImpl<E> getPrev() {
+ return prev;
+ }
+
+ /**
+ * Sets prev link
+ *
+ * @param b
+ * the previous node
+ */
+ void setPrev(NodeImpl<E> b) {
+ prev = b;
+ }
+
+ /**
+ * Returns true if this is a header, trailer, or marker node
+ */
+ boolean isSpecial() {
+ return element == null;
+ }
+
+ /**
+ * Returns true if this is a trailer node
+ */
+ boolean isTrailer() {
+ return getNext() == null;
+ }
+
+ /**
+ * Returns true if this is a header node
+ */
+ boolean isHeader() {
+ return getPrev() == null;
+ }
+
+ /**
+ * Returns true if this is a marker node
+ */
+ boolean isMarker() {
+ return getPrev() == this;
+ }
+
+ /**
+ * Returns true if this node is followed by a marker, meaning that it is
+ * deleted.
+ *
+ * @return true if this node is deleted
+ */
+ boolean isDeleted() {
+ NodeImpl<E> f = getNext();
+ return f != null && f.isMarker();
+ }
+
+ /**
+ * Returns next node, ignoring deletion marker
+ */
+ private NodeImpl<E> nextNonmarker() {
+ NodeImpl<E> f = getNext();
+ return (f == null || !f.isMarker()) ? f : f.getNext();
+ }
+
+ /**
+ * Returns the next non-deleted node, swinging next pointer around any
+ * encountered deleted nodes, and also patching up successor''s prev
+ * link to point back to this. Returns null if this node is trailer so
+ * has no successor.
+ *
+ * @return successor, or null if no such
+ */
+ NodeImpl<E> successor() {
+ NodeImpl<E> f = nextNonmarker();
+ for (;;) {
+ if (f == null)
+ return null;
+ if (!f.isDeleted()) {
+ if (f.getPrev() != this && !isDeleted())
+ f.setPrev(this); // relink f's prev
+ return f;
+ }
+ NodeImpl<E> s = f.nextNonmarker();
+ if (f == getNext())
+ casNext(f, s); // unlink f
+ f = s;
+ }
+ }
+
+ /**
+ * Returns the apparent predecessor of target by searching forward for
+ * it starting at this node, patching up pointers while traversing. Used
+ * by predecessor().
+ *
+ * @return target's predecessor, or null if not found
+ */
+ private NodeImpl<E> findPredecessorOf(NodeImpl<E> target) {
+ NodeImpl<E> n = this;
+ for (;;) {
+ NodeImpl<E> f = n.successor();
+ if (f == target)
+ return n;
+ if (f == null)
+ return null;
+ n = f;
+ }
+ }
+
+ /**
+ * Returns the previous non-deleted node, patching up pointers as
+ * needed. Returns null if this node is header so has no successor. May
+ * also return null if this node is deleted, so doesn't have a distinct
+ * predecessor.
+ *
+ * @return predecessor or null if not found
+ */
+ NodeImpl<E> predecessor() {
+ NodeImpl<E> n = this;
+ for (;;) {
+ NodeImpl<E> b = n.getPrev();
+ if (b == null)
+ return n.findPredecessorOf(this);
+ NodeImpl<E> s = b.getNext();
+ if (s == this)
+ return b;
+ if (s == null || !s.isMarker()) {
+ NodeImpl<E> p = b.findPredecessorOf(this);
+ if (p != null)
+ return p;
+ }
+ n = b;
+ }
+ }
+
+ /**
+ * Returns the next node containing a nondeleted user element. Use for
+ * forward list traversal.
+ *
+ * @return successor, or null if no such
+ */
+ NodeImpl<E> forward() {
+ NodeImpl<E> f = successor();
+ return (f == null || f.isSpecial()) ? null : f;
+ }
+
+ /**
+ * Returns previous node containing a nondeleted user element, if
+ * possible. Use for backward list traversal, but beware that if this
+ * method is called from a deleted node, it might not be able to
+ * determine a usable predecessor.
+ *
+ * @return predecessor, or null if no such could be found
+ */
+ NodeImpl<E> back() {
+ NodeImpl<E> f = predecessor();
+ return (f == null || f.isSpecial()) ? null : f;
+ }
+
+ /**
+ * Tries to insert a node holding element as successor, failing if this
+ * node is deleted.
+ *
+ * @param element
+ * the element
+ * @return the new node, or null on failure.
+ */
+ NodeImpl<E> append(E element) {
+ for (;;) {
+ NodeImpl<E> f = getNext();
+ if (f == null || f.isMarker())
+ return null;
+ NodeImpl<E> x = new NodeImpl<E>(element, f, this);
+ if (casNext(f, x)) {
+ f.setPrev(x); // optimistically link
+ return x;
+ }
+ }
+ }
+
+ /**
+ * Tries to insert a node holding element as predecessor, failing if no
+ * live predecessor can be found to link to.
+ *
+ * @param element
+ * the element
+ * @return the new node, or null on failure.
+ */
+ NodeImpl<E> prepend(E element) {
+ for (;;) {
+ NodeImpl<E> b = predecessor();
+ if (b == null)
+ return null;
+ NodeImpl<E> x = new NodeImpl<E>(element, this, b);
+ if (b.casNext(this, x)) {
+ setPrev(x); // optimistically link
+ return x;
+ }
+ }
+ }
+
+ /**
+ * Tries to mark this node as deleted, failing if already deleted or if
+ * this node is header or trailer
+ *
+ * @return true if successful
+ */
+ boolean delete() {
+ NodeImpl<E> b = getPrev();
+ NodeImpl<E> f = getNext();
+ if (b != null && f != null && !f.isMarker()
+ && casNext(f, new NodeImpl(f))) {
+ if (b.casNext(this, f))
+ f.setPrev(b);
+ return true;
+ }
+ return false;
+ }
+
+ /**
+ * Tries to insert a node holding element to replace this node. failing
+ * if already deleted.
+ *
+ * @param newElement
+ * the new element
+ * @return the new node, or null on failure.
+ */
+ NodeImpl<E> replace(E newElement) {
+ for (;;) {
+ NodeImpl<E> b = getPrev();
+ NodeImpl<E> f = getNext();
+ if (b == null || f == null || f.isMarker())
+ return null;
+ NodeImpl<E> x = new NodeImpl<E>(newElement, f, b);
+ if (casNext(f, new NodeImpl(x))) {
+ b.successor(); // to relink b
+ x.successor(); // to relink f
+ return x;
+ }
+ }
+ }
+}