Changeset View
Changeset View
Standalone View
Standalone View
src/radix.h
Show First 20 Lines • Show All 132 Lines • ▼ Show 20 Lines | RCUPtr<T> get(const KeyType &key) { | ||||
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<RadixTree *>(this)->get(key).release(); | ||||
return RCUPtr<const T>::acquire(ptr); | return RCUPtr<const T>::acquire(ptr); | ||||
} | } | ||||
template <typename Callable> void forEachLeaf(Callable &&func) const { | template <typename Callable> bool forEachLeaf(Callable &&func) const { | ||||
RCULock lock; | RCULock lock; | ||||
forEachLeaf(root.load(), std::move(func)); | return forEachLeaf(root.load(), std::move(func)); | ||||
} | } | ||||
#define SEEK_LEAF_LOOP() \ | #define SEEK_LEAF_LOOP() \ | ||||
RadixElement e = eptr->load(); \ | RadixElement e = eptr->load(); \ | ||||
\ | \ | ||||
/* Walk down the tree until we find a leaf for our node. */ \ | /* Walk down the tree until we find a leaf for our node. */ \ | ||||
do { \ | do { \ | ||||
while (e.isNode()) { \ | while (e.isNode()) { \ | ||||
▲ Show 20 Lines • Show All 93 Lines • ▼ Show 20 Lines | bool insert(const KeyType &key, RCUPtr<T> value) { | ||||
newChild->get(level, leafKey)->store(RadixElement()); | newChild->get(level, leafKey)->store(RadixElement()); | ||||
} | } | ||||
} | } | ||||
} | } | ||||
#undef SEEK_LEAF_LOOP | #undef SEEK_LEAF_LOOP | ||||
template <typename Callable> | template <typename Callable> | ||||
void forEachLeaf(RadixElement e, Callable &&func) const { | bool forEachLeaf(RadixElement e, Callable &&func) const { | ||||
if (e.isNode()) { | if (e.isLeaf()) { | ||||
e.getNode()->forEachChild( | |||||
[&](const std::atomic<RadixElement> *pElement) { | |||||
forEachLeaf(pElement->load(), func); | |||||
}); | |||||
return; | |||||
} | |||||
T *leaf = e.getLeaf(); | T *leaf = e.getLeaf(); | ||||
if (leaf != nullptr) { | if (leaf != nullptr) { | ||||
func(RCUPtr<T>::copy(leaf)); | return func(RCUPtr<T>::copy(leaf)); | ||||
} | |||||
return true; | |||||
} | } | ||||
return e.getNode()->forEachChild( | |||||
[&](const std::atomic<RadixElement> *pElement) { | |||||
return forEachLeaf(pElement->load(), func); | |||||
}); | |||||
} | } | ||||
struct RadixElement { | struct RadixElement { | ||||
private: | private: | ||||
union { | union { | ||||
RadixNode *node; | RadixNode *node; | ||||
T *leaf; | T *leaf; | ||||
uintptr_t raw; | uintptr_t raw; | ||||
▲ Show 20 Lines • Show All 95 Lines • ▼ Show 20 Lines | public: | ||||
RadixNode &operator=(const RadixNode &) = delete; | RadixNode &operator=(const RadixNode &) = delete; | ||||
std::atomic<RadixElement> *get(uint32_t level, const KeyType &key) { | std::atomic<RadixElement> *get(uint32_t level, const KeyType &key) { | ||||
return &children[(key >> uint32_t(level * BITS)) & MASK]; | return &children[(key >> uint32_t(level * BITS)) & MASK]; | ||||
} | } | ||||
bool isShared() const { return refcount > 0; } | bool isShared() const { return refcount > 0; } | ||||
template <typename Callable> void forEachChild(Callable &&func) const { | template <typename Callable> bool forEachChild(Callable &&func) const { | ||||
for (size_t i = 0; i < CHILD_PER_LEVEL; i++) { | for (size_t i = 0; i < CHILD_PER_LEVEL; i++) { | ||||
func(&children[i]); | if (!func(&children[i])) { | ||||
return false; | |||||
} | |||||
} | } | ||||
return true; | |||||
} | } | ||||
}; | }; | ||||
// Make sure the alignment works for T and RadixElement. | // Make sure the alignment works for T and RadixElement. | ||||
static_assert(alignof(T) > 1, "T's alignment must be 2 or more."); | static_assert(alignof(T) > 1, "T's alignment must be 2 or more."); | ||||
static_assert(alignof(RadixNode) > 1, | static_assert(alignof(RadixNode) > 1, | ||||
"RadixNode alignment must be 2 or more."); | "RadixNode alignment must be 2 or more."); | ||||
}; | }; | ||||
Show All 22 Lines |