org.jboss.util.collection

Class ConcurrentSkipListMap.Node<K,V>

java.lang.Object

org.jboss.util.collection.ConcurrentSkipListMap.Node<K,V>

Enclosing class:

ConcurrentSkipListMap<K,V>

static final class ConcurrentSkipListMap.Node<K,V>
extends java.lang.Object

Nodes hold keys and values, and are singly linked in sorted order, possibly with some intervening marker nodes. The list is headed by a dummy node accessible as head.node. The value field is declared only as Object because it takes special non-V values for marker and header nodes.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) K	key
(package private) ConcurrentSkipListMap.Node<K,V>	next
(package private) static java.util.concurrent.atomic.AtomicReferenceFieldUpdater<ConcurrentSkipListMap.Node,ConcurrentSkipListMap.Node>	nextUpdater Updater for casNext
(package private) java.lang.Object	value
(package private) static java.util.concurrent.atomic.AtomicReferenceFieldUpdater<ConcurrentSkipListMap.Node,java.lang.Object>	valueUpdater

Constructor Summary

Constructors

Constructor and Description
Node(ConcurrentSkipListMap.Node<K,V> next) Creates a new marker node.
Node(K key, java.lang.Object value, ConcurrentSkipListMap.Node<K,V> next) Creates a new regular node.

Method Summary

Modifier and Type	Method and Description
(package private) boolean	appendMarker(ConcurrentSkipListMap.Node<K,V> f) Tries to append a deletion marker to this node.
(package private) boolean	casNext(ConcurrentSkipListMap.Node<K,V> cmp, ConcurrentSkipListMap.Node<K,V> val) compareAndSet next field
(package private) boolean	casValue(java.lang.Object cmp, java.lang.Object val) compareAndSet value field
(package private) ConcurrentSkipListMap.SnapshotEntry<K,V>	createSnapshot() Create and return a new SnapshotEntry holding current mapping if this node holds a valid value, else null
(package private) V	getValidValue() Return value if this node contains a valid key-value pair, else null.
(package private) void	helpDelete(ConcurrentSkipListMap.Node<K,V> b, ConcurrentSkipListMap.Node<K,V> f) Helps out a deletion by appending marker or unlinking from predecessor.
(package private) boolean	isBaseHeader() Return true if this node is the header of base-level list.
(package private) boolean	isMarker() Return true if this node is a marker.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

key

final K key

value

volatile java.lang.Object value

next

volatile ConcurrentSkipListMap.Node<K,V> next

nextUpdater

static final java.util.concurrent.atomic.AtomicReferenceFieldUpdater<ConcurrentSkipListMap.Node,ConcurrentSkipListMap.Node> nextUpdater

Updater for casNext

valueUpdater

static final java.util.concurrent.atomic.AtomicReferenceFieldUpdater<ConcurrentSkipListMap.Node,java.lang.Object> valueUpdater

Constructor Detail

Node

Node(K key,
     java.lang.Object value,
     ConcurrentSkipListMap.Node<K,V> next)

Creates a new regular node.

Node

Node(ConcurrentSkipListMap.Node<K,V> next)

Creates a new marker node. A marker is distinguished by having its value field point to itself. Marker nodes also have null keys, a fact that is exploited in a few places, but this doesn't distinguish markers from the base-level header node (head.node), which also has a null key.

Method Detail

casValue

boolean casValue(java.lang.Object cmp,
                 java.lang.Object val)

compareAndSet value field

casNext

boolean casNext(ConcurrentSkipListMap.Node<K,V> cmp,
                ConcurrentSkipListMap.Node<K,V> val)

compareAndSet next field

isMarker

boolean isMarker()

Return true if this node is a marker. This method isn't actually called in an any current code checking for markers because callers will have already read value field and need to use that read (not another done here) and so directly test if value points to node.

Parameters:

n - a possibly null reference to a node

Returns:

true if this node is a marker node

isBaseHeader

boolean isBaseHeader()

Return true if this node is the header of base-level list.

Returns:

true if this node is header node

appendMarker

boolean appendMarker(ConcurrentSkipListMap.Node<K,V> f)

Tries to append a deletion marker to this node.

Parameters:

f - the assumed current successor of this node

Returns:

true if successful

helpDelete

void helpDelete(ConcurrentSkipListMap.Node<K,V> b,
                ConcurrentSkipListMap.Node<K,V> f)

Helps out a deletion by appending marker or unlinking from predecessor. This is called during traversals when value field seen to be null.

Parameters:

b - predecessor

f - successor

getValidValue

V getValidValue()

Return value if this node contains a valid key-value pair, else null.

Returns:

this node's value if it isn't a marker or header or is deleted, else null.

createSnapshot

ConcurrentSkipListMap.SnapshotEntry<K,V> createSnapshot()

Create and return a new SnapshotEntry holding current mapping if this node holds a valid value, else null

Returns:

new entry or null