From 22771d471930ce88e1e75d0ca9dd8c65a7b0f895 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 20 Jan 2021 12:39:22 -0800 Subject: Export of internal Abseil changes -- 642ab296a2c9629c44f3f2ce6911cd2488bcf416 by Derek Mauro : Remove an obsolete check in CMakeLists.txt PiperOrigin-RevId: 352852564 -- ce78cb96bcfd162737dbcf35005da3d1d6a3486b by Abseil Team : Clarify that the calling *thread* must have locked the mutex in order to unlock it. PiperOrigin-RevId: 352801804 -- 24e1f5f72756046f5265abf618e951c341f09b8d by Derek Mauro : Fixes failing CMake string comparisons https://cmake.org/cmake/help/latest/policy/CMP0054.html Fixes #791 PiperOrigin-RevId: 352791054 -- 0ac10bc3f4dca2c4c4b51d7b8196a2eaee9537a1 by Abseil Team : Introduce CordRepRing class This change introduces the CordRepRing class that implements all the lower level / internal implementation for upcoming CordRepRing ring buffer support in cord. PiperOrigin-RevId: 352771994 -- 4bd36dda61760785844f0f29f26d90cc18046f75 by Abseil Team : Optimize InlineData representation for cord sampling (cordz) This CL changes InlineData to allow us to store a (future) Cordz Info pointer directly into the inline representation: - make InlineData a class that provides a public API to set the active union members (tree or chars) and safely access that data. - change 'tree' and 'profiled' bits to be the 2 least significant bits, allowing us 62 continquous bits for storing a Cordz Info pointer. PiperOrigin-RevId: 352642411 -- dc55ba71bbce0e6a83e05a453990c51ac3d68426 by Mark Barolak : Add unit test coverage for the mutating overload of absl::AsciiStrToLower. PiperOrigin-RevId: 352626006 GitOrigin-RevId: 642ab296a2c9629c44f3f2ce6911cd2488bcf416 Change-Id: I6c5929dd830d3c630e14e7fd5387fc3e25a69100 --- absl/copts/AbseilConfigureCopts.cmake | 16 +- absl/strings/BUILD.bazel | 23 + absl/strings/CMakeLists.txt | 21 + absl/strings/ascii_test.cc | 4 + absl/strings/cord.cc | 119 +-- absl/strings/cord.h | 63 +- absl/strings/cord_ring_test.cc | 1572 ++++++++++++++++++++++++++++++++ absl/strings/internal/cord_internal.cc | 4 + absl/strings/internal/cord_internal.h | 206 ++++- absl/strings/internal/cord_rep_flat.h | 4 +- absl/strings/internal/cord_rep_ring.cc | 895 ++++++++++++++++++ absl/strings/internal/cord_rep_ring.h | 576 ++++++++++++ absl/synchronization/mutex.h | 2 +- absl/types/CMakeLists.txt | 4 - 14 files changed, 3367 insertions(+), 142 deletions(-) create mode 100644 absl/strings/cord_ring_test.cc create mode 100644 absl/strings/internal/cord_rep_ring.cc create mode 100644 absl/strings/internal/cord_rep_ring.h (limited to 'absl') diff --git a/absl/copts/AbseilConfigureCopts.cmake b/absl/copts/AbseilConfigureCopts.cmake index acd46d04..90a1449d 100644 --- a/absl/copts/AbseilConfigureCopts.cmake +++ b/absl/copts/AbseilConfigureCopts.cmake @@ -12,16 +12,16 @@ else() set(ABSL_BUILD_DLL FALSE) endif() -if("${CMAKE_SYSTEM_PROCESSOR}" MATCHES "x86_64|amd64|AMD64") +if(CMAKE_SYSTEM_PROCESSOR MATCHES "x86_64|amd64|AMD64") if (MSVC) set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_MSVC_X64_FLAGS}") else() set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_X64_FLAGS}") endif() -elseif("${CMAKE_SYSTEM_PROCESSOR}" MATCHES "arm.*|aarch64") - if ("${CMAKE_SIZEOF_VOID_P}" STREQUAL "8") +elseif(CMAKE_SYSTEM_PROCESSOR MATCHES "arm.*|aarch64") + if (CMAKE_SIZEOF_VOID_P STREQUAL "8") set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_ARM64_FLAGS}") - elseif("${CMAKE_SIZEOF_VOID_P}" STREQUAL "4") + elseif(CMAKE_SIZEOF_VOID_P STREQUAL "4") set(ABSL_RANDOM_RANDEN_COPTS "${ABSL_RANDOM_HWAES_ARM32_FLAGS}") else() message(WARNING "Value of CMAKE_SIZEOF_VOID_P (${CMAKE_SIZEOF_VOID_P}) is not supported.") @@ -32,10 +32,10 @@ else() endif() -if("${CMAKE_CXX_COMPILER_ID}" STREQUAL "GNU") +if(CMAKE_CXX_COMPILER_ID STREQUAL "GNU") set(ABSL_DEFAULT_COPTS "${ABSL_GCC_FLAGS}") set(ABSL_TEST_COPTS "${ABSL_GCC_FLAGS};${ABSL_GCC_TEST_FLAGS}") -elseif("${CMAKE_CXX_COMPILER_ID}" MATCHES "Clang") +elseif(CMAKE_CXX_COMPILER_ID STREQUAL "Clang") # MATCHES so we get both Clang and AppleClang if(MSVC) # clang-cl is half MSVC, half LLVM @@ -45,7 +45,7 @@ elseif("${CMAKE_CXX_COMPILER_ID}" MATCHES "Clang") else() set(ABSL_DEFAULT_COPTS "${ABSL_LLVM_FLAGS}") set(ABSL_TEST_COPTS "${ABSL_LLVM_FLAGS};${ABSL_LLVM_TEST_FLAGS}") - if("${CMAKE_CXX_COMPILER_ID}" STREQUAL "Clang") + if(CMAKE_CXX_COMPILER_ID STREQUAL "Clang") # AppleClang doesn't have lsan # https://developer.apple.com/documentation/code_diagnostics if(NOT CMAKE_CXX_COMPILER_VERSION VERSION_LESS 3.5) @@ -54,7 +54,7 @@ elseif("${CMAKE_CXX_COMPILER_ID}" MATCHES "Clang") endif() endif() endif() -elseif("${CMAKE_CXX_COMPILER_ID}" STREQUAL "MSVC") +elseif(CMAKE_CXX_COMPILER_ID STREQUAL "MSVC") set(ABSL_DEFAULT_COPTS "${ABSL_MSVC_FLAGS}") set(ABSL_TEST_COPTS "${ABSL_MSVC_FLAGS};${ABSL_MSVC_TEST_FLAGS}") set(ABSL_DEFAULT_LINKOPTS "${ABSL_MSVC_LINKOPTS}") diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 70016791..d7c322f6 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -269,10 +269,12 @@ cc_library( name = "cord_internal", srcs = [ "internal/cord_internal.cc", + "internal/cord_rep_ring.cc", ], hdrs = [ "internal/cord_internal.h", "internal/cord_rep_flat.h", + "internal/cord_rep_ring.h", ], copts = ABSL_DEFAULT_COPTS, visibility = [ @@ -281,9 +283,13 @@ cc_library( deps = [ ":strings", "//absl/base:base_internal", + "//absl/base:config", "//absl/base:core_headers", + "//absl/base:raw_logging_internal", + "//absl/base:throw_delegate", "//absl/container:compressed_tuple", "//absl/container:inlined_vector", + "//absl/container:layout", "//absl/meta:type_traits", ], ) @@ -347,6 +353,23 @@ cc_test( ], ) +cc_test( + name = "cord_ring_test", + size = "medium", + srcs = ["cord_ring_test.cc"], + copts = ABSL_TEST_COPTS, + visibility = ["//visibility:private"], + deps = [ + ":cord_internal", + ":strings", + "//absl/base:config", + "//absl/base:core_headers", + "//absl/base:raw_logging_internal", + "//absl/debugging:leak_check", + "@com_google_googletest//:gtest_main", + ], +) + cc_test( name = "substitute_test", size = "small", diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 654d0fd6..a6204bf6 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -558,6 +558,8 @@ absl_cc_library( "cord.cc" "internal/cord_internal.cc" "internal/cord_internal.h" + "internal/cord_rep_ring.h" + "internal/cord_rep_ring.cc" "internal/cord_rep_flat.h" COPTS ${ABSL_DEFAULT_COPTS} @@ -565,6 +567,7 @@ absl_cc_library( absl::base absl::base_internal absl::compressed_tuple + absl::config absl::core_headers absl::endian absl::fixed_array @@ -574,6 +577,7 @@ absl_cc_library( absl::raw_logging_internal absl::strings absl::strings_internal + absl::throw_delegate absl::type_traits PUBLIC ) @@ -609,3 +613,20 @@ absl_cc_test( absl::fixed_array gmock_main ) + +absl_cc_test( + NAME + cord_ring_test + SRCS + "cord_ring_test.cc" + COPTS + ${ABSL_TEST_COPTS} + DEPS + absl::config + absl::cord + absl::strings + absl::base + absl::core_headers + absl::raw_logging_internal + gmock_main +) diff --git a/absl/strings/ascii_test.cc b/absl/strings/ascii_test.cc index 5ecd23f8..83af7825 100644 --- a/absl/strings/ascii_test.cc +++ b/absl/strings/ascii_test.cc @@ -197,11 +197,15 @@ TEST(AsciiStrTo, Lower) { const std::string str("GHIJKL"); const std::string str2("MNOPQR"); const absl::string_view sp(str2); + std::string mutable_str("STUVWX"); EXPECT_EQ("abcdef", absl::AsciiStrToLower(buf)); EXPECT_EQ("ghijkl", absl::AsciiStrToLower(str)); EXPECT_EQ("mnopqr", absl::AsciiStrToLower(sp)); + absl::AsciiStrToLower(&mutable_str); + EXPECT_EQ("stuvwx", mutable_str); + char mutable_buf[] = "Mutable"; std::transform(mutable_buf, mutable_buf + strlen(mutable_buf), mutable_buf, absl::ascii_tolower); diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index c118bdd8..df8c26d4 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc @@ -255,50 +255,49 @@ 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_tagged_size(static_cast(n)); + cord_internal::SmallMemmove(data_.as_chars(), data, n, nullify_tail); + set_inline_size(n); } inline char* Cord::InlineRep::set_data(size_t n) { assert(n <= kMaxInline); ResetToEmpty(); - set_tagged_size(static_cast(n)); - return data_.as_chars; + set_inline_size(n); + return data_.as_chars(); } inline CordRep* Cord::InlineRep::force_tree(size_t extra_hint) { - size_t len = tagged_size(); - if (len > kMaxInline) { - return data_.as_tree.rep; + if (data_.is_tree()) { + return data_.as_tree(); } + size_t len = inline_size(); CordRepFlat* result = CordRepFlat::New(len + extra_hint); result->length = len; - static_assert(kMinFlatLength >= sizeof(data_.as_chars), ""); - memcpy(result->Data(), data_.as_chars, sizeof(data_.as_chars)); + static_assert(kMinFlatLength >= sizeof(data_), ""); + memcpy(result->Data(), data_.as_chars(), sizeof(data_)); set_tree(result); return result; } inline void Cord::InlineRep::reduce_size(size_t n) { - size_t tag = tagged_size(); + size_t tag = inline_size(); assert(tag <= kMaxInline); assert(tag >= n); tag -= n; - memset(data_.as_chars + tag, 0, n); - set_tagged_size(static_cast(tag)); + memset(data_.as_chars() + tag, 0, n); + set_inline_size(static_cast(tag)); } inline void Cord::InlineRep::remove_prefix(size_t n) { - cord_internal::SmallMemmove(data_.as_chars, data_.as_chars + n, - tagged_size() - n); + cord_internal::SmallMemmove(data_.as_chars(), data_.as_chars() + n, + inline_size() - n); reduce_size(n); } void Cord::InlineRep::AppendTree(CordRep* tree) { if (tree == nullptr) return; - size_t len = tagged_size(); - if (len == 0) { + if (data_.is_empty()) { set_tree(tree); } else { set_tree(Concat(force_tree(0), tree)); @@ -307,8 +306,7 @@ void Cord::InlineRep::AppendTree(CordRep* tree) { void Cord::InlineRep::PrependTree(CordRep* tree) { assert(tree != nullptr); - size_t len = tagged_size(); - if (len == 0) { + if (data_.is_empty()) { set_tree(tree); } else { set_tree(Concat(tree, force_tree(0))); @@ -363,12 +361,14 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size, } // Try to fit in the inline buffer if possible. - size_t inline_length = tagged_size(); - if (inline_length < kMaxInline && max_length <= kMaxInline - inline_length) { - *region = data_.as_chars + inline_length; - *size = max_length; - set_tagged_size(static_cast(inline_length + max_length)); - return; + if (!is_tree()) { + size_t inline_length = inline_size(); + if (max_length <= kMaxInline - inline_length) { + *region = data_.as_chars() + inline_length; + *size = max_length; + set_inline_size(inline_length + max_length); + return; + } } CordRep* root = force_tree(max_length); @@ -390,12 +390,14 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size) { const size_t max_length = std::numeric_limits::max(); // Try to fit in the inline buffer if possible. - size_t inline_length = tagged_size(); - if (inline_length < kMaxInline) { - *region = data_.as_chars + inline_length; - *size = kMaxInline - inline_length; - set_tagged_size(kMaxInline); - return; + if (!data_.is_tree()) { + size_t inline_length = inline_size(); + if (inline_length < kMaxInline) { + *region = data_.as_chars() + inline_length; + *size = kMaxInline - inline_length; + set_inline_size(kMaxInline); + return; + } } CordRep* root = force_tree(max_length); @@ -549,24 +551,25 @@ template Cord& Cord::operator=(std::string&& src); // we keep it here to make diffs easier. 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 = tagged_size(); - if (inline_length < kMaxInline && src_size <= kMaxInline - inline_length) { - // Append new data to embedded array - set_tagged_size(static_cast(inline_length + src_size)); - memcpy(data_.as_chars + inline_length, src_data, src_size); - return; - } - - CordRep* root = tree(); size_t appended = 0; - if (root) { + CordRep* root = nullptr; + if (is_tree()) { + root = data_.as_tree(); char* region; 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; + } + // 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 @@ -578,7 +581,7 @@ void Cord::InlineRep::AppendArray(const char* src_data, size_t src_size) { root = CordRepFlat::New(std::max(size1, size2)); appended = std::min( src_size, root->flat()->Capacity() - inline_length); - memcpy(root->flat()->Data(), data_.as_chars, inline_length); + memcpy(root->flat()->Data(), data_.as_chars(), inline_length); memcpy(root->flat()->Data() + inline_length, src_data, appended); root->length = inline_length + appended; set_tree(root); @@ -684,18 +687,19 @@ void Cord::Prepend(const Cord& src) { void Cord::Prepend(absl::string_view src) { if (src.empty()) return; // memcpy(_, nullptr, 0) is undefined. - 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(&contents_), data, - InlineRep::kMaxInline + 1); - } else { - contents_.PrependTree(NewTree(src.data(), src.size(), 0)); + 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; + } } + contents_.PrependTree(NewTree(src.data(), src.size(), 0)); } template > @@ -888,7 +892,7 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const { } else if (new_size <= InlineRep::kMaxInline) { Cord::ChunkIterator it = chunk_begin(); it.AdvanceBytes(pos); - char* dest = sub_cord.contents_.data_.as_chars; + char* dest = sub_cord.contents_.data_.as_chars(); size_t remaining_size = new_size; while (remaining_size > it->size()) { cord_internal::SmallMemmove(dest, it->data(), it->size()); @@ -897,7 +901,7 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const { ++it; } cord_internal::SmallMemmove(dest, it->data(), remaining_size); - sub_cord.contents_.set_tagged_size(new_size); + sub_cord.contents_.set_inline_size(new_size); } else { sub_cord.contents_.set_tree(NewSubRange(tree, pos, new_size)); } @@ -1086,9 +1090,8 @@ bool ComputeCompareResult(int memcmp_res) { // Helper routine. Locates the first flat chunk of the Cord without // initializing the iterator. inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const { - size_t n = tagged_size(); - if (n <= kMaxInline) { - return absl::string_view(data_.as_chars, n); + if (!is_tree()) { + return absl::string_view(data_.as_chars(), data_.inline_size()); } CordRep* node = tree(); diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 7136f034..9d8764a0 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -665,8 +665,6 @@ class Cord { public: static constexpr unsigned char kMaxInline = cord_internal::kMaxInline; static_assert(kMaxInline >= sizeof(absl::cord_internal::CordRep*), ""); - static constexpr unsigned char kTreeFlag = cord_internal::kTreeFlag; - static constexpr unsigned char kProfiledFlag = cord_internal::kProfiledFlag; constexpr InlineRep() : data_() {} InlineRep(const InlineRep& src); @@ -685,6 +683,7 @@ class Cord { char* set_data(size_t n); // Write data to the result // Returns nullptr if holding bytes absl::cord_internal::CordRep* tree() const; + absl::cord_internal::CordRep* as_tree() const; // Discards old pointer, if any void set_tree(absl::cord_internal::CordRep* rep); // Replaces a tree with a new root. This is faster than set_tree, but it @@ -728,13 +727,13 @@ class Cord { memcpy(&(*dst)[0], &data_, sizeof(data_) - 1); // erase is faster than resize because the logic for memory allocation is // not needed. - dst->erase(tagged_size()); + dst->erase(inline_size()); } // Copies the inline contents into `dst`. Assumes the cord is not empty. void CopyToArray(char* dst) const; - bool is_tree() const { return tagged_size() > kMaxInline; } + bool is_tree() const { return data_.is_tree(); } private: friend class Cord; @@ -745,14 +744,8 @@ class Cord { void ResetToEmpty() { data_ = {}; } - // This uses reinterpret_cast instead of the union to avoid accessing the - // inactive union element. The tagged size is not a common prefix. - void set_tagged_size(char new_tag) { - reinterpret_cast(&data_)[kMaxInline] = new_tag; - } - char tagged_size() const { - return reinterpret_cast(&data_)[kMaxInline]; - } + void set_inline_size(size_t size) { data_.set_inline_size(size); } + size_t inline_size() const { return data_.inline_size(); } cord_internal::InlineData data_; }; @@ -948,35 +941,39 @@ inline void Cord::InlineRep::Swap(Cord::InlineRep* rhs) { } inline const char* Cord::InlineRep::data() const { - return is_tree() ? nullptr : data_.as_chars; + return is_tree() ? nullptr : data_.as_chars(); +} + +inline absl::cord_internal::CordRep* Cord::InlineRep::as_tree() const { + assert(data_.is_tree()); + return data_.as_tree(); } inline absl::cord_internal::CordRep* Cord::InlineRep::tree() const { if (is_tree()) { - return data_.as_tree.rep; + return as_tree(); } else { return nullptr; } } -inline bool Cord::InlineRep::empty() const { return tagged_size() == 0; } +inline bool Cord::InlineRep::empty() const { return data_.is_empty(); } inline size_t Cord::InlineRep::size() const { - const char tag = tagged_size(); - if (tag <= kMaxInline) return tag; - return static_cast(tree()->length); + return is_tree() ? as_tree()->length : inline_size(); } inline void Cord::InlineRep::set_tree(absl::cord_internal::CordRep* rep) { if (rep == nullptr) { ResetToEmpty(); } else { - bool was_tree = is_tree(); - data_.as_tree = {rep, {}, tagged_size()}; - if (!was_tree) { - // If we were not a tree already, set the tag. - // Otherwise, leave it alone because it might have the profile bit on. - set_tagged_size(kTreeFlag); + if (data_.is_tree()) { + // `data_` already holds a 'tree' value and an optional cordz_info value. + // Replace the tree value only, leaving the cordz_info value unchanged. + data_.set_tree(rep); + } else { + // `data_` contains inlined data: initialize data_ to tree value `rep`. + data_.make_tree(rep); } } } @@ -987,7 +984,7 @@ inline void Cord::InlineRep::replace_tree(absl::cord_internal::CordRep* rep) { set_tree(rep); return; } - data_.as_tree = {rep, {}, tagged_size()}; + data_.set_tree(rep); } inline absl::cord_internal::CordRep* Cord::InlineRep::clear() { @@ -998,9 +995,9 @@ inline absl::cord_internal::CordRep* Cord::InlineRep::clear() { inline void Cord::InlineRep::CopyToArray(char* dst) const { assert(!is_tree()); - size_t n = tagged_size(); + size_t n = inline_size(); assert(n != 0); - cord_internal::SmallMemmove(dst, data_.as_chars, n); + cord_internal::SmallMemmove(dst, data_.as_chars(), n); } constexpr inline Cord::Cord() noexcept {} @@ -1011,11 +1008,9 @@ constexpr Cord::Cord(strings_internal::StringConstant) cord_internal::kMaxInline ? cord_internal::InlineData( strings_internal::StringConstant::value) - : cord_internal::InlineData(cord_internal::AsTree{ + : cord_internal::InlineData( &cord_internal::ConstInitExternalStorage< - strings_internal::StringConstant>::value, - {}, - cord_internal::kTreeFlag})) {} + strings_internal::StringConstant>::value)) {} inline Cord& Cord::operator=(const Cord& x) { contents_ = x.contents_; @@ -1107,12 +1102,12 @@ inline bool Cord::StartsWith(absl::string_view rhs) const { inline Cord::ChunkIterator::ChunkIterator(const Cord* cord) : bytes_remaining_(cord->size()) { - if (cord->empty()) return; if (cord->contents_.is_tree()) { - stack_of_right_children_.push_back(cord->contents_.tree()); + stack_of_right_children_.push_back(cord->contents_.as_tree()); operator++(); } else { - current_chunk_ = absl::string_view(cord->contents_.data(), cord->size()); + current_chunk_ = + absl::string_view(cord->contents_.data(), bytes_remaining_); } } diff --git a/absl/strings/cord_ring_test.cc b/absl/strings/cord_ring_test.cc new file mode 100644 index 00000000..7d75e106 --- /dev/null +++ b/absl/strings/cord_ring_test.cc @@ -0,0 +1,1572 @@ +// Copyright 2020 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 +#include +#include +#include +#include + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/base/macros.h" +#include "absl/debugging/leak_check.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_ring.h" +#include "absl/strings/str_cat.h" +#include "absl/strings/string_view.h" + +extern thread_local bool cord_ring; + +// TOOD(b/177688959): weird things happened with the original test +#define ASAN_BUG_177688959_FIXED false + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace { + +using RandomEngine = std::mt19937_64; + +using ::absl::cord_internal::CordRep; +using ::absl::cord_internal::CordRepConcat; +using ::absl::cord_internal::CordRepExternal; +using ::absl::cord_internal::CordRepFlat; +using ::absl::cord_internal::CordRepRing; +using ::absl::cord_internal::CordRepSubstring; + +using ::absl::cord_internal::CONCAT; +using ::absl::cord_internal::EXTERNAL; +using ::absl::cord_internal::SUBSTRING; + +using testing::ElementsAre; +using testing::ElementsAreArray; +using testing::Eq; +using testing::Ge; +using testing::Le; +using testing::Lt; +using testing::Ne; +using testing::SizeIs; + +using index_type = CordRepRing::index_type; + +enum InputShareMode { kPrivate, kShared, kSharedIndirect }; + +// TestParam class used by all test fixtures. +// Not all fixtures use all possible input combinations +struct TestParam { + TestParam() = default; + explicit TestParam(InputShareMode input_share_mode) + : input_share_mode(input_share_mode) {} + + // Run the test with the 'rep under test' to be privately owned. + // Otherwise, the rep has a shared ref count of 2 or higher. + bool refcount_is_one = true; + + // Run the test with the 'rep under test' being allocated with enough capacity + // to accommodate any modifications made to it. Otherwise, the rep has zero + // extra (reserve) capacity. + bool with_capacity = true; + + // For test providing possibly shared input such as Append(.., CordpRep*), + // this field defines if that input is adopted with a refcount of one + // (privately owned / donated), or shared. For composite inputs such as + // 'substring of flat', we also have the 'shared indirect' value which means + // the top level node is not shared, but the contained child node is shared. + InputShareMode input_share_mode = kPrivate; + + std::string ToString() const { + return absl::StrCat(refcount_is_one ? "Private" : "Shared", + with_capacity ? "" : "_NoCapacity", + (input_share_mode == kPrivate) ? "" + : (input_share_mode == kShared) + ? "_SharedInput" + : "_IndirectSharedInput"); + } +}; +using TestParams = std::vector; + +// Matcher validating when mutable copies are required / performed. +MATCHER_P2(EqIfPrivate, param, rep, + absl::StrCat("Equal 0x", absl::Hex(rep), " if private")) { + return param.refcount_is_one ? arg == rep : arg != rep; +} + +// Matcher validating when mutable copies are required / performed. +MATCHER_P2(EqIfPrivateAndCapacity, param, rep, + absl::StrCat("Equal 0x", absl::Hex(rep), + " if private and capacity")) { + return (param.refcount_is_one && param.with_capacity) ? arg == rep + : arg != rep; +} + +MATCHER_P2(EqIfInputPrivate, param, rep, "Equal if input is private") { + return param.input_share_mode == kPrivate ? arg == rep : arg != rep; +} + +// Matcher validating the core in-variants of the CordRepRing instance. +MATCHER(IsValidRingBuffer, "RingBuffer is valid") { + std::stringstream ss; + if (!arg->IsValid(ss)) { + *result_listener << "\nERROR: " << ss.str() << "\nRING = " << *arg; + return false; + } + return true; +} + +// Returns the flats contained in the provided CordRepRing +std::vector ToFlats(const CordRepRing* r) { + std::vector flats; + flats.reserve(r->entries()); + index_type pos = r->head(); + do { + flats.push_back(r->entry_data(pos)); + } while ((pos = r->advance(pos)) != r->tail()); + return flats; +} + +class not_a_string_view { + public: + explicit not_a_string_view(absl::string_view s) + : data_(s.data()), size_(s.size()) {} + explicit not_a_string_view(const void* data, size_t size) + : data_(data), size_(size) {} + + not_a_string_view remove_prefix(size_t n) const { + return not_a_string_view(static_cast(data_) + n, size_ - n); + } + + not_a_string_view remove_suffix(size_t n) const { + return not_a_string_view(data_, size_ - n); + } + + const void* data() const { return data_; } + size_t size() const { return size_; } + + private: + const void* data_; + size_t size_; +}; + +bool operator==(not_a_string_view lhs, not_a_string_view rhs) { + return lhs.data() == rhs.data() && lhs.size() == rhs.size(); +} + +std::ostream& operator<<(std::ostream& s, not_a_string_view rhs) { + return s << "{ data: " << rhs.data() << " size: " << rhs.size() << "}"; +} + +std::vector ToRawFlats(const CordRepRing* r) { + std::vector flats; + flats.reserve(r->entries()); + index_type pos = r->head(); + do { + flats.emplace_back(r->entry_data(pos)); + } while ((pos = r->advance(pos)) != r->tail()); + return flats; +} + +// Returns the value contained in the provided CordRepRing +std::string ToString(const CordRepRing* r) { + std::string value; + value.reserve(r->length); + index_type pos = r->head(); + do { + absl::string_view sv = r->entry_data(pos); + value.append(sv.data(), sv.size()); + } while ((pos = r->advance(pos)) != r->tail()); + return value; +} + +// Creates a flat for testing +CordRep* MakeFlat(absl::string_view s, size_t extra = 0) { + CordRepFlat* flat = CordRepFlat::New(s.length() + extra); + memcpy(flat->Data(), s.data(), s.length()); + flat->length = s.length(); + return flat; +} + +// Creates an external node for testing +CordRepExternal* MakeExternal(absl::string_view s) { + struct Rep : public CordRepExternal { + std::string s; + explicit Rep(absl::string_view s) : s(s) { + this->tag = EXTERNAL; + this->base = s.data(); + this->length = s.length(); + this->releaser_invoker = [](CordRepExternal* self) { + delete static_cast(self); + }; + } + }; + return new Rep(s); +} + +CordRepExternal* MakeFakeExternal(size_t length) { + struct Rep : public CordRepExternal { + std::string s; + explicit Rep(size_t len) { + this->tag = EXTERNAL; + this->base = this->storage; + this->length = len; + this->releaser_invoker = [](CordRepExternal* self) { + delete static_cast(self); + }; + } + }; + return new Rep(length); +} + +// Creates a flat or an external node for testing depending on the size. +CordRep* MakeLeaf(absl::string_view s, size_t extra = 0) { + if (s.size() <= absl::cord_internal::kMaxFlatLength) { + return MakeFlat(s, extra); + } else { + return MakeExternal(s); + } +} + +// Creates a substring node +CordRepSubstring* MakeSubstring(size_t start, size_t len, CordRep* rep) { + auto* sub = new CordRepSubstring; + sub->tag = SUBSTRING; + sub->start = start; + sub->length = (len <= 0) ? rep->length - start + len : len; + sub->child = rep; + return sub; +} + +// Creates a substring node removing the specified prefix +CordRepSubstring* RemovePrefix(size_t start, CordRep* rep) { + return MakeSubstring(start, rep->length - start, rep); +} + +// Creates a substring node removing the specified suffix +CordRepSubstring* RemoveSuffix(size_t length, CordRep* rep) { + return MakeSubstring(0, rep->length - length, rep); +} + +CordRepConcat* MakeConcat(CordRep* left, CordRep* right, int depth = 0) { + auto* concat = new CordRepConcat; + concat->tag = CONCAT; + concat->length = left->length + right->length; + concat->left = left; + concat->right = right; + concat->set_depth(depth); + return concat; +} + +enum Composition { kMix, kAppend, kPrepend }; + +Composition RandomComposition() { + RandomEngine rng(testing::GTEST_FLAG(random_seed)); + return (rng() & 1) ? kMix : ((rng() & 1) ? kAppend : kPrepend); +} + +absl::string_view ToString(Composition composition) { + switch (composition) { + case kAppend: + return "Append"; + case kPrepend: + return "Prepend"; + case kMix: + return "Mix"; + } + assert(false); + return "???"; +} + +constexpr const char* kFox = "The quick brown fox jumps over the lazy dog"; +constexpr const char* kFoxFlats[] = {"The ", "quick ", "brown ", + "fox ", "jumps ", "over ", + "the ", "lazy ", "dog"}; +constexpr const char* kAlphabet = "abcdefghijklmnopqrstuvwxyz"; + +CordRepRing* FromFlats(Span flats, + Composition composition = kAppend) { + if (flats.empty()) return nullptr; + CordRepRing* ring = nullptr; + switch (composition) { + case kAppend: + ring = CordRepRing::Create(MakeLeaf(flats.front()), flats.size() - 1); + for (int i = 1; i < flats.size(); ++i) { + ring = CordRepRing::Append(ring, MakeLeaf(flats[i])); + } + break; + case kPrepend: + ring = CordRepRing::Create(MakeLeaf(flats.back()), flats.size() - 1); + for (int i = static_cast(flats.size() - 2); i >= 0; --i) { + ring = CordRepRing::Prepend(ring, MakeLeaf(flats[i])); + } + break; + case kMix: + size_t middle1 = flats.size() / 2, middle2 = middle1; + ring = CordRepRing::Create(MakeLeaf(flats[middle1]), flats.size() - 1); + if (!flats.empty()) { + if ((flats.size() & 1) == 0) { + ring = CordRepRing::Prepend(ring, MakeLeaf(flats[--middle1])); + } + for (int i = 1; i <= middle1; ++i) { + ring = CordRepRing::Prepend(ring, MakeLeaf(flats[middle1 - i])); + ring = CordRepRing::Append(ring, MakeLeaf(flats[middle2 + i])); + } + } + break; + } + EXPECT_THAT(ToFlats(ring), ElementsAreArray(flats)); + return ring; +} + +std::ostream& operator<<(std::ostream& s, const TestParam& param) { + return s << param.ToString(); +} + +std::string TestParamToString(const testing::TestParamInfo& info) { + return info.param.ToString(); +} + +class CordRingTest : public testing::Test { + public: + ~CordRingTest() override { +#if ASAN_BUG_177688959_FIXED + for (CordRep* rep : unrefs_) { + CordRep::Unref(rep); + } +#endif + } + + template + CordRepType* NeedsUnref(CordRepType* rep) { + assert(rep); +#if ASAN_BUG_177688959_FIXED + unrefs_.push_back(rep); +#endif + return rep; + } + + template + CordRepType* Ref(CordRepType* rep) { + CordRep::Ref(rep); + return NeedsUnref(rep); + } + + void Unref(CordRep* rep) { +#if !ASAN_BUG_177688959_FIXED + CordRep::Unref(rep); +#endif + } + + private: +#if ASAN_BUG_177688959_FIXED + std::vector unrefs_; +#endif +}; + +class CordRingTestWithParam : public testing::TestWithParam { + public: + ~CordRingTestWithParam() override { +#if ASAN_BUG_177688959_FIXED + for (CordRep* rep : unrefs_) { + CordRep::Unref(rep); + } +#endif + } + + CordRepRing* CreateWithCapacity(CordRep* child, size_t extra_capacity) { + if (!GetParam().with_capacity) extra_capacity = 0; + CordRepRing* ring = CordRepRing::Create(child, extra_capacity); + ring->SetCapacityForTesting(1 + extra_capacity); + return RefIfShared(ring); + } + + bool Shared() const { return !GetParam().refcount_is_one; } + bool InputShared() const { return GetParam().input_share_mode == kShared; } + bool InputSharedIndirect() const { + return GetParam().input_share_mode == kSharedIndirect; + } + + template + CordRepType* NeedsUnref(CordRepType* rep) { + assert(rep); +#if ASAN_BUG_177688959_FIXED + unrefs_.push_back(rep); +#endif + return rep; + } + + template + CordRepType* Ref(CordRepType* rep) { + CordRep::Ref(rep); + return NeedsUnref(rep); + } + + void Unref(CordRep* rep) { +#if !ASAN_BUG_177688959_FIXED + CordRep::Unref(rep); +#endif + } + + template + CordRepType* RefIfShared(CordRepType* rep) { + return Shared() ? Ref(rep) : rep; + } + + void UnrefIfShared(CordRep* rep) { + if (Shared()) Unref(rep); + } + + template + CordRepType* RefIfInputShared(CordRepType* rep) { + return InputShared() ? Ref(rep) : rep; + } + + void UnrefIfInputShared(CordRep* rep) { + if (InputShared()) Unref(rep); + } + + template + CordRepType* RefIfInputSharedIndirect(CordRepType* rep) { + return InputSharedIndirect() ? Ref(rep) : rep; + } + + void UnrefIfInputSharedIndirect(CordRep* rep) { + if (InputSharedIndirect()) Unref(rep); + } + + private: +#if ASAN_BUG_177688959_FIXED + std::vector unrefs_; +#endif +}; + +class CordRingCreateTest : public CordRingTestWithParam { + public: + static TestParams CreateTestParams() { + TestParams params; + params.emplace_back(InputShareMode::kPrivate); + params.emplace_back(InputShareMode::kShared); + return params; + } +}; + +class CordRingSubTest : public CordRingTestWithParam { + public: + static TestParams CreateTestParams() { + TestParams params; + for (bool refcount_is_one : {true, false}) { + TestParam param; + param.refcount_is_one = refcount_is_one; + params.push_back(param); + } + return params; + } +}; + +class CordRingBuildTest : public CordRingTestWithParam { + public: + static TestParams CreateTestParams() { + TestParams params; + for (bool refcount_is_one : {true, false}) { + for (bool with_capacity : {true, false}) { + TestParam param; + param.refcount_is_one = refcount_is_one; + param.with_capacity = with_capacity; + params.push_back(param); + } + } + return params; + } +}; + +class CordRingCreateFromTreeTest : public CordRingTestWithParam { + public: + static TestParams CreateTestParams() { + TestParams params; + params.emplace_back(InputShareMode::kPrivate); + params.emplace_back(InputShareMode::kShared); + params.emplace_back(InputShareMode::kSharedIndirect); + return params; + } +}; + +class CordRingBuildInputTest : public CordRingTestWithParam { + public: + static TestParams CreateTestParams() { + TestParams params; + for (bool refcount_is_one : {true, false}) { + for (bool with_capacity : {true, false}) { + for (InputShareMode share_mode : {kPrivate, kShared, kSharedIndirect}) { + TestParam param; + param.refcount_is_one = refcount_is_one; + param.with_capacity = with_capacity; + param.input_share_mode = share_mode; + params.push_back(param); + } + } + } + return params; + } +}; + +INSTANTIATE_TEST_CASE_P(WithParam, CordRingSubTest, + testing::ValuesIn(CordRingSubTest::CreateTestParams()), + TestParamToString); + +INSTANTIATE_TEST_CASE_P( + WithParam, CordRingCreateTest, + testing::ValuesIn(CordRingCreateTest::CreateTestParams()), + TestParamToString); + +INSTANTIATE_TEST_CASE_P( + WithParam, CordRingCreateFromTreeTest, + testing::ValuesIn(CordRingCreateFromTreeTest::CreateTestParams()), + TestParamToString); + +INSTANTIATE_TEST_CASE_P( + WithParam, CordRingBuildTest, + testing::ValuesIn(CordRingBuildTest::CreateTestParams()), + TestParamToString); + +INSTANTIATE_TEST_CASE_P( + WithParam, CordRingBuildInputTest, + testing::ValuesIn(CordRingBuildInputTest::CreateTestParams()), + TestParamToString); + +TEST_P(CordRingCreateTest, CreateFromFlat) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + CordRepRing* result = NeedsUnref(CordRepRing::Create(MakeFlat(str1))); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(str1.size())); + EXPECT_THAT(ToFlats(result), ElementsAre(str1)); + Unref(result); +} + +TEST_P(CordRingCreateTest, CreateFromRing) { + CordRepRing* ring = RefIfShared(FromFlats(kFoxFlats)); + CordRepRing* result = NeedsUnref(CordRepRing::Create(ring)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivate(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAreArray(kFoxFlats)); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingCreateFromTreeTest, CreateFromSubstringRing) { + CordRepRing* ring = RefIfInputSharedIndirect(FromFlats(kFoxFlats)); + CordRep* sub = RefIfInputShared(MakeSubstring(2, 11, ring)); + CordRepRing* result = NeedsUnref(CordRepRing::Create(sub)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfInputPrivate(GetParam(), ring)); + EXPECT_THAT(ToString(result), string_view(kFox).substr(2, 11)); + UnrefIfInputSharedIndirect(ring); + UnrefIfInputShared(sub); + Unref(result); +} + +TEST_F(CordRingTest, CreateWithIllegalExtraCapacity) { + CordRep* flat = NeedsUnref(MakeFlat("Hello world")); +#if defined(ABSL_HAVE_EXCEPTIONS) + try { + CordRepRing::Create(flat, CordRepRing::kMaxCapacity); + GTEST_FAIL() << "expected std::length_error exception"; + } catch (const std::length_error&) { + } +#elif defined(GTEST_HAS_DEATH_TEST) + EXPECT_DEATH(CordRepRing::Create(flat, CordRepRing::kMaxCapacity), ".*"); +#endif + Unref(flat); +} + +TEST_P(CordRingCreateFromTreeTest, CreateFromSubstringOfFlat) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + auto* flat = RefIfInputShared(MakeFlat(str1)); + auto* child = RefIfInputSharedIndirect(MakeSubstring(4, 20, flat)); + CordRepRing* result = NeedsUnref(CordRepRing::Create(child)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(20)); + EXPECT_THAT(ToFlats(result), ElementsAre(str1.substr(4, 20))); + Unref(result); + UnrefIfInputShared(flat); + UnrefIfInputSharedIndirect(child); +} + +TEST_P(CordRingCreateTest, CreateFromExternal) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + auto* child = RefIfInputShared(MakeExternal(str1)); + CordRepRing* result = NeedsUnref(CordRepRing::Create(child)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(str1.size())); + EXPECT_THAT(ToFlats(result), ElementsAre(str1)); + Unref(result); + UnrefIfInputShared(child); +} + +TEST_P(CordRingCreateFromTreeTest, CreateFromSubstringOfExternal) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + auto* external = RefIfInputShared(MakeExternal(str1)); + auto* child = RefIfInputSharedIndirect(MakeSubstring(1, 24, external)); + CordRepRing* result = NeedsUnref(CordRepRing::Create(child)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(24)); + EXPECT_THAT(ToFlats(result), ElementsAre(str1.substr(1, 24))); + Unref(result); + UnrefIfInputShared(external); + UnrefIfInputSharedIndirect(child); +} + +TEST_P(CordRingCreateFromTreeTest, CreateFromSubstringOfLargeExternal) { + auto* external = RefIfInputShared(MakeFakeExternal(1 << 20)); + auto str = not_a_string_view(external->base, 1 << 20) + .remove_prefix(1 << 19) + .remove_suffix(6); + auto* child = + RefIfInputSharedIndirect(MakeSubstring(1 << 19, (1 << 19) - 6, external)); + CordRepRing* result = NeedsUnref(CordRepRing::Create(child)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(str.size())); + EXPECT_THAT(ToRawFlats(result), ElementsAre(str)); + Unref(result); + UnrefIfInputShared(external); + UnrefIfInputSharedIndirect(child); +} + +TEST_P(CordRingBuildInputTest, CreateFromConcat) { + CordRep* flats[] = {MakeFlat("abcdefgh"), MakeFlat("ijklm"), + MakeFlat("nopqrstuv"), MakeFlat("wxyz")}; + auto* left = MakeConcat(RefIfInputSharedIndirect(flats[0]), flats[1]); + auto* right = MakeConcat(flats[2], RefIfInputSharedIndirect(flats[3])); + auto* concat = RefIfInputShared(MakeConcat(left, right)); + CordRepRing* result = NeedsUnref(CordRepRing::Create(concat)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(26)); + EXPECT_THAT(ToString(result), Eq(kAlphabet)); + UnrefIfInputSharedIndirect(flats[0]); + UnrefIfInputSharedIndirect(flats[3]); + UnrefIfInputShared(concat); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, CreateFromSubstringConcat) { + for (size_t off = 0; off < 26; ++off) { + for (size_t len = 1; len < 26 - off; ++len) { + CordRep* flats[] = {MakeFlat("abcdefgh"), MakeFlat("ijklm"), + MakeFlat("nopqrstuv"), MakeFlat("wxyz")}; + auto* left = MakeConcat(RefIfInputSharedIndirect(flats[0]), flats[1]); + auto* right = MakeConcat(flats[2], RefIfInputSharedIndirect(flats[3])); + auto* concat = MakeConcat(left, right); + auto* child = RefIfInputShared(MakeSubstring(off, len, concat)); + CordRepRing* result = NeedsUnref(CordRepRing::Create(child)); + ASSERT_THAT(result, IsValidRingBuffer()); + ASSERT_THAT(result->length, Eq(len)); + ASSERT_THAT(ToString(result), string_view(kAlphabet).substr(off, len)); + UnrefIfInputSharedIndirect(flats[0]); + UnrefIfInputSharedIndirect(flats[3]); + UnrefIfInputShared(child); + Unref(result); + } + } +} + +TEST_P(CordRingCreateTest, Properties) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + CordRepRing* result = NeedsUnref(CordRepRing::Create(MakeFlat(str1), 120)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->head(), Eq(0)); + EXPECT_THAT(result->tail(), Eq(1)); + EXPECT_THAT(result->capacity(), Ge(120 + 1)); + EXPECT_THAT(result->capacity(), Le(2 * 120 + 1)); + EXPECT_THAT(result->entries(), Eq(1)); + EXPECT_THAT(result->begin_pos(), Eq(0)); + Unref(result); +} + +TEST_P(CordRingCreateTest, EntryForNewFlat) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + CordRep* child = MakeFlat(str1); + CordRepRing* result = NeedsUnref(CordRepRing::Create(child, 120)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->entry_child(0), Eq(child)); + EXPECT_THAT(result->entry_end_pos(0), Eq(str1.length())); + EXPECT_THAT(result->entry_data_offset(0), Eq(0)); + Unref(result); +} + +TEST_P(CordRingCreateTest, EntryForNewFlatSubstring) { + absl::string_view str1 = "1234567890abcdefghijklmnopqrstuvwxyz"; + CordRep* child = MakeFlat(str1); + CordRep* substring = MakeSubstring(10, 26, child); + CordRepRing* result = NeedsUnref(CordRepRing::Create(substring, 1)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->entry_child(0), Eq(child)); + EXPECT_THAT(result->entry_end_pos(0), Eq(26)); + EXPECT_THAT(result->entry_data_offset(0), Eq(10)); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendFlat) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, MakeFlat(str2))); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(result->length, Eq(str1.size() + str2.size())); + EXPECT_THAT(ToFlats(result), ElementsAre(str1, str2)); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, PrependFlat) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, MakeFlat(str2))); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(result->length, Eq(str1.size() + str2.size())); + EXPECT_THAT(ToFlats(result), ElementsAre(str2, str1)); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendString) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(result->length, Eq(str1.size() + str2.size())); + EXPECT_THAT(ToFlats(result), ElementsAre(str1, str2)); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendStringHavingExtra) { + absl::string_view str1 = "1234"; + absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + CordRepRing* ring = CreateWithCapacity(MakeFlat(str1, 26), 0); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(str1.size() + str2.size())); + EXPECT_THAT(result, EqIfPrivate(GetParam(), ring)); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendStringHavingPartialExtra) { + absl::string_view str1 = "1234"; + absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + + // Create flat with at least one extra byte. We don't expect to have sized + // alloc and capacity rounding to grant us enough to not make it partial. + auto* flat = MakeFlat(str1, 1); + size_t avail = flat->flat()->Capacity() - flat->length; + ASSERT_THAT(avail, Lt(str2.size())) << " adjust test for larger flats!"; + + // Construct the flats we do expect using all of `avail`. + absl::string_view str1a = str2.substr(0, avail); + absl::string_view str2a = str2.substr(avail); + + CordRepRing* ring = CreateWithCapacity(flat, 1); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(str1.size() + str2.size())); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + if (GetParam().refcount_is_one) { + EXPECT_THAT(ToFlats(result), ElementsAre(StrCat(str1, str1a), str2a)); + } else { + EXPECT_THAT(ToFlats(result), ElementsAre(str1, str2)); + } + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendStringHavingExtraInSubstring) { + absl::string_view str1 = "123456789_1234"; + absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + CordRep* flat = RemovePrefix(10, MakeFlat(str1, 26)); + CordRepRing* ring = CreateWithCapacity(flat, 0); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivate(GetParam(), ring)); + EXPECT_THAT(result->length, Eq(4 + str2.size())); + if (GetParam().refcount_is_one) { + EXPECT_THAT(ToFlats(result), ElementsAre(StrCat("1234", str2))); + } else { + EXPECT_THAT(ToFlats(result), ElementsAre("1234", str2)); + } + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendStringHavingSharedExtra) { + absl::string_view str1 = "123456789_1234"; + absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + for (int shared_type = 0; shared_type < 2; ++shared_type) { + SCOPED_TRACE(absl::StrCat("Shared extra type ", shared_type)); + + // Create a flat that is shared in some way. + CordRep* flat = nullptr; + CordRep* flat1 = nullptr; + if (shared_type == 0) { + // Shared flat + flat = CordRep::Ref(MakeFlat(str1.substr(10), 100)); + } else if (shared_type == 1) { + // Shared flat inside private substring + flat1 = CordRep::Ref(MakeFlat(str1)); + flat = RemovePrefix(10, flat1); + } else { + // Private flat inside shared substring + flat = CordRep::Ref(RemovePrefix(10, MakeFlat(str1, 100))); + } + + CordRepRing* ring = CreateWithCapacity(flat, 1); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(result->length, Eq(4 + str2.size())); + EXPECT_THAT(ToFlats(result), ElementsAre("1234", str2)); + UnrefIfShared(ring); + Unref(result); + + CordRep::Unref(shared_type == 1 ? flat1 : flat); + } +} + +TEST_P(CordRingBuildTest, AppendStringWithExtra) { + absl::string_view str1 = "1234"; + absl::string_view str2 = "1234567890"; + absl::string_view str3 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, str2, 26)); + result = CordRepRing::Append(result, str3); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(str1.size() + str2.size() + str3.size())); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre(str1, StrCat(str2, str3))); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, PrependString) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + // Use external rep to avoid appending to first flat + CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, str2)); + ASSERT_THAT(result, IsValidRingBuffer()); + if (GetParam().with_capacity && GetParam().refcount_is_one) { + EXPECT_THAT(result, Eq(ring)); + } else { + EXPECT_THAT(result, Ne(ring)); + } + EXPECT_THAT(result->length, Eq(str1.size() + str2.size())); + EXPECT_THAT(ToFlats(result), ElementsAre(str2, str1)); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, PrependStringHavingExtra) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz1234"; + absl::string_view str2 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + CordRep* flat = RemovePrefix(26, MakeFlat(str1)); + CordRepRing* ring = CreateWithCapacity(flat, 0); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, str2)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivate(GetParam(), ring)); + EXPECT_THAT(result->length, Eq(4 + str2.size())); + if (GetParam().refcount_is_one) { + EXPECT_THAT(ToFlats(result), ElementsAre(StrCat(str2, "1234"))); + } else { + EXPECT_THAT(ToFlats(result), ElementsAre(str2, "1234")); + } + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, PrependStringHavingSharedExtra) { + absl::string_view str1 = "123456789_ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + absl::string_view str2 = "abcdefghij"; + absl::string_view str1a = str1.substr(10); + for (int shared_type = 1; shared_type < 2; ++shared_type) { + SCOPED_TRACE(absl::StrCat("Shared extra type ", shared_type)); + + // Create a flat that is shared in some way. + CordRep* flat = nullptr; + CordRep* flat1 = nullptr; + if (shared_type == 1) { + // Shared flat inside private substring + flat = RemovePrefix(10, flat1 = CordRep::Ref(MakeFlat(str1))); + } else { + // Private flat inside shared substring + flat = CordRep::Ref(RemovePrefix(10, MakeFlat(str1, 100))); + } + + CordRepRing* ring = CreateWithCapacity(flat, 1); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, str2)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result->length, Eq(str1a.size() + str2.size())); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre(str2, str1a)); + UnrefIfShared(ring); + Unref(result); + CordRep::Unref(shared_type == 1 ? flat1 : flat); + } +} + +TEST_P(CordRingBuildTest, PrependStringWithExtra) { + absl::string_view str1 = "1234"; + absl::string_view str2 = "1234567890"; + absl::string_view str3 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; + CordRepRing* ring = CreateWithCapacity(MakeExternal(str1), 1); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, str2, 26)); + ASSERT_THAT(result, IsValidRingBuffer()); + result = CordRepRing::Prepend(result, str3); + EXPECT_THAT(result->length, Eq(str1.size() + str2.size() + str3.size())); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre(StrCat(str3, str2), str1)); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendPrependStringMix) { + const auto& flats = kFoxFlats; + CordRepRing* ring = CreateWithCapacity(MakeFlat(flats[4]), 8); + CordRepRing* result = ring; + for (int i = 1; i <= 4; ++i) { + result = CordRepRing::Prepend(result, flats[4 - i]); + result = CordRepRing::Append(result, flats[4 + i]); + } + UnrefIfShared(ring); + NeedsUnref(result); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToString(result), kFox); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendPrependStringMixWithExtra) { + const auto& flats = kFoxFlats; + CordRepRing* ring = CreateWithCapacity(MakeFlat(flats[4], 100), 8); + CordRepRing* result = ring; + for (int i = 1; i <= 4; ++i) { + result = CordRepRing::Prepend(result, flats[4 - i], 100); + result = CordRepRing::Append(result, flats[4 + i], 100); + } + NeedsUnref(result); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + if (GetParam().refcount_is_one) { + EXPECT_THAT(ToFlats(result), + ElementsAre("The quick brown fox ", "jumps over the lazy dog")); + } else { + EXPECT_THAT(ToFlats(result), ElementsAre("The quick brown fox ", "jumps ", + "over the lazy dog")); + } + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendPrependStringMixWithPrependedExtra) { + const auto& flats = kFoxFlats; + CordRep* flat = MakeFlat(StrCat(std::string(50, '.'), flats[4]), 50); + CordRepRing* ring = CreateWithCapacity(RemovePrefix(50, flat), 0); + CordRepRing* result = ring; + for (int i = 1; i <= 4; ++i) { + result = CordRepRing::Prepend(result, flats[4 - i], 100); + result = CordRepRing::Append(result, flats[4 + i], 100); + } + result = NeedsUnref(result); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivate(GetParam(), ring)); + if (GetParam().refcount_is_one) { + EXPECT_THAT(ToFlats(result), ElementsAre(kFox)); + } else { + EXPECT_THAT(ToFlats(result), ElementsAre("The quick brown fox ", "jumps ", + "over the lazy dog")); + } + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingSubTest, SubRing) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + string_view all = kFox; + for (size_t offset = 0; offset < all.size() - 1; ++offset) { + CordRepRing* ring = RefIfShared(FromFlats(flats, composition)); + CordRepRing* result = CordRepRing::SubRing(ring, offset, 0); + EXPECT_THAT(result, nullptr); + UnrefIfShared(ring); + + for (size_t len = 1; len < all.size() - offset; ++len) { + ring = RefIfShared(FromFlats(flats, composition)); + result = NeedsUnref(CordRepRing::SubRing(ring, offset, len)); + ASSERT_THAT(result, IsValidRingBuffer()); + ASSERT_THAT(result, EqIfPrivate(GetParam(), ring)); + ASSERT_THAT(ToString(result), Eq(all.substr(offset, len))); + UnrefIfShared(ring); + Unref(result); + } + } +} + +TEST_P(CordRingSubTest, SubRingFromLargeExternal) { + auto composition = RandomComposition(); + std::string large_string(1 << 20, '.'); + const char* flats[] = { + "abcdefghijklmnopqrstuvwxyz", + large_string.c_str(), + "ABCDEFGHIJKLMNOPQRSTUVWXYZ", + }; + std::string buffer = absl::StrCat(flats[0], flats[1], flats[2]); + absl::string_view all = buffer; + for (size_t offset = 0; offset < 30; ++offset) { + CordRepRing* ring = RefIfShared(FromFlats(flats, composition)); + CordRepRing* result = CordRepRing::SubRing(ring, offset, 0); + EXPECT_THAT(result, nullptr); + UnrefIfShared(ring); + + for (size_t len = all.size() - 30; len < all.size() - offset; ++len) { + ring = RefIfShared(FromFlats(flats, composition)); + result = NeedsUnref(CordRepRing::SubRing(ring, offset, len)); + ASSERT_THAT(result, IsValidRingBuffer()); + ASSERT_THAT(result, EqIfPrivate(GetParam(), ring)); + auto str = ToString(result); + ASSERT_THAT(str, SizeIs(len)); + ASSERT_THAT(str, Eq(all.substr(offset, len))); + UnrefIfShared(ring); + Unref(result); + } + } +} + +TEST_P(CordRingSubTest, RemovePrefix) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + string_view all = kFox; + CordRepRing* ring = RefIfShared(FromFlats(flats, composition)); + CordRepRing* result = CordRepRing::RemovePrefix(ring, all.size()); + EXPECT_THAT(result, nullptr); + UnrefIfShared(ring); + + for (size_t len = 1; len < all.size(); ++len) { + ring = RefIfShared(FromFlats(flats, composition)); + result = NeedsUnref(CordRepRing::RemovePrefix(ring, len)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivate(GetParam(), ring)); + EXPECT_THAT(ToString(result), Eq(all.substr(len))); + UnrefIfShared(ring); + Unref(result); + } +} + +TEST_P(CordRingSubTest, RemovePrefixFromLargeExternal) { + CordRepExternal* external1 = MakeFakeExternal(1 << 20); + CordRepExternal* external2 = MakeFakeExternal(1 << 20); + CordRepRing* ring = CordRepRing::Create(external1, 1); + ring = CordRepRing::Append(ring, external2); + CordRepRing* result = NeedsUnref(CordRepRing::RemovePrefix(ring, 1 << 16)); + EXPECT_THAT( + ToRawFlats(result), + ElementsAre( + not_a_string_view(external1->base, 1 << 20).remove_prefix(1 << 16), + not_a_string_view(external2->base, 1 << 20))); + Unref(result); +} + +TEST_P(CordRingSubTest, RemoveSuffix) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + string_view all = kFox; + CordRepRing* ring = RefIfShared(FromFlats(flats, composition)); + CordRepRing* result = CordRepRing::RemoveSuffix(ring, all.size()); + EXPECT_THAT(result, nullptr); + UnrefIfShared(ring); + + for (size_t len = 1; len < all.size(); ++len) { + ring = RefIfShared(FromFlats(flats, composition)); + result = NeedsUnref(CordRepRing::RemoveSuffix(ring, len)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivate(GetParam(), ring)); + EXPECT_THAT(ToString(result), Eq(all.substr(0, all.size() - len))); + UnrefIfShared(ring); + Unref(result); + } +} + +TEST_P(CordRingSubTest, AppendRing) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats).subspan(1); + CordRepRing* ring = CreateWithCapacity(MakeFlat(kFoxFlats[0]), flats.size()); + CordRepRing* child = FromFlats(flats, composition); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, child)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivate(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAreArray(kFoxFlats)); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, AppendRingWithFlatOffset) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size()); + CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition)); + CordRep* stripped = RemovePrefix(10, child); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("Head", "brown ", "fox ", "jumps ", + "over ", "the ", "lazy ", "dog")); + UnrefIfInputSharedIndirect(child); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, AppendRingWithBrokenOffset) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size()); + CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition)); + CordRep* stripped = RemovePrefix(21, child); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), + ElementsAre("Head", "umps ", "over ", "the ", "lazy ", "dog")); + UnrefIfInputSharedIndirect(child); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, AppendRingWithFlatLength) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size()); + CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition)); + CordRep* stripped = RemoveSuffix(8, child); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("Head", "The ", "quick ", "brown ", + "fox ", "jumps ", "over ", "the ")); + UnrefIfInputSharedIndirect(child); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendRingWithBrokenFlatLength) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size()); + CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition)); + CordRep* stripped = RemoveSuffix(15, child); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("Head", "The ", "quick ", "brown ", + "fox ", "jumps ", "ov")); + UnrefIfInputSharedIndirect(child); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendRingMiddlePiece) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size()); + CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition)); + CordRep* stripped = MakeSubstring(7, child->length - 27, child); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), + ElementsAre("Head", "ck ", "brown ", "fox ", "jum")); + UnrefIfInputSharedIndirect(child); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildTest, AppendRingSinglePiece) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Head"), flats.size()); + CordRep* child = RefIfInputSharedIndirect(FromFlats(flats, composition)); + CordRep* stripped = RefIfInputShared(MakeSubstring(11, 3, child)); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("Head", "row")); + UnrefIfInputSharedIndirect(child); + UnrefIfInputShared(stripped); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, AppendRingSinglePieceWithPrefix) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + size_t extra_capacity = 1 + (GetParam().with_capacity ? flats.size() : 0); + CordRepRing* ring = CordRepRing::Create(MakeFlat("Head"), extra_capacity); + ring->SetCapacityForTesting(1 + extra_capacity); + ring = RefIfShared(CordRepRing::Prepend(ring, MakeFlat("Prepend"))); + assert(ring->IsValid(std::cout)); + CordRepRing* child = RefIfInputSharedIndirect(FromFlats(flats, composition)); + CordRep* stripped = RefIfInputShared(MakeSubstring(11, 3, child)); + CordRepRing* result = NeedsUnref(CordRepRing::Append(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("Prepend", "Head", "row")); + UnrefIfInputSharedIndirect(child); + UnrefIfInputShared(stripped); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, PrependRing) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto fox = MakeSpan(kFoxFlats); + auto flats = MakeSpan(fox).subspan(0, fox.size() - 1); + CordRepRing* ring = CreateWithCapacity(MakeFlat(fox.back()), flats.size()); + CordRepRing* child = RefIfInputShared(FromFlats(flats, composition)); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, child)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAreArray(kFoxFlats)); + UnrefIfInputShared(child); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, PrependRingWithFlatOffset) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size()); + CordRep* child = RefIfInputShared(FromFlats(flats, composition)); + CordRep* stripped = RefIfInputSharedIndirect(RemovePrefix(10, child)); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("brown ", "fox ", "jumps ", "over ", + "the ", "lazy ", "dog", "Tail")); + UnrefIfInputShared(child); + UnrefIfInputSharedIndirect(stripped); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, PrependRingWithBrokenOffset) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size()); + CordRep* child = RefIfInputShared(FromFlats(flats, composition)); + CordRep* stripped = RefIfInputSharedIndirect(RemovePrefix(21, child)); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped)); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), + ElementsAre("umps ", "over ", "the ", "lazy ", "dog", "Tail")); + UnrefIfInputShared(child); + UnrefIfInputSharedIndirect(stripped); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, PrependRingWithFlatLength) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size()); + CordRep* child = RefIfInputShared(FromFlats(flats, composition)); + CordRep* stripped = RefIfInputSharedIndirect(RemoveSuffix(8, child)); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("The ", "quick ", "brown ", "fox ", + "jumps ", "over ", "the ", "Tail")); + UnrefIfShared(ring); + UnrefIfInputShared(child); + UnrefIfInputSharedIndirect(stripped); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, PrependRingWithBrokenFlatLength) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size()); + CordRep* child = RefIfInputShared(FromFlats(flats, composition)); + CordRep* stripped = RefIfInputSharedIndirect(RemoveSuffix(15, child)); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("The ", "quick ", "brown ", "fox ", + "jumps ", "ov", "Tail")); + UnrefIfInputShared(child); + UnrefIfInputSharedIndirect(stripped); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, PrependRingMiddlePiece) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size()); + CordRep* child = RefIfInputShared(FromFlats(flats, composition)); + CordRep* stripped = + RefIfInputSharedIndirect(MakeSubstring(7, child->length - 27, child)); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), + ElementsAre("ck ", "brown ", "fox ", "jum", "Tail")); + UnrefIfInputShared(child); + UnrefIfInputSharedIndirect(stripped); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, PrependRingSinglePiece) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CreateWithCapacity(MakeFlat("Tail"), flats.size()); + CordRep* child = RefIfInputShared(FromFlats(flats, composition)); + CordRep* stripped = RefIfInputSharedIndirect(MakeSubstring(11, 3, child)); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("row", "Tail")); + UnrefIfInputShared(child); + UnrefIfInputSharedIndirect(stripped); + UnrefIfShared(ring); + Unref(result); +} + +TEST_P(CordRingBuildInputTest, PrependRingSinglePieceWithPrefix) { + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + auto flats = MakeSpan(kFoxFlats); + size_t extra_capacity = 1 + (GetParam().with_capacity ? flats.size() : 0); + CordRepRing* ring = CordRepRing::Create(MakeFlat("Tail"), extra_capacity); + ring->SetCapacityForTesting(1 + extra_capacity); + ring = RefIfShared(CordRepRing::Prepend(ring, MakeFlat("Prepend"))); + CordRep* child = RefIfInputShared(FromFlats(flats, composition)); + CordRep* stripped = RefIfInputSharedIndirect(MakeSubstring(11, 3, child)); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, stripped)); + ASSERT_THAT(result, IsValidRingBuffer()); + EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); + EXPECT_THAT(ToFlats(result), ElementsAre("row", "Prepend", "Tail")); + UnrefIfInputShared(child); + UnrefIfInputSharedIndirect(stripped); + UnrefIfShared(ring); + Unref(result); +} + +TEST_F(CordRingTest, Find) { + constexpr const char* flats[] = { + "abcdefghij", "klmnopqrst", "uvwxyz", "ABCDEFGHIJ", + "KLMNOPQRST", "UVWXYZ", "1234567890", "~!@#$%^&*()_", + "+-=", "[]\\{}|;':", ",/<>?", "."}; + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + CordRepRing* ring = NeedsUnref(FromFlats(flats, composition)); + std::string value = ToString(ring); + for (int i = 0; i < value.length(); ++i) { + CordRepRing::Position found = ring->Find(i); + auto data = ring->entry_data(found.index); + ASSERT_THAT(found.offset, Lt(data.length())); + ASSERT_THAT(data[found.offset], Eq(value[i])); + } + Unref(ring); +} + +TEST_F(CordRingTest, FindWithHint) { + constexpr const char* flats[] = { + "abcdefghij", "klmnopqrst", "uvwxyz", "ABCDEFGHIJ", + "KLMNOPQRST", "UVWXYZ", "1234567890", "~!@#$%^&*()_", + "+-=", "[]\\{}|;':", ",/<>?", "."}; + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + CordRepRing* ring = NeedsUnref(FromFlats(flats, composition)); + std::string value = ToString(ring); + +#if defined(GTEST_HAS_DEATH_TEST) + // Test hint beyond valid position + index_type head = ring->head(); + EXPECT_DEBUG_DEATH(ring->Find(ring->advance(head), 0), ".*"); + EXPECT_DEBUG_DEATH(ring->Find(ring->advance(head), 9), ".*"); + EXPECT_DEBUG_DEATH(ring->Find(ring->advance(head, 3), 24), ".*"); +#endif + + int flat_pos = 0; + size_t flat_offset = 0; + for (auto sflat : flats) { + string_view flat(sflat); + for (int offset = 0; offset < flat.length(); ++offset) { + for (int start = 0; start <= flat_pos; ++start) { + index_type hint = ring->advance(ring->head(), start); + CordRepRing::Position found = ring->Find(hint, flat_offset + offset); + ASSERT_THAT(found.index, Eq(ring->advance(ring->head(), flat_pos))); + ASSERT_THAT(found.offset, Eq(offset)); + } + } + ++flat_pos; + flat_offset += flat.length(); + } + Unref(ring); +} + +TEST_F(CordRingTest, FindInLargeRing) { + constexpr const char* flats[] = { + "abcdefghij", "klmnopqrst", "uvwxyz", "ABCDEFGHIJ", + "KLMNOPQRST", "UVWXYZ", "1234567890", "~!@#$%^&*()_", + "+-=", "[]\\{}|;':", ",/<>?", "."}; + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + CordRepRing* ring = FromFlats(flats, composition); + for (int i = 0; i < 13; ++i) { + ring = CordRepRing::Append(ring, FromFlats(flats, composition)); + } + NeedsUnref(ring); + std::string value = ToString(ring); + for (int i = 0; i < value.length(); ++i) { + CordRepRing::Position pos = ring->Find(i); + auto data = ring->entry_data(pos.index); + ASSERT_THAT(pos.offset, Lt(data.length())); + ASSERT_THAT(data[pos.offset], Eq(value[i])); + } + Unref(ring); +} + +TEST_F(CordRingTest, FindTail) { + constexpr const char* flats[] = { + "abcdefghij", "klmnopqrst", "uvwxyz", "ABCDEFGHIJ", + "KLMNOPQRST", "UVWXYZ", "1234567890", "~!@#$%^&*()_", + "+-=", "[]\\{}|;':", ",/<>?", "."}; + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + CordRepRing* ring = NeedsUnref(FromFlats(flats, composition)); + std::string value = ToString(ring); + + for (int i = 0; i < value.length(); ++i) { + CordRepRing::Position pos = ring->FindTail(i + 1); + auto data = ring->entry_data(ring->retreat(pos.index)); + ASSERT_THAT(pos.offset, Lt(data.length())); + ASSERT_THAT(data[data.length() - pos.offset - 1], Eq(value[i])); + } + Unref(ring); +} + +TEST_F(CordRingTest, FindTailWithHint) { + constexpr const char* flats[] = { + "abcdefghij", "klmnopqrst", "uvwxyz", "ABCDEFGHIJ", + "KLMNOPQRST", "UVWXYZ", "1234567890", "~!@#$%^&*()_", + "+-=", "[]\\{}|;':", ",/<>?", "."}; + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + CordRepRing* ring = NeedsUnref(FromFlats(flats, composition)); + std::string value = ToString(ring); + + // Test hint beyond valid position +#if defined(GTEST_HAS_DEATH_TEST) + index_type head = ring->head(); + EXPECT_DEBUG_DEATH(ring->FindTail(ring->advance(head), 1), ".*"); + EXPECT_DEBUG_DEATH(ring->FindTail(ring->advance(head), 10), ".*"); + EXPECT_DEBUG_DEATH(ring->FindTail(ring->advance(head, 3), 26), ".*"); +#endif + + for (int i = 0; i < value.length(); ++i) { + CordRepRing::Position pos = ring->FindTail(i + 1); + auto data = ring->entry_data(ring->retreat(pos.index)); + ASSERT_THAT(pos.offset, Lt(data.length())); + ASSERT_THAT(data[data.length() - pos.offset - 1], Eq(value[i])); + } + Unref(ring); +} + +TEST_F(CordRingTest, FindTailInLargeRing) { + constexpr const char* flats[] = { + "abcdefghij", "klmnopqrst", "uvwxyz", "ABCDEFGHIJ", + "KLMNOPQRST", "UVWXYZ", "1234567890", "~!@#$%^&*()_", + "+-=", "[]\\{}|;':", ",/<>?", "."}; + auto composition = RandomComposition(); + SCOPED_TRACE(ToString(composition)); + CordRepRing* ring = FromFlats(flats, composition); + for (int i = 0; i < 13; ++i) { + ring = CordRepRing::Append(ring, FromFlats(flats, composition)); + } + NeedsUnref(ring); + std::string value = ToString(ring); + for (int i = 0; i < value.length(); ++i) { + CordRepRing::Position pos = ring->FindTail(i + 1); + auto data = ring->entry_data(ring->retreat(pos.index)); + ASSERT_THAT(pos.offset, Lt(data.length())); + ASSERT_THAT(data[data.length() - pos.offset - 1], Eq(value[i])); + } + Unref(ring); +} + +TEST_F(CordRingTest, GetCharacter) { + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = CordRepRing::Create(MakeFlat("Tail"), flats.size()); + CordRep* child = FromFlats(flats, kAppend); + CordRepRing* result = NeedsUnref(CordRepRing::Prepend(ring, child)); + std::string value = ToString(result); + for (int i = 0; i < value.length(); ++i) { + ASSERT_THAT(result->GetCharacter(i), Eq(value[i])); + } + Unref(result); +} + +TEST_F(CordRingTest, GetCharacterWithSubstring) { + absl::string_view str1 = "abcdefghijklmnopqrstuvwxyz"; + auto* child = MakeSubstring(4, 20, MakeFlat(str1)); + CordRepRing* result = NeedsUnref(CordRepRing::Create(child)); + ASSERT_THAT(result, IsValidRingBuffer()); + std::string value = ToString(result); + for (int i = 0; i < value.length(); ++i) { + ASSERT_THAT(result->GetCharacter(i), Eq(value[i])); + } + Unref(result); +} + +TEST_F(CordRingTest, Dump) { + std::stringstream ss; + auto flats = MakeSpan(kFoxFlats); + CordRepRing* ring = NeedsUnref(FromFlats(flats, kPrepend)); + ss << *ring; + Unref(ring); +} + +} // namespace +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc index 59f2e4d9..905ffd0c 100644 --- a/absl/strings/internal/cord_internal.cc +++ b/absl/strings/internal/cord_internal.cc @@ -19,6 +19,7 @@ #include "absl/container/inlined_vector.h" #include "absl/strings/internal/cord_rep_flat.h" +#include "absl/strings/internal/cord_rep_ring.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -48,6 +49,9 @@ void CordRep::Destroy(CordRep* rep) { rep = left; continue; } + } else if (rep->tag == RING) { + CordRepRing::Destroy(rep->ring()); + rep = nullptr; } else if (rep->tag == EXTERNAL) { CordRepExternal::Delete(rep); rep = nullptr; diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index b586ea37..011b49d3 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h @@ -1,4 +1,4 @@ -// Copyright 2020 The Abseil Authors. +// 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. @@ -21,6 +21,7 @@ #include #include +#include "absl/base/config.h" #include "absl/base/internal/invoke.h" #include "absl/base/optimization.h" #include "absl/container/internal/compressed_tuple.h" @@ -145,13 +146,14 @@ struct CordRepConcat; struct CordRepExternal; struct CordRepFlat; struct CordRepSubstring; +class CordRepRing; // Various representations that we allow enum CordRepKind { - CONCAT = 0, - EXTERNAL = 1, - SUBSTRING = 2, - RING = 3, + CONCAT = 0, + EXTERNAL = 1, + SUBSTRING = 2, + RING = 3, // We have different tags for different sized flat arrays, // starting with FLAT, and limited to MAX_FLAT_TAG. The 224 value is based on @@ -160,7 +162,7 @@ enum CordRepKind { // as the Tag <---> Size logic so that FLAT stil represents the minimum flat // allocation size. (32 bytes as of now). FLAT = 4, - MAX_FLAT_TAG = 224, + MAX_FLAT_TAG = 224 }; struct CordRep { @@ -177,6 +179,8 @@ struct CordRep { uint8_t tag; char storage[1]; // Starting point for flat array: MUST BE LAST FIELD + inline CordRepRing* ring(); + inline const CordRepRing* ring() const; inline CordRepConcat* concat(); inline const CordRepConcat* concat() const; inline CordRepSubstring* substring(); @@ -306,45 +310,165 @@ CordRepExternal ConstInitExternalStorage::value(Str::value); enum { kMaxInline = 15, - // Tag byte & kMaxInline means we are storing a pointer. - kTreeFlag = 1 << 4, - // Tag byte & kProfiledFlag means we are profiling the Cord. - kProfiledFlag = 1 << 5 -}; - -// If the data has length <= kMaxInline, we store it in `as_chars`, and -// store the size in `tagged_size`. -// Else we store it in a tree and store a pointer to that tree in -// `as_tree.rep` and store a tag in `tagged_size`. -struct AsTree { - absl::cord_internal::CordRep* rep; - char padding[kMaxInline + 1 - sizeof(absl::cord_internal::CordRep*) - 1]; - char tagged_size; }; constexpr char GetOrNull(absl::string_view data, size_t pos) { return pos < data.size() ? data[pos] : '\0'; } -union InlineData { - constexpr InlineData() : as_chars{} {} - explicit constexpr InlineData(AsTree tree) : as_tree(tree) {} +// We store cordz_info as 64 bit pointer value in big endian format. This +// guarantees that the least significant byte of cordz_info matches the last +// byte of the inline data representation in as_chars_, which holds the inlined +// size or the 'is_tree' bit. +using cordz_info_t = int64_t; + +// Assert that the `cordz_info` pointer value perfectly overlaps the last half +// of `as_chars_` and can hold a pointer value. +static_assert(sizeof(cordz_info_t) * 2 == kMaxInline + 1, ""); +static_assert(sizeof(cordz_info_t) >= sizeof(intptr_t), ""); + +// BigEndianByte() creates a big endian representation of 'value', i.e.: a big +// endian value where the last byte in the host's representation holds 'value`, +// with all other bytes being 0. +static constexpr cordz_info_t BigEndianByte(unsigned char value) { +#if defined(ABSL_IS_BIG_ENDIAN) + return value; +#else + return static_cast(value) << ((sizeof(cordz_info_t) - 1) * 8); +#endif +} + +class InlineData { + public: + // kNullCordzInfo holds the big endian representation of intptr_t(1) + // This is the 'null' / initial value of 'cordz_info'. The null value + // is specifically big endian 1 as with 64-bit pointers, the last + // byte of cordz_info overlaps with the last byte holding the tag. + static constexpr cordz_info_t kNullCordzInfo = BigEndianByte(1); + + // kFakeCordzInfo holds a 'fake', non-null cordz-info value we use to + // emulate the previous 'kProfiled' tag logic in 'set_profiled' until + // cord code is changed to store cordz_info values in InlineData. + static constexpr cordz_info_t kFakeCordzInfo = BigEndianByte(9); + + constexpr InlineData() : as_chars_{0} {} + explicit constexpr InlineData(CordRep* rep) : as_tree_(rep) {} explicit constexpr InlineData(absl::string_view chars) - : as_chars{GetOrNull(chars, 0), GetOrNull(chars, 1), - GetOrNull(chars, 2), GetOrNull(chars, 3), - GetOrNull(chars, 4), GetOrNull(chars, 5), - GetOrNull(chars, 6), GetOrNull(chars, 7), - GetOrNull(chars, 8), GetOrNull(chars, 9), - GetOrNull(chars, 10), GetOrNull(chars, 11), - GetOrNull(chars, 12), GetOrNull(chars, 13), - GetOrNull(chars, 14), static_cast(chars.size())} {} - - AsTree as_tree; - char as_chars[kMaxInline + 1]; + : as_chars_{ + GetOrNull(chars, 0), GetOrNull(chars, 1), + GetOrNull(chars, 2), GetOrNull(chars, 3), + GetOrNull(chars, 4), GetOrNull(chars, 5), + GetOrNull(chars, 6), GetOrNull(chars, 7), + GetOrNull(chars, 8), GetOrNull(chars, 9), + GetOrNull(chars, 10), GetOrNull(chars, 11), + GetOrNull(chars, 12), GetOrNull(chars, 13), + GetOrNull(chars, 14), static_cast((chars.size() << 1))} {} + + // Returns true if the current instance is empty. + // The 'empty value' is an inlined data value of zero length. + bool is_empty() const { return tag() == 0; } + + // Returns true if the current instance holds a tree value. + bool is_tree() const { return (tag() & 1) != 0; } + + // Returns true if the current instance holds a cordz_info value. + // Requires the current instance to hold a tree value. + bool is_profiled() const { + assert(is_tree()); + return as_tree_.cordz_info != kNullCordzInfo; + } + + // Returns a read only pointer to the character data inside this instance. + // Requires the current instance to hold inline data. + const char* as_chars() const { + assert(!is_tree()); + return as_chars_; + } + + // Returns a mutable pointer to the character data inside this instance. + // Should be used for 'write only' operations setting an inlined value. + // Applications can set the value of inlined data either before or after + // setting the inlined size, i.e., both of the below are valid: + // + // // Set inlined data and inline size + // memcpy(data_.as_chars(), data, size); + // data_.set_inline_size(size); + // + // // Set inlined size and inline data + // data_.set_inline_size(size); + // memcpy(data_.as_chars(), data, size); + // + // It's an error to read from the returned pointer without a preceding write + // if the current instance does not hold inline data, i.e.: is_tree() == true. + char* as_chars() { return as_chars_; } + + // Returns the tree value of this value. + // Requires the current instance to hold a tree value. + CordRep* as_tree() const { + assert(is_tree()); + return as_tree_.rep; + } + + // Initialize this instance to holding the tree value `rep`, + // initializing the cordz_info to null, i.e.: 'not profiled'. + void make_tree(CordRep* rep) { + as_tree_.rep = rep; + as_tree_.cordz_info = kNullCordzInfo; + } + + // Set the tree value of this instance to 'rep`. + // Requires the current instance to already hold a tree value. + // Does not affect the value of cordz_info. + void set_tree(CordRep* rep) { + assert(is_tree()); + as_tree_.rep = rep; + } + + // Returns the size of the inlined character data inside this instance. + // Requires the current instance to hold inline data. + size_t inline_size() const { + assert(!is_tree()); + return tag() >> 1; + } + + // Sets the size of the inlined character data inside this instance. + // Requires `size` to be <= kMaxInline. + // See the documentation on 'as_chars()' for more information and examples. + void set_inline_size(size_t size) { + ABSL_ASSERT(size <= kMaxInline); + tag() = static_cast(size << 1); + } + + // Sets or unsets the 'is_profiled' state of this instance. + // Requires the current instance to hold a tree value. + void set_profiled(bool profiled) { + assert(is_tree()); + as_tree_.cordz_info = profiled ? kFakeCordzInfo : kNullCordzInfo; + } + + private: + // See cordz_info_t for forced alignment and size of `cordz_info` details. + struct AsTree { + explicit constexpr AsTree(absl::cord_internal::CordRep* tree) + : rep(tree), cordz_info(kNullCordzInfo) {} + absl::cord_internal::CordRep* rep; + alignas(sizeof(cordz_info_t)) cordz_info_t cordz_info; + }; + + char& tag() { return reinterpret_cast(this)[kMaxInline]; } + char tag() const { return reinterpret_cast(this)[kMaxInline]; } + + // If the data has length <= kMaxInline, we store it in `as_chars_`, and + // store the size in the last char of `as_chars_` shifted left + 1. + // Else we store it in a tree and store a pointer to that tree in + // `as_tree_.rep` and store a tag in `tagged_size`. + union { + char as_chars_[kMaxInline + 1]; + AsTree as_tree_; + }; }; + static_assert(sizeof(InlineData) == kMaxInline + 1, ""); -static_assert(sizeof(AsTree) == sizeof(InlineData), ""); -static_assert(offsetof(AsTree, tagged_size) == kMaxInline, ""); inline CordRepConcat* CordRep::concat() { assert(tag == CONCAT); @@ -386,6 +510,16 @@ inline const CordRepFlat* CordRep::flat() const { return reinterpret_cast(this); } +inline CordRepRing* CordRep::ring() { + assert(tag == RING); + return reinterpret_cast(this); +} + +inline const CordRepRing* CordRep::ring() const { + assert(tag == RING); + return reinterpret_cast(this); +} + inline CordRep* CordRep::Ref(CordRep* rep) { assert(rep != nullptr); rep->refcount.Increment(); diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h index 8c7d160e..5f7d55ce 100644 --- a/absl/strings/internal/cord_rep_flat.h +++ b/absl/strings/internal/cord_rep_flat.h @@ -104,7 +104,8 @@ struct CordRepFlat : public CordRep { // Flat CordReps are allocated and constructed with raw ::operator new and // placement new, and must be destructed and deallocated accordingly. static void Delete(CordRep*rep) { - assert(rep->tag >= FLAT); + assert(rep->tag >= FLAT && rep->tag <= MAX_FLAT_TAG); + #if defined(__cpp_sized_deallocation) size_t size = TagToAllocatedSize(rep->tag); rep->~CordRep(); @@ -115,6 +116,7 @@ struct CordRepFlat : public CordRep { #endif } + // Returns a pointer to the data inside this flat rep. char* Data() { return storage; } const char* Data() const { return storage; } diff --git a/absl/strings/internal/cord_rep_ring.cc b/absl/strings/internal/cord_rep_ring.cc new file mode 100644 index 00000000..358b0d92 --- /dev/null +++ b/absl/strings/internal/cord_rep_ring.cc @@ -0,0 +1,895 @@ +// Copyright 2020 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_ring.h" + +#include +#include +#include +#include +#include +#include +#include + +#include "absl/base/internal/raw_logging.h" +#include "absl/base/internal/throw_delegate.h" +#include "absl/base/macros.h" +#include "absl/container/inlined_vector.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_flat.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// See https://bugs.llvm.org/show_bug.cgi?id=48477 +#ifdef __clang__ +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wshadow" +#pragma clang diagnostic ignored "-Wshadow-field" +#endif + +namespace { + +using index_type = CordRepRing::index_type; + +enum class Direction { kForward, kReversed }; + +inline bool IsFlatOrExternal(CordRep* rep) { + return rep->tag >= FLAT || rep->tag == EXTERNAL; +} + +// Verifies that n + extra <= kMaxCapacity: throws std::length_error otherwise. +inline void CheckCapacity(size_t n, size_t extra) { + if (ABSL_PREDICT_FALSE(extra > CordRepRing::kMaxCapacity - n)) { + base_internal::ThrowStdLengthError("Maximum capacity exceeded"); + } +} + +// Removes a reference from `rep` only. +// Asserts that the refcount after decrement is not zero. +inline bool UnrefNeverOne(CordRep* rep) { + bool result = rep->refcount.Decrement(); + assert(result); + return result; +} + +// Creates a flat from the provided string data, allocating up to `extra` +// capacity in the returned flat depending on kMaxFlatLength limitations. +// Requires `len` to be less or equal to `kMaxFlatLength` +CordRepFlat* CreateFlat(const char* s, size_t n, size_t extra = 0) { // NOLINT + assert(n <= kMaxFlatLength); + auto* rep = CordRepFlat::New(n + extra); + rep->length = n; + memcpy(rep->Data(), s, n); + return rep; +} + +// 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); + if (ABSL_PREDICT_FALSE(!substring->refcount.Decrement())) { + UnrefNeverOne(child); + delete substring; + } + } + return child; +} + +// Unrefs the provided `concat`, and returns `{concat->left, concat->right}` +// Adds or assumes a reference on `concat->left` and `concat->right`. +std::pair ClipConcat(CordRepConcat* concat) { + auto result = std::make_pair(concat->left, concat->right); + if (concat->refcount.IsOne()) { + delete concat; + } else { + CordRep::Ref(result.first); + CordRep::Ref(result.second); + if (ABSL_PREDICT_FALSE(!concat->refcount.Decrement())) { + UnrefNeverOne(result.first); + UnrefNeverOne(result.second); + delete concat; + } + } + return result; +} + +// Unrefs the entries in `[head, tail)`. +// Requires all entries to be a FLAT or EXTERNAL node. +void UnrefEntries(const CordRepRing* rep, index_type head, index_type tail) { + rep->ForEach(head, tail, [rep](index_type ix) { + CordRep* child = rep->entry_child(ix); + if (!child->refcount.Decrement()) { + if (child->tag >= FLAT) { + CordRepFlat::Delete(child->flat()); + } else { + CordRepExternal::Delete(child->external()); + } + } + }); +} + +template +void Consume(Direction direction, CordRep* rep, F&& fn) { + size_t offset = 0; + size_t length = rep->length; + struct Entry { + CordRep* rep; + size_t offset; + size_t length; + }; + absl::InlinedVector stack; + + for (;;) { + if (rep->tag >= FLAT || rep->tag == EXTERNAL || rep->tag == RING) { + fn(rep, offset, length); + if (stack.empty()) return; + + rep = stack.back().rep; + offset = stack.back().offset; + length = stack.back().length; + stack.pop_back(); + } else if (rep->tag == SUBSTRING) { + offset += rep->substring()->start; + rep = ClipSubstring(rep->substring()); + } else if (rep->tag == CONCAT) { + auto res = ClipConcat(rep->concat()); + CordRep* left = res.first; + CordRep* right = res.second; + + 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 (direction == Direction::kReversed) { + stack.push_back({left, offset, length_left}); + rep = right; + offset = 0; + length = length_right; + } else { + stack.push_back({right, 0, length_right}); + rep = left; + length = length_left; + } + } else { + assert("Valid tag" == nullptr); + return; + } + } +} + +template +void Consume(CordRep* rep, F&& fn) { + return Consume(Direction::kForward, rep, std::forward(fn)); +} + +template +void RConsume(CordRep* rep, F&& fn) { + return Consume(Direction::kReversed, rep, std::forward(fn)); +} + +} // namespace + +std::ostream& operator<<(std::ostream& s, const CordRepRing& rep) { + // Note: 'pos' values are defined as size_t (for overflow reasons), but that + // prints really awkward for small prepended values such as -5. ssize_t is not + // portable (POSIX), so we use ptrdiff_t instead to cast to signed values. + s << " CordRepRing(" << &rep << ", length = " << rep.length + << ", head = " << rep.head_ << ", tail = " << rep.tail_ + << ", cap = " << rep.capacity_ << ", rc = " << rep.refcount.Get() + << ", begin_pos_ = " << static_cast(rep.begin_pos_) << ") {\n"; + CordRepRing::index_type head = rep.head(); + do { + CordRep* child = rep.entry_child(head); + s << " entry[" << head << "] length = " << rep.entry_length(head) + << ", child " << child << ", clen = " << child->length + << ", tag = " << static_cast(child->tag) + << ", rc = " << child->refcount.Get() + << ", offset = " << rep.entry_data_offset(head) + << ", end_pos = " << static_cast(rep.entry_end_pos(head)) + << "\n"; + head = rep.advance(head); + } while (head != rep.tail()); + return s << "}\n"; +} + +void CordRepRing::AddDataOffset(index_type index, size_t n) { + entry_data_offset()[index] += static_cast(n); +} + +void CordRepRing::SubLength(index_type index, size_t n) { + entry_end_pos()[index] -= n; +} + +class CordRepRing::Filler { + public: + Filler(CordRepRing* rep, index_type pos) : rep_(rep), head_(pos), pos_(pos) {} + + index_type head() const { return head_; } + index_type pos() const { return pos_; } + + void Add(CordRep* child, size_t offset, pos_type end_pos) { + rep_->entry_end_pos()[pos_] = end_pos; + rep_->entry_child()[pos_] = child; + rep_->entry_data_offset()[pos_] = static_cast(offset); + pos_ = rep_->advance(pos_); + } + + private: + CordRepRing* rep_; + index_type head_; + index_type pos_; +}; + +constexpr size_t CordRepRing::kMaxCapacity; // NOLINT: needed for c++11 + +bool CordRepRing::IsValid(std::ostream& output) const { + if (capacity_ == 0) { + output << "capacity == 0"; + return false; + } + + if (head_ >= capacity_ || tail_ >= capacity_) { + output << "head " << head_ << " and/or tail " << tail_ << "exceed capacity " + << capacity_; + return false; + } + + const index_type back = retreat(tail_); + size_t pos_length = Distance(begin_pos_, entry_end_pos(back)); + if (pos_length != length) { + output << "length " << length << " does not match positional length " + << pos_length << " from begin_pos " << begin_pos_ << " and entry[" + << back << "].end_pos " << entry_end_pos(back); + return false; + } + + index_type head = head_; + pos_type begin_pos = begin_pos_; + do { + pos_type end_pos = entry_end_pos(head); + size_t entry_length = Distance(begin_pos, end_pos); + if (entry_length == 0) { + output << "entry[" << head << "] has an invalid length " << entry_length + << " from begin_pos " << begin_pos << " and end_pos " << end_pos; + return false; + } + + CordRep* child = entry_child(head); + if (child == nullptr) { + output << "entry[" << head << "].child == nullptr"; + return false; + } + if (child->tag < FLAT && child->tag != EXTERNAL) { + output << "entry[" << head << "].child has an invalid tag " + << static_cast(child->tag); + return false; + } + + size_t offset = entry_data_offset(head); + if (offset >= child->length || entry_length > child->length - offset) { + output << "entry[" << head << "] has offset " << offset + << " and entry length " << entry_length + << " which are outside of the childs length of " << child->length; + return false; + } + + begin_pos = end_pos; + head = advance(head); + } while (head != tail_); + + return true; +} + +#ifdef EXTRA_CORD_RING_VALIDATION +CordRepRing* CordRepRing::Validate(CordRepRing* rep, const char* file, + int line) { + if (!rep->IsValid(std::cerr)) { + std::cerr << "\nERROR: CordRepRing corrupted"; + if (line) std::cerr << " at line " << line; + if (file) std::cerr << " in file " << file; + std::cerr << "\nContent = " << *rep; + abort(); + } + return rep; +} +#endif // EXTRA_CORD_RING_VALIDATION + +CordRepRing* CordRepRing::New(size_t capacity, size_t extra) { + CheckCapacity(capacity, extra); + + size_t size = AllocSize(capacity += extra); + void* mem = ::operator new(size); + auto* rep = new (mem) CordRepRing(static_cast(capacity)); + rep->tag = RING; + rep->capacity_ = static_cast(capacity); + rep->begin_pos_ = 0; + return rep; +} + +void CordRepRing::SetCapacityForTesting(size_t capacity) { + // Adjust for the changed layout + assert(capacity <= capacity_); + assert(head() == 0 || head() < tail()); + memmove(Layout::Partial(capacity).Pointer<1>(data_) + head(), + Layout::Partial(capacity_).Pointer<1>(data_) + head(), + entries() * sizeof(Layout::ElementType<1>)); + memmove(Layout::Partial(capacity, capacity).Pointer<2>(data_) + head(), + Layout::Partial(capacity_, capacity_).Pointer<2>(data_) + head(), + entries() * sizeof(Layout::ElementType<2>)); + capacity_ = static_cast(capacity); +} + +void CordRepRing::Delete(CordRepRing* rep) { + assert(rep != nullptr && rep->tag == RING); +#if defined(__cpp_sized_deallocation) + size_t size = AllocSize(rep->capacity_); + rep->~CordRepRing(); + ::operator delete(rep, size); +#else + rep->~CordRepRing(); + ::operator delete(rep); +#endif +} + +void CordRepRing::Destroy(CordRepRing* rep) { + UnrefEntries(rep, rep->head(), rep->tail()); + Delete(rep); +} + +template +void CordRepRing::Fill(const CordRepRing* src, index_type head, + index_type tail) { + this->length = src->length; + head_ = 0; + tail_ = advance(0, src->entries(head, tail)); + begin_pos_ = src->begin_pos_; + + // TODO(mvels): there may be opportunities here for large buffers. + auto* dst_pos = entry_end_pos(); + auto* dst_child = entry_child(); + auto* dst_offset = entry_data_offset(); + src->ForEach(head, tail, [&](index_type index) { + *dst_pos++ = src->entry_end_pos(index); + CordRep* child = src->entry_child(index); + *dst_child++ = ref ? CordRep::Ref(child) : child; + *dst_offset++ = src->entry_data_offset(index); + }); +} + +CordRepRing* CordRepRing::Copy(CordRepRing* rep, index_type head, + index_type tail, size_t extra) { + CordRepRing* newrep = CordRepRing::New(rep->entries(head, tail), extra); + newrep->Fill(rep, head, tail); + CordRep::Unref(rep); + return newrep; +} + +CordRepRing* CordRepRing::Mutable(CordRepRing* rep, size_t extra) { + // Get current number of entries, and check for max capacity. + size_t entries = rep->entries(); + + size_t min_extra = (std::max)(extra, rep->capacity() * 2 - entries); + if (!rep->refcount.IsOne()) { + return Copy(rep, rep->head(), rep->tail(), min_extra); + } else if (entries + extra > rep->capacity()) { + CordRepRing* newrep = CordRepRing::New(entries, min_extra); + newrep->Fill(rep, rep->head(), rep->tail()); + CordRepRing::Delete(rep); + return newrep; + } else { + return rep; + } +} + +Span CordRepRing::GetAppendBuffer(size_t size) { + assert(refcount.IsOne()); + index_type back = retreat(tail_); + CordRep* child = entry_child(back); + if (child->tag >= FLAT && child->refcount.IsOne()) { + size_t capacity = child->flat()->Capacity(); + pos_type end_pos = entry_end_pos(back); + size_t data_offset = entry_data_offset(back); + size_t entry_length = Distance(entry_begin_pos(back), end_pos); + size_t used = data_offset + entry_length; + if (size_t n = (std::min)(capacity - used, size)) { + child->length = data_offset + entry_length + n; + entry_end_pos()[back] = end_pos + n; + this->length += n; + return {child->flat()->Data() + used, n}; + } + } + return {nullptr, 0}; +} + +Span CordRepRing::GetPrependBuffer(size_t size) { + assert(refcount.IsOne()); + CordRep* child = entry_child(head_); + size_t data_offset = entry_data_offset(head_); + if (data_offset && child->refcount.IsOne() && child->tag >= FLAT) { + size_t n = (std::min)(data_offset, size); + this->length += n; + begin_pos_ -= n; + data_offset -= n; + entry_data_offset()[head_] = static_cast(data_offset); + return {child->flat()->Data() + data_offset, n}; + } + return {nullptr, 0}; +} + +CordRepRing* CordRepRing::CreateFromLeaf(CordRep* child, size_t offset, + size_t length, size_t extra) { + CordRepRing* rep = CordRepRing::New(1, extra); + rep->head_ = 0; + rep->tail_ = rep->advance(0); + rep->length = length; + rep->entry_end_pos()[0] = length; + rep->entry_child()[0] = child; + rep->entry_data_offset()[0] = static_cast(offset); + return Validate(rep); +} + +CordRepRing* CordRepRing::CreateSlow(CordRep* child, size_t extra) { + CordRepRing* rep = nullptr; + Consume(child, [&](CordRep* child, size_t offset, size_t length) { + if (IsFlatOrExternal(child)) { + rep = rep ? AppendLeaf(rep, child, offset, length) + : CreateFromLeaf(child, offset, length, extra); + } else if (rep) { + rep = AddRing(rep, child->ring(), offset, length); + } else if (offset == 0 && child->length == length) { + rep = Mutable(child->ring(), extra); + } else { + rep = SubRing(child->ring(), offset, length, extra); + } + }); + return Validate(rep, nullptr, __LINE__); +} + +CordRepRing* CordRepRing::Create(CordRep* child, size_t extra) { + size_t length = child->length; + if (IsFlatOrExternal(child)) { + return CreateFromLeaf(child, 0, length, extra); + } + if (child->tag == RING) { + return Mutable(child->ring(), extra); + } + return CreateSlow(child, extra); +} + +template +CordRepRing* CordRepRing::AddRing(CordRepRing* rep, CordRepRing* ring, + size_t offset, size_t length) { + assert(offset < ring->length); + constexpr bool append = mode == AddMode::kAppend; + Position head = ring->Find(offset); + Position tail = ring->FindTail(head.index, offset + length); + const index_type entries = ring->entries(head.index, tail.index); + + rep = Mutable(rep, entries); + + // The delta for making ring[head].end_pos into 'len - offset' + const pos_type delta_length = + (append ? rep->begin_pos_ + rep->length : rep->begin_pos_ - length) - + ring->entry_begin_pos(head.index) - head.offset; + + // Start filling at `tail`, or `entries` before `head` + Filler filler(rep, append ? rep->tail_ : rep->retreat(rep->head_, entries)); + + if (ring->refcount.IsOne()) { + // Copy entries from source stealing the ref and adjusting the end position. + // Commit the filler as this is no-op. + ring->ForEach(head.index, tail.index, [&](index_type ix) { + filler.Add(ring->entry_child(ix), ring->entry_data_offset(ix), + ring->entry_end_pos(ix) + delta_length); + }); + + // Unref entries we did not copy over, and delete source. + if (head.index != ring->head_) UnrefEntries(ring, ring->head_, head.index); + if (tail.index != ring->tail_) UnrefEntries(ring, tail.index, ring->tail_); + CordRepRing::Delete(ring); + } else { + ring->ForEach(head.index, tail.index, [&](index_type ix) { + CordRep* child = ring->entry_child(ix); + filler.Add(child, ring->entry_data_offset(ix), + ring->entry_end_pos(ix) + delta_length); + CordRep::Ref(child); + }); + CordRepRing::Unref(ring); + } + + if (head.offset) { + // Increase offset of first 'source' entry appended or prepended. + // This is always the entry in `filler.head()` + rep->AddDataOffset(filler.head(), head.offset); + } + + if (tail.offset) { + // Reduce length of last 'source' entry appended or prepended. + // This is always the entry tailed by `filler.pos()` + rep->SubLength(rep->retreat(filler.pos()), tail.offset); + } + + // Commit changes + rep->length += length; + if (append) { + rep->tail_ = filler.pos(); + } else { + rep->head_ = filler.head(); + rep->begin_pos_ -= length; + } + + return Validate(rep); +} + +CordRepRing* CordRepRing::AppendSlow(CordRepRing* rep, CordRep* child) { + Consume(child, [&rep](CordRep* child, size_t offset, size_t length) { + if (child->tag == RING) { + rep = AddRing(rep, child->ring(), offset, length); + } else { + rep = AppendLeaf(rep, child, offset, length); + } + }); + return rep; +} + +CordRepRing* CordRepRing::AppendLeaf(CordRepRing* rep, CordRep* child, + size_t offset, size_t length) { + rep = Mutable(rep, 1); + index_type back = rep->tail_; + const pos_type begin_pos = rep->begin_pos_ + rep->length; + rep->tail_ = rep->advance(rep->tail_); + rep->length += length; + rep->entry_end_pos()[back] = begin_pos + length; + rep->entry_child()[back] = child; + rep->entry_data_offset()[back] = static_cast(offset); + return Validate(rep, nullptr, __LINE__); +} + +CordRepRing* CordRepRing::Append(CordRepRing* rep, CordRep* child) { + size_t length = child->length; + if (IsFlatOrExternal(child)) { + return AppendLeaf(rep, child, 0, length); + } + if (child->tag == RING) { + return AddRing(rep, child->ring(), 0, length); + } + return AppendSlow(rep, child); +} + +CordRepRing* CordRepRing::PrependSlow(CordRepRing* rep, CordRep* child) { + RConsume(child, [&](CordRep* child, size_t offset, size_t length) { + if (IsFlatOrExternal(child)) { + rep = PrependLeaf(rep, child, offset, length); + } else { + rep = AddRing(rep, child->ring(), offset, length); + } + }); + return Validate(rep); +} + +CordRepRing* CordRepRing::PrependLeaf(CordRepRing* rep, CordRep* child, + size_t offset, size_t length) { + rep = Mutable(rep, 1); + index_type head = rep->retreat(rep->head_); + pos_type end_pos = rep->begin_pos_; + rep->head_ = head; + rep->length += length; + rep->begin_pos_ -= length; + rep->entry_end_pos()[head] = end_pos; + rep->entry_child()[head] = child; + rep->entry_data_offset()[head] = static_cast(offset); + return Validate(rep); +} + +CordRepRing* CordRepRing::Prepend(CordRepRing* rep, CordRep* child) { + size_t length = child->length; + if (IsFlatOrExternal(child)) { + return PrependLeaf(rep, child, 0, length); + } + if (child->tag == RING) { + return AddRing(rep, child->ring(), 0, length); + } + return PrependSlow(rep, child); +} + +CordRepRing* CordRepRing::Append(CordRepRing* rep, absl::string_view data, + size_t extra) { + if (rep->refcount.IsOne()) { + Span avail = rep->GetAppendBuffer(data.length()); + if (!avail.empty()) { + memcpy(avail.data(), data.data(), avail.length()); + data.remove_prefix(avail.length()); + } + } + if (data.empty()) return Validate(rep); + + const size_t flats = (data.length() - 1) / kMaxFlatLength + 1; + rep = Mutable(rep, flats); + + Filler filler(rep, rep->tail_); + pos_type pos = rep->begin_pos_ + rep->length; + + while (data.length() >= kMaxFlatLength) { + auto* flat = CreateFlat(data.data(), kMaxFlatLength); + filler.Add(flat, 0, pos += kMaxFlatLength); + data.remove_prefix(kMaxFlatLength); + } + + if (data.length()) { + auto* flat = CreateFlat(data.data(), data.length(), extra); + filler.Add(flat, 0, pos += data.length()); + } + + rep->length = pos - rep->begin_pos_; + rep->tail_ = filler.pos(); + + return Validate(rep); +} + +CordRepRing* CordRepRing::Prepend(CordRepRing* rep, absl::string_view data, + size_t extra) { + if (rep->refcount.IsOne()) { + Span avail = rep->GetPrependBuffer(data.length()); + if (!avail.empty()) { + const char* tail = data.data() + data.length() - avail.length(); + memcpy(avail.data(), tail, avail.length()); + data.remove_suffix(avail.length()); + } + } + if (data.empty()) return rep; + + const size_t flats = (data.length() - 1) / kMaxFlatLength + 1; + rep = Mutable(rep, flats); + pos_type pos = rep->begin_pos_; + Filler filler(rep, rep->retreat(rep->head_, static_cast(flats))); + + size_t first_size = data.size() - (flats - 1) * kMaxFlatLength; + CordRepFlat* flat = CordRepFlat::New(first_size + extra); + flat->length = first_size + extra; + memcpy(flat->Data() + extra, data.data(), first_size); + data.remove_prefix(first_size); + filler.Add(flat, extra, pos); + pos -= first_size; + + while (!data.empty()) { + assert(data.size() >= kMaxFlatLength); + flat = CreateFlat(data.data(), kMaxFlatLength); + filler.Add(flat, 0, pos); + pos -= kMaxFlatLength; + data.remove_prefix(kMaxFlatLength); + } + + rep->head_ = filler.head(); + rep->length += rep->begin_pos_ - pos; + rep->begin_pos_ = pos; + + return Validate(rep); +} + +// 32 entries is 32 * sizeof(pos_type) = 4 cache lines on x86 +static constexpr index_type kBinarySearchThreshold = 32; +static constexpr index_type kBinarySearchEndCount = 8; + +template +CordRepRing::index_type CordRepRing::FindBinary(index_type head, + index_type tail, + size_t offset) const { + index_type count = tail + (wrap ? capacity_ : 0) - head; + do { + count = (count - 1) / 2; + assert(count < entries(head, tail_)); + index_type mid = wrap ? advance(head, count) : head + count; + index_type after_mid = wrap ? advance(mid) : mid + 1; + bool larger = (offset >= entry_end_offset(mid)); + head = larger ? after_mid : head; + tail = larger ? tail : mid; + assert(head != tail); + } while (ABSL_PREDICT_TRUE(count > kBinarySearchEndCount)); + return head; +} + +CordRepRing::Position CordRepRing::FindSlow(index_type head, + size_t offset) const { + index_type tail = tail_; + + // Binary search until we are good for linear search + // Optimize for branchless / non wrapping ops + if (tail > head) { + index_type count = tail - head; + if (count > kBinarySearchThreshold) { + head = FindBinary(head, tail, offset); + } + } else { + index_type count = capacity_ + tail - head; + if (count > kBinarySearchThreshold) { + head = FindBinary(head, tail, offset); + } + } + + pos_type pos = entry_begin_pos(head); + pos_type end_pos = entry_end_pos(head); + while (offset >= Distance(begin_pos_, end_pos)) { + head = advance(head); + pos = end_pos; + end_pos = entry_end_pos(head); + } + + return {head, offset - Distance(begin_pos_, pos)}; +} + +CordRepRing::Position CordRepRing::FindTailSlow(index_type head, + size_t offset) const { + index_type tail = tail_; + const size_t tail_offset = offset - 1; + + // Binary search until we are good for linear search + // Optimize for branchless / non wrapping ops + if (tail > head) { + index_type count = tail - head; + if (count > kBinarySearchThreshold) { + head = FindBinary(head, tail, tail_offset); + } + } else { + index_type count = capacity_ + tail - head; + if (count > kBinarySearchThreshold) { + head = FindBinary(head, tail, tail_offset); + } + } + + size_t end_offset = entry_end_offset(head); + while (tail_offset >= end_offset) { + head = advance(head); + end_offset = entry_end_offset(head); + } + + return {advance(head), end_offset - offset}; +} + +char CordRepRing::GetCharacter(size_t offset) const { + assert(offset < length); + + Position pos = Find(offset); + size_t data_offset = entry_data_offset(pos.index) + pos.offset; + return GetRepData(entry_child(pos.index))[data_offset]; +} + +CordRepRing* CordRepRing::SubRing(CordRepRing* rep, size_t offset, + size_t length, size_t extra) { + assert(offset <= rep->length); + assert(offset <= rep->length - length); + + if (length == 0) { + CordRep::Unref(rep); + return nullptr; + } + + // Find position of first byte + Position head = rep->Find(offset); + Position tail = rep->FindTail(head.index, offset + length); + const size_t new_entries = rep->entries(head.index, tail.index); + + if (rep->refcount.IsOne() && extra <= (rep->capacity() - new_entries)) { + // We adopt a privately owned rep and no extra entries needed. + if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index); + if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_); + rep->head_ = head.index; + rep->tail_ = tail.index; + } else { + // Copy subset to new rep + rep = Copy(rep, head.index, tail.index, extra); + head.index = rep->head_; + tail.index = rep->tail_; + } + + // Adjust begin_pos and length + rep->length = length; + rep->begin_pos_ += offset; + + // Adjust head and tail blocks + if (head.offset) { + rep->AddDataOffset(head.index, head.offset); + } + if (tail.offset) { + rep->SubLength(rep->retreat(tail.index), tail.offset); + } + + return Validate(rep); +} + +CordRepRing* CordRepRing::RemovePrefix(CordRepRing* rep, size_t len, + size_t extra) { + assert(len <= rep->length); + if (len == rep->length) { + CordRep::Unref(rep); + return nullptr; + } + + Position head = rep->Find(len); + if (rep->refcount.IsOne()) { + if (head.index != rep->head_) UnrefEntries(rep, rep->head_, head.index); + rep->head_ = head.index; + } else { + rep = Copy(rep, head.index, rep->tail_, extra); + head.index = rep->head_; + } + + // Adjust begin_pos and length + rep->length -= len; + rep->begin_pos_ += len; + + // Adjust head block + if (head.offset) { + rep->AddDataOffset(head.index, head.offset); + } + + return Validate(rep); +} + +CordRepRing* CordRepRing::RemoveSuffix(CordRepRing* rep, size_t len, + size_t extra) { + assert(len <= rep->length); + + if (len == rep->length) { + CordRep::Unref(rep); + return nullptr; + } + + Position tail = rep->FindTail(rep->length - len); + if (rep->refcount.IsOne()) { + // We adopt a privately owned rep, scrub. + if (tail.index != rep->tail_) UnrefEntries(rep, tail.index, rep->tail_); + rep->tail_ = tail.index; + } else { + // Copy subset to new rep + rep = Copy(rep, rep->head_, tail.index, extra); + tail.index = rep->tail_; + } + + // Adjust length + rep->length -= len; + + // Adjust tail block + if (tail.offset) { + rep->SubLength(rep->retreat(tail.index), tail.offset); + } + + return Validate(rep); +} + +#ifdef __clang__ +#pragma clang diagnostic pop +#endif + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl diff --git a/absl/strings/internal/cord_rep_ring.h b/absl/strings/internal/cord_rep_ring.h new file mode 100644 index 00000000..e6f6b59c --- /dev/null +++ b/absl/strings/internal/cord_rep_ring.h @@ -0,0 +1,576 @@ +// Copyright 2020 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_RING_H_ +#define ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_ + +#include +#include +#include +#include +#include +#include + +#include "absl/container/internal/layout.h" +#include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_flat.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// See https://bugs.llvm.org/show_bug.cgi?id=48477 +#ifdef __clang__ +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wshadow" +#pragma clang diagnostic ignored "-Wshadow-field" +#endif + +// All operations modifying a ring buffer are implemented as static methods +// requiring a CordRepRing instance with a reference adopted by the method. +// +// The methods return the modified ring buffer, which may be equal to the input +// if the input was not shared, and having large enough capacity to accommodate +// any newly added node(s). Otherwise, a copy of the input rep with the new +// node(s) added is returned. +// +// Any modification on non shared ring buffers with enough capacity will then +// require minimum atomic operations. Caller should where possible provide +// reasonable `extra` hints for both anticipated extra `flat` byte space, as +// well as anticipated extra nodes required for complex operations. +// +// Example of code creating a ring buffer, adding some data to it, +// and discarding the buffer when done: +// +// void FunWithRings() { +// // Create ring with 3 flats +// CordRep* flat = CreateFlat("Hello"); +// CordRepRing* ring = CordRepRing::Create(flat, 2); +// ring = CordRepRing::Append(ring, CreateFlat(" ")); +// ring = CordRepRing::Append(ring, CreateFlat("world")); +// DoSomethingWithRing(ring); +// CordRep::Unref(ring); +// } +// +// Example of code Copying an existing ring buffer and modifying it: +// +// void MoreFunWithRings(CordRepRing* src) { +// CordRepRing* ring = CordRep::Ref(src)->ring(); +// ring = CordRepRing::Append(ring, CreateFlat("Hello")); +// ring = CordRepRing::Append(ring, CreateFlat(" ")); +// ring = CordRepRing::Append(ring, CreateFlat("world")); +// DoSomethingWithRing(ring); +// CordRep::Unref(ring); +// } +// +class CordRepRing : public CordRep { + public: + // `pos_type` represents a 'logical position'. A CordRepRing instance has a + // `begin_pos` (default 0), and each node inside the buffer will have an + // `end_pos` which is the `end_pos` of the previous node (or `begin_pos`) plus + // this node's length. The purpose is to allow for a binary search on this + // position, while allowing O(1) prepend and append operations. + using pos_type = uint64_t; + + // `index_type` is the type for the `head`, `tail` and `capacity` indexes. + // Ring buffers are limited to having no more than four billion entries. + using index_type = uint32_t; + + // `offset_type` is the type for the data offset inside a child rep's data. + using offset_type = uint32_t; + + // Position holds the node index and relative offset into the node for + // some physical offset in the contained data as returned by the Find() + // and FindTail() methods. + struct Position { + index_type index; + size_t offset; + }; + + // The maximum # of child nodes that can be hosted inside a CordRepRing. + static constexpr size_t kMaxCapacity = (std::numeric_limits::max)(); + + // CordRepring can not be default constructed, moved, copied or assigned. + CordRepRing() = delete; + CordRepRing(const CordRepRing&) = delete; + CordRepRing& operator=(const CordRepRing&) = delete; + + // Returns true if this instance is valid, false if some or all of the + // invariants are broken. Intended for debug purposes only. + // `output` receives an explanation of the broken invariants. + bool IsValid(std::ostream& output) const; + + // Returns the size in bytes for a CordRepRing with `capacity' entries. + static constexpr size_t AllocSize(size_t capacity); + + // Returns the distance in bytes from `pos` to `end_pos`. + static constexpr size_t Distance(pos_type pos, pos_type end_pos); + + // Creates a new ring buffer from the provided `rep`. Adopts a reference + // on `rep`. The returned ring buffer has a capacity of at least `extra + 1` + static CordRepRing* Create(CordRep* child, size_t extra = 0); + + // `head`, `tail` and `capacity` indexes defining the ring buffer boundaries. + index_type head() const { return head_; } + index_type tail() const { return tail_; } + index_type capacity() const { return capacity_; } + + // Returns the number of entries in this instance. + index_type entries() const { return entries(head_, tail_); } + + // Returns the logical begin position of this instance. + pos_type begin_pos() const { return begin_pos_; } + + // Returns the number of entries for a given head-tail range. + // Requires `head` and `tail` values to be less than `capacity()`. + index_type entries(index_type head, index_type tail) const { + assert(head < capacity_ && tail < capacity_); + return tail - head + ((tail > head) ? 0 : capacity_); + } + + // Returns the logical end position of entry `index`. + pos_type const& entry_end_pos(index_type index) const { + assert(IsValidIndex(index)); + return Layout::Partial().Pointer<0>(data_)[index]; + } + + // Returns the child pointer of entry `index`. + CordRep* const& entry_child(index_type index) const { + assert(IsValidIndex(index)); + return Layout::Partial(capacity()).Pointer<1>(data_)[index]; + } + + // Returns the data offset of entry `index` + offset_type const& entry_data_offset(index_type index) const { + assert(IsValidIndex(index)); + return Layout::Partial(capacity(), capacity()).Pointer<2>(data_)[index]; + } + + // Appends the provided child node to the `rep` instance. + // Adopts a reference from `rep` and `child` which may not be null. + // If the provided child is a FLAT or EXTERNAL node, or a SUBSTRING node + // containing a FLAT or EXTERNAL node, then flat or external the node is added + // 'as is', with an offset added for the SUBSTRING case. + // If the provided child is a RING or CONCAT tree, or a SUBSTRING of a RING or + // CONCAT tree, then all child nodes not excluded by any start offset or + // length values are added recursively. + static CordRepRing* Append(CordRepRing* rep, CordRep* child); + + // Appends the provided string data to the `rep` instance. + // This function will attempt to utilize any remaining capacity in the last + // node of the input if that node is not shared (directly or indirectly), and + // of type FLAT. Remaining data will be added as one or more FLAT nodes. + // Any last node added to the ring buffer will be allocated with up to + // `extra` bytes of capacity for (anticipated) subsequent append actions. + static CordRepRing* Append(CordRepRing* rep, string_view data, + size_t extra = 0); + + // Prepends the provided child node to the `rep` instance. + // Adopts a reference from `rep` and `child` which may not be null. + // If the provided child is a FLAT or EXTERNAL node, or a SUBSTRING node + // containing a FLAT or EXTERNAL node, then flat or external the node is + // prepended 'as is', with an optional offset added for the SUBSTRING case. + // If the provided child is a RING or CONCAT tree, or a SUBSTRING of a RING + // or CONCAT tree, then all child nodes not excluded by any start offset or + // length values are added recursively. + static CordRepRing* Prepend(CordRepRing* rep, CordRep* child); + + // Prepends the provided string data to the `rep` instance. + // This function will attempt to utilize any remaining capacity in the first + // node of the input if that node is not shared (directly or indirectly), and + // of type FLAT. Remaining data will be added as one or more FLAT nodes. + // Any first node prepnded to the ring buffer will be allocated with up to + // `extra` bytes of capacity for (anticipated) subsequent prepend actions. + static CordRepRing* Prepend(CordRepRing* rep, string_view data, + size_t extra = 0); + + // Returns a span referencing potentially unused capacity in the last node. + // The returned span may be empty if no such capacity is available, or if the + // current instance is shared. Else, a span of size `n <= size` is returned. + // If non empty, the ring buffer is adjusted to the new length, with the newly + // added capacity left uninitialized. Callers should assign a value to the + // entire span before any other operations on this instance. + Span GetAppendBuffer(size_t size); + + // Returns a span referencing potentially unused capacity in the first node. + // This function is identical to GetAppendBuffer except that it returns a span + // referencing up to `size` capacity directly before the existing data. + Span GetPrependBuffer(size_t size); + + // Returns a cord ring buffer containing `length` bytes of data starting at + // `offset`. If the input is not shared, this function will remove all head + // and tail child nodes outside of the requested range, and adjust the new + // head and tail nodes as required. If the input is shared, this function + // returns a new instance sharing some or all of the nodes from the input. + static CordRepRing* SubRing(CordRepRing* r, size_t offset, size_t length, + size_t extra = 0); + + // Returns a cord ring buffer with the first `length` bytes removed. + // If the input is not shared, this function will remove all head child nodes + // fully inside the first `length` bytes, and adjust the new head as required. + // If the input is shared, this function returns a new instance sharing some + // or all of the nodes from the input. + static CordRepRing* RemoveSuffix(CordRepRing* r, size_t length, + size_t extra = 0); + + // Returns a cord ring buffer with the last `length` bytes removed. + // If the input is not shared, this function will remove all head child nodes + // fully inside the first `length` bytes, and adjust the new head as required. + // If the input is shared, this function returns a new instance sharing some + // or all of the nodes from the input. + static CordRepRing* RemovePrefix(CordRepRing* r, size_t len, + size_t extra = 0); + + // Returns the character at `offset`. Requires that `offset < length`. + char GetCharacter(size_t offset) const; + + // Testing only: set capacity to requested capacity. + void SetCapacityForTesting(size_t capacity); + + // Returns the CordRep data pointer for the provided CordRep. + // Requires that the provided `rep` is either a FLAT or EXTERNAL CordRep. + static const char* GetLeafData(const CordRep* rep); + + // Returns the CordRep data pointer for the provided CordRep. + // Requires that `rep` is either a FLAT, EXTERNAL, or SUBSTRING CordRep. + static const char* GetRepData(const CordRep* rep); + + // Advances the provided position, wrapping around capacity as needed. + // Requires `index` < capacity() + inline index_type advance(index_type index) const; + + // Advances the provided position by 'n`, wrapping around capacity as needed. + // Requires `index` < capacity() and `n` <= capacity. + inline index_type advance(index_type index, index_type n) const; + + // Retreats the provided position, wrapping around 0 as needed. + // Requires `index` < capacity() + inline index_type retreat(index_type index) const; + + // Retreats the provided position by 'n', wrapping around 0 as needed. + // Requires `index` < capacity() + inline index_type retreat(index_type index, index_type n) const; + + // Returns the logical begin position of entry `index` + pos_type const& entry_begin_pos(index_type index) const { + return (index == head_) ? begin_pos_ : entry_end_pos(retreat(index)); + } + + // Returns the physical start offset of entry `index` + size_t entry_start_offset(index_type index) const { + return Distance(begin_pos_, entry_begin_pos(index)); + } + + // Returns the physical end offset of entry `index` + size_t entry_end_offset(index_type index) const { + return Distance(begin_pos_, entry_end_pos(index)); + } + + // Returns the data length for entry `index` + size_t entry_length(index_type index) const { + return Distance(entry_begin_pos(index), entry_end_pos(index)); + } + + // Returns the data for entry `index` + absl::string_view entry_data(index_type index) const; + + // Returns the position for `offset` as {index, prefix}. `index` holds the + // index of the entry at the specified offset and `prefix` holds the relative + // offset inside that entry. + // Requires `offset` < length. + // + // For example we can implement GetCharacter(offset) as: + // char GetCharacter(size_t offset) { + // Position pos = this->Find(offset); + // return this->entry_data(pos.pos)[pos.offset]; + // } + inline Position Find(size_t offset) const; + + // Find starting at `head` + inline Position Find(index_type head, size_t offset) const; + + // Returns the tail position for `offset` as {tail index, suffix}. + // `tail index` holds holds the index of the entry holding the offset directly + // before 'offset` advanced by one. 'suffix` holds the relative offset from + // that relative offset in the entry to the end of the entry. + // For example, FindTail(length) will return {tail(), 0}, FindTail(length - 5) + // will return {retreat(tail), 5)} provided the preceding entry contains at + // least 5 bytes of data. + // Requires offset >= 1 && offset <= length. + // + // This function is very useful in functions that need to clip the end of some + // ring buffer such as 'RemovePrefix'. + // For example, we could implement RemovePrefix for non shared instances as: + // void RemoveSuffix(size_t n) { + // Position pos = FindTail(length - n); + // UnrefEntries(pos.pos, this->tail_); + // this->tail_ = pos.pos; + // entry(retreat(pos.pos)).end_pos -= pos.offset; + // } + inline Position FindTail(size_t offset) const; + + // Find tail starting at `head` + inline Position FindTail(index_type head, size_t offset) const; + + // Invokes f(index_type index) for each entry inside the range [head, tail> + template + void ForEach(index_type head, index_type tail, F&& f) const { + index_type n1 = (tail > head) ? tail : capacity_; + for (index_type i = head; i < n1; ++i) f(i); + if (tail <= head) { + for (index_type i = 0; i < tail; ++i) f(i); + } + } + + // Invokes f(index_type index) for each entry inside this instance. + template + void ForEach(F&& f) const { + ForEach(head_, tail_, std::forward(f)); + } + + // Dump this instance's data tp stream `s` in human readable format, excluding + // the actual data content itself. Intended for debug purposes only. + friend std::ostream& operator<<(std::ostream& s, const CordRepRing& rep); + + private: + enum class AddMode { kAppend, kPrepend }; + + using Layout = container_internal::Layout; + + class Filler; + class Transaction; + class CreateTransaction; + + static constexpr size_t kLayoutAlignment = Layout::Partial().Alignment(); + + // Creates a new CordRepRing. + explicit CordRepRing(index_type capacity) : capacity_(capacity) {} + + // Returns true if `index` is a valid index into this instance. + bool IsValidIndex(index_type index) const; + + // Debug use only: validates the provided CordRepRing invariants. + // Verification of all CordRepRing methods can be enabled by defining + // EXTRA_CORD_RING_VALIDATION, i.e.: `--copts=-DEXTRA_CORD_RING_VALIDATION` + // Verification is VERY expensive, so only do it for debugging purposes. + static CordRepRing* Validate(CordRepRing* rep, const char* file = nullptr, + int line = 0); + + // Allocates a CordRepRing large enough to hold `capacity + extra' entries. + // The returned capacity may be larger if the allocated memory allows for it. + // The maximum capacity of a CordRepRing is capped at kMaxCapacity. + // Throws `std::length_error` if `capacity + extra' exceeds kMaxCapacity. + static CordRepRing* New(size_t capacity, size_t extra); + + // Deallocates (but does not destroy) the provided ring buffer. + static void Delete(CordRepRing* rep); + + // Destroys the provided ring buffer, decrementing the reference count of all + // contained child CordReps. The provided 1\`rep` should have a ref count of + // one (pre decrement destroy call observing `refcount.IsOne()`) or zero (post + // decrement destroy call observing `!refcount.Decrement()`). + static void Destroy(CordRepRing* rep); + + // Returns a mutable reference to the logical end position array. + pos_type* entry_end_pos() { + return Layout::Partial().Pointer<0>(data_); + } + + // Returns a mutable reference to the child pointer array. + CordRep** entry_child() { + return Layout::Partial(capacity()).Pointer<1>(data_); + } + + // Returns a mutable reference to the data offset array. + offset_type* entry_data_offset() { + return Layout::Partial(capacity(), capacity()).Pointer<2>(data_); + } + + // Find implementations for the non fast path 0 / length cases. + Position FindSlow(index_type head, size_t offset) const; + Position FindTailSlow(index_type head, size_t offset) const; + + // Finds the index of the first node that is inside a reasonable distance + // of the node at `offset` from which we can continue with a linear search. + template + index_type FindBinary(index_type head, index_type tail, size_t offset) const; + + // Fills the current (initialized) instance from the provided source, copying + // entries [head, tail). Adds a reference to copied entries if `ref` is true. + template + void Fill(const CordRepRing* src, index_type head, index_type tail); + + // Create a copy of 'rep', copying all entries [head, tail), allocating room + // for `extra` entries. Adds a reference on all copied entries. + static CordRepRing* Copy(CordRepRing* rep, index_type head, index_type tail, + size_t extra = 0); + + // Returns a Mutable CordRepRing reference from `rep` with room for at least + // `extra` additional nodes. Adopts a reference count from `rep`. + // This function will return `rep` if, and only if: + // - rep.entries + extra <= rep.capacity + // - rep.refcount == 1 + // Otherwise, this function will create a new copy of `rep` with additional + // capacity to satisfy `extra` extra nodes, and unref the old `rep` instance. + // + // If a new CordRepRing can not be allocated, or the new capacity would exceed + // the maxmimum capacity, then the input is consumed only, and an exception is + // thrown. + static CordRepRing* Mutable(CordRepRing* rep, size_t extra); + + // Slow path for Append(CordRepRing* rep, CordRep* child). This function is + // exercised if the provided `child` in Append() is not a leaf node, i.e., a + // ring buffer or old (concat) cord tree. + static CordRepRing* AppendSlow(CordRepRing* rep, CordRep* child); + + // Appends the provided leaf node. Requires `child` to be FLAT or EXTERNAL. + static CordRepRing* AppendLeaf(CordRepRing* rep, CordRep* child, + size_t offset, size_t length); + + // Prepends the provided leaf node. Requires `child` to be FLAT or EXTERNAL. + static CordRepRing* PrependLeaf(CordRepRing* rep, CordRep* child, + size_t offset, size_t length); + + // Slow path for Prepend(CordRepRing* rep, CordRep* child). This function is + // exercised if the provided `child` in Prepend() is not a leaf node, i.e., a + // ring buffer or old (concat) cord tree. + static CordRepRing* PrependSlow(CordRepRing* rep, CordRep* child); + + // Slow path for Create(CordRep* child, size_t extra). This function is + // exercised if the provided `child` in Prepend() is not a leaf node, i.e., a + // ring buffer or old (concat) cord tree. + static CordRepRing* CreateSlow(CordRep* child, size_t extra); + + // Creates a new ring buffer from the provided `child` leaf node. Requires + // `child` to be FLAT or EXTERNAL. on `rep`. + // The returned ring buffer has a capacity of at least `1 + extra` + static CordRepRing* CreateFromLeaf(CordRep* child, size_t offset, + size_t length, size_t extra); + + // Appends or prepends (depending on AddMode) the ring buffer in `ring' to + // `rep` starting at `offset` with length `length`. + template + static CordRepRing* AddRing(CordRepRing* rep, CordRepRing* ring, + size_t offset, size_t length); + + // Increases the data offset for entry `index` by `n`. + void AddDataOffset(index_type index, size_t n); + + // Descreases the length for entry `index` by `n`. + void SubLength(index_type index, size_t n); + + index_type head_; + index_type tail_; + index_type capacity_; + pos_type begin_pos_; + + alignas(kLayoutAlignment) char data_[kLayoutAlignment]; + + friend struct CordRep; +}; + +constexpr size_t CordRepRing::AllocSize(size_t capacity) { + return sizeof(CordRepRing) - sizeof(data_) + + Layout(capacity, capacity, capacity).AllocSize(); +} + +inline constexpr size_t CordRepRing::Distance(pos_type pos, pos_type end_pos) { + return (end_pos - pos); +} + +inline const char* CordRepRing::GetLeafData(const CordRep* rep) { + return rep->tag != EXTERNAL ? rep->flat()->Data() : rep->external()->base; +} + +inline const char* CordRepRing::GetRepData(const CordRep* rep) { + if (rep->tag >= FLAT) return rep->flat()->Data(); + if (rep->tag == EXTERNAL) return rep->external()->base; + return GetLeafData(rep->substring()->child) + rep->substring()->start; +} + +inline CordRepRing::index_type CordRepRing::advance(index_type index) const { + assert(index < capacity_); + return ++index == capacity_ ? 0 : index; +} + +inline CordRepRing::index_type CordRepRing::advance(index_type index, + index_type n) const { + assert(index < capacity_ && n <= capacity_); + return (index += n) >= capacity_ ? index - capacity_ : index; +} + +inline CordRepRing::index_type CordRepRing::retreat(index_type index) const { + assert(index < capacity_); + return (index > 0 ? index : capacity_) - 1; +} + +inline CordRepRing::index_type CordRepRing::retreat(index_type index, + index_type n) const { + assert(index < capacity_ && n <= capacity_); + return index >= n ? index - n : capacity_ - n + index; +} + +inline absl::string_view CordRepRing::entry_data(index_type index) const { + size_t data_offset = entry_data_offset(index); + return {GetRepData(entry_child(index)) + data_offset, entry_length(index)}; +} + +inline bool CordRepRing::IsValidIndex(index_type index) const { + if (index >= capacity_) return false; + return (tail_ > head_) ? (index >= head_ && index < tail_) + : (index >= head_ || index < tail_); +} + +#ifndef EXTRA_CORD_RING_VALIDATION +inline CordRepRing* CordRepRing::Validate(CordRepRing* rep, + const char* /*file*/, int /*line*/) { + return rep; +} +#endif + +inline CordRepRing::Position CordRepRing::Find(size_t offset) const { + assert(offset < length); + return (offset == 0) ? Position{head_, 0} : FindSlow(head_, offset); +} + +inline CordRepRing::Position CordRepRing::Find(index_type head, + size_t offset) const { + assert(offset < length); + assert(IsValidIndex(head) && offset >= entry_start_offset(head)); + return (offset == 0) ? Position{head_, 0} : FindSlow(head, offset); +} + +inline CordRepRing::Position CordRepRing::FindTail(size_t offset) const { + assert(offset > 0 && offset <= length); + return (offset == length) ? Position{tail_, 0} : FindTailSlow(head_, offset); +} + +inline CordRepRing::Position CordRepRing::FindTail(index_type head, + size_t offset) const { + assert(offset > 0 && offset <= length); + assert(IsValidIndex(head) && offset >= entry_start_offset(head) + 1); + return (offset == length) ? Position{tail_, 0} : FindTailSlow(head, offset); +} + +std::ostream& operator<<(std::ostream& s, const CordRepRing& rep); + +#ifdef __clang__ +#pragma clang diagnostic pop +#endif + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_ diff --git a/absl/synchronization/mutex.h b/absl/synchronization/mutex.h index 598d1e06..4dd51fec 100644 --- a/absl/synchronization/mutex.h +++ b/absl/synchronization/mutex.h @@ -162,7 +162,7 @@ class ABSL_LOCKABLE Mutex { // Mutex::Unlock() // // Releases this `Mutex` and returns it from the exclusive/write state to the - // free state. Caller must hold the `Mutex` exclusively. + // free state. Calling thread must hold the `Mutex` exclusively. void Unlock() ABSL_UNLOCK_FUNCTION(); // Mutex::TryLock() diff --git a/absl/types/CMakeLists.txt b/absl/types/CMakeLists.txt index 3f99ad8a..c356b211 100644 --- a/absl/types/CMakeLists.txt +++ b/absl/types/CMakeLists.txt @@ -353,9 +353,6 @@ absl_cc_test( gmock_main ) -# TODO(cohenjon,zhangxy) Figure out why this test is failing on gcc 4.8 -if(CMAKE_CXX_COMPILER_ID STREQUAL "GNU" AND CMAKE_CXX_COMPILER_VERSION VERSION_LESS 4.9) -else() absl_cc_test( NAME variant_exception_safety_test @@ -370,4 +367,3 @@ absl_cc_test( absl::memory gmock_main ) -endif() -- cgit v1.2.3