cord_rep_btree.cc | Explore in Territory

// 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_btree.h"

#include <atomic>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <ostream>
#include <string>

#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/base/optimization.h"
#include "absl/strings/internal/cord_data_edge.h"
#include "absl/strings/internal/cord_internal.h"
#include "absl/strings/internal/cord_rep_consume.h"
#include "absl/strings/internal/cord_rep_flat.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/string_view.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {

#ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL
constexpr size_t CordRepBtree::kMaxCapacity;
#endif

namespace {

NodeStack;
EdgeType;
OpResult;
CopyResult;

constexpr auto kFront = …;
constexpr auto kBack = …;

ABSL_CONST_INIT std::atomic<bool> cord_btree_exhaustive_validation(false);

// Implementation of the various 'Dump' functions.
// Prints the entire tree structure or 'rep'. External callers should
// not specify 'depth' and leave it to its default (0) value.
// Rep may be a CordRepBtree tree, or a SUBSTRING / EXTERNAL / FLAT node.
void DumpAll(const CordRep* rep,
             bool include_contents,
             std::ostream& stream,
             size_t depth = 0) { … }

// TODO(b/192061034): add 'bytes to copy' logic to avoid large slop on substring
// small data out of large reps, and general efficiency of 'always copy small
// data'. Consider making this a cord rep internal library function.
CordRepSubstring* CreateSubstring(CordRep* rep, size_t offset, size_t n) { … }

// TODO(b/192061034): consider making this a cord rep library function.
inline CordRep* MakeSubstring(CordRep* rep, size_t offset, size_t n) { … }

// TODO(b/192061034): consider making this a cord rep library function.
inline CordRep* MakeSubstring(CordRep* rep, size_t offset) { … }

// Resizes `edge` to the provided `length`. Adopts a reference on `edge`.
// This method directly returns `edge` if `length` equals `edge->length`.
// If `is_mutable` is set to true, this function may return `edge` with
// `edge->length` set to the new length depending on the type and size of
// `edge`. Otherwise, this function returns a new CordRepSubstring value.
// Requires `length > 0 && length <= edge->length`.
CordRep* ResizeEdge(CordRep* edge, size_t length, bool is_mutable) { … }

template <EdgeType edge_type>
inline absl::string_view Consume(absl::string_view s, size_t n) { … }

template <EdgeType edge_type>
inline absl::string_view Consume(char* dst, absl::string_view s, size_t n) { … }

// Known issue / optimization weirdness: the store associated with the
// decrement introduces traffic between cpus (even if the result of that
// traffic does nothing), making this faster than a single call to
// refcount.Decrement() checking the zero refcount condition.
template <typename R, typename Fn>
inline void FastUnref(R* r, Fn&& fn) { … }


void DeleteSubstring(CordRepSubstring* substring) { … }

// Deletes a leaf node data edge. Requires `IsDataEdge(rep)`.
void DeleteLeafEdge(CordRep* rep) { … }

// StackOperations contains the logic to build a left-most or right-most stack
// (leg) down to the leaf level of a btree, and 'unwind' / 'Finalize' methods to
// propagate node changes up the stack.
template <EdgeType edge_type>
struct StackOperations { … };

}  // namespace

void SetCordBtreeExhaustiveValidation(bool do_exaustive_validation) { … }

bool IsCordBtreeExhaustiveValidationEnabled() { … }

void CordRepBtree::Dump(const CordRep* rep, absl::string_view label,
                        bool include_contents, std::ostream& stream) { … }

void CordRepBtree::Dump(const CordRep* rep, absl::string_view label,
                        std::ostream& stream) { … }

void CordRepBtree::Dump(const CordRep* rep, std::ostream& stream) { … }

template <size_t size>
static void DestroyTree(CordRepBtree* tree) { … }

void CordRepBtree::Destroy(CordRepBtree* tree) { … }

bool CordRepBtree::IsValid(const CordRepBtree* tree, bool shallow) { … }

#ifndef NDEBUG

CordRepBtree* CordRepBtree::AssertValid(CordRepBtree* tree, bool shallow) { … }

const CordRepBtree* CordRepBtree::AssertValid(const CordRepBtree* tree,
                                              bool shallow) { … }

#endif  // NDEBUG

template <EdgeType edge_type>
inline OpResult CordRepBtree::AddEdge(bool owned, CordRep* edge, size_t delta) { … }

template <EdgeType edge_type>
OpResult CordRepBtree::SetEdge(bool owned, CordRep* edge, size_t delta) { … }

template <EdgeType edge_type>
CordRepBtree* CordRepBtree::AddCordRep(CordRepBtree* tree, CordRep* rep) { … }

template <>
CordRepBtree* CordRepBtree::NewLeaf<kBack>(absl::string_view data,
                                           size_t extra) { … }

template <>
CordRepBtree* CordRepBtree::NewLeaf<kFront>(absl::string_view data,
                                            size_t extra) { … }

template <>
absl::string_view CordRepBtree::AddData<kBack>(absl::string_view data,
                                               size_t extra) { … }

template <>
absl::string_view CordRepBtree::AddData<kFront>(absl::string_view data,
                                                size_t extra) { … }

template <EdgeType edge_type>
CordRepBtree* CordRepBtree::AddData(CordRepBtree* tree, absl::string_view data,
                                    size_t extra) { … }

template <EdgeType edge_type>
CordRepBtree* CordRepBtree::Merge(CordRepBtree* dst, CordRepBtree* src) { … }

CopyResult CordRepBtree::CopySuffix(size_t offset) { … }

CopyResult CordRepBtree::CopyPrefix(size_t n, bool allow_folding) { … }

CordRep* CordRepBtree::ExtractFront(CordRepBtree* tree) { … }

CordRepBtree* CordRepBtree::ConsumeBeginTo(CordRepBtree* tree, size_t end,
                                           size_t new_length) { … }

CordRep* CordRepBtree::RemoveSuffix(CordRepBtree* tree, size_t n) { … }

CordRep* CordRepBtree::SubTree(size_t offset, size_t n) { … }

CordRepBtree* CordRepBtree::MergeTrees(CordRepBtree* left,
                                       CordRepBtree* right) { … }

bool CordRepBtree::IsFlat(absl::string_view* fragment) const { … }

bool CordRepBtree::IsFlat(size_t offset, const size_t n,
                          absl::string_view* fragment) const { … }

char CordRepBtree::GetCharacter(size_t offset) const { … }

Span<char> CordRepBtree::GetAppendBufferSlow(size_t size) { … }

CordRepBtree* CordRepBtree::CreateSlow(CordRep* rep) { … }

CordRepBtree* CordRepBtree::AppendSlow(CordRepBtree* tree, CordRep* rep) { … }

CordRepBtree* CordRepBtree::PrependSlow(CordRepBtree* tree, CordRep* rep) { … }

CordRepBtree* CordRepBtree::Append(CordRepBtree* tree, absl::string_view data,
                                   size_t extra) { … }

CordRepBtree* CordRepBtree::Prepend(CordRepBtree* tree, absl::string_view data,
                                    size_t extra) { … }

template CordRepBtree* CordRepBtree::AddCordRep<kFront>(CordRepBtree* tree,
                                                        CordRep* rep);
template CordRepBtree* CordRepBtree::AddCordRep<kBack>(CordRepBtree* tree,
                                                       CordRep* rep);
template CordRepBtree* CordRepBtree::AddData<kFront>(CordRepBtree* tree,
                                                     absl::string_view data,
                                                     size_t extra);
template CordRepBtree* CordRepBtree::AddData<kBack>(CordRepBtree* tree,
                                                    absl::string_view data,
                                                    size_t extra);

void CordRepBtree::Rebuild(CordRepBtree** stack, CordRepBtree* tree,
                           bool consume) { … }

CordRepBtree* CordRepBtree::Rebuild(CordRepBtree* tree) { … }

CordRepBtree::ExtractResult CordRepBtree::ExtractAppendBuffer(
    CordRepBtree* tree, size_t extra_capacity) { … }

}  // namespace cord_internal
ABSL_NAMESPACE_END
}  // namespace absl
chromium/third_party/abseil-cpp/absl/strings/internal/cord_rep_btree.cc
