Class LockFreePrefixTree
The LockFreePrefixTree 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 LockFreePrefix tree represents a Tree of nodes of classNode
, 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 tryResizeLinear
or 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
object.
 Since:
 22.3

Nested Class Summary
Modifier and TypeClassDescriptionstatic class
Policy for allocating objects of the lockfree prefix tree.static class
Allocator that allocates objects directly on the managed heap.static class
static class
Allocator that internally maintains several pools of preallocated objects, and allocates objects from those pools. 
Constructor Summary
ConstructorDescriptionLockFreePrefixTree
(LockFreePrefixTree.Allocator allocator) Create newLockFreePrefixTree
with root being a Node with key 0. 
Method Summary
Modifier and TypeMethodDescriptionvoid
reset()
Resets the tree.root()
The root node of the tree.<C> void
topDown
(C initialContext, BiFunction<C, Long, C> createContext, BiConsumer<C, Long> consumeValue) Traverse the tree topdown while maintaining a context.

Constructor Details

LockFreePrefixTree
Create newLockFreePrefixTree
with root being a Node with key 0. Since:
 22.3


Method Details

allocator

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

reset
public void reset()Resets the tree. Since:
 23.0

topDown
public <C> void topDown(C initialContext, BiFunction<C, Long, C> createContext, BiConsumer<C, Long> consumeValue) Traverse the tree topdown while maintaining a context. The context is a generic data structure corresponding to the depth of the traversal, i.e. given the initialContext and a createContext function, a new context is created for each visited child using the createContext function, starting with initialContext. Type Parameters:
C
 The type of the context Parameters:
initialContext
 The context for the root of the treecreateContext
 A function defining how the context for children is createdconsumeValue
 A function that consumes the nodes value Since:
 22.3
