intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 79 insertions, 0 deletions

diff --git a/library/cpp/containers/comptrie/node.cpp b/library/cpp/containers/comptrie/node.cpp
new file mode 100644
index 0000000000..5fd22f15ec
--- /dev/null
+++ b/library/cpp/containers/comptrie/node.cpp
@@ -0,0 +1,79 @@
+#include "node.h"
+#include "leaf_skipper.h"
+#include "comptrie_impl.h"
+
+#include <util/system/yassert.h>
+#include <util/generic/yexception.h>
+
+namespace NCompactTrie {
+    TNode::TNode()
+        : Offset(0)
+        , LeafLength(0)
+        , CoreLength(0)
+        , Label(0)
+    {
+        for (auto& offset : Offsets) {
+            offset = 0;
+        }
+    }
+
+    // We believe that epsilon links are found only on the forward-position and that afer jumping an epsilon link you come to an ordinary node.
+
+    TNode::TNode(const char* data, size_t offset, const ILeafSkipper& skipFunction)
+        : Offset(offset)
+        , LeafLength(0)
+        , CoreLength(0)
+        , Label(0)
+    {
+        for (auto& anOffset : Offsets) {
+            anOffset = 0;
+        }
+        if (!data)
+            return; // empty constructor
+
+        const char* datapos = data + offset;
+        char flags = *(datapos++);
+        Y_ASSERT(!IsEpsilonLink(flags));
+        Label = *(datapos++);
+
+        size_t leftsize = LeftOffsetLen(flags);
+        size_t& leftOffset = Offsets[D_LEFT];
+        leftOffset = UnpackOffset(datapos, leftsize);
+        if (leftOffset) {
+            leftOffset += Offset;
+        }
+        datapos += leftsize;
+
+        size_t rightsize = RightOffsetLen(flags);
+        size_t& rightOffset = Offsets[D_RIGHT];
+        rightOffset = UnpackOffset(datapos, rightsize);
+        if (rightOffset) {
+            rightOffset += Offset;
+        }
+        datapos += rightsize;
+
+        if (flags & MT_FINAL) {
+            Offsets[D_FINAL] = datapos - data;
+            LeafLength = skipFunction.SkipLeaf(datapos);
+        }
+
+        CoreLength = 2 + leftsize + rightsize + LeafLength;
+        if (flags & MT_NEXT) {
+            size_t& forwardOffset = Offsets[D_NEXT];
+            forwardOffset = Offset + CoreLength;
+            // There might be an epsilon link at the forward position.
+            // If so, set the ForwardOffset to the value that points to the link's end.
+            const char* forwardPos = data + forwardOffset;
+            const char forwardFlags = *forwardPos;
+            if (IsEpsilonLink(forwardFlags)) {
+                // Jump through the epsilon link.
+                size_t epsilonOffset = UnpackOffset(forwardPos + 1, forwardFlags & MT_SIZEMASK);
+                if (!epsilonOffset) {
+                    ythrow yexception() << "Corrupted epsilon link";
+                }
+                forwardOffset += epsilonOffset;
+            }
+        }
+    }
+
+}