1 // Copyright 2021 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/strings/internal/cord_rep_consume.h"
16
17 #include <array>
18 #include <utility>
19
20 #include "absl/container/inlined_vector.h"
21 #include "absl/functional/function_ref.h"
22 #include "absl/strings/internal/cord_internal.h"
23
24 namespace absl {
25 ABSL_NAMESPACE_BEGIN
26 namespace cord_internal {
27
28 namespace {
29
30 // Unrefs the provided `substring`, and returns `substring->child`
31 // Adds or assumes a reference on `substring->child`
ClipSubstring(CordRepSubstring * substring)32 CordRep* ClipSubstring(CordRepSubstring* substring) {
33 CordRep* child = substring->child;
34 if (substring->refcount.IsOne()) {
35 delete substring;
36 } else {
37 CordRep::Ref(child);
38 CordRep::Unref(substring);
39 }
40 return child;
41 }
42
43 // Unrefs the provided `concat`, and returns `{concat->left, concat->right}`
44 // Adds or assumes a reference on `concat->left` and `concat->right`.
45 // Returns an array of 2 elements containing the left and right nodes.
ClipConcat(CordRepConcat * concat)46 std::array<CordRep*, 2> ClipConcat(CordRepConcat* concat) {
47 std::array<CordRep*, 2> result{concat->left, concat->right};
48 if (concat->refcount.IsOne()) {
49 delete concat;
50 } else {
51 CordRep::Ref(result[0]);
52 CordRep::Ref(result[1]);
53 CordRep::Unref(concat);
54 }
55 return result;
56 }
57
Consume(bool forward,CordRep * rep,ConsumeFn consume_fn)58 void Consume(bool forward, CordRep* rep, ConsumeFn consume_fn) {
59 size_t offset = 0;
60 size_t length = rep->length;
61 struct Entry {
62 CordRep* rep;
63 size_t offset;
64 size_t length;
65 };
66 absl::InlinedVector<Entry, 40> stack;
67
68 for (;;) {
69 if (rep->tag == CONCAT) {
70 std::array<CordRep*, 2> res = ClipConcat(rep->concat());
71 CordRep* left = res[0];
72 CordRep* right = res[1];
73
74 if (left->length <= offset) {
75 // Don't need left node
76 offset -= left->length;
77 CordRep::Unref(left);
78 rep = right;
79 continue;
80 }
81
82 size_t length_left = left->length - offset;
83 if (length_left >= length) {
84 // Don't need right node
85 CordRep::Unref(right);
86 rep = left;
87 continue;
88 }
89
90 // Need both nodes
91 size_t length_right = length - length_left;
92 if (forward) {
93 stack.push_back({right, 0, length_right});
94 rep = left;
95 length = length_left;
96 } else {
97 stack.push_back({left, offset, length_left});
98 rep = right;
99 offset = 0;
100 length = length_right;
101 }
102 } else if (rep->tag == SUBSTRING) {
103 offset += rep->substring()->start;
104 rep = ClipSubstring(rep->substring());
105 } else {
106 consume_fn(rep, offset, length);
107 if (stack.empty()) return;
108
109 rep = stack.back().rep;
110 offset = stack.back().offset;
111 length = stack.back().length;
112 stack.pop_back();
113 }
114 }
115 }
116
117 } // namespace
118
Consume(CordRep * rep,ConsumeFn consume_fn)119 void Consume(CordRep* rep, ConsumeFn consume_fn) {
120 return Consume(true, rep, std::move(consume_fn));
121 }
122
ReverseConsume(CordRep * rep,ConsumeFn consume_fn)123 void ReverseConsume(CordRep* rep, ConsumeFn consume_fn) {
124 return Consume(false, rep, std::move(consume_fn));
125 }
126
127 } // namespace cord_internal
128 ABSL_NAMESPACE_END
129 } // namespace absl
130