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 <arith_uint256.h> | |||||
#include <rcu.h> | #include <rcu.h> | ||||
#include <util/system.h> | #include <util/system.h> | ||||
#include <array> | #include <array> | ||||
#include <atomic> | #include <atomic> | ||||
#include <cstdint> | #include <cstdint> | ||||
#include <memory> | #include <memory> | ||||
#include <type_traits> | #include <type_traits> | ||||
▲ Show 20 Lines • Show All 345 Lines • ▼ Show 20 Lines | public: | ||||
e.incrementRefCount(); | e.incrementRefCount(); | ||||
non_atomic_children_DO_NOT_USE[i] = e; | non_atomic_children_DO_NOT_USE[i] = e; | ||||
} | } | ||||
} | } | ||||
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 >> (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> void 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]); | func(&children[i]); | ||||
} | } | ||||
} | } | ||||
}; | }; | ||||
// 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."); | ||||
}; | }; | ||||
/** | |||||
* Facility for using an uint256 as a radix tree key. | |||||
*/ | |||||
struct Uint256KeyWrapper { | |||||
arith_uint256 base; | |||||
Uint256KeyWrapper(const uint256 &keyIn) : base(UintToArith256(keyIn)) {} | |||||
Uint256KeyWrapper(const base_uint<256> &keyIn) : base(keyIn) {} | |||||
Uint256KeyWrapper operator>>(uint32_t shift) const { return base >> shift; } | |||||
Uint256KeyWrapper operator&(const Uint256KeyWrapper &mask) const { | |||||
return base & mask.base; | |||||
} | |||||
operator size_t() const { return size_t(base.GetLow64()); } | |||||
}; | |||||
// The radix tree relies on sizeof to gather the bit length of the key | |||||
static_assert(sizeof(Uint256KeyWrapper) == 32, | |||||
"Uint256KeyWrapper key size should be 256 bits"); | |||||
#endif // BITCOIN_RADIX_H | #endif // BITCOIN_RADIX_H |