cord_rep_btree.h | 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.

#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_H_
#define ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_H_

#include <cassert>
#include <cstdint>
#include <iosfwd>

#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_flat.h"
#include "absl/strings/string_view.h"
#include "absl/types/span.h"

namespace absl {
ABSL_NAMESPACE_BEGIN
namespace cord_internal {

// `SetCordBtreeExhaustiveValidation()` can be set to force exhaustive
// validation in debug assertions, and code that calls `IsValid()`
// explicitly. By default, assertions should be relatively cheap and
// AssertValid() can easily lead to O(n^2) complexity as recursive / full tree
// validation is O(n).
void SetCordBtreeExhaustiveValidation(bool do_exaustive_validation);
bool IsCordBtreeExhaustiveValidationEnabled();

class CordRepBtreeNavigator;

// CordRepBtree is as the name implies a btree implementation of a Cordrep tree.
// Data is stored at the leaf level only, non leaf nodes contain down pointers
// only. Allowed types of data edges are FLAT, EXTERNAL and SUBSTRINGs of FLAT
// or EXTERNAL nodes. The implementation allows for data to be added to either
// end of the tree only, it does not provide any 'insert' logic. This has the
// benefit that we can expect good fill ratios: all nodes except the outer
// 'legs' will have 100% fill ratios for trees built using Append/Prepend
// methods. Merged trees will typically have a fill ratio well above 50% as in a
// similar fashion, one side of the merged tree will typically have a 100% fill
// ratio, and the 'open' end will average 50%. All operations are O(log(n)) or
// better, and the tree never needs balancing.
//
// All methods accepting a CordRep* or CordRepBtree* adopt a reference on that
// input unless explicitly stated otherwise. All functions returning a CordRep*
// or CordRepBtree* instance transfer a reference back to the caller.
// Simplified, callers both 'donate' and 'consume' a reference count on each
// call, simplifying the API. An example of building a tree:
//
//   CordRepBtree* tree = CordRepBtree::Create(MakeFlat("Hello"));
//   tree = CordRepBtree::Append(tree, MakeFlat("world"));
//
// In the above example, all inputs are consumed, making each call affecting
// `tree` reference count neutral. The returned `tree` value can be different
// from the input if the input is shared with other threads, or if the tree
// grows in height, but callers typically never have to concern themselves with
// that and trust that all methods DTRT at all times.
class CordRepBtree : public CordRep { … };

inline CordRepBtree* CordRep::btree() { … }

inline const CordRepBtree* CordRep::btree() const { … }

inline void CordRepBtree::InitInstance(int height, size_t begin, size_t end) { … }

inline CordRep* CordRepBtree::Edge(size_t index) const { … }

inline CordRep* CordRepBtree::Edge(EdgeType edge_type) const { … }

inline absl::Span<CordRep* const> CordRepBtree::Edges() const { … }

inline absl::Span<CordRep* const> CordRepBtree::Edges(size_t begin,
                                                      size_t end) const { … }

inline absl::string_view CordRepBtree::Data(size_t index) const { … }

inline CordRepBtree* CordRepBtree::New(int height) { … }

inline CordRepBtree* CordRepBtree::New(CordRep* rep) { … }

inline CordRepBtree* CordRepBtree::New(CordRepBtree* front,
                                       CordRepBtree* back) { … }

inline void CordRepBtree::Unref(absl::Span<CordRep* const> edges) { … }

inline CordRepBtree* CordRepBtree::CopyRaw(size_t new_length) const { … }

inline CordRepBtree* CordRepBtree::Copy() const { … }

inline CordRepBtree* CordRepBtree::CopyToEndFrom(size_t begin,
                                                 size_t new_length) const { … }

inline CordRepBtree* CordRepBtree::CopyBeginTo(size_t end,
                                               size_t new_length) const { … }

inline void CordRepBtree::AlignBegin() { … }

inline void CordRepBtree::AlignEnd() { … }

template <>
inline void CordRepBtree::Add<CordRepBtree::kBack>(CordRep* rep) { … }

template <>
inline void CordRepBtree::Add<CordRepBtree::kBack>(
    absl::Span<CordRep* const> edges) { … }

template <>
inline void CordRepBtree::Add<CordRepBtree::kFront>(CordRep* rep) { … }

template <>
inline void CordRepBtree::Add<CordRepBtree::kFront>(
    absl::Span<CordRep* const> edges) { … }

template <CordRepBtree::EdgeType edge_type>
inline void CordRepBtree::SetEdge(CordRep* edge) { … }

inline CordRepBtree::OpResult CordRepBtree::ToOpResult(bool owned) { … }

inline CordRepBtree::Position CordRepBtree::IndexOf(size_t offset) const { … }

inline CordRepBtree::Position CordRepBtree::IndexBefore(size_t offset) const { … }

inline CordRepBtree::Position CordRepBtree::IndexBefore(Position front,
                                                        size_t offset) const { … }

inline CordRepBtree::Position CordRepBtree::IndexOfLength(size_t n) const { … }

inline CordRepBtree::Position CordRepBtree::IndexBeyond(
    const size_t offset) const { … }

inline CordRepBtree* CordRepBtree::Create(CordRep* rep) { … }

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

extern template CordRepBtree* CordRepBtree::AddCordRep<CordRepBtree::kBack>(
    CordRepBtree* tree, CordRep* rep);

extern template CordRepBtree* CordRepBtree::AddCordRep<CordRepBtree::kFront>(
    CordRepBtree* tree, CordRep* rep);

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

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

#ifdef NDEBUG

inline CordRepBtree* CordRepBtree::AssertValid(CordRepBtree* tree,
                                               bool /* shallow */) {
  return tree;
}

inline const CordRepBtree* CordRepBtree::AssertValid(const CordRepBtree* tree,
                                                     bool /* shallow */) {
  return tree;
}

#endif

}  // namespace cord_internal
ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_STRINGS_INTERNAL_CORD_REP_BTREE_H_
chromium/third_party/abseil-cpp/absl/strings/internal/cord_rep_btree.h
