Bitcoin ABC  0.24.7
P2P Digital Currency
Classes | Public Member Functions | Private Types | Private Member Functions | Private Attributes | Static Private Attributes | List of all members
RadixTree< T > Struct Template Reference

This is a radix tree storing values identified by a unique key. More...

#include <radix.h>

Classes

struct  RadixElement
 
struct  RadixNode
 

Public Member Functions

 RadixTree ()
 
 ~RadixTree ()
 
 RadixTree (const RadixTree &)=delete
 
RadixTreeoperator= (const RadixTree &)=delete
 
bool insert (const RCUPtr< T > &value)
 Insert a value into the tree. More...
 
RCUPtr< T > get (const K &key)
 Get the value corresponding to a key. More...
 
RCUPtr< const T > get (const K &key) const
 
RCUPtr< T > remove (const K &key)
 Remove an element from the tree. More...
 

Private Types

using K = typename std::remove_reference< decltype(std::declval< T & >().getId())>::type
 

Private Member Functions

bool insert (const K &key, RCUPtr< T > value)
 

Private Attributes

std::atomic< RadixElementroot
 

Static Private Attributes

static const int BITS = 4
 
static const int MASK = (1 << BITS) - 1
 
static const size_t CHILD_PER_LEVEL = 1 << BITS
 
static const size_t KEY_BITS = 8 * sizeof(K)
 
static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS
 

Detailed Description

template<typename T>
struct RadixTree< T >

This is a radix tree storing values identified by a unique key.

The tree is composed of nodes (RadixNode) containing an array of RadixElement. The key is split into chunks of a few bits that serve as an index into that array. RadixElement is a discriminated union of either a RadixNode* representing the next level in the tree, or a T* representing a leaf. New RadixNode are added lazily when two leaves would go in the same slot.

Reads walk the tree using sequential atomic loads, and insertions are done using CAS, which ensures both can be executed lock free. Removing any elements from the tree can also be done using CAS, but requires waiting for other readers before being destroyed. The tree uses RCU to track which thread is reading the tree, which allows deletion to wait for other readers to be up to speed before destroying anything. It is therefore crucial that the lock be taken before reading anything in the tree.

Definition at line 35 of file radix.h.

Member Typedef Documentation

◆ K

template<typename T >
using RadixTree< T >::K = typename std::remove_reference<decltype( std::declval<T &>().getId())>::type
private

Definition at line 42 of file radix.h.

Constructor & Destructor Documentation

◆ RadixTree() [1/2]

template<typename T >
RadixTree< T >::RadixTree ( )
inline

Definition at line 52 of file radix.h.

◆ ~RadixTree()

template<typename T >
RadixTree< T >::~RadixTree ( )
inline

Definition at line 53 of file radix.h.

◆ RadixTree() [2/2]

template<typename T >
RadixTree< T >::RadixTree ( const RadixTree< T > &  )
delete

Member Function Documentation

◆ get() [1/2]

template<typename T >
RCUPtr<T> RadixTree< T >::get ( const K key)
inline

Get the value corresponding to a key.

Returns the value if found, nullptr if not.

Definition at line 70 of file radix.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ get() [2/2]

template<typename T >
RCUPtr<const T> RadixTree< T >::get ( const K key) const
inline

Definition at line 91 of file radix.h.

Here is the call graph for this function:

◆ insert() [1/2]

template<typename T >
bool RadixTree< T >::insert ( const K key,
RCUPtr< T >  value 
)
inlineprivate

Definition at line 136 of file radix.h.

Here is the call graph for this function:

◆ insert() [2/2]

template<typename T >
bool RadixTree< T >::insert ( const RCUPtr< T > &  value)
inline

Insert a value into the tree.

Returns true if the value was inserted, false if it was already present.

Definition at line 62 of file radix.h.

◆ operator=()

template<typename T >
RadixTree& RadixTree< T >::operator= ( const RadixTree< T > &  )
delete

◆ remove()

template<typename T >
RCUPtr<T> RadixTree< T >::remove ( const K key)
inline

Remove an element from the tree.

Returns the removed element, or nullptr if there isn't one.

Definition at line 100 of file radix.h.

Here is the call graph for this function:

Member Data Documentation

◆ BITS

template<typename T >
const int RadixTree< T >::BITS = 4
staticprivate

Definition at line 37 of file radix.h.

◆ CHILD_PER_LEVEL

template<typename T >
const size_t RadixTree< T >::CHILD_PER_LEVEL = 1 << BITS
staticprivate

Definition at line 39 of file radix.h.

◆ KEY_BITS

template<typename T >
const size_t RadixTree< T >::KEY_BITS = 8 * sizeof(K)
staticprivate

Definition at line 43 of file radix.h.

◆ MASK

template<typename T >
const int RadixTree< T >::MASK = (1 << BITS) - 1
staticprivate

Definition at line 38 of file radix.h.

◆ root

template<typename T >
std::atomic<RadixElement> RadixTree< T >::root
private

Definition at line 47 of file radix.h.

◆ TOP_LEVEL

template<typename T >
const uint32_t RadixTree< T >::TOP_LEVEL = (KEY_BITS - 1) / BITS
staticprivate

Definition at line 44 of file radix.h.


The documentation for this struct was generated from the following file: