Class 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.

  • Constructor Details

  • Method Details

    • allocator

      public LockFreePrefixTree.Allocator allocator()
    • root

      public LockFreePrefixTree.Node root()
      The root node of the tree.
      the root of the tree
    • reset

      public void reset()
      Resets the tree.
    • 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
      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