Class LockFreePrefixTree

java.lang.Object

org.graalvm.collections.LockFreePrefixTree

public class LockFreePrefixTree
extends Object

Thread-safe and lock-free prefix-tree implementation in which keys are sequences of 64-bit values, and the values are 64-bit values. The LockFreePrefixTree supports the same operations as the PrefixTree as follows:

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

Nested Classes

Modifier and Type	Class	Description
static class	LockFreePrefixTree.Allocator	Policy for allocating objects of the lock-free prefix tree.
static class	LockFreePrefixTree.HeapAllocator	Allocator that allocates objects directly on the managed heap.
static class	LockFreePrefixTree.Node
static class	LockFreePrefixTree.ObjectPoolingAllocator	Allocator that internally maintains several pools of preallocated objects, and allocates objects from those pools.

Constructor Summary

Constructors

Constructor	Description
LockFreePrefixTree(LockFreePrefixTree.Allocator allocator)	Create new LockFreePrefixTree with root being a Node with key 0.

Method Summary

Modifier and Type	Method	Description
LockFreePrefixTree.Allocator	allocator()
void	reset()	Resets the tree.
LockFreePrefixTree.Node	root()	The root node of the tree.
<C> void	topDown(C initialContext, BiFunction<C,Long,C> createContext, BiConsumer<C,Long> consumeValue)	Traverse the tree top-down while maintaining a context.

Methods inherited from class Object

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

Constructor Details

LockFreePrefixTree

public LockFreePrefixTree(LockFreePrefixTree.Allocator allocator)

Create new LockFreePrefixTree with root being a Node with key 0.

Since:

22.3

Method Details

allocator

public LockFreePrefixTree.Allocator allocator()

root

public LockFreePrefixTree.Node 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 top-down 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 tree

createContext - A function defining how the context for children is created

consumeValue - A function that consumes the nodes value

Since:

22.3