Cord Cord::ChunkIterator::AdvanceAndReadBytes()

in absl/strings/cord.cc [1512:1647]
105 lines of code
23 McCabe index (conditional complexity)

Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
  ABSL_HARDENING_ASSERT(bytes_remaining_ >= n &&
                        "Attempted to iterate past `end()`");
  Cord subcord;
  auto constexpr method = CordzUpdateTracker::kCordReader;

  if (n <= InlineRep::kMaxInline) {
    // Range to read fits in inline data. Flatten it.
    char* data = subcord.contents_.set_data(n);
    while (n > current_chunk_.size()) {
      memcpy(data, current_chunk_.data(), current_chunk_.size());
      data += current_chunk_.size();
      n -= current_chunk_.size();
      ++*this;
    }
    memcpy(data, current_chunk_.data(), n);
    if (n < current_chunk_.size()) {
      RemoveChunkPrefix(n);
    } else if (n > 0) {
      ++*this;
    }
    return subcord;
  }

  if (btree_reader_) {
    size_t chunk_size = current_chunk_.size();
    if (n <= chunk_size && n <= kMaxBytesToCopy) {
      subcord = Cord(current_chunk_.substr(0, n), method);
      if (n < chunk_size) {
        current_chunk_.remove_prefix(n);
      } else {
        current_chunk_ = btree_reader_.Next();
      }
    } else {
      CordRep* rep;
      current_chunk_ = btree_reader_.Read(n, chunk_size, rep);
      subcord.contents_.EmplaceTree(rep, method);
    }
    bytes_remaining_ -= n;
    return subcord;
  }

  auto& stack_of_right_children = stack_of_right_children_;
  if (n < current_chunk_.size()) {
    // Range to read is a proper subrange of the current chunk.
    assert(current_leaf_ != nullptr);
    CordRep* subnode = CordRep::Ref(current_leaf_);
    const char* data = subnode->IsExternal() ? subnode->external()->base
                                             : subnode->flat()->Data();
    subnode = NewSubstring(subnode, current_chunk_.data() - data, n);
    subcord.contents_.EmplaceTree(VerifyTree(subnode), method);
    RemoveChunkPrefix(n);
    return subcord;
  }

  // Range to read begins with a proper subrange of the current chunk.
  assert(!current_chunk_.empty());
  assert(current_leaf_ != nullptr);
  CordRep* subnode = CordRep::Ref(current_leaf_);
  if (current_chunk_.size() < subnode->length) {
    const char* data = subnode->IsExternal() ? subnode->external()->base
                                             : subnode->flat()->Data();
    subnode = NewSubstring(subnode, current_chunk_.data() - data,
                           current_chunk_.size());
  }
  n -= current_chunk_.size();
  bytes_remaining_ -= current_chunk_.size();

  // Process the next node(s) on the stack, reading whole subtrees depending on
  // their length and how many bytes we are advancing.
  CordRep* node = nullptr;
  while (!stack_of_right_children.empty()) {
    node = stack_of_right_children.back();
    stack_of_right_children.pop_back();
    if (node->length > n) break;
    // TODO(qrczak): This might unnecessarily recreate existing concat nodes.
    // Avoiding that would need pretty complicated logic (instead of
    // current_leaf, keep current_subtree_ which points to the highest node
    // such that the current leaf can be found on the path of left children
    // starting from current_subtree_; delay creating subnode while node is
    // below current_subtree_; find the proper node along the path of left
    // children starting from current_subtree_ if this loop exits while staying
    // below current_subtree_; etc.; alternatively, push parents instead of
    // right children on the stack).
    subnode = Concat(subnode, CordRep::Ref(node));
    n -= node->length;
    bytes_remaining_ -= node->length;
    node = nullptr;
  }

  if (node == nullptr) {
    // We have reached the end of the Cord.
    assert(bytes_remaining_ == 0);
    subcord.contents_.EmplaceTree(VerifyTree(subnode), method);
    return subcord;
  }

  // Walk down the appropriate branches until we hit a non-CONCAT node. Save the
  // right children to the stack for subsequent traversal.
  while (node->IsConcat()) {
    if (node->concat()->left->length > n) {
      // Push right, descend left.
      stack_of_right_children.push_back(node->concat()->right);
      node = node->concat()->left;
    } else {
      // Read left, descend right.
      subnode = Concat(subnode, CordRep::Ref(node->concat()->left));
      n -= node->concat()->left->length;
      bytes_remaining_ -= node->concat()->left->length;
      node = node->concat()->right;
    }
  }

  // Get the child node if we encounter a SUBSTRING.
  size_t offset = 0;
  size_t length = node->length;
  if (node->IsSubstring()) {
    offset = node->substring()->start;
    node = node->substring()->child;
  }

  // Range to read ends with a proper (possibly empty) subrange of the current
  // chunk.
  assert(node->IsExternal() || node->IsFlat());
  assert(length > n);
  if (n > 0) {
    subnode = Concat(subnode, NewSubstring(CordRep::Ref(node), offset, n));
  }
  const char* data =
      node->IsExternal() ? node->external()->base : node->flat()->Data();
  current_chunk_ = absl::string_view(data + offset + n, length - n);
  current_leaf_ = node;
  bytes_remaining_ -= n;
  subcord.contents_.EmplaceTree(VerifyTree(subnode), method);
  return subcord;
}