xrpld
Loading...
Searching...
No Matches
SHAMapInnerNode.h
1#pragma once
2
3#include <xrpl/basics/CountedObject.h>
4#include <xrpl/basics/SHAMapHash.h>
5#include <xrpl/basics/Slice.h>
6#include <xrpl/protocol/Serializer.h>
7#include <xrpl/shamap/SHAMapNodeID.h>
8#include <xrpl/shamap/SHAMapTreeNode.h>
9#include <xrpl/shamap/detail/TaggedPointer.h>
10
11#include <atomic>
12#include <cstdint>
13#include <optional>
14#include <string>
15
16namespace xrpl {
17
18class SHAMapInnerNode final : public SHAMapTreeNode, public CountedObject<SHAMapInnerNode>
19{
20public:
24 static constexpr unsigned int kBranchFactor = 16;
25
26private:
33
34 // Pin that wrapping fullBelowGen_ in an atomic keeps the packed layout, and that the load
35 // isFullBelow() does once per node of every walk stays lock-free.
37 static_assert(sizeof(std::atomic<std::uint32_t>) == sizeof(std::uint32_t));
38 static_assert(alignof(std::atomic<std::uint32_t>) == alignof(std::uint32_t));
39
48
53
65 void
67
78 getChildIndex(unsigned int i) const;
79
87 template <class F>
88 void
89 iterChildren(F&& f) const;
90
99 template <class F>
100 void
101 iterNonEmptyChildIndexes(F&& f) const;
102
103public:
104 explicit SHAMapInnerNode(std::uint32_t cowid, std::uint8_t numAllocatedChildren = 2);
105
108 operator=(SHAMapInnerNode const&) = delete;
110
111 // Needed to support intrusive weak pointers
112 void
113 partialDestructor() override;
114
116 clone(std::uint32_t cowid) const override;
117
119 getType() const override
120 {
122 }
123
124 bool
125 isLeaf() const override
126 {
127 return false;
128 }
129
130 bool
131 isInner() const override
132 {
133 return true;
134 }
135
136 bool
137 isEmpty() const;
138
139 bool
140 isEmptyBranch(unsigned int branch) const;
141
142 unsigned int
143 getBranchCount() const;
144
145 SHAMapHash const&
146 getChildHash(unsigned int branch) const;
147
148 void
149 setChild(unsigned int branch, SHAMapTreeNodePtr child);
150
151 void
152 shareChild(unsigned int branch, SHAMapTreeNodePtr const& child);
153
155 getChildPointer(unsigned int branch);
156
158 getChild(unsigned int branch);
159
161 canonicalizeChild(unsigned int branch, SHAMapTreeNodePtr node);
162
163 // sync functions
164 bool
165 isFullBelow(std::uint32_t generation) const;
166
167 void
169
170 void
171 updateHash() override;
172
176 void
178
179 void
180 serializeForWire(Serializer&) const override;
181
182 void
183 serializeWithPrefix(Serializer&) const override;
184
186 getString(SHAMapNodeID const&) const override;
187
188 void
189 invariants(bool isRoot = false) const override;
190
191 static SHAMapTreeNodePtr
192 makeFullInner(Slice data, SHAMapHash const& hash, bool hashValid);
193
194 static SHAMapTreeNodePtr
196};
197
198inline bool
200{
201 return isBranch_ == 0;
202}
203
204inline bool
205SHAMapInnerNode::isEmptyBranch(unsigned int branch) const
206{
207 return (isBranch_ & (1u << branch)) == 0u;
208}
209
210inline unsigned int
215
216inline bool
218{
219 return fullBelowGen_.load(std::memory_order_relaxed) == generation;
220}
221
222inline void
224{
225 fullBelowGen_.store(gen, std::memory_order_relaxed);
226}
227
228} // namespace xrpl
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.
bool isFullBelow(std::uint32_t generation) const
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.
SHAMapNodeType getType() const override
Determines the type of node.
void setFullBelowGen(std::uint32_t gen)
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)
bool isInner() const override
Determines if this is an inner node.
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.
bool isLeaf() const override
Determines if this is a leaf node.
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)
SHAMapInnerNode & operator=(SHAMapInnerNode const &)=delete
SHAMapInnerNode(SHAMapInnerNode const &)=delete
bool isEmptyBranch(unsigned int branch) const
Identifies a node inside a SHAMap.
SHAMapTreeNode(std::uint32_t cowid) noexcept
Construct a node.
An immutable linear range of bytes.
Definition Slice.h:28
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.
Use hash_* containers for keys that do not need a cryptographically secure hashing algorithm.
Definition algorithm.h:5
intr_ptr::SharedPtr< SHAMapTreeNode > SHAMapTreeNodePtr
unsigned int popcnt16(std::uint16_t a)