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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
// Copyright 2021 The Abseil Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#include "absl/strings/internal/cord_rep_consume.h"
#include <array>
#include <utility>
#include "absl/container/inlined_vector.h"
#include "absl/functional/function_ref.h"
#include "absl/strings/internal/cord_internal.h"
namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {
namespace {
// Unrefs the provided `substring`, and returns `substring->child`
// Adds or assumes a reference on `substring->child`
CordRep* ClipSubstring(CordRepSubstring* substring) {
CordRep* child = substring->child;
if (substring->refcount.IsOne()) {
delete substring;
} else {
CordRep::Ref(child);
CordRep::Unref(substring);
}
return child;
}
// Unrefs the provided `concat`, and returns `{concat->left, concat->right}`
// Adds or assumes a reference on `concat->left` and `concat->right`.
// Returns an array of 2 elements containing the left and right nodes.
std::array<CordRep*, 2> ClipConcat(CordRepConcat* concat) {
std::array<CordRep*, 2> result{concat->left, concat->right};
if (concat->refcount.IsOne()) {
delete concat;
} else {
CordRep::Ref(result[0]);
CordRep::Ref(result[1]);
CordRep::Unref(concat);
}
return result;
}
void Consume(bool forward, CordRep* rep, ConsumeFn consume_fn) {
size_t offset = 0;
size_t length = rep->length;
struct Entry {
CordRep* rep;
size_t offset;
size_t length;
};
absl::InlinedVector<Entry, 40> stack;
for (;;) {
if (rep->tag == CONCAT) {
std::array<CordRep*, 2> res = ClipConcat(rep->concat());
CordRep* left = res[0];
CordRep* right = res[1];
if (left->length <= offset) {
// Don't need left node
offset -= left->length;
CordRep::Unref(left);
rep = right;
continue;
}
size_t length_left = left->length - offset;
if (length_left >= length) {
// Don't need right node
CordRep::Unref(right);
rep = left;
continue;
}
// Need both nodes
size_t length_right = length - length_left;
if (forward) {
stack.push_back({right, 0, length_right});
rep = left;
length = length_left;
} else {
stack.push_back({left, offset, length_left});
rep = right;
offset = 0;
length = length_right;
}
} else if (rep->tag == SUBSTRING) {
offset += rep->substring()->start;
rep = ClipSubstring(rep->substring());
} else {
consume_fn(rep, offset, length);
if (stack.empty()) return;
rep = stack.back().rep;
offset = stack.back().offset;
length = stack.back().length;
stack.pop_back();
}
}
}
} // namespace
void Consume(CordRep* rep, ConsumeFn consume_fn) {
return Consume(true, rep, std::move(consume_fn));
}
void ReverseConsume(CordRep* rep, ConsumeFn consume_fn) {
return Consume(false, rep, std::move(consume_fn));
}
} // namespace cord_internal
ABSL_NAMESPACE_END
} // namespace absl
|
