Changeset View
Changeset View
Standalone View
Standalone View
src/radix.h
// Copyright (c) 2019 The Bitcoin developers | // Copyright (c) 2019 The Bitcoin developers | ||||
// Distributed under the MIT software license, see the accompanying | // Distributed under the MIT software license, see the accompanying | ||||
// file COPYING or http://www.opensource.org/licenses/mit-license.php. | // file COPYING or http://www.opensource.org/licenses/mit-license.php. | ||||
#ifndef BITCOIN_RADIX_H | #ifndef BITCOIN_RADIX_H | ||||
#define BITCOIN_RADIX_H | #define BITCOIN_RADIX_H | ||||
#include <rcu.h> | #include <rcu.h> | ||||
#include <util/system.h> | #include <util/system.h> | ||||
#include <boost/noncopyable.hpp> | |||||
#include <array> | #include <array> | ||||
#include <atomic> | #include <atomic> | ||||
#include <cstdint> | #include <cstdint> | ||||
#include <memory> | #include <memory> | ||||
#include <type_traits> | #include <type_traits> | ||||
/** | /** | ||||
* This is a radix tree storing values identified by a unique key. | * This is a radix tree storing values identified by a unique key. | ||||
Show All 12 Lines | |||||
* 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. | ||||
* | * | ||||
* It is not possible to delete anything from the tree at this time. The tree | * It is not possible to delete anything from the tree at this time. The tree | ||||
* itself cannot be destroyed and will leak memory instead of cleaning up after | * itself cannot be destroyed and will leak memory instead of cleaning up after | ||||
* itself. This obviously needs to be fixed in subsequent revisions. | * itself. This obviously needs to be fixed in subsequent revisions. | ||||
*/ | */ | ||||
template <typename T> struct RadixTree : public boost::noncopyable { | template <typename T> struct RadixTree { | ||||
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; | ||||
typedef typename std::remove_reference<decltype( | typedef typename std::remove_reference<decltype( | ||||
std::declval<T &>().getId())>::type K; | std::declval<T &>().getId())>::type K; | ||||
static const size_t KEY_BITS = 8 * sizeof(K); | static const size_t KEY_BITS = 8 * sizeof(K); | ||||
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()) {} | RadixTree() : root(RadixElement()) {} | ||||
~RadixTree() { root.load().release(); } | ~RadixTree() { root.load().release(); } | ||||
RadixTree(const RadixTree &) = delete; | |||||
RadixTree &operator=(const RadixTree &) = delete; | |||||
/** | /** | ||||
* 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 175 Lines • ▼ Show 20 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 : public boost::noncopyable { | struct RadixNode { | ||||
IMPLEMENT_RCU_REFCOUNT(uint64_t); | IMPLEMENT_RCU_REFCOUNT(uint64_t); | ||||
private: | private: | ||||
union { | union { | ||||
std::array<std::atomic<RadixElement>, CHILD_PER_LEVEL> children; | std::array<std::atomic<RadixElement>, CHILD_PER_LEVEL> children; | ||||
std::array<RadixElement, CHILD_PER_LEVEL> | std::array<RadixElement, CHILD_PER_LEVEL> | ||||
non_atomic_children_DO_NOT_USE; | non_atomic_children_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_children_DO_NOT_USE() { | : non_atomic_children_DO_NOT_USE() { | ||||
get(level, key)->store(e); | get(level, key)->store(e); | ||||
} | } | ||||
~RadixNode() { | ~RadixNode() { | ||||
for (RadixElement e : non_atomic_children_DO_NOT_USE) { | for (RadixElement e : non_atomic_children_DO_NOT_USE) { | ||||
e.release(); | e.release(); | ||||
} | } | ||||
} | } | ||||
RadixNode(const RadixNode &) = delete; | |||||
RadixNode &operator=(const RadixNode &) = delete; | |||||
std::atomic<RadixElement> *get(uint32_t level, const K &key) { | std::atomic<RadixElement> *get(uint32_t level, const K &key) { | ||||
return &children[(key >> (level * BITS)) & MASK]; | return &children[(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 |