summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
authorGravatar Martijn Vels <mvels@google.com>2023-09-08 11:18:54 -0700
committerGravatar Copybara-Service <copybara-worker@google.com>2023-09-08 11:19:54 -0700
commitefb035a5973b60d35ed8fcaa43e6736936a96173 (patch)
tree5d1a245997c1d47b339b355fdfddcecbf692818a /absl
parent09d29c580a30a463fac58ce8b926d283a07f656d (diff)
Remove CordRepRing experiment.
We have no intention to use it instead of the CordRepBtree implementation, so cleanup up and remove all code and references. PiperOrigin-RevId: 563803813 Change-Id: I95a67318d0f722f3eb7ecdcc7b6c87e28f2e26dd
Diffstat (limited to 'absl')
-rw-r--r--absl/strings/BUILD.bazel38
-rw-r--r--absl/strings/CMakeLists.txt38
-rw-r--r--absl/strings/cord.h1
-rw-r--r--absl/strings/cord_analysis.cc13
-rw-r--r--absl/strings/cord_ring_reader_test.cc180
-rw-r--r--absl/strings/cord_ring_test.cc1458
-rw-r--r--absl/strings/cord_test.cc2
-rw-r--r--absl/strings/internal/cord_internal.cc6
-rw-r--r--absl/strings/internal/cord_internal.h20
-rw-r--r--absl/strings/internal/cord_rep_ring.cc773
-rw-r--r--absl/strings/internal/cord_rep_ring.h607
-rw-r--r--absl/strings/internal/cord_rep_ring_reader.h118
-rw-r--r--absl/strings/internal/cordz_info.cc17
-rw-r--r--absl/strings/internal/cordz_info_statistics_test.cc77
14 files changed, 5 insertions, 3343 deletions
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