aboutsummaryrefslogtreecommitdiffstats
path: root/library/cpp/containers/comptrie/writeable_node.cpp
diff options
context:
space:
mode:
authorAnton Samokhvalov <pg83@yandex.ru>2022-02-10 16:45:15 +0300
committerDaniil Cherednik <dcherednik@yandex-team.ru>2022-02-10 16:45:15 +0300
commit72cb13b4aff9bc9cf22e49251bc8fd143f82538f (patch)
treeda2c34829458c7d4e74bdfbdf85dff449e9e7fb8 /library/cpp/containers/comptrie/writeable_node.cpp
parent778e51ba091dc39e7b7fcab2b9cf4dbedfb6f2b5 (diff)
downloadydb-72cb13b4aff9bc9cf22e49251bc8fd143f82538f.tar.gz
Restoring authorship annotation for Anton Samokhvalov <pg83@yandex.ru>. Commit 1 of 2.
Diffstat (limited to 'library/cpp/containers/comptrie/writeable_node.cpp')
-rw-r--r--library/cpp/containers/comptrie/writeable_node.cpp156
1 files changed, 78 insertions, 78 deletions
diff --git a/library/cpp/containers/comptrie/writeable_node.cpp b/library/cpp/containers/comptrie/writeable_node.cpp
index 404003dbbd..d0e986f99a 100644
--- a/library/cpp/containers/comptrie/writeable_node.cpp
+++ b/library/cpp/containers/comptrie/writeable_node.cpp
@@ -3,94 +3,94 @@
#include "comptrie_impl.h"
namespace NCompactTrie {
- TWriteableNode::TWriteableNode()
- : LeafPos(nullptr)
- , LeafLength(0)
- , ForwardOffset(NPOS)
- , LeftOffset(NPOS)
- , RightOffset(NPOS)
- , Label(0)
- {
- }
-
- static size_t GetOffsetFromEnd(const TNode& node, size_t absOffset) {
- return absOffset ? absOffset - node.GetOffset() - node.GetCoreLength() : NPOS;
- }
+ TWriteableNode::TWriteableNode()
+ : LeafPos(nullptr)
+ , LeafLength(0)
+ , ForwardOffset(NPOS)
+ , LeftOffset(NPOS)
+ , RightOffset(NPOS)
+ , Label(0)
+ {
+ }
- TWriteableNode::TWriteableNode(const TNode& node, const char* data)
- : LeafPos(node.IsFinal() ? data + node.GetLeafOffset() : nullptr)
- , LeafLength(node.GetLeafLength())
- , ForwardOffset(GetOffsetFromEnd(node, node.GetForwardOffset()))
- , LeftOffset(GetOffsetFromEnd(node, node.GetLeftOffset()))
- , RightOffset(GetOffsetFromEnd(node, node.GetRightOffset()))
- , Label(node.GetLabel())
- {
- }
+ static size_t GetOffsetFromEnd(const TNode& node, size_t absOffset) {
+ return absOffset ? absOffset - node.GetOffset() - node.GetCoreLength() : NPOS;
+ }
+
+ TWriteableNode::TWriteableNode(const TNode& node, const char* data)
+ : LeafPos(node.IsFinal() ? data + node.GetLeafOffset() : nullptr)
+ , LeafLength(node.GetLeafLength())
+ , ForwardOffset(GetOffsetFromEnd(node, node.GetForwardOffset()))
+ , LeftOffset(GetOffsetFromEnd(node, node.GetLeftOffset()))
+ , RightOffset(GetOffsetFromEnd(node, node.GetRightOffset()))
+ , Label(node.GetLabel())
+ {
+ }
- size_t TWriteableNode::Measure() const {
- size_t len = 2 + LeafLength;
- size_t fwdLen = 0;
- size_t lastLen = 0;
- size_t lastFwdLen = 0;
- // Now, increase all the offsets by the length and recalculate everything, until it converges
- do {
- lastLen = len;
- lastFwdLen = fwdLen;
+ size_t TWriteableNode::Measure() const {
+ size_t len = 2 + LeafLength;
+ size_t fwdLen = 0;
+ size_t lastLen = 0;
+ size_t lastFwdLen = 0;
+ // Now, increase all the offsets by the length and recalculate everything, until it converges
+ do {
+ lastLen = len;
+ lastFwdLen = fwdLen;
- len = 2 + LeafLength;
- len += MeasureOffset(LeftOffset != NPOS ? LeftOffset + lastLen : 0);
- len += MeasureOffset(RightOffset != NPOS ? RightOffset + lastLen : 0);
+ len = 2 + LeafLength;
+ len += MeasureOffset(LeftOffset != NPOS ? LeftOffset + lastLen : 0);
+ len += MeasureOffset(RightOffset != NPOS ? RightOffset + lastLen : 0);
+
+ // Relative forward offset of 0 means we don't need extra length for an epsilon link.
+ // But an epsilon link means we need an extra 1 for the flags and the forward offset is measured
+ // from the start of the epsilon link, not from the start of our node.
+ if (ForwardOffset != NPOS && ForwardOffset != 0) {
+ fwdLen = MeasureOffset(ForwardOffset + lastFwdLen) + 1;
+ len += fwdLen;
+ }
- // Relative forward offset of 0 means we don't need extra length for an epsilon link.
- // But an epsilon link means we need an extra 1 for the flags and the forward offset is measured
- // from the start of the epsilon link, not from the start of our node.
- if (ForwardOffset != NPOS && ForwardOffset != 0) {
- fwdLen = MeasureOffset(ForwardOffset + lastFwdLen) + 1;
- len += fwdLen;
- }
-
- } while (lastLen != len || lastFwdLen != fwdLen);
-
- return len;
- }
+ } while (lastLen != len || lastFwdLen != fwdLen);
- size_t TWriteableNode::Pack(char* buffer) const {
- const size_t length = Measure();
+ return len;
+ }
- char flags = 0;
- if (LeafPos) {
- flags |= MT_FINAL;
- }
- if (ForwardOffset != NPOS) {
- flags |= MT_NEXT;
- }
+ size_t TWriteableNode::Pack(char* buffer) const {
+ const size_t length = Measure();
- const size_t leftOffset = LeftOffset != NPOS ? LeftOffset + length : 0;
- const size_t rightOffset = RightOffset != NPOS ? RightOffset + length : 0;
- const size_t leftOffsetSize = MeasureOffset(leftOffset);
- const size_t rightOffsetSize = MeasureOffset(rightOffset);
- flags |= (leftOffsetSize << MT_LEFTSHIFT);
- flags |= (rightOffsetSize << MT_RIGHTSHIFT);
+ char flags = 0;
+ if (LeafPos) {
+ flags |= MT_FINAL;
+ }
+ if (ForwardOffset != NPOS) {
+ flags |= MT_NEXT;
+ }
- buffer[0] = flags;
- buffer[1] = Label;
- size_t usedLen = 2;
- usedLen += PackOffset(buffer + usedLen, leftOffset);
- usedLen += PackOffset(buffer + usedLen, rightOffset);
+ const size_t leftOffset = LeftOffset != NPOS ? LeftOffset + length : 0;
+ const size_t rightOffset = RightOffset != NPOS ? RightOffset + length : 0;
+ const size_t leftOffsetSize = MeasureOffset(leftOffset);
+ const size_t rightOffsetSize = MeasureOffset(rightOffset);
+ flags |= (leftOffsetSize << MT_LEFTSHIFT);
+ flags |= (rightOffsetSize << MT_RIGHTSHIFT);
- if (LeafPos && LeafLength) {
- memcpy(buffer + usedLen, LeafPos, LeafLength);
- usedLen += LeafLength;
- }
+ buffer[0] = flags;
+ buffer[1] = Label;
+ size_t usedLen = 2;
+ usedLen += PackOffset(buffer + usedLen, leftOffset);
+ usedLen += PackOffset(buffer + usedLen, rightOffset);
- if (ForwardOffset != NPOS && ForwardOffset != 0) {
- const size_t fwdOffset = ForwardOffset + length - usedLen;
- size_t fwdOffsetSize = MeasureOffset(fwdOffset);
- buffer[usedLen++] = (char)(fwdOffsetSize & MT_SIZEMASK);
- usedLen += PackOffset(buffer + usedLen, fwdOffset);
- }
- Y_ASSERT(usedLen == length);
- return usedLen;
+ if (LeafPos && LeafLength) {
+ memcpy(buffer + usedLen, LeafPos, LeafLength);
+ usedLen += LeafLength;
+ }
+
+ if (ForwardOffset != NPOS && ForwardOffset != 0) {
+ const size_t fwdOffset = ForwardOffset + length - usedLen;
+ size_t fwdOffsetSize = MeasureOffset(fwdOffset);
+ buffer[usedLen++] = (char)(fwdOffsetSize & MT_SIZEMASK);
+ usedLen += PackOffset(buffer + usedLen, fwdOffset);
+ }
+ Y_ASSERT(usedLen == length);
+ return usedLen;
}
}