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

#include <radix.h>

Inheritance diagram for RadixTree< T, Adapter >:

Collaboration diagram for RadixTree< T, Adapter >:

Classes
struct	RadixElement

struct	RadixNode

Public Member Functions
	RadixTree ()

	~RadixTree ()

	RadixTree (const RadixTree &src)
	Copy semantic.

RadixTree &	operator= (const RadixTree &rhs)

	RadixTree (RadixTree &&src)
	Move semantic.

RadixTree &	operator= (RadixTree &&rhs)

bool	insert (const RCUPtr< T > &value)
	Insert a value into the tree.

RCUPtr< T >	get (const KeyType &key)
	Get the value corresponding to a key.

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.

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< RadixElement >	root

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 call graph for this function:

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.

Here is the call graph for this function:

◆ 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:

src/radix.h

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ KeyType

Constructor & Destructor Documentation

◆ RadixTree() [1/3]

◆ ~RadixTree()

◆ RadixTree() [2/3]

◆ RadixTree() [3/3]

Member Function Documentation

◆ forEachLeaf() [1/2]

◆ forEachLeaf() [2/2]

◆ get() [1/2]

◆ get() [2/2]

◆ getId()

◆ insert() [1/2]

◆ insert() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ remove()

Member Data Documentation

◆ BITS

◆ CHILD_PER_LEVEL

◆ KEY_BITS

◆ MASK

◆ root

◆ TOP_LEVEL