Changeset View
Changeset View
Standalone View
Standalone View
src/radix.h
Show All 27 Lines | |||||
* Reads walk the tree using sequential atomic loads, and insertions are done | * Reads walk the tree using sequential atomic loads, and insertions are done | ||||
* using CAS, which ensures both can be executed lock free. Removing any | * 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 | * 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 | * 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 | * 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 | * to speed before destroying anything. It is therefore crucial that the lock be | ||||
* taken before reading anything in the tree. | * taken before reading anything in the tree. | ||||
*/ | */ | ||||
template <typename T> struct RadixTree { | template <typename T> struct Uint256RadixKey { | ||||
private: | private: | ||||
static const int BITS = 4; | static const int BITS = 4; | ||||
static const int MASK = (1 << BITS) - 1; | static const int MASK = (1 << BITS) - 1; | ||||
static const size_t CHILD_PER_LEVEL = 1 << BITS; | static const size_t CHILD_PER_LEVEL = 1 << BITS; | ||||
using KeyType = typename std::remove_reference<decltype( | using KeyType = typename std::remove_reference<decltype( | ||||
std::declval<T &>().getId())>::type; | std::declval<T &>().getId())>::type; | ||||
static const size_t KEY_BITS = 8 * sizeof(KeyType); | static const size_t KEY_BITS = 8 * sizeof(KeyType); | ||||
static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS; | static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS; | ||||
struct RadixElement; | struct RadixElement; | ||||
struct RadixNode; | struct RadixNode; | ||||
std::atomic<RadixElement> root; | std::atomic<RadixElement> root; | ||||
public: | public: | ||||
RadixTree() : root(RadixElement()) {} | Uint256RadixKey() : root(RadixElement()) {} | ||||
~RadixTree() { root.load().decrementRefCount(); } | ~Uint256RadixKey() { root.load().decrementRefCount(); } | ||||
/** | /** | ||||
* Copy semantic. | * Copy semantic. | ||||
*/ | */ | ||||
RadixTree(const RadixTree &src) : RadixTree() { | Uint256RadixKey(const Uint256RadixKey &src) : Uint256RadixKey() { | ||||
{ | { | ||||
RCULock lock; | RCULock lock; | ||||
RadixElement e = src.root.load(); | RadixElement e = src.root.load(); | ||||
e.incrementRefCount(); | e.incrementRefCount(); | ||||
root = e; | root = e; | ||||
} | } | ||||
// Make sure we the writes in the tree are behind us so | // Make sure we the writes in the tree are behind us so | ||||
// this copy won't mutate behind our back. | // this copy won't mutate behind our back. | ||||
RCULock::synchronize(); | RCULock::synchronize(); | ||||
} | } | ||||
RadixTree &operator=(const RadixTree &rhs) { | Uint256RadixKey &operator=(const Uint256RadixKey &rhs) { | ||||
{ | { | ||||
RCULock lock; | RCULock lock; | ||||
RadixElement e = rhs.root.load(); | RadixElement e = rhs.root.load(); | ||||
e.incrementRefCount(); | e.incrementRefCount(); | ||||
root.load().decrementRefCount(); | root.load().decrementRefCount(); | ||||
root = e; | root = e; | ||||
} | } | ||||
// Make sure we the writes in the tree are behind us so | // Make sure we the writes in the tree are behind us so | ||||
// this copy won't mutate behind our back. | // this copy won't mutate behind our back. | ||||
RCULock::synchronize(); | RCULock::synchronize(); | ||||
return *this; | return *this; | ||||
} | } | ||||
/** | /** | ||||
* Move semantic. | * Move semantic. | ||||
*/ | */ | ||||
RadixTree(RadixTree &&src) : RadixTree() { *this = std::move(src); } | Uint256RadixKey(Uint256RadixKey &&src) : Uint256RadixKey() { | ||||
RadixTree &operator=(RadixTree &&rhs) { | *this = std::move(src); | ||||
} | |||||
Uint256RadixKey &operator=(Uint256RadixKey &&rhs) { | |||||
{ | { | ||||
RCULock lock; | RCULock lock; | ||||
RadixElement e = rhs.root.load(); | RadixElement e = rhs.root.load(); | ||||
rhs.root = root.load(); | rhs.root = root.load(); | ||||
root = e; | root = e; | ||||
} | } | ||||
return *this; | return *this; | ||||
Show All 28 Lines | RCUPtr<T> get(const KeyType &key) { | ||||
return RCUPtr<T>(); | return RCUPtr<T>(); | ||||
} | } | ||||
// The leaf is non-null and the keys match. We have our guy. | // The leaf is non-null and the keys match. We have our guy. | ||||
return RCUPtr<T>::copy(leaf); | return RCUPtr<T>::copy(leaf); | ||||
} | } | ||||
RCUPtr<const T> get(const KeyType &key) const { | RCUPtr<const T> get(const KeyType &key) const { | ||||
T const *ptr = const_cast<RadixTree *>(this)->get(key).release(); | T const *ptr = const_cast<Uint256RadixKey *>(this)->get(key).release(); | ||||
return RCUPtr<const T>::acquire(ptr); | return RCUPtr<const T>::acquire(ptr); | ||||
} | } | ||||
template <typename Callable> bool forEachLeaf(Callable &&func) const { | template <typename Callable> bool forEachLeaf(Callable &&func) const { | ||||
RCULock lock; | RCULock lock; | ||||
return forEachLeaf(root.load(), std::move(func)); | return forEachLeaf(root.load(), std::move(func)); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 269 Lines • Show Last 20 Lines |