diff options
| -rw-r--r-- | CMake/AbseilDll.cmake | 3 | ||||
| -rw-r--r-- | absl/strings/BUILD.bazel | 38 | ||||
| -rw-r--r-- | absl/strings/CMakeLists.txt | 38 | ||||
| -rw-r--r-- | absl/strings/cord.h | 1 | ||||
| -rw-r--r-- | absl/strings/cord_analysis.cc | 13 | ||||
| -rw-r--r-- | absl/strings/cord_ring_reader_test.cc | 180 | ||||
| -rw-r--r-- | absl/strings/cord_ring_test.cc | 1458 | ||||
| -rw-r--r-- | absl/strings/cord_test.cc | 2 | ||||
| -rw-r--r-- | absl/strings/internal/cord_internal.cc | 6 | ||||
| -rw-r--r-- | absl/strings/internal/cord_internal.h | 20 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_ring.cc | 773 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_ring.h | 607 | ||||
| -rw-r--r-- | absl/strings/internal/cord_rep_ring_reader.h | 118 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_info.cc | 17 | ||||
| -rw-r--r-- | absl/strings/internal/cordz_info_statistics_test.cc | 77 |
15 files changed, 5 insertions, 3346 deletions
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 0b2d5c76..f8eeb140 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake @@ -288,9 +288,6 @@ set(ABSL_INTERNAL_DLL_FILES "strings/internal/cord_rep_consume.h" "strings/internal/cord_rep_consume.cc" "strings/internal/cord_rep_flat.h" - "strings/internal/cord_rep_ring.cc" - "strings/internal/cord_rep_ring.h" - "strings/internal/cord_rep_ring_reader.h" "strings/internal/cordz_functions.cc" "strings/internal/cordz_functions.h" "strings/internal/cordz_handle.cc" diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index a858d0b2..e226a27d 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -360,7 +360,6 @@ cc_library( "internal/cord_rep_btree_reader.cc", "internal/cord_rep_consume.cc", "internal/cord_rep_crc.cc", - "internal/cord_rep_ring.cc", ], hdrs = [ "internal/cord_data_edge.h", @@ -371,8 +370,6 @@ cc_library( "internal/cord_rep_consume.h", "internal/cord_rep_crc.h", "internal/cord_rep_flat.h", - "internal/cord_rep_ring.h", - "internal/cord_rep_ring_reader.h", ], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -889,41 +886,6 @@ 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", - "//absl/types:span", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( - name = "cord_ring_reader_test", - size = "medium", - srcs = ["cord_ring_reader_test.cc"], - copts = ABSL_TEST_COPTS, - visibility = ["//visibility:private"], - deps = [ - ":cord_internal", - ":strings", - "//absl/base:config", - "//absl/base:core_headers", - "//absl/debugging:leak_check", - "//absl/types:span", - "@com_google_googletest//:gtest_main", - ], -) - -cc_test( name = "substitute_test", size = "small", srcs = ["substitute_test.cc"], diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 27e7ce4f..8bd93271 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -637,8 +637,6 @@ absl_cc_library( "internal/cord_rep_crc.h" "internal/cord_rep_consume.h" "internal/cord_rep_flat.h" - "internal/cord_rep_ring.h" - "internal/cord_rep_ring_reader.h" SRCS "internal/cord_internal.cc" "internal/cord_rep_btree.cc" @@ -646,7 +644,6 @@ absl_cc_library( "internal/cord_rep_btree_reader.cc" "internal/cord_rep_crc.cc" "internal/cord_rep_consume.cc" - "internal/cord_rep_ring.cc" COPTS ${ABSL_DEFAULT_COPTS} DEPS @@ -1117,41 +1114,6 @@ absl_cc_test( absl_cc_test( NAME - cord_ring_test - SRCS - "cord_ring_test.cc" - COPTS - ${ABSL_TEST_COPTS} - DEPS - absl::base - absl::config - absl::cord_internal - absl::core_headers - absl::raw_logging_internal - absl::span - absl::strings - GTest::gmock_main -) - -absl_cc_test( - NAME - cord_ring_reader_test - SRCS - "cord_ring_reader_test.cc" - COPTS - ${ABSL_TEST_COPTS} - DEPS - absl::base - absl::config - absl::cord_internal - absl::core_headers - absl::span - absl::strings - GTest::gmock_main -) - -absl_cc_test( - NAME cordz_test SRCS "cordz_test.cc" diff --git a/absl/strings/cord.h b/absl/strings/cord.h index 0dede5c7..dbfca805 100644 --- a/absl/strings/cord.h +++ b/absl/strings/cord.h @@ -86,7 +86,6 @@ #include "absl/strings/internal/cord_rep_btree.h" #include "absl/strings/internal/cord_rep_btree_reader.h" #include "absl/strings/internal/cord_rep_crc.h" -#include "absl/strings/internal/cord_rep_ring.h" #include "absl/strings/internal/cordz_functions.h" #include "absl/strings/internal/cordz_info.h" #include "absl/strings/internal/cordz_statistics.h" diff --git a/absl/strings/cord_analysis.cc b/absl/strings/cord_analysis.cc index e3824281..b0f1a3e6 100644 --- a/absl/strings/cord_analysis.cc +++ b/absl/strings/cord_analysis.cc @@ -24,7 +24,6 @@ #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/cord_rep_btree.h" #include "absl/strings/internal/cord_rep_crc.h" -#include "absl/strings/internal/cord_rep_ring.h" namespace absl { ABSL_NAMESPACE_BEGIN @@ -131,16 +130,6 @@ void AnalyzeDataEdge(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) { raw_usage.Add(size, rep); } -// Computes the memory size of the provided Ring tree. -template <Mode mode> -void AnalyzeRing(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) { - const CordRepRing* ring = rep.rep->ring(); - raw_usage.Add(CordRepRing::AllocSize(ring->capacity()), rep); - ring->ForEach([&](CordRepRing::index_type pos) { - AnalyzeDataEdge(rep.Child(ring->entry_child(pos)), raw_usage); - }); -} - // Computes the memory size of the provided Btree tree. template <Mode mode> void AnalyzeBtree(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) { @@ -175,8 +164,6 @@ size_t GetEstimatedUsage(const CordRep* rep) { AnalyzeDataEdge(repref, raw_usage); } else if (repref.rep->tag == BTREE) { AnalyzeBtree(repref, raw_usage); - } else if (repref.rep->tag == RING) { - AnalyzeRing(repref, raw_usage); } else { assert(false); } diff --git a/absl/strings/cord_ring_reader_test.cc b/absl/strings/cord_ring_reader_test.cc deleted file mode 100644 index d135f3cf..00000000 --- a/absl/strings/cord_ring_reader_test.cc +++ /dev/null @@ -1,180 +0,0 @@ -// 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 <array> -#include <cstdlib> -#include <cstring> -#include <ctime> - -#include "gmock/gmock.h" -#include "gtest/gtest.h" -#include "absl/base/config.h" -#include "absl/strings/internal/cord_internal.h" -#include "absl/strings/internal/cord_rep_ring.h" -#include "absl/strings/internal/cord_rep_ring_reader.h" -#include "absl/strings/string_view.h" -#include "absl/types/span.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace cord_internal { -namespace { - -using testing::Eq; - -// Creates a flat for testing -CordRep* MakeFlat(absl::string_view s) { - CordRepFlat* flat = CordRepFlat::New(s.length()); - memcpy(flat->Data(), s.data(), s.length()); - flat->length = s.length(); - return flat; -} - -CordRepRing* FromFlats(Span<absl::string_view const> flats) { - CordRepRing* ring = CordRepRing::Create(MakeFlat(flats[0]), flats.size() - 1); - for (int i = 1; i < flats.size(); ++i) { - ring = CordRepRing::Append(ring, MakeFlat(flats[i])); - } - return ring; -} - -std::array<absl::string_view, 12> TestFlats() { - return {"abcdefghij", "klmnopqrst", "uvwxyz", "ABCDEFGHIJ", - "KLMNOPQRST", "UVWXYZ", "1234567890", "~!@#$%^&*()_", - "+-=", "[]\\{}|;':", ",/<>?", "."}; -} - -TEST(CordRingReaderTest, DefaultInstance) { - CordRepRingReader reader; - EXPECT_FALSE(static_cast<bool>(reader)); - EXPECT_THAT(reader.ring(), Eq(nullptr)); -#ifndef NDEBUG - EXPECT_DEATH_IF_SUPPORTED(reader.length(), ".*"); - EXPECT_DEATH_IF_SUPPORTED(reader.consumed(), ".*"); - EXPECT_DEATH_IF_SUPPORTED(reader.remaining(), ".*"); - EXPECT_DEATH_IF_SUPPORTED(reader.Next(), ".*"); - EXPECT_DEATH_IF_SUPPORTED(reader.Seek(0), ".*"); -#endif -} - -TEST(CordRingReaderTest, Reset) { - CordRepRingReader reader; - auto flats = TestFlats(); - CordRepRing* ring = FromFlats(flats); - - absl::string_view first = reader.Reset(ring); - EXPECT_THAT(first, Eq(flats[0])); - EXPECT_TRUE(static_cast<bool>(reader)); - EXPECT_THAT(reader.ring(), Eq(ring)); - EXPECT_THAT(reader.index(), Eq(ring->head())); - EXPECT_THAT(reader.node(), Eq(ring->entry_child(ring->head()))); - EXPECT_THAT(reader.length(), Eq(ring->length)); - EXPECT_THAT(reader.consumed(), Eq(flats[0].length())); - EXPECT_THAT(reader.remaining(), Eq(ring->length - reader.consumed())); - - reader.Reset(); - EXPECT_FALSE(static_cast<bool>(reader)); - EXPECT_THAT(reader.ring(), Eq(nullptr)); - - CordRep::Unref(ring); -} - -TEST(CordRingReaderTest, Next) { - CordRepRingReader reader; - auto flats = TestFlats(); - CordRepRing* ring = FromFlats(flats); - CordRepRing::index_type head = ring->head(); - - reader.Reset(ring); - size_t consumed = reader.consumed(); - size_t remaining = reader.remaining(); - for (int i = 1; i < flats.size(); ++i) { - CordRepRing::index_type index = ring->advance(head, i); - consumed += flats[i].length(); - remaining -= flats[i].length(); - absl::string_view next = reader.Next(); - ASSERT_THAT(next, Eq(flats[i])); - ASSERT_THAT(reader.index(), Eq(index)); - ASSERT_THAT(reader.node(), Eq(ring->entry_child(index))); - ASSERT_THAT(reader.consumed(), Eq(consumed)); - ASSERT_THAT(reader.remaining(), Eq(remaining)); - } - -#ifndef NDEBUG - EXPECT_DEATH_IF_SUPPORTED(reader.Next(), ".*"); -#endif - - CordRep::Unref(ring); -} - -TEST(CordRingReaderTest, SeekForward) { - CordRepRingReader reader; - auto flats = TestFlats(); - CordRepRing* ring = FromFlats(flats); - CordRepRing::index_type head = ring->head(); - - reader.Reset(ring); - size_t consumed = 0; - size_t remaining = ring->length; - for (int i = 0; i < flats.size(); ++i) { - CordRepRing::index_type index = ring->advance(head, i); - size_t offset = consumed; - consumed += flats[i].length(); - remaining -= flats[i].length(); - for (int off = 0; off < flats[i].length(); ++off) { - absl::string_view chunk = reader.Seek(offset + off); - ASSERT_THAT(chunk, Eq(flats[i].substr(off))); - ASSERT_THAT(reader.index(), Eq(index)); - ASSERT_THAT(reader.node(), Eq(ring->entry_child(index))); - ASSERT_THAT(reader.consumed(), Eq(consumed)); - ASSERT_THAT(reader.remaining(), Eq(remaining)); - } - } - - CordRep::Unref(ring); -} - -TEST(CordRingReaderTest, SeekBackward) { - CordRepRingReader reader; - auto flats = TestFlats(); - CordRepRing* ring = FromFlats(flats); - CordRepRing::index_type head = ring->head(); - - reader.Reset(ring); - size_t consumed = ring->length; - size_t remaining = 0; - for (int i = flats.size() - 1; i >= 0; --i) { - CordRepRing::index_type index = ring->advance(head, i); - size_t offset = consumed - flats[i].length(); - for (int off = 0; off < flats[i].length(); ++off) { - absl::string_view chunk = reader.Seek(offset + off); - ASSERT_THAT(chunk, Eq(flats[i].substr(off))); - ASSERT_THAT(reader.index(), Eq(index)); - ASSERT_THAT(reader.node(), Eq(ring->entry_child(index))); - ASSERT_THAT(reader.consumed(), Eq(consumed)); - ASSERT_THAT(reader.remaining(), Eq(remaining)); - } - consumed -= flats[i].length(); - remaining += flats[i].length(); - } -#ifndef NDEBUG - EXPECT_DEATH_IF_SUPPORTED(reader.Seek(ring->length), ".*"); -#endif - CordRep::Unref(ring); -} - -} // namespace -} // namespace cord_internal -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/strings/cord_ring_test.cc b/absl/strings/cord_ring_test.cc deleted file mode 100644 index 74f57c77..00000000 --- a/absl/strings/cord_ring_test.cc +++ /dev/null @@ -1,1458 +0,0 @@ -// 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 <cassert> -#include <cstdlib> -#include <cstring> -#include <ctime> -#include <iostream> -#include <ostream> -#include <random> -#include <sstream> -#include <string> -#include <vector> - -#include "gmock/gmock.h" -#include "gtest/gtest.h" -#include "absl/base/config.h" -#include "absl/strings/internal/cord_internal.h" -#include "absl/strings/internal/cord_rep_flat.h" -#include "absl/strings/internal/cord_rep_ring.h" -#include "absl/strings/str_cat.h" -#include "absl/strings/string_view.h" -#include "absl/types/span.h" - -extern thread_local bool cord_ring; - -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::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<TestParam>; - -// 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 : true; -} - -// 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 : true; -} - -// Matcher validating a shared ring was re-allocated. Should only be used for -// tests doing exactly one update as subsequent updates could return the -// original (freed and re-used) pointer. -MATCHER_P2(NeIfShared, param, rep, - absl::StrCat("Not equal 0x", absl::Hex(rep), " if shared")) { - return param.refcount_is_one ? true : 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<string_view> ToFlats(const CordRepRing* r) { - std::vector<string_view> 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<const char*>(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<not_a_string_view> ToRawFlats(const CordRepRing* r) { - std::vector<not_a_string_view> 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<Rep*>(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 = reinterpret_cast<const char*>(this->storage); - this->length = len; - this->releaser_invoker = [](CordRepExternal* self) { - delete static_cast<Rep*>(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); -} - -enum Composition { kMix, kAppend, kPrepend }; - -Composition RandomComposition() { - RandomEngine rng(GTEST_FLAG_GET(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"}; - -CordRepRing* FromFlats(Span<const char* const> 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<int>(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<TestParam>& info) { - return info.param.ToString(); -} - -class CordRingTest : public testing::Test { - public: - ~CordRingTest() override { - for (CordRep* rep : unrefs_) { - CordRep::Unref(rep); - } - } - - template <typename CordRepType> - CordRepType* NeedsUnref(CordRepType* rep) { - assert(rep); - unrefs_.push_back(rep); - return rep; - } - - template <typename CordRepType> - CordRepType* Ref(CordRepType* rep) { - CordRep::Ref(rep); - return NeedsUnref(rep); - } - - private: - std::vector<CordRep*> unrefs_; -}; - -class CordRingTestWithParam : public testing::TestWithParam<TestParam> { - public: - ~CordRingTestWithParam() override { - for (CordRep* rep : unrefs_) { - CordRep::Unref(rep); - } - } - - 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 <typename CordRepType> - CordRepType* NeedsUnref(CordRepType* rep) { - assert(rep); - unrefs_.push_back(rep); - return rep; - } - - template <typename CordRepType> - CordRepType* Ref(CordRepType* rep) { - CordRep::Ref(rep); - return NeedsUnref(rep); - } - - template <typename CordRepType> - CordRepType* RefIfShared(CordRepType* rep) { - return Shared() ? Ref(rep) : rep; - } - - template <typename CordRepType> - CordRepType* RefIfInputShared(CordRepType* rep) { - return InputShared() ? Ref(rep) : rep; - } - - template <typename CordRepType> - CordRepType* RefIfInputSharedIndirect(CordRepType* rep) { - return InputSharedIndirect() ? Ref(rep) : rep; - } - - private: - std::vector<CordRep*> unrefs_; -}; - -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_SUITE_P(WithParam, CordRingSubTest, - testing::ValuesIn(CordRingSubTest::CreateTestParams()), - TestParamToString); - -INSTANTIATE_TEST_SUITE_P( - WithParam, CordRingCreateTest, - testing::ValuesIn(CordRingCreateTest::CreateTestParams()), - TestParamToString); - -INSTANTIATE_TEST_SUITE_P( - WithParam, CordRingCreateFromTreeTest, - testing::ValuesIn(CordRingCreateFromTreeTest::CreateTestParams()), - TestParamToString); - -INSTANTIATE_TEST_SUITE_P( - WithParam, CordRingBuildTest, - testing::ValuesIn(CordRingBuildTest::CreateTestParams()), - TestParamToString); - -INSTANTIATE_TEST_SUITE_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)); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAreArray(kFoxFlats)); -} - -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)); -} - -TEST_F(CordRingTest, CreateWithIllegalExtraCapacity) { -#if defined(ABSL_HAVE_EXCEPTIONS) - CordRep* flat = NeedsUnref(MakeFlat("Hello world")); - try { - CordRepRing::Create(flat, CordRepRing::kMaxCapacity); - GTEST_FAIL() << "expected std::length_error exception"; - } catch (const std::length_error&) { - } -#elif defined(GTEST_HAS_DEATH_TEST) - CordRep* flat = NeedsUnref(MakeFlat("Hello world")); - EXPECT_DEATH(CordRepRing::Create(flat, CordRepRing::kMaxCapacity), ".*"); -#endif -} - -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))); -} - -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)); -} - -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))); -} - -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)); -} - -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)); -} - -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)); -} - -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)); -} - -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, NeIfShared(GetParam(), ring)); - EXPECT_THAT(result->length, Eq(str1.size() + str2.size())); - EXPECT_THAT(ToFlats(result), ElementsAre(str1, str2)); -} - -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, NeIfShared(GetParam(), ring)); - EXPECT_THAT(result->length, Eq(str1.size() + str2.size())); - EXPECT_THAT(ToFlats(result), ElementsAre(str2, str1)); -} - -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, NeIfShared(GetParam(), ring)); - EXPECT_THAT(result->length, Eq(str1.size() + str2.size())); - EXPECT_THAT(ToFlats(result), ElementsAre(str1, str2)); -} - -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)); - EXPECT_THAT(result, NeIfShared(GetParam(), ring)); -} - -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)); - EXPECT_THAT(result, NeIfShared(GetParam(), ring)); - if (GetParam().refcount_is_one) { - EXPECT_THAT(ToFlats(result), ElementsAre(StrCat(str1, str1a), str2a)); - } else { - EXPECT_THAT(ToFlats(result), ElementsAre(str1, str2)); - } -} - -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, NeIfShared(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)); - } -} - -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, NeIfShared(GetParam(), ring)); - EXPECT_THAT(result->length, Eq(4 + str2.size())); - EXPECT_THAT(ToFlats(result), ElementsAre("1234", str2)); - - 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))); -} - -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)); -} - -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, NeIfShared(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")); - } -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre(str2, str1a)); - 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)); -} - -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]); - } - NeedsUnref(result); - ASSERT_THAT(result, IsValidRingBuffer()); - EXPECT_THAT(result, EqIfPrivateAndCapacity(GetParam(), ring)); - EXPECT_THAT(ToString(result), kFox); -} - -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")); - } -} - -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")); - } -} - -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); - - 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(result, NeIfShared(GetParam(), ring)); - ASSERT_THAT(ToString(result), Eq(all.substr(offset, len))); - } - } -} - -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); - - 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)); - ASSERT_THAT(result, NeIfShared(GetParam(), ring)); - auto str = ToString(result); - ASSERT_THAT(str, SizeIs(len)); - ASSERT_THAT(str, Eq(all.substr(offset, len))); - } - } -} - -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); - - 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)); - ASSERT_THAT(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToString(result), Eq(all.substr(len))); - } -} - -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))); -} - -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); - - for (size_t len = 1; len < all.size(); ++len) { - ring = RefIfShared(FromFlats(flats, composition)); - result = NeedsUnref(CordRepRing::RemoveSuffix(ring, len)); - ASSERT_THAT(result, IsValidRingBuffer()); - ASSERT_THAT(result, EqIfPrivate(GetParam(), ring)); - ASSERT_THAT(result, NeIfShared(GetParam(), ring)); - ASSERT_THAT(ToString(result), Eq(all.substr(0, all.size() - len))); - } -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAreArray(kFoxFlats)); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("Head", "brown ", "fox ", "jumps ", - "over ", "the ", "lazy ", "dog")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), - ElementsAre("Head", "umps ", "over ", "the ", "lazy ", "dog")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("Head", "The ", "quick ", "brown ", - "fox ", "jumps ", "over ", "the ")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("Head", "The ", "quick ", "brown ", - "fox ", "jumps ", "ov")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), - ElementsAre("Head", "ck ", "brown ", "fox ", "jum")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("Head", "row")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("Prepend", "Head", "row")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAreArray(kFoxFlats)); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("brown ", "fox ", "jumps ", "over ", - "the ", "lazy ", "dog", "Tail")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), - ElementsAre("umps ", "over ", "the ", "lazy ", "dog", "Tail")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("The ", "quick ", "brown ", "fox ", - "jumps ", "over ", "the ", "Tail")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("The ", "quick ", "brown ", "fox ", - "jumps ", "ov", "Tail")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), - ElementsAre("ck ", "brown ", "fox ", "jum", "Tail")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("row", "Tail")); -} - -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(result, NeIfShared(GetParam(), ring)); - EXPECT_THAT(ToFlats(result), ElementsAre("row", "Prepend", "Tail")); -} - -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])); - } -} - -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(); - } -} - -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])); - } -} - -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])); - } -} - -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])); - } -} - -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])); - } -} - -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])); - } -} - -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])); - } -} - -TEST_F(CordRingTest, IsFlatSingleFlat) { - for (bool external : {false, true}) { - SCOPED_TRACE(external ? "With External" : "With Flat"); - absl::string_view str = "Hello world"; - CordRep* rep = external ? MakeExternal(str) : MakeFlat(str); - CordRepRing* ring = NeedsUnref(CordRepRing::Create(rep)); - - // The ring is a single non-fragmented flat: - absl::string_view fragment; - EXPECT_TRUE(ring->IsFlat(nullptr)); - EXPECT_TRUE(ring->IsFlat(&fragment)); - EXPECT_THAT(fragment, Eq("Hello world")); - fragment = ""; - EXPECT_TRUE(ring->IsFlat(0, 11, nullptr)); - EXPECT_TRUE(ring->IsFlat(0, 11, &fragment)); - EXPECT_THAT(fragment, Eq("Hello world")); - - // Arbitrary ranges must check true as well. - EXPECT_TRUE(ring->IsFlat(1, 4, &fragment)); - EXPECT_THAT(fragment, Eq("ello")); - EXPECT_TRUE(ring->IsFlat(6, 5, &fragment)); - EXPECT_THAT(fragment, Eq("world")); - } -} - -TEST_F(CordRingTest, IsFlatMultiFlat) { - for (bool external : {false, true}) { - SCOPED_TRACE(external ? "With External" : "With Flat"); - absl::string_view str1 = "Hello world"; - absl::string_view str2 = "Halt and catch fire"; - CordRep* rep1 = external ? MakeExternal(str1) : MakeFlat(str1); - CordRep* rep2 = external ? MakeExternal(str2) : MakeFlat(str2); - CordRepRing* ring = CordRepRing::Append(CordRepRing::Create(rep1), rep2); - NeedsUnref(ring); - - // The ring is fragmented, IsFlat() on the entire cord must be false. - EXPECT_FALSE(ring->IsFlat(nullptr)); - absl::string_view fragment = "Don't touch this"; - EXPECT_FALSE(ring->IsFlat(&fragment)); - EXPECT_THAT(fragment, Eq("Don't touch this")); - - // Check for ranges exactly within both flats. - EXPECT_TRUE(ring->IsFlat(0, 11, &fragment)); - EXPECT_THAT(fragment, Eq("Hello world")); - EXPECT_TRUE(ring->IsFlat(11, 19, &fragment)); - EXPECT_THAT(fragment, Eq("Halt and catch fire")); - - // Check for arbitrary partial range inside each flat. - EXPECT_TRUE(ring->IsFlat(1, 4, &fragment)); - EXPECT_THAT(fragment, "ello"); - EXPECT_TRUE(ring->IsFlat(26, 4, &fragment)); - EXPECT_THAT(fragment, "fire"); - - // Check ranges spanning across both flats - fragment = "Don't touch this"; - EXPECT_FALSE(ring->IsFlat(1, 18, &fragment)); - EXPECT_FALSE(ring->IsFlat(10, 2, &fragment)); - EXPECT_THAT(fragment, Eq("Don't touch this")); - } -} - -TEST_F(CordRingTest, Dump) { - std::stringstream ss; - auto flats = MakeSpan(kFoxFlats); - CordRepRing* ring = NeedsUnref(FromFlats(flats, kPrepend)); - ss << *ring; -} - -} // namespace -ABSL_NAMESPACE_END -} // namespace absl diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc index 36478890..aba555fb 100644 --- a/absl/strings/cord_test.cc +++ b/absl/strings/cord_test.cc @@ -2110,8 +2110,6 @@ TEST_P(CordTest, DiabolicalGrowth) { // This test exercises a diabolical Append(<one char>) on a cord, making the // cord shared before each Append call resulting in a terribly fragmented // resulting cord. - // TODO(b/183983616): Apply some minimum compaction when copying a shared - // source cord into a mutable copy for updates in CordRepRing. RandomEngine rng(GTEST_FLAG_GET(random_seed)); const std::string expected = RandomLowercaseString(&rng, 5000); absl::Cord cord; diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc index b7874385..57d9d385 100644 --- a/absl/strings/internal/cord_internal.cc +++ b/absl/strings/internal/cord_internal.cc @@ -22,15 +22,12 @@ #include "absl/strings/internal/cord_rep_btree.h" #include "absl/strings/internal/cord_rep_crc.h" #include "absl/strings/internal/cord_rep_flat.h" -#include "absl/strings/internal/cord_rep_ring.h" #include "absl/strings/str_cat.h" namespace absl { ABSL_NAMESPACE_BEGIN namespace cord_internal { -ABSL_CONST_INIT std::atomic<bool> cord_ring_buffer_enabled( - kCordEnableRingBufferDefault); ABSL_CONST_INIT std::atomic<bool> shallow_subcords_enabled( kCordShallowSubcordsDefault); @@ -47,9 +44,6 @@ void CordRep::Destroy(CordRep* rep) { if (rep->tag == BTREE) { CordRepBtree::Destroy(rep->btree()); return; - } else if (rep->tag == RING) { - CordRepRing::Destroy(rep->ring()); - return; } else if (rep->tag == EXTERNAL) { CordRepExternal::Delete(rep); return; diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index 9ec6b2a6..a487fd59 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h @@ -55,24 +55,15 @@ struct CordRepExternal; struct CordRepFlat; struct CordRepSubstring; struct CordRepCrc; -class CordRepRing; class CordRepBtree; class CordzInfo; // Default feature enable states for cord ring buffers -enum CordFeatureDefaults { - kCordEnableRingBufferDefault = false, - kCordShallowSubcordsDefault = false -}; +enum CordFeatureDefaults { kCordShallowSubcordsDefault = false }; -extern std::atomic<bool> cord_ring_buffer_enabled; extern std::atomic<bool> shallow_subcords_enabled; -inline void enable_cord_ring_buffer(bool enable) { - cord_ring_buffer_enabled.store(enable, std::memory_order_relaxed); -} - inline void enable_shallow_subcords(bool enable) { shallow_subcords_enabled.store(enable, std::memory_order_relaxed); } @@ -215,7 +206,7 @@ enum CordRepKind { SUBSTRING = 1, CRC = 2, BTREE = 3, - RING = 4, + UNUSED_4 = 4, EXTERNAL = 5, // We have different tags for different sized flat arrays, @@ -234,12 +225,8 @@ enum CordRepKind { // There are various locations where we want to check if some rep is a 'plain' // data edge, i.e. an external or flat rep. By having FLAT == EXTERNAL + 1, we // can perform this check in a single branch as 'tag >= EXTERNAL' -// Likewise, we have some locations where we check for 'ring or external/flat', -// so likewise align RING to EXTERNAL. // Note that we can leave this optimization to the compiler. The compiler will // DTRT when it sees a condition like `tag == EXTERNAL || tag >= FLAT`. -static_assert(RING == BTREE + 1, "BTREE and RING not consecutive"); -static_assert(EXTERNAL == RING + 1, "BTREE and EXTERNAL not consecutive"); static_assert(FLAT == EXTERNAL + 1, "EXTERNAL and FLAT not consecutive"); struct CordRep { @@ -283,15 +270,12 @@ struct CordRep { // # LINT.ThenChange(cord_rep_btree.h:copy_raw) // Returns true if this instance's tag matches the requested type. - constexpr bool IsRing() const { return tag == RING; } constexpr bool IsSubstring() const { return tag == SUBSTRING; } constexpr bool IsCrc() const { return tag == CRC; } constexpr bool IsExternal() const { return tag == EXTERNAL; } constexpr bool IsFlat() const { return tag >= FLAT; } constexpr bool IsBtree() const { return tag == BTREE; } - inline CordRepRing* ring(); - inline const CordRepRing* ring() const; inline CordRepSubstring* substring(); inline const CordRepSubstring* substring() const; inline CordRepCrc* crc(); diff --git a/absl/strings/internal/cord_rep_ring.cc b/absl/strings/internal/cord_rep_ring.cc deleted file mode 100644 index af2fc768..00000000 --- a/absl/strings/internal/cord_rep_ring.cc +++ /dev/null @@ -1,773 +0,0 @@ -// 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 <cassert> -#include <cstddef> -#include <cstdint> -#include <iostream> -#include <limits> -#include <memory> -#include <string> - -#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_consume.h" -#include "absl/strings/internal/cord_rep_flat.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace cord_internal { - -namespace { - -using index_type = CordRepRing::index_type; - -enum class Direction { kForward, kReversed }; - -inline bool IsFlatOrExternal(CordRep* rep) { - return rep->IsFlat() || rep->IsExternal(); -} - -// 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"); - } -} - -// 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 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()); - } - } - }); -} - -} // 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<ptrdiff_t>(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<int>(child->tag) - << ", rc = " << child->refcount.Get() - << ", offset = " << rep.entry_data_offset(head) - << ", end_pos = " << static_cast<ptrdiff_t>(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<offset_type>(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_type>(offset); - pos_ = rep_->advance(pos_); - } - - private: - CordRepRing* rep_; - index_type head_; - index_type pos_; -}; - -#ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL -constexpr size_t CordRepRing::kMaxCapacity; -#endif - -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<int>(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 child's 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<index_type>(capacity)); - rep->tag = RING; - rep->capacity_ = static_cast<index_type>(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<index_type>(capacity); -} - -void CordRepRing::Delete(CordRepRing* rep) { - assert(rep != nullptr && rep->IsRing()); -#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 <bool ref> -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<true>(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(); - - if (!rep->refcount.IsOne()) { - return Copy(rep, rep->head(), rep->tail(), extra); - } else if (entries + extra > rep->capacity()) { - const size_t min_grow = rep->capacity() + rep->capacity() / 2; - const size_t min_extra = (std::max)(extra, min_grow - entries); - CordRepRing* newrep = CordRepRing::New(entries, min_extra); - newrep->Fill<false>(rep, rep->head(), rep->tail()); - CordRepRing::Delete(rep); - return newrep; - } else { - return rep; - } -} - -Span<char> 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<char> 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<offset_type>(data_offset); - return {child->flat()->Data() + data_offset, n}; - } - return {nullptr, 0}; -} - -CordRepRing* CordRepRing::CreateFromLeaf(CordRep* child, size_t offset, - size_t len, size_t extra) { - CordRepRing* rep = CordRepRing::New(1, extra); - rep->head_ = 0; - rep->tail_ = rep->advance(0); - rep->length = len; - rep->entry_end_pos()[0] = len; - rep->entry_child()[0] = child; - rep->entry_data_offset()[0] = static_cast<offset_type>(offset); - return Validate(rep); -} - -CordRepRing* CordRepRing::CreateSlow(CordRep* child, size_t extra) { - CordRepRing* rep = nullptr; - Consume(child, [&](CordRep* child_arg, size_t offset, size_t len) { - if (IsFlatOrExternal(child_arg)) { - rep = rep ? AppendLeaf(rep, child_arg, offset, len) - : CreateFromLeaf(child_arg, offset, len, extra); - } else if (rep) { - rep = AddRing<AddMode::kAppend>(rep, child_arg->ring(), offset, len); - } else if (offset == 0 && child_arg->length == len) { - rep = Mutable(child_arg->ring(), extra); - } else { - rep = SubRing(child_arg->ring(), offset, len, 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->IsRing()) { - return Mutable(child->ring(), extra); - } - return CreateSlow(child, extra); -} - -template <CordRepRing::AddMode mode> -CordRepRing* CordRepRing::AddRing(CordRepRing* rep, CordRepRing* ring, - size_t offset, size_t len) { - assert(offset < ring->length); - constexpr bool append = mode == AddMode::kAppend; - Position head = ring->Find(offset); - Position tail = ring->FindTail(head.index, offset + len); - 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_ - len) - - 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 += len; - if (append) { - rep->tail_ = filler.pos(); - } else { - rep->head_ = filler.head(); - rep->begin_pos_ -= len; - } - - return Validate(rep); -} - -CordRepRing* CordRepRing::AppendSlow(CordRepRing* rep, CordRep* child) { - Consume(child, [&rep](CordRep* child_arg, size_t offset, size_t len) { - if (child_arg->IsRing()) { - rep = AddRing<AddMode::kAppend>(rep, child_arg->ring(), offset, len); - } else { - rep = AppendLeaf(rep, child_arg, offset, len); - } - }); - return rep; -} - -CordRepRing* CordRepRing::AppendLeaf(CordRepRing* rep, CordRep* child, - size_t offset, size_t len) { - 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 += len; - rep->entry_end_pos()[back] = begin_pos + len; - rep->entry_child()[back] = child; - rep->entry_data_offset()[back] = static_cast<offset_type>(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->IsRing()) { - return AddRing<AddMode::kAppend>(rep, child->ring(), 0, length); - } - return AppendSlow(rep, child); -} - -CordRepRing* CordRepRing::PrependSlow(CordRepRing* rep, CordRep* child) { - ReverseConsume(child, [&](CordRep* child_arg, size_t offset, size_t len) { - if (IsFlatOrExternal(child_arg)) { - rep = PrependLeaf(rep, child_arg, offset, len); - } else { - rep = AddRing<AddMode::kPrepend>(rep, child_arg->ring(), offset, len); - } - }); - return Validate(rep); -} - -CordRepRing* CordRepRing::PrependLeaf(CordRepRing* rep, CordRep* child, - size_t offset, size_t len) { - rep = Mutable(rep, 1); - index_type head = rep->retreat(rep->head_); - pos_type end_pos = rep->begin_pos_; - rep->head_ = head; - rep->length += len; - rep->begin_pos_ -= len; - rep->entry_end_pos()[head] = end_pos; - rep->entry_child()[head] = child; - rep->entry_data_offset()[head] = static_cast<offset_type>(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->IsRing()) { - return AddRing<AddMode::kPrepend>(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<char> 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<char> 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<index_type>(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 <bool wrap> -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<false>(head, tail, offset); - } - } else { - index_type count = capacity_ + tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<true>(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<false>(head, tail, tail_offset); - } - } else { - index_type count = capacity_ + tail - head; - if (count > kBinarySearchThreshold) { - head = FindBinary<true>(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 len, size_t extra) { - assert(offset <= rep->length); - assert(offset <= rep->length - len); - - if (len == 0) { - CordRep::Unref(rep); - return nullptr; - } - - // Find position of first byte - Position head = rep->Find(offset); - Position tail = rep->FindTail(head.index, offset + len); - 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 = len; - 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); -} - -} // 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 deleted file mode 100644 index 79a2fdb1..00000000 --- a/absl/strings/internal/cord_rep_ring.h +++ /dev/null @@ -1,607 +0,0 @@ -// 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 <cassert> -#include <cstddef> -#include <cstdint> -#include <iosfwd> -#include <limits> -#include <memory> - -#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 { - -// 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 = size_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<uint32_t>::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<char> 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<char> GetPrependBuffer(size_t size); - - // Returns a cord ring buffer containing `len` 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 len, - size_t extra = 0); - - // Returns a cord ring buffer with the first `len` 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 len, - size_t extra = 0); - - // Returns a cord ring buffer with the last `len` 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; - - // Returns true if this instance manages a single contiguous buffer, in which - // case the (optional) output parameter `fragment` is set. Otherwise, the - // function returns false, and `fragment` is left unchanged. - bool IsFlat(absl::string_view* fragment) const; - - // Returns true if the data starting at `offset` with length `len` is - // managed by this instance inside a single contiguous buffer, in which case - // the (optional) output parameter `fragment` is set to the contiguous memory - // starting at offset `offset` with length `length`. Otherwise, the function - // returns false, and `fragment` is left unchanged. - bool IsFlat(size_t offset, size_t len, absl::string_view* fragment) 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 <typename F> - 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 <typename F> - void ForEach(F&& f) const { - ForEach(head_, tail_, std::forward<F>(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<pos_type, CordRep*, offset_type>; - - 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 <bool wrap> - 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 <bool ref> - 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 maximum 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 `len`. - template <AddMode mode> - static CordRepRing* AddRing(CordRepRing* rep, CordRepRing* ring, - size_t offset, size_t len); - - // Increases the data offset for entry `index` by `n`. - void AddDataOffset(index_type index, size_t n); - - // Decreases 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); -} - -// Now that CordRepRing is defined, we can define CordRep's helper casts: -inline CordRepRing* CordRep::ring() { - assert(IsRing()); - return static_cast<CordRepRing*>(this); -} - -inline const CordRepRing* CordRep::ring() const { - assert(IsRing()); - return static_cast<const CordRepRing*>(this); -} - -inline bool CordRepRing::IsFlat(absl::string_view* fragment) const { - if (entries() == 1) { - if (fragment) *fragment = entry_data(head()); - return true; - } - return false; -} - -inline bool CordRepRing::IsFlat(size_t offset, size_t len, - absl::string_view* fragment) const { - const Position pos = Find(offset); - const absl::string_view data = entry_data(pos.index); - if (data.length() >= len && data.length() - len >= pos.offset) { - if (fragment) *fragment = data.substr(pos.offset, len); - return true; - } - return false; -} - -std::ostream& operator<<(std::ostream& s, const CordRepRing& rep); - -} // namespace cord_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_STRINGS_INTERNAL_CORD_REP_RING_H_ diff --git a/absl/strings/internal/cord_rep_ring_reader.h b/absl/strings/internal/cord_rep_ring_reader.h deleted file mode 100644 index 7ceeaa00..00000000 --- a/absl/strings/internal/cord_rep_ring_reader.h +++ /dev/null @@ -1,118 +0,0 @@ -// Copyright 2021 The Abseil Authors -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - -#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_RING_READER_H_ -#define ABSL_STRINGS_INTERNAL_CORD_REP_RING_READER_H_ - -#include <cassert> -#include <cstddef> -#include <cstdint> - -#include "absl/strings/internal/cord_internal.h" -#include "absl/strings/internal/cord_rep_ring.h" -#include "absl/strings/string_view.h" - -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace cord_internal { - -// CordRepRingReader provides basic navigation over CordRepRing data. -class CordRepRingReader { - public: - // Returns true if this instance is not empty. - explicit operator bool() const { return ring_ != nullptr; } - - // Returns the ring buffer reference for this instance, or nullptr if empty. - CordRepRing* ring() const { return ring_; } - - // Returns the current node index inside the ring buffer for this instance. - // The returned value is undefined if this instance is empty. - CordRepRing::index_type index() const { return index_; } - - // Returns the current node inside the ring buffer for this instance. - // The returned value is undefined if this instance is empty. - CordRep* node() const { return ring_->entry_child(index_); } - - // Returns the length of the referenced ring buffer. - // Requires the current instance to be non empty. - size_t length() const { - assert(ring_); - return ring_->length; - } - - // Returns the end offset of the last navigated-to chunk, which represents the - // total bytes 'consumed' relative to the start of the ring. The returned - // value is never zero. For example, initializing a reader with a ring buffer - // with a first chunk of 19 bytes will return consumed() = 19. - // Requires the current instance to be non empty. - size_t consumed() const { - assert(ring_); - return ring_->entry_end_offset(index_); - } - - // Returns the number of bytes remaining beyond the last navigated-to chunk. - // Requires the current instance to be non empty. - size_t remaining() const { - assert(ring_); - return length() - consumed(); - } - - // Resets this instance to an empty value - void Reset() { ring_ = nullptr; } - - // Resets this instance to the start of `ring`. `ring` must not be null. - // Returns a reference into the first chunk of the provided ring. - absl::string_view Reset(CordRepRing* ring) { - assert(ring); - ring_ = ring; - index_ = ring_->head(); - return ring_->entry_data(index_); - } - - // Navigates to the next chunk inside the reference ring buffer. - // Returns a reference into the navigated-to chunk. - // Requires remaining() to be non zero. - absl::string_view Next() { - assert(remaining()); - index_ = ring_->advance(index_); - return ring_->entry_data(index_); - } - - // Navigates to the chunk at offset `offset`. - // Returns a reference into the navigated-to chunk, adjusted for the relative - // position of `offset` into that chunk. For example, calling Seek(13) on a - // ring buffer containing 2 chunks of 10 and 20 bytes respectively will return - // a string view into the second chunk starting at offset 3 with a size of 17. - // Requires `offset` to be less than `length()` - absl::string_view Seek(size_t offset) { - assert(offset < length()); - size_t current = ring_->entry_end_offset(index_); - CordRepRing::index_type hint = (offset >= current) ? index_ : ring_->head(); - const CordRepRing::Position head = ring_->Find(hint, offset); - index_ = head.index; - auto data = ring_->entry_data(head.index); - data.remove_prefix(head.offset); - return data; - } - - private: - CordRepRing* ring_ = nullptr; - CordRepRing::index_type index_; -}; - -} // namespace cord_internal -ABSL_NAMESPACE_END -} // namespace absl - -#endif // ABSL_STRINGS_INTERNAL_CORD_REP_RING_READER_H_ diff --git a/absl/strings/internal/cordz_info.cc b/absl/strings/internal/cordz_info.cc index b830c25c..b24c3da7 100644 --- a/absl/strings/internal/cordz_info.cc +++ b/absl/strings/internal/cordz_info.cc @@ -21,7 +21,6 @@ #include "absl/strings/internal/cord_internal.h" #include "absl/strings/internal/cord_rep_btree.h" #include "absl/strings/internal/cord_rep_crc.h" -#include "absl/strings/internal/cord_rep_ring.h" #include "absl/strings/internal/cordz_handle.h" #include "absl/strings/internal/cordz_statistics.h" #include "absl/strings/internal/cordz_update_tracker.h" @@ -97,14 +96,11 @@ class CordRepAnalyzer { repref = CountLinearReps(repref, memory_usage_); switch (repref.tag()) { - case CordRepKind::RING: - AnalyzeRing(repref); - break; case CordRepKind::BTREE: AnalyzeBtree(repref); break; default: - // We should have either a btree or ring node if not null. + // We should have a btree node if not null. ABSL_ASSERT(repref.tag() == CordRepKind::UNUSED_0); break; } @@ -204,17 +200,6 @@ class CordRepAnalyzer { return rep; } - // Analyzes the provided ring. - void AnalyzeRing(RepRef rep) { - statistics_.node_count++; - statistics_.node_counts.ring++; - const CordRepRing* ring = rep.rep->ring(); - memory_usage_.Add(CordRepRing::AllocSize(ring->capacity()), rep.refcount); - ring->ForEach([&](CordRepRing::index_type pos) { - CountLinearReps(rep.Child(ring->entry_child(pos)), memory_usage_); - }); - } - // Analyzes the provided btree. void AnalyzeBtree(RepRef rep) { statistics_.node_count++; diff --git a/absl/strings/internal/cordz_info_statistics_test.cc b/absl/strings/internal/cordz_info_statistics_test.cc index aad3b1ec..d55773f2 100644 --- a/absl/strings/internal/cordz_info_statistics_test.cc +++ b/absl/strings/internal/cordz_info_statistics_test.cc @@ -25,7 +25,6 @@ #include "absl/strings/internal/cord_rep_btree.h" #include "absl/strings/internal/cord_rep_crc.h" #include "absl/strings/internal/cord_rep_flat.h" -#include "absl/strings/internal/cord_rep_ring.h" #include "absl/strings/internal/cordz_info.h" #include "absl/strings/internal/cordz_sample_token.h" #include "absl/strings/internal/cordz_statistics.h" @@ -123,11 +122,6 @@ size_t SizeOf(const CordRepExternal* rep) { return sizeof(CordRepExternalImpl<intptr_t>) + rep->length; } -template <> -size_t SizeOf(const CordRepRing* rep) { - return CordRepRing::AllocSize(rep->capacity()); -} - // Computes fair share memory used in a naive 'we dare to recurse' way. double FairShareImpl(CordRep* rep, size_t ref) { double self = 0.0, children = 0.0; @@ -144,11 +138,6 @@ double FairShareImpl(CordRep* rep, size_t ref) { for (CordRep*edge : rep->btree()->Edges()) { children += FairShareImpl(edge, ref); } - } else if (rep->tag == RING) { - self = SizeOf(rep->ring()); - rep->ring()->ForEach([&](CordRepRing::index_type i) { - self += FairShareImpl(rep->ring()->entry_child(i), 1); - }); } else { assert(false); } @@ -294,64 +283,6 @@ TEST(CordzInfoStatisticsTest, SharedSubstring) { EXPECT_THAT(SampleCord(substring), EqStatistics(expected)); } - -TEST(CordzInfoStatisticsTest, Ring) { - RefHelper ref; - auto* flat1 = Flat(240); - auto* flat2 = Flat(2000); - auto* flat3 = Flat(70); - auto* external = External(3000); - CordRepRing* ring = CordRepRing::Create(flat1); - ring = CordRepRing::Append(ring, flat2); - ring = CordRepRing::Append(ring, flat3); - ring = ref.NeedsUnref(CordRepRing::Append(ring, external)); - - CordzStatistics expected; - expected.size = ring->length; - expected.estimated_memory_usage = SizeOf(ring) + SizeOf(flat1) + - SizeOf(flat2) + SizeOf(flat3) + - SizeOf(external); - expected.estimated_fair_share_memory_usage = expected.estimated_memory_usage; - expected.node_count = 5; - expected.node_counts.flat = 3; - expected.node_counts.flat_128 = 1; - expected.node_counts.flat_256 = 1; - expected.node_counts.external = 1; - expected.node_counts.ring = 1; - - EXPECT_THAT(SampleCord(ring), EqStatistics(expected)); -} - -TEST(CordzInfoStatisticsTest, SharedSubstringRing) { - RefHelper ref; - auto* flat1 = ref.Ref(Flat(240)); - auto* flat2 = Flat(200); - auto* flat3 = Flat(70); - auto* external = ref.Ref(External(3000), 5); - CordRepRing* ring = CordRepRing::Create(flat1); - ring = CordRepRing::Append(ring, flat2); - ring = CordRepRing::Append(ring, flat3); - ring = ref.Ref(CordRepRing::Append(ring, external), 4); - auto* substring = ref.Ref(ref.NeedsUnref(Substring(ring))); - - - CordzStatistics expected; - expected.size = substring->length; - expected.estimated_memory_usage = SizeOf(ring) + SizeOf(flat1) + - SizeOf(flat2) + SizeOf(flat3) + - SizeOf(external) + SizeOf(substring); - expected.estimated_fair_share_memory_usage = FairShare(substring); - expected.node_count = 6; - expected.node_counts.flat = 3; - expected.node_counts.flat_128 = 1; - expected.node_counts.flat_256 = 2; - expected.node_counts.external = 1; - expected.node_counts.ring = 1; - expected.node_counts.substring = 1; - - EXPECT_THAT(SampleCord(substring), EqStatistics(expected)); -} - TEST(CordzInfoStatisticsTest, BtreeLeaf) { ASSERT_THAT(CordRepBtree::kMaxCapacity, Ge(3u)); RefHelper ref; @@ -528,14 +459,10 @@ TEST(CordzInfoStatisticsTest, ThreadSafety) { CordRep::Unref(cord.as_tree()); cord.set_inline_size(0); } else { - // Coin toss to 25% ring, 25% btree, and 50% flat. + // Coin toss to 50% btree, and 50% flat. CordRep* rep = Flat(256); if (coin_toss(gen) != 0) { - if (coin_toss(gen) != 0) { - rep = CordRepRing::Create(rep); - } else { - rep = CordRepBtree::Create(rep); - } + rep = CordRepBtree::Create(rep); } // Maybe CRC this cord |