public class LockFreePrefixTree extends Object
The LockFreePrefixTree supports a single operation
root, which returns the root node. The
nodes support the following operations:
at to obtain a child node,
obtain the value at the current node,
setValue to atomically set the value, and
incValue to atomically increment the value.
The LockFreePrefix tree represents a Tree of nodes of class
Node, with each node having a
key and an atomic reference array of children. The underlying
children structure is
represented as a LinearArray if the number of children is under a threshold, and represented by a
hash table once the threshold is reached.
Any additions or accesses to the datastructure are done using the
at function. The
at function takes a key value as a parameter and either returns an already existing node
or inserts a new node and returns it. The function may cause the underlying AtomicReferenceArray
to grow in size, either with
tryResizeHash. Insertion of new
nodes is always done with the CAS operation, to ensure atomic updates and guarantee the progress
of at least a single thread in the execution. Additionally, any growth operations occur
atomically, as we perform a CAS with the reference to the Array to a new, freshly allocated array
|Modifier and Type||Class and Description|
|Constructor and Description|
|Modifier and Type||Method and Description|
The root node of the tree.
Traverse the tree top-down while maintaining a context.
LockFreePrefixTreewith root being a Node with key 0.
public LockFreePrefixTree.Node root()
public <C> void topDown(C initialContext, BiFunction<C,Long,C> createContext, BiConsumer<C,Long> consumeValue)
C- The type of the context
initialContext- The context for the root of the tree
createContext- A function defining how the context for children is created
consumeValue- A function that consumes the nodes value