ConcurrentLinkedDeque.Node

java.lang.Object
- java.util.concurrent.atomic.AtomicReference<ConcurrentLinkedDeque.Node<E>>
- - com.mongodb.ConcurrentLinkedDeque.Node<E>

All Implemented Interfaces:

java.io.Serializable

Enclosing class:

ConcurrentLinkedDeque<E>
```
static final class ConcurrentLinkedDeque.Node<E>
extends java.util.concurrent.atomic.AtomicReference<ConcurrentLinkedDeque.Node<E>>
```
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.

Field Summary

Fields
Modifier and Type Field and Description

(package private) E element

private ConcurrentLinkedDeque.Node<E> prev

private static long serialVersionUID

Fields
Modifier and Type	Field and Description
`(package private) E`	`element`
`private ConcurrentLinkedDeque.Node<E>`	`prev`
`private static long`	`serialVersionUID`

Constructor Summary

Constructors
Constructor and Description
`Node(ConcurrentLinkedDeque.Node<E> next)` Creates a marker node with given successor.
`Node(E element, ConcurrentLinkedDeque.Node<E> next, ConcurrentLinkedDeque.Node<E> prev)` Creates a node with given contents.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`(package private) ConcurrentLinkedDeque.Node<E>`	`append(E element)` Tries to insert a node holding element as successor, failing if this node is deleted.
`(package private) ConcurrentLinkedDeque.Node<E>`	`back()` Returns previous node containing a nondeleted user element, if possible.
`private boolean`	`casNext(ConcurrentLinkedDeque.Node<E> cmp, ConcurrentLinkedDeque.Node<E> val)` compareAndSet next link
`(package private) boolean`	`delete()` Tries to mark this node as deleted, failing if already deleted or if this node is header or trailer.
`private ConcurrentLinkedDeque.Node<E>`	`findPredecessorOf(ConcurrentLinkedDeque.Node<E> target)` Returns the apparent predecessor of target by searching forward for it, starting at this node, patching up pointers while traversing.
`(package private) ConcurrentLinkedDeque.Node<E>`	`forward()` Returns the next node containing a nondeleted user element.
`private ConcurrentLinkedDeque.Node<E>`	`getNext()` Gets next link (which is actually the value held as atomic reference).
`private ConcurrentLinkedDeque.Node<E>`	`getPrev()` Gets prev link.
`(package private) boolean`	`isDeleted()` Returns true if this node is followed by a marker node, meaning that this node is deleted.
`(package private) boolean`	`isHeader()` Returns true if this is a header node.
`(package private) boolean`	`isMarker()` Returns true if this is a marker node.
`(package private) boolean`	`isSpecial()` Returns true if this is a header, trailer, or marker node.
`(package private) boolean`	`isTrailer()` Returns true if this is a trailer node.
`private ConcurrentLinkedDeque.Node<E>`	`nextNonmarker()` Returns next node, ignoring deletion marker.
`(package private) ConcurrentLinkedDeque.Node<E>`	`predecessor()` Returns the previous non-deleted node, patching up pointers as needed.
`(package private) ConcurrentLinkedDeque.Node<E>`	`prepend(E element)` Tries to insert a node holding element as predecessor, failing if no live predecessor can be found to link to.
`(package private) ConcurrentLinkedDeque.Node<E>`	`replace(E newElement)` Tries to insert a node holding element to replace this node.
`(package private) void`	`setNext(ConcurrentLinkedDeque.Node<E> n)` Sets next link.
`(package private) void`	`setPrev(ConcurrentLinkedDeque.Node<E> b)` Sets prev link.
`(package private) ConcurrentLinkedDeque.Node<E>`	`successor()` 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.

Methods inherited from class java.util.concurrent.atomic.AtomicReference
accumulateAndGet, compareAndSet, get, getAndAccumulate, getAndSet, getAndUpdate, lazySet, set, toString, updateAndGet, weakCompareAndSet

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- Field Detail
  - prev
```
private volatile ConcurrentLinkedDeque.Node<E> prev
```
  - element
```
final E element
```
  - serialVersionUID
```
private static final long serialVersionUID
```
    See Also:
    
    Constant Field Values
- Constructor Detail
  - Node
```
Node(E element,
     ConcurrentLinkedDeque.Node<E> next,
     ConcurrentLinkedDeque.Node<E> prev)
```
    Creates a node with given contents.
  - Node
```
Node(ConcurrentLinkedDeque.Node<E> next)
```
    Creates a marker node with given successor.
- Method Detail
  - getNext
```
private ConcurrentLinkedDeque.Node<E> getNext()
```
    Gets next link (which is actually the value held as atomic reference).
  - setNext
```
void setNext(ConcurrentLinkedDeque.Node<E> n)
```
    Sets next link.
    
    Parameters:
    
    n - the next node
  - casNext
```
private boolean casNext(ConcurrentLinkedDeque.Node<E> cmp,
                        ConcurrentLinkedDeque.Node<E> val)
```
    compareAndSet next link
  - getPrev
```
private ConcurrentLinkedDeque.Node<E> getPrev()
```
    Gets prev link.
  - setPrev
```
void setPrev(ConcurrentLinkedDeque.Node<E> b)
```
    Sets prev link.
    
    Parameters:
    
    b - the previous node
  - isSpecial
```
boolean isSpecial()
```
    Returns true if this is a header, trailer, or marker node.
  - isTrailer
```
boolean isTrailer()
```
    Returns true if this is a trailer node.
  - isHeader
```
boolean isHeader()
```
    Returns true if this is a header node.
  - isMarker
```
boolean isMarker()
```
    Returns true if this is a marker node.
  - isDeleted
```
boolean isDeleted()
```
    Returns true if this node is followed by a marker node, meaning that this node is deleted.
    
    Returns:
    
    true if this node is deleted
  - nextNonmarker
```
private ConcurrentLinkedDeque.Node<E> nextNonmarker()
```
    Returns next node, ignoring deletion marker.
  - successor
```
ConcurrentLinkedDeque.Node<E> successor()
```
    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.
    
    Returns:
    
    successor, or null if no such
  - findPredecessorOf
```
private ConcurrentLinkedDeque.Node<E> findPredecessorOf(ConcurrentLinkedDeque.Node<E> target)
```
    Returns the apparent predecessor of target by searching forward for it, starting at this node, patching up pointers while traversing. Used by predecessor().
    
    Returns:
    
    target's predecessor, or null if not found
  - predecessor
```
ConcurrentLinkedDeque.Node<E> predecessor()
```
    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.
    
    Returns:
    
    predecessor, or null if not found
  - forward
```
ConcurrentLinkedDeque.Node<E> forward()
```
    Returns the next node containing a nondeleted user element. Use for forward list traversal.
    
    Returns:
    
    successor, or null if no such
  - back
```
ConcurrentLinkedDeque.Node<E> back()
```
    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.
    
    Returns:
    
    predecessor, or null if no such could be found
  - append
```
ConcurrentLinkedDeque.Node<E> append(E element)
```
    Tries to insert a node holding element as successor, failing if this node is deleted.
    
    Parameters:
    
    element - the element
    
    Returns:
    
    the new node, or null on failure
  - prepend
```
ConcurrentLinkedDeque.Node<E> prepend(E element)
```
    Tries to insert a node holding element as predecessor, failing if no live predecessor can be found to link to.
    
    Parameters:
    
    element - the element
    
    Returns:
    
    the new node, or null on failure
  - delete
```
boolean delete()
```
    Tries to mark this node as deleted, failing if already deleted or if this node is header or trailer.
    
    Returns:
    
    true if successful
  - replace
```
ConcurrentLinkedDeque.Node<E> replace(E newElement)
```
    Tries to insert a node holding element to replace this node. failing if already deleted. A currently unused proof of concept that demonstrates atomic node content replacement. Although this implementation ensures that exactly one version of this Node is alive at a given time, it fails to maintain atomicity in the sense that iterators may encounter both the old and new versions of the element.
    
    Parameters:
    
    newElement - the new element
    
    Returns:
    
    the new node, or null on failure

Class ConcurrentLinkedDeque.Node<E>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.util.concurrent.atomic.AtomicReference

Methods inherited from class java.lang.Object

Field Detail

prev

element

serialVersionUID

Constructor Detail

Node

Node

Method Detail

getNext

setNext

casNext

getPrev

setPrev

isSpecial

isTrailer

isHeader

isMarker

isDeleted

nextNonmarker

successor

findPredecessorOf

predecessor

forward

back

append

prepend

delete

replace