diff options
author | Anton Samokhvalov <pg83@yandex.ru> | 2022-02-10 16:45:15 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:15 +0300 |
commit | 72cb13b4aff9bc9cf22e49251bc8fd143f82538f (patch) | |
tree | da2c34829458c7d4e74bdfbdf85dff449e9e7fb8 /library/cpp/containers/comptrie/writeable_node.cpp | |
parent | 778e51ba091dc39e7b7fcab2b9cf4dbedfb6f2b5 (diff) | |
download | ydb-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.cpp | 156 |
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; } } |