blob: cd98e6b4d663d9a2fbb171a50810cae7effb402c (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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;
}
}
}
}
|
