diff options
Diffstat (limited to 'third_party/abseil-cpp/absl/strings/cord.cc')
| -rw-r--r-- | third_party/abseil-cpp/absl/strings/cord.cc | 1310 |
1 files changed, 641 insertions, 669 deletions
diff --git a/third_party/abseil-cpp/absl/strings/cord.cc b/third_party/abseil-cpp/absl/strings/cord.cc index 854047ca98..d9503ae332 100644 --- a/third_party/abseil-cpp/absl/strings/cord.cc +++ b/third_party/abseil-cpp/absl/strings/cord.cc @@ -15,12 +15,10 @@ #include "absl/strings/cord.h" #include <algorithm> -#include <atomic> #include <cstddef> #include <cstdio> #include <cstdlib> #include <iomanip> -#include <iostream> #include <limits> #include <ostream> #include <sstream> @@ -30,17 +28,11 @@ #include "absl/base/casts.h" #include "absl/base/internal/raw_logging.h" -#include "absl/base/macros.h" #include "absl/base/port.h" #include "absl/container/fixed_array.h" #include "absl/container/inlined_vector.h" #include "absl/strings/escaping.h" #include "absl/strings/internal/cord_internal.h" -#include "absl/strings/internal/cord_rep_btree.h" -#include "absl/strings/internal/cord_rep_flat.h" -#include "absl/strings/internal/cordz_statistics.h" -#include "absl/strings/internal/cordz_update_scope.h" -#include "absl/strings/internal/cordz_update_tracker.h" #include "absl/strings/internal/resize_uninitialized.h" #include "absl/strings/str_cat.h" #include "absl/strings/str_format.h" @@ -51,18 +43,144 @@ namespace absl { ABSL_NAMESPACE_BEGIN using ::absl::cord_internal::CordRep; -using ::absl::cord_internal::CordRepBtree; using ::absl::cord_internal::CordRepConcat; using ::absl::cord_internal::CordRepExternal; -using ::absl::cord_internal::CordRepFlat; using ::absl::cord_internal::CordRepSubstring; -using ::absl::cord_internal::CordzUpdateTracker; -using ::absl::cord_internal::InlineData; -using ::absl::cord_internal::kMaxFlatLength; -using ::absl::cord_internal::kMinFlatLength; -using ::absl::cord_internal::kInlinedVectorSize; -using ::absl::cord_internal::kMaxBytesToCopy; +// Various representations that we allow +enum CordRepKind { + CONCAT = 0, + EXTERNAL = 1, + SUBSTRING = 2, + + // We have different tags for different sized flat arrays, + // starting with FLAT + FLAT = 3, +}; + +namespace { + +// Type used with std::allocator for allocating and deallocating +// `CordRepExternal`. std::allocator is used because it opaquely handles the +// different new / delete overloads available on a given platform. +struct alignas(absl::cord_internal::ExternalRepAlignment()) ExternalAllocType { + unsigned char value[absl::cord_internal::ExternalRepAlignment()]; +}; + +// Returns the number of objects to pass in to std::allocator<ExternalAllocType> +// allocate() and deallocate() to create enough room for `CordRepExternal` with +// `releaser_size` bytes on the end. +constexpr size_t GetExternalAllocNumObjects(size_t releaser_size) { + // Be sure to round up since `releaser_size` could be smaller than + // `sizeof(ExternalAllocType)`. + return (sizeof(CordRepExternal) + releaser_size + sizeof(ExternalAllocType) - + 1) / + sizeof(ExternalAllocType); +} + +// Allocates enough memory for `CordRepExternal` and a releaser with size +// `releaser_size` bytes. +void* AllocateExternal(size_t releaser_size) { + return std::allocator<ExternalAllocType>().allocate( + GetExternalAllocNumObjects(releaser_size)); +} + +// Deallocates the memory for a `CordRepExternal` assuming it was allocated with +// a releaser of given size and alignment. +void DeallocateExternal(CordRepExternal* p, size_t releaser_size) { + std::allocator<ExternalAllocType>().deallocate( + reinterpret_cast<ExternalAllocType*>(p), + GetExternalAllocNumObjects(releaser_size)); +} + +// Returns a pointer to the type erased releaser for the given CordRepExternal. +void* GetExternalReleaser(CordRepExternal* rep) { + return rep + 1; +} + +} // namespace + +namespace cord_internal { + +inline CordRepConcat* CordRep::concat() { + assert(tag == CONCAT); + return static_cast<CordRepConcat*>(this); +} + +inline const CordRepConcat* CordRep::concat() const { + assert(tag == CONCAT); + return static_cast<const CordRepConcat*>(this); +} + +inline CordRepSubstring* CordRep::substring() { + assert(tag == SUBSTRING); + return static_cast<CordRepSubstring*>(this); +} + +inline const CordRepSubstring* CordRep::substring() const { + assert(tag == SUBSTRING); + return static_cast<const CordRepSubstring*>(this); +} + +inline CordRepExternal* CordRep::external() { + assert(tag == EXTERNAL); + return static_cast<CordRepExternal*>(this); +} + +inline const CordRepExternal* CordRep::external() const { + assert(tag == EXTERNAL); + return static_cast<const CordRepExternal*>(this); +} + +} // namespace cord_internal + +static const size_t kFlatOverhead = offsetof(CordRep, data); + +static_assert(kFlatOverhead == 13, "Unittests assume kFlatOverhead == 13"); + +// Largest and smallest flat node lengths we are willing to allocate +// Flat allocation size is stored in tag, which currently can encode sizes up +// to 4K, encoded as multiple of either 8 or 32 bytes. +// If we allow for larger sizes, we need to change this to 8/64, 16/128, etc. +static constexpr size_t kMaxFlatSize = 4096; +static constexpr size_t kMaxFlatLength = kMaxFlatSize - kFlatOverhead; +static constexpr size_t kMinFlatLength = 32 - kFlatOverhead; + +// Prefer copying blocks of at most this size, otherwise reference count. +static const size_t kMaxBytesToCopy = 511; + +// Helper functions for rounded div, and rounding to exact sizes. +static size_t DivUp(size_t n, size_t m) { return (n + m - 1) / m; } +static size_t RoundUp(size_t n, size_t m) { return DivUp(n, m) * m; } + +// Returns the size to the nearest equal or larger value that can be +// expressed exactly as a tag value. +static size_t RoundUpForTag(size_t size) { + return RoundUp(size, (size <= 1024) ? 8 : 32); +} + +// Converts the allocated size to a tag, rounding down if the size +// does not exactly match a 'tag expressible' size value. The result is +// undefined if the size exceeds the maximum size that can be encoded in +// a tag, i.e., if size is larger than TagToAllocatedSize(<max tag>). +static uint8_t AllocatedSizeToTag(size_t size) { + const size_t tag = (size <= 1024) ? size / 8 : 128 + size / 32 - 1024 / 32; + assert(tag <= std::numeric_limits<uint8_t>::max()); + return tag; +} + +// Converts the provided tag to the corresponding allocated size +static constexpr size_t TagToAllocatedSize(uint8_t tag) { + return (tag <= 128) ? (tag * 8) : (1024 + (tag - 128) * 32); +} + +// Converts the provided tag to the corresponding available data length +static constexpr size_t TagToLength(uint8_t tag) { + return TagToAllocatedSize(tag) - kFlatOverhead; +} + +// Enforce that kMaxFlatSize maps to a well-known exact tag value. +static_assert(TagToAllocatedSize(224) == kMaxFlatSize, "Bad tag logic"); constexpr uint64_t Fibonacci(unsigned char n, uint64_t a = 0, uint64_t b = 1) { return n == 0 ? a : Fibonacci(n - 1, b, a + b); @@ -77,30 +195,70 @@ static_assert(Fibonacci(63) == 6557470319842, // The root node depth is allowed to become twice as large to reduce rebalancing // for larger strings (see IsRootBalanced). static constexpr uint64_t min_length[] = { - Fibonacci(2), Fibonacci(3), Fibonacci(4), Fibonacci(5), - Fibonacci(6), Fibonacci(7), Fibonacci(8), Fibonacci(9), - Fibonacci(10), Fibonacci(11), Fibonacci(12), Fibonacci(13), - Fibonacci(14), Fibonacci(15), Fibonacci(16), Fibonacci(17), - Fibonacci(18), Fibonacci(19), Fibonacci(20), Fibonacci(21), - Fibonacci(22), Fibonacci(23), Fibonacci(24), Fibonacci(25), - Fibonacci(26), Fibonacci(27), Fibonacci(28), Fibonacci(29), - Fibonacci(30), Fibonacci(31), Fibonacci(32), Fibonacci(33), - Fibonacci(34), Fibonacci(35), Fibonacci(36), Fibonacci(37), - Fibonacci(38), Fibonacci(39), Fibonacci(40), Fibonacci(41), - Fibonacci(42), Fibonacci(43), Fibonacci(44), Fibonacci(45), - Fibonacci(46), Fibonacci(47), + Fibonacci(2), + Fibonacci(3), + Fibonacci(4), + Fibonacci(5), + Fibonacci(6), + Fibonacci(7), + Fibonacci(8), + Fibonacci(9), + Fibonacci(10), + Fibonacci(11), + Fibonacci(12), + Fibonacci(13), + Fibonacci(14), + Fibonacci(15), + Fibonacci(16), + Fibonacci(17), + Fibonacci(18), + Fibonacci(19), + Fibonacci(20), + Fibonacci(21), + Fibonacci(22), + Fibonacci(23), + Fibonacci(24), + Fibonacci(25), + Fibonacci(26), + Fibonacci(27), + Fibonacci(28), + Fibonacci(29), + Fibonacci(30), + Fibonacci(31), + Fibonacci(32), + Fibonacci(33), + Fibonacci(34), + Fibonacci(35), + Fibonacci(36), + Fibonacci(37), + Fibonacci(38), + Fibonacci(39), + Fibonacci(40), + Fibonacci(41), + Fibonacci(42), + Fibonacci(43), + Fibonacci(44), + Fibonacci(45), + Fibonacci(46), + Fibonacci(47), 0xffffffffffffffffull, // Avoid overflow }; static const int kMinLengthSize = ABSL_ARRAYSIZE(min_length); -static inline bool btree_enabled() { - return cord_internal::cord_btree_enabled.load( - std::memory_order_relaxed); -} +// The inlined size to use with absl::InlinedVector. +// +// Note: The InlinedVectors in this file (and in cord.h) do not need to use +// the same value for their inlined size. The fact that they do is historical. +// It may be desirable for each to use a different inlined size optimized for +// that InlinedVector's usage. +// +// TODO(jgm): Benchmark to see if there's a more optimal value than 47 for +// the inlined vector size (47 exists for backward compatibility). +static const int kInlinedVectorSize = 47; static inline bool IsRootBalanced(CordRep* node) { - if (!node->IsConcat()) { + if (node->tag != CONCAT) { return true; } else if (node->concat()->depth() <= 15) { return true; @@ -114,8 +272,7 @@ static inline bool IsRootBalanced(CordRep* node) { } static CordRep* Rebalance(CordRep* node); -static void DumpNode(CordRep* rep, bool include_data, std::ostream* os, - int indent = 0); +static void DumpNode(CordRep* rep, bool include_data, std::ostream* os); static bool VerifyNode(CordRep* root, CordRep* start_node, bool full_validation); @@ -135,9 +292,103 @@ static inline CordRep* VerifyTree(CordRep* node) { return node; } +// -------------------------------------------------------------------- +// Memory management + +inline CordRep* Ref(CordRep* rep) { + if (rep != nullptr) { + rep->refcount.Increment(); + } + return rep; +} + +// This internal routine is called from the cold path of Unref below. Keeping it +// in a separate routine allows good inlining of Unref into many profitable call +// sites. However, the call to this function can be highly disruptive to the +// register pressure in those callers. To minimize the cost to callers, we use +// a special LLVM calling convention that preserves most registers. This allows +// the call to this routine in cold paths to not disrupt the caller's register +// pressure. This calling convention is not available on all platforms; we +// intentionally allow LLVM to ignore the attribute rather than attempting to +// hardcode the list of supported platforms. +#if defined(__clang__) && !defined(__i386__) +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wattributes" +__attribute__((preserve_most)) +#pragma clang diagnostic pop +#endif +static void UnrefInternal(CordRep* rep) { + assert(rep != nullptr); + + absl::InlinedVector<CordRep*, kInlinedVectorSize> pending; + while (true) { + if (rep->tag == CONCAT) { + CordRepConcat* rep_concat = rep->concat(); + CordRep* right = rep_concat->right; + if (!right->refcount.Decrement()) { + pending.push_back(right); + } + CordRep* left = rep_concat->left; + delete rep_concat; + rep = nullptr; + if (!left->refcount.Decrement()) { + rep = left; + continue; + } + } else if (rep->tag == EXTERNAL) { + CordRepExternal* rep_external = rep->external(); + absl::string_view data(rep_external->base, rep->length); + void* releaser = GetExternalReleaser(rep_external); + size_t releaser_size = rep_external->releaser_invoker(releaser, data); + rep_external->~CordRepExternal(); + DeallocateExternal(rep_external, releaser_size); + rep = nullptr; + } else if (rep->tag == SUBSTRING) { + CordRepSubstring* rep_substring = rep->substring(); + CordRep* child = rep_substring->child; + delete rep_substring; + rep = nullptr; + if (!child->refcount.Decrement()) { + rep = child; + continue; + } + } else { + // Flat CordReps are allocated and constructed with raw ::operator new + // and placement new, and must be destructed and deallocated + // accordingly. +#if defined(__cpp_sized_deallocation) + size_t size = TagToAllocatedSize(rep->tag); + rep->~CordRep(); + ::operator delete(rep, size); +#else + rep->~CordRep(); + ::operator delete(rep); +#endif + rep = nullptr; + } + + if (!pending.empty()) { + rep = pending.back(); + pending.pop_back(); + } else { + break; + } + } +} + +inline void Unref(CordRep* rep) { + // Fast-path for two common, hot cases: a null rep and a shared root. + if (ABSL_PREDICT_TRUE(rep == nullptr || + rep->refcount.DecrementExpectHighRefcount())) { + return; + } + + UnrefInternal(rep); +} + // Return the depth of a node static int Depth(const CordRep* rep) { - if (rep->IsConcat()) { + if (rep->tag == CONCAT) { return rep->concat()->depth(); } else { return 0; @@ -158,19 +409,17 @@ static void SetConcatChildren(CordRepConcat* concat, CordRep* left, // The returned node has a refcount of 1. static CordRep* RawConcat(CordRep* left, CordRep* right) { // Avoid making degenerate concat nodes (one child is empty) - if (left == nullptr) return right; - if (right == nullptr) return left; - if (left->length == 0) { - CordRep::Unref(left); + if (left == nullptr || left->length == 0) { + Unref(left); return right; } - if (right->length == 0) { - CordRep::Unref(right); + if (right == nullptr || right->length == 0) { + Unref(right); return left; } CordRepConcat* rep = new CordRepConcat(); - rep->tag = cord_internal::CONCAT; + rep->tag = CONCAT; SetConcatChildren(rep, left, right); return rep; @@ -204,41 +453,35 @@ static CordRep* MakeBalancedTree(CordRep** reps, size_t n) { return reps[0]; } -static CordRepFlat* CreateFlat(const char* data, size_t length, - size_t alloc_hint) { - CordRepFlat* flat = CordRepFlat::New(length + alloc_hint); - flat->length = length; - memcpy(flat->Data(), data, length); - return flat; -} - -// Creates a new flat or Btree out of the specified array. -// The returned node has a refcount of 1. -static CordRep* NewBtree(const char* data, size_t length, size_t alloc_hint) { - if (length <= kMaxFlatLength) { - return CreateFlat(data, length, alloc_hint); +// Create a new flat node. +static CordRep* NewFlat(size_t length_hint) { + if (length_hint <= kMinFlatLength) { + length_hint = kMinFlatLength; + } else if (length_hint > kMaxFlatLength) { + length_hint = kMaxFlatLength; } - CordRepFlat* flat = CreateFlat(data, kMaxFlatLength, 0); - data += kMaxFlatLength; - length -= kMaxFlatLength; - auto* root = CordRepBtree::Create(flat); - return CordRepBtree::Append(root, {data, length}, alloc_hint); + + // Round size up so it matches a size we can exactly express in a tag. + const size_t size = RoundUpForTag(length_hint + kFlatOverhead); + void* const raw_rep = ::operator new(size); + CordRep* rep = new (raw_rep) CordRep(); + rep->tag = AllocatedSizeToTag(size); + return VerifyTree(rep); } // Create a new tree out of the specified array. // The returned node has a refcount of 1. -static CordRep* NewTree(const char* data, size_t length, size_t alloc_hint) { +static CordRep* NewTree(const char* data, + size_t length, + size_t alloc_hint) { if (length == 0) return nullptr; - if (btree_enabled()) { - return NewBtree(data, length, alloc_hint); - } absl::FixedArray<CordRep*> reps((length - 1) / kMaxFlatLength + 1); size_t n = 0; do { const size_t len = std::min(length, kMaxFlatLength); - CordRepFlat* rep = CordRepFlat::New(len + alloc_hint); + CordRep* rep = NewFlat(len + alloc_hint); rep->length = len; - memcpy(rep->Data(), data, len); + memcpy(rep->data, data, len); reps[n++] = VerifyTree(rep); data += len; length -= len; @@ -248,12 +491,18 @@ static CordRep* NewTree(const char* data, size_t length, size_t alloc_hint) { namespace cord_internal { -void InitializeCordRepExternal(absl::string_view data, CordRepExternal* rep) { +ExternalRepReleaserPair NewExternalWithUninitializedReleaser( + absl::string_view data, ExternalReleaserInvoker invoker, + size_t releaser_size) { assert(!data.empty()); + + void* raw_rep = AllocateExternal(releaser_size); + auto* rep = new (raw_rep) CordRepExternal(); rep->length = data.size(); rep->tag = EXTERNAL; rep->base = data.data(); - VerifyTree(rep); + rep->releaser_invoker = invoker; + return {VerifyTree(rep), GetExternalReleaser(rep)}; } } // namespace cord_internal @@ -261,155 +510,87 @@ void InitializeCordRepExternal(absl::string_view data, CordRepExternal* rep) { static CordRep* NewSubstring(CordRep* child, size_t offset, size_t length) { // Never create empty substring nodes if (length == 0) { - CordRep::Unref(child); + Unref(child); return nullptr; } else { CordRepSubstring* rep = new CordRepSubstring(); assert((offset + length) <= child->length); rep->length = length; - rep->tag = cord_internal::SUBSTRING; + rep->tag = SUBSTRING; rep->start = offset; rep->child = child; return VerifyTree(rep); } } -// Creates a CordRep from the provided string. If the string is large enough, -// and not wasteful, we move the string into an external cord rep, preserving -// the already allocated string contents. -// Requires the provided string length to be larger than `kMaxInline`. -static CordRep* CordRepFromString(std::string&& src) { - assert(src.length() > cord_internal::kMaxInline); - if ( - // String is short: copy data to avoid external block overhead. - src.size() <= kMaxBytesToCopy || - // String is wasteful: copy data to avoid pinning too much unused memory. - src.size() < src.capacity() / 2 - ) { - return NewTree(src.data(), src.size(), 0); - } - - struct StringReleaser { - void operator()(absl::string_view /* data */) {} - std::string data; - }; - const absl::string_view original_data = src; - auto* rep = - static_cast<::absl::cord_internal::CordRepExternalImpl<StringReleaser>*>( - absl::cord_internal::NewExternalRep(original_data, - StringReleaser{std::move(src)})); - // Moving src may have invalidated its data pointer, so adjust it. - rep->base = rep->template get<0>().data.data(); - return rep; -} - // -------------------------------------------------------------------- // Cord::InlineRep functions -constexpr unsigned char Cord::InlineRep::kMaxInline; +// This will trigger LNK2005 in MSVC. +#ifndef COMPILER_MSVC +const unsigned char Cord::InlineRep::kMaxInline; +#endif // COMPILER_MSVC inline void Cord::InlineRep::set_data(const char* data, size_t n, bool nullify_tail) { static_assert(kMaxInline == 15, "set_data is hard-coded for a length of 15"); - cord_internal::SmallMemmove(data_.as_chars(), data, n, nullify_tail); - set_inline_size(n); + cord_internal::SmallMemmove(data_, data, n, nullify_tail); + data_[kMaxInline] = static_cast<char>(n); } inline char* Cord::InlineRep::set_data(size_t n) { assert(n <= kMaxInline); - ResetToEmpty(); - set_inline_size(n); - return data_.as_chars(); + memset(data_, 0, sizeof(data_)); + data_[kMaxInline] = static_cast<char>(n); + return data_; +} + +inline CordRep* Cord::InlineRep::force_tree(size_t extra_hint) { + size_t len = data_[kMaxInline]; + CordRep* result; + if (len > kMaxInline) { + memcpy(&result, data_, sizeof(result)); + } else { + result = NewFlat(len + extra_hint); + result->length = len; + memcpy(result->data, data_, len); + set_tree(result); + } + return result; } inline void Cord::InlineRep::reduce_size(size_t n) { - size_t tag = inline_size(); + size_t tag = data_[kMaxInline]; assert(tag <= kMaxInline); assert(tag >= n); tag -= n; - memset(data_.as_chars() + tag, 0, n); - set_inline_size(static_cast<char>(tag)); + memset(data_ + tag, 0, n); + data_[kMaxInline] = static_cast<char>(tag); } inline void Cord::InlineRep::remove_prefix(size_t n) { - cord_internal::SmallMemmove(data_.as_chars(), data_.as_chars() + n, - inline_size() - n); + cord_internal::SmallMemmove(data_, data_ + n, data_[kMaxInline] - n); reduce_size(n); } -// Returns `rep` converted into a CordRepBtree. -// Directly returns `rep` if `rep` is already a CordRepBtree. -static CordRepBtree* ForceBtree(CordRep* rep) { - return rep->IsBtree() ? rep->btree() : CordRepBtree::Create(rep); -} - -void Cord::InlineRep::AppendTreeToInlined(CordRep* tree, - MethodIdentifier method) { - assert(!is_tree()); - if (!data_.is_empty()) { - CordRepFlat* flat = MakeFlatWithExtraCapacity(0); - if (btree_enabled()) { - tree = CordRepBtree::Append(CordRepBtree::Create(flat), tree); - } else { - tree = Concat(flat, tree); - } - } - EmplaceTree(tree, method); -} - -void Cord::InlineRep::AppendTreeToTree(CordRep* tree, MethodIdentifier method) { - assert(is_tree()); - const CordzUpdateScope scope(data_.cordz_info(), method); - if (btree_enabled()) { - tree = CordRepBtree::Append(ForceBtree(data_.as_tree()), tree); - } else { - tree = Concat(data_.as_tree(), tree); - } - SetTree(tree, scope); -} - -void Cord::InlineRep::AppendTree(CordRep* tree, MethodIdentifier method) { +void Cord::InlineRep::AppendTree(CordRep* tree) { if (tree == nullptr) return; - if (data_.is_tree()) { - AppendTreeToTree(tree, method); - } else { - AppendTreeToInlined(tree, method); - } -} - -void Cord::InlineRep::PrependTreeToInlined(CordRep* tree, - MethodIdentifier method) { - assert(!is_tree()); - if (!data_.is_empty()) { - CordRepFlat* flat = MakeFlatWithExtraCapacity(0); - if (btree_enabled()) { - tree = CordRepBtree::Prepend(CordRepBtree::Create(flat), tree); - } else { - tree = Concat(tree, flat); - } - } - EmplaceTree(tree, method); -} - -void Cord::InlineRep::PrependTreeToTree(CordRep* tree, - MethodIdentifier method) { - assert(is_tree()); - const CordzUpdateScope scope(data_.cordz_info(), method); - if (btree_enabled()) { - tree = CordRepBtree::Prepend(ForceBtree(data_.as_tree()), tree); + size_t len = data_[kMaxInline]; + if (len == 0) { + set_tree(tree); } else { - tree = Concat(tree, data_.as_tree()); + set_tree(Concat(force_tree(0), tree)); } - SetTree(tree, scope); } -void Cord::InlineRep::PrependTree(CordRep* tree, MethodIdentifier method) { - assert(tree != nullptr); - if (data_.is_tree()) { - PrependTreeToTree(tree, method); +void Cord::InlineRep::PrependTree(CordRep* tree) { + if (tree == nullptr) return; + size_t len = data_[kMaxInline]; + if (len == 0) { + set_tree(tree); } else { - PrependTreeToInlined(tree, method); + set_tree(Concat(tree, force_tree(0))); } } @@ -419,29 +600,20 @@ void Cord::InlineRep::PrependTree(CordRep* tree, MethodIdentifier method) { // written to region and the actual size increase will be written to size. static inline bool PrepareAppendRegion(CordRep* root, char** region, size_t* size, size_t max_length) { - if (root->IsBtree() && root->refcount.IsMutable()) { - Span<char> span = root->btree()->GetAppendBuffer(max_length); - if (!span.empty()) { - *region = span.data(); - *size = span.size(); - return true; - } - } - // Search down the right-hand path for a non-full FLAT node. CordRep* dst = root; - while (dst->IsConcat() && dst->refcount.IsMutable()) { + while (dst->tag == CONCAT && dst->refcount.IsOne()) { dst = dst->concat()->right; } - if (!dst->IsFlat() || !dst->refcount.IsMutable()) { + if (dst->tag < FLAT || !dst->refcount.IsOne()) { *region = nullptr; *size = 0; return false; } const size_t in_use = dst->length; - const size_t capacity = dst->flat()->Capacity(); + const size_t capacity = TagToLength(dst->tag); if (in_use == capacity) { *region = nullptr; *size = 0; @@ -456,281 +628,214 @@ static inline bool PrepareAppendRegion(CordRep* root, char** region, } dst->length += size_increase; - *region = dst->flat()->Data() + in_use; + *region = dst->data + in_use; *size = size_increase; return true; } -template <bool has_length> void Cord::InlineRep::GetAppendRegion(char** region, size_t* size, - size_t length) { - auto constexpr method = CordzUpdateTracker::kGetAppendRegion; + size_t max_length) { + if (max_length == 0) { + *region = nullptr; + *size = 0; + return; + } - CordRep* root = tree(); - size_t sz = root ? root->length : inline_size(); - if (root == nullptr) { - size_t available = kMaxInline - sz; - if (available >= (has_length ? length : 1)) { - *region = data_.as_chars() + sz; - *size = has_length ? length : available; - set_inline_size(has_length ? sz + length : kMaxInline); - return; - } + // Try to fit in the inline buffer if possible. + size_t inline_length = data_[kMaxInline]; + if (inline_length < kMaxInline && max_length <= kMaxInline - inline_length) { + *region = data_ + inline_length; + *size = max_length; + data_[kMaxInline] = static_cast<char>(inline_length + max_length); + return; } - size_t extra = has_length ? length : (std::max)(sz, kMinFlatLength); - CordRep* rep = root ? root : MakeFlatWithExtraCapacity(extra); - CordzUpdateScope scope(root ? data_.cordz_info() : nullptr, method); - if (PrepareAppendRegion(rep, region, size, length)) { - CommitTree(root, rep, scope, method); + CordRep* root = force_tree(max_length); + + if (PrepareAppendRegion(root, region, size, max_length)) { return; } // Allocate new node. - CordRepFlat* new_node = CordRepFlat::New(extra); - new_node->length = std::min(new_node->Capacity(), length); - *region = new_node->Data(); + CordRep* new_node = + NewFlat(std::max(static_cast<size_t>(root->length), max_length)); + new_node->length = + std::min(static_cast<size_t>(TagToLength(new_node->tag)), max_length); + *region = new_node->data; *size = new_node->length; - - if (btree_enabled()) { - rep = CordRepBtree::Append(ForceBtree(rep), new_node); - } else { - rep = Concat(rep, new_node); - } - CommitTree(root, rep, scope, method); + replace_tree(Concat(root, new_node)); } -// Computes the memory side of the provided edge which must be a valid data edge -// for a btrtee, i.e., a FLAT, EXTERNAL or SUBSTRING of a FLAT or EXTERNAL node. -static bool RepMemoryUsageDataEdge(const CordRep* rep, - size_t* total_mem_usage) { - size_t maybe_sub_size = 0; - if (ABSL_PREDICT_FALSE(rep->IsSubstring())) { - maybe_sub_size = sizeof(cord_internal::CordRepSubstring); - rep = rep->substring()->child; - } - if (rep->IsFlat()) { - *total_mem_usage += maybe_sub_size + rep->flat()->AllocatedSize(); - return true; +void Cord::InlineRep::GetAppendRegion(char** region, size_t* size) { + const size_t max_length = std::numeric_limits<size_t>::max(); + + // Try to fit in the inline buffer if possible. + size_t inline_length = data_[kMaxInline]; + if (inline_length < kMaxInline) { + *region = data_ + inline_length; + *size = kMaxInline - inline_length; + data_[kMaxInline] = kMaxInline; + return; } - if (rep->IsExternal()) { - // We don't know anything about the embedded / bound data, but we can safely - // assume it is 'at least' a word / pointer to data. In the future we may - // choose to use the 'data' byte as a tag to identify the types of some - // well-known externals, such as a std::string instance. - *total_mem_usage += maybe_sub_size + - sizeof(cord_internal::CordRepExternalImpl<intptr_t>) + - rep->length; - return true; + + CordRep* root = force_tree(max_length); + + if (PrepareAppendRegion(root, region, size, max_length)) { + return; } - return false; + + // Allocate new node. + CordRep* new_node = NewFlat(root->length); + new_node->length = TagToLength(new_node->tag); + *region = new_node->data; + *size = new_node->length; + replace_tree(Concat(root, new_node)); } // If the rep is a leaf, this will increment the value at total_mem_usage and // will return true. static bool RepMemoryUsageLeaf(const CordRep* rep, size_t* total_mem_usage) { - if (rep->IsFlat()) { - *total_mem_usage += rep->flat()->AllocatedSize(); + if (rep->tag >= FLAT) { + *total_mem_usage += TagToAllocatedSize(rep->tag); return true; } - if (rep->IsExternal()) { - // We don't know anything about the embedded / bound data, but we can safely - // assume it is 'at least' a word / pointer to data. In the future we may - // choose to use the 'data' byte as a tag to identify the types of some - // well-known externals, such as a std::string instance. - *total_mem_usage += - sizeof(cord_internal::CordRepExternalImpl<intptr_t>) + rep->length; + if (rep->tag == EXTERNAL) { + *total_mem_usage += sizeof(CordRepConcat) + rep->length; return true; } return false; } void Cord::InlineRep::AssignSlow(const Cord::InlineRep& src) { - assert(&src != this); - assert(is_tree() || src.is_tree()); - auto constexpr method = CordzUpdateTracker::kAssignCord; - if (ABSL_PREDICT_TRUE(!is_tree())) { - EmplaceTree(CordRep::Ref(src.as_tree()), src.data_, method); - return; - } + ClearSlow(); - CordRep* tree = as_tree(); - if (CordRep* src_tree = src.tree()) { - // Leave any existing `cordz_info` in place, and let MaybeTrackCord() - // decide if this cord should be (or remains to be) sampled or not. - data_.set_tree(CordRep::Ref(src_tree)); - CordzInfo::MaybeTrackCord(data_, src.data_, method); - } else { - CordzInfo::MaybeUntrackCord(data_.cordz_info()); - data_ = src.data_; + memcpy(data_, src.data_, sizeof(data_)); + if (is_tree()) { + Ref(tree()); } - CordRep::Unref(tree); } -void Cord::InlineRep::UnrefTree() { +void Cord::InlineRep::ClearSlow() { if (is_tree()) { - CordzInfo::MaybeUntrackCord(data_.cordz_info()); - CordRep::Unref(tree()); + Unref(tree()); } + memset(data_, 0, sizeof(data_)); } // -------------------------------------------------------------------- // Constructors and destructors -Cord::Cord(absl::string_view src, MethodIdentifier method) - : contents_(InlineData::kDefaultInit) { - const size_t n = src.size(); - if (n <= InlineRep::kMaxInline) { - contents_.set_data(src.data(), n, true); - } else { - CordRep* rep = NewTree(src.data(), n, 0); - contents_.EmplaceTree(rep, method); - } +Cord::Cord(const Cord& src) : contents_(src.contents_) { + Ref(contents_.tree()); // Does nothing if contents_ has embedded data } -template <typename T, Cord::EnableIfString<T>> -Cord::Cord(T&& src) : contents_(InlineData::kDefaultInit) { - if (src.size() <= InlineRep::kMaxInline) { - contents_.set_data(src.data(), src.size(), true); +Cord::Cord(absl::string_view src) { + const size_t n = src.size(); + if (n <= InlineRep::kMaxInline) { + contents_.set_data(src.data(), n, false); } else { - CordRep* rep = CordRepFromString(std::forward<T>(src)); - contents_.EmplaceTree(rep, CordzUpdateTracker::kConstructorString); + contents_.set_tree(NewTree(src.data(), n, 0)); } } -template Cord::Cord(std::string&& src); - // The destruction code is separate so that the compiler can determine // that it does not need to call the destructor on a moved-from Cord. void Cord::DestroyCordSlow() { - assert(contents_.is_tree()); - CordzInfo::MaybeUntrackCord(contents_.cordz_info()); - CordRep::Unref(VerifyTree(contents_.as_tree())); + Unref(VerifyTree(contents_.tree())); } // -------------------------------------------------------------------- // Mutators void Cord::Clear() { - if (CordRep* tree = contents_.clear()) { - CordRep::Unref(tree); - } -} - -Cord& Cord::AssignLargeString(std::string&& src) { - auto constexpr method = CordzUpdateTracker::kAssignString; - assert(src.size() > kMaxBytesToCopy); - CordRep* rep = CordRepFromString(std::move(src)); - if (CordRep* tree = contents_.tree()) { - CordzUpdateScope scope(contents_.cordz_info(), method); - contents_.SetTree(rep, scope); - CordRep::Unref(tree); - } else { - contents_.EmplaceTree(rep, method); - } - return *this; + Unref(contents_.clear()); } Cord& Cord::operator=(absl::string_view src) { - auto constexpr method = CordzUpdateTracker::kAssignString; + const char* data = src.data(); size_t length = src.size(); CordRep* tree = contents_.tree(); if (length <= InlineRep::kMaxInline) { - // Embed into this->contents_, which is somewhat subtle: - // - MaybeUntrackCord must be called before Unref(tree). - // - MaybeUntrackCord must be called before set_data() clobbers cordz_info. - // - set_data() must be called before Unref(tree) as it may reference tree. - if (tree != nullptr) CordzInfo::MaybeUntrackCord(contents_.cordz_info()); + // Embed into this->contents_ contents_.set_data(data, length, true); - if (tree != nullptr) CordRep::Unref(tree); + Unref(tree); return *this; } - if (tree != nullptr) { - CordzUpdateScope scope(contents_.cordz_info(), method); - if (tree->IsFlat() && tree->flat()->Capacity() >= length && - tree->refcount.IsMutable()) { - // Copy in place if the existing FLAT node is reusable. - memmove(tree->flat()->Data(), data, length); - tree->length = length; - VerifyTree(tree); - return *this; - } - contents_.SetTree(NewTree(data, length, 0), scope); - CordRep::Unref(tree); - } else { - contents_.EmplaceTree(NewTree(data, length, 0), method); + if (tree != nullptr && tree->tag >= FLAT && + TagToLength(tree->tag) >= length && tree->refcount.IsOne()) { + // Copy in place if the existing FLAT node is reusable. + memmove(tree->data, data, length); + tree->length = length; + VerifyTree(tree); + return *this; } + contents_.set_tree(NewTree(data, length, 0)); + Unref(tree); return *this; } // TODO(sanjay): Move to Cord::InlineRep section of file. For now, // we keep it here to make diffs easier. -void Cord::InlineRep::AppendArray(absl::string_view src, - MethodIdentifier method) { - if (src.empty()) return; // memcpy(_, nullptr, 0) is undefined. +void Cord::InlineRep::AppendArray(const char* src_data, size_t src_size) { + if (src_size == 0) return; // memcpy(_, nullptr, 0) is undefined. + // Try to fit in the inline buffer if possible. + size_t inline_length = data_[kMaxInline]; + if (inline_length < kMaxInline && src_size <= kMaxInline - inline_length) { + // Append new data to embedded array + data_[kMaxInline] = static_cast<char>(inline_length + src_size); + memcpy(data_ + inline_length, src_data, src_size); + return; + } + + CordRep* root = tree(); size_t appended = 0; - CordRep* rep = tree(); - const CordRep* const root = rep; - CordzUpdateScope scope(root ? cordz_info() : nullptr, method); - if (root != nullptr) { + if (root) { char* region; - if (PrepareAppendRegion(rep, ®ion, &appended, src.size())) { - memcpy(region, src.data(), appended); + if (PrepareAppendRegion(root, ®ion, &appended, src_size)) { + memcpy(region, src_data, appended); } } else { - // Try to fit in the inline buffer if possible. - size_t inline_length = inline_size(); - if (src.size() <= kMaxInline - inline_length) { - // Append new data to embedded array - memcpy(data_.as_chars() + inline_length, src.data(), src.size()); - set_inline_size(inline_length + src.size()); - return; - } - - // Allocate flat to be a perfect fit on first append exceeding inlined size. - // Subsequent growth will use amortized growth until we reach maximum flat - // size. - rep = CordRepFlat::New(inline_length + src.size()); - appended = std::min(src.size(), rep->flat()->Capacity() - inline_length); - memcpy(rep->flat()->Data(), data_.as_chars(), inline_length); - memcpy(rep->flat()->Data() + inline_length, src.data(), appended); - rep->length = inline_length + appended; - } - - src.remove_prefix(appended); - if (src.empty()) { - CommitTree(root, rep, scope, method); + // It is possible that src_data == data_, but when we transition from an + // InlineRep to a tree we need to assign data_ = root via set_tree. To + // avoid corrupting the source data before we copy it, delay calling + // set_tree until after we've copied data. + // We are going from an inline size to beyond inline size. Make the new size + // either double the inlined size, or the added size + 10%. + const size_t size1 = inline_length * 2 + src_size; + const size_t size2 = inline_length + src_size / 10; + root = NewFlat(std::max<size_t>(size1, size2)); + appended = std::min(src_size, TagToLength(root->tag) - inline_length); + memcpy(root->data, data_, inline_length); + memcpy(root->data + inline_length, src_data, appended); + root->length = inline_length + appended; + set_tree(root); + } + + src_data += appended; + src_size -= appended; + if (src_size == 0) { return; } - if (btree_enabled()) { - // TODO(b/192061034): keep legacy 10% growth rate: consider other rates. - rep = ForceBtree(rep); - const size_t min_growth = std::max<size_t>(rep->length / 10, src.size()); - rep = CordRepBtree::Append(rep->btree(), src, min_growth - src.size()); - } else { - // Use new block(s) for any remaining bytes that were not handled above. - // Alloc extra memory only if the right child of the root of the new tree - // is going to be a FLAT node, which will permit further inplace appends. - size_t length = src.size(); - if (src.size() < kMaxFlatLength) { - // The new length is either - // - old size + 10% - // - old_size + src.size() - // This will cause a reasonable conservative step-up in size that is - // still large enough to avoid excessive amounts of small fragments - // being added. - length = std::max<size_t>(rep->length / 10, src.size()); - } - rep = Concat(rep, NewTree(src.data(), src.size(), length - src.size())); + // Use new block(s) for any remaining bytes that were not handled above. + // Alloc extra memory only if the right child of the root of the new tree is + // going to be a FLAT node, which will permit further inplace appends. + size_t length = src_size; + if (src_size < kMaxFlatLength) { + // The new length is either + // - old size + 10% + // - old_size + src_size + // This will cause a reasonable conservative step-up in size that is still + // large enough to avoid excessive amounts of small fragments being added. + length = std::max<size_t>(root->length / 10, src_size); } - CommitTree(root, rep, scope, method); + set_tree(Concat(root, NewTree(src_data, src_size, length - src_size))); } inline CordRep* Cord::TakeRep() const& { - return CordRep::Ref(contents_.tree()); + return Ref(contents_.tree()); } inline CordRep* Cord::TakeRep() && { @@ -741,17 +846,10 @@ inline CordRep* Cord::TakeRep() && { template <typename C> inline void Cord::AppendImpl(C&& src) { - auto constexpr method = CordzUpdateTracker::kAppendCord; if (empty()) { - // Since destination is empty, we can avoid allocating a node, - if (src.contents_.is_tree()) { - // by taking the tree directly - CordRep* rep = std::forward<C>(src).TakeRep(); - contents_.EmplaceTree(rep, method); - } else { - // or copying over inline data - contents_.data_ = src.contents_.data_; - } + // In case of an empty destination avoid allocating a new node, do not copy + // data. + *this = std::forward<C>(src); return; } @@ -761,12 +859,12 @@ inline void Cord::AppendImpl(C&& src) { CordRep* src_tree = src.contents_.tree(); if (src_tree == nullptr) { // src has embedded data. - contents_.AppendArray({src.contents_.data(), src_size}, method); + contents_.AppendArray(src.contents_.data(), src_size); return; } - if (src_tree->IsFlat()) { + if (src_tree->tag >= FLAT) { // src tree just has one flat node. - contents_.AppendArray({src_tree->flat()->Data(), src_size}, method); + contents_.AppendArray(src_tree->data, src_size); return; } if (&src == this) { @@ -781,36 +879,18 @@ inline void Cord::AppendImpl(C&& src) { return; } - // Guaranteed to be a tree (kMaxBytesToCopy > kInlinedSize) - CordRep* rep = std::forward<C>(src).TakeRep(); - contents_.AppendTree(rep, CordzUpdateTracker::kAppendCord); -} - -void Cord::Append(const Cord& src) { - AppendImpl(src); + contents_.AppendTree(std::forward<C>(src).TakeRep()); } -void Cord::Append(Cord&& src) { - AppendImpl(std::move(src)); -} +void Cord::Append(const Cord& src) { AppendImpl(src); } -template <typename T, Cord::EnableIfString<T>> -void Cord::Append(T&& src) { - if (src.size() <= kMaxBytesToCopy) { - Append(absl::string_view(src)); - } else { - CordRep* rep = CordRepFromString(std::forward<T>(src)); - contents_.AppendTree(rep, CordzUpdateTracker::kAppendString); - } -} - -template void Cord::Append(std::string&& src); +void Cord::Append(Cord&& src) { AppendImpl(std::move(src)); } void Cord::Prepend(const Cord& src) { CordRep* src_tree = src.contents_.tree(); if (src_tree != nullptr) { - CordRep::Ref(src_tree); - contents_.PrependTree(src_tree, CordzUpdateTracker::kPrependCord); + Ref(src_tree); + contents_.PrependTree(src_tree); return; } @@ -819,42 +899,28 @@ void Cord::Prepend(const Cord& src) { return Prepend(src_contents); } -void Cord::PrependArray(absl::string_view src, MethodIdentifier method) { +void Cord::Prepend(absl::string_view src) { if (src.empty()) return; // memcpy(_, nullptr, 0) is undefined. - if (!contents_.is_tree()) { - size_t cur_size = contents_.inline_size(); - if (cur_size + src.size() <= InlineRep::kMaxInline) { - // Use embedded storage. - char data[InlineRep::kMaxInline + 1] = {0}; - memcpy(data, src.data(), src.size()); - memcpy(data + src.size(), contents_.data(), cur_size); - memcpy(contents_.data_.as_chars(), data, InlineRep::kMaxInline + 1); - contents_.set_inline_size(cur_size + src.size()); - return; - } - } - CordRep* rep = NewTree(src.data(), src.size(), 0); - contents_.PrependTree(rep, method); -} - -template <typename T, Cord::EnableIfString<T>> -inline void Cord::Prepend(T&& src) { - if (src.size() <= kMaxBytesToCopy) { - Prepend(absl::string_view(src)); + size_t cur_size = contents_.size(); + if (!contents_.is_tree() && cur_size + src.size() <= InlineRep::kMaxInline) { + // Use embedded storage. + char data[InlineRep::kMaxInline + 1] = {0}; + data[InlineRep::kMaxInline] = cur_size + src.size(); // set size + memcpy(data, src.data(), src.size()); + memcpy(data + src.size(), contents_.data(), cur_size); + memcpy(reinterpret_cast<void*>(&contents_), data, + InlineRep::kMaxInline + 1); } else { - CordRep* rep = CordRepFromString(std::forward<T>(src)); - contents_.PrependTree(rep, CordzUpdateTracker::kPrependString); + contents_.PrependTree(NewTree(src.data(), src.size(), 0)); } } -template void Cord::Prepend(std::string&& src); - static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { if (n >= node->length) return nullptr; - if (n == 0) return CordRep::Ref(node); + if (n == 0) return Ref(node); absl::InlinedVector<CordRep*, kInlinedVectorSize> rhs_stack; - while (node->IsConcat()) { + while (node->tag == CONCAT) { assert(n <= node->length); if (n < node->concat()->left->length) { // Push right to stack, descend left. @@ -869,19 +935,19 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { assert(n <= node->length); if (n == 0) { - CordRep::Ref(node); + Ref(node); } else { size_t start = n; size_t len = node->length - n; - if (node->IsSubstring()) { + if (node->tag == SUBSTRING) { // Consider in-place update of node, similar to in RemoveSuffixFrom(). start += node->substring()->start; node = node->substring()->child; } - node = NewSubstring(CordRep::Ref(node), start, len); + node = NewSubstring(Ref(node), start, len); } while (!rhs_stack.empty()) { - node = Concat(node, CordRep::Ref(rhs_stack.back())); + node = Concat(node, Ref(rhs_stack.back())); rhs_stack.pop_back(); } return node; @@ -892,11 +958,11 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) { // edited in place iff that node and all its ancestors have a refcount of 1. static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) { if (n >= node->length) return nullptr; - if (n == 0) return CordRep::Ref(node); + if (n == 0) return Ref(node); absl::InlinedVector<CordRep*, kInlinedVectorSize> lhs_stack; - bool inplace_ok = node->refcount.IsMutable(); + bool inplace_ok = node->refcount.IsOne(); - while (node->IsConcat()) { + while (node->tag == CONCAT) { assert(n <= node->length); if (n < node->concat()->right->length) { // Push left to stack, descend right. @@ -907,28 +973,28 @@ static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) { n -= node->concat()->right->length; node = node->concat()->left; } - inplace_ok = inplace_ok && node->refcount.IsMutable(); + inplace_ok = inplace_ok && node->refcount.IsOne(); } assert(n <= node->length); if (n == 0) { - CordRep::Ref(node); - } else if (inplace_ok && !node->IsExternal()) { + Ref(node); + } else if (inplace_ok && node->tag != EXTERNAL) { // Consider making a new buffer if the current node capacity is much // larger than the new length. - CordRep::Ref(node); + Ref(node); node->length -= n; } else { size_t start = 0; size_t len = node->length - n; - if (node->IsSubstring()) { + if (node->tag == SUBSTRING) { start = node->substring()->start; node = node->substring()->child; } - node = NewSubstring(CordRep::Ref(node), start, len); + node = NewSubstring(Ref(node), start, len); } while (!lhs_stack.empty()) { - node = Concat(CordRep::Ref(lhs_stack.back()), node); + node = Concat(Ref(lhs_stack.back()), node); lhs_stack.pop_back(); } return node; @@ -942,18 +1008,9 @@ void Cord::RemovePrefix(size_t n) { if (tree == nullptr) { contents_.remove_prefix(n); } else { - auto constexpr method = CordzUpdateTracker::kRemovePrefix; - CordzUpdateScope scope(contents_.cordz_info(), method); - if (tree->IsBtree()) { - CordRep* old = tree; - tree = tree->btree()->SubTree(n, tree->length - n); - CordRep::Unref(old); - } else { - CordRep* newrep = RemovePrefixFrom(tree, n); - CordRep::Unref(tree); - tree = VerifyTree(newrep); - } - contents_.SetTreeOrEmpty(tree, scope); + CordRep* newrep = RemovePrefixFrom(tree, n); + Unref(tree); + contents_.replace_tree(VerifyTree(newrep)); } } @@ -965,16 +1022,9 @@ void Cord::RemoveSuffix(size_t n) { if (tree == nullptr) { contents_.reduce_size(n); } else { - auto constexpr method = CordzUpdateTracker::kRemoveSuffix; - CordzUpdateScope scope(contents_.cordz_info(), method); - if (tree->IsBtree()) { - tree = CordRepBtree::RemoveSuffix(tree->btree(), n); - } else { - CordRep* newrep = RemoveSuffixFrom(tree, n); - CordRep::Unref(tree); - tree = VerifyTree(newrep); - } - contents_.SetTreeOrEmpty(tree, scope); + CordRep* newrep = RemoveSuffixFrom(tree, n); + Unref(tree); + contents_.replace_tree(VerifyTree(newrep)); } } @@ -1006,13 +1056,13 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) { results.pop_back(); results.push_back(Concat(left, right)); } else if (pos == 0 && n == node->length) { - results.push_back(CordRep::Ref(node)); - } else if (!node->IsConcat()) { - if (node->IsSubstring()) { + results.push_back(Ref(node)); + } else if (node->tag != CONCAT) { + if (node->tag == SUBSTRING) { pos += node->substring()->start; node = node->substring()->child; } - results.push_back(NewSubstring(CordRep::Ref(node), pos, n)); + results.push_back(NewSubstring(Ref(node), pos, n)); } else if (pos + n <= node->concat()->left->length) { todo.push_back(SubRange(node->concat()->left, pos, n)); } else if (pos >= node->concat()->left->length) { @@ -1034,20 +1084,17 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const { size_t length = size(); if (pos > length) pos = length; if (new_size > length - pos) new_size = length - pos; - if (new_size == 0) return sub_cord; - CordRep* tree = contents_.tree(); if (tree == nullptr) { // sub_cord is newly constructed, no need to re-zero-out the tail of // contents_ memory. sub_cord.contents_.set_data(contents_.data() + pos, new_size, false); - return sub_cord; - } - - if (new_size <= InlineRep::kMaxInline) { - char* dest = sub_cord.contents_.data_.as_chars(); + } else if (new_size == 0) { + // We want to return empty subcord, so nothing to do. + } else if (new_size <= InlineRep::kMaxInline) { Cord::ChunkIterator it = chunk_begin(); it.AdvanceBytes(pos); + char* dest = sub_cord.contents_.data_; size_t remaining_size = new_size; while (remaining_size > it->size()) { cord_internal::SmallMemmove(dest, it->data(), it->size()); @@ -1056,17 +1103,10 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const { ++it; } cord_internal::SmallMemmove(dest, it->data(), remaining_size); - sub_cord.contents_.set_inline_size(new_size); - return sub_cord; - } - - if (tree->IsBtree()) { - tree = tree->btree()->SubTree(pos, new_size); + sub_cord.contents_.data_[InlineRep::kMaxInline] = new_size; } else { - tree = NewSubRange(tree, pos, new_size); + sub_cord.contents_.set_tree(NewSubRange(tree, pos, new_size)); } - sub_cord.contents_.EmplaceTree(tree, contents_.data_, - CordzUpdateTracker::kSubCord); return sub_cord; } @@ -1085,7 +1125,7 @@ class CordForest { CordRep* node = pending.back(); pending.pop_back(); CheckNode(node); - if (ABSL_PREDICT_FALSE(!node->IsConcat())) { + if (ABSL_PREDICT_FALSE(node->tag != CONCAT)) { AddNode(node); continue; } @@ -1100,9 +1140,9 @@ class CordForest { concat_node->left = concat_freelist_; concat_freelist_ = concat_node; } else { - CordRep::Ref(concat_node->right); - CordRep::Ref(concat_node->left); - CordRep::Unref(concat_node); + Ref(concat_node->right); + Ref(concat_node->left); + Unref(concat_node); } } else { AddNode(node); @@ -1135,7 +1175,7 @@ class CordForest { void AddNode(CordRep* node) { CordRep* sum = nullptr; - // Collect together everything with which we will merge with node + // Collect together everything with which we will merge node int i = 0; for (; node->length > min_length[i + 1]; ++i) { auto& tree_at_i = trees_[i]; @@ -1179,7 +1219,7 @@ class CordForest { static void CheckNode(CordRep* node) { ABSL_INTERNAL_CHECK(node->length != 0u, ""); - if (node->IsConcat()) { + if (node->tag == CONCAT) { ABSL_INTERNAL_CHECK(node->concat()->left != nullptr, ""); ABSL_INTERNAL_CHECK(node->concat()->right != nullptr, ""); ABSL_INTERNAL_CHECK(node->length == (node->concat()->left->length + @@ -1199,7 +1239,7 @@ class CordForest { static CordRep* Rebalance(CordRep* node) { VerifyTree(node); - assert(node->IsConcat()); + assert(node->tag == CONCAT); if (node->length == 0) { return nullptr; @@ -1249,33 +1289,25 @@ bool ComputeCompareResult<bool>(int memcmp_res) { } // namespace -// Helper routine. Locates the first flat or external chunk of the Cord without -// initializing the iterator, and returns a string_view referencing the data. +// Helper routine. Locates the first flat chunk of the Cord without +// initializing the iterator. inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const { - if (!is_tree()) { - return absl::string_view(data_.as_chars(), data_.inline_size()); + size_t n = data_[kMaxInline]; + if (n <= kMaxInline) { + return absl::string_view(data_, n); } CordRep* node = tree(); - if (node->IsFlat()) { - return absl::string_view(node->flat()->Data(), node->length); + if (node->tag >= FLAT) { + return absl::string_view(node->data, node->length); } - if (node->IsExternal()) { + if (node->tag == EXTERNAL) { return absl::string_view(node->external()->base, node->length); } - if (node->IsBtree()) { - CordRepBtree* tree = node->btree(); - int height = tree->height(); - while (--height >= 0) { - tree = tree->Edge(CordRepBtree::kFront)->btree(); - } - return tree->Data(tree->begin()); - } - // Walk down the left branches until we hit a non-CONCAT node. - while (node->IsConcat()) { + while (node->tag == CONCAT) { node = node->concat()->left; } @@ -1284,16 +1316,16 @@ inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const { size_t length = node->length; assert(length != 0); - if (node->IsSubstring()) { + if (node->tag == SUBSTRING) { offset = node->substring()->start; node = node->substring()->child; } - if (node->IsFlat()) { - return absl::string_view(node->flat()->Data() + offset, length); + if (node->tag >= FLAT) { + return absl::string_view(node->data + offset, length); } - assert(node->IsExternal() && "Expect FLAT or EXTERNAL node here"); + assert((node->tag == EXTERNAL) && "Expect FLAT or EXTERNAL node here"); return absl::string_view(node->external()->base + offset, length); } @@ -1473,47 +1505,48 @@ void Cord::CopyToArraySlowPath(char* dst) const { } } -Cord::ChunkIterator& Cord::ChunkIterator::AdvanceStack() { - auto& stack_of_right_children = stack_of_right_children_; - if (stack_of_right_children.empty()) { +Cord::ChunkIterator& Cord::ChunkIterator::operator++() { + assert(bytes_remaining_ > 0 && "Attempted to iterate past `end()`"); + assert(bytes_remaining_ >= current_chunk_.size()); + bytes_remaining_ -= current_chunk_.size(); + + if (stack_of_right_children_.empty()) { assert(!current_chunk_.empty()); // Called on invalid iterator. // We have reached the end of the Cord. return *this; } // Process the next node on the stack. - CordRep* node = stack_of_right_children.back(); - stack_of_right_children.pop_back(); + CordRep* node = stack_of_right_children_.back(); + stack_of_right_children_.pop_back(); // Walk down the left branches until we hit a non-CONCAT node. Save the // right children to the stack for subsequent traversal. - while (node->IsConcat()) { - stack_of_right_children.push_back(node->concat()->right); + while (node->tag == CONCAT) { + stack_of_right_children_.push_back(node->concat()->right); node = node->concat()->left; } // Get the child node if we encounter a SUBSTRING. size_t offset = 0; size_t length = node->length; - if (node->IsSubstring()) { + if (node->tag == SUBSTRING) { offset = node->substring()->start; node = node->substring()->child; } - assert(node->IsExternal() || node->IsFlat()); + assert(node->tag == EXTERNAL || node->tag >= FLAT); assert(length != 0); const char* data = - node->IsExternal() ? node->external()->base : node->flat()->Data(); + node->tag == EXTERNAL ? node->external()->base : node->data; current_chunk_ = absl::string_view(data + offset, length); current_leaf_ = node; return *this; } Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { - ABSL_HARDENING_ASSERT(bytes_remaining_ >= n && - "Attempted to iterate past `end()`"); + 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. @@ -1532,34 +1565,14 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { } 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(); + CordRep* subnode = Ref(current_leaf_); + const char* data = + subnode->tag == EXTERNAL ? subnode->external()->base : subnode->data; subnode = NewSubstring(subnode, current_chunk_.data() - data, n); - subcord.contents_.EmplaceTree(VerifyTree(subnode), method); + subcord.contents_.set_tree(VerifyTree(subnode)); RemoveChunkPrefix(n); return subcord; } @@ -1567,10 +1580,10 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { // 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_); + CordRep* subnode = Ref(current_leaf_); if (current_chunk_.size() < subnode->length) { - const char* data = subnode->IsExternal() ? subnode->external()->base - : subnode->flat()->Data(); + const char* data = + subnode->tag == EXTERNAL ? subnode->external()->base : subnode->data; subnode = NewSubstring(subnode, current_chunk_.data() - data, current_chunk_.size()); } @@ -1580,20 +1593,20 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { // 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(); + 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 + // 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)); + subnode = Concat(subnode, Ref(node)); n -= node->length; bytes_remaining_ -= node->length; node = nullptr; @@ -1602,20 +1615,20 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { if (node == nullptr) { // We have reached the end of the Cord. assert(bytes_remaining_ == 0); - subcord.contents_.EmplaceTree(VerifyTree(subnode), method); + subcord.contents_.set_tree(VerifyTree(subnode)); 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()) { + while (node->tag == CONCAT) { if (node->concat()->left->length > n) { // Push right, descend left. - stack_of_right_children.push_back(node->concat()->right); + 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)); + subnode = Concat(subnode, Ref(node->concat()->left)); n -= node->concat()->left->length; bytes_remaining_ -= node->concat()->left->length; node = node->concat()->right; @@ -1625,24 +1638,22 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) { // Get the child node if we encounter a SUBSTRING. size_t offset = 0; size_t length = node->length; - if (node->IsSubstring()) { + if (node->tag == SUBSTRING) { 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(node->tag == EXTERNAL || node->tag >= FLAT); assert(length > n); - if (n > 0) { - subnode = Concat(subnode, NewSubstring(CordRep::Ref(node), offset, n)); - } + if (n > 0) subnode = Concat(subnode, NewSubstring(Ref(node), offset, n)); const char* data = - node->IsExternal() ? node->external()->base : node->flat()->Data(); + node->tag == EXTERNAL ? node->external()->base : node->data; current_chunk_ = absl::string_view(data + offset + n, length - n); current_leaf_ = node; bytes_remaining_ -= n; - subcord.contents_.EmplaceTree(VerifyTree(subnode), method); + subcord.contents_.set_tree(VerifyTree(subnode)); return subcord; } @@ -1654,19 +1665,12 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) { n -= current_chunk_.size(); bytes_remaining_ -= current_chunk_.size(); - if (stack_of_right_children_.empty()) { - // We have reached the end of the Cord. - assert(bytes_remaining_ == 0); - return; - } - // Process the next node(s) on the stack, skipping whole subtrees depending on // their length and how many bytes we are advancing. CordRep* node = nullptr; - auto& stack_of_right_children = stack_of_right_children_; - while (!stack_of_right_children.empty()) { - node = stack_of_right_children.back(); - stack_of_right_children.pop_back(); + while (!stack_of_right_children_.empty()) { + node = stack_of_right_children_.back(); + stack_of_right_children_.pop_back(); if (node->length > n) break; n -= node->length; bytes_remaining_ -= node->length; @@ -1681,10 +1685,10 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) { // 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()) { + while (node->tag == CONCAT) { if (node->concat()->left->length > n) { // Push right, descend left. - stack_of_right_children.push_back(node->concat()->right); + stack_of_right_children_.push_back(node->concat()->right); node = node->concat()->left; } else { // Skip left, descend right. @@ -1697,22 +1701,22 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) { // Get the child node if we encounter a SUBSTRING. size_t offset = 0; size_t length = node->length; - if (node->IsSubstring()) { + if (node->tag == SUBSTRING) { offset = node->substring()->start; node = node->substring()->child; } - assert(node->IsExternal() || node->IsFlat()); + assert(node->tag == EXTERNAL || node->tag >= FLAT); assert(length > n); const char* data = - node->IsExternal() ? node->external()->base : node->flat()->Data(); + node->tag == EXTERNAL ? node->external()->base : node->data; current_chunk_ = absl::string_view(data + offset + n, length - n); current_leaf_ = node; bytes_remaining_ -= n; } char Cord::operator[](size_t i) const { - ABSL_HARDENING_ASSERT(i < size()); + assert(i < size()); size_t offset = i; const CordRep* rep = contents_.tree(); if (rep == nullptr) { @@ -1721,15 +1725,13 @@ char Cord::operator[](size_t i) const { while (true) { assert(rep != nullptr); assert(offset < rep->length); - if (rep->IsFlat()) { + if (rep->tag >= FLAT) { // Get the "i"th character directly from the flat array. - return rep->flat()->Data()[offset]; - } else if (rep->IsBtree()) { - return rep->btree()->GetCharacter(offset); - } else if (rep->IsExternal()) { + return rep->data[offset]; + } else if (rep->tag == EXTERNAL) { // Get the "i"th character from the external array. return rep->external()->base[offset]; - } else if (rep->IsConcat()) { + } else if (rep->tag == CONCAT) { // Recursively branch to the side of the concatenation that the "i"th // character is on. size_t left_length = rep->concat()->left->length; @@ -1741,7 +1743,7 @@ char Cord::operator[](size_t i) const { } } else { // This must be a substring a node, so bypass it to get to the child. - assert(rep->IsSubstring()); + assert(rep->tag == SUBSTRING); offset += rep->substring()->start; rep = rep->substring()->child; } @@ -1749,7 +1751,6 @@ char Cord::operator[](size_t i) const { } absl::string_view Cord::FlattenSlowPath() { - assert(contents_.is_tree()); size_t total_size = size(); CordRep* new_rep; char* new_buffer; @@ -1757,9 +1758,9 @@ absl::string_view Cord::FlattenSlowPath() { // Try to put the contents into a new flat rep. If they won't fit in the // biggest possible flat node, use an external rep instead. if (total_size <= kMaxFlatLength) { - new_rep = CordRepFlat::New(total_size); + new_rep = NewFlat(total_size); new_rep->length = total_size; - new_buffer = new_rep->flat()->Data(); + new_buffer = new_rep->data; CopyToArraySlowPath(new_buffer); } else { new_buffer = std::allocator<char>().allocate(total_size); @@ -1770,35 +1771,29 @@ absl::string_view Cord::FlattenSlowPath() { s.size()); }); } - CordzUpdateScope scope(contents_.cordz_info(), CordzUpdateTracker::kFlatten); - CordRep::Unref(contents_.as_tree()); - contents_.SetTree(new_rep, scope); + Unref(contents_.tree()); + contents_.set_tree(new_rep); return absl::string_view(new_buffer, total_size); } /* static */ bool Cord::GetFlatAux(CordRep* rep, absl::string_view* fragment) { assert(rep != nullptr); - if (rep->IsFlat()) { - *fragment = absl::string_view(rep->flat()->Data(), rep->length); + if (rep->tag >= FLAT) { + *fragment = absl::string_view(rep->data, rep->length); return true; - } else if (rep->IsExternal()) { + } else if (rep->tag == EXTERNAL) { *fragment = absl::string_view(rep->external()->base, rep->length); return true; - } else if (rep->IsBtree()) { - return rep->btree()->IsFlat(fragment); - } else if (rep->IsSubstring()) { + } else if (rep->tag == SUBSTRING) { CordRep* child = rep->substring()->child; - if (child->IsFlat()) { - *fragment = absl::string_view( - child->flat()->Data() + rep->substring()->start, rep->length); + if (child->tag >= FLAT) { + *fragment = + absl::string_view(child->data + rep->substring()->start, rep->length); return true; - } else if (child->IsExternal()) { + } else if (child->tag == EXTERNAL) { *fragment = absl::string_view( child->external()->base + rep->substring()->start, rep->length); return true; - } else if (child->IsBtree()) { - return child->btree()->IsFlat(rep->substring()->start, rep->length, - fragment); } } return false; @@ -1807,15 +1802,6 @@ absl::string_view Cord::FlattenSlowPath() { /* static */ void Cord::ForEachChunkAux( absl::cord_internal::CordRep* rep, absl::FunctionRef<void(absl::string_view)> callback) { - if (rep->IsBtree()) { - ChunkIterator it(rep), end; - while (it != end) { - callback(*it); - ++it; - } - return; - } - assert(rep != nullptr); int stack_pos = 0; constexpr int stack_max = 128; @@ -1823,7 +1809,7 @@ absl::string_view Cord::FlattenSlowPath() { absl::cord_internal::CordRep* stack[stack_max]; absl::cord_internal::CordRep* current_node = rep; while (true) { - if (current_node->IsConcat()) { + if (current_node->tag == CONCAT) { if (stack_pos == stack_max) { // There's no more room on our stack array to add another right branch, // and the idea is to avoid allocations, so call this function @@ -1857,9 +1843,9 @@ absl::string_view Cord::FlattenSlowPath() { } } -static void DumpNode(CordRep* rep, bool include_data, std::ostream* os, - int indent) { +static void DumpNode(CordRep* rep, bool include_data, std::ostream* os) { const int kIndentStep = 1; + int indent = 0; absl::InlinedVector<CordRep*, kInlinedVectorSize> stack; absl::InlinedVector<int, kInlinedVectorSize> indents; for (;;) { @@ -1870,29 +1856,27 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os, *os << "]"; *os << " " << (IsRootBalanced(rep) ? 'b' : 'u'); *os << " " << std::setw(indent) << ""; - if (rep->IsConcat()) { + if (rep->tag == CONCAT) { *os << "CONCAT depth=" << Depth(rep) << "\n"; indent += kIndentStep; indents.push_back(indent); stack.push_back(rep->concat()->right); rep = rep->concat()->left; - } else if (rep->IsSubstring()) { + } else if (rep->tag == SUBSTRING) { *os << "SUBSTRING @ " << rep->substring()->start << "\n"; indent += kIndentStep; rep = rep->substring()->child; - } else { // Leaf or ring - if (rep->IsExternal()) { + } else { // Leaf + if (rep->tag == EXTERNAL) { *os << "EXTERNAL ["; if (include_data) *os << absl::CEscape(std::string(rep->external()->base, rep->length)); *os << "]\n"; - } else if (rep->IsFlat()) { - *os << "FLAT cap=" << rep->flat()->Capacity() << " ["; + } else { + *os << "FLAT cap=" << TagToLength(rep->tag) << " ["; if (include_data) - *os << absl::CEscape(std::string(rep->flat()->Data(), rep->length)); + *os << absl::CEscape(std::string(rep->data, rep->length)); *os << "]\n"; - } else { - CordRepBtree::Dump(rep, /*label=*/ "", include_data, *os); } if (stack.empty()) break; rep = stack.back(); @@ -1924,7 +1908,7 @@ static bool VerifyNode(CordRep* root, CordRep* start_node, ABSL_INTERNAL_CHECK(node->length != 0, ReportError(root, node)); } - if (node->IsConcat()) { + if (node->tag == CONCAT) { ABSL_INTERNAL_CHECK(node->concat()->left != nullptr, ReportError(root, node)); ABSL_INTERNAL_CHECK(node->concat()->right != nullptr, @@ -1936,13 +1920,13 @@ static bool VerifyNode(CordRep* root, CordRep* start_node, worklist.push_back(node->concat()->right); worklist.push_back(node->concat()->left); } - } else if (node->IsFlat()) { - ABSL_INTERNAL_CHECK(node->length <= node->flat()->Capacity(), + } else if (node->tag >= FLAT) { + ABSL_INTERNAL_CHECK(node->length <= TagToLength(node->tag), ReportError(root, node)); - } else if (node->IsExternal()) { + } else if (node->tag == EXTERNAL) { ABSL_INTERNAL_CHECK(node->external()->base != nullptr, ReportError(root, node)); - } else if (node->IsSubstring()) { + } else if (node->tag == SUBSTRING) { ABSL_INTERNAL_CHECK( node->substring()->start < node->substring()->child->length, ReportError(root, node)); @@ -1971,7 +1955,7 @@ static bool VerifyNode(CordRep* root, CordRep* start_node, while (true) { const CordRep* next_node = nullptr; - if (cur_node->IsConcat()) { + if (cur_node->tag == CONCAT) { total_mem_usage += sizeof(CordRepConcat); const CordRep* left = cur_node->concat()->left; if (!RepMemoryUsageLeaf(left, &total_mem_usage)) { @@ -1985,21 +1969,9 @@ static bool VerifyNode(CordRep* root, CordRep* start_node, } next_node = right; } - } else if (cur_node->IsBtree()) { - total_mem_usage += sizeof(CordRepBtree); - const CordRepBtree* node = cur_node->btree(); - if (node->height() == 0) { - for (const CordRep* edge : node->Edges()) { - RepMemoryUsageDataEdge(edge, &total_mem_usage); - } - } else { - for (const CordRep* edge : node->Edges()) { - tree_stack.push_back(edge); - } - } } else { // Since cur_node is not a leaf or a concat node it must be a substring. - assert(cur_node->IsSubstring()); + assert(cur_node->tag == SUBSTRING); total_mem_usage += sizeof(CordRepSubstring); next_node = cur_node->substring()->child; if (RepMemoryUsageLeaf(next_node, &total_mem_usage)) { @@ -2026,14 +1998,14 @@ std::ostream& operator<<(std::ostream& out, const Cord& cord) { } namespace strings_internal { -size_t CordTestAccess::FlatOverhead() { return cord_internal::kFlatOverhead; } -size_t CordTestAccess::MaxFlatLength() { return cord_internal::kMaxFlatLength; } +size_t CordTestAccess::FlatOverhead() { return kFlatOverhead; } +size_t CordTestAccess::MaxFlatLength() { return kMaxFlatLength; } size_t CordTestAccess::FlatTagToLength(uint8_t tag) { - return cord_internal::TagToLength(tag); + return TagToLength(tag); } uint8_t CordTestAccess::LengthToTag(size_t s) { ABSL_INTERNAL_CHECK(s <= kMaxFlatLength, absl::StrCat("Invalid length ", s)); - return cord_internal::AllocatedSizeToTag(s + cord_internal::kFlatOverhead); + return AllocatedSizeToTag(s + kFlatOverhead); } size_t CordTestAccess::SizeofCordRepConcat() { return sizeof(CordRepConcat); } size_t CordTestAccess::SizeofCordRepExternal() { |