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.