1 files changed, 265 insertions, 0 deletions
diff --git a/third_party/abseil-cpp/absl/strings/internal/cord_rep_btree_navigator.h b/third_party/abseil-cpp/absl/strings/internal/cord_rep_btree_navigator.h
new file mode 100644
index 0000000000..971b92eda6
--- /dev/null
+++ b/third_party/abseil-cpp/absl/strings/internal/cord_rep_btree_navigator.h
@@ -0,0 +1,265 @@
+// 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.
+
+#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_NAVIGATOR_H_
+#define ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_NAVIGATOR_H_
+
+#include <cassert>
+#include <iostream>
+
+#include "absl/strings/internal/cord_internal.h"
+#include "absl/strings/internal/cord_rep_btree.h"
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace cord_internal {
+
+// CordRepBtreeNavigator is a bi-directional navigator allowing callers to
+// navigate all the (leaf) data edges in a CordRepBtree instance.
+//
+// A CordRepBtreeNavigator instance is by default empty. Callers initialize a
+// navigator instance by calling one of `InitFirst()`, `InitLast()` or
+// `InitOffset()`, which establishes a current position. Callers can then
+// navigate using the `Next`, `Previous`, `Skip` and `Seek` methods.
+//
+// The navigator instance does not take or adopt a reference on the provided
+// `tree` on any of the initialization calls. Callers are responsible for
+// guaranteeing the lifecycle of the provided tree. A navigator instance can
+// be reset to the empty state by calling `Reset`.
+//
+// A navigator only keeps positional state on the 'current data edge', it does
+// explicitly not keep any 'offset' state. The class does accept and return
+// offsets in the `Read()`, `Skip()` and 'Seek()` methods as these would
+// otherwise put a big burden on callers. Callers are expected to maintain
+// (returned) offset info if they require such granular state.
+class CordRepBtreeNavigator {
+ public:
+  // The logical position as returned by the Seek() and Skip() functions.
+  // Returns the current leaf edge for the desired seek or skip position and
+  // the offset of that position inside that edge.
+  struct Position {
+    CordRep* edge;
+    size_t offset;
+  };
+
+  // The read result as returned by the Read() function.
+  // `tree` contains the resulting tree which is identical to the result
+  // of calling CordRepBtree::SubTree(...) on the tree being navigated.
+  // `n` contains the number of bytes used from the last navigated to
+  // edge of the tree.
+  struct ReadResult {
+    CordRep* tree;
+    size_t n;
+  };
+
+  // Returns true if this instance is not empty.
+  explicit operator bool() const;
+
+  // Returns the tree for this instance or nullptr if empty.
+  CordRepBtree* btree() const;
+
+  // Returns the data edge of the current position.
+  // Requires this instance to not be empty.
+  CordRep* Current() const;
+
+  // Resets this navigator to `tree`, returning the first data edge in the tree.
+  CordRep* InitFirst(CordRepBtree* tree);
+
+  // Resets this navigator to `tree`, returning the last data edge in the tree.
+  CordRep* InitLast(CordRepBtree* tree);
+
+  // Resets this navigator to `tree` returning the data edge at position
+  // `offset` and the relative offset of `offset` into that data edge.
+  // Returns `Position.edge = nullptr` if the provided offset is greater
+  // than or equal to the length of the tree, in which case the state of
+  // the navigator instance remains unchanged.
+  Position InitOffset(CordRepBtree* tree, size_t offset);
+
+  // Navigates to the next data edge.
+  // Returns the next data edge or nullptr if there is no next data edge, in
+  // which case the current position remains unchanged.
+  CordRep* Next();
+
+  // Navigates to the previous data edge.
+  // Returns the previous data edge or nullptr if there is no previous data
+  // edge, in which case the current position remains unchanged.
+  CordRep* Previous();
+
+  // Navigates to the data edge at position `offset`. Returns the navigated to
+  // data edge in `Position.edge` and the relative offset of `offset` into that
+  // data edge in `Position.offset`. Returns `Position.edge = nullptr` if the
+  // provide offset is greater than or equal to the tree's length.
+  Position Seek(size_t offset);
+
+  // Reads `n` bytes of data starting at offset `edge_offset` of the current
+  // data edge, and returns the result in `ReadResult.tree`. `ReadResult.n`
+  // contains the 'bytes used` from the last / current data edge in the tree.
+  // This allows users that mix regular navigation (using string views) and
+  // 'read into cord' navigation to keep track of the current state, and which
+  // bytes have been consumed from a navigator.
+  // This function returns `ReadResult.tree = nullptr` if the requested length
+  // exceeds the length of the tree starting at the current data edge.
+  ReadResult Read(size_t edge_offset, size_t n);
+
+  // Skips `n` bytes forward from the current data edge, returning the navigated
+  // to data edge in `Position.edge` and `Position.offset` containing the offset
+  // inside that data edge. Note that the state of the navigator is left
+  // unchanged if `n` is smaller than the length of the current data edge.
+  Position Skip(size_t n);
+
+  // Resets this instance to the default / empty state.
+  void Reset();
+
+ private:
+  // Slow path for Next() if Next() reached the end of a leaf node. Backtracks
+  // up the stack until it finds a node that has a 'next' position available,
+  // and then does a 'front dive' towards the next leaf node.
+  CordRep* NextUp();
+
+  // Slow path for Previous() if Previous() reached the beginning of a leaf
+  // node. Backtracks up the stack until it finds a node that has a 'previous'
+  // position available, and then does a 'back dive' towards the previous leaf
+  // node.
+  CordRep* PreviousUp();
+
+  // Generic implementation of InitFirst() and InitLast().
+  template <CordRepBtree::EdgeType edge_type>
+  CordRep* Init(CordRepBtree* tree);
+
+  // `height_` contains the height of the current tree, or -1 if empty.
+  int height_ = -1;
+
+  // `index_` and `node_` contain the navigation state as the 'path' to the
+  // current data edge which is at `node_[0]->Edge(index_[0])`. The contents
+  // of these are undefined until the instance is initialized (`height_ >= 0`).
+  uint8_t index_[CordRepBtree::kMaxHeight];
+  CordRepBtree* node_[CordRepBtree::kMaxHeight];
+};
+
+// Returns true if this instance is not empty.
+inline CordRepBtreeNavigator::operator bool() const { return height_ >= 0; }
+
+inline CordRepBtree* CordRepBtreeNavigator::btree() const {
+  return height_ >= 0 ? node_[height_] : nullptr;
+}
+
+inline CordRep* CordRepBtreeNavigator::Current() const {
+  assert(height_ >= 0);
+  return node_[0]->Edge(index_[0]);
+}
+
+inline void CordRepBtreeNavigator::Reset() { height_ = -1; }
+
+inline CordRep* CordRepBtreeNavigator::InitFirst(CordRepBtree* tree) {
+  return Init<CordRepBtree::kFront>(tree);
+}
+
+inline CordRep* CordRepBtreeNavigator::InitLast(CordRepBtree* tree) {
+  return Init<CordRepBtree::kBack>(tree);
+}
+
+template <CordRepBtree::EdgeType edge_type>
+inline CordRep* CordRepBtreeNavigator::Init(CordRepBtree* tree) {
+  assert(tree != nullptr);
+  assert(tree->size() > 0);
+  int height = height_ = tree->height();
+  size_t index = tree->index(edge_type);
+  node_[height] = tree;
+  index_[height] = static_cast<uint8_t>(index);
+  while (--height >= 0) {
+    tree = tree->Edge(index)->btree();
+    node_[height] = tree;
+    index = tree->index(edge_type);
+    index_[height] = static_cast<uint8_t>(index);
+  }
+  return node_[0]->Edge(index);
+}
+
+inline CordRepBtreeNavigator::Position CordRepBtreeNavigator::Seek(
+    size_t offset) {
+  assert(btree() != nullptr);
+  int height = height_;
+  CordRepBtree* edge = node_[height];
+  if (ABSL_PREDICT_FALSE(offset >= edge->length)) return {nullptr, 0};
+  CordRepBtree::Position index = edge->IndexOf(offset);
+  index_[height] = static_cast<uint8_t>(index.index);
+  while (--height >= 0) {
+    edge = edge->Edge(index.index)->btree();
+    node_[height] = edge;
+    index = edge->IndexOf(index.n);
+    index_[height] = static_cast<uint8_t>(index.index);
+  }
+  return {edge->Edge(index.index), index.n};
+}
+
+inline CordRepBtreeNavigator::Position CordRepBtreeNavigator::InitOffset(
+    CordRepBtree* tree, size_t offset) {
+  assert(tree != nullptr);
+  if (ABSL_PREDICT_FALSE(offset >= tree->length)) return {nullptr, 0};
+  height_ = tree->height();
+  node_[height_] = tree;
+  return Seek(offset);
+}
+
+inline CordRep* CordRepBtreeNavigator::Next() {
+  CordRepBtree* edge = node_[0];
+  return index_[0] == edge->back() ? NextUp() : edge->Edge(++index_[0]);
+}
+
+inline CordRep* CordRepBtreeNavigator::Previous() {
+  CordRepBtree* edge = node_[0];
+  return index_[0] == edge->begin() ? PreviousUp() : edge->Edge(--index_[0]);
+}
+
+inline CordRep* CordRepBtreeNavigator::NextUp() {
+  assert(index_[0] == node_[0]->back());
+  CordRepBtree* edge;
+  size_t index;
+  int height = 0;
+  do {
+    if (++height > height_) return nullptr;
+    edge = node_[height];
+    index = index_[height] + 1;
+  } while (index == edge->end());
+  index_[height] = static_cast<uint8_t>(index);
+  do {
+    node_[--height] = edge = edge->Edge(index)->btree();
+    index_[height] = static_cast<uint8_t>(index = edge->begin());
+  } while (height > 0);
+  return edge->Edge(index);
+}
+
+inline CordRep* CordRepBtreeNavigator::PreviousUp() {
+  assert(index_[0] == node_[0]->begin());
+  CordRepBtree* edge;
+  size_t index;
+  int height = 0;
+  do {
+    if (++height > height_) return nullptr;
+    edge = node_[height];
+    index = index_[height];
+  } while (index == edge->begin());
+  index_[height] = static_cast<uint8_t>(--index);
+  do {
+    node_[--height] = edge = edge->Edge(index)->btree();
+    index_[height] = static_cast<uint8_t>(index = edge->back());
+  } while (height > 0);
+  return edge->Edge(index);
+}
+
+}  // namespace cord_internal
+ABSL_NAMESPACE_END
+}  // namespace absl
+
+#endif  // ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_NAVIGATOR_H_