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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
#include "writeable_node.h"
#include "node.h"
#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(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;
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;
}
} while (lastLen != len || lastFwdLen != fwdLen);
return len;
}
size_t TWriteableNode::Pack(char* buffer) const {
const size_t length = Measure();
char flags = 0;
if (LeafPos) {
flags |= MT_FINAL;
}
if (ForwardOffset != NPOS) {
flags |= MT_NEXT;
}
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);
buffer[0] = flags;
buffer[1] = Label;
size_t usedLen = 2;
usedLen += PackOffset(buffer + usedLen, leftOffset);
usedLen += PackOffset(buffer + usedLen, rightOffset);
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;
}
}
|
