absl/strings/internal/cord_rep_consume.cc

// 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->IsConcat()) {
      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