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.
template<typename T , typename Adapter = PassthroughAdapter<T>>
Get the value corresponding to a key.
Returns the value if found, nullptr if not.
Definition at line 118 of file radix.h.
template<typename T , typename Adapter = PassthroughAdapter<T>>
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.
template<typename T , typename Adapter = PassthroughAdapter<T>>
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.