1#include <xrpl/shamap/SHAMapInnerNode.h>
3#include <xrpl/basics/IntrusivePointer.h>
4#include <xrpl/basics/IntrusivePointer.ipp>
5#include <xrpl/basics/SHAMapHash.h>
6#include <xrpl/basics/Slice.h>
7#include <xrpl/basics/base_uint.h>
8#include <xrpl/basics/contract.h>
9#include <xrpl/basics/spinlock.h>
10#include <xrpl/beast/utility/instrumentation.h>
11#include <xrpl/protocol/HashPrefix.h>
12#include <xrpl/protocol/Serializer.h>
13#include <xrpl/protocol/digest.h>
14#include <xrpl/shamap/SHAMapNodeID.h>
15#include <xrpl/shamap/SHAMapTreeNode.h>
16#include <xrpl/shamap/detail/TaggedPointer.h>
17#include <xrpl/shamap/detail/TaggedPointer.ipp>
82 p->fullBelowGen_.store(
83 fullBelowGen_.load(std::memory_order_relaxed), std::memory_order_relaxed);
89 std::tie(std::ignore, cloneHashes, cloneChildren) =
90 p->hashesAndChildren_.getHashesAndChildren();
95 auto cloneChildIndex = 0u;
97 cloneHashes[cloneChildIndex++] = thisHashes[indexNum];
103 [&](
auto branchNum,
auto indexNum) { cloneHashes[branchNum] = thisHashes[indexNum]; });
111 auto cloneChildIndex = 0u;
113 cloneChildren[cloneChildIndex++] = thisChildren[indexNum];
119 cloneChildren[branchNum] = thisChildren[indexNum];
137 auto hashes = ret->hashesAndChildren_.getHashes();
143 if (hashes[i].isNonZero())
144 ret->isBranch_ |= (1u << i);
147 ret->resizeChildArrays(ret->getBranchCount());
168 if (
auto const s = data.size(); (s % kChunkSize != 0) || (s > kChunkSize *
kBranchFactor))
175 auto hashes = ret->hashesAndChildren_.getHashes();
180 auto const pos = si.
get8();
185 hashes[pos].asUInt256() = hash;
187 if (hashes[pos].isNonZero())
188 ret->isBranch_ |= (1u << pos);
191 ret->resizeChildArrays(ret->getBranchCount());
219 if (
auto p = children[indexNum].
get())
220 hashes[indexNum] = p->getHash();
228 XRPL_ASSERT(!
isEmpty(),
"xrpl::SHAMapInnerNode::serializeForWire : is non-empty");
251 XRPL_ASSERT(!
isEmpty(),
"xrpl::SHAMapInnerNode::serializeWithPrefix : is non-empty");
275 XRPL_ASSERT(branch <
kBranchFactor,
"xrpl::SHAMapInnerNode::setChild : valid branch input");
276 XRPL_ASSERT(
cowid_,
"xrpl::SHAMapInnerNode::setChild : nonzero cowid");
277 XRPL_ASSERT(child.get() !=
this,
"xrpl::SHAMapInnerNode::setChild : valid child input");
279 auto const dstIsBranch = [&] {
288 auto const dstToAllocate =
popcnt16(dstIsBranch);
301 hashes[childIndex].zero();
302 children[childIndex] = std::move(child);
309 "xrpl::SHAMapInnerNode::setChild : maximum branch count");
316 XRPL_ASSERT(branch <
kBranchFactor,
"xrpl::SHAMapInnerNode::shareChild : valid branch input");
317 XRPL_ASSERT(
cowid_,
"xrpl::SHAMapInnerNode::shareChild : nonzero cowid");
318 XRPL_ASSERT(child,
"xrpl::SHAMapInnerNode::shareChild : non-null child input");
319 XRPL_ASSERT(child.get() !=
this,
"xrpl::SHAMapInnerNode::shareChild : valid child input");
322 !
isEmptyBranch(branch),
"xrpl::SHAMapInnerNode::shareChild : non-empty branch input");
331 branch <
kBranchFactor,
"xrpl::SHAMapInnerNode::getChildPointer : valid branch input");
333 !
isEmptyBranch(branch),
"xrpl::SHAMapInnerNode::getChildPointer : non-empty branch input");
346 XRPL_ASSERT(branch <
kBranchFactor,
"xrpl::SHAMapInnerNode::getChild : valid branch input");
347 XRPL_ASSERT(!
isEmptyBranch(branch),
"xrpl::SHAMapInnerNode::getChild : non-empty branch input");
360 XRPL_ASSERT(branch <
kBranchFactor,
"xrpl::SHAMapInnerNode::getChildHash : valid branch input");
364 return kZeroShaMapHash;
371 branch <
kBranchFactor,
"xrpl::SHAMapInnerNode::canonicalizeChild : valid branch input");
372 XRPL_ASSERT(node !=
nullptr,
"xrpl::SHAMapInnerNode::canonicalizeChild : valid node input");
375 "xrpl::SHAMapInnerNode::canonicalizeChild : non-empty branch input");
376 auto const childIndex =
380 node->getHash() == hashes[childIndex],
381 "xrpl::SHAMapInnerNode::canonicalizeChild : node and branch inputs "
387 if (children[childIndex])
390 node = children[childIndex];
395 children[childIndex] = node;
403 [[maybe_unused]]
unsigned count = 0;
409 for (
auto i = 0u; i < branchCount; ++i)
412 hashes[i].isNonZero(),
413 "xrpl::SHAMapInnerNode::invariants : nonzero hash in branch");
414 if (children[i] !=
nullptr)
415 children[i]->invariants();
423 if (hashes[i].isNonZero())
427 "xrpl::SHAMapInnerNode::invariants : valid branch when "
429 if (children[i] !=
nullptr)
430 children[i]->invariants();
437 "xrpl::SHAMapInnerNode::invariants : valid branch when "
445 XRPL_ASSERT(
hash_.isNonZero(),
"xrpl::SHAMapInnerNode::invariants : nonzero hash");
446 XRPL_ASSERT(count >= 1,
"xrpl::SHAMapInnerNode::invariants : minimum count");
449 (count == 0) ?
hash_.isZero() :
hash_.isNonZero(),
450 "xrpl::SHAMapInnerNode::invariants : hash and count do match");
static constexpr std::size_t kBytes
Classes to handle arrays of spinlocks packed into a single atomic integer:
UInt256 const & asUInt256() const
std::optional< unsigned int > getChildIndex(unsigned int i) const
Get the child's index inside the hashes or children array (stored in hashesAndChildren_.
void serializeWithPrefix(Serializer &) const override
Serialize the node in a format appropriate for hashing.
void updateHash() override
Recalculate the hash of this node.
TaggedPointer hashesAndChildren_
Opaque type that contains the hashes array (array of type SHAMapHash) and the children array (array o...
SHAMapHash const & getChildHash(unsigned int branch) const
unsigned int getBranchCount() const
static constexpr unsigned int kBranchFactor
Each inner node has 16 children (the 'radix tree' part of the map).
~SHAMapInnerNode() override
void updateHashDeep()
Recalculate the hash of all children and this node.
void iterNonEmptyChildIndexes(F &&f) const
Call the f callback for all non-empty branches.
SHAMapTreeNodePtr clone(std::uint32_t cowid) const override
Make a copy of this node, setting the owner.
void shareChild(unsigned int branch, SHAMapTreeNodePtr const &child)
static SHAMapTreeNodePtr makeCompressedInner(Slice data)
std::string getString(SHAMapNodeID const &) const override
SHAMapInnerNode(std::uint32_t cowid, std::uint8_t numAllocatedChildren=2)
void iterChildren(F &&f) const
Call the f callback for all 16 (branchFactor) branches - even if the branch is empty.
void resizeChildArrays(std::uint8_t toAllocate)
Convert arrays stored in hashesAndChildren_ so they can store the requested number of children.
void invariants(bool isRoot=false) const override
std::atomic< std::uint32_t > fullBelowGen_
Written from more than one thread, since canonicalization shares a node between maps and a walk can r...
void setChild(unsigned int branch, SHAMapTreeNodePtr child)
void partialDestructor() override
SHAMapTreeNodePtr getChild(unsigned int branch)
std::atomic< std::uint16_t > lock_
A bitlock for the children of this node, with one bit per child.
SHAMapTreeNode * getChildPointer(unsigned int branch)
void serializeForWire(Serializer &) const override
Serialize the node in a format appropriate for sending over the wire.
SHAMapTreeNodePtr canonicalizeChild(unsigned int branch, SHAMapTreeNodePtr node)
static SHAMapTreeNodePtr makeFullInner(Slice data, SHAMapHash const &hash, bool hashValid)
bool isEmptyBranch(unsigned int branch) const
Identifies a node inside a SHAMap.
std::uint32_t cowid_
Determines the owning SHAMap, if any.
SHAMapTreeNode(std::uint32_t cowid) noexcept
Construct a node.
virtual std::string getString(SHAMapNodeID const &) const
BaseUInt< Bits, Tag > getBitString()
bool empty() const noexcept
int addBitString(BaseUInt< Bits, Tag > const &v)
int add8(unsigned char byteValue)
void reset()
Set the pointer to null, decrement the strong count, and run the appropriate release action.
An immutable linear range of bytes.
A spinlock implemented on top of an atomic integer.
TaggedPointer is a combination of a pointer and a mask stored in the lowest two bits.
std::uint32_t cowid() const
Returns the SHAMap that owns this node.
void hash_append(Hasher &h, T const &t) noexcept
Logically concatenate input data to a Hasher.
SharedPtr< T > makeShared(A &&... args)
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
intr_ptr::SharedPtr< SHAMapTreeNode > SHAMapTreeNodePtr
T get(Section const §ion, std::string const &name, T const &defaultValue=T{})
Retrieve a key/value pair from a section.
static constexpr unsigned char const kWireTypeCompressedInner
std::string to_string(BaseUInt< Bits, Tag > const &a)
unsigned int popcnt16(std::uint16_t a)
detail::BasicSha512HalfHasher< false > Sha512HalfHasher
void hash_append(Hasher &h, Slice const &v)
@ InnerNode
inner node in V1 tree
static constexpr unsigned char const kWireTypeInner
XRPL_NO_SANITIZE_ADDRESS void Throw(Args &&... args)