diff options
Diffstat (limited to 'third_party/abseil-cpp/absl/strings/internal/cord_rep_consume.cc')
-rw-r--r-- | third_party/abseil-cpp/absl/strings/internal/cord_rep_consume.cc | 129 |
1 files changed, 129 insertions, 0 deletions
diff --git a/third_party/abseil-cpp/absl/strings/internal/cord_rep_consume.cc b/third_party/abseil-cpp/absl/strings/internal/cord_rep_consume.cc new file mode 100644 index 0000000000..81514543db --- /dev/null +++ b/third_party/abseil-cpp/absl/strings/internal/cord_rep_consume.cc @@ -0,0 +1,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 |