Changeset View
Changeset View
Standalone View
Standalone View
src/radix.h
Show First 20 Lines • Show All 84 Lines • ▼ Show 20 Lines | T *get(const K &key) { | ||||
// 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 leaf; | return leaf; | ||||
} | } | ||||
const T *get(const K &key) const { | const T *get(const K &key) const { | ||||
return const_cast<RadixTree *>(this)->get(key); | return const_cast<RadixTree *>(this)->get(key); | ||||
} | } | ||||
/** | |||||
* Remove an element from the tree. | |||||
* Returns true if the element was removed from the tree, false if the | |||||
* element wasn't found in the tree. | |||||
*/ | |||||
bool remove(const K &key) { | |||||
uint32_t level = TOP_LEVEL; | |||||
RCULock lock; | |||||
std::atomic<RadixElement> *eptr = &root; | |||||
RadixElement e = eptr->load(); | |||||
// Walk down the tree until we find a leaf for our node. | |||||
while (e.isNode()) { | |||||
Node: | |||||
eptr = e.getNode()->get(level--, key); | |||||
e = eptr->load(); | |||||
} | |||||
T *leaf = e.getLeaf(); | |||||
if (leaf == nullptr || leaf->getId() != key) { | |||||
// We failed to find the proper element. | |||||
return false; | |||||
} | |||||
// We have the proper element, try to delete it. | |||||
if (eptr->compare_exchange_strong(e, RadixElement())) { | |||||
return true; | |||||
} | |||||
// The element was replaced, either by a subtree or another element. | |||||
if (e.isNode()) { | |||||
goto Node; | |||||
} | |||||
// The element in the slot is not the one we are looking for. | |||||
return false; | |||||
} | |||||
private: | private: | ||||
bool insert(const K &key, T *value) { | bool insert(const K &key, T *value) { | ||||
uint32_t level = TOP_LEVEL; | uint32_t level = TOP_LEVEL; | ||||
RCULock lock; | RCULock lock; | ||||
std::atomic<RadixElement> *eptr = &root; | std::atomic<RadixElement> *eptr = &root; | ||||
while (true) { | while (true) { | ||||
▲ Show 20 Lines • Show All 114 Lines • Show Last 20 Lines |