Changeset View
Changeset View
Standalone View
Standalone View
src/radix.h
Show First 20 Lines • Show All 50 Lines • ▼ Show 20 Lines | private: | ||||
struct RadixElement; | struct RadixElement; | ||||
struct RadixNode; | struct RadixNode; | ||||
std::atomic<RadixElement> root; | std::atomic<RadixElement> root; | ||||
public: | public: | ||||
RadixTree() : root(RadixElement()) {} | RadixTree() : root(RadixElement()) {} | ||||
~RadixTree() { root.load().release(); } | |||||
/** | /** | ||||
* Insert a value into the tree. | * Insert a value into the tree. | ||||
* Returns true if the value was inserted, false if it was already present. | * Returns true if the value was inserted, false if it was already present. | ||||
*/ | */ | ||||
bool insert(const RCUPtr<T> &value) { | bool insert(const RCUPtr<T> &value) { | ||||
return insert(value->getId(), value); | return insert(value->getId(), value); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 107 Lines • ▼ Show 20 Lines | bool insert(const K &key, RCUPtr<T> value) { | ||||
// There is an element there, but it isn't a subtree. We need to | // There is an element there, but it isn't a subtree. We need to | ||||
// convert it into a subtree and resume insertion into that subtree. | // convert it into a subtree and resume insertion into that subtree. | ||||
std::unique_ptr<RadixNode> newChild = | std::unique_ptr<RadixNode> newChild = | ||||
MakeUnique<RadixNode>(level, leafKey, e); | MakeUnique<RadixNode>(level, leafKey, e); | ||||
if (eptr->compare_exchange_strong(e, | if (eptr->compare_exchange_strong(e, | ||||
RadixElement(newChild.get()))) { | RadixElement(newChild.get()))) { | ||||
// We have a subtree, resume normal operations from there. | // We have a subtree, resume normal operations from there. | ||||
newChild.release(); | newChild.release(); | ||||
} else { | |||||
// We failed to insert our subtree, clean it before it is freed. | |||||
newChild->get(level, leafKey)->store(RadixElement()); | |||||
} | } | ||||
} | } | ||||
} | } | ||||
struct RadixElement { | struct RadixElement { | ||||
private: | private: | ||||
union { | union { | ||||
RadixNode *node; | RadixNode *node; | ||||
T *leaf; | T *leaf; | ||||
uintptr_t raw; | uintptr_t raw; | ||||
}; | }; | ||||
static const uintptr_t DISCRIMINANT = 0x01; | static const uintptr_t DISCRIMINANT = 0x01; | ||||
bool getDiscriminent() const { return (raw & DISCRIMINANT) != 0; } | bool getDiscriminent() const { return (raw & DISCRIMINANT) != 0; } | ||||
public: | public: | ||||
explicit RadixElement() : raw(DISCRIMINANT) {} | explicit RadixElement() : raw(DISCRIMINANT) {} | ||||
explicit RadixElement(RadixNode *nodeIn) : node(nodeIn) {} | explicit RadixElement(RadixNode *nodeIn) : node(nodeIn) {} | ||||
explicit RadixElement(T *leafIn) : leaf(leafIn) { raw |= DISCRIMINANT; } | explicit RadixElement(T *leafIn) : leaf(leafIn) { raw |= DISCRIMINANT; } | ||||
/** | /** | ||||
* RadixElement is designed to be a dumb wrapper. This allows any | |||||
* container to release what is held by the RadixElement. | |||||
*/ | |||||
void release() { | |||||
if (isNode()) { | |||||
RadixNode *ptr = getNode(); | |||||
RCUPtr<RadixNode>::acquire(ptr); | |||||
} else { | |||||
T *ptr = getLeaf(); | |||||
RCUPtr<T>::acquire(ptr); | |||||
} | |||||
} | |||||
/** | |||||
* Node features. | * Node features. | ||||
*/ | */ | ||||
bool isNode() const { return !getDiscriminent(); } | bool isNode() const { return !getDiscriminent(); } | ||||
RadixNode *getNode() { | RadixNode *getNode() { | ||||
assert(isNode()); | assert(isNode()); | ||||
return node; | return node; | ||||
} | } | ||||
Show All 14 Lines | public: | ||||
} | } | ||||
const T *getLeaf() const { | const T *getLeaf() const { | ||||
assert(isLeaf()); | assert(isLeaf()); | ||||
return const_cast<RadixElement *>(this)->getLeaf(); | return const_cast<RadixElement *>(this)->getLeaf(); | ||||
} | } | ||||
}; | }; | ||||
struct RadixNode { | struct RadixNode : public boost::noncopyable { | ||||
IMPLEMENT_RCU_REFCOUNT(uint64_t); | |||||
private: | private: | ||||
union { | union { | ||||
std::array<std::atomic<RadixElement>, CHILD_PER_LEVEL> childs; | std::array<std::atomic<RadixElement>, CHILD_PER_LEVEL> childs; | ||||
std::array<RadixElement, CHILD_PER_LEVEL> | std::array<RadixElement, CHILD_PER_LEVEL> | ||||
non_atomic_childs_DO_NOT_USE; | non_atomic_childs_DO_NOT_USE; | ||||
}; | }; | ||||
public: | public: | ||||
RadixNode(uint32_t level, const K &key, RadixElement e) | RadixNode(uint32_t level, const K &key, RadixElement e) | ||||
: non_atomic_childs_DO_NOT_USE() { | : non_atomic_childs_DO_NOT_USE() { | ||||
get(level, key)->store(e); | get(level, key)->store(e); | ||||
} | } | ||||
~RadixNode() { | |||||
for (RadixElement e : non_atomic_childs_DO_NOT_USE) { | |||||
e.release(); | |||||
} | |||||
} | |||||
std::atomic<RadixElement> *get(uint32_t level, const K &key) { | std::atomic<RadixElement> *get(uint32_t level, const K &key) { | ||||
return &childs[(key >> (level * BITS)) & MASK]; | return &childs[(key >> (level * BITS)) & MASK]; | ||||
} | } | ||||
}; | }; | ||||
// 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."); | ||||
}; | }; | ||||
#endif // BITCOIN_RADIX_H | #endif // BITCOIN_RADIX_H |