Class SeqLockPrefixTree
The prefix tree supports a single operation root
, which returns the root node. The nodes
support the following operations: at
to obtain a child node, value
to obtain the
value at the current node, setValue
to atomically set the value and incValue
to
atomically increment the value.
The prefix tree is implemented as follows. The tree points to the root node. Each node points to a set of child nodes, where each child is associated with a key. Each node additionally holds an arity, which is the number of children, and the 64bit value of that node.
The set of child nodes can be represented as null
if the set is empty, an arraylist if
the the set is small, or a hash table if the set is large. In all cases, the keys and the child
nodes are kept in separate arrays.
The at
operation, which takes a node and a key, and returns the corresponding child node,
deserves an additional explanation. This operation creates an existing child associated with the
key, or atomically creates a new child, if there was no child for that key.
The at
operation is implemented as follows. There is a fastpath, which executes when the
child node already exists, and there are no concurrent modifications at that node, and the
slowpath, which executes when the child does not exist or when there is a concurrent
modification. To ensure that the slow path does not obtain a monitor, the fastpath relies on a
seqlock. This is a lightweight readwrite lock that consists of a single 64bit counter,
whose value is even when the lock is in the read mode, and odd when the lock is in the write
mode. The lock can be held by any number of readers, but at most 1 writer at any time.
In the readmode, the reader must verify that the value of the lock is even and that it did not change from the point when the read started until the point when the read ended, and additionally takes care that reading an invalid state does not crash the execution. If the read fails for either of these reasons, the reader proceeds to the writemode. In the writemode, the reader or the writer enters a heavy lock (i.e. monitor) and then increments the seqlock's value by one, does the modification, and then increments the seqlock's value by one to make it even again. The volatile access semantics of the seqlock's value, along with the fact that the node's data only "grows" over time, are the properties that ensure the correctness of this implementation.
 Since:
 22.3

Nested Class Summary

Constructor Summary

Method Summary

Constructor Details

SeqLockPrefixTree
public SeqLockPrefixTree()Create newSeqLockPrefixTree
with root being a Node with key 0. Since:
 22.3


Method Details

root
The root node of the tree. Returns:
 the root of the tree
 Since:
 22.3
