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

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

#include <radix.h>

Inheritance diagram for RadixTree< T, Adapter >:
[legend]
Collaboration diagram for RadixTree< T, Adapter >:
[legend]

Classes

struct  RadixElement
 
struct  RadixNode
 

Public Member Functions

 RadixTree ()
 
 ~RadixTree ()
 
 RadixTree (const RadixTree &src)
 Copy semantic. More...
 
RadixTreeoperator= (const RadixTree &rhs)
 
 RadixTree (RadixTree &&src)
 Move semantic. More...
 
RadixTreeoperator= (RadixTree &&rhs)
 
bool insert (const RCUPtr< T > &value)
 Insert a value into the tree. More...
 
RCUPtr< T > get (const KeyType &key)
 Get the value corresponding to a key. More...
 
RCUPtr< const T > get (const KeyType &key) const
 
template<typename Callable >
bool forEachLeaf (Callable &&func) const
 
RCUPtr< T > remove (const KeyType &key)
 Remove an element from the tree. More...
 

Private Types

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

Private Member Functions

KeyType getId (const T &value) const
 
bool insert (const KeyType &key, RCUPtr< T > value)
 
template<typename Callable >
bool forEachLeaf (RadixElement e, Callable &&func) const
 
- Private Member Functions inherited from PassthroughAdapter< T >
auto && getId (const T &e) const
 

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(KeyType)
 
static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS
 

Detailed Description

template<typename T, typename Adapter = PassthroughAdapter<T>>
struct RadixTree< T, Adapter >

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 40 of file radix.h.

Member Typedef Documentation

◆ KeyType

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

Definition at line 46 of file radix.h.

Constructor & Destructor Documentation

◆ RadixTree() [1/3]

template<typename T , typename Adapter = PassthroughAdapter<T>>
RadixTree< T, Adapter >::RadixTree ( )
inline

Definition at line 58 of file radix.h.

◆ ~RadixTree()

template<typename T , typename Adapter = PassthroughAdapter<T>>
RadixTree< T, Adapter >::~RadixTree ( )
inline

Definition at line 59 of file radix.h.

◆ RadixTree() [2/3]

template<typename T , typename Adapter = PassthroughAdapter<T>>
RadixTree< T, Adapter >::RadixTree ( const RadixTree< T, Adapter > &  src)
inline

Copy semantic.

Definition at line 64 of file radix.h.

Here is the call graph for this function:

◆ RadixTree() [3/3]

template<typename T , typename Adapter = PassthroughAdapter<T>>
RadixTree< T, Adapter >::RadixTree ( RadixTree< T, Adapter > &&  src)
inline

Move semantic.

Definition at line 96 of file radix.h.

Member Function Documentation

◆ forEachLeaf() [1/2]

template<typename T , typename Adapter = PassthroughAdapter<T>>
template<typename Callable >
bool RadixTree< T, Adapter >::forEachLeaf ( Callable &&  func) const
inline

Definition at line 144 of file radix.h.

Here is the caller graph for this function:

◆ forEachLeaf() [2/2]

template<typename T , typename Adapter = PassthroughAdapter<T>>
template<typename Callable >
bool RadixTree< T, Adapter >::forEachLeaf ( RadixElement  e,
Callable &&  func 
) const
inlineprivate

Definition at line 258 of file radix.h.

Here is the call graph for this function:

◆ get() [1/2]

template<typename T , typename Adapter = PassthroughAdapter<T>>
RCUPtr<T> RadixTree< T, Adapter >::get ( const KeyType key)
inline

Get the value corresponding to a key.

Returns the value if found, nullptr if not.

Definition at line 118 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 , typename Adapter = PassthroughAdapter<T>>
RCUPtr<const T> RadixTree< T, Adapter >::get ( const KeyType key) const
inline

Definition at line 139 of file radix.h.

Here is the call graph for this function:

◆ getId()

template<typename T , typename Adapter = PassthroughAdapter<T>>
KeyType RadixTree< T, Adapter >::getId ( const T &  value) const
inlineprivate

Definition at line 210 of file radix.h.

Here is the caller graph for this function:

◆ insert() [1/2]

template<typename T , typename Adapter = PassthroughAdapter<T>>
bool RadixTree< T, Adapter >::insert ( const KeyType key,
RCUPtr< T >  value 
)
inlineprivate

Definition at line 212 of file radix.h.

Here is the call graph for this function:

◆ insert() [2/2]

template<typename T , typename Adapter = PassthroughAdapter<T>>
bool RadixTree< T, Adapter >::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 112 of file radix.h.

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

◆ operator=() [1/2]

template<typename T , typename Adapter = PassthroughAdapter<T>>
RadixTree& RadixTree< T, Adapter >::operator= ( const RadixTree< T, Adapter > &  rhs)
inline

Definition at line 77 of file radix.h.

Here is the call graph for this function:

◆ operator=() [2/2]

template<typename T , typename Adapter = PassthroughAdapter<T>>
RadixTree& RadixTree< T, Adapter >::operator= ( RadixTree< T, Adapter > &&  rhs)
inline

Definition at line 97 of file radix.h.

◆ remove()

template<typename T , typename Adapter = PassthroughAdapter<T>>
RCUPtr<T> RadixTree< T, Adapter >::remove ( const KeyType key)
inline

Remove an element from the tree.

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

Definition at line 181 of file radix.h.

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

Member Data Documentation

◆ BITS

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

Definition at line 42 of file radix.h.

◆ CHILD_PER_LEVEL

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

Definition at line 44 of file radix.h.

◆ KEY_BITS

template<typename T , typename Adapter = PassthroughAdapter<T>>
const size_t RadixTree< T, Adapter >::KEY_BITS = 8 * sizeof(KeyType)
staticprivate

Definition at line 49 of file radix.h.

◆ MASK

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

Definition at line 43 of file radix.h.

◆ root

template<typename T , typename Adapter = PassthroughAdapter<T>>
std::atomic<RadixElement> RadixTree< T, Adapter >::root
private

Definition at line 55 of file radix.h.

◆ TOP_LEVEL

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

Definition at line 50 of file radix.h.


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